Моделирование объекта системы и сети электросвязи

 

Σ p ^{( i )} ( k,j ) = 1 
 

Представление с помощью таблиц пригодно и для  адаптивных стратегий. 

Для анализа  вводится также понятие вектора потока в линиях:

f = f ₁, f ₂…..f _b, 
 

где b – общее число ориентированных линий в сети;

f _i – усредненный поток данных, бит\с, передаваемый по линии i с учетом всех пакетов.

f – является многопродуктовым МП потоком для конкретной матрицы потоков. 

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

Т = (1/γ) * Σ f _i \ ( C _i – f _i )

  Т – суммарная средняя задержка пакета, с\пак;

γ = Σ Σ r _{i, j} – cуммарная интенсивность вх.потока пакетов, пак\с;

N – число узлов; b – число направленных линий;

r _{i, j} – cредняя интенсивность пакетов, следующих из источника i к адресату j, пак\с;

f _i –суммарный поток в канале, бит\с;

С _i – пропускная способность канала, бит\с; 

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

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

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

 
 
 
 
 
 

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

 
 

  
 
 
 
 

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

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

Основные графовые обозначения:

• граф G = ( N,А )  – конечное непустое множество узлов N и некоторый набор А пар различных узлов из N;
• каждая пара узлов в А называется дугой ( ориентированной );

 
 
 
 
 
 
 

Несколько примеров: 

             2                                            2

1                                                                                                  1

                          3                1                   3 
 

       4 

N = {1,2,3,4}                             N = {1,2,3}                                    N = {1}

A = {(1,2),(2,3),(4,1),(2,4)}      A = {(1,2)}                                     A = { } 

Узлы называются вершинами, дуги – ребрами, ветвями, звеньями или линиями. Если n ₁ и n ₂ являются узлами графа, а ( n ₁, n ₂ ) – дугой, то эта дуга инцидентна n ₁ и n ₂;

• переходом ( или маршрутом ) по графу G называется последовательность узлов (n ₁, n ₂,….n _i ), таких, что все пары ( n ₁, n ₂), (n ₂, n ₃ )…….( n _{i – 1}, n _i ) являются дугами графа G.
• переход, в котором нет повторяющихся узлов, называется путем.
• переход ( n₁ …..n _i ), в котором n ₁ = n _i , i > 3 и нет повторяющихся узлов, кроме n ₁ = n  _i называется циклом ( на рис. для 1-ого примера: последовательности (1,4,2,3), (1,4,2.1), (1,4,2,1,4,1), (2,3,2) и (2) являются переходами; каждая из последовательностей (1,4,2,3) и (2) является путем, а (1,4,2,1) – циклом ).
• граф связный, если для каждого узла i существует путь ( i = n ₁…..n _l = j ) к любому другому узлу j.
• деревом называется связный граф, не имеющий циклов;
• остовным деревом графа G называется подграф графа G, который является деревом и содержит все узлы графа G;
• ориентированный граф ( диграф) G = ( N,A ) – это конечное непустое множество узлов N и набор А упорядоченных пар различных узлов из N( каждая упорядоченная пара узлов – это ориентированная дуга );
• ориентированный путь – это ориентированный переход с неповторяющимися узлами, а ориентированный цикл – это ориентированный переход ( n ₁…..n _l ) c неповторяющимися узлами, такой, что n ₁ = n _l и l › 2.
• длина любого ориентированного пути p = ( i, j,k….l,m ) определяется как d _{i j} + d _{i k} +….+ d _{l m} ( d – длина дуги ).

НАХОЖДЕНИЕ  КРАТЧАЙШЕГО ПУТИ

 

Существуют три  стандартных алгоритма решения задачи отыскания кратчайшего пути – алгоритм Беллмана – Форда, алгоритм Дейкстра и алгоритм Флойда – Уоршела.

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

Алгоритм  Беллмана – Форда 

 

                                                           Задача нах.  кратч. пути; длины дуг указаны

Узел-ист

 
 

                        D ^{( 1)}₂ = 1           D ^{( 1)}₄ = ∞

                                                            Кратч. пути, использ. не более  одной дуги 

 

D ⁽¹⁾₁ = 0

 

                       D ^{( 1)}₃ = 4           D ^{( 1)}₅ = ∞ 
 

                            D ^{( 2)}₂ = 1         D ^{( 2)}₄ = 9 

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

D ^{( 2)}₁ = 0

                              D ^{( 2)}₃ = 2       D ^{( 2)}₅ = 6 
 
 

                              D ^{( 3)}₂ = 1         D ^{( 3)}₄ = 9

D ^{( 3)}₁ = 0

                                                                 Кратч.путь, исп.не более трех  дуг 

 

                                 D ^{( 3)}₃ = 2         D ^{( 3)}₅ = 4 
 
 
 

                             D ^{( 4)}₂ = 1         D ^{( 4)}₄ = 8

      D ^{( 4)}₁ = 0

                                                                     Итоговое дерево кратч. путей

 

                                D ^{( 4)}₃ = 2        D ^{( 4)}₅ = 4 

D ^{( h )} – длина кратчайшего пути, содержащего не более h дуг, причем путь содержит не более N – 1 дуг ( N – число узлов );

Пусть D _i - длина кратчайшего пути от узла 1 к узлу i; D ₁ = 0; h = N – 1, тогда: 

D _i = min ( D _j + d _{j i} ) для всех i = 1 

Это уравнение Беллмана, оно означает, что длина кратчайшего пути от узла 1 к i равна сумме длины пути к узлу, предшествующему узлу i ( на кратчайшем пути ) и расстояния на последней дуге пути. 

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

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

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

 

Этот алгоритм требует, чтобы длины всех дуг  были положительны; объем вычислений для этого алгоритма меньше, чем  у алгоритма Беллмана – Форда.

Основная идея – отыскивать кратчайшие пути в  порядке возрастания длины пути.

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

Для описания процедуры  в виде алгоритма каждому узлу i присваивается метка D _i ( оценка длины кратчайшего пути от узла1). Если эта оценка неизменна ( узел окончательно помечен), то множество окончательно помеченных узлов обозначают Р.

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