4.6.1.3.Сеть с пакетной коммутацией

Коммутация пакетов является развитием метода коммутации сообщений. Она позволяет добиться дальнейшего увеличения пропускной способности сети, скорости и надежности передачи данных. В сети с коммутацией пакетов сообщения разделяются на отдельные части, называемые пакетами (см. рисунок 4.39). Каждый пакет имеет, как правило, фиксированную длину и снабжается заголовком, указывающим адрес пункта отправления, адрес пункта назначения и номер пакета в сообщении. Максимальная длина пакета лежит в пределах от 10⁴ до 2*10⁴ бит. Разложение сообщения на пакеты и восстановление его после передачи осуществляются оконечным оборудованием источника и адресата.

Рисунок 4.40-Пакетирование сообщений

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

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

Рисунок 4.41-Различные пути передачи пакетов

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

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

42. Управление потоком в сети и модель скользящего окна

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

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

Для предотвращения возникновения тупиковых ситуаций существуют специальные методы. Наиболее распространенным является метод скользящего окна [14].

4.6.2.1.Метод скользящего окна

Окно – это неподтвержденные пакеты, находящиеся в виртуальном канале.

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

Рисунок 4.42-Модель массового обслуживания для виртуального канала

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

Рисунок 4.43-Управление с помощью скользящего окна: (а) начальное состояние, (б) пакет 1 подтвержден, (в) следующий пакет (2) подтвержден

Разомкнутая сеть может быть отнесена к составным системам массового обслуживания. Она имеет показатели, определенные в форме произведения (то есть вероятности состояний всей сети выражаются произведениями вероятностей состояний каждой системы обслуживания). Наложим на эту модель скользящее окно (рисунок 4.44).

Рисунок 4.44-Модель управления с помощью скользящего окна

В данном случае – частный случай замкнутой сети массового обслуживания. Здесь источник и получатель связаны дополнительной искусственной системой обслуживания, обозначаемой М+1, интенсивность обслуживания которой равна , что соответствует интенсивности входящего потока в ВК. По замкнутой системе циркулирует фиксированное число N пакетов. Отметим теперь, как эта модель замкнутой системы охватывает механизм скользящего окна. Если в ВК (верхние М систем обслуживания) находятся N пакетов, нижняя система обслуживания М+1 пуста и обслуживать не может. Это моделирует состояние блокировки, которое пакеты встречают при поступлении в момент исчерпанного окна. В момент, когда один из N пакетов в ВК поступает к получателю, он появляется в системе обслуживания М+1 и источник теперь может доставить пакеты с пуассоновской интенсивностью . Это имеет место всегда, если в ВК находится менее N пакетов; тогда остальные накапливаются в искусственной системе обслуживания М+1.

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

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

На рисунке 4.45 показана замкнутая сеть массового обслуживания с одной системой обслуживания СО, вынесенной за ее пределы. Предположим, что требуется найти вероятности состояний только этой системы. Теорема Нортона устанавливает, что если сеть массового обслуживания имеет решение в форме произведения, то отдельная зависящая от состояния система массового обслуживания, входящая в эту сеть, может быть выделена путем короткого замыкания точек А и В, как показано на рисунке 4.45б, позволяя n пакетам циркулировать по вновь образованной замкнутой сети. Значительно более простой эквивалентной моделью для решения этой задачи является модель, показанная на рисунке 4.45в. В ней эквивалентная система обслуживания Нортона с интенсивностью обслуживания u(n), где n – состояние СО, заменяет всю сеть между точками А и В на рисунке 4.45а.

а) б)

в)

Рисунок 4.45-Применение теоремы Нортона к сетям массового обслуживания: (а) исходная сеть, (б) применение теоремы Нортона, (в) эквивалентная модель

Пусть теперь общее количество пакетов равно N. Если верхняя система обслуживания находится в состоянии n, то нижняя система будет в состоянии N-n. Вероятность p_n того, что верхняя система находится в состоянии n равна

(4.15)

где р₀ находится из обычного нормирующего условия для вероятностей

(4.16)

Эквивалентная замена для рассматриваемой сети приводит к зависящей от состояния характеристике обслуживания

. (4.17)

Производительность u(n) в случае, когда среди М показанных СО распределены n пакетов, всегда меньше или равна . Она должна удовлетворять условию

{система непуста}. (4.18)

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

. (4.19)

На основании формулы Литтла задержка Е(Т) ВК из конца в конец равна отношению среднего числа пакетов в ВК к :

. (4.20)

Чтобы увидеть, как хорошо работает управление с помощью окна и определить значение N, предлагаемое для соответствующей характеристики управления, рассмотрим область очень большой нагрузки. Предположим, что . Тогда очевидно, что как только пакет поступит к получателю и к источнику вернется подтверждение, в ВК немедленно вводится другой пакет. Таким образом, в этом предельном случае ВК всегда находится в состоянии N, E(n)=N и производительность равна

, . (4.21)

На основании формулы Литтла непосредственно получим

, . (4.22)

Из этого равенства видно, что минимальная задержка имеет место при N=1. Это соответствует ожиданию. При увеличении размера окна N задержка растет пропорционально, а производительность сначала линейно растет с N, но затем выравнивается, приближаясь к максимальному значению все более и более медленно с ростом N. Объединив равенства (4.21) и (4.22), получим простое выражение для характеристики обмена между задержкой и производительностью

, . (4.23)

Равенство справедливо только для целых значений N.

Какое значение N должно применяться? Из (4.21) и (4.22) видно, что оптимальное N = M-1. Увеличение N за пределы этой точки приводит к устойчивому росту задержки.

43. Выбор кратчайших путей (маршрутизация) в сетях