Коммутация каналов. Процедура установления соединения

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

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

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

· Для распознания таких ситуаций обмен данными в сети с коммутацией каналов предваряется процедурой установления соединения.

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

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

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

· Когда запрос проходит до конечного узла, имеется полная информация о возможности установления соединения.

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

· Возможен и отказ в установлении соединения.

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

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

2.Сетевой уровень. Входное дерево. Алгоритм Дейкстры (Л 6/14-16).

Можно рассмотреть множество оптимальных маршрутов в виде дерева, называемого входным деревом.

Входное дерево (а – вся сеть, b – входное дерево для роутера B):

Концепция кратчайшего пути:

§ Строим граф подсети: узлы – вершины, линии связи – дуги.

§ Вводим веса на дуги (можно брать одинаковые, можно учитывать длину линий и т.д.).

§ Можно учесть среднюю длину очереди, время задержки пересылки, и т.д.

§ При выборе маршрута между двумя маршрутизаторами находим кротчайший путь между ними в графе.

§ Существуют разные алгоритмы поиска кратчайшего пути.

Алгоритм Дейкстры

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

РИС 5.6

Выбор кратчайшего пути. (пояснение картинки) Начнем наше изучение алгоритмов выбора маршрутов с метода, широко приме­няемого в различных формах благодаря его простоте и понятности. Идея заклю­чается в построении графа подсети, в котором каждый узел будет соответство­вать маршрутизатору, а каждая дуга - линии связи (часто называемой просто связью). При выборе маршрута между двумя маршрутизаторами алгоритм про­сто находит кратчайший путь между ними на графе. Концепция кратчайшего пути требует некоторого пояснения. Один из спосо­бов измерения длины пути состоит в подсчете количества транзитных участков. В таком случае путь ABC и ABE на рис.5.6 имеют одинаковую длину. Можно из­мерять расстояния в километрах. В таком случае окажется, что путь ABC значительно длиннее пути ABE (предполагается, что рисунок изображен с соблюдени­ем масштаба). Однако помимо учета количества транзитных участков и физической длины линий возможен учет и других параметров. Например, каждой дуге графа можно поставить в соответствие среднюю длину очереди и время задержки пересылки, определяемые каждый час с помощью передачи специального тестового пакета. В таком графе кратчайший путь определяется как самый быстрый путь, а не путь с самой короткой длиной кабеля или путь, состоящий из минимального числа отдельных отрезков кабеля.

В общем случае параметры дуг графа являются функциями расстояния, про­пускной способности, средней загруженности, стоимости связи средней длины очереди, измеренной величины задержки и других факторов. Изменяя весовую функцию, алгоритм может вычислять кратчайший путь с учетом любого количе­ства критериев в различных комбинациях. Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году. Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, показывая оптимальные пути. Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориентировочными. Когда выясняется, что отметка действительно соответствует крат­чайшему возможному пути, она становится постоянной и в дальнейшем не изме­няется. Чтобы показать, как работает этот алгоритм, рассмотрим взвешенный нена­правленный граф (рис. 5.6, а), где весовые коэффициенты соответствуют, напри­мер, расстояниям. Мы хотим найти кратчайший путь от А к D. Для начала мы черным кружком помечаем узел А как постоянный. Затем мы исследуем все со­седние с ним узлы, указывая около них расстояние до узла А. Если отыскивается более короткий путь к какому-либо узлу, то вместе с указанием расстояния в от­метке меняется и узел, через который прошел более короткий путь. Таким обра­зом, позднее можно восстановить весь путь. Рассмотрев все соседние с А узлы, мы помечаем ближайший узел как постоянный, как показано на рис. 5.6, б. Этот узел становится новым рабочим узлом. Теперь мы повторяем ту же процедуру с узлом В, исследуя все его соседние узлы. Если сумма расстояния от узла В и значения отметки в узле В (расстояния от А до В) оказывается меньше, чем отметка у исследуемого узла (уже найденное другим путем расстояние от А), это значит, что найден более короткий путь, по­этому пометка узла изменяется. После того как все соседние с рабочим узлы исследованы и временные отмет­ки при необходимости изменены, по всему графу ищется узел с наименьшей вре­менной отметкой. Этот узел помечается как постоянный и становится текущим рабочим узлом. На рис. 5.6 показаны первые пять этапов работы алгоритма. Чтобы понять, как работает алгоритм, посмотрим на рис. 5.6, в. На данном этапе узел Е только что был отмечен как постоянный. По такому же принципу следуем дальше.

Дата добавления: 2015-08-09