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

Содержание

Слайд 2

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

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

Слайд 3

Сервисы, предоставляемые транспортному уровнь Сервисы сетевого уровня не должны зависеть от

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

Сервисы сетевого уровня не должны зависеть от технологии

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

Слайд 5

Слайд 6

Слайд 7

Алгоритмы маршрутизации Основная функция сетевого уровня заключается в выборе маршрута для

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

Основная функция сетевого уровня заключается в выборе маршрута для пакетов

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

Алгоритмы маршрутизации Алгоритм маршрутизации реализуется той частью программного обеспечения сетевого уровня,

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

Алгоритм маршрутизации реализуется той частью программного обеспечения сетевого уровня, которая

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

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

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

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

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

Алгоритмы маршрутизации Один из них обрабатывает приходящие пакеты и выбирает для

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

Один из них обрабатывает приходящие пакеты и выбирает для них

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

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

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

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


устойчивостью,
справедливостью,
оптимальностью.
Слайд 12

Алгоритмы маршрутизации В качестве компромисса многие сети стараются минимизировать количество пересылок

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

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

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

Неадаптивные алгоритмы Не учитывают при выборе маршрута топологию и текущее состояние

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

Не учитывают при выборе маршрута топологию и текущее состояние сети

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

Адаптивные алгоритмы Изменяют решение о выборе маршрутов при изменении топологии и

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

Изменяют решение о выборе маршрутов при изменении топологии и также

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

Принцип оптимальности маршрута Общие положения, описывающие оптимальные маршруты, вне зависимости от

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

Общие положения, описывающие оптимальные маршруты, вне зависимости от топологии

или трафика.
Основополагающей идеей является принцип оптимальности.
Слайд 16

Принцип оптимальности маршрута Если маршрутизатор В располагается на оптимальном маршруте от

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

Если маршрутизатор В располагается на оптимальном маршруте от маршрутизатора

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

Принцип оптимальности маршрута Прямым следствием принципа оптимальности является возможность рассмотрения множества

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

Прямым следствием принципа оптимальности является возможность рассмотрения множества оптимальных

маршрутов от всех источников к приемникам в виде дерева.
Такое дерево называется входным деревом. Расстояния измеряются количеством транзитных участков.
Слайд 18

Принцип оптимальности маршрута У одной сети могут существовать несколько входных деревьев

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

У одной сети могут существовать несколько входных деревьев с

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

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

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

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

Слайд 20

Принцип оптимальности маршрута Входное дерево не содержит петель, поэтому каждый пакет

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

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

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

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

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

Идея заключается в построении графа подсети, в котором каждый

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

Выбор кратчайшего пути Один из способов измерения длины пути состоит в

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

Один из способов измерения длины пути состоит в подсчете

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

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

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

Возможен учет и других параметров. Например, каждой дуге графа

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

Выбор кратчайшего пути В общем случае параметры дуг графа являются функциями

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

В общем случае параметры дуг графа являются функциями расстояния,

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

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

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

Первые пять шагов вычисления кратчайшего пути от 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

Маршрутизация с учетом состояния линии Каждый маршрутизатор должен: Обнаруживать своих соседей

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

Каждый маршрутизатор должен:
Обнаруживать своих соседей и узнавать

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

Знакомство с соседями Когда маршрутизатор загружается, его первая задача состоит в

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

Когда маршрутизатор загружается, его первая задача состоит в получении

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

Знакомство с соседями Имена маршрутизаторов должны быть совершенно уникальными, поскольку, если

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

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

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

Знакомство с соседями Когда два или более маршрутизаторов объединены в локальную

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

Когда два или более маршрутизаторов объединены в локальную сеть,

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

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

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

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

Слайд 50

Измерение стоимости линии Алгоритм маршрутизации с учетом состояния линии требует от

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

Алгоритм маршрутизации с учетом состояния линии требует от каждого

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

Измерение стоимости линии Измерив время двойного оборота этого пакета и разделив

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

Измерив время двойного оборота этого пакета и разделив его

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

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

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

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

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

Создание пакетов состояния линий После того как информация, необходимая для обмена,

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

После того как информация, необходимая для обмена, собрана,

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

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

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

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

подсети
Слайд 55

Создание пакетов состояния линий Самое трудное при создании пакетов заключается в

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

