Понимание принципов использования скользящего окна. Повторная передача и скользящее окно

Транспортный уровень использует службы, предоставляемые сетевым уровнем:

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

􀂄 поток данных транспортного уровня является логическим соединением между конечными точками сети;

􀂄 механизм скользящего окна обеспечивает сквозное управление и надежность соединения, позволяет отслеживать последовательность номеров пакетов и уведомлений;

􀂄 для управления различными сетевыми соединениями в протоколах четвертого уровня TCP и UDP и для передачи информации верхним уровням используются так называемые порты (port).

Транспортный уровень стека TCP/IP

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

Введение в транспортный уровень стека TCP/IP

Для описания четвертого, транспортного, уровня часто используется выражение качество обслуживания . Протокол UDP, который подробно рассматривается ниже, относится к транспортному уровню и обеспечивает работу транспортных служб без установления соединения. Однако основным протоколом, работающим на рассматриваемом уровне, является протокол TCP, который использует механизм установления соединения. Главными функциями этого протокола являются транспортировка и надежное управление потоком информации от отправителя к получателю. К основным функциям транспортного уровня относятся обеспечение сквозного управления передачей, управление потоком посредством механизма скользящего окна (sliding window) и гарантирование надежности доставки за счет установки последовательных номеров и использования подтверждений.

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

Транспортный уровень предоставляет средства для надежной передачи данных от узла-отправителя узлу-получателю. На этом уровне создается логическое соединение между конечными точками сети; кроме того, к задачам транспортного уровня относятся сегментация и повторная сборка данных, передаваемых различными приложениями верхних уровней в один поток данных транспортного уровня. Этот поток обеспечивает сквозную передачу данных между конечными точками.

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

Транспортный уровень обеспечивает следующие функции:

сегментацию данных приложений верхних уровней;

управление сквозным взаимодействием;

передачу сегментов от одного конечного узла другому;

управление потоком посредством изменения размера окна;

обеспечение надежности путем назначения номеров и использования подтверждений.

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

Набор протоколов TCP/IP состоит из двух отдельных протоколов: TCP и IP. Протокол IP является протоколом третьего уровня без установления соединения, который обеспечивает эффективную передачу данных по сети. TCP является протоколом четвертого уровня, представляет собой службу с установлением соединения и обеспечивает управление потоком данных и, следовательно, высокую надежность передачи. Сочетание указанных двух протоколов позволяет решать широкий круг задач по передаче данных. Конечно же, стек протоколов TCP/IP состоит и из многих других протоколов, однако протоколы TCP и IP являются основными. К слову, вся сеть Internet основана именно на стеке протоколов TCP/IP.

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

Когда протокол TCP транспортного уровня пересылает сегменты данных, он может гарантировать целостность данных. Одним из методов достижения этой цели является управление потоком (flow control ) , которое позволяет избежать проблем, связанных с ситуациями, когда узел на одном конце соединения переполняет буферы станции на другом конце. Переполнение вызывает серьезные проблемы, поскольку может привести к потере данных.

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

гарантирует, что отправитель будет получать подтверждение о доставке каждого сегмента;

обеспечивает повторную пересылку любых сегментов, подтверждение о доставке которых не было получено;

позволяет сортировать сегменты в пункте назначения в правильном порядке;

не допускает перегрузку сети и обеспечивает управление заторами в случае их возникновения.

Установка , управление и разрыв сеанса

В эталонной модели OSI несколько приложений могут одновременно использовать одно транспортное соединение. Функция транспортировки данных реализуются посегментно. Это означает, что различные приложения могут передавать данные по принципу ‘‘первым пришел, первым обслужен’’ (FIFO). Сегменты могут быть предназначены как одному получателю, так и разным. Это правило иногда называют механизмом мультиплексирования диалогов приложений верхнего уровня (рис. 3).

Рис. 3. Различные приложения самого верхнего уровня модели OSI используют транспортный уровень

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

После завершения процесса синхронизации и установки соединения начинается передача данных. В процессе пересылки обе станции не перестают обмениваться сообщениями, которые позволяют убедиться, что принимаемые данные верны. На рис. 4 проиллюстрировано типичное соединение между отправителем и получателем. Первое сообщение-запрос необходимо для синхронизации конечных узлов. Второе и третье необходимы для подтверждения начального запроса синхронизации; они также синхронизируют параметры соединения в обратном направлении. Последнее сообщение является подтверждением (acknowledgment), которое используется для информирования получателя о том, что обе стороны готовы установить соединение. После установления соединения начинается передача данных.

Рис. 4. Процесс установления соединения с одноранговой системой

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

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

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

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

Трехэтапное квитирование

Протокол TCP использует алгоритм работы с установлением соединения, поэтому перед передачей данных должно быть установлено логическое соединение. Для того чтобы установить сетевое соединение между двумя рабочими станциями, необходимо синхронизировать их начальные порядковые номера (ISN - Initial Sequence Number). Синхронизация достигается за счет обмена специализированными сегментами, которые содержат контрольный бит SYN (сокращение от s ynchronization ) и номера ISN. Модули, которые несут в себе бит SYN, также иногда называют SYN-сообщениями. Для решения задачи установления нужно подобрать соответствующий механизм выбора ISN-номеров методом установки начального соединения для обмена ISN-номерами.

Для синхронизации необходимо, чтобы каждая сторона отправляла свой начальный порядковый номер ISN и принимала подтверждение в виде сообщения-уведомления ACK (сокращение от acknowledgment ) от другого участника соединения. Кроме того, каждая сторона должна получать ISN-номер коммуникационного партнера и отправлять уведомление ACK об этом. Последовательность обмена сообщениями между двумя узлами сети, А и Б, описана ниже.

Такой обмен сообщениями называется трехэтапным квитированием (three - way handshake ) (рис. 5).

Рис. 5. Трехэтапное квитирование

1. A  Б SYN. Мой начальный порядковый номер ISN равен X, номер ACK = 0, бит SYN установлен, однако бит ACK не установлен.

2. Б  A ACK. Твой порядковый номер равен X+1, мой ISN-номер равен Y, биты SYN и ACK установлены.

3. A  Б ACK. Твой порядковый номер равен Y+1, мой порядковый номер = Х+1, бит ACK установлен, а бит SYN не установлен.

Трехэтапное квитирование является асинхронным механизмом соединения, который необходим для синхронизации порядковых номеров, поскольку такие номера не зависят от некоторого виртуального глобального счетчика в сети. Поэтому в сети, работающей под управлением протокола TCP, используются различные механизмы назначения ISN-номеров. Одним из них является трехэтапное квитирование. Однако этот механизм предназначен не только для получения ISN-номера. При помощи него конечные устройства обмениваются информацией о размере окна передачи данных, параметре MTU и задержке передачи данных в сети. Получатель первого сигнала SYN не имеет в наличии средств, которые позволят определить, был ли полученный сегмент отложенным старым или новым сообщением, до тех пор, пока не будет получено следующее сообщение; единственным исключением является случай, когда получатель хранит последний порядковый номер, используемый при соединении (что не всегда возможно). Таким образом, получатель должен запросить у отправителя проверку такого сообщения SYN.

Механизм скользящего окна

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

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

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

Рис. 6. Размер окна равен одному

Для управления потоком данных, передаваемых между двумя устройствами, в протоколе TCP используется механизм управления потоком (flow-control mechanism). Получатель докладывает отправителю о получении данных; получение такого уведомления позволяет установить размер окна. Окно определяет количество октетов, отсчитываемое от текущего номера подтверждения, которое TCP-устройство способно принять в заданный момент времени.

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

Размер окна TCP может изменяться в процессе передачи потока данных между двумя сетевыми устройствами. В каждом подтверждении, отправленном от получателя, содержится информация о количестве байтов, которые получатель способен принять. В протоколе TCP предусмотрено использование так называемого окна управления заторами, которое в нормальном состоянии равно окну устройства-получателя, но его размер уменьшается вдвое, если теряется какой-либо сегмент данных (например, при перегрузке в сети). Такой механизм позволяет уменьшать или увеличивать размер окна по мере необходимости в процессе управления буфером устройства и обработкой потока данных. Больший размер окна позволяет передать одновременно большее количество октетов.

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

Подтверждения

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

На рис. 7 показан отправитель, который передает пакеты 1, 2 и 3. Получатель подтверждает прием пакетов, запрашивая пакет 4. Отправитель, получив подтверждение, посылает пакеты 4, 5 и 6. Если пакет 5 не доставляется получателю, он посылает соответствующее подтверждение с запросом о повторной отправке пакета 5. Отправитель повторно отсылает пакет 5 и должен получить соответствующее подтверждение, чтобы продолжить передачу пакета с номером 7.

Протокол TCP обеспечивает соблюдение последовательности сегментов с последующим подтверждением. Каждой дейтаграмме перед передачей присваивается номер (рис. 8). После того как получатель принял все дейтаграммы, они собираются в завершенное сообщение. В обязанности протокола TCP входит восстановление поврежденных, утерянных, дублированных или пришедших в неверном порядке данных, которые передавались через сеть Internet. Механизм восстановления функционирует за счет назначения порядкового номера каждому переданному октету, после приема которого получатель должен отправить подтверждение (ACK). Если же в течение интервала времени ожидания подтверждение не было получено, данные передаются отправителем повторно. После доставки октетов получателю их порядковые номера используются для сборки сообщения из фрагментов и устранения дубликатов. Поврежденные данные восстанавливаются при помощи контрольной суммы, которая добавляется к каждому передаваемому сегменту. Контрольная сумма проверяется получателем, и, если она не совпадает, поврежденные данные отбрасываются.

Рис. 7. Размер окна равен трем

Рис. 8. Порядковые номера и подтверждения

Протокол TCP

TCP (Transmission Control Protocol - протокол управления передачей ) является протоколом с установлением соединения транспортного уровня и обеспечивает надежную, дуплексную передачу данных. Протокол TCP является частью стека протоколов TCP/IP. В среде с установлением соединения для начала передачи данных между двумя компьютерами должно быть установлено соединение. Протокол TCP отвечает за сегментацию сообщений в пакеты, повторную сборку их получателем и повторную передачу любых частей данных, если они не были приняты. Протокол также способен создавать виртуальные каналы между приложениями конечных пользователей.

Службы и протоколы верхнего уровня, которые используют механизмы TCP:

FTP (File Transfer Protocol - протокол передачи файлов);

HTTP (Hypertext Transfer Protocol - протокол передачи гипертекста);

SMTP (Simple Mail Transfer Protocol - простой протокол электронной почты);

Поля ТСР-сегмента, показанные на слайде, описаны ниже.

Порт отправителя - номер вызывающего порта.

Порт получателя - номер вызываемого порта.

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

Номер подтверждения - номер следующего ожидаемого ТСР-октета.

HLEN - количество 32!разрядных слов в заголовке.

Зарезервированное поле - все биты установлены в значение 0.

Биты кода - служебные функции (например, установка и завершение сеанса).

Окно - количество октетов, с которым отправитель готов согласиться.

Контрольная сумма - расчетная контрольная сумма заголовка и полей данных.

Указатель срочных данных - указывает конец срочных данных.

Параметры - в настоящее время определен один параметр: максимальный размер ТСР-сегмента.

Данные - данные протокола более высокого уровня.

Протокол UDP

UDP (User Datagram Protocol - протокол передачи дейтаграмм пользователя ), формат сегмента которого показан на слайде, является транспортным протоколом без установления соединения в стеке протоколов TCP/IP. UDP - это простой протокол, который осуществляет обмен дейтаграммами без подтверждения и без гарантии доставки. Простота протокола становится очевидной при сравнении форматов сегментов протоколов UDP и TCP. При использовании протокола UDP обработка ошибок и повторная передача данных должна осуществляться протоколом более высокого уровня. Например, если при пересылке данных по протоколу TFTP передача оборвалась, то только человек-оператор может повторно загрузить информацию.

В списке ниже перечислены поля UDP-сегмента, который показан на слайде

Порт отправителя - номер вызывающего порта.

Порт получателя - номер вызываемого порта.

Длина - количество байтов, включая заголовок и данные.

Контрольная сумма - расчетная контрольная сумма заголовка и полей данных.

Данные - данные протокола более высокого уровня.

В протоколе UDP не используется механизм скользящего окна, поэтому надежность передачи данных должна обеспечиваться протоколами уровня приложений (application layer protocol). Протокол UDP был разработан для приложений, у которых нет необходимости соединять вместе упорядоченные сегменты.

Протокол UDP используют такие службы и протоколы верхнего уровня:

TFTP (Trivial File Transfer Protocol - простейший протокол передачи файлов);

SNMP (Simple Network Management Protocol - простой протокол управления сетью);

DHCP (Dynamic Host Configuration Protocol - протокол динамической конфигурации узла);

DNS (Domain Name System - служба доменных имен).

Номера портов протоколов TCP и UDP

Для передачи информации на верхние уровни как протокол ТСР, так и протокол UDP используют номер порта (port) или так называемого сокета (socket). Номера портов используются для отслеживания различных взаимодействий, одновременно ведущихся в сети.

Разработчики прикладного программного обеспечения договорились пользоваться зарезервированными номерами портов, назначением которых руководит агентство по выделению имен и уникальных параметров протоколов Internet (IANA - Internet Assigned Numbers Authority). Например, при любом обмене, связанном с передачей данных по протоколу FTP, должны использоваться стандартные порты 20 (для данных) и 21 (для управления). Сетевым взаимодействиям, не связанным с приложениями, имеющими общеизвестный номер порта, номера портов присваиваются произвольным образом, но при этом они выбираются из конкретного диапазона значений - выше 1023. Некоторые порты зарезервированы в протоколах TCP и UDP. Несмотря на то, что некоторые порты зарезервированы в протоколах TCP и UDP, приложения могут быть не жестко привязаны к этим номерам.

Как показано на слайде, для выбора соответствующего приложения конечная система использует номер порта. Номер порта отправителя - обычно какой-либо номер больше 1023, который присваивается динамически узлом-отправителем. Например, узел пытается соединиться с другим узлом по протоколу FTP, отправляя пакеты, в которых указан номер TCP-порта получателя 21 (FTP), и динамически генерирует номер порта отправителя 1028. Такая пара портов (отправителя и получателя) определяет уникальность взаимодействия между двумя узлами. Если тот же узел инициирует FTP-соединение с третьим узлом, то порт получателя остается равным 21, но порт отправителя выбирается отличным от предыдущего (например, 1030), для того чтобы разделить два сеанса связи.

Алгоритм адаптивного тайм-аута KARN

Тайм-ауты

Номера байтов

Дубликаты

Проблемы, решаемые процедурой handshaking

Если станция передает 20 байт, то сервер увеличит ACK на 20 (станет 751 байт) и т.д.

Подтверждения генерируется для всех байт, которые приходят в нужной последовательности. Если будут переданы дубликаты, это не испортит картину. Можно 3 раза подтвердить, что пришло 731 байт (это пример). Все подтверждения кумулятивные. Потерянные подтверждения не создают проблем.

Дубликаты в TCP могут возникать:

1. Из-за потери оригинального сегмента
2. Из-за потери подтверждения
3. Из-за превышения времени повторной передачи
4. Из-за задержки сегмента
5. Из-за перебора всех возможных номеров байтов

Последовательные номера до 2 32 . При скорости 2 Мбит/сек на перебор всех значений уйдет 9 часов. Из-за дублирования последовательного номера может получиться дубликат. С повышением скорости вероятность этого увеличивается.

Борются невероятным количеством средств.

Задают тайм-ауты. Значение тайм-аута влияет на производительность. Тайм-аут связан с временем двойного пробега (RTT). Большой тайм-аут – большое ожидание при ошибке. Маленький тайм-аут – ненужная повторная передача.

Существуют различные алгоритмы адаптивного тайм-аута (задача ОС). CISCO использует алгоритм KARN.

Суть алгоритма. Вычисляется среднее время RTT, умножается на определенный коэффициент (в KARN коэффициент равен 2). Необходимо изменять не только среднее время тайм-аута, но изменять размер окна. В KARN окно меняется до тех пор, пока свободным не станет от 20% до 40% от окна.

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

Завершается соединение, когда станция шлет серверу флаг FIN. Сервер отсылает ACK и FIN. Далее сервер шлет еще раз FIN, а станция ACK и FIN.

Защита от перегрузок – медленный старт – не сразу и быстро отправлять пакеты в сеть.

Существует также механизм быстрой повторной передачи (не нужен медленный старт) и

механизм задержанного подтверждения (в Windows).

Что такое скользящее окно?

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

Скользящее окно TCP

Что такое транспортный протокол?

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

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

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

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

Если, наоборот, вероятность столкновения данных велика, TCP уменьшает размер скользящего окна. Если размер скользящего окна принять равным восьми пакетам при обычном сетевом трафике, то в худших условиях, когда Интернет сильно загружен, его размер может уменьшиться до пяти. Наоборот, когда данных в сети немного, размер окна может увеличиться, например, до 10-20 пакетов.

Имейте в виду, что описанная в предыдущих абзацах схема несколько упрощена. На самом деле TCP задает размер окна в байтах. То есть размер окна по умолчанию может равняться нескольким тысячам байтов, а не восьми, десяти и двенадцати байтам, как в предыдущем примере. Как правило, модуль TCP передает несколько сегментов, прежде чем скользящее окно заполнится целиком. Большинство систем в Интернет устанавливают окно равным по умолчанию 4096 байтам. Иногда размер окна равен 8192 или 16384 байтам.

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

Итак, существует два метода организации процесса обмена квитанциями: метод простоя источника и метод скользящего окна.

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

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

Рис. 1. Метод простоя источника

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

Второй метод называется методом скользящего окна (sliding window). В этом методе для повышения скорости передачи данных источнику разрешается передать некоторое количество кадров в непрерывном режиме, то есть в максимально возможном для источника темпе еще до получения на эти кадры квитанций. Количество кадров, которые разрешается передавать таким образом, называется размером окна.

Рисунок 2 иллюстрирует применение данного метода для окна размером 5 кадров. В начальный момент, когда еще не послано ни одного кадра, окно определяет диапазон номеров кадров от 1 до 5 включительно. Источник начинает передавать кадры и через какое-то время получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности (но не обязательно в том же темпе), что и кадры, которым они соответствуют. В момент получения отправителем квитанции 1 окно сдвигается на одну позицию вверх, определяя новый диапазон разрешенных к отправке кадров (от 2 до 6).

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

Рис. 2. Метод скользящего окна

После получения квитанции 2 (на кадр 2) окно сдвигается вверх на единицу, определяя диапазон разрешенных к передаче кадров от 3 до 7. Аналогичное «скольжение» окна вверх происходит после получения каждой квитанции: окно сдвигается вверх на 1, но его размер при этом не меняется и остается равным 5. После прихода квитанции 8 окно оказывается в диапазоне от 9 до 13 и остается таковым достаточно долго, так как по каким-то причинам источник перестает получать подтверждения о доставке кадров. Отправив последний разрешенный кадр 13, передатчик снова прекращает передачу с тем, чтобы возобновить ее после прихода квитанции 9.

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

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

Данный алгоритм (алгоритм LZ77 4Назван по именам авторов Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Опубликован в 1977 году. ) был одним из первых, использующих словарь . В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность перемещается ("скользит") по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n . Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и только первый элемент незакодированной последовательности - {0, 1, e} .

Описанная выше схема кодирования приводит к понятию скользящего окна (англ. sliding window), состоящего из двух частей:

1. подпоследовательность уже закодированных элементов длины N - словарь - буфер поиска (англ. search buffer);
2. подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (англ. look-ahead buffer).

В терминах скользящего окна алгоритм сжатия описывается так: если e 1 , . . . , e i - уже закодированная подпоследовательность, то e i-N+1 , . . . , e i - суть словарь или буфер поиска, а e i+1 , . . . , e i+n - буфер предварительного просмотра. Аналогично, задача состоит в поиске наибольшей цепочки элементов из буфера предварительного просмотра, начиная с элемента e i+1 , совпадающей с цепочкой из буфера поиска - эта цепочка может начинаться с любого элемента и заканчиваться любым элементом , т.е. выходить за пределы буфера поиска, вторгаясь в буфер предварительного просмотра. Естественно, что выходить за пределы скользящего окна нельзя. Пусть в скользящем окне найдена максимальная по длине совпавшая цепочка элементов e i-p , . . . , e i+q , тогда она будет закодирована следующим образом: {p+1, q+p+1, e i+p+q+2 } - смещение относительно начала буфера предварительного просмотра (e i+1) , длина совпавшей цепочки, элемент, следующий за совпавшей цепочкой из буфера предварительного просмотра. Если в результате поиска найдено два совпадения с одинаковой длиной, то выбирается ближайшее к началу буфера предварительного просмотра. После этого скользящее окно смещается на p + q + 2 элементов вперед, и процедура поиска повторяется.

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

Приведем пример сжатия данным алгоритмом. Сожмем строку "TOBEORNOTTOBE" с параметрами N = 10 и n = 3 :

Если выделить для хранения смещения 4 бита, длины - 2 бита, а элементов - 8 бит, то длина закодированной последовательности (без учета обозначения конца последовательности) составит 4 x 8 + 2 x 8 + 8 x 8 = 112 бит, а исходной - 102 бита. В данном случае мы не сжали последовательность, а, наоборот, увеличили избыточность представления. Это связано с тем, что длина последовательности слишком мала для такого алгоритма. Но, например, рисунок кодового дерева Хаффмена на рис. 13.1 , занимающий 420 килобайт дискового пространства, после сжатия имеет размер около 310 килобайт.

Ниже приведен псевдокод алгоритма сжатия.

// M - фиксированная граница // считываем символы последовательно из входного потока // in - вход - сжатая последовательность // n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // SlideWindow - буфер поиска while(!in.EOF()) //пока есть данные { // ищем максимальное совпадение и его параметры SlideWindow.FindBestMatch(in, n, pos, len, nelem); // пишем выход: смещение, длина, элемент out.Write(pos); out.Write(len); out.Write(nelem); // сдвинем скользящее окно на len + 1 элементов SlideWindow.Move(in, len + 1); } Листинг 13.2. Алгоритм сжатия методом LZ77

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

Видно, что процесс декодирования значительно проще с вычислительной точки зрения.

// n - максимальная длина цепочки // pos - положение в словаре, len - длина цепочки // nelem - элемент за цепочкой, str - найденная цепочка // in - вход, out - выход // Dict - словарь while(!in.EOF()) //пока есть данные { in.Read(pos); in.Read(len); in.Read(nelem); if(pos == 0) { //новый отдельный символ //удаляем из словаря первый (дальний) один элемент Dict.Remove(1); //добавляем в словарь элемент Dict.Add(nelem); out.Write(nelem); } else { //скопируем соответствующую строку из словаря str = Dict.Get(pos, len); //удалим из словаря len + 1 элементов Dict.Remove(len + 1); //Добавляем в словарь цепочку Dict.Add(str + nelem); out.Write(str + nelem); } } Листинг 13.3. Алгоритм

Данный алгоритм является родоначальником целого семейства алгоритмов, и сам по себе в изначальном виде практически не используется. К его достоинствам можно отнести приличную степень сжатия на достаточно больших последовательностях, быструю распаковку, а также отсутствие патента 5документ, обеспечивающий исключительное право эксплуатировать изобретение в течение известного времени (обычно 15-20 лет) на алгоритм. К недостаткам относят медленную скорость сжатия, а также меньшую, чем у альтернативных алгоритмов, степень сжатия (модификации алгоритма борются с этим недостатком). Сочетание алгоритмов Хаффмена (Huffman) ( "Алгоритмы сжатия изображений без потерь") и LZ77 называют методом DEFLATE 6Так называется сжатие, а разжатие называется INFLATE (англ. DEFLATE - сдувать, INFLATE - надувать). . Метод DEFLATE используется в графическом формате PNG, а также в универсальном формате сжатия данных ZIP.