INTUIT.ru::Интернет-Университет Информационных Технологий

Управление трафиком предназначено для обеспечения качества обслуживания доставки информации конечному потребителю и эффективным использованием ресурсов сети. Управление трафиком можно классифицировать по трем уровням:

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

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

Обработка пакета вдоль пути - это накопление и обработка очереди от

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

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

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

Вероятность потери пакета из конца в конец - это вероятность потери пакета по всему пути. Она ограничена суммой вероятностей потери в каждой системе.

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

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

Дисциплина обслуживания "в порядке поступления" и приоритетные очереди

Самый простой подход к планированию очереди - дисциплина FIFO (first in first out) в порядке поступления ("первым пришел, первым вышел"), где пакеты передаются в порядке их поступления, как показано на рис. 7.2. Пакеты отклоняются, когда буфер полностью занят. Задержка и потеря пребывающих пакетов такого типа очереди зависят от интервала времени между двумя поступлениями соседних пакетов, а также от их длины. Когда интервалы между поступлениями пакетов становятся слишком малыми или длина пакета значительно увеличивается, пакеты будут иметь тенденцию к созданию и очереди тогда будут расти, ухудшая характеристики сети. Поскольку при дисциплине обслуживания в порядке поступления в очередь все пакеты обрабатываются без приоритетов, невозможно обеспечить различные информационные потоки отличающимися требованиями к качеству обслуживания. При такой дисциплине обслуживания возникает напряженная ситуация (hogging), когда пользователь, передающий пакеты на высокой скорости, заполняет буферы в системе, лишая других пользователей, работающих с меньшей интенсивностью, доступа к буферу.

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

Использование заголовка для определения приоритета очереди

Использование заголовка для определения приоритета очереди - второй метод, который определяет классы обслуживания. Отдельные буферы обслуживают различные классы обслуживания, имеющие различный приоритет (отметку коэффициента потери ячеек - CLP). Как показано на рис. 7.3, в каждый момент времени оборудование линии передачи, получая следующий пакет для передачи, выбирает пакет в зависимости от состояния очереди с высоким приоритетом. Например, пакет, который требует малого времени задержки, устанавливается в очередь, имеющую высокий приоритет (

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

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

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

Сортировка пакетов

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

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

Равнодоступная дисциплина

Равнодоступная дисциплина очереди пытается обеспечить равноправный доступ к пропускной способности канала. В компьютерной технике такая дисциплина называется дисциплиной, формируемой процессором (processor sharing discipline). Каждый пользовательский поток имеет свой собственный логический буфер. В идеальной системе пропускная способность передачи, скажем, C бит/с, разделена одинаково среди буферов. Содержание каждого буфера может тогда рассматриваться как жидкость, которая непрерывно вытекает. Такая ассоциация позволит в дальнейшем построить удобную модель. Размер буфера для каждого пользовательского потока может быть выбран так, чтобы выполнить заданные требования по вероятности потерь - ячейки или пакеты данного пользователя должны отклоняться, когда буфер полон.

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

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

, то каждый поток гарантируется не менее чем

бит/с.

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

бит/с.

Практически деление пропускной способности "поровну" невозможно. Как показано на рис. 7.5, один из подходов состоит в циклическом опросе каждого непустого буфера (round robin polling) и передаче по одному биту. Однако декомпозиция результирующего потока бит в составляющие пакеты требовала бы введения цикловой синхронизации и сложной обработки при выводе. В случае ATM равнодоступной организации очереди можно добиться относительно простым способом. Поскольку в ATM все пакеты имеют одну и ту же длину, система может обслуживать циклически непустые буфера по одному пакету. Пользовательским потокам тогда гарантирован равный доступ к ресурсам передачи.

Следует обратить внимание, что при опросе имеются как минимум две стратегии считывания: по битам и по пакетам. Каждая из них оказывает различное влияние на времена ожидания. Разновидностью такой очереди является взвешенная равнодоступная очередь (Weighted Fair Queuing - WFQ). Она используется в том случае, когда имеются пользователи с различными требованиями. Как и в предыдущем случае, для потока каждого пользователя выделяется свой буфер, но каждый буфер имеет вес, который определяет долю участия в разделении производительности линии. Если, например, буфер 1 имеет вес 1, а буфер 2 имеет вес 3, то когда оба буфера не пусты, буфер 2 будет сканироваться в 3 раза чаще, чем буфер 1. При этом говорят, что буфер 1 получает 1/4 производительности линии, а буфер 2 - 3/4 производительности.

Еще одна разновидность равнодоступной очереди - случайное ранее обнаружение (Random Early Detection - RED). В этой системе происходит опрос буферов по случайному закону. При этом производится анализ заполнения буфера, и при угрозе переполнения проводится сброс пакетов.

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

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

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

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

Этот процесс иллюстрирует рис. 7.7 (кривая, относящаяся к неуправляемому процессу). Цель управления трафиком на уровне потока состоит в том, чтобы управлять индивидуальными потоками и поддерживать работу (управляемая кривая) при наличии перегрузки. Поэтому этот процесс можно назвать управлением перегрузками.

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

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

управление с явными потерями (open-loop control) и управление с повторной передачей (closed loop control). Управление с явными потерями препятствует возникновению перегрузки, контролируя, что трафик, сгенерированный источником, не ухудшит характеристики до уровня ниже заданного качества обслуживания.

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

Управление с явными потерями

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

Для сохранения характеристик сети класс управления с явными потерями использует три механизма:

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

Управление доступом было первоначально разработано для сетей пакетной коммутации с виртуальными каналами, таких как ATM, но потом было распространено для дейтаграммных сетей. Управление доступом в ATM работает на уровне соединений, поэтому оно было названо управлением доступом к соединению (Call Admission Control - CAC). Управление доступом в дейтаграммной сети имеет смысл, только если пакеты данного потока следуют одним и тем же путем.

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

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

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

Стратегия безопасности

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

Большинство устройств, осуществляющих охрану, используют принцип "дырявого ведра". Представим себе, что трафик, поступающий на устройство охраны, - это вода, наполняющая ведро, которое имеет на дне дырку. Ведро имеет глубину и протекает с постоянной скоростью, пока ведро не пусто. Новая порция воды (пакетов) будет конформна, если ведро не переполнится. Если ведро наполнено, новая порция воды неконформна и вода должна быть удалена (или отлита в другое ведро после осуществления маркирования). Размер дырки связан со скоростью осушения ведра. Дырка гарантирует, что ведро не переполнится, пока скорость осушения выше, чем скорость наполнения водой. Глубина ведра поглощает колебания потока воды. Если скорость наполнения ведра постоянна и примерно равна скорости вытекания, то глубина ведра может быть очень малой. Рассмотрим один из алгоритмов дырявого ведра, определенный Форумом ATM. В нем пакет предполагается постоянной длины (например, ячейка ATM). Запишем в счетчик содержимое дырявого ведра. Когда поступает пакет, содержимое (счетчика) увеличивается на одну и ту же величину

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

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

устанавливается на нуль и последнее время поступления пакета (Last Conforming Time - LST) устанавливается на время поступления первого пакета. Глубина ведра -

, где

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

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

единиц. Таким образом, остающаяся емкость ведра равна

, где

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

. Если ведро не пусто, то проверяется, не переполнено ли оно

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

Пример работы алгоритма дырявого ведра продемонстрирован на рис. 7.9, где показан пример графика.

Данные для диаграммы приведены в таблице 7.1.

В этом примере величина шага наполнения ведра

, глубина

, скорость вытекания

пакет в один момент времени.

Поступление первой части пакетов увеличивает содержание ведра до 4. К моменту второго поступления содержимое уменьшается до 3. Дополнение его содержимого увеличивает его до семи. К моменту прибытия следующей порции пакетов (через 3 момента времени) содержимое ведра уменьшается до 4 и при поступлении пакетов увеличивается до 8. Далее это значение уменьшается до 5 и увеличивается до 9. Следующая

Таблица 7.1. Пример диаграммы дырявого ведра
содержимое ведра до поступления пакетов	содержимое ведра после поступления пакетов	Интервал между поступлениями пакетов	содержимое ведра к моменту следующего поступления	Примечание
0	4	1	3
3	7	3	4
4	8	3	5
5	9	2	7
7	11			Пакет не принят
	9	7	2
2	6	7	0	Размерность меньше нуля
0	4	1	3
3	7	1	6
6	10			Пакет не принят
	10	5	5
5	9			Далее процесс продолжается

порция поступает через 2 момента времени и содержимое ведра будет равно 7, и если добавить 4 пакета, то это значение 11 превысит глубину ведра. Поэтому ведро не наполняется и продолжает опустошаться. Следующая порция пакетов поступает через 7 интервалов после последнего поступления конформной (принятой) порции пакетов. К этому моменту величина содержимого равна 2, а после добавления она становится равна 6.

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

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

Если

- количество пакетов, поступающих в один момент времени, а

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

пакетов (предполагаем, что в один интервал времени убывает один пакет). Число шагов, через которое накопится

пакетов (заполнится пространство

, равно

С учетом первого шага разрешенное накопление пакетов не приводящее к потерям MBS (максимальный размер пачки - maximum burst size) определяется выражением ( рис. 7.10).

После того как будет накоплено

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

Величину, обратную

, часто называют поддерживаемой скоростью (Sustainable Rate).

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

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

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

Формирование трафика может быть реализовано многими методами. Формирование трафика с использованием принципа дырявого ведра - очень простое устройство. Оно показано на рис. 7.13.

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

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

Более реалистичный формирователь, называемый формирователем допустимого трафика по принципу ведра (token bucket traffic shaper), регулирует только неконформные пакеты. Пакеты, которые определены как конформные, пропускаются без задержки. На рис. 7.13 показано допустимое ведро, полученное расширением дырявого ведра. Метки генерируются периодически с постоянной скоростью и накапливаются в ведре меток. Если ведро меток полное, прибывающие метки отклоняются. Пакет от буфера может быть выведен, если в буфере меток есть метка. Если буфер меток пуст, прибывающие пакеты ждут в пакетном буфере. Поэтому можно представить себе, что метка - это разрешение на передачу.

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

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

Гарантии качества обслуживания и расписание обслуживания

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

Пусть

- размер буфера в байтах и пусть

- скорость меток, выраженная в байт/c. Тогда период за период

- максимальный трафик, проходящий через формирователь, может быть

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

байт/c - линейная скорость при условии, что

На рис. 7.14 а показано расположение буферов очередей, а на рис. 7.14б - занятость буфера как функция времени. Предположим, что буфер меток позволяет принять всплеск

байт, и эти байты будут накоплены к моменту

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

байт/с, и передача проходит на скорости мультиплексора

байт/с. Тогда занятость буфера будет уменьшаться согласно формуле

байт/с. Важно заметить, что занятие буфера всегда меньше

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

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

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

в секунду.

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

Этот результат при ограничении $r \leq R$ обеспечивает условие для установления соединения по сети пакетной коммутации, при котором гарантирована доставка пакета за определенное время.

Управление с обратной связью

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

Управление перегрузкой обычно применяет механизм управления с обратной связью (управление по замкнутому шлейфу - closed loop control). Этот механизм опирается на получение информации по обратной связи, чтобы регулировать скорость передачи потока пакетов. Основой для принятия решений служит информация обратной связи о состоянии сети. Это может быть информация о заполнении буферов, использовании линии связи или другая существенная информация о перегрузке. Получатель информации обратной связи обычно зависит от уровня связи, который занимается управлением перегрузкой. В системе TCP/IP управление реализовано на транспортном уровне, и таким образом получатель информации обратной связи обычно постоянно находится в источнике. В системе ATM управление реализовано в уровне ATM, соответствующем сетевому уровню, и таким образом получатель информации обратной связи может постоянно находиться в промежуточном узле.

Имеются два типа управления по обратной связи: из конца в конец и по участкам.

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

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

Управление по участкам обычно может реагировать намного быстрее, чем управление из конца в конец, из-за более короткой задержки распространения. При управлении с обратной связью по участкам состояние сети распространяется в направлении к расположенному выше по направлению потока узлу, как показано на рис. 7.15б. Когда узел обнаруживает перегрузку на исходящей линии связи, он может сообщить эту информацию расположенному выше по потоку соседу и замедлить скорость передачи этого узла. В результате расположенный выше по потоку узел может также испытать перегрузку. Тогда он может передать своему расположенному выше по потоку соседу сигнал уменьшить скорость. Этот процесс "обратного давления" (backpressure) от одного нижестоящего узла до другого вышестоящего узла может продолжиться до тех пор, пока этот сигнал не попадет к источнику.

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

Управление с обратной связью в ATM-сетях - это один из примеров, когда источник постоянно корректирует свою скорость передачи согласно явной информации обратной связи, которая записывается в один бит. Этот бит называется "явный указатель перегрузки" (Explicit Congestion Indication - EFCI) и устанавливается в заголовке ячейки ATM в идентификаторе полезной нагрузки (см. таблицу 5.1). Когда узел обнаруживает угрозу перегрузки, он устанавливает бит EFCI в ячейке данных, передаваемых по загруженной линии в направлении пункта назначения. Пункт назначения, получив такие ячейки, посылает специальное сообщение для указания источнику, что обнаружена перегрузка. Источник должен регулировать свою скорость передачи.

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

Управление перегрузкой в TCP - один из примеров, который регулирует скорость передачи, используя неявную обратную связь, устанавливает отсутствие подтверждения, включая тайм-аут для повторной передачи. Когда в источнике сработает тайм-аут, он уменьшает скорость передачи, уменьшая "окно передачи". Затем источник ступенчато увеличивает скорость передачи, пока снова не будет обнаружена перегрузка, и потом повторяется весь цикл. Управление перегрузкой будет обсуждаться при рассмотрении протоколов TCP.

Управление трафиком на уровне объединенных потоков

На уровне объединенных потоков управление трафиком имеет дело с разнообразными потоками. Этот уровень работает в течение относительно долгого времени - от нескольких минут до нескольких дней. Управление трафиком на уровне объединенных потоков часто называют проектированием трафика (traffic engineering). Главная цель проектирования трафика: распределить объединенные потоки по сети так, чтобы эффективно использовать ее ресурсы. При маршрутизации выбор самого короткого пути позволяет доставлять трафик наиболее быстро к пункту назначения. Как показано на рис. 7.16, концепция выбора самого короткого пути, к сожалению, не может привести к эффективной передаче потоков.

В этом примере возникают требования передачи трафика между источниками 1, 2 и 3 к пункту назначения 8. При использовании маршрутизации по принципу самого короткого пути линия связи, соединяющая узлы 4 и 8, имеет высокую нагрузку, в то время как другие линии связи загружены мало. рис. 7.16б показывает пример лучшего распределения трафика, где он распределен по сети так, чтобы потоки, создающие опасность перегрузки на критическом направлении между узлом 4 и узлом 8, были удалены.

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

Предположим, что заявка на передачу трафика требует пропускной способности B между данным источником и пунктом назначения. Сначала алгоритм сокращает любую линию связи сети, которая имеет пропускную способность меньше, чем B. Затем алгоритм выполняет самую короткую маршрутизацию по принципу выбора самого короткого пути между данным источником и пунктом назначения. Рассмотрим пример, показанный на рис. 7.16. Предположим, что надо установить три пути: узел 1 к узлу 8 (путь 1), узел 2 к узлу 8 (путь 2), и узел 3 к узлу 8 (путь 3). Предположим, что пропускная способность, которая требуется для каждого пути, - B, и каждая линия связи имеет пропускную способность B. Первоначально самый короткий путь 1 может быть выбран по маршруту 1-4-8. Выбор этого маршрута исключает из поиска линии 1-4 и 4-8. Следующий путь 2 выбирает наикратчайший путь 2-4-5-8 в уже усеченной топологии. Теперь из поиска исключаются линии 2-4, 4-5 и 5-8. Путь 3 использует снова усеченную топологию и выбирает наикратчайший путь 3-6-7-8.

Маршрутизация по самому короткому пути не всегда приводит к желательному результату. Рассмотрим теперь случай, где пути устанавливаются в соответствии со следующей заявкой: путь 2, путь 1 и путь 3.

Читатель может проверить, что путь 2 выберет маршрут 2-4-8, а путь 1 выберет маршрут 1-4-6-7-8. В этом случае путь 3 не может быть успешно установлен. Этот пример показывает, что последовательность выбора пути играет при маршрутизации по принципу самого короткого пути важную роль в возможном размещении пути. Оптимальное размещение пути должно было бы рассмотреть все возможные заявки на имеющиеся пути, поступившие в одно и то же время, так, чтобы оптимизация могла быть сделана глобально.