Самое трудное при создании пакетов заключается в выборе

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

Распространение пакетов состояния линий Самая сложная часть алгоритма заключается в распространении

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

Самая сложная часть алгоритма заключается в распространении пакетов

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

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

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

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

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

Распространение пакетов состояния линий Основная идея алгоритма распространения пакетов состояния линии

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

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

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

Распространение пакетов состояния линий Маршрутизаторы записывают все пары (источник, порядковый номер),

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

Маршрутизаторы записывают все пары (источник, порядковый номер), которые

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

Распространение пакетов состояния линий Если это новый пакет, он рассылается дальше

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

Если это новый пакет, он рассылается дальше по

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

Распространение пакетов состояния линий Проблемы с алгоритмом: если последовательный номер, достигнув

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

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

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

Распространение пакетов состояния линий 3. может произойти искажение порядкового номера —

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

3. может произойти искажение порядкового номера — например,

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

Распространение пакетов состояния линий Решение проблем заключается в помещении в пакет

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

Решение проблем заключается в помещении в пакет после

его порядкового номера возраста пакета и уменьшении его на единицу каждую секунду.
Когда возраст уменьшается до нуля, информация от этого маршрутизатора удаляется.
Слайд 64

Распространение пакетов состояния линий В нормальной ситуации новый пакет приходит, например,

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

В нормальной ситуации новый пакет приходит, например, каждые

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

Распространение пакетов состояния линий Поле возраста также уменьшается на единицу каждым

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

Поле возраста также уменьшается на единицу каждым маршрутизатором

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

Распространение пакетов состояния линий Буфер пакетов маршрутизатора B

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

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

Слайд 67

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

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

Каждый ряд в структуре данных, используемой маршрутизатором B

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

Распространение пакетов состояния линий Флаги отсылки означают, что этот пакет следует

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

Флаги отсылки означают, что этот пакет следует отослать

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

Распространение пакетов состояния линий Пакет состояния линий от маршрутизатора А пришел

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

Пакет состояния линий от маршрутизатора А пришел напрямую,

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

Вычисление новых маршрутов Собрав полный комплект пакетов состояния линий, маршрутизатор может

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

Собрав полный комплект пакетов состояния линий, маршрутизатор может построить

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

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

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

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

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

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

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

В подсети, состоящей из n маршрутизаторов, у каждого из

которых k соседей, количество памяти, необходимой для хранения входной информации, пропорционально kn.
Может потребоваться много времени на обработку информации.
Слайд 73

Вычисление новых маршрутов Неисправности оборудования или программного обеспечения могут привести к

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

Неисправности оборудования или программного обеспечения могут привести к очень

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

Вычисление новых маршрутов Если маршрутизатор не сможет переслать пакеты или повредит

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

Если маршрутизатор не сможет переслать пакеты или повредит их

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

Протоколы, применяющие маршрутизацию с учетом состояния линии Открытый протокол внутреннего шлюза

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

Открытый протокол внутреннего шлюза OSPF.
Связь

между промежуточными системами - IS-IS.
Слайд 76

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

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

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


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

Иерархическая маршрутизация Возрастает размер служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает

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

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

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

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

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

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

регионы.
Каждый маршрутизатор знает все детали выбора маршрутов в пределах своей области, но ему ничего не известно о внутреннем строении других регионов.
Слайд 79

Иерархическая маршрутизация При объединении нескольких сетей естественно рассматривать их как отдельные

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

При объединении нескольких сетей естественно рассматривать их как отдельные регионы,

при этом маршрутизаторы одной сети освобождаются от необходимости знать топологию других сетей.
Слайд 80

Иерархическая маршрутизация В очень больших сетях двухуровневой иерархии может оказаться недостаточно.

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

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

потребоваться группировать регионы в кластеры, кластеры в зоны, зоны в группы, и т.д.
Слайд 81

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

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

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

Слайд 82

Иерархическая маршрутизация Платой за уменьшение размеров таблицы маршрутов является увеличение длины

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

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


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

Иерархическая маршрутизация Если подсеть разбить на 24 региона по 30 маршрутизаторов

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

Если подсеть разбить на 24 региона по 30 маршрутизаторов в

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

Иерархическая маршрутизация При выборе трехуровневой иерархии, состоящей из 8 кластеров по

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

При выборе трехуровневой иерархии, состоящей из 8 кластеров по 9

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

Иерархическая маршрутизация Оптимальное количество уровней иерархии для подсети, состоящей из N

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

Оптимальное количество уровней иерархии для подсети, состоящей из N маршрутизаторов,

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

Иерархическая маршрутизация В некоторых приложениях хостам требуется посылать сообщения на множество

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

В некоторых приложениях хостам требуется посылать сообщения на множество хостов

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

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

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

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

заинтересованным хостам получить их.
Широковещанием называется рассылка пакетов по всем пунктам назначения.
Слайд 88

Широковещательная маршрутизация Один из методов широковещательной маршрутизации не требует никаких способностей

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

Один из методов широковещательной маршрутизации не требует никаких способностей от

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

Широковещательная маршрутизация Еще одним очевидным кандидатом является метод заливки. Проблема с

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

Еще одним очевидным кандидатом является метод заливки.
Проблема с применением

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

Широковещательная маршрутизация Третий алгоритм называется многоадресной маршрутизацией. При использовании этого метода

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

Третий алгоритм называется многоадресной маршрутизацией.
При использовании этого метода в

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

Широковещательная маршрутизация Маршрутизатором создается копия пакета для каждой из используемых исходящих

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

Маршрутизатором создается копия пакета для каждой из используемых исходящих линий.

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

Широковещательная маршрутизация Многоадресная маршрутизация подобна индивидуально адресуемым пакетам с той разницей,

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

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

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

Широковещательная маршрутизация Четвертый алгоритм широковещательной маршрутизации в явном виде использует корневое

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

Четвертый алгоритм широковещательной маршрутизации в явном виде использует корневое дерево

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

Широковещательная маршрутизация Если каждый маршрутизатор знает, какие из его линий принадлежат

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

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

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

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

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

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

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

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

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

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

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

Широковещательная маршрутизация Когда прибывает широковещательный пакет, маршрутизатор проверяет, используется ли та

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

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

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

Широковещательная маршрутизация Тогда маршрутизатор рассылает этот пакет по всем линиям, кроме

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

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

по которой он прибыл.
Однако если пакет прибывает от того же источника по другой линии, он отвергается как вероятный дубликат.
Слайд 99

Широковещательная маршрутизация Продвижение по встречному пути (a) Подсеть (b) связующее дерево

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

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

Дерево, построенное методом продвижения по встречному пути
Слайд 100

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

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

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

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

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

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

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

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

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

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

Алгоритм маршрутизации должен знать о присоединении хоста к какой-нибудь группе.


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

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

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

(a) Подсеть. (b) Связующее дерево для самого левого маршрутизатора.

(c) Многоадресное дерево для группы 1.
(d) Многоадресное дерево для группы 2.
Слайд 104

Многоадресная рассылка Многоадресные пакеты рассылаются только вдоль соответствующего их группе усеченного

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

Многоадресные пакеты рассылаются только вдоль соответствующего их группе усеченного связующего

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

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

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

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

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

Многоадресная рассылка Также пакет PRUNE может отправить маршрутизатор, у которого нет

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

Также пакет PRUNE может отправить маршрутизатор, у которого нет хостов,

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

Многоадресная рассылка Недостаток данного алгоритма заключается в его плохой применимости к

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

Недостаток данного алгоритма заключается в его плохой применимости к большим

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

Многоадресная рассылка Альтернативный метод использует деревья с основанием в сердцевине, где

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

Альтернативный метод использует деревья с основанием в сердцевине, где для

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

Алгоритмы маршрутизации для мобильных хостов WAN, с которой соединены LAN, MAN, и беспроводные соты

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

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

беспроводные соты
Слайд 110

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

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

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

Слайд 111

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

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

Ситуация с мобильными маршрутизаторами:
Военная техника.
Отсутствие инфраструктуры.
Морская флотилия.
Постоянное перемещение
Службы

спасения.
Инфраструктура разрушена.
Собрание людей с портативными компьютерами.
Отсутствие 802.11.
Слайд 112

Построение маршрута (a) Зона широковещания А. (b) После получения B и

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

(a) Зона широковещания А.
(b) После получения B и D широковещательного

пакета от A.
(c) После получения C, F и G широковещательного пакета от A.
(d) После получения E, H, и I широковещательного пакета от A.
Слайд 113

Построение маршрута Формат пакета ROUTE REQUEST.

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

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

Слайд 114

Построение маршрута Формат пакета ROUTE REPLY.

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

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

Слайд 115

Обслуживание маршрута (a) Таблица маршрутизации узла D перед выходом из сети

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

(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) требует обнаруживать зарождающуюся перегрузку. Если

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

Регулирование трафика (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) можно получить

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

Такую оценку времени ожидания в очереди (d) можно получить с

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

Регулирование трафика ЭВСС (экспоненциально взвешенное скользящее среднее — Exponentialy Weighted Moving

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

ЭВСС (экспоненциально взвешенное скользящее среднее — 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 мгновенно спадает. На

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

Нагрузка на 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 на утерю пакетов

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

Реакцией транспортных протоколов наподобие TCP на утерю пакетов при

перегрузке является ответное снижение трафика от источника.
Слайд 191

Случайное раннее обнаружение Обоснование такой логики состоит в том, что TCP

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

Обоснование такой логики состоит в том, что TCP предназначен

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

Случайное раннее обнаружение Чтобы TCP работал эффективно, беспроводные линии связи должны

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

Чтобы 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. Как зарезервировать ресурсы на маршрутизаторах, необходимые для обеспечения

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

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. Переменная битовая скорость

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

1. Постоянная битовая скорость (телефония).
2. Переменная битовая скорость в реальном

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

Требования приложений Постоянная битовая скорость — это попытка моделирования проводной сети

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

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

предоставления фиксированной пропускной способности и фиксированной задержки.
Слайд 226

Требования приложений Битовая скорость может быть переменной, например, при передаче сжатого

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

Битовая скорость может быть переменной, например, при передаче сжатого видео,

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

Требования приложений Фильмы на самом деле проигрываются не в реальном времени:

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

Фильмы на самом деле проигрываются не в реальном времени: часто

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

Требования приложений Приложениям типа электронной почты нужно принципиальное наличие хоть какой-нибудь

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

Приложениям типа электронной почты нужно принципиальное наличие хоть какой-нибудь битовой

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

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

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

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

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

Формирование трафика В инфокоммуникационных сетях трафик является неравномерным. Трафик неравномерен по

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

В инфокоммуникационных сетях трафик является неравномерным.
Трафик неравномерен по 3

причинам:
непостоянная скорость трафика (например, при видеоконференциях со сжатием);
взаимодействие пользователя и приложения;
переключение компьютера между задачами.
Слайд 231

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

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

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

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

Формирование трафика Формирование трафика (traffic shaping) — способ регулировки средней скорости

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

Формирование трафика (traffic shaping) — способ регулировки средней скорости и

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

Формирование трафика Когда устанавливается поток, пользователь и сеть (то есть клиент

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

Когда устанавливается поток, пользователь и сеть (то есть клиент и

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

Формирование трафика Иногда такое соглашение называется соглашением об уровне обслуживания (SLA,

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

Иногда такое соглашение называется соглашением об уровне обслуживания (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/ΔT.
Слайд 257

Реализация маркерного ведра Если все пакеты имеют одинаковый объем, уровень ведра

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

Если все пакеты имеют одинаковый объем, уровень ведра можно

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

Реализация маркерного ведра Недостатком алгоритма маркерного ведра является то, что скорость

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

Недостатком алгоритма маркерного ведра является то, что скорость передачи

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

Реализация маркерного ведра Один из способов получения более гладкого трафика состоит

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

Один из способов получения более гладкого трафика состоит в

помещении еще одного маркерного ведра после первого.
Скорость второго ведра должна быть гораздо выше скорости первого.
Слайд 260

Реализация маркерного ведра Первое ведро определяет характеристики трафика и фиксирует его

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

Первое ведро определяет характеристики трафика и фиксирует его скорость,

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

Реализация маркерного ведра Например, если скорость второго ведра равна 500 Мбит/с,

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

Например, если скорость второго ведра равна 500 Мбит/с, а

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

Реализация маркерного ведра Когда маркерные ведра используются для формирования трафика на

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

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

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

Реализация маркерного ведра Рассмотренные методы позволяют формировать сетевой трафик, приводя его

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

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

более управляемому виду и обеспечивая тем самым выполнение требований по качеству обслуживания.
Слайд 264

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

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

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


Для этого будем считать, что все пакеты в потоке следуют по одному и тому же пути.
Слайд 265

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

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

При распределении их случайным образом между несколькими маршрутизаторами невозможно что-либо

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

Диспетчеризация пакетов Алгоритмы распределения ресурсов маршрутизатора между пакетами потока и конкурирующими

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

Алгоритмы распределения ресурсов маршрутизатора между пакетами потока и конкурирующими потоками

называются алгоритмами диспетчеризации пакетов (packet scheduling algorithm).
Слайд 267

Диспетчеризация пакетов Резервироваться могут три типа ресурсов: 1. Пропускная способность. 2.

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

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

центрального процессора.
Слайд 268

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

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

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

чем канал может обработать.
Слайд 269

Диспетчеризация пакетов Когда прибывает пакет, он хранится в буфере маршрутизатора до

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

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

пор, пока он не будет передан по выбранной исходящей линии.
Слайд 270

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

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

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

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

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

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

Время центрального процесса также может расходоваться на обработку пакетов.
Существует

предельная скорость, с которой маршрутизатор может обрабатывать пакеты.
Слайд 272

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

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

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

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

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

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

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

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

Диспетчеризация пакетов Простейший вариант диспетчера: Каждый маршрутизатор помещает пакеты в очередь

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

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

каждой исходящей линии), где пакеты ждут отправки.
Слайд 275

Диспетчеризация пакетов При этом отправка пакетов происходит в том же порядке,

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

При этом отправка пакетов происходит в том же порядке, в

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

Диспетчеризация пакетов Маршрутизаторы, работающие по принципу FIFO, при переполнении очереди обычно

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

Маршрутизаторы, работающие по принципу FIFO, при переполнении очереди обычно удаляют

последние прибывшие пакеты.
Такое поведение называется ≪обрубанием хвоста≫ (tail drop).
Слайд 277

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

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

Алгоритм случайного раннего обнаружения (RED) удаляет новые пакеты случайным образом

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

Диспетчеризация пакетов Диспетчеризация FIFO не позволяет обеспечить высокое качество обслуживания: если

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

Диспетчеризация FIFO не позволяет обеспечить высокое качество обслуживания: если потоков

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

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

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

Если пакеты обрабатываются в порядке поступления, агрессивный отправитель захватит большую

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

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

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

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

множество различных алгоритмов диспетчеризации пакетов.
Слайд 281

Диспетчеризация пакетов Одним из первых алгоритмов диспетчеризации пакетов был алгоритм справедливого

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

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

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

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

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

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

первый пакет следующей очереди.
Слайд 283

Диспетчеризация пакетов Если за данную исходящую линию борются n хостов, то

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

Если за данную исходящую линию борются 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), работает эффективнее. Она

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

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

применяется для алгоритма взвешенного справедливого обслуживания.
Слайд 292

Диспетчеризация пакетов Существуют другие алгоритмы диспетчеризации. К ним относится, например, приоритетная

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

Существуют другие алгоритмы диспетчеризации. К ним относится, например, приоритетная диспетчеризация,

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

Диспетчеризация пакетов Пакеты с одинаковым приоритетом отправляются по принципу FIFO. Существенным

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

Пакеты с одинаковым приоритетом отправляются по принципу FIFO.
Существенным недостатком

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

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

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

Если присвоить высокоприоритетной очереди большой вес (скажем, 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,

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

Если трафик передается пачками, то пачка максимального размера, B, может

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

Управление доступом Если этот показатель слишком высокий, поток может запросить большую

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

Если этот показатель слишком высокий, поток может запросить большую пропускную

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

Управление доступом Гарантии пропускной способности и задержки для потока будут выполнены,

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

Гарантии пропускной способности и задержки для потока будут выполнены, даже

если другие потоки будут копить трафик и отправлять его одновременно.
Слайд 318

Управление доступом Результат не зависит от количества маршрутизаторов в узлах пути

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

Результат не зависит от количества маршрутизаторов в узлах пути и

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

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

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

В наихудшем случае, если крупный объем трафика поступит на первый

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

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

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

Технология предназначена как для одноадресных и для многоадресных приложений.
Примером

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

Интегральное обслуживание Данной услугой может пользоваться большое число абонентов, расположенных в

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

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

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

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

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

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

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

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

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

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

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

RSVP — протокол резервирования ресурсов Главная составляющая архитектуры интегрального обслуживания, открытая

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

Главная составляющая архитектуры интегрального обслуживания, открытая для

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

RSVP — протокол резервирования ресурсов RSVP позволяет нескольким отправителям посылать данные

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

RSVP позволяет нескольким отправителям посылать данные нескольким

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

RSVP — протокол резервирования ресурсов Простейшая форма этого протокола использует многоадресную

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

Простейшая форма этого протокола использует многоадресную маршрутизацию

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

RSVP — протокол резервирования ресурсов Затем стандартный алгоритм многоадресной маршрутизации строит

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

Затем стандартный алгоритм многоадресной маршрутизации строит связующее

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

RSVP — протокол резервирования ресурсов Единственное отличие от обычной многоадресной маршрутизации

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

Единственное отличие от обычной многоадресной маршрутизации состоит

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

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

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

Слайд 330

RSVP — протокол резервирования ресурсов Для улучшения качества приема и устранения

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

Для улучшения качества приема и устранения перегрузки

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

RSVP — протокол резервирования ресурсов На каждом транзитном участке маршрутизатор замечает

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

На каждом транзитном участке маршрутизатор замечает запрос

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

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

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

Слайд 333

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

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

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

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

Дифференцированное обслуживание В системах с тысячами или миллионами потоков интегральное обслуживание

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

В системах с тысячами или миллионами потоков интегральное обслуживание применить

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

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

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

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

связаны со сложными процессами обмена между маршрутизаторами при установке потоков.
Слайд 336

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

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

По этим причинам был создан упрощенный подход к повышению качества

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

Дифференцированное обслуживание Подход известен как ориентированное на классы (в отличие от

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

Подход известен как ориентированное на классы (в отличие от ориентированного

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

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

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

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

интернет-провайдер или телефонную компанию).
Администрация определяет множество классов обслуживания и соответствующие правила маршрутизации.
Слайд 339

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

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

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

информацией о классе.
Эти сведения записываются в поле Дифференцированное обслуживание пакетов IPv4 и IPv6.
Слайд 340

Дифференцированное обслуживание Классы определяют пошаговое поведение (per hop behaviors), так как

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

Классы определяют пошаговое поведение (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).
- Предыдущая
Предметно-проблемное поле педагогики
Следующая -
Образы защитников отечества в различных жанрах музыки

Похожие презентации

Научно-техническая революция
Туманные вычисления и интернет вещей. (Лекция 4)
Подходы к системе авторских прав. Стимулы к формированию системы открытого доступа. Примеры реализации идеи открытого доступа
Интерфейс систем управления складом
Информатика. Введение. Предмет и задачи
Устройство компьютера
Операционные среды, системы и оболочки. Операционные системы
Формирование отчетов в конфигурациях 1С:Предприятие с помощью системы компановки данных
Выполнение геометрических построений в системе компьютерного черчения КОМПАС. Геометрическое построение угла, равного заданному
Аттестационная работа. Образовательная программа Информатика плюс химия равно проект
Введение в язык разметки HTML
Базы данных - 4
Розробка бази даних фермерського господарства
Збереження і видобування даних
Анализ функциональной и информационной архитектуры ИС на соответствие модели объекта автоматизации
Презентация "MSC.Dytran - 01" - скачать презентации по Информатике
Совершенная дизъюнктивная нормальная форма
Виды профессиональной информационной деятельности человека с использованием технических средств и информационных ресурсов
Исследование методов решения задач представления чисел с помощью систем счисления
Мобильное приложение для отелей
Архитектура веб-студии и ее связь со специализацией Архитектура веб-студии и ее связь со специализацией Константин Ткаченко
Продвижение молодежной страницы в социальных сетях
Робота з кластером ІФКС
Направления информационной защиты. (Глава 2)
Kinder-Inter.net. Обзор образовательных сайтов для детей и их родителей
Управление и кибернетика (Информатика 9 класс)
Microsoft PowerPoint
Дагестанский государственный педагогический университет Математический факультет Кафедра преподавания математики и информатик
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть