Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 126
Текст из файла (страница 126)
Маршрутизатор, ужаснувшись при виде последнего числа, может отвергнуть такой поток. При минимальном размере пакета, равном 1000 байт, 5-мегабайтный поток тем же самым маршрутизатором мог бы быть принят. Пропорциональная маршрутизация Большинство алгоритмов маршрутизации пытаются искать наилучшие пути для каждого адресата и направлять весь трафик по оптимальному пути. Альтернативный подход, позволяющий повысить качество обслуживания, состоит в разделении трафика для одного и того же адресата между несколькими маршрутами. Поскольку маршрутизаторы обычно не следят за нагрузкой на всю сеть в целом, остается лишь один способ разделения графика — на основе доступной локальной информации.
Одним из простых методов является маршрутизация, пропорциональная или эквивалентная емкостям исходящих связей. Однако существуют и более сложные алгоритмы ()че1акийс! и ХЬапя, 2002). Диспетчеризация пакетов Если маршрутизатор имеет поддержку нескольких потоков, существует опасность того, что один из них захватит слишком большую часть пропускной способности и не даст жить всем остальным потокам. Обработка пакетов в порядке поступления может привести к тому, что агрессивный источник загрузит все производственные мощности маршрутизаторов, через которые проходит его поток, и тем самым снизит качество обслуживания других источников. Для пресечения Качество обслуживания 4 71 подобных попыток были разработаны алгоритмы диспетчеризации пакетов (ВЬЮ и Сготчсго)Г, 2000).
Одним из первых был алгоритм справедливого обслуживания (Хая1е, 1987), Суть его состоит в том, что маршрутизаторы организуют отдельные очереди для каждой исходящей линии, по одной для каждого потока. Как только линия освобождается, маршрутизатор начинает циклически сканировать очереди, выбирая первый пакет следующей очереди, Таким образом, если за данную исходящую динию борются и хостов, то каждый из них имеет возможность отправить свой пакет, пропустив п — 1 чужих пакетов. Агрессивному хосту не поможет то, что в его очереди стоит больше пакетов, чем у остальных. Однако и с этим алгоритмом связана одна проблема: предоставляемая им пропускная способность напрямую зависит от размера пакета, используемого хостом: болыпая часть предоставляется хостам с большими пакетами, и меньшая— хостам с небольшими пакетами.
В книге (Оешегз и др., 1990) предлагается улучшенная версия, в которой циклический опрос производится с целью выхватывания не пакета, а байта. То есть очереди сканируются побайтно до того момента, пока не будет выхвачен последний байт последнего пакета. После этого пакеты отправляются в том порядке, в котором они заканчивались при опросе очередей. Алгоритм проиллюстрирован на рпс, 5.31. Пакет Время финишироввния 17 1В 20 в б Рис. В.З1. Маршрутизатор о пятью очередями пакетов для линии О 1в); время окончания оквнированиядля пяти пвкетов(б) На рис.
5.31, а мы видим пакеты длиной от 2 до 6 байт. Во время (виртуального) первого такта извлекается первый байт пакета с линии А, Затем следует чтервый байт пакета с линии В, и т. д. Первым, через 8 тактов, закончится пакет С Порядок сортировки пакетов приведен на рисунке справа (рис. 5.31, 6). При ~тгсутствии новых поступлений пакеты будут отсылаться в указанном порядке, тначииая с С и заканчивая А.
Проблема данного алгоритма заключается в том, что он дает всем хостам одиНаковые приоритеты. Во многих случаях желательно предоставлять, например, 472 Глава 5. Сетевой уровень видеосерверам большую пропускную способность, чем обычным файл-серверам, чтобы они могли посылать два или более байт за такт опроса. Такая модификация алгоритма называется взвешенным справедливым обслуживанием. Иногда весовой коэффициент эквивалентен числу потоков, генерируемых машиной, таким образом все процессы получают равные доли пропускной способности.
Одна из эффективных реализаций данного алгоритма описывается в (5ЬгеедЬаг и ЧагйЬезе, 1995). Все чаще и чаще встречаются аппаратные реализации передачи пакетов через маршрутизаторы или коммутаторы (Е1Ьапапу и др., 2001). Интегральное обслуживание В 1995 — 1997 годы проблемная группа проектирования сети Интернет (1ЕТР) прилагала множество усилий по продвижению архитектуры потокового мультимедиа. В результате появилось две дюжины документов КРС, начинающихся с префикса КРС и включающих порядковые номера 2205 — 2210, Общее название этих трудов — потоковые алгоритмы или интегральное обслуживание. Предлагаемая технология предназначена как для одноадресных, так и для многоадресных приложений.
Примером первых может быть видеоклип на сайте новостей, доставляемый в виде потока пользователю, пожелавшему посмотреть его. Пример вторых — набор станций цифрового телевидения, осуществляющих широковешательное распространение своих программ в виде потоков 1Р-пакетов. Данной услугой может пользоваться большое число абонентов, расположенных в разных географических точках. Далее мы более подробно рассмотрим многоадресную рассылку, поскольку одиоцадресная передача — это лишь особый случай многоадресной.
Во многих приложениях с многоадресной маршрутизацией группы пользователей могут меняться динамически. Например, люди могут подкл1очаться к участию в видеоконференциях, но со временем это занятие им надоедает, и они переключаются на мыльные оперы или спортивные каналы. В данном случае стратегия предварительного резервирования пропускной способности не совсем подходит, потому что при этом каждому источнику пришлось бы запоминать все изменения в составе аудитории.
В системах, предназначенных для передачи телевизионного сигнала миллионам абонентов, такой подход и вовсе нс годится. ЙЗЧР— протокол резервирования ресурсов Главный протокол архитектуры интегрального обслуживания, разработанный 1ЕТР, называется протоколом резервирования ресурсов (ЕБЧР— Кезоцгсе ге5егЪ'аг(оп Ргогосо1), Он описывается в документе КРС 2205 и других документах-протоколах.
Как следует из названия, протокол предназначен для резервирования Ресурсов; другие протоколы применяются для описания передачи данных. ЮЧР позволяет нескольким отправителям посылать данные нескольким группам абонентов, разрешает отдельным получателям переключать каналы и оптимизирует использование пропускной способности, в то же время устраняя возникновение перегрузки. Качество обслуживания 473 Простейшая форма этого протокола использует многоадресную маршрутизацию с применением связующих деревьев, обсуждавшуюся ранее.
Каждой группе назначается групповой адрес. Чтобы послать данные группе, отправитель помешает ее адрес в заголовки пакетов. Затем стандартный алгоритм многоадресной маршрутизации строит связующее дерево, покрываюшее всех членов группы. Алгоритм маршрутизации не является частью протокола КЗ'тгр. Единственное отличие от нормальной многоадресной маршрутизации состоит в том, что группе периодически рассылается дополнительная информация, с помошью которой маршрутизаторы обновляют определенные структуры данных. Для примера рассмотрим сеть, показанную на рис. 5.32, а. Хосты 1 и 2 являются многоадресными передатчиками, а хосты 3, 4 и 5 — многоадресными приемниками. В данном примере передатчики и приемники разделены, однако в обшем случае эти два множества могут перекрываться.
Деревья многоадресной рассылки для хостов 1 и 2 показаны на рис. 5.32, б и в соответственно. Передатчики Дз Да Дб Дз Де Дв $~ 4 )е Приемники Рис. 6 32. Сеть (а); связующее дерево многоадресной рассылки для хоста 1 (б); связующее дерево многоадресной рассылки для хоста 2 (е) Для улучшения качества приема и устранения перегрузки каждый получатель в группе может послать передатчику (вверх по дереву) запрос на резервирование, Запрос продвигается, используя обсуждавшийся ранее алгоритм обратного, пути. На каждом транзитном участке маршрутизатор замечает запрос и резервиРует необходимую пропускную способность.
Если пропускной способности недостаточно, он отвечает сообщением об ошибке. К тому моменту как запрос доходит до передатчика, пропускная способность зарезервирована вдоль всего пути от отправителя к получателю. 414 Глава 5. Сетевой уровень Пример резервирования показан на рис.
5.33, а. Здесь хост 3 запросил канал к хосту 1. После создания канала поток пакетов от хоста 1 к хосту 3 может течь, не боясь попасть в затор. Рассмотрим, что произойдет, если теперь хост 3 зарезервирует канал к другому передатчику, хосту 2, чтобы пользователь мог одновременно смотреть две телевизионные программы, Зарезервированный второй канал показан на рис. 5.33, б. Обратите вниманигк между хостом 3 и маршрутизатором Е требуется наличие двух отдельных каналов, так как передаются два независимых потока. Пропускная способность, зарезервированная дпя источника 2 Е ° Е 0 Пропускная спокоен зарезервированна для источника т Н ° ) 6 Рис. 5.33. Хост 3 запрашивает канал к хосту 1 (е); затем хост 3 запрашивает второй канал к хосту 2 (б); хост 5 запрашивает канал к хосту! (в) Наконец, на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
