Сетевой уровень

1. Сетевой уровень

2. Функционирование протоколов сетевого уровня

3. Сервисы, предоставляемые транспортному уровнь

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

4.

5.

6.

7. Алгоритмы маршрутизации

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

8. Алгоритмы маршрутизации

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

9. Алгоритмы маршрутизации

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

10. Алгоритмы маршрутизации

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

11. Алгоритмы маршрутизации

• Желательно, чтобы алгоритм выбора
маршрута обладал определенными
свойствами
–
–
–
–
–
–
корректностью,
простотой,
надежностью,
устойчивостью,
справедливостью,
оптимальностью.

12. Алгоритмы маршрутизации

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

13. Неадаптивные алгоритмы

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

14. Адаптивные алгоритмы

• Изменяют решение о выборе маршрутов
при изменении топологии и также часто в
зависимости от загруженности линий.
• Адаптивные алгоритмы отличаются:
– источниками получения информации,
– моментами изменения маршрутов,
– данными, использующимися для
оптимизации.

15. Принцип оптимальности маршрута

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

16. Принцип оптимальности маршрута

• Если маршрутизатор В
располагается на оптимальном
маршруте от маршрутизатора А к
маршрутизатору С, то оптимальный
маршрут от маршрутизатора В к
маршрутизатору С совпадет с
частью первого маршрута.

17. Принцип оптимальности маршрута

• Прямым следствием принципа оптимальности
является возможность рассмотрения
множества оптимальных маршрутов от всех
источников к приемникам в виде дерева.
• Такое дерево называется входным деревом.
Расстояния измеряются количеством
транзитных участков.

18. Принцип оптимальности маршрута

• У одной сети могут существовать несколько
входных деревьев с одинаковыми длинами путей.
• Цель всех алгоритмов выбора маршрутов
заключается в вычислении и использовании
входных деревьев для всех маршрутизаторов.

19. Принцип оптимальности маршрута

(a) Подсеть (b) Входное дерево для маршрутизатора
B

20. Принцип оптимальности маршрута

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

21. Выбор кратчайшего пути

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

22. Выбор кратчайшего пути

• Один из способов измерения длины пути состоит в
подсчете количества транзитных участков.
• В таком случае пути ABC и ABE имеют
одинаковую длину. Можно измерять расстояния в
километрах. В таком случае окажется, что путь
ABC значительно длиннее пути ABE.

23. Выбор кратчайшего пути

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

24. Выбор кратчайшего пути

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

25. Выбор кратчайшего пути

Первые пять шагов вычисления кратчайшего пути от A к D.
Стрелка указывает на рабочий узел

26. Заливка

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

27. Заливка

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

28. Заливка

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

29. Заливка

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

30. Заливка

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

31. Заливка

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

32. Заливка

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

33. Заливка

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

34. Заливка

• Третье применение алгоритма заливки —
эталонное тестирование других алгоритмов
выбора маршрутов, так как заливка всегда
находит все возможные пути в сети, а
следовательно, и кратчайшие.
• Ухудшить эталонные показатели времени
доставки могут разве что накладные расходы,
вызванные огромным количеством пакетов,
формируемых самим алгоритмом заливки.

35. Маршрутизация по вектору расстояний

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

36. Маршрутизация по вектору расстояний

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

37. Маршрутизация по вектору расстояний

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

38. Маршрутизация по вектору расстояний

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

39. Маршрутизация по вектору расстояний

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

40. Маршрутизация по вектору расстояний

• Допустим, одна из таких таблиц пришла от
соседа X, и в ней указывается, что время
распространения от маршрутизатора X до
маршрутизатора i равно Хi.
• Если маршрутизатор знает, что время пересылки
до маршрутизатора X равно m, тогда задержка
при передаче пакета маршрутизатору i через
маршрутизатор X составит Xi + m.

41. Маршрутизация по вектору расстояний

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

42. Маршрутизация по вектору расстояний

43. Проблема счета до бесконечности

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

44. Проблема счета до бесконечности

45. Маршрутизация с учетом состояния линии

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

46. Знакомство с соседями

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

47. Знакомство с соседями

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

48. Знакомство с соседями

• Когда два или более маршрутизаторов
объединены в локальную сеть, ситуация
несколько усложняется.
• Один из способов моделирования локальной
сети состоит в том, что ЛВС рассматривается
в виде узла графа, как и маршрутизаторы.

49. Знакомство с соседями

(a) Девять маршрутизаторов и LAN. (b)
Графовая модель (a).

50. Измерение стоимости линии

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

51. Измерение стоимости линии

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

52. Измерение стоимости линии

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

53. Создание пакетов состояния линий

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

