Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

Пропорциональная маршрутизация

Большинство алгоритмов маршрутизации пытаются искать наилучшие пути для каждого адресата и направлять весь трафик по оптимальному пути. Альтернативный подход, позволяющий повысить качество обслуживания, состоит в разделении трафика для одного и того же адресата между несколькими маршрутами. Поскольку маршрутизаторы обычно не следят за нагрузкой на всю сеть в целом, остается лишь один способ разделения трафика — на основе доступной локальной информации. Одним из простых методов является маршрутизация, пропорциональная или эквивалентная емкостям исходящих связей. Однако существуют и более сложные алгоритмы (Nelakuditi и Zhang, 2002).

Диспетчеризация пакетов

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

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

Однако и с этим алгоритмом связана одна проблема: предоставляемая им пропускная способность напрямую зависит от размера пакета, используемого хостом: большая часть предоставляется хостам с большими пакетами, и меньшая — хостам с небольшими пакетами. В книге (Demers и др., 1990) предлагается улучшенная версия, в которой циклический опрос производится с целью выхватывания не пакета, а байта. То есть очереди сканируются побайтно до того момента, пока не будет выхвачен последний байт последнего пакета. После этого пакеты Отправляются в том порядке, в котором они заканчивались при опросе очередей. Алгоритм проиллюстрирован на рис. 5.31.

Рис. 5.31. Маршрутизатор с пятью очередями пакетов для линии О (а); время окончания сканирования для пяти пакетов (б)

На рис. 5.31, а мы видим пакеты длиной от 2 до 6 байт. Во время (виртуального) первого такта извлекается первый байт пакета с линии А. Затем следует первый байт пакета с линии В, и т. д. Первым, через 8 тактов, закончится пакет С. Порядок сортировки пакетов приведен на рисунке справа (рис. 5.31, б). При отсутствии новых поступлений пакеты будут отсылаться в указанном порядке, начиная с С и заканчивая А.

Проблема данного алгоритма заключается в том, что он дает всем хостам одинаковые приоритеты. Во многих случаях желательно предоставлять, например, видеосерверам большую пропускную способность, чем обычным файл-серверам, чтобы они могли посылать два или более байт за такт опроса. Такая модификация алгоритма называется взвешенным справедливым обслуживанием. Иногда весовой коэффициент эквивалентен числу потоков, генерируемых машиной, таким образом все процессы получают равные доли пропускной способности. Одна из эффективных реализаций данного алгоритма описывается в (Shreedhar и Varghese, 1995). Все чаще и чаще встречаются аппаратные реализации передачи пакетов через маршрутизаторы или коммутаторы (Elhanany и др., 2001).


Математика Вычислить двойной интеграл примеры
Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес