Адаптивная система управления потоком для транспортного протокола в сетях с коммутацией пакетов

Доступ к сервисам сетевого уровня возможен на интерфейсе между сетевым и транспортным уровнями. Важность данного интерфейса определяется тем, что часто этот интерфейс отделяет потребителя коммуникационных услуг от их поставщика, т.е. оператора базовой сети. Оператор базовой сети имеет полный контроль над протоколами предшествующими транспортному уровню. Именно по этой причине интерфейс должен прорабатываться особенно тщательно. Сервисы сетевого уровня любой коммуникационной системы должны обладать следующими основными характеристиками:

ѕ сервисы не зависят от канальной технологии базовой сети.

ѕ транспортный уровень должен быть экранирован от количества, типов и топологий различных базовых сетей.

ѕ если сетевые адреса являются доступными для транспортного уровня, то они должны укладываться в пределы стандартной схемы адресации, в которой каждый адрес уникален.

Рассмотрим вкратце функционирование протокола IP, и проанализируем его с точки зрения среды исполнения транспортного протокола.

Получая данные от вышележащего уровня в виде блоков конечного размера, протокол IP инкапсулирует их в пакет, добавляя к данным пользователя свой заголовок. На рис. 7. приведены поля заголовка протокола IPv6. Для нас представляет интерес то, что в заголовке отсутствует поле кода циркулярного контроля. Это связано с тем, что задача проверки и коррекции ошибок передачи возложена на канальный уровень, который всегда выполняет эту проверку. Протокол IPv4 осуществлял проверку целостности данных при помощи кода контроля четности, но из функциональности IPv6 данная операция была изъята, поскольку она дублирует аналогичную или более мощную систему канального уровня.

Рис. 7. Формат заголовка пакета протокола IP (изображен для IP версии 6).

Закончив компоновку пакета, IP передает его в сеть на маршрутизатор топологически более близкий к узлу которому адресовано сообщение. Каждый IP пакет в заголовке содержит полный адрес отправителя и получателя. Маршрутизаторы в составе сети обмениваются топологической информацией с помощью протоколов маршрутизации и благодаря этому обладают знанием топологии сети. Получая IP пакет, каждый маршрутизатор сравнивает адрес узла назначения с имеющейся у него таблицей топологической информацией и направляет пакет на соответствующий выходной порт. Поскольку разные маршрутизаторы могут обладать различным представлением о топологии сети, то и маршрутов между двумя узлами в сети может быть несколько. Если на выходной порт маршрутизатора поступает больше пакетов в единицу времени, чем может его покинуть, то пакеты организуются в очередь. Поскольку ресурсы буферного пространства маршрутизаторов конечны, то переполнение очереди приводит к потерям пакетов.

1.7.6.2.2. Возникновение и коррекция ошибок

Низкое соотношение энергии сигнала к энергии шума на линии приводит к искажениям принимаемого сигнала и как следствие к высокой вероятности битовых ошибок на приемнике. Ошибки канала передачи данных проявляются как:

1. Вставленные данные: данные, полученные приемником, но никогда не передававшиеся отправителем.

2. Потерянные данные: данные отправленные, но не дошедшие до получателя (исчезнувшие на физическом уровне).

3. Дублированные данные: данные, переданные единожды и полученные в нескольких экземплярах

4. Искаженные данные: данные, поврежденные в транзите

5. Разупорядоченные данные: данные, последовательность получения которых не совпадает с последовательностью передачи

Применяемые на канальном уровне алгоритмы распознавания и коррекции ошибок с достаточной вероятностью позволяют отобразить ошибки типа вставленных и искаженных данных на оставшиеся три типа ошибок, а именно потеря, дублирование и разупорядочивание данных.

Сетевой уровень стека TCP/IP предоставляет пользователю ненадежный сервис без установки логического соединения. Сказанное означает, что IP пакеты могут начать поступать в сеть без задержки, как только информация готова к отправке (пакет сформирован). Отправленные пакеты не подтверждаются получателем. Пакет может быть потерян, и никогда не дойти до получателя, по нескольким причинам: он может быть отброшен из переполненного буфера маршрутизатора вследствие перегрузки последнего, либо данные в составе пакета могут быть разрушены в процессе передачи по ненадежному каналу. Таким образом, сетевой уровень может привнести дополнительные ошибки типа потерь данных. Также вследствие возможности наличия нескольких маршрутов к получателю порядок прибытия пакетов может не совпадать с порядком их отправки, если поток пакетов будут доставляться по маршрутам с различной задержкой. Более того, существует возможность доставки получателю нескольких копий одного пакета.

Протокол TCP, таким образом, должен самостоятельно отслеживать возникновение трех типов ошибок данных и осуществлять самостоятельное восстановление в ситуациях, когда сегмент не приходит вообще, когда сегменты доставляются сетью не в том порядке, в котором были отправлены и когда сеть доставляет несколько копий одного сегмента.

1.7.6.2.3. Управление потоком

Каждый из нижележащих уровней осуществляет управление скоростью передачи данных. Физический уровень ответственен за синхронизацию записи и сканирования среды передачи. Канальный уровень управляет скоростью передачи пакетов между двумя узлами, применяя схему управления потоком той или иной сложности, в зависимости от назначения - Xon/Xoff, Alternating bit [42], sliding window [43] и т.п. Сетевой уровень также имеет примитивную схему управления потоком. Маршрутизатор в состоянии перегрузки может отправить своим топологическим соседям сообщение о наличии перегрузки при помощи протокола ICMP. Однако все алгоритмы канального и сетевого уровней осуществляют управление скоростью потока лишь локально. TCP, как протокол транспортного уровня, осуществляет управление потоком по всей длине логического канала между передающей и принимающей системами.

В протоколе TCP существует механизм, ограничивающий скорость отправки сегментов в сеть, для того чтобы избежать переполнения буферов промежуточных маршрутизаторов и буфера приемника.

1.7.6.3. Процедурные правила

