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

Рис. 12. Сравнение методов  коммутации сообщений, коммутации

пакетов и статистического уплотнения

Однако кроме мультиплексоров  каждый узел сети коммутации пакетов  должен иметь достаточный объем  памяти для накопления целого пакета, проверки наличия в нем ошибок, его обработки и повторной  передачи. Строго говоря, статистический мультиплексор не накапливает целое сообщение или пакет. Он коммутирует поступающие данные по мере того, как они принимаются. Функции защиты от ошибок (контроль с помощью избыточных кодов и запросы повторной передачи) реализуются между оконечными точками «соединения», а не между узлами. В целом основой АГВР и СТУВР является мультиплексор (демультиплексор). Узел коммутации пакетов выполняет функции, подобные функциям мультиплексора и, кроме того, также функции контроля на уровне сообщений и на уровне сети. (13)

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

- динамическая маршрутизация;

- маршрутизация по виртуальным каналам;

- маршрутизация по фиксированному пути.

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

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

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

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

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

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

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

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

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

Режим передачи пакетов между двумя конечными узлами сети предполагает независимую маршрутизацию каждого пакета. Такой режим работы сети называется датаграммным, и при его использовании коммутатор может изменить маршрут какого-либо пакета в зависимости от состояния сети - работоспособности каналов и других коммутаторов, длины очередей пакетов в соседних коммутаторах и т. п. Существует и другой режим работы сети - передача пакетов по виртуальному каналу (virtual circuit или virtual channel). В этом случае перед тем, как начать передачу данных между двумя конечными узлами, должен быть установлен виртуальный канал, который представляет собой единственный маршрут, соединяющий эти конечные узлы. Виртуальный канал может быть динамическим или постоянным. Динамический виртуальный канал устанавливается при передаче в сеть специального пакета - запроса на установление соединения. Этот пакет проходит через коммутаторы и «прокладывает» виртуальный канал. Это означает, что коммутаторы запоминают маршрут для данного соединения и при поступлении последующих пакетов данного соединения отправляют их всегда по проложенному маршруту. Постоянные виртуальные каналы создаются администраторами сети путем ручной настройки коммутаторов. При отказе коммутатора или канала на пути виртуального канала соединение разрывается, и виртуальный канал нужно прокладывать заново. При этом он, естественно, обойдет отказавшие участки сети. Каждый режим передачи пакетов имеет свои преимущества и недостатки. Датаграммный метод не требует предварительного установления соединения и поэтому работает без задержки перед передачей данных. Это особенно выгодно для передачи небольшого объема данных, когда время установления соединения может быть соизмеримым со временем передачи данных. Кроме того, датаграммный метод быстрее адаптируется к изменениям в сети. При использовании метода виртуальных каналов время, затраченное на установление виртуального канала, компенсируется последующей быстрой передачей всего потока пакетов. Коммутаторы распознают принадлежность пакета к виртуальному каналу по специальной метке - номеру виртуального канала, а не анализируют адреса конечных узлов, как это делается при датаграммном методе. (18)

Одним из главных преимуществ  работы сети с использованием виртуальных  каналов является возможность обеспечить более упорядоченное управление доставкой пакетов. Если узел, входящий в виртуальный канал, никогда не передает пакет, относящийся к определенному «соединению», до тех пор пока не будет подтверждена правильность приема предыдущего пакета, то последовательность поступления пакетов не нарушается. Второе преимущество виртуального канала — это пониженные требования к адресации отдельных пакетов. После установления виртуального канала отпадает необходимость в полных адресах пунктов назначения, указываемых в пакетах. Вместо адресов пунктов назначения могут использоваться местные идентификаторы виртуального канала каждой линии. По существу, идентификаторы виртуального канала являются указателями адресов памяти процессоров коммутации на узлах коммутации пакетов. Эти адреса памяти содержат соответствующую информацию относительно фактического источника, пункта назначения и маршрутизации пакетов. Другая важная особенность режима работы с виртуальными каналами — это присущая ему способность содействовать управлению потоками, что будет обсуждено в следующем разделе. Основным недостатком работы с виртуальными каналами является возможность увеличения задержек при передаче сообщений. При установлении соединительного пути для виртуального канала он выбирается так, чтобы минимизировать задержку пакетов в сети с учетом нагрузки на сети в данный момент. Если нагрузка меняется, то пакеты, относящиеся к определенному виртуальному каналу, могут испытывать длительную задержку из-за пребывания в очередях на некоторых линиях, хотя в это же время другие линии могут быть загружены в меньшей степени. В работе сообщается, что анализ методов маршрутизации, проведенный для нескольких конфигураций небольших сетей, указывает на возможность сократить задержку пакета на 10 ... 27%, если вместо фиксированной маршрутизации применить адаптивную. Могло бы показаться, что сама процедура установления соединения является недостатком сети с виртуальными каналами. Однако фактически для управления потоком необходимо осуществлять обмен сообщениями типа запрос — ответ для определения состояния узла назначения до того, как источнику будет разрешено начать передачу потока пакетов. Таким образом, накладные расходы на управление и задержка, обусловленная установлением «соединения», являются обычно необходимыми требованиями даже в сетях с динамической маршрутизацией. (15)

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

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

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

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

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