Уильям Стивенс - UNIX: разработка сетевых приложений
delta = measuredRTT - srtt
srtt ← srtt + g × delta
rttvar ← rttvar + h (|delta| - rttvar)
RTO = srtt + 4 × rttvar
delta — это разность между измеренным RTT и текущим сглаженным показателем RTT (srtt). g — это приращение, применяемое к показателю RTT, равное 1/8. h — это приращение, применяемое к сглаженному показателю среднего отклонения, равное ¼.
ПРИМЕЧАНИЕДва приращения и множитель 4 в вычислении RTO специально выражены степенями числа 2 и могут быть вычислены с использованием операций сдвига вместо деления и умножения. На самом деле реализация TCP в ядре (см. раздел 25.7 [128]) для ускорения вычислений обычно использует арифметику с фиксированной точкой, но мы для простоты используем в нашем коде вычисления с плавающей точкой.
Другой важный момент, отмеченный в [52], заключается в том, что по истечении времени таймера повторной передачи для следующего RTO должно использоваться экспоненциальное смещение (exponential backoff). Например, если наше первое значение RTO равно 2 с и за это время ответа не получено, следующее значение RTO будет равно 4 с. Если ответ все еще не последовал, следующее значение RTO будет 8 с, затем 16 и т.д.
Алгоритмы Джекобсона (Jacobson) реализуют вычисление RTO при измерении RTT и увеличение RTO при повторной передаче. Однако, когда клиент выполняет повторную передачу и получает ответ, возникает проблема неопределенности повторной передачи (retransmission ambiguity problem). На рис. 22.2 показаны три возможных сценария, при которых истекает время ожидания повторной передачи:
■ запрос потерян;
■ ответ потерян;
■ значение RTO слишком мало.
Рис. 22.2. Три сценария, возможные при истечении времени таймера повторной передачи
Когда клиент получает ответ на запрос, отправленный повторно, он не может сказать, какому из запросов соответствует ответ. На рисунке, изображенном справа, ответ соответствует начальному запросу, в то время как на двух других рисунках ответ соответствуют второму запросу.
Алгоритм Карна (Karn) [58] обрабатывает этот сценарий в соответствии со следующими правилами, применяемыми в любом случае, когда ответ получен на запрос, отправленный более одного раза:
■ Если для запроса и ответа было измерено значение RTT, не следует использовать его для обновления оценочных значений, так как мы не знаем, какому запросу соответствует ответ.
■ Поскольку ответ пришел до того, как истекло время нашего таймера повторной передачи, используйте для следующего пакета текущее значение RTO. Только когда мы получим ответ на запрос, который не был передан повторно, мы изменяем значение RTT и снова вычисляем RTO.
При написании наших функций RTT применить алгоритм Карна несложно, но оказывается, что существует и более изящное решение. Оно используется в расширениях TCP для сетей с высокой пропускной способностью, то есть сетей, обладающих либо широкой полосой пропускания, либо большим значением RTT, либо обоими этими свойствами (RFC 1323 [53]). Кроме добавления порядкового номера к началу каждого запроса, который сервер должен отразить, мы добавляем отметку времени, которую сервер также должен отразить. Каждый раз, отправляя запрос, мы сохраняем в этой отметке значение текущего времени. Когда приходит ответ, мы вычисляем величину RTT для этого пакета как текущее время минус значение отметки времени, отраженной сервером в своем ответе. Поскольку каждый запрос несет отметку времени, отражаемую сервером, мы можем вычислить RTT для каждого ответа, который мы получаем. Теперь нет никакой неопределенности. Более того, поскольку сервер только отражает отметку времени клиента, клиент может использовать для отметок времени любые удобные единицы, и при этом не требуется, чтобы клиент и сервер синхронизировали часы.
Пример
Свяжем теперь всю эту информацию воедино в примере. Мы начнем с функции main нашего клиента UDP, представленного в листинге 8.3, и изменим в ней только номер порта с SERV_PORT на 7 (стандартный эхо-сервер, см. табл. 2.1).
В листинге 22.4 показана функция dg_cli. Единственное изменение по сравнению с листингом 8.4 состоит в замене вызовов функций sendto и recvfrom вызовом нашей новой функции dg_send_recv.
Перед тем как представить функцию dg_send_recv и наши функции RTT, которые она вызывает, мы показываем в листинге 22.5 нашу схему реализации функциональных свойств, повышающих надежность клиента UDP. Все функции, имена которых начинаются с rtt_, описаны далее.
Листинг 22.4. Функция dg_cli, вызывающая нашу функцию dg_send_recv
//rtt/dg_cli.c
1 #include "unp.h"
2 ssize_t Dg_send_recv(int, const void*, size_t, void*, size_t,
3 const SA*, socklen_t);
4 void
5 dg_cli(FILE *fp, int sockfd, const SA *pservaddr, socklen_t servlen)
6 {
7 ssize_t n;
8 char sendline[MAXLINE], recvline[MAXLINE + 1];
9 while (Fgets(sendline, MAXLINE, fp) != NULL) {
10 n = Dg_send_recv(sockfd, sendline, strlen(sendline),
11 recvline, MAXLINE, pservaddr, servlen);
12 recvline[n] = 0; /* завершающий нуль */
13 Fputs(recvline, stdout);
14 }
15 }
Листинг 22.5. Схема функций RTT и последовательность их вызова
static sigjmp_buf jmpbuf;
{
формирование запроса
signal(SIGALRM, sig_alrm); /* устанавливаем обработчик сигнала */
rtt_newpack(); /* инициализируем значение счетчика rexmt нулем */
sendagain:
sendto();
alarm(rtt_start()); /* задаем аргумент функции alarm равным RTO */
if (sigsetjmp(jmpbuf, 1) != 0) {
if (rtt_timeout()) /* удваиваем RTO, обновляем оценочные значения */
отказываемся от дальнейших попыток
goto sendagain; /* повторная передача */
}
do {
recvfrom();
} while (неправильный порядковый номер);
alarm(0); /* отключаем сигнал alarm */
rtt_stop(); /* вычисляем RTT и обновляем оценочные значения */
обрабатываем ответ
}
void sig_alrm(int signo) {
siglongjmp(jmpbuf, 1);
}
Если приходит ответ, но его порядковый номер отличается от предполагаемого, мы снова вызываем функцию recvfrom, но не отправляем снова тот же запрос и не перезапускаем работающий таймер повторной передачи. Обратите внимание, что в крайнем правом случае на рис. 22.2 последний ответ, полученный на отправленный повторно запрос, будет находиться в приемном буфере сокета до тех пор, пока клиент не решит отправить следующий запрос (и получить на него ответ). Это нормально, поскольку клиент прочитает этот ответ, отметит, что порядковый номер отличается от предполагаемого, проигнорирует ответ и снова вызовет функцию recvfrom.
Мы вызываем функции sigsetjmp и siglongjmp, чтобы предотвратить возникновение ситуации гонок с сигналом SIGALRM, который мы описали в разделе 20.5. В листинге 22.6 показана первая часть нашей функции dg_send_recv.
Листинг 22.6. Функция dg_send_recv: первая половина
//rtt/dg_send_recv.c
1 #include "unprtt.h"
2 #include <setjmp.h>
3 #define RTT_DEBUG
4 static struct rtt_info rttinfo;
5 static int rttinit = 0;
6 static struct msghdr msgsend, msgrecv;
/* предполагается, что обе структуры инициализированы нулем */
7 static struct hdr {
8 uint32_t seq; /* порядковый номер */
9 uint32_t ts; /* отметка времени при отправке */
10 } sendhdr, recvhdr;
11 static void signalrm(int signo);
12 static sigjmp_buf jmpbuf;
13 ssize_t
14 dg_send_recv(int fd, const void *outbuff, size_t outbytes,
15 void *inbuff, size_t inbytes,
16 const SA *destaddr, socklen_t destlen)
17 {
18 ssize_t n;
19 struct iovec iovsend[2], iovrecv[2];
20 if (rttinit == 0) {
21 rtt_init(&rttinfo); /* первый вызов */
22 rttinit = 1;
23 rtt_d_flag = 1;
24 }
25 sendhdr.seq++;
26 msgsend.msg_name = destaddr;
27 msgsend.msg_namelen = destlen;
28 msgsend.msg_iov = iovsend;
29 msgsend.msg_iovlen = 2;
30 iovsend[0].iov_base = &sendhdr;
31 iovsend[0].iov_len = sizeof(struct hdr);
32 iovsend[1].iov_base = outbuff;
33 iovsend[1].iov_len = outbytes;
34 msgrecv.msg_name = NULL;
35 msgrecv.msg_namelen = 0;
36 msgrecv.msg_iov = iovrecv;
37 msgrecv.msg_iovlen = 2;
38 iovrecv[0].iov_base = &recvhdr;
39 iovrecv[0].iov_len = sizeof(struct hdr);
40 iovrecv[l].iov_base = inbuff;