Сервис транспортного уровня реализуется транспортным протоколом между двумя объектами транспортного уровня. Процедурные правила, требуемые для реализации этого сервиса слишком громоздки, поэтому их формальное описание например в виде конечных автоматов было бы слишком громоздким. Далее мы дадим описание процедурных правил TCP в виде отдельных алгоритмов. Отдельными важными аспектами транспортного протокола, которые должны быть учтены в его процедурных правилах являются:

ѕ Адресация и мультиплексирование

ѕ Инициализация и закрытие связи

ѕ Буферизация и управление потоком

1.7.6.4. Словарь транспортного протокола

Словарь простейшего транспортного протокола, обеспечивающего надежный канал связи и контроль скорости передачи, должен позволять передавать следующие типы сообщений [1, 3]:

Данные (DATA)

Подтверждения (ACK)

Размер приемного окна (WND)

Таким образом, минимальный словарь транспортного протокола обеспечивающего надежную связь таков: V={DATA, ACK, WND}. Если рассматривать каждое направление полнодуплексного транспортного соединения раздельно, то данные передаются в направлении от отправителя к получателю, а подтверждения и обновления окна в противоположном направлении.

Поскольку каждое индивидуальное сообщение транспортного протокола инкапсулируется сетевым уровнем в отдельный пакет, то выгодно объединить как можно больше сообщений в каждом TPDU. Реально в каждом сообщении объединяются все эти типы. Формат сообщений транспортного протокола таков:

{DATA, SEQ}

{ACK, SEQ, WND}, где SEQ и WND - целые числа.

Поскольку транспортные соединения рассчитаны на двусторонний обмен сообщениями, то объединяются все поля в едином формате сообщения:

{DATA, SEQ, ACK, SEQ, WND}

Число SEQ на второй позиции нумерует передаваемые данные, а в третьей позиции - подтверждаемые данные.

1.7.6.5. Кодировка сообщений на транспортном уровне

Итак, словарь транспортных протоколов состоит из сообщений - так называемых TPDU, которые инкапсулируют передаваемые данные. Сам TPDU в свою очередь заключен в пакет сетевого уровня.

Формат сегмента, как правило, следующий: заголовок фиксированной длины выровненный на 32 битной границе предшествует полю данных переменной длины. Более конкретная схема кодировки сегмента и детализация дополнительных полей приведена в схеме заголовка TCP сегмента (рис. 8.).

Рис. 8. Формат заголовка сегмента TCP.

Заголовок сегмента транспортного протокола содержит поле, позволяющее проверить целостность данных и заголовка принятого сегмента. В протоколе TCP это 16-ти битное поле несет проверочную сумму, полученную суммированием по модулю 2 всех 16-ти битных слов части заголовка и поля данных.

При получении сегмента проверочная сумма вычисляется заново и если результат не равен нулю, то сегмент содержащий ошибку отбрасывается.

1.7.6.6. Адресация

Для установки связи с удаленным приложением требуется указать его адрес. Адресация необходима для всех видов сетей. Существует метод, позволяющий устанавливать транспортный адрес, по которому приложение-сервер ожидает прибытия запроса на соединение. Для архитектуры TCP/IP это пара: IP адреса и номер локального порта. Объекты транспортного уровня допускают использование нескольких транспортных адресов (рис. 9), при этом мультиплексирование потоков в пределах узла осуществляется самим транспортным протоколом. Постоянно существующие серверные приложения адресуются напрямую, для работы с приложениями, запускаемыми лишь на время существования сессии, используется так называемый «протокол первоначального соединения» или интернет сервер (UNIX inetd) [75].



Рис. 9. Точки доступа к сервису транспортного уровня (ТДТС).

Изображены интерфейсы транспортного уровня с уровнем приложения и сетевым уровнем.

1.7.6.7. Установка соединения

Без способности БС к накоплению пакетов задача установления соединений свелась бы к двум действиям - послать запрос на соединение - дождаться положительного ответа на него. На самом же деле проблема значительно более сложна. Если БС перегружена, и подтверждения не успевают прибыть к отправителю вовремя, то и запросы на установление соединения могут быть отправлены несколько раз. Поскольку маршрутизация каждого пакета происходит независимо, то существует вероятность задержки некоторых пакетов в течение более длительного времени, чем других и, соответственно, сбоев при установлении соединения. Единичная транзакция может, таким образом, случайно произойти два и более раза.

Используемый в архитектуре TCP/IP метод сочетает с идентификацию каждого пакета с требованием ограничения времени жизни пакетов в сети. Причем идентификация каждого пакета подразумевает наличие у него порядкового номера.

В реальности необходимо гарантировать, что не только сам пакет исчез из сети, но и все его подтверждения, поэтому используется промежуток времени Т, кратный максимальному времени жизни пакета. Если прошло время Т с момента отправки пакета, то мы можем быть уверены, что ни сам пакет, ни его подтверждения не существуют на сети. Если опираться на такую предпосылку, то можно разработать надежный способ безопасной установки соединения. Метод был впервые предложен [37] в 1975 и усовершенствован [38] в 1978. Метод называется «трехсторонний обмен» (Three-way handshake). Этот метод не требует использования обеими сторонами одних и тех же номеров. Нормальная процедура установки соединения иллюстрирована на рис. 10 (часть А.) Устройство А посылает запрос на соединение (CR) устройству В, указывая при этом начальный порядковый номер который будет использоваться транспортным протоколом устройства А для передачи данных. Устройство В, получив запрос, реагирует отправкой пакета, уведомляющего о согласии установить соединение, указывает свой собственный начальный номер у и подтверждает номер x. После этого в первом пакете с данными, который имеет номер х, машина А подтверждает прием сообщения с номером у. Варианты В. и С. иллюстрируют поведение транспортных объектов при получении дубликата запроса на соединение и дубликата подтверждения.

Рис. 10. Установка соединения по методу тройного обмена. Часть А. - нормальная установка соединения. В. - реакция на дубликат запроса. С. - реакция на дубликат запроса и данных.

Схема установки соединения приведенная выше применяется транспортным протоколом TCP. Альтернативная схема надежной установки соединения в условиях наличия задержанных копий сообщений описана [39].

1.7.6.8. Разрыв соединения

Для закрытия транспортного соединения используется так называемый симметричный разрыв, при котором каждое направление соединения считается независимым и закрывается по отдельности.

Рис. 11 иллюстрирует процесс закрытия соединения с использованием таймеров. Несмотря на относительную надежность такого протокола, он может не сработать в случае потери начального DR и всех N повторных передач. В этом случае инициирующая сторона закроет соединение, противоположная же не получив информации о закрытии будет активной. Такое состояние называется полуоткрытое соединение. Для предотвращения возникновения таких состояний вводится правило, по которому соединение будет автоматически закрываться, если в течение определенного времени на нем не зарегистрировано никакой активности.

Рис. 11. Сценарии разрыва соединения с использованием подтверждений и таймеров.

Часть А. - сценарий без ошибочных ситуаций. В, С и D - различные сценарии возникновения ошибок. Потерянный сегмент изображается звездочкой.

Если же соединение должно оставаться открытым в течение длительного времени, ожидая появления данных для передачи, то сторонам придется периодически обмениваться пустыми сообщениями, удерживающими противоположную сторону от закрытия.

1.7.6.9. Управление потоком и буферизация данных

Управление потоком непосредственно связано с буферизацией. Задачей процесса управления потоком является не допустить переполнения получателя и промежуточных узлов информацией, которую те не успевали бы обрабатывать. В том случае, если БС предоставляет ненадежный датаграммный сервис, то отправитель должен буферизовывать отправленные сообщения на случай возникновения необходимости повторной отправки. Получатель, зная, что сообщения остаются в памяти отправителя пока не поступит подтверждение их приема, может выделять или не выделять буферное пространство для каждого соединения. В случае буферизации сообщений у получателя, что позволяет существенно повысить производительность системы, возникает вопрос о схеме выделения памяти под буферы. Это может быть и система буферов равных размеров (если все сообщения примерно одного размера) или большой циркулярный буфер или набор буферов разных размеров.

Оптимальное решение относительно буферизации у отправителя и получателя зависит от характеристик потока. Например, для трафика порожденного интерактивной работой с удаленным терминалом, характеризуемого небольшой скоростью, лучше вообще не выделять буферов, а получать и передавать информацию приложениям по мере ее поступления (естественно, что переданное сообщение должно оставаться в памяти отправителя до получения подтверждения). С другой стороны для потока созданного не интерактивной передачей данных, например - загрузкой удаленного файла, эффективность может быть существенно повышена, если получатель выделит максимальное количество буферного пространства, чтобы как можно более повысить скорость передачи.

Таким образом, с течением времени отправитель и получатель должны согласовывать свои схемы выделения буферного пространства. Отправитель должен иметь возможность запрашивать получателя о выделении определенного количества буферного пространства или же получатель (не имеющий информации о потребностях отправителя) должен сообщать, что для соединения зарезервировано Х буферов.

Выделение буферов должно происходить независимо от прихода подтверждений (в отличие от большинства протоколов канального уровня). Эта схема подразумевает наличие

«окна» переменного размера. Получатель выделяет такое количество буферного пространства в ответ на запрос отправителя, какое позволяют его ресурсы. Каждый раз, посылая сообщение, отправитель должен уменьшить указанное количество и временно прекратить передачу, если размер свободного буферного пространства у получателя уменьшится до нуля. Получатель, в свою очередь должен указывать текущий размер окна и номер подтверждения в потоке идущем в обратном направлении. При увеличении количества памяти доступной для буферизации сетевых соединений уже не недостаток свободного буферного пространства будет ограничивать максимальную скорость передачи данных, а доступная пропускная способность БС. Таким образом, необходим механизм управления потоком, который учитывает также и несущую способность БС, а не только количество буферного пространства у конечных участников обмена. Если используется механизм ограничивающего окна, то его размер должен отражать текущую пропускную способность БС.

1.7.7. Протокол TCP

Семейство протоколов TCP/IP включает в себя два протокола транспортного уровня это TCP - Transmission Control Protocol - и UDP User Datagram Protocol. UDP достаточно прост, по существу это небольшое дополнение к IP, и не использует виртуальный канал. TCP это надежный протокол, который использует предварительную установку виртуального канала и доставляет данные пользователя без ошибок. ТСР был специально разработан, чтобы обеспечивать надежную передачу байтового потока от отправителя к получателю через ненадежную БС. БС может состоять из различных сетевых компонентов, обладающих разными топологическими схемами, технологиями, пропускной способностью, задержками.

Формально протокол ТСР был определен в RFC 793 [4]. Со временем накопившиеся ошибки и недостатки были учтены и нашли выражение в требованиях к устройствам интернет в RFC 1122 [5]. В дальнейшем было проведено большое количество исследований с протоколом. Часть модификаций стала стандартом и новые спецификации протокола содержится в RFC 1323 [6].

Каждое устройство, поддерживающее ТСР, содержит в себе объект протокола, который управляет ТСР потоками и взаимодействует с уровнем IP. Этот объект принимает потоки данных от локальных процессов, разбивает их на сообщения определенной длины (сегменты) и передает сегмент на уровень IP для его передачи в виде отдельного IP пакета. По прибытии на адресуемую машину информация из этих пакетов передается ТСР объекту, который реконструирует оригинальный байтовый поток и передает ее пользовательской программе. Уровень IP не гарантирует доставку пакетов, поэтому ТСР должен отслеживать потерянные пакеты и осуществлять повторную отправку. Пакеты могут прибывать и в также является реконструкция порядка в битовом потоке. Для управления потоком и предотвращения перегрузок БС ТСР применяет механизм скользящего окна [43].

1.7.7.1. Модель обслуживания ТСР

Доступ к сервису ТСР можно получить путем создания на конечных машинах точек доступа (Sockets). Каждая такая точка имеет адрес, состоящий из IP адреса машины и 16-ти битного номера, уникального в пределах устройства, идентифицирующего порт. ТСР соединение устанавливается между двумя точками доступа и пара транспортных адресов однозначно идентифицирует соединение. Несколько соединений могут оканчиваться на одной точке доступа. Порты с номерами ниже 256 однозначно соответствуют набору конкретных приложений. Порты с другими номерами выделяются приложениям динамически. Все ТСР соединения полнодуплексные и имеют тип точка-точка. Соединение представляет собой неструктурированный байтовый поток, т.е. границы между сообщениями не сохраняются.

Когда приложение передает данные ТСР, протокол может либо сразу осуществить их отправку, либо накопить достаточное их количество в буфере. Если же приложению необходимо послать информацию мгновенно, то оно может использовать флаг PUSH. Кроме того, существует возможность пересылать срочную информацию с использованием флага URGENT. Когда приложение устанавливает этот флаг, то ТСР передает все имеющиеся данные без промедления, кроме того, ТСР получателя генерирует прерывание для приложения которому предназначается срочная информация и указывает на положение ее в полученном потоке.

Каждый байт ТСР соединения имеет уникальный 32-х битный порядковый номер. Эти номера используются не только для подтверждений, но и для механизма управления окном. Объекты ТСР обмениваются информацией в виде сегментов. Сегмент состоит из 20-ти байтного заголовка (+ необязательная часть) и нуля или более байтов данных (рис. 8). Протокол сам принимает решение относительно размера сегмента. Существуют два ограничения размера сегмента. Первое: сегмент должен умещаться в пределах максимального размера поля полезной нагрузки IP -216 байт. Второе: каждая сетевая технология имеет так называемую максимальную единицу передачи (Maximum Transfer Unit - MTU) в которую и должен уместиться полный IP пакет, включающий в себя IP и ТСР заголовки и данные.

Одновременно с передачей сегмента запускается таймер повторной передачи. Когда сегмент прибывает к получателю, ТСР объект последнего отправляет сегмент, содержащий подтверждение приема этого сегмента. Если таймер повторной передачи для сегмента срабатывает раньше времени прихода подтверждения, то данный сегмент ретранслируется.

1.7.7.3. Формат заголовка ТСР

Заголовок сегмента ТСР содержит следующие поля (рис. 8):

Порядковый номер идентифицирует первый байт данных в этом пакете, может также использоваться для указания первого номера в серии который будет использоваться в последующих передачах.

Номер подтверждения - содержит порядковый номер следующего байта данных, который ожидается на принимающем устройстве.

Флаги - разнообразная контрольная информация:

URG - срочные данные, указатель на срочные данные в этом случае указывает на их положение в сегменте

ACK - 1 значит, что поле подтверждения содержит правильную информацию PSH - получатель должен доставить данные приложению как можно скорее RST - соединение должно быть закрыто

SYN - используется для установки соединения, запрос на установку содержит SYN=1, ACK=0, ответ на этот сегмент содержит SYN=1, ACK=1.

FIN - отправитель сигнализирует о желании закрыть соединение. После отправки FIN машина может еще неограниченно долго продолжать получать информацию. SYN и FIN сегменты имеют порядковые номера, что гарантирует их обработку в правильном порядке.

Размер окна сообщает о том, как много байтов можно отправить, начиная с последнего подтвержденного байта. Этот размер может быть равен нулю.

1.7.7.4. Управление соединением

Установка соединения в ТСР использует процедуру трехстороннего обмена. Для открытия соединения пассивная сторона исполняет примитивы LISTEN и ACCEPT, а другая открывает соединение в активном режиме, исполняя примитив CONNECT. Когда запрос на открытие соединения, прибывает к получателю, тот проверяет, есть ли процесс зарегистрированный для приема соединений по указанному порту. Если такой процесс существует, то соединение устанавливается (рис. 12 часть A).

Рис. 12. Сценарии установки соединения TCP. Часть А.- нормальная процедура, часть В.- установка соединения при столкновении запросов.

Хотя ТСР соединения полнодуплексные, закрываются соединения в каждом направлении по отдельности. В нормальной ситуации требуется четыре сегмента, чтобы полностью закрыть соединение (два FIN и два ACK). По каждому из симплексных соединений данные могут передаваться неограниченно долго. Для предотвращения появления полуоткрытых соединений используются несколько таймеров. Если ответ не сегмент FIN не приходит в течение двух максимальных периодов жизни пакета, отправитель сегмента FIN разрывает соединение.

1.7.7.5. Управление передачей

Управление окном в ТСР не привязано напрямую к подтверждениям (как во многих протокола канального уровня).

Подтверждения, используемые протоколом TCP, являются кумулятивными, т.е. каждое подтверждение соответствует последнему полученному в правильном порядке байту потока. Приход подтверждения с номером N означает, что все байты [0…N-1] были успешно доставлены получателю.

1.7.7.6. Управление окном и тактика подтверждений

На ранних стадиях эксплуатации протокола было замечено, что часто в сетях возникали перегрузки при очень низком эффективном использовании ресурсов [8]. Были выявлены три независимые причины этого: приложение вызывающие протокол для отправки незначительного количества информации, обновление окна ТСР очень маленькими порциями и вызывающие ответные сегменты с малой полезной нагрузкой, и сам протокол посылающий слишком много подтверждений. Было предложено использовать так называемый алгоритм SWS [5] для решения проблемы с обновлением окна.

А. Алгоритм SWS у получателя, совмещен с задержкой подтверждения предписывает: обновление окна вместе с подтверждением отправляется только если освободившийся объем буфера превосходит определенную долю общего буферного пространства (30-50%) или 2-3 максимальных размера сегмента.

Б. Алгоритм SWS у отправителя предписывает: отправитель пытается приблизительно оценить размер буфера получателя, отслеживая максимальный размер окна открываемого получателем на данном соединении. max(SND.WND). Используемое окно, данные в пределах которого могут быть отправлены, вычисляется U=SND.UNA + SND.WND - SND.NXT. Если D количество данных буферизованных протоколом, но еще не отправленных, то ТСР отправляет данные если:

ѕ Есть возможность послать сегмент максимального размера min(D,U) >= Eff.snd.MSS

ѕ установлен флаг PUSH и [SND.NXT = SND.UNA] && PUSHED && D <= U [SND.NXT = SND.UNA] условие налагаемое алгоритмом Nagle. [8].

ѕ как минимум доля Fs от максимального окна может быть отправлена [SND.NXT = SND.UNA] && min(D, U) >= Fs * Max(SND.WND)

ѕ установлен флаг PUSH и сработал таймер

В. Алгоритм Nagle: эффективен когда приложение передает малые объемы информации. Согласно этому алгоритму, если есть неподтвержденные данные (SND.NXT > SND.UNA), то ТСР отправителя буферизует данные без отправки, несмотря на наличие флага PUSH, до момента, когда либо приходит подтверждение, либо становится возможным отправить сегмент максимального размера.

Г. Алгоритм задержки подтверждений требует:

Подтверждение должно задерживаться не менее чем на 0.5 с. Подтверждения задерживаются до тех пор, пока не возникнет возможность указать новое окно или данные отправляются в противоположном направлении. Таймер генерирует безусловное подтверждение каждые 200 мс. Кроме того, каждый второй сегмент должен подтверждаться. Также сегменты, буферизованные у получателя (прибывшие в неправильной последовательности) генерируют подтверждение мгновенно для включения механизма быстрой ретрансляции.

1.7.7.7. Управление потоком и предотвращение перегрузок

Если суммарная скорость поступления данных в на сеть превышает максимальную скорость, с которой сеть передает эти данные, то возникает перегрузка сети. Если состояние перегрузки длится в течении времени, достаточного для переполнения буферов в сети, то происходят потери данных в сети. Потерянные сегменты ретранслируются протоколом TCP и способствуют продолжению роста перегрузки. Алгоритм управления потоком транспортного протокола должен предотвращать возникновение перегрузки и способствовать выходу сети из состояний перегрузки, в случае его возникновения.

Перегрузка сети может быть предотвращена с помощью использования принципа сохранения пакетов [2] - если сеть загружена полностью, то не передавать следующий пакет раньше, чем предыдущий покинет сеть (т.е. будет доставлен по назначению). ТСР стремится следовать этому принципу, изменяя размер окна.

Схема определения наступления состояния перегрузки в TCP основывается на предположении, что причина всех потерь пакетов заключается в переполнении очередей маршрутизаторов, т.е. перегрузке сети. Таким образом, алгоритм управления потоком в ТСР считает потери связанные с разрушением данных из-за шума на линии несущественными и реагирует на все потери как на признак перегрузки. Такой механизм является неэффективным, особенно в случае беспроводных соединений, таких как радио и спутниковые каналы, ИК приемопередатчики.

ТСР оперирует двумя окнами, одно определяет размер буфера отправителя, другое (CWND) является результатом попыток протокола определить пропускную способность сети на данном соединении. Для отправки данных используется минимальное из двух окон.

Механизмы Slow start, congestion avoidance, fast retransmit, fast recovery [6] являются стандартом для современных реализаций ТСР.

Slow start (замедленный запуск) применяется для постепенного увеличения скорости передачи информации после открытия соединения или потери пакета. Изначально размер окна CWND устанавливается равным одному сегменту. После получения каждого подтверждения CWND увеличивается на размер одного сегмента. Алгоритм медленного запуска отключается когда происходит потеря сегмента или достигается верхняя границаокна получателя. Время, затрачиваемое для полного открытия окна

t ? RTT ? log 2W где W - размер окна в сегментах.

Congestion avoidance (предотвращение перегрузки) используется для определения наличия дополнительной пропускной способности. Обычно этот алгоритм действует совместно с алгоритмом медленного старта. Для фиксации момента перехода с медленного старта на предотвращение перегрузки используют переменную SSTHRESH. SSTHRESH инициализируется размером максимально возможного окна при открытии нового соединения. Медленный старт продолжается пока значение CWND не достигнет SSTHRESH, после этого режим роста CWND изменяется на линейный, а именно, для каждого подтверждения CWND увеличивается на значение (1/ CWND).

Fast Retransmit (быстрая ретрансляция). Использует последовательное получение подтверждения одного и того же сегмента, как признак потери, ретранслирует этот сегмент до срабатывания таймера ретрансляции.

Fast recovery (быстрое восстановление). После срабатывания механизма быстрой ретрансляции ТСР переходит в режим предотвращения перегрузки, а не медленного старта. После прихода третьего дубликата подтверждения SSTHRESH устанавливается равной Ѕ CWND, и отсутствующий сегмент ретранслируется, CWND устанавливается равным SSTHRESH+3 (количество сегментов покинувших сеть). Затем на каждое подтверждение CWND увеличивается на размер одного сегмента. Если размер CWND позволяет, передаются дополнительные сегменты. Когда приходит подтверждение, включающее в себя ретранслированный сегмент, CWND устанавливается равным SSTHRESH и ТСР переходит в режим предотвращения перегрузки. Описанные выше механизмы являются стандартной частью протокола TCP, их применение регламентируется RFC 1323 [6].

1.7.7.8. Управление таймерами

Объекты ТСР концептуально используют несколько таймеров для выполнения своих функций. Наиболее важным из них является таймер повторной передачи (ТПП). ТПП перезапускается каждый раз при отправке сегмента. Если подтверждение приема сегмента не приходит до срабатывания таймера, то этот сегмент ретранслируется.

Определение суммарного времени затрачиваемого сегментом на достижение получателя и времени затрачиваемого подтверждением, чтобы вернуться к отправителю (RTT) само по себе достаточно сложно в реализации, еще сложнее даже зная это время правильно установить интервал таймера. Если ТПП установлен на слишком короткий интервал, то повторная передача произойдет еще до того как может прибыть подтверждение и это еще больше увеличит степень загрузки БС. Если же таймер установлен со слишком длительную задержку, то некоторую часть времени канал будет использоваться неэффективно. Кроме того, среднее значение измеряемого RTT и его дисперсии крайне динамично меняется с течением времени в зависимости от степени загрузки БС.

В протоколе TCP используется высоко динамичный алгоритм, который непрерывно корректирует значение ТПП, отслеживая время обращения сегментов в сети. Этот алгоритм функционирует следующим образом [2]: для каждого соединения ТСР сохраняет значение наилучшей текущей оценки времени обращения сегментов в переменной RTT. При отправке сегмента устанавливается таймер для контроля повторного отправления и для измерения RTT. Если подтверждение прибывает до срабатывания таймера, то, измеряя время которое прошло до прихода подтверждения (М), ТСР обновляет среднее значение RTT по формуле:

RTT ? б ? RTT ? (1 ? б ) ? M

где б весовой коэффициент применимый к старому значению (с типичным значением 7/8).

Для того, чтобы значение RTT не искажалось из-за учета ретранслированных сегментов, Карном [7] был предложен алгоритм, который добавил к ТСР следующее правило: не обновлять значение RTT по данным, относящимся к ретранслированным сегментам, вместо этого значение ТПП удваивается с каждой ретрансляцией. Этот принцип получил название “Exponential Backoff”.

1.8 Свойство самоподобия сетевого трафика

1.8.1. Традиционная методология: системы массового обслуживания

Традиционной методологией применяемой для изучения процессов происходящих в территориально распределенных сетях с большим количеством пользователей до недавнего времени являлась теория массового обслуживания [9].

Применение теории массового обслуживания к исследованию процессов, происходящих в сетях передачи данных, основывается на предположении о том, что моменты поступления требований в систему (моменты прихода пакетов в маршрутизатор) образуют пуассоновский поток с интенсивностью л . Если распределение длительностей времени обслуживания также является пуассоновским, то применение методологии системы массового обслуживания М/М/1 позволяет определить среднее число требований в системе и с помощью теоремы Литтла связать это число со средней задержкой в системе в равновесном состоянии. Анализ систем массового обслуживания предполагает, что процесс, считающий число требований находящихся в системе является марковским процессом с непрерывным или дискретным временем, исследование которого и дает среднее число требований в системе в стационарном режиме. Таким образом, получают формулы для среднего числа требований и среднего времени пребывания требований в системе.

Если же предполагается произвольное распределение длительностей обслуживания требований, то такая система массового обслуживания обозначается M/G/1 и среднее время пребывания требования в обслуживающем приборе выражается формулой Поллачека- Хинчина.

Для сетей с коммутацией пакетов вообще и сетей передачи данных в частности долгое время применялись методы, основывающиеся на предположении о том, моментов прибытия пакетов или инициализации соединений имеют ограниченную дисперсию, поскольку аналитическая модель для таких систем хорошо известна [88, 9]. На основании этой модели рассчитывались основные характеристики сети, и производилось планирование ее ресурсов, в частности, объема буферного пространства.

1.8.2. Критика традиционных моделей трафика

С развитием сети Интернет и появлением возможности исследования большого количества экспериментального материала по трафику начали появляться свидетельства в пользу того, что трафик в сетях с коммутацией пакетов с большей точностью моделируется статистически самоподобными процессами [95] или, по крайней мере, не имеет экспоненциального распределения [90, 91]. Для самоподобного процесса представляющего пакетный трафик не существует естественного ограничения длительности всплеска. Всплески могут происходить в любом временном масштабе. Кроме того, множество типов обменов в современной сети инициируются и управляются операционной системой сетевых узлов автоматически, например обновления маршрутной информации, трафик протоколов SMTP, NNTP, что может приводить в глобальной синхронизации потоков в сети [92]. Такая ситуация является невозможной для пуассоновской модели, однако имеет место в реальности.

Итак, традиционный подход к моделированию трафика сети с коммутацией пакетов базируется полностью на предположении о неограниченности дисперсии процесса поступления пакетов, что позволяет применять теоретический аппарат марковских цепей для анализа таких систем. Однако развитие современных скоростных сетей передачи данных и мультимедиа информации с выраженной гетерогенной физической и логической инфраструктурой и большим набором разнообразных сервисов и генерируемых ими потоков, приводит к появлению существенно более сложных характеристик потоков. Трафик в таких сетях имеет явно выраженный всплесковый характер, не сглаживаемый усреднением по длительным временным промежуткам и большому числу потоков. Традиционный подход к моделированию трафика изменялся путем разработки все более сложных стохастических моделей: fluid flow models, Markov modulated Poisson processes, Markovian arrival processes, Batched Markovian arival processes, и т.д. Основной целью разработки всех этих моделей являлось сохранение возможности аналитического подхода к исследованию задач управления очередями и эффективностью системы. Однако, авторы обзора [93] отмечают, что статистические свойства стохастических моделей не совпадают со свойствами экспериментальных данных по сетевому трафику. Причиной того, что стохастический анализ применялся в течении длительного времени, был недостаток эмпирических данных. Сейчас в экспериментальных данных и модельных экспериментах нет недостатка - получено большое количество наборов данных по трафику в территориально распределенных сетях, в ЛВС, для различных технологий канального уровня и для разнообразных протоколов прикладного уровня, для TCP/IP и ATM сетей.

В связи с этим, усилия ученых сейчас направлены на разработку новых способов анализа коммуникационных систем.

1.8.3. Исследования экспериментальных данных

Исследования большого объема данных по трафику с высоким разрешением по времени было проведено в целом ряде работ, перечисленных в [93]. Эти работы показали, что трафик реальных сетей с коммутацией пакетов обладает характеристиками самоподобия или мультифрактальности. Более того, в цитируемых работах показывается существенное отличие статистических характеристик трафика генерируемого традиционными стохастическими моделями и эмпирическими данными.

Подробный библиографический обзор на тему самоподобия и фрактальных свойств процессов в телекоммуникационных сетях, а также моделирования современных высокоскоростных сетей представлен в работе [93] и включает в себя аннотации 420 работ.

Большое число работ, упоминаемых в [93] посвящено нахождению физического или феноменологического объяснения фрактальной природы эмпирически изучаемого трафика. В этих исследованиях приводится связь фрактальной природы наблюдаемого трафика с синдромом бесконечной дисперсии или так называемыми распределениями с тяжелыми хвостами.

На настоящий момент, согласно авторам работы [93], не существует аналитического аппарата применимого процессам, характеризующимся свойством самоподобия.

Для того чтобы определить наличие характеристик самоподобия у больших последовательностей результатов измерения трафика применяются несколько статистических методов: R/S статистика, дисперсионно-временной анализ, метод спектральных областей и другие [94].

1.8.4. Определения моно- и мультифрактальных процессов

В работе [95] даются принятые на сегодня определения и признаки самоподобных (монофрактальных) и мультифрактальных процессов.

Коэффициент H, называется коэффициентом или параметром Хёрста и является мерой самоподобия.

1.8.5. Причина свойств самоподобия Интернет трафика

Причиной наличия свойства самоподобия, как показано в работах [98, 97], является распределение ON периодов имеющее тяжелый хвост (убывающий гиперболически).

Авторы [97] предлагают разделять объяснения причин самоподобия трафик в больших и малых временных диапазонах. Так самоподобие LAN и WAN трафика в масштабах порядка секунды и более объясняется и математически доказывается в [98]. Однако для полного понимания динамики сетевого трафика необходимо исследовать причины мультифрактальных характеристик трафика в масштабах менее одной секунды, в котором поведение трафика особенно динамично. В этих масштабах локальное поведение каждого из составляющих трафик потоков определяется используемым данным протоколом алгоритмом управления потоком. В общем же поведение суммарного трафика определяется взаимодействием нескольких реализаций одного или нескольких протоколов в совокупности с взаимодействием потоков в обслуживающем приборе.

1.8.5.1. Трафик с малым разрешением по времени

Предположим, что каждое индивидуальное соединение i отправляет пакеты с постоянной скоростью в период ON и не отправляет пакетов вообще в период OFF. Такое поведение ЛВС было показано в [100] как обмены типа "запрос-ответ". С другой стороны для территориально распределенных сетей, например Интернет, индивидуальные соединения ассоциируются с сессиями, устанавливаемые транспортным протоколом типа TCP. Каждая такая сессия инициализируется в некоторый случайный момент времени, осуществляет передачу в течение некоторого времени с постоянной скоростью, а затем отключается. Каждая сессия обслуживает то или иное приложение, реализующее свой протокол прикладного уровня, например FTP[DATA], TELNET, NNTP, SMTP, HTTP. Для периодов длиной до 1 часа было показано, что процесс инициализации сессий в сетях является пуассоновским [91]. Для анализа трафика в большом временном масштабе только характеристики самих сессий важны для построения модели, в то время как индивидуальные процессы прибытия пакетов в рамках каждой сессии не рассматриваются. Для полного описания процесса счетчика общего трафика необходимо рассмотреть распределение длительностей сессий или ON/OFF периодов. Данные реальных наблюдений за потоками в LAN и WAN [91, 100] дают основание утверждать, что распределение длин ON/OFF периодов имеет бесконечную дисперсию и тяжелый хвост.

В работе [98] доказывается тот факт, что распределение длительностей периодов ON/OFF спадающее гиперболически или по степенному закону (выражение 13) при больших значениях количества потоков и длительном времени наблюдения определяют наличие свойства LRD суммарного потока с параметром Хёрста.

Авторы доказали, что отклонение от среднего значения представляет собой дробный гауссовский шум (Fractional Gaussian Noise) - классический пример в точности самоподобного процесса. Таким образом, в больших временных масштабах (асимптотическое) самоподобие сетевого трафика является следствием свойств сессий обмена (ON/OFF периодов). А именно того, что длительности этих периодов имеют распределение с тяжелым хвостом. Поэтому в больших масштабах самоподобие трафика не зависит от инфраструктуры сети или ее протоколов, а определяется набором информационных объектов передаваемых по этой сети. Дальнейшее развитие этой гипотезы дано в [99], где показано, что причиной наличия тяжелых хвостов в распределении длительностей ON периодов является соответствующее распределение размеров объектов в WWW - доминантной информационной системы в сети Интернет. В [99] наблюдения за реальным HTTP трафиком и файлами отчета крупнейших WWW серверов показывают наличие связи между гиперболическим распределением размеров информационных объектов WWW и гиперболическим распределением длительностей HTTP сессий, трафик которых составляет более половины всего Интернет трафика (по результатам множества исследований). Таким образом, трафик с малым разрешением по времени адекватно моделируется самоподобными или асимптотически самоподобными процессами согласно результатам [95, 97, 100].

1.8.5.2. Трафик с высоким разрешением по времени

Возвращаясь к высокодинамичному поведению сетевого трафика в малых временных масштабах, авторы [97] указывают на то, что причинами появления свойства LRD трафика в этих условиях являются свойства самих транспортных протоколов, управляющих потоками. Поскольку эти алгоритмы отвечают непосредственно за диспетчеризацию индивидуальных пакетов в рамках отдельных соединений, то вызываемые ими выраженные локальные нерегулярности трафика не являются связанными с самоподобными свойствами трафика в более грубом временном масштабе. Так при малом временном разрешении интернет трафик наиболее качественно описывается именно мультифрактальными процессами [96].

Надо отметить, что до настоящего времени неизвестна причина вызывающая такое поведение трафика.

1.8.6. Методы определения меры самоподобия

Для оценки меры самоподобия трафика ARTCP нами применены два метода - метод R/S статистики и метод Aggregated Variance. Оба метода относятся к числу хорошо изученных и успешно применяются в целом ряде работ [94].

1.9 Управление потоками в коммуникационных системах

1.9.1. Общие принципы

Управление потоками в коммуникационных сетях обозначает регулировку скорости отправки данных в сеть с целью достижения максимального использования ресурса сети и минимизации потерь данных.

В состав протокола TCP входит большое число разнообразных механизмов, которые отвечают за различную функциональность и находятся в определенном взаимодействии между собой в силу концептуально-необходимой связи или связи, возникшей при реализации. На рис. 14 приведена схема основных механизмов, входящих в состав самой распространенной реализации протокола TCP - Reno в составе 4.4 BSD UNIX [64].

Рис. 14. Набор функций и алгоритмов в составе стандартного протокола TCP.

Задачу управления скоростью передачи данных можно условно разбить на два компонента: не допущение переполнения принимающей стороны, и не допущение переполнения сети. Иными словами, целью системы управления потоком является выравнивание скорости передачи данных со скоростью их приема. Механизм контроля перегрузки отправляет данные в сеть не быстрее, чем сеть может их доставлять в место назначения и не быстрее, чем получатель может их обрабатывать.

Перегрузка в сети с коммутацией пакетов это такое состояние, при котором производительность системы падает в связи с переполнением ресурсов сети - коммуникационных каналов, процессорного времени и буферного пространства. Последствия перегрузки проявляются в увеличении времени доставки данных, падении эффективности использования сетевых ресурсов и так называемом сетевом коллапсе, когда процесс передачи полезных данных в сети полностью прекращается.

Изучение систем управления потоками и предотвращения перегрузок, очень важно для развития сетей. Из множества предложенных схем лишь несколько стали стандартами и получили широкое распространение: IBM Systems Networking Architecture (SNA) [10], Digital's Networking Architecture (DNA) [11], и модель TCP/IP [12]. Наиболее полная классификация различных методик управления потоком приводится в [13].

1.9.1.1. Перегрузка и методы ее контроля в сетях с коммутацией пакетов

Перегрузка является проблемой неэффективного совместного использования разделяемых ресурсов. В сети ресурсы распределены между всеми узлами, коммутаторами и каналами передачи данных. Любой из этих трех компонентов может стать узким местом в сети и вызвать ее перегрузку. С одной стороны сеть должна обслуживать все пользовательские запросы на передачу данных, которые, как правило, не могут быть предсказаны детерминистически и выражаются в виде всплесков по отношению к времени возникновения, скорости и объему передаваемой информации. С другой стороны все физические ресурсы сети имеют ограниченную мощность и должны быть управляемыми для достижения оптимального общего использования многими сессиями обмена данными. Более формальное описание состояния перегрузки сети можно получить рассмотрев производительность ее работы в зависимости от нагрузки (рис. 15).

Рис. 15. Зависимость характеристик сети от нагрузки. Пропускная способность (вверху), время задержки (в середине), мощность сети (внизу).

После достижения сетью насыщенного состояния (точка А) пропускная способность перестает расти, а время ответа (RTT) продолжает, поскольку происходит заполнение буферов внутри сетевых устройств. Мощность сети достигает пика в точке А - это оптимальный режим работы сети.

Механизмы управления потоками должны удерживать режим работы сети на оптимальном значении нагрузки и обеспечивать возможность выхода из состояния перегрузки, если перегрузка все-таки произошла. Механизм управления потоками в сетях TCP/IP обеспечивается как самими конечными системами, в которых исполняются объекты протокола TCP, так и с помощью определенных механизмов управления очередями и диспетчеризации потоков в маршрутизаторах.

1.9.2. Управление задержкой сети

Задержка данных при их передаче по сети состоит из двух компонентов. Для передачи мультимедиа информации очень важно чтобы значение задержки и ее дисперсия для индивидуальных пакетов были минимальными. Это требование выражается в требовании минимальности очередей в маршрутизаторах.

Поскольку TCP в процессе передачи целиком заполняет очередь маршрутизатора, то за счет компонента Dq общая задержка в сети существенно возрастает. Поэтому в сетях, где величина задержка актуальна, помимо управления скоростью средствами протокола транспортного уровня необходимо использовать механизмы, расположенные в маршрутизаторах [16].

1.9.2.1. Алгоритм RED

Поскольку средствами одного протокола TCP обеспечить минимальность средней длины очередей в сетевых устройствах невозможно, то в схеме управления трафиком должны быть задействованы сами сетевые устройства. Для реализации такого управления используется алгоритм случайного раннего обнаружения (Random Early Detection - RED) [18].

Алгоритм RED применяется для предотвращения перегрузок в сетях передачи данных работающих по принципу коммутации пакетов. Маршрутизатор определяет близость состояния перегрузки, вычисляя среднюю длину очереди. Маршрутизатор оповещает соединения, проходящие через него, о состоянии перегрузки путем отбрасывания пакетов. Вероятность отбрасывания зависит от средней взвешенной длины очереди, пока ее значение находится в заданных пределах и становится равной единице при пересечении верхней границы.

Маршрутизатор применяющий алгоритм RED позволяет удерживать низкой среднюю длину очереди, при этом допуская принятие в очередь всплески пакетов. В режиме перегрузки вероятность оповещения определенного транспортного соединения, путем отбрасывания или отметки пакета, с целью уменьшения окна контроля потока для этого соединения, пропорциональна доле этого соединения в общей пропускной способности канала. Алгоритм RED предназначен для работы с транспортным протоколом, который управляет своей пропускной способностью, реагируя на потери пакетов, которые протокол считает признаком перегрузки, снижением своей скорости передачи. RED не допускает дискриминации неравномерных потоков и приводит к глобальной синхронизации многих соединений.