54. Создание пакетов состояния линий

(a) Подсеть (b) Пакеты состояния линий для
этой подсети

55. Создание пакетов состояния линий

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

56. Распространение пакетов состояния линий

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

57. Распространение пакетов состояния линий

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

58. Распространение пакетов состояния линий

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

59. Распространение пакетов состояния линий

• Маршрутизаторы записывают все пары
(источник, порядковый номер), которые
им попадаются.
• Когда приходит новый пакет состояния
линий, маршрутизатор ищет адрес его
отправителя и порядковый номер
пакета в своем списке.

60. Распространение пакетов состояния линий

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

61. Распространение пакетов состояния линий

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

62. Распространение пакетов состояния линий

3. может произойти искажение
порядкового номера — например,
вместо номера 4 будет принято число
65 540 (ошибка в 1-м бите); в этом
случае пакеты с 5-го по 65 540-й
будут игнорироваться некоторыми
маршрутизаторами как устаревшие.

63. Распространение пакетов состояния линий

• Решение проблем заключается в
помещении в пакет после его
порядкового номера возраста пакета
и уменьшении его на единицу
каждую секунду.
• Когда возраст уменьшается до нуля,
информация от этого
маршрутизатора удаляется.

64. Распространение пакетов состояния линий

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

65. Распространение пакетов состояния линий

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

66. Распространение пакетов состояния линий

Буфер пакетов маршрутизатора B

67. Распространение пакетов состояния линий

• Каждый ряд в структуре данных, используемой
маршрутизатором B соответствует недавно
полученному, но еще не полностью обработанному
пакету состояния линий.
• В таблице записываются адрес отправителя,
порядковый номер, возраст и данные.
• В таблице содержатся флаги рассылки и
подтверждений для каждой из трех линий
маршрутизатора В (к А, С и F соответственно).

68. Распространение пакетов состояния линий

• Флаги отсылки означают, что этот
пакет следует отослать по
соответствующей линии.
• Флаги подтверждений означают, что
нужно подтвердить получение этого
пакета по данной линии.

69. Распространение пакетов состояния линий

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

70. Вычисление новых маршрутов

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

71. Вычисление новых маршрутов

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

72. Вычисление новых маршрутов

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

73. Вычисление новых маршрутов

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

74. Вычисление новых маршрутов

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

75. Протоколы, применяющие маршрутизацию с учетом состояния линии

• Открытый протокол внутреннего
шлюза OSPF.
• Связь между промежуточными
системами - IS-IS.

76. Иерархическая маршрутизация

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

77. Иерархическая маршрутизация

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

78. Иерархическая маршрутизация

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

79. Иерархическая маршрутизация

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

80. Иерархическая маршрутизация

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

81. Иерархическая маршрутизация

Иерархическая маршрутизация

82. Иерархическая маршрутизация

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

83. Иерархическая маршрутизация

• Если подсеть разбить на 24 региона
по 30 маршрутизаторов в каждом
регионе, тогда каждому
маршрутизатору потребуется 30
локальных записей плюс 23 записи
об удаленных регионах.
• Итого 53 записи.

84. Иерархическая маршрутизация

• При выборе трехуровневой иерархии,
состоящей из 8 кластеров по 9 регионов из 10
маршрутизаторов, каждому маршрутизатору
понадобится 10 строк в таблице для
локальных маршрутизаторов, 8 строк для
маршрутизации в другие регионы в пределах
своего кластера, плюс 7 строк для удаленных
кластеров.
• Итого 25 строк.

85. Иерархическая маршрутизация

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

86. Иерархическая маршрутизация

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

87. Широковещательная маршрутизация

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

88. Широковещательная маршрутизация

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

89. Широковещательная маршрутизация

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

90. Широковещательная маршрутизация

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

91. Широковещательная маршрутизация

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

92. Широковещательная маршрутизация

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

93. Широковещательная маршрутизация

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

94. Широковещательная маршрутизация

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

95. Широковещательная маршрутизация

• Единственной проблемой этого метода
является то, что каждому маршрутизатору
необходимо обладать информацией о
связующем дереве.
• Иногда такая информация доступна
(например, в случае маршрутизации с учетом
состояния линий), но иногда — нет (при
маршрутизации по векторам расстояний).

96. Широковещательная маршрутизация

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

97. Широковещательная маршрутизация

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

98. Широковещательная маршрутизация

• Тогда маршрутизатор рассылает этот пакет по
всем линиям, кроме той, по которой он
прибыл.
• Однако если пакет прибывает от того же
источника по другой линии, он отвергается
как вероятный дубликат.

99. Широковещательная маршрутизация

Продвижение по встречному пути (a) Подсеть (b)
связующее дерево (c) Дерево, построенное методом
продвижения по встречному пути

100. Многоадресная рассылка

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

101. Многоадресная рассылка

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

102. Многоадресная рассылка

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

103. Многоадресная рассылка

(a) Подсеть. (b) Связующее дерево для самого левого
маршрутизатора. (c) Многоадресное дерево для группы 1.
(d) Многоадресное дерево для группы 2.

104. Многоадресная рассылка

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

105. Многоадресная рассылка

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

106. Многоадресная рассылка

• Также пакет PRUNE может отправить
маршрутизатор, у которого нет хостов,
входящих в группу, если он получил
многоадресное сообщение по всем своим
линиям.
• В результате подсеть постепенно рекурсивно
усекается.

107. Многоадресная рассылка

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

108. Многоадресная рассылка

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

109. Алгоритмы маршрутизации для мобильных хостов

WAN, с которой соединены LAN, MAN, и
беспроводные соты

110. Алгоритмы маршрутизации для мобильных хостов

Маршрутизация пакетов мобильным хостам

111. Маршрутизация в специальных сетях

Ситуация с мобильными маршрутизаторами:
1.Военная техника.
– Отсутствие инфраструктуры.
2.Морская флотилия.
– Постоянное перемещение
3.Службы спасения.
– Инфраструктура разрушена.
4. Собрание людей с портативными компьютерами.
– Отсутствие 802.11.

112. Построение маршрута

(a) Зона широковещания А.
(b) После получения B и D широковещательного пакета от A.
(c) После получения C, F и G широковещательного пакета от A.
(d) После получения E, H, и I широковещательного пакета от A.

113. Построение маршрута

Формат пакета ROUTE REQUEST.

114. Построение маршрута

Формат пакета ROUTE REPLY.

115. Обслуживание маршрута

(a) Таблица маршрутизации узла D перед выходом из сети узла G.
(b) граф-схема сети после выхода из нее G.

116. Алгоритмы борьбы с перегрузкой

117. Перегрузка

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

118. Перегрузка

• За борьбу с перегрузкой отвечают
сетевой и транспортный уровни.
• Сетевой уровень должен решить, что
делать с лишними пакетами.
• Эффективный метод борьбы с
перегрузкой — снижение нагрузки
на сеть со стороны транспортного
уровня.

119. Перегрузка

120. Перегрузка

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

121. Перегрузка

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

122. Перегрузка

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

123. Перегрузка

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

124. Предотвращение перегрузки

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

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

• Управление потоком относится к
трафику между двумя конкретными
станциями — отправителем и
получателем.
• Задача управления потоком состоит в
согласовании скорости передачи
отправителя со скоростью, с которой
получатель способен принимать поток
пакетов.

126. Борьба с перегрузкой и управление потоком

• Лучшее решение проблем перегрузки и
управления потоком — добиться того,
чтобы хост работал медленнее.
• Хост может получить просьбу замедлить
передачу в двух случаях: когда с
передаваемым потоком не справляется
получатель или когда с ним не
справляется вся сеть.

127. Подходы к борьбе с перегрузкой

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

128. Подходы к борьбе с перегрузкой

• Временные шкалы подходов к борьбе с
перегрузкой:

129. Обеспечение сети

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

130. Обеспечение сети

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

131. Учет состояния трафика

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

132. Учет состояния трафика

• Можно отвести трафик от загруженных
линий, изменив весовые коэффициенты
кратчайшего пути.
• Такие решения называются
маршрутизацией с учетом состояния
трафика (traffic-aware routing). В этом
случае полезно разделять трафик,
направляя его по разным линиям.

133. Управление доступом

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

134. Управление доступом

• В сети виртуальных каналов новые
соединения могут быть отклонены,
если они приведут к перегрузке сети.
• Это называется управлением
доступом (admission control).

135. Регулирование трафика

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

136. Регулирование трафика

• Регулирование трафика (traffic throttling)
требует обнаруживать зарождающуюся
перегрузку.
• Если маршрутизаторы будут следить за средней
нагрузкой на сеть, временем ожидания в очереди
и числом утерянных пакетов. Увеличение
значений параметров сигнализирует о
приближении к перегрузке.

137. Регулирование трафика

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

138. Сброс нагрузки

• Если все остальные методы не работают, сеть
вынуждена удалить пакеты, которые она не
может доставить.
• Для этого используется общий термин сброс
нагрузки (load shedding).
• Если правильно выбрать удаляемые пакеты,
можно предотвратить затор.

139. Маршрутизация с учетом состояния трафика

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

140. Маршрутизация с учетом состояния трафика

• Протоколы маршрутизации сети Интернет
обычно не строят маршруты на основании
нагрузки на сеть.
• Вместо этого перегрузки регулируются вне
протокола маршрутизации за счет изменения
входных данных.
• Это называется управлением трафиком
(traffic engineering).

141. Управление доступом

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

142. Управление доступом

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

143. Управление доступом

• Часто в качестве характеристик
трафика выступают скорость и
форма.
• Вопрос простого описания этих
характеристик достаточно трудный:
трафик обычно неравномерен,
поэтому средняя скорость не
является показательной.

144. Управление доступом

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

145. Управление доступом

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

146. Управление доступом

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

147. Управление доступом

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

148. Управление доступом

• Можно совместить принципы
управления доступом и маршрутизации
с учетом состояния трафика, направляя
маршруты в обход ≪горячих точек≫.
• Предположим, что хост, соединенный с
маршрутизатором A, хочет установить
соединение с хостом, соединенным с
маршрутизатором B.

149. Управление доступом

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

150. Управление доступом

а – перегруженная сеть;
б – часть сети без перегрузки

151. Регулирование трафика

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

152. Регулирование трафика

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

153. Регулирование трафика

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

154. Регулирование трафика

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

155. Регулирование трафика

• Средние показатели использования линий не
отражают реальной картины при прерывистом
трафике.
• Так, значение 50 % — это немного при сплошном
трафике и слишком много при переменном
трафике. Число утерянных пакетов становится
известно слишком поздно: пакеты начинают
теряться уже после возникновения перегрузки.

156. Регулирование трафика

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

157. Регулирование трафика

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

158. Регулирование трафика

• ЭВСС (экспоненциально взвешенное
скользящее среднее — Exponentialy
Weighted Moving Average, EWMA)
сглаживает различные флуктуации и
работает как фильтр низких частот.
• Как только значение d выходит за
пороговый уровень, маршрутизатор
узнает о начале перегрузки.

159. Регулирование трафика

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

160. Регулирование трафика

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

161. Сдерживающие пакеты

• Самый простой способ сообщить
отправителю о перегрузке — сказать об этом
прямо.
• При таком подходе маршрутизатор выбирает
перегружающий пакет и отправляет
источнику сдерживающий пакет (choke
packet).
• Информация об источнике берется из
задержанного пакета.

162. Сдерживающие пакеты

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

163. Сдерживающие пакеты

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

164. Сдерживающие пакеты

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

165. Сдерживающие пакеты

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

166. Явное уведомление о перегрузке

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

167. Явное уведомление о перегрузке

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

168. Явное уведомление о перегрузке

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

169. Явное уведомление о перегрузке

170. Обратное давление на ретрансляционных участках

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

171. Обратное давление на ретрансляционных участках

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

172. Обратное давление на ретрансляционных участках

• Как только сдерживающий пакет достигает
точки F, поток данных от F в сторону D
должен быть уменьшен. Таким образом, F
резервирует для соединения большее
количество буферной памяти: источник все
еще продолжает заваливать это направление
своими данными.

173. Обратное давление на ретрансляционных участках

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

174. Обратное давление на ретрансляционных участках

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

175. Обратное давление на ретрансляционных участках

Обратное
давление на
ретрансляцион
ных участках

176. Обратное давление на ретрансляционных участках

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

177. Сброс нагрузки

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

178. Сброс нагрузки

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

179. Сброс нагрузки

• Для передачи файла более старый пакет
ценится выше нового, так как отвержение
пакета номер 6 и сохранение пакетов с
номерами, например, с 7 по 10 лишь заставит
получателя выполнить лишнюю работу:
поместить в буфер данные, которые он еще не
может использовать.

180. Сброс нагрузки

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

181. Сброс нагрузки

• Первую стратегию (старое лучше нового)
часто называют винной стратегией, а вторую
(новое лучше старого) — молочной
стратегией.

182. Сброс нагрузки

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

183. Сброс нагрузки

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

184. Сброс нагрузки

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

185. Сброс нагрузки

• При отсутствии стимула все будут помечать
свои пакеты не иначе как ОЧЕНЬ ВАЖНО —
НИ В КОЕМ СЛУЧАЕ НЕ ВЫБРАСЫВАТЬ.
• Предотвращение неоправданного использования
таких отметок часто достигается за счет сетевых
ресурсов и денежных средств.

186. Сброс нагрузки

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

187. Случайное раннее обнаружение

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

188. Случайное раннее обнаружение

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

189. Случайное раннее обнаружение

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

190. Случайное раннее обнаружение

• Реакцией транспортных протоколов
наподобие TCP на утерю пакетов при
перегрузке является ответное снижение
трафика от источника.

191. Случайное раннее обнаружение

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

192. Случайное раннее обнаружение

• Чтобы TCP работал эффективно,
беспроводные линии связи должны
справляться с ошибками передачи на
канальном уровне (так, чтобы на сетевом
уровне они были не видны).

193. Случайное раннее обнаружение

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

194. Случайное раннее обнаружение

• Популярный алгоритм, реализующий данную
идею, называется случайным ранним
обнаружением (RED — Random Early
Detection).
• Для определения условий, при которых
следует начинать терять пакеты,
маршрутизаторы постоянно высчитывают
скользящее среднее длин своих очередей.

195. Случайное раннее обнаружение

• Когда средняя длина очереди на какой-либо
связи превышает пороговое значение, эта
связь объявляется перегруженной и
небольшая часть пакетов удаляется
случайным образом.

196. Случайное раннее обнаружение

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

197. Случайное раннее обнаружение

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

198. Случайное раннее обнаружение

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

199. Случайное раннее обнаружение

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

200. Случайное раннее обнаружение

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

201. Качество обслуживания

202. Качество обслуживания

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

203. Качество обслуживания

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

204. Качество обслуживания

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

205. Качество обслуживания

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

206. Качество обслуживания

• Благодаря механизмам обеспечения
качества обслуживания сеть может
выполнить свои обязательства даже
при резком увеличении объема
трафика за счет отклонения
некоторых запросов.

207. Качество обслуживания

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

208. Качество обслуживания

3. Как зарезервировать ресурсы на
маршрутизаторах, необходимые для
обеспечения производительности.
4. Может ли сеть принять больший
объем трафика.

209. Качество обслуживания

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

210. Требования приложений

• Последовательность пакетов, передающихся
от источника к приемнику, называется
потоком (flow).
• При этом в сетях, ориентированных на
соединение, поток могут составлять все
пакеты соединения, а в сетях без
установления соединения — все пакеты,
отправленные от одного процесса к другому.

211. Требования приложений

• Каждому потоку требуются условия,
характеризуемые четырьмя основными
параметрами:
–
–
–
–
пропускная способность;
задержка;
флуктуация;
потери.
• Вместе они формируют качество обслуживания
(QoS — Quality of Service).

212. Требования приложений

• Требования к сети являются менее жесткими,
чем требования приложений, так как в
некоторых случаях приложение может само
улучшить уровень обслуживания,
предоставленный сетью.
• Для надежной передачи файлов сеть не
обязана работать без потерь; время задержки
не должно быть одинаковым при передаче
пакетов для аудио и видео.

213. Требования приложений

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

214. Строгость требований приложений к качеству обслуживания

215. Пропускная способность

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

216. Задрежки

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

217. Задрежки

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

218. Задрежки

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

219. Флуктуации

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

220. Флуктуации

• Видео- и особенно аудиоданные
исключительно чувствительны к
флуктуациям.

221. Потери

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

222. Потери

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

223. Требования приложений

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

224. Требования приложений

1. Постоянная битовая скорость (телефония).
2. Переменная битовая скорость в реальном
времени (сжатые видеоданные при проведении
видеоконференций).
3. Переменная битовая скорость не в реальном
времени (просмотр фильмов).
4. Доступная битовая скорость (передача
файлов).

225. Требования приложений

• Постоянная битовая скорость — это попытка
моделирования проводной сети путем
предоставления фиксированной пропускной
способности и фиксированной задержки.

226. Требования приложений

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

227. Требования приложений

• Фильмы на самом деле проигрываются
не в реальном времени: часто несколько
секунд видеозаписи доставляется перед
проигрыванием и хранится в буфере,
поэтому флуктуации попросту приводят
к колебаниям объема видео, которое
было получено, но не воспроизведено.

228. Требования приложений

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

229. Формирование трафика

• Прежде чем гарантировать пользователю
определенное качество обслуживания, сеть
должна знать примерный объем трафика.
• В телефонных сетях его оценить легко:
обычный звонок (в несжатом формате)
требует скорости 64 Кбит/с и одного 8битного отсчета каждые 125 мкс.

230. Формирование трафика

• В инфокоммуникационных сетях трафик
является неравномерным.
• Трафик неравномерен по 3 причинам:
– непостоянная скорость трафика (например,
при видеоконференциях со сжатием);
– взаимодействие пользователя и
приложения;
– переключение компьютера между
задачами.

231. Формирование трафика

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

232. Формирование трафика

• Формирование трафика (traffic shaping) —
способ регулировки средней скорости и
равномерности потока входных данных.
• Приложения должны иметь возможность
передавать такой трафик, который им нужен
(включая неравномерный); при этом
необходим простой и удобный способ
описания возможных схем трафика.

233. Формирование трафика

• Когда устанавливается поток,
пользователь и сеть (то есть клиент
и оператор связи) договариваются об
определенной схеме (то есть форме)
трафика для данного потока.

234. Формирование трафика

• Иногда такое соглашение называется
соглашением об уровне обслуживания
(SLA, Service Level Agreement).
• До тех пор пока клиент выполняет свою
часть условий соглашения и посылает
пакеты не чаще оговоренного в договоре
графика, интернет-провайдер обязуется
доставлять их в определенный срок.

235. Формирование трафика

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

236. Формирование трафика

• Пакеты, отправка которых выходит
за рамки условий соглашения, могут
удаляться или помечаться как
низкоприоритетные.
• Наблюдение за потоком трафика
называется политикой трафика
(traffic policing).

237. Формирование трафика

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

238. Алгоритмы дырявого и маркерного ведра

• Независимо от скорости, с которой вода
наливается в ведро, выходной поток обладает
постоянной скоростью R, когда в ведре есть
вода, и нулевой скоростью, когда ведро
пустое.
• Когда ведро наполняется и вода занимает весь
объем B, вся лишняя вода выливается через
край и теряется.

239. Алгоритмы дырявого и маркерного ведра

а — формирование пакетов;
б — дырявое ведро; в — маркерное ведро

240. Алгоритмы дырявого ведра

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

241. Алгоритм дырявого ведра

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

242. Алгоритм маркерного ведра

• Другой вариант представляется в виде
ведра, которое в данный момент
наполняется. Вода вытекает из крана со
скоростью R, а объем ведра равен B.
• Чтобы отправить пакет, необходимо,
чтобы из ведра можно было вылить воду
(маркеры).

243. Алгоритм маркерного ведра

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

244. Формирование трафика маркерным ведром

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

245. Формирование трафика маркерным ведром

• Предположим, что маршрутизаторы могут
принимать данные на максимальной скорости
только в течение небольших промежутков
времени — до тех пор, пока буфер не
заполнится.
• Размер буфера составляет 9600 Кбайт, что
меньше, чем объем пикового трафика.

246. Формирование трафика маркерным ведром

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

247. Формирование трафика маркерным ведром

• Чтобы избежать такой утери пакетов, можно
сформировать трафик на хосте по методу
маркерного ведра. Если скорость R равна 200
Мбит/с, а емкость B равна 9600 Кбайт, трафик
попадает в границы возможностей сети.
• Хост может отправлять трафик на максимальной
скорости в 1000 Мбит/с в течение небольшого
промежутка времени — до тех пор, пока ведро не
станет пустым.

248. Формирование трафика маркерным ведром

• Затем он должен будет снизить скорость до 200
Мбит/с и отправить оставшуюся часть трафика.
Идея в том, чтобы растянуть время отправки
пикового трафика (пачки пакетов), если сеть не в
состоянии обработать его в один прием.

249. Формирование трафика маркерным ведром

250. Формирование трафика маркерным ведром

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

251. Формирование трафика маркерным ведром

• Чтобы трафик был равномерным, его можно
сформировать. На схеме в показан исходящий
трафик маркерного ведра со скоростью 200 Мбит/с
и емкостью 0. Трафик полностью выровнен.
• Крупные пачки не принимаются; трафик приходит
с постоянной скоростью. Уровень воды в ведре,
соответственно, всегда равен нулю (схема е).
Трафик помещается в очередь хоста, и в каждый
момент времени какой-то пакет ожидает отправки.

252. Формирование трафика маркерным ведром

• Когда трафик не поступает, ведро постепенно
наполняется; пока данные приходят со
скоростью заполнения ведра, оно остается
пустым.

253. Формирование трафика маркерным ведром

• Такое ведро маршрутизатор может
использовать для проверки трафика,
передаваемого хостом.
• Его можно расположить на одном из концов
сети; если трафик соответствует маркерному
ведру, указанному в соглашении об
обслуживании, он сможет через него пройти.

254. Формирование трафика маркерным ведром

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

255. Формирование трафика маркерным ведром

• В примере ведро становится пустым лишь на
короткое время — после получения большого
объема трафика. После этого оно
восстанавливается и снова готово принять
такой трафик.

256. Реализация маркерного ведра

• Дырявое ведро и маркерное ведро просты в
реализации.
• На практике маркерное ведро и сеть имеют
дело с дискретными величинами.
• Реализация алгоритма маркерного ведра
подразумевает наличие переменной,
считающей маркеры. Счетчик увеличивается
на R/DT.

257. Реализация маркерного ведра

• Если все пакеты имеют одинаковый объем,
уровень ведра можно измерять в пакетах
(например, 200 Мбит — это 20 пакетов по
1250 байт).
• Чаще всего используются пакеты разного
размера. Тогда уровень ведра исчисляется в
байтах.

258. Реализация маркерного ведра

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

259. Реализация маркерного ведра

• Один из способов получения более гладкого
трафика состоит в помещении еще одного
маркерного ведра после первого.
• Скорость второго ведра должна быть гораздо
выше скорости первого.

260. Реализация маркерного ведра

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

261. Реализация маркерного ведра

• Например, если скорость второго
ведра равна 500 Мбит/с, а емкость —
0, первая пачка поступит в сеть с
максимальной скоростью 500
Мбит/с.
• Это меньше, чем наше предыдущее
значение 1000 Мбит/с.

262. Реализация маркерного ведра

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

263. Реализация маркерного ведра

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

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

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

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

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

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

• Алгоритмы распределения
ресурсов маршрутизатора между
пакетами потока и
конкурирующими потоками
называются алгоритмами
диспетчеризации пакетов
(packet scheduling algorithm).

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

Резервироваться могут три типа
ресурсов:
1. Пропускная способность.
2. Буферное пространство.
3. Время центрального процессора.

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

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

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

• Когда прибывает пакет, он хранится в
буфере маршрутизатора до тех пор,
пока он не будет передан по
выбранной исходящей линии.

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

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

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

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

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

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

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

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

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

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

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

• При этом отправка пакетов происходит в том
же порядке, в котором они пришли.
• Этот принцип называется FIFO (First-In
First-Out, первым пришел — первым
ушел), или FCFS (First-Come First-Serve,
первым пришел — первым
обслуживается).

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

• Маршрутизаторы, работающие по принципу
FIFO, при переполнении очереди обычно
удаляют последние прибывшие пакеты.
• Такое поведение называется ≪обрубанием
хвоста≫ (tail drop).

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

• Алгоритм случайного раннего обнаружения
(RED) удаляет новые пакеты случайным
образом при росте длины очереди.
• Другие алгоритмы диспетчеризации
используют для выбора удаляемых пакетов
самые разные возможности.

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

• Диспетчеризация FIFO не позволяет обеспечить
высокое качество обслуживания: если потоков
несколько, один из них может влиять на
производительность других.
• Если первый поток будет вести себя агрессивно и
отправлять большие объемы трафика, его пакеты
будут помещаться в очередь.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работа алгоритма: а — взвешенное справедливое
обслуживание;
б — время окончания отправки для пакетов

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

• При условии отсутствия новых пакетов
порядок окончания отправки пакетов будет
таким: A, B, F, D (хотя F прибывает после D).
• Если в верхний поток поступит небольшой
пакет, который закончит отправку раньше D,
то он обойдет D только в том случае, если его
передача еще не началась.

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

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

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

• Алгоритм дает всем хостам одинаковые
приоритеты. Во многих случаях желательно
предоставлять, например, видео-серверам
большую пропускную способность, чем обычным
файл-серверам, чтобы они могли посылать два или
более байт за цикл.
• Такая модификация алгоритма называется
взвешенным справедливым обслуживанием
(WFQ — Weighted Fair Queueing).

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

• Упрощенная схема DRR (deficit round robin),
работает эффективнее.
• Она широко применяется для алгоритма
взвешенного справедливого обслуживания.

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

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

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

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

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

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

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

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

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

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

297. Управление доступом

• Гарантии качества обслуживания
выполняются через управление доступом.
• Пользователь передает в сеть поток,
предъявляя определенные требования к
качеству обслуживания.

298. Управление доступом

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

299. Управление доступом

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

300. Управление доступом

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

301. Управление доступом

• Чтобы выполнить свои обязательства перед
клиентом, сеть выберет другой путь для
отправки крупного потока.
• Такой подход называется QoSмаршрутизацией (QoS routing).

302. Управление доступом

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

303. Управление доступом

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

304. Управление доступом

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

305. Управление доступом

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

306. Управление доступом

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

307. Управление доступом

• Гарантии позволяют добавить
дополнительный поток, используя
фиксированные мощности.
• Некоторые приложения могут
поторговаться за параметры пакетов,
а некоторые не могут.

308. Управление доступом

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

309. Управление доступом

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

310. Управление доступом

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

311. Управление доступом

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

312. Пример спецификации потока

Параметр
Размер маркерного ведра
Единицы
измерения
Байт
Минимальный размер пакета
Байт
Скорость маркерного ведра
байт/с
Пиковая скорость передачи данных
байт/с
Максимальный размер пакета
Байт

313. Управление доступом

Гарантии пропускной способности и задержки с
использованием маркерных ведер и взвешенного
справедливого обслуживания

314. Управление доступом

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

315. Управление доступом

• Если трафик передается пачками, то пачка
максимального размера, B, может прибыть на
маршрутизатор целиком.
• Тогда максимальная задержка, D, будет равна
времени прохождения пакета через
маршрутизатор при фиксированной
пропускной способности, или B/R (не считая
эффектов пакетирования).

316. Управление доступом

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

317. Управление доступом

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

318. Управление доступом

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

319. Максимальная задержка

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

320. Интегральное обслуживание

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

321. Интегральное обслуживание

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

322. Интегральное обслуживание

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

323. Интегральное обслуживание

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

324. RSVP — протокол резервирования ресурсов

• Главная составляющая архитектуры
интегрального обслуживания, открытая для
пользователей сети, называется протоколом
резервирования ресурсов (RSVP —
Resource reSerVation Protocol).
• Протокол предназначен для резервирования
ресурсов; другие протоколы применяются для
описания передачи данных.

325. RSVP — протокол резервирования ресурсов

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

326. RSVP — протокол резервирования ресурсов

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

327. RSVP — протокол резервирования ресурсов

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

328. RSVP — протокол резервирования ресурсов

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

329. RSVP — протокол резервирования ресурсов

330. RSVP — протокол резервирования ресурсов

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

331. RSVP — протокол резервирования ресурсов

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

332. RSVP — протокол резервирования ресурсов

333. Дифференцированное обслуживание

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

334. Дифференцированное обслуживание

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

335. Дифференцированное обслуживание

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

336. Дифференцированное обслуживание

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

337. Дифференцированное обслуживание

• Подход известен как ориентированное на
классы (в отличие от ориентированного на
потоки) качество обслуживания.
• Была стандартизована специальная
архитектура под названием
дифференцированное обслуживание
(differentiated services).

338. Дифференцированное обслуживание

• Дифференцированное обслуживание может
предоставляться набором маршрутизаторов,
образующих административный домен
(например, интернет-провайдер или
телефонную компанию).
• Администрация определяет множество
классов обслуживания и соответствующие
правила маршрутизации.

339. Дифференцированное обслуживание

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

340. Дифференцированное обслуживание

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

341. Дифференцированное обслуживание

• К трафику класса могут предъявляться
определенные требования, касающиеся его
формы.
• Например, от него может потребоваться,
чтобы он представлял собой ≪дырявое
ведро≫ с определенной скоростью
просачивания данных через ≪дырочку≫.

342. Дифференцированное обслуживание

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

343. Дифференцированное обслуживание

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

344. Дифференцированное обслуживание

• Рассмотрим в качестве примера
интернет-телефонию.
• При потоковом алгоритме
обслуживания каждому
телефонному соединению
предоставляются собственные
ресурсы и гарантии.

345. Дифференцированное обслуживание

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

346. Срочная пересылка

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

347. Срочная пересылка

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

348. Срочная пересылка

• Их нужно пересылать между сетями так,
будто кроме них в сети больше нет вообще
никаких пакетов.
• Тогда они получат обслуживание с низкими
потерями, низкой задержкой и низкой
флуктуацией — как раз то, что нужно для IPтелефонии.

349. Срочная пересылка

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

350. Срочная пересылка

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

351. Срочная пересылка

352. Срочная пересылка

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

353. Срочная пересылка

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

354. Гарантированная пересылка

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

355. Гарантированная пересылка

• Кроме того, определены три класса
игнорирования пакетов, попавших в
затор (низкий, средний и высокий).
• Итого получается 12 сочетаний, то
есть 12 классов обслуживания.

356. Гарантированная пересылка

• На первом шаге пакеты разбиваются на
четыре класса приоритетов. Эта процедура
может выполняться на хосте-источнике или
на первом маршрутизаторе.
• Скорость высокоприоритетных пакетов
может быть ограничена оператором в рамках
соглашения о предоставлении услуг.

357. Гарантированная пересылка

Возможная реализация гарантированной пересылки
потока данных

358. Гарантированная пересылка

• Следующий шаг — определение
классов игнорирования пакетов.
• Для этого пакеты каждого класса
приоритетов проходят проверку с
помощью маркерного ведра или
похожей схемы.

359. Гарантированная пересылка

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

360. Гарантированная пересылка

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

361. Гарантированная пересылка

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

362. Гарантированная пересылка

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

363. Гарантированная пересылка

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