close

Вход

Забыли?

вход по аккаунту

?

Zaikin Apparatn sredstva i algoritmi marshrutiz v setyah s paketn kommut Metodi analiza parametrov

код для вставкиСкачать
Федеральное агентство связи
Государственное федеральное образовательное учреждение
высшего профессионального образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
ЭЛЕКТРОННАЯ
БИБЛИОТЕЧНАЯ СИСТЕМА
Самара
Федеральное агентство связи
Государственное образовательное учреждение высшего профессионального
образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
Кафедра МСИБ
Аппаратные средства и алгоритмы маршрутизации в сетях с пакетной
коммутацией. Методы анализа параметров
Учебное пособие по дисциплинам МвСПК, ТиТДЭС
Для студентов 4 курса
дневного отделения
(специальности 210400, 210404, 210406)
Составитель: к.т.н., доц. Зайкин В.П.
Редактор: к.т.н., доц. Киреева Н.В.
Рецензент: д.т.н., проф. Карташевский В.Г.
САМАРА
2011
2
Рецензент – доктор технических наук, профессор, заведующий кафедрой
«Мультисервисные сети и информационная безопасность» В.Г. Карташевский
Зайкин В.П.,
Аппаратные средства, алгоритмы маршрутизации и методы анализа сетей с
пакетной коммутацией, - С.:ИУНЛ ПГУТИ, 2011. – 137с.
Рекомендовано ГОУ ВПО ПГУТИ в качестве учебного пособия для студентов
ПГУТИ специальностей 210400, 210406 по дисциплинам ТиТДЭС и МвСПК
Протокол кафедры МСИБ ПГУТИ №7от 4.06. 2011г.
© ИУНЛ ПГУТИ
© Зайкин В.П.,
3
Оглавление
1. Уровневая модель взаимодействия открытых систем (OSI) 6
2. Маршрутизация ............................................ 16
2.1 Мосты........................................................... 16
2.1.1 Классификация мостов ........................... 16
2.2 Коммутаторы............................................... 20
2.2.1 Типы коммутаторов ................................ 21
2.2.2 Технические параметры коммутаторов.25
2.2.3 Дополнительные возможности коммутаторов.
28
2.3 Маршрутизаторы ........................................ 31
2.4 Протоколы маршрутизации ....................... 33
2.4.1 Протоколы длины вектора ..................... 34
2.4.2 Протоколы состояния канала ................. 34
2.4.3 Протоколы политики (правил) маршрутизации 35
2.4.4 Усиленная однопроцессорная архитектура 37
2.4.5 Симметричная многопроцессорная архитектура 37
3. Алгоритмы маршрутизации ............................ 38
3.1 Алгоритм Дийкстра. Теоретическая часть38
3.1.1 Формальное описание алгоритма .......... 39
3.1.2 Решение задачи вручную ........................ 40
3.1.3 Определение таблицы минимальных путей 41
3.1.4 Определение минимального пути методом «отката»
44
3.1.5 Программирование .................................. 45
3.1.6 Результаты работы программы ........... 54
3.2 Метод Флойда ............................................. 55
3.2.1 Теоретическая часть ............................. 55
3.2.2 Формальное описание алгоритма ....... 56
3.2.3 Пример решения задачи ...................... 57
3.2.4 Программирование ............................... 63
3.2.5 Результат работы программы.............. 68
3.3 Метод Форда-Фолкерсона (Ford-Falkerson)69
3.3.1 Теоретическая часть ............................. 69
3.3.2 Алгоритм Форда-Фалкерсона нахождения множества вершин А V,
определяющих минимальное сечение ............ 71
3.3.3 Решение задачи вручную ..................... 72
3.3.4 Программа ............................................. 77
3.4 Метод поиска маршрута в связном графе (алгоритм Терри)
89
3.4.1 Теоретическая часть ............................. 89
3.4.2 Алгоритм Терри.................................... 89
3.4.3 Решение задачи вручную ..................... 90
3.4.4 Программирование ............................... 95
3.4.5 Решение задачи на ПВМ...................... 97
4 Структурный анализ сети ................................ 98
4.1 Структура сети. Основные понятия.......... 98
4
4.2 Основные сетевые топологии.................. 101
4.2.1 Разновидности древовидной топологии101
4.2.2 Сетевидные топологии ......................... 103
4.3 Структурная матрица сети ....................... 106
4.3.1 Результаты операций над структурными матрицами. 107
4.3.2 Результаты, получаемые преобразованием определителя структурной
матрицы ........................................................... 110
4.4 Основные свойства булевых определителей 110
4.5 Применение определителей характеристической матрицы
111
4.5.1 Сечения и разрезы. Дерево путей. ....... 111
4.5.2 Дерево путей .......................................... 115
4.6 Нахождение путей с минимальным весом118
5 Анализ временных параметров звена данных сети с пакетной коммутацией
121
5.1 Модель звена передачи данных как системы массового обслуживания
(СМО). ................................................................. 121
5.2 Входящий поток........................................ 122
5.3 Время обслуживания ................................ 124
5.3.1 Параметры распределения времени передачи по звену данных при
использовании РОС-НП. ............................... 126
5.3.2 Параметры распределения времени передачи по звену данных при
использовании РОС-ОЖ ................................ 127
5.4 Среднее время задержки сообщения ...... 128
5.5 Выходящий поток. .................................... 129
5.6 Достоверность работы звена данных. .... 131
5.7 Достоверность принятия сообщений...... 133
6 Анализ надежности системы передачи данных136
6.1 Основные понятия надежности систем ПД.136
6.2 Основные показатели надежности.......... 137
6.3 Основные пути повышения надежности 141
Список литературы ............................................... 143
5
1. Уровневая модель взаимодействия открытых систем (OSI)
В 1984 году с целью упрощения взаимодействия устройств в сетях
Международная организация по стандартизации (International Organization of
Standardization
ISO)
предложила
семиуровневую
эталонную
коммуникационную модель «Взаимодействие Открытых Систем» (Open System
Interconnection - OSI).
Разработка этой модели была обусловлена рядом факторов и причин,
такими как:
 появление новых технологий, таких как Fast Ethernet, 100VG-AnyLan,
FDDI;
 резкое
расширение
оборудования;
списка
фирм-производителей
сетевого
 отсутствие единой, стандартной и независимой от поставщика среды,
т.е. наличия оборудования, работающего по одним и тем же правилам и
т.д.
Все эти причины привели к необходимости разработки базовой модели
сетевого взаимодействия. Модель OSI стала основой новых разработок в
области сетевой коммутации, она позволила соединить в единую сеть всѐ
многообразие выпускаемых программно-аппаратных средств. Кроме того,
модель OSI является самой лучшей методологической основой для изучения
сетевых технологий.
Эталонная модель OSI разбивает большую задачу организации движения
информации в сети на семь относительно автономных, более мелких подзадач.
Каждая из семи подзадач соответствует своему, строго определѐнному
уровню модели OSI.
Эталонная модель OSI включает в себя следующие уровни:
1. Приложений (Application);
2. Представления (Presentation);
3. Сеансовый (Session);
4. Транспортный (Transport);
5. Сетевой (Network);
6. Канальный (Data Link);
7. Физический (Physical).
Прикладной уровень отвечает за доступ приложений в сеть. В
действительности – это набор разнообразных протоколов, с помощью которых
организуется доступ к разделяемым ресурсам, совместная работа пользователей
и управление сетью компьютеров.
6
К числу наиболее распространѐнных протоколов верхних уровней
относятся:
FTP – протокол переноса файлов;
TFTP – упрощѐнный протокол переноса файлов;
X.400 – электронная почта;
Telnet
SMTP – простой протокол почтового обмена;
CMIP – общий протокол управления информацией;
SNMP – простой протокол управления сетью;
NFS – сетевая файловая система;
FTAM – метод доступа для переноса файлов;
Уровень представления отвечает за возможность диалога между
приложениями, функционирующими на разных машинах. Этот уровень
гарантирует, что информация, передаваемая прикладным уровнем, будет
понятна прикладному уровню в другой системе. При необходимости уровень
представления выполняет преобразование форматов данных в некоторый
общий формат представления, а на приѐме, соответственно, выполняет
обратное преобразование.
Таким образом, прикладные уровни могут преодолеть, например,
синтаксические различия в представлении данных. На этом уровне может
выполняться шифрование и дешифрование данных, благодаря которому
секретность обмена данными обеспечивается сразу для всех прикладных
сервисов.
Примером протокола, работающего на уровне представления, является
протокол Secure Socket Layer (SSL), который обеспечивает секретный
обмен сообщениями для протоколов прикладного уровня стека TCP/IP.
Протоколы уровня представления обычно являются составной частью
функций трѐх верхних уровней модели.
Сеансовый уровень координирует обмен информацией между
системами. Он обеспечивает управление диалогом для того, чтобы
фиксировать, какая из сторон является активной в настоящий момент, а также
предоставляет средства синхронизации. Последние добавляют к пакетам
информацию, которую используют коммуникационные протоколы и которая
служит для поддержания сеанса до завершения передачи.
На практике немногие приложения используют сеансовый уровень, он
редко реализуется и обычно является составной частью функций трѐх верхних
уровней модели.
7
Транспортный уровень делит потоки информации на достаточно
малые фрагменты (пакеты) для передачи их на сетевой уровень, обеспечивает
наивысший уровень управления процессом перемещения данных из одной
системы в другую с той степенью надѐжности, которая требуется.
Модель OSI определяет пять классов сервиса, предоставляемых
транспортным уровнем. Эти виды сервиса отличаются качеством
предоставляемых услуг: срочностью, возможностью восстановления
прерванной связи, наличием средств мультиплексирования нескольких
соединений между различными прикладными протоколами через общий
транспортный протокол, а главное – способностью к обнаружению и
исправлению ошибок передачи, таких как искажение, потеря и дублирование
пакетов.
Как правило, все протоколы, начиная с транспортного уровня и выше,
реализуются программными средствами конечных узлов сети –
компонентами их сетевых операционных систем.
Наиболее распространѐнные протоколы транспортного уровня:
TCP – протокол управления передачей
NCP – Netware Core Protocol
SPX – упорядоченный обмен пакетами
На сетевом уровне вводится понятие «сеть». Уровень необходим для
образования единой транспортной системы, объединяющей несколько
сетей с различными принципами передачи информации между конечными
узлами.
В данном случае под сетью понимается совокупность компьютеров,
соединѐнных между собой в соответствии с одной из стандартных типовых
топологий и использующих для передачи данных один из протоколов
канального уровня, определѐнный для этой топологии.
Сообщения сетевого уровня принято называть пакетами (packets).
На этом же уровне происходит маршрутизация пакетов на основе
преобразования MAC-адресов в сетевые адреса. Сетевой уровень обеспечивает
также прозрачную передачу пакетов на транспортный уровень.
Наиболее часто на сетевом уровне используются протоколы:
IP – протокол Internet
IPX – протокол межсетевого обмена
X.25 - (частично протокол реализован на уровне 2)
CLNP – сетевой протокол без организации соединений
На канальном уровне биты группируются в наборы, называемые
кадрами (frames).
8
Канальный уровень обеспечивает создание кадров, а также
обеспечивает корректность передачи и приѐма кадров, помещая специальную
последовательность бит в начало и конец каждого кадра, чтобы обозначить его
границы, а также вычисляет контрольную сумму, суммируя все байты кадра
определѐнным способом и добавляя к нему контрольную сумму.
Этот уровень обслуживает запросы сетевого уровня и использует сервис
физического уровня для приѐма и передачи пакетов.
Спецификации IEEE 802.x делят канальный уровень на два подуровня:
управление логическим каналом (LLC)
и управление доступом к среде (MAC).
Подуровень LLC обеспечивает обслуживание сетевого уровня,
подуровень MAC регулирует доступ к разделяемой физической среде.
а
На канальном уровне наиболее часто используются протоколы:
HDLC для последовательных (двухточечных) соединений;
IEEE 802.2 LLC (тип I и тип II) обеспечивают MAC для сред 802.x;
Ethernet;
Token ring;
X.25;
Frame relay.
Физический уровень получает пакеты данных от вышележащего
канального уровня и преобразует их в оптические или электрические сигналы,
соответствующие 0 и 1 бинарного потока. Эти сигналы посылаются через среду
передачи на приѐмный узел.
К этому уровню имеют отношение характеристики физических
сред передачи данных, такие как полоса пропускания, помехозащищѐнность,
волновое сопротивление и другие.
На этом уровне определяются характеристики электрических
сигналов, такие как крутизна фронтов импульсов, уровни напряжения или
тока передаваемого сигнала, тип кодирования, скорость передачи сигналов.
Кроме того, на этом уровне
назначение каждого контакта.
стандартизуются типы разъѐмов и
К числу наиболее распространѐнных спецификаций физического уровня
относятся:
EIA-RS-232-C, CCITT - V.24/V.28 – механические/электрические
характеристики несбалансированного последовательного интерфейса;
9
EIA-RS-422/449, CCITT - V.10 – механические, электрические и
оптические характеристики сбалансированного последовательного
интерфейса;
IEEE 802.3 – Ethernet;
IEEE 802.5 – Token ring.
Модель OSI описывает процедуры продвижения информации через
сетевую среду от прикладной программы одного компьютера до другой,
находящейся на другом компьютере.
При этом информация, которой обмениваются взаимодействующие
процессы, проходит от прикладной программы – источника вниз через все
уровни своей системы. Это диктуется тем, что одноименные уровни разных
систем не могут взаимодействовать между собой напрямую.
По мере прохождения информации вниз внутри своей системы
информация преобразуется в вид, удобный для передачи по физическим
каналам связи.
Исходная информация
Полученные данные
7
6
5
4
3
2
1
7
6
5
4
3
2
1
преобразование при приѐме
Преобразование при передаче
На узле – приемнике принятое сообщение проходит через все уровни
данной системы наверх. По мере продвижения по уровням блоки данных,
последовательно освобождаясь от заголовков и концевиков и преобразуется в
итоге в первоначальный вид (см. рис.1).
передача данных по физическому каналу
Рис.1.1 Схема преобразования информации при движении по уровням
модели
Эталонная модель OSI не является реализацией сети. Она только
определяет функции каждого уровня и даѐт простое представление о движении
данных в сети. Она служит основой для описания и понимания сетевой
стратегии в целом.
Для представления организации межсетевого взаимодействия
необходимым и достаточным условием является знание процессов,
соответствующих первым трѐм уровням эталонной модели OSI:
физического, канального и сетевого.
Физический уровень – самый низкий в модели OSI. На нѐм
определяются электрические, механические, функциональные и процедурные
10
параметры для физической связи в системах. Физическая связь и не разрывная с
ней эксплуатационная готовность являются основной функцией этого уровня.
Уровень описывает процесс прохождения сигналов через среду передачи
между сетевыми устройствами.
Средой передачи может быть медный кабель (коаксиал, витая пара, и т.д.),
оптоволокно, радиоканал.
Computer
Computer
010100100110100110
U
t
Рис.1.2. передача данных по физической среде
Спецификации физического уровня определяют такие характеристики, как
уровни напряжения, синхронизацию изменений напряжения, скорость передачи
физической информации, максимальные расстояния, физические соединения и
т.д.
Большинство базовых технологий локальных сетей допускают
использование различных спецификаций физического уровня в одной сети.
Данные спецификации отличаются средой передачи и способами
представления сигналов в этих средах.
Например, технология Ethernet, обеспечивающая передачу со скоростью
10 Мбит/с, имеет шесть вариантов реализации физического уровня: 10BASE5, 10BASE-2, 10BASE-T, FOIRL, 10BASE-FL и 10BASE-FB. Согласование
этих вариантов выполняют специальные устройства, имеющие интерфейсы с
трансиверами различных типов.
Канальный уровень обеспечивает надѐжную передачу данных через
физический канал. Он оперирует блоками данных, которые называют кадрами
(frame). В локальных сетях используется разделяемая среда передачи данных.
Основной функцией канального уровня при приѐме кадра из сети и
отправки его в сеть является реализация процедуры доступа к среде передачи
данных.
При выполнении этой задачи канальный уровень осуществляет:
-
физическую адресацию передаваемых сообщений;
11
-
выполнение правил использования физического канала;
-
выявление неисправностей;
-
управление потоками информации.
Функции канального уровня реализуются установленными в компьютерах
сетевыми адаптерами и соответствующими драйверами, а также
различным коммуникационным оборудованием:
мостами,
коммутаторами,
маршрутизаторами.
Институт инженеров по электротехнике и электронике (Institute of
Electrical and Electronics Engineers - IEEE) предложил другой, широко
используемый вариант модели OSI. Этот подход стал основой проектирования
локальных сетей.
IEEE-модель отличается тем, что в локальных сетях канальный уровень
разделяется на два подуровня (см. рис.3):
уровень управления логическим каналом (Logical Link Control – LLC);
уровень доступа к среде (Media Access Layer – MAC).
12
Рис.1.3. Структура канального уровня
Сетевой уровень обеспечивает возможность соединения и выбора
маршрута между двумя конечными системами, подключенными к разным
сетям.
Сетевой уровень служит для образования единой транспортной
системы, объединяющей несколько сетей с различными принципами
передачи данных.
Уровень предоставляет средства для решения следующих задач:
доставки пакетов в сети с произвольной топологией;
структуризации сети методом локализации широковещательного
трафика;
согласования различных методов работы канального уровня.
13
MAC
Data Link
LLC
MAC-уровень обеспечивает доступ к каналу передачи данных. На этом уровне
формируется физический адрес устройства, работающего с этим каналом. Этот
физический адрес обозначается как MAC-адрес. Каждое устройство сети
идентифицируется этим уникальным адресом, который присваивается каждому
сетевому интерфейсу устройства. MAC-адрес позволяет выполнять единичную
адресацию кадров, групповую и широковещательную. При передаче данных в
сети отправитель указывает MAC-адрес получателя в передаваемом кадре.
Кроме того, MAC-уровень должен согласовать дуплексный режим работы
уровня LLC с режимом работы физического уровня. Для этого он буферизует
кадры для передачи их по назначению в момент получения доступа к среде.
Уровень LLC отвечает за достоверную передачу кадров данных между
станциями сети и реализует взаимодействие с сетевым уровнем. Он даѐт более
высоким уровням возможность управления качеством услуг. LLC обеспечивает
сервис трѐх типов:
1.
сервис без подтверждения доставки и установления соединения. Этот
вид сервиса называют дейтаграммным. Он не гарантирует доставку кадров. Он
чаще используется в приложениях, где протоколы более высокого уровня сами
обеспечивают защиту от ошибок и функции потоковой передачи данных;
2.
сервис с установлением соединения – обеспечивает самый надѐжный
обмен кадрами;
3.
сервис без установления соединения с подтверждением доставки.
Сетевой уровень введѐн для обеспечения работы на произвольных сетевых
топологиях с сохранением возможности использования простого метода
передачи пакета при типовых топологиях.
Канальный уровень не способен осуществлять адресацию в сетях с
развитой структурой. Поэтому при передаче информации через объединенную
сеть в кадры канального уровня добавляется заголовок сетевого уровня,
который имеет унифицированный формат, не зависящий от формата кадров
канального уровня сетей, входящих в объединѐнную сеть.
Основное место в заголовке сетевого уровня отводится адресу
получателя. При этом используется не MAC-адрес, а составной адрес –
номер сети и номер абонента в данной сети.
Такая нумерация сетей позволяет протоколам сетевого уровня составлять
точный план связей и выбирать оптимальные маршруты при любой топологии.
Network
Data Link
Physical
З 1 Данные
З2
Данные
Данные
Пакеты
Кадры
З 1 – заголовок пакета
сетевого уровня
Потоки бит
З 2 – заголовок
кадра канального
уровня
Рис.1.4.
структуры сообщений при движении по уровням модели
Трансформация
Для более чѐткого представления о назначениях сетей их часто условно
делят на три большие категории:
глобальные сети (WAN),
городские сети (MAN)
и локальные сети (LAN).
Глобальные сети позволяют организовать взаимодействие между
абонентами на больших расстояниях. Эти сети работают на более низких
скоростях и имеют большие задержки при соединениях. Глобальные сети WAN
могут также иметь обозначение систем дальней связи (СДС).
Городские сети позволяют взаимодействовать на территориальных
образованиях меньших размеров и работают на скоростях от средних до
высоких. Они получили своѐ название из-за способности одной MAN занимать
область размером с большой город. Эти сети работают с меньшими
задержками, чем глобальные, но не могут обеспечить взаимодействие на
больших расстояниях. Городские сети часто определяют как корпоративные,
распределѐнные.
Локальные сети (российская аббревиатура ЛВС – локальные
вычислительные сети) обеспечивают наивысшие скорости обмена
информацией между компьютерами.
Кроме отличий по скорости передачи данных между этими типами сетей
существуют и другие отличия.
14
В локальных сетях каждый компьютер содержит сетевое интерфейсное
устройство, которое соединяет его с сетевой средой передачи.
Сети MAN содержат активные коммутирующие устройства.
WAN (MAN)
LAN#1
LAN#3
M2
M1
LAN#2
Рис.1.5. образование городской сети путем объединения локальных
сетей с использованием маршрутизаторов
Глобальные сети обычно состоят из групп сложных маршрутизаторов
пакетов, соединѐнных линиями связи. Сеть может быть расширена
добавлением нового маршрутизатора.
Глобальные и городские сети могут быть получены соединением с
помощью маршрутизаторов некоторого количества локальных сетей (см.
рис.5):
15
2. Маршрутизация
В сложных распределѐнных сетях часто существует возможность выбора
нескольких альтернативных маршрутов передачи информации между двумя
конечными станциями.
Маршрутизаторы совместно с конечными станциями решают свою
основную задачу – выбор маршрута. Маршрутизатор выбирает маршрут на
основании имеющейся у него информации о текущем состоянии и
конфигурации сети.
Для хорошего понимания процессов маршрутизации необходимо знание
также основных принципов работы мостов и коммутаторов.
2.1
Мосты
Мост (bridge) – это устройство, которое обеспечивает взаимосвязь двух
(реже нескольких) локальных сетей посредством передачи кадров из одной сети
в другую с использованием процедуры промежуточной буферизации.
Мост, в отличие от повторителя, не старается поддержать побитовый
синхронизм в обеих объединяемых сетях. Вместо этого он выступает по
отношению к каждой из сетей как конечный узел. Он принимает кадр,
буферизует его, анализирует адрес назначения кадра и только в том случае,
когда адресуемый узел действительно принадлежит другой сети, он передаѐт
его туда.
Таким образом, мост изолирует трафик одного сегмента от трафика
другого сегмента, фильтруя кадры, уменьшая при этом коэффициент загрузки
сегментов.
Кроме того, он уменьшает возможности несанкционированного
доступа, так как пакеты, предназначенные для циркуляции внутри одного
сегмента, физически не появляются на других, что исключает их
«прослушивание» станциями других сегментов.
2.1.1 Классификация мостов
МОСТЫ
Локальные
Глобальные
С маршрутизацией
от источника
Прозрачные
Рис.2.1. Классификация мостов
Локальные мосты оборудуются портами для подключения к ЛВС.
Типичными для такой среды носителями являются:
коаксиальный кабель;
16
волоконно-оптический кабель;
или витая пара.
Важным свойством локальных мостов является их способность соединять
сети, использующие разные среды.
Например, с их помощью можно подключить сеть на коаксиальном кабеле
к сети с волоконно-оптическим кабелем или любую из них к сети на витой
паре.
Глобальные мосты – это такие мосты, порты которых согласуются со
средами для передачи информации на большие расстояния (сети WAN/MAN).
У глобальных мостов могут быть интерфейсы как для передачи на
большие расстояния, так и локальные.
Мосты первого типа выполняют так называемую маршрутизацию от
источника (Source Routing).
Термин «маршрутизация от источника» ввела фирма IBM для описания
процесса прохождения кадров через мосты в сетях Token Ring.
В такой сети мостам не требуется содержать адресную базу данных.
Они определяют путь прохождения кадра исходя из информации, хранящейся в
самом кадре.
Сеть Token
Ring #1
Станция
А
Сеть Token
Ring #2
Мост#1
Мост#2
Computer
Сеть Token
Ring #3
Станция
В
Computer
Рис.2.2 Структура глобальной сети на основе мостов
Ниже приведѐн
станциями:
алгоритм
установления
связи
между
конечными
1. Конечная станция A, которой необходимо связаться с другой конечной
станцией B, посылает специальный кадр, называемый кадрисследователь (Explorer Frame). При получении этого кадра Мост#1
вносит информацию о направлении, с которого был получен кадр, и
собственное имя в специально отведѐнное в кадре место. Далее он
передаѐт этот кадр по всем направлениям, кроме того, по которому он
был принят;
2. После получения всех кадров-исследователей конечная станция B
выбирает один из возможных маршрутов и посылает ответ станцииотправителю A. Как правило, выбирается тот маршрут, который
соответствует первому пришедшему кадру-исследователю, так как в
17
этом случае маршрут является наиболее коротким (время прохождения
кадра-исследователя минимально);
3. В посылаемом конечной станцией B ответе содержится информация о
маршруте, по которому должны быть посланы все остальные кадры.
После получения маршрута станция-отправитель A запоминает его и
использует всегда для отправки кадров получателю B.
Мосты второго типа называются «прозрачными» (transparent).
Прозрачные мосты, в свою очередь, делятся на три подтипа:
- Прозрачные (Transparent) – используются для объединения сетей с
идентичными протоколами на канальном и физическом уровнях
модели OSI (Ethernet-Ethernet, Token Ring- Token Ring и т.д.);
- Транслирующие (Translating) – используются для объединения сетей с
разными протоколами на канальном и физическом уровне;
- Инкапсулирующие (Encapsulating) – предназначены для объединения
сетей с одинаковыми протоколами (например, Ethernet) на канальном и
физическом уровне через сеть с другими протоколами (например, FDDI).
Прозрачные мосты являются наиболее распространѐнным типом. Для них
сеть представляется наборами MAC-адресов устройств, используемых на
канальном уровне. Мосты ориентируются на эти адреса для принятия решения
о передаче кадра. При этом кадр записывается во внутренний буфер моста.
Мосты этого типа не имеют доступа к информации об адресах сетей,
относящейся к сетевому уровню. Они ничего «не знают» о топологии связей
сегментов или сетей между собой.
Можно поэтому утверждать, что такие мосты являются совершенно
прозрачными для протоколов, начиная с сетевого уровня и выше.
Эта прозрачность позволяет мостам передавать кадры, не влияя на их
содержимое.
Мосты работают на MAC-подуровне канального уровня эталонной модели
OSI и обеспечивают возможность соединения двух или более локальных сетей
для образования логически единой сети.
Составляющие локальные сети становятся в этом случае сетевыми
сегментами полученной сети.
При передаче кадра внутри прозрачного моста происходит его
регенерация и трансляция с одного порта на другой.
Прозрачные мосты имеют дело, как с адресом отправителя, так и с адресом
получателя, находящимися в кадрах локальных сетей.
Мост использует адрес отправителя для автоматического построения
своей базы данных адресов устройств, называемой также MAC-таблицей.
18
В этой таблице устанавливается принадлежность адреса станции к какомулибо порту моста. Все операции, которые выполняет мост, связаны с этой
базой данных.
Все порты моста работают в так называемом неразборчивом режиме
захвата кадров, то есть все поступающие на порт кадры сохраняются в
буферной памяти. С помощью такого режима мост следит за всем трафиком,
передаваемым в присоединѐнных к нему сегментах, и использует проходящие
через него кадры для изучения состава сети.
Таблица
MAC-адресов
ПО моста
Буферная память
Порт#1
Сеть#1
Порт#2
Сеть#2
Рис.2.3 Процесс передачи кадров внутри прозрачного моста
Функциональную основу мостов составляют следующие свойства:
обучение;
фильтрация;
передача;
широковещание.
Поскольку существует возможность перемещения станций из одного
сегмента в другой, то мосты должны периодически обновлять содержимое
своих адресных баз.
Для реализации этой функции записи в адресной базе делятся на два типа:
статические и динамические.
19
Входящий
кадр
Обучение
включено?
нет
да
Адрес
отправителя в
базе?
Сброс
таймера
неактивности
Разрешено
продвижение
кадра?
да
Создание
новой записи
в базе
да
Адрес
нет Передача кадра
на все порты
получателя в
(широковещание)
базе?
да
нет
Удаление
кадра
(фильтрация)
нет
да
Конечные
станции в
одном
сегменте
нет
Передача
кадра на
соответству
ющий порт
Рис.2.4 Алгоритм работы прозрачного моста:
С каждой динамической записью связан таймер неактивности. При
получении кадра с адресом отправителя, который соответствует имеющейся в
адресной базе записи, соответствующий таймер неактивности сбрасывается в
исходное состояние.
Если от какой-либо станции долгое время не поступают кадры, то таймер
неактивности исчерпывает заданный интервал и соответствующая ему запись
удаляется из адресной базы.
2.2
Коммутаторы
Коммутатор (switch) – это устройство, конструктивно выполненное в
виде сетевого концентратора и действующее как высокоскоростной
многопортовый мост. Встроенный механизм коммутации позволяет
осуществить широковещательное сегментирование локальной сети, а также
выделить полосу пропускания к конечным станциям в сети.
Эти устройства появились в конце 80-х годов и использовались как
коммутаторы уровня предприятия. На первых порах использование
коммутирующих устройств носило исключительно тактический характер –
когда возникла необходимость решить задачу ограниченной пропускной
способности или производительности.
20
Широкое внедрение коммутаторов резко повысило пропускную
способность сетей за счѐт равномерного распределения полосы пропускания
между пользователями и приложениями.
Первоначальная стоимость коммутаторов была довольно высока. Тем не
менее, они оказались дешевле и проще в использовании, чем маршрутизаторы.
В последнее время использование коммутаторов вышло за пределы
применения на уровне предприятия. Это можно объяснить тем, что
коммутаторы позволяют повысить отдачу от существующей сети, при этом для
повышения производительности не нужно менять существующую кабельную
систему и оборудование конечных пользователей.
Под коммутацией обычно понимают четыре различные технологии:
конфигурационная коммутация;
коммутация кадров;
коммутация ячеек;
преобразование между кадрами и ячейками.
2.2.1 Типы коммутаторов
Различают коммутаторы:
 с коммутационной матрицей;
 с общей шиной;
 с разделяемой многовходовой памятью.
Коммутаторы с коммутационной матрицей за счѐт параллельной
обработки данных позволяют реализовать наиболее быстрый способ
взаимодействия портов. Эта реализация возможна только для определѐнного
числа портов. При этом сложность схемы возрастает пропорционально
квадрату количества портов коммутатора.
Предположим, необходимо передать кадр из порта 1 в порт 5. Процессор
коммутатора обращается к коммутационной матрице и пытается установить в
ней путь, связывающий эти порты.
Коммутационная матрица может это сделать только в том случае, если
порт адреса назначения в этот момент свободен.
21
Порт 1
Порт 2
Порт 3
Порт 4
Порт 5
Порт 6
Рис.2.5 Коммутатор с коммутационной матрицей
Если этот порт занят, то кадр буферизуется процессором порта 1, после
чего процессор коммутатора ожидает освобождения порта 5 и образования
коммутационной матрицей нужного пути.
После установления нужного пути по нему направляются буферизованные
портом 1 кадры, которые после получения ими доступа к среде передаются в
сеть через порт 5.
Матрица может быть реализована на основе комбинационных схем
различного типа, но еѐ особенностью остаѐтся технология коммутации
физических каналов.
Основным недостатком данной технологии является отсутствие
возможности буферизации данных внутри коммутационной матрицы.
В коммутаторах с общей шиной в режиме разделения времени
используется высокоскоростная шина для связи процессоров портов.
В этой архитектуре
процессоры портов.
активную роль
играют специализированные
Высокоскоростная шина играет пассивную роль.
Чтобы шина не была узким местом коммутатора, еѐ производительность
должна быть в несколько раз выше скорости поступления данных на входные
порты.
Для уменьшения задержек при передаче кадр должен передаваться по
шине небольшими частями. Размер этих частей определяется производителем
коммутатора.
Шина, так же, как и коммутационная матрица, не может осуществлять
промежуточную буферизацию.
Коммутаторы с разделяемой многовходовой памятью.
Входные блоки процессоров портов таких коммутаторов соединяются
через переключатели входа с разделяемой памятью.
22
Выходные блоки этих же процессоров соединяются с этой памятью через
переключатели выхода.
Переключением входа и выхода разделяемой памяти управляет блок
управления портами. Он организует в разделяемой памяти несколько очередей
данных, по одной для каждого выходного порта.
Блок управления портами
Порт 1
Порт 1
Режим
портов:
Режим
портов:
Порт 2
Порт 2
приѐм
данных
передача
данных
Порт N
Порт N
Переключатели
входа
Разделяемая память
Переключатели
выхода
Рис.2.6 Схема коммутатора с разделяемой многовходовой памятью
Входные блоки процессоров передают блоку управления запросы на
запись данных в очередь того порта, который соответствует адресу назначения
пакета.
Блок управления портами по очереди подключает вход памяти к одному из
входных блоков процессора, и тот переписывает часть данных в очередь
определѐнного выходного порта.
По мере заполнения очередей блок управления производит поочерѐдное
подключение выхода разделяемой многовходовой памяти к выходным портам,
и данные из очереди переписываются в выходной буфер процессора.
Некоторые производители используют в своих коммутаторах различные
приѐмы управления потоком кадров для предотвращения потерь при
перегрузках в сети.
Потеря даже небольшого количества кадров обычно намного снижает
полезную производительность сети.
Поэтому при перегрузке рационально было бы замедлить интенсивность
поступления кадров от конечных узлов к коммутатору.
Для реализации алгоритма снижения интенсивности поступления кадров в
распоряжении коммутатора должен быть механизм снижения интенсивности
трафика подключенных к его портам узлов.
Существует два способа реализации снижения интенсивности трафика:
агрессивное поведение порта
23
и метод обратного давления.
Агрессивное поведение порта коммутатора может быть реализовано:
путѐм захвата среды передачи данных
или после коллизии в сети (для сети Ethernet).
Эти два случая иллюстрируются рисунком 12:
50
9,1
Кадры
коммутатора
Кадр 1
Кадр 2
Кадр 3
Коллизия
Кадры
компьютера
Ожидание
9,6
51,2
Ожидание
Ожидание
Коллизия
Рис.2.7 Механизмы снижения интенсивности трафика
В первом случае коммутатор окончил передачу очередного кадра и
сделал технологическую паузу в 9.1мкс вместо положенной паузы в 9.6мкс.
При этом компьютер, сделав ту же паузу, но в 9.6мкс, не смог захватить среду
передачи данных.
Во втором случае кадры коммутатора и компьютера столкнулись, и
была зафиксирована коллизия. Компьютер делает стандартную паузу после
коллизии в 51.2мкс, а коммутатор – в 50мкс. И в этом случае среда передачи
остаѐтся за коммутатором.
В основе метода обратного давления лежит передача компьютеру
фиктивных кадров при отсутствии в буфере коммутатора кадров для
передачи по данному порту.
В этом случае коммутатор может не нарушать алгоритм доступа, однако
интенсивность передачи кадров в коммутатор в среднем уменьшается вдвое.
Метод обратного давления используется либо для разгрузки общего
буфера, либо для разгрузки буфера процессора другого порта, в который
передаѐт свои кадры данный порт.
Существует два способа передачи пакетов коммутаторами:
со сквозной обработкой
и с буферизацией.
24
Коммутатор со сквозной обработкой кадров считывает только
физический адрес назначения, а сам кадр передаѐтся без проверки его
содержимого. Этот способ представляет собой, по сути, конвейерную
обработку кадров с частичным совмещением этапов передачи. В принципе,
коммутатор может выполнять проверку некорректности передаваемого кадра,
но не может изъять его из сети, так как часть его байтов уже передана в сеть.
Использование сквозной коммутации может дать значительный выигрыш в
производительности, но за счѐт снижения надѐжности. В сетях с технологией
обнаружения коллизий передача непроверенных искажѐнных кадров может
привести к нарушению целостности данных.
При коммутации с буферизацией происходит проверка содержимого
кадра: если в кадре содержится ошибка, то он отбраковывается.
Коммутатор представляет собой сложное устройство, имеющее один или
несколько процессорных модулей, и естественно, что он может выполнять
помимо основной задачи по передаче кадров с порта на порт некоторые
дополнительные функции. К ним относятся:
трансляция протоколов канального уровня;
фильтрация кадров;
использование различных классов сервиса;
поддержка виртуальных сетей.
По конструктивному исполнению коммутаторы делятся:
на автономные коммутаторы с фиксированным количеством портов;
модульные коммутаторы на основе шасси;
коммутаторы с фиксированным количеством портов, собираемые в стек.
2.2.2 Технические параметры коммутаторов.
К основным техническим параметрам, которыми можно оценить
коммутатор, построенный с использованием любой архитектуры, является
скорость фильтрации (filtering) и скорость продвижения (forwarding).
Скорость фильтрации определяет количество кадров в секунду, с
которыми коммутатор успевает проделать следующие операции:
прием кадра в свой буфер;
нахождения порта для адреса назначения кадра в адресной таблице;
уничтожение кадра (порт назначения совпадает с портом-источником).
Скорость продвижения, по аналогии с предыдущим пунктом, определяет
количество кадров в секунду, которые могут быть обработаны по следующему
алгоритму:
25
прием кадра в свой буфер,
нахождения порта для адреса назначения кадра;
передача кадра в сеть через найденный (по адресной таблице
соответствия) порт назначения.
По умолчанию считается, что эти показатели измеряются на протоколе
Ethernet для кадров минимального размера (длиной 64 байта). Так как основное
время занимает анализ заголовка, то чем короче передаваемые кадры, тем более
серьезную нагрузку они создают на процессор и шину коммутатора.
Следующими по значимости техническими параметрами коммутатора
будут:
пропускная способность (throughput);
задержка передачи кадра.
размер внутренней адресной таблицы.
размер буфера (буферов) кадров;
производительность коммутатора;
Пропускная способность измеряется количеством данных, переданных
через порты в единицу времени. Естественно, что чем больше длина кадра
(больше данных прикреплено к одному заголовку), тем больше должна быть
пропускная способность. Так, при типичной для таких устройств "паспортной"
скорости продвижения в 14880 кадров в секунду, пропускная способность
составит 5.48 Мб/с на пакетах по 64 байта, и ограничение скорости передачи
данных будет наложено коммутатором.
В то же время, при передаче кадров максимальной длины (1500 байт),
скорость продвижения составит 812 кадров в секунду, а пропускная
способность - 9,74 Мб/c. Фактически, ограничение на передачу данных будет
определяться скоростью протокола Ethernet.
Задержка передачи кадра означает время, прошедшее с момента начала
записи кадра в буфер входного порта коммутатора, до появления на его
выходном порту. Можно сказать, что это время продвижения единичного кадра
(буферизация, просмотр таблицы, принятие решения о фильтрации или
продвижении, и получение доступа к среде выходного порта).
Величина задержки очень сильно зависит от способа продвижения кадров.
Если применяется метод коммутации "на лету", то задержки невелики и
составляют от 10 мкс до 40 мкс, в то время как при полной буферизации - от 50
мкс до 200 мкс (в зависимости от длины кадров).
В случае большой загруженности коммутатора (или даже одного из его
портов), получается, что даже при коммутации "на лету" большая часть
входящих кадров вынужденно буферизируется. Поэтому, наиболее сложные и
дорогие модели имеют возможность автоматической смены механизма работы
коммутатора (адаптацию) в зависимости от нагрузки и характера трафика.
26
Размер адресной таблицы (САМ-таблицы). Определяет максимальное
количество MAC-адресов, которые содержатся в таблице соответствия портов и
МАС-адресов. В технической документации обычно приводится на один порт,
как число адресов, но иногда бывает, что указывается размер памяти под
таблицу в килобайтах (одна запись занимает не менее 8 кб, и "подменить"
число весьма выгодно недобросовестному производителю).
Для каждого порта САМ-таблица соответствия может быть разной, и при
ее переполнении наиболее старая запись стирается, а новая - заносится в
таблицу. Поэтому при превышении количества адресов сеть может продолжить
работу, но при этом сильно замедлиться работа самого коммутатора, а
подключенные к нему сегменты будут загружены избыточным трафиком.
Раньше встречались модели (например, 3com SuperStack II 1000 Desktop), в
которых размер таблицы позволял хранить один или несколько адресов, из-за
чего приходилось относиться очень внимательно к дизайну сети. Однако,
сейчас даже самые дешевые настольные коммутаторы имеют таблицу из 2-3К
адресов (а магистральные еще больше), и этот параметр перестал быть узким
местом технологии.
Объем буфера. Он необходим коммутатору для временного хранения
кадров данных в тех случаях, когда нет возможности сразу их передать на порт
назначения. Понятно, что трафик неравномерен, всегда есть пульсации,
которые нужно сглаживать. И чем больше объем буфера, тем большую
нагрузку он может "принять на себя".
Простые модели коммутаторов имеют буферную память в несколько сотен
килобайт на порт, в более дорогих моделях это значение достигает нескольких
мегабайт.
Производительность коммутаторов. Прежде всего, надо отметить, что
коммутатор - сложное многопортовое устройство, и просто так, по каждому
параметру в отдельности, нельзя оценить его пригодность к решению
поставленной задачи. Существует большое количество вариантов трафика, с
разной интенсивностью, размерами кадров, распределением по портам, и т.п.
Общей методики оценки (эталонного трафика) до сих пор нет, и используются
разнообразные "корпоративные тесты". Они достаточно сложны, и в данной
книге придется ограничиться только общими рекомендациями.
Идеальный коммутатор должен передавать кадры между портами с той же
самой скоростью, с которой их генерируют подключенный узлы, без потерь, и
не вносить дополнительных задержек. Для этого внутренние элементы
коммутатора (процессоры портов, межмодульная шина, центральный
процессор и т.п.) должны справляться с обработкой поступающего трафика.
В то же время, на практике есть много вполне объективных ограничений
на возможности свитчей. Классический случай, когда несколько узлов сети
интенсивно взаимодействуют с одним сервером, неизбежно вызовет
27
уменьшение реальной производительности из-за фиксированной скорости
протокола.
На сегодня производители вполне освоили производство коммутаторов
(10/100baseT), даже очень дешевые модели имеют достаточную пропускную
способность, и достаточно быстрые процессоры. Проблемы начинаются, когда
нужно применять более сложные методы ограничений скорости подключенных
узлов (обратного давления), фильтрации, и других протоколов, рассмотренных
ниже.
В заключение, нужно сказать, что лучшим критерием по-прежнему
остается практика, когда коммутатор показывает свои возможности в реальной
сети.
2.2.3 Дополнительные возможности коммутаторов.
Как уже отмечалось выше, современные коммутаторы имеют настолько
много возможностей, что обычная коммутация (казавшаяся технологическим
чудом десять лет назад) уходит на второй план. Действительно, быстро, и
относительно качественно, коммутировать кадры умеют модели стоимостью от
$50 до $5000. Различие идет именно по дополнительным возможностям.
Понятно, что наибольшее количество дополнительных возможностей
имеют управляемые коммутаторы. Далее будут специально выделены
опции, которые обычно нельзя корректно реализовать на настраиваемых
коммутаторах.
Соединение коммутаторов в стек. Эта дополнительная опция одна из
наиболее простых, и широко используемых в больших сетях. Ее смысл соединить несколько устройств скоростной общей шиной для повышения
производительности узла связи. При этом иногда могут быть использованы
опции единого управления, мониторинга и диагностики.
Надо заметить, что не все вендоры используют технологию соединения
коммутаторов при помощи специальных портов (стекирование). В этой области
все большее распространение получают линии Gigabit Ethernet, или при
помощи группировки нескольких (до 8) портов в один канал связи.
Протокол покрывающего дерева (Spanning Tree Protocol, STP). Для
простых ЛВС соблюдать в процессе эксплуатации правильную топологию
Ethernet (иерархическая звезда) не сложно. Но при большой инфраструктуре
это становится серьезной проблемой - неправильная кроссировка (замыкание
сегмента в кольцо) может привести к остановке функционирования всей сети
или ее части. Причем найти место аварии может быть совсем не просто.
С другой стороны, подобные избыточные связи часто удобны (многие
транспортные сети передачи данных построены именно по кольцевой
архитектуре), и могут сильно повысить надежность - при наличии корректного
механизма обработки петель.
28
Для решения этой задачи используется Spanning Tree Protocol (STP),
при котором коммутаторы автоматически создают активную древовидную
конфигурацию связей, находя ее с помощью обмена служебными пакетами
(Bridge Protocol Data Unit, BPDU), которые помещаются в поле данных
кадра Ethernet. В результате, порты, на которых замыкаются петли,
блокируются, но могут быть автоматически включены в случае разрыва
основного канала.
Таким образом, технология STA обеспечивает поддержку резервных
связей в сети сложной топологии, и возможность ее автоматическую изменения
без участия администратора. Такая возможность более чем полезна в больших
(или распределенных) сетях, но в силу своей сложности редко используется в
настраиваемых коммутаторах.
Способы управления входящим потоком. Как уже отмечалось выше,
при неравномерной загрузке коммутатора он просто физически не сможет
пропустить через себя поток данных на полной скорости. Но просто
отбрасывать лишние кадры по понятным причинам (например разрыв TCP
сессий) крайне не желательно. Поэтому приходится использовать механизм
ограничения интенсивности передаваемого узлом трафика.
Возможно два способа - агрессивный захват среды передачи
(например, коммутатор может не соблюдать стандартные временные
интервалы). Но этот способ годится только для "общей" среды передачи, редко
используемой в коммутируемом Ethernet. Этим же недостатком обладает
метод обратного давления (backpressure), при котором узлу передаются
фиктивные кадры.
Поэтому на практике востребована технология Advanced Flow Control
(описана в стандарте IEEE 802.3х), смысл которой в передаче коммутатором
узлу специальных кадров "пауза".
Фильтрация трафика. Часто бывает очень полезно задавать на портах
коммутатора дополнительные условия фильтрации входящих или исходящих
кадров. Таким способом можно ограничивать доступ определенных групп
пользователей к определенным сервисам сети, используя МАС-адрес, или тэг
виртуальной сети.
Как правило, условия фильтрации записываются в виде булевских
выражений, формируемых с помощью логических операций AND и OR.
Сложная фильтрация требует от коммутатора дополнительной
вычислительной мощности, и при ее нехватке может существенно снизить
производительность устройства.
Возможность фильтрации очень важна для сетей, в которых конечными
пользователями выступают "коммерческие" абоненты, поведение которых
невозможно регулировать административными мерами. Так как они могут
предпринимать несанкционированные деструктивные действия (например,
29
подделывать IP или MAC адрес своего компютера), желательно предоставить
для этого минимум возможностей.
Коммутация третьего уровня (Layer 3). Из-за быстрого роста скоростей,
и широкого применения коммутаторов, на сегодня образовался видимый
разрыв между возможностями коммутации и классической маршрутизацией
при помощи универсальных компьютеров.
Наиболее логично в этой ситуации дать управляемому коммутатору
возможность анализировать кадры на третьем уровне (по 7-ми уровневой
модели OSI). Такая упрощенная маршрутизация дает возможность значительно
поднять скорость, более гибко управлять трафиком большой ЛВС.
Однако в транспортных сетях передачи данных применение коммутаторов
пока очень ограничено, хотя тенденция к стиранию их отличий от
маршрутизаторов по возможностям прослеживается достаточно явно.
Управление и возможности мониторинга. Обширные дополнительные
возможности подразумевают развитые и удобные средства управления. Ранее
производимые устройства могли управляться несколькими кнопками через
небольшой цифровой индикатор, или через консольный порт.
В настоящее время выпускаются коммутаторы с управлением через
обычный порт 10/100baseT при помощи Telnet'а, Веб-браузера, или по
протоколу SNMP.
Если первые два способа по большому счету являются лишь удобным
продолжением обычных стартовых настроек, то SNMP позволяет использовать
коммутатор как поистине универсальный инструмент.
Для Etherenet интересны только его расширения - RMON и SMON.
Ниже рассмотрен RMON-I, кроме него существует RMON-II
(затрагивающий более высокие уровни OSI). Более того, в свитчах "среднего
уровня" как правило, реализованы только группы RMON 1-4 и 9.
Принцип работы следующий: RMON-агенты на свитчах передают
информацию на центральный сервер, где специальное программное
обеспечение (например, HP Open View) обрабатывает информацию,
представляя ее в удобном для администрирования виде.
Причем процессом можно управлять - удаленным изменением настроек
привести работу сети в норму. Кроме мониторинга и управления, при помощи
SNMP можно строить систему биллинга. Пока это выглядит несколько
экзотично, но примеры реального использования данного механизма уже есть.
Стандарт RMON-I MIB описывает 9 групп объектов:
1. Statistics - текущие накопленные статистические данные о
характеристиках кадров, количестве коллизий, ошибочных кадров (с
детализацией по типам ошибок) и т.п.
30
2. History - статистические данные, сохраненные через определенные
промежутки времени для последующего анализа тенденций их
изменений.
3. Alarms - пороговые значения статистических показателей, при
превышении которых агент RMON генерирует определенное событие.
Реализация этой группы требует реализации группы Events - события.
4. Host - данные о хостах сети, обнаруженных в результате анализа MACадресов кадров, циркулирующих в сети.
5. Host TopN - таблица N хостов сети, имеющих наивысшие значения
заданных статистических параметров.
6. Traffic Matrix - статистика о интенсивности трафика между каждой парой
хостов сети, упорядоченная в виде матрицы.
7. Filter - условия фильтрации пакетов; пакеты, удовлетворяющие
заданному условию, могут быть либо захвачены, либо могут
генерировать события.
8. Packet Capture - группа пакетов, захваченных по заданным условиям
фильтрации.
9. Event - условия регистрации событий и оповещения о событиях.
Более подробное рассмотрение возможностей SNMP потребует издания
отдельного пособия, поэтому ограничимся весьма общим описанием этого
сложного, но мощного инструмента.
Виртуальные сети (Virtual Local-Area Network, VLAN). Пожалуй, это
наиболее важная (особенно для домашних сетей), и широко используемая
возможность современных коммутаторов. Надо отметить, что существует
несколько принципиально отличных способов построения виртуальных сетей с
помощью коммутаторов.
Краткий смысл - средствами коммутаторов (2 уровня модели OSI) создать
несколько виртуальных (независимых друг от друга сетей) на одной
физической ЛВС Ethernet, предоставив возможность центральному
маршрутизатору управлять портами (или группами портов) на отдаленных
коммутаторах. Что собственно и делает VLAN очень удобным средством для
оказания услуг передачи данных (провайдинга).
2.3
Маршрутизаторы
Маршрутизатор (router) – это устройство третьего уровня эталонной
модели OSI, использующее одну или более метрик для определения
оптимального пути передачи трафика на основе информации сетевого уровня.
Маршрутизаторы – это чаще всего специализированные компьютеры с
устройствами ввода-вывода, со специальным программным обеспечением.
Маршрутизатор может быть программным – это программное
обеспечение, работающее на компьютере общего назначения, как правило, на
сетевом сервере.
31
Основная функция всех маршрутизаторов – маршрутизация трафика.
Кроме того, они могут выполнять ряд дополнительных функций. Процесс
маршрутизации можно представить двумя иерархически связанными
компонентами:
1.
Создание и сопровождение таблиц маршрутизации. Основная
функция таблицы маршрутизации – в установлении соответствия между
адресом сетевого уровня получателя и адресом сетевого уровня следующего
транзитного узла. Этим двум адресам ставится в соответствие определѐнный
выходной физический порт. Такой процесс можно назвать определением
маршрута для перемещения пакета;
2.
Передача пакетов. При этом проводится проверка контрольной
суммы заголовка пакета, определяется получатель пакета с адресом канального
уровня и производится отправка пакета с выполнением процедур очерѐдности,
фрагментации, фильтрации и т.д.
Уровень маршрутизации
Блок основных и
дополнительных
средств
Протокол
маршрутизации
Внутренний
интерфейс 1
(маршрут 1)
Внутренний
интерфейс N
(маршрут N)
Блокраспределитель
пакетов
Входящие
пакеты
Блок выбора
маршрутов
База данных:
Таблица
маршрутизации
База данных:
1. Полит. очерѐдности
2. Фрагментации
3. Фильтрации
4. и т. д.
Исходящие
пакеты
Уровень передачи пакетов
Рис.2.8 Функциональная схема маршрутизатора
Исходя из данного описания процесса маршрутизации можно составить
функциональную схему маршрутизатора, которая показана на рисунке 2.8:
В качестве иллюстрации приведена структура таблицы маршрутизации для
протокола IP.
Таблица маршрутизации для протокола IP:
Destination
Mask
Gateway
Metric
Status
TTL
Source
10.0.0.0
255.0.0.0
10.0.0.1
0
Up
-
Connected
20.0.0.0
255.0.0.0
20.0.0.1
0
Up
-
Connected
128.113.0.0
255.255.0.0
10.0.0.2
1
Up
160
RIP
32
129.213.0.0
255.255.0.0
10.0.0.2
2
Up
160
RIP
140.204.0.0
255.255.0.0
10.0.0.2
4
Up
160
RIP
152.67.0.0
255.255.0.0
10.0.0.2
3
Up
160
RIP
161.71.0.0
255.255.0.0
20.0.0.2
3
Up
160
RIP
164.117.0.0
255.255.0.0
20.0.0.2
4
Up
160
RIP
190.1.0.0
255.255.0.0
20.0.0.2
2
Up
160
RIP
130.87.0.0
255.255.0.0
20.0.0.2
1
-
Static
Столбцы имеют следующие значения:
- Destination – получатель пакетов. Получателем может быть как отдельная
станция, так и отдельные подсети в протоколе IP;
- Mask – маска подсети, ассоциирующаяся с сетевым адресом получателя;
- Gateway – IP-адрес следующего маршрутизатора на пути следования
пакетов;
- Metric – метрика маршрута, связанная с протоколом маршрутизации,
создавшим данную запись в таблице;
- Status – статус маршрута;
- TTL (Time-To-Live) – количество времени в секундах, в течение которого
данный маршрут будет оставаться в таблице маршрутизации;
- Source – указывает, является ли маршрут статическим (Static), напрямую
подключенным в сеть (Connected) или динамическим, полученным с
помощью протоколов маршрутизации (RIP, OSPF, IS-IS, EGP и т.д.).
Алгоритмы маршрутизации должны обладать рядом свойств. К ним
относятся:
 оптимальность при выборе маршрута;
 простота реализации;
 живучесть и стабильность;
 быстрая сходимость;
 гибкость.
Алгоритмы маршрутизации могут быть:
статическими или динамическими;
одномаршрутными или многомаршрутными;
одноуровневыми или иерархическими;
внутридоменными или междоменными;
одноадресными или групповыми.
2.4
Протоколы маршрутизации
33
Существует три основные группы протоколов маршрутизации.
Деление на группы определяется типом реализуемого алгоритма
определения оптимального маршрута.
К этим группам относятся протоколы:
длины вектора;
состояния канала;
политики маршрутизации.
2.4.1 Протоколы длины вектора
Это самые простые и самые распространѐнные. Своѐ название этот тип
протокола получил от способа обмена информацией.
Маршрутизатор с определѐнной периодичностью копирует адреса
получателей и метрику из своей таблицы маршрутизации и помещает эту
информацию в рассылаемые соседям сообщения об обновлении.
Соседние маршрутизаторы сверяют полученные данные со своими
собственными таблицами маршрутизации и вносят необходимые изменения.
После этого они сами рассылают сообщения об обновлении. Таким образом,
каждый маршрутизатор владеет информацией о маршрутах во всей сети.
При очевидной простоте алгоритма говорить о полной его надѐжности
нельзя. Он может работать наиболее эффективно только в небольших сетях.
К Протоколам данной группы относятся RIP IP, RIP IPX, AppleTalk
RTMP и Cisco IGRP.
2.4.2 Протоколы состояния канала
Данные протоколы реализуют алгоритм маршрутизации, предложенный в
1970 году Эдсгером Дейкстрой. Они значительно сложнее, чем протоколы
длины вектора.
Вместо рассылки соседям содержимого своих таблиц маршрутизации
каждый маршрутизатор осуществляет широковещательную рассылку списка
маршрутизаторов, с которыми он имеет непосредственную связь, и списка
напрямую подключенных к нему локальных сетей.
Эта информация является частью данных о состоянии канала и
рассылается в специальных сообщениях.
Кроме того, маршрутизатор рассылает сообщения о состоянии канала
только в случае изменения информации о них или по истечении заданного
интервала времени.
Протоколы состояния канала трудны в реализации и нуждаются в
значительном объѐме памяти для хранения информации о состоянии каналов.
Примерами этих протоколов могут служить: OSPF, IS-IS, Novell NLSP и
Cisco EIGRP.
34
2.4.3 Протоколы политики (правил) маршрутизации
Относятся к третьей группе протоколов. Они наиболее эффективно
решают задачу доставки получателю информации по разрешѐнным путям.
Эта категория протоколов используется при маршрутизации в Internet и
позволяет операторам получать информацию о маршрутизации от соседних
операторов на основании специальных критериев.
Алгоритмы, реализующие политики маршрутизации, опираются на
алгоритмы длины вектора, но информация о показателях путей
базируется на списке операторов магистрали.
Примерами протоколов данной категории могут служить BGP и EGP.
Уровень передачи пакетов реализован на алгоритмах коммутации и
в основном одинаков для большинства протоколов маршрутизации.
Отправитель, имея адрес маршрутизатора, посылает ему пакет,
адресованный специально в физический адрес этого маршрутизатора (MACуровень), но с адресом протокола (сетевой уровень) получателя. После
проверки адреса протокола получателя пакета маршрутизатор определяет,
«знает» ли он, как передать этот пакет следующему маршрутизатору в пути.
Если знает, то пакет отсылается путѐм замены физического адреса
получателя на физический адрес следующего маршрутизатора. Если не знает,
то пакет игнорируется. Следующая пересылка может либо быть, либо не быть
получателем пакета.
Если нет, то третий маршрутизатор является следующим пересылающим
устройством. Он выполняет такой же процесс принятия решения коммутации.
По мере прохождения пакета через сеть его физический адрес меняется, а
адрес протокола сетевого уровня остаѐтся неизменным. Этот процесс
проиллюстрирован на рисунке 2.9:
35
Пакет
А
Сетевой адрес – станция Б
Физический адрес – М 2
М2
Пакет
Сетевой адрес – станция Б
Физический адрес – Б
Сетевой адрес – станция Б
Физический адрес – М 1
Пакет
М1
Сетевой адрес – станция Б
Физический адрес – М 3
Пакет М 3
Б
Рис.2.9 Процесс продвижения пакета по сети
Маршрутизаторы функционируют на третьем уровне эталонной
модели OSI. Это предусматривает внесение в заголовок информации,
обеспечивающей интеллектуальную обработку пакетов.
Поскольку маршрутизаторы в основном работают с протоколом IP, они
способны реализовать связь без непосредственных соединений между
абонентами, при которой каждый пакет обрабатывается независимо и
отправляется получателю. При этом автоматически определяется совокупность
полос пропускания, позволяющая соответствующим образом распределять
трафик, достигая при этом высокой производительности.
При создании и дальнейшем развитии маршрутизаторов используются
три основных типа архитектуры:
однопроцессорная;
усиленная однопроцессорная;
симметричная многопроцессорная.
При однопроцессорной архитектуре на центральный процессор
маршрутизатора возлагается вся нагрузка по обработке трафика. Это
фильтрация и передача пакетов, модификация заголовков пакетов, обновление
таблиц маршрутизации, выделение служебных пакетов, работа с протоколом
SNMP, формирование управляющих пакетов и т.д.
Решение такого широкого спектра задач приводит к понижению
производительности процессора при усложнении окружающей сетевой среды.
Надѐжность маршрутизатора целиком зависит от работоспособности
36
центрального процессора. Даже применение мощного RISC-процессора не
снимает проблем, связанных с данной архитектурой.
Для преодоления части недостатков однопроцессорной архитектуры на
практике применяется метод еѐ усиления.
2.4.4 Усиленная однопроцессорная архитектура
При реализации этой архитектуры каждый интерфейсный модуль
маршрутизатора оснащается периферийным процессором. Этот процессор
решает задачи фильтрации и маршрутизации пакетов.
Центральный процессор при этом решает задачи, которые нельзя поручить
периферийному. Поэтому полученный эффект недостаточен для решения всех
возникающих при работе маршрутизатора проблем.
2.4.5 Симметричная многопроцессорная архитектура
В ней отсутствуют недостатки, присущие двум вышеназванным
архитектурам, так как происходит равномерное распределение нагрузки на все
сетевые интерфейсные модули.
Каждый модуль содержит свой процессор, который выполняет все задачи
маршрутизации и имеет свою копию таблицы маршрутизации.
Преимущества такой архитектуры признаны ведущими производителями
маршрутизаторов. Данная архитектура даѐт возможность получать
теоретически неограниченную мощность маршрутизаторов.
Сдерживающим фактором является ограниченное число стандартных
операционных систем, способных в полной мере реализовать преимущества
данной архитектуры.
37
3. Алгоритмы маршрутизации
3.1
Алгоритм Дийкстра. Теоретическая часть
Пусть G=<V,X> - взвешенный граф.
V - множество вершин графа, | V | n ; X – множество рѐбер графа.
Веса дуг имеют положительные значения.
Граф задан матрицей весов дуг C(G) [cij ] размера n n .
Задача о кратчайшем маршруте состоит в отыскании маршрута
минимального веса при условии, что хотя бы один такой маршрут существует.
Начальную и конечную вершины обозначим соответственно v0 и vk .
(v0 , vi ,...vi ,(n 1) , vk ) - маршрут минимального веса будем называть кратчайшим
маршрутом.
На каждом i-м шаге алгоритма Дийкстра всякая вершина v j V получает
метку M (v j ) , которая может быть постоянной или временной.
Значения меток определяют верхние границы кратчайших маршрутов от
начальной вершины v0 до произвольной вершины vj.
Постоянная метка (будем обозначать M * (v j ) ) есть вес кратчайшего
маршрута, проходящего только через те метки, которые получили к данному iму шагу постоянные метки.
Постоянные метки не меняют своего значения до конца алгоритма.
Кроме метки M * (v j ) с каждой вершиной v j V (за исключением
начальной вершины) связывают еще одну метку (v j ) . На каждом шаге метка
(v j ) является номером вершины, предшествующей vj на (v0…vj)min маршруте,
имеющем минимальный вес среди всех (v0…vj) маршрутов, проходящих через
вершины, получивших к данному шагу постоянные метки. После того, как
оконечная вершина маршрута vk получила окончательную метку M * (v j ) , с
помощью меток (v j ) легко указать последовательность вершин в кратчайшем
маршруте можно использовать следующую рекуррентную процедуру: если
вершина v j 1 непосредственно предшествует v j в кратчайшем (v0…vj)min маршруте, то для неѐ выполняется соотношение
M*(vj-1) + L (vj-1,vj) = M*(vj)
(1)
На подготовительном (нулевом) шаге начальной вершине
v0
*
присваивается окончательная метка M (v0) = 0, а всем остальным вершинам vj
(j=1,2,..n) - временные метки M(vj) = .
Общий i-й шаг состоит в следующем.
38
Вершину vj , получившую постоянную метку M*i-1(vj) на предыдущем
шаге будем обозначать pi-1=vj . Вершины, являющиеся образами вершины pi-1 ,
будем обозначать v
.
i ( pi 1 )
Вершины v
имеют временные метки. Для них производится
i ( pi 1 )
пересчет меток в соответствии с формулой
Mi(v)=min{Mi-1(v),M*i-1(pi-1) + L(pi-1,v)},
(2)
где L(pi-1,v) – веса дуг, соединяющих вершину pi-1, получившую
окончательную метку на предыдущем шаге, с еѐ «детьми» v
( pi 1 ) .
i
Метки остальных вершин остаются без изменений.
Среди всех вершин с временными метками находится вершина
имеющая минимальную метку
M(v*)=min{M(v)|v V’i-1}
v*,
(3)
На каждом шаге определяется множество вершин V*i, получивших
окончательные метки, V’I – множество вершин, имеющих временные метки.
Метка вершины v* считается постоянной и принимается pi=v*.
Тогда
V*i = Vi-1 {v*}; V*i = V‘i-1\{v*}
(4)
Поиск минимального маршрута заканчивается, когда vk получает
окончательную метку M(v*) – вес кратчайшего (v0…vk)min – маршрута.
Этот маршрут определяется с помощью меток
(v0 ,..., v k )min
где
m
(v k )
(v0 ,..,
3
(v k ),
2
(v j ) :
(v k ), (v k ), v k ) , (5)
( (... ( v k )...))
- для любой вершины графа.
m раз
3.1.1 Формальное описание алгоритма
1.Положить M*(v0)=0 и считать эту метку постоянной.
Положить Mj(vj)= для всех vj V, vj vi; V0*={v0}; V’0={v1, v2,..,vn}.
2. Для всех v
формуле (6):
i
(pi 1 ) с временными метками пересчитать метки по
Mi(v)=min{Mi-1(v),M*i-1(pi-1) + L(pi-1,v)},
3. Множество вершин с временными метками Vi-1=Vi/{v}.
Среди вершин с временными метками vj Vi-1 найти такую v*, что Mi(v*) =
min (Mi(v)).
Считать метку M*i(v*) постоянной
Присвоить pi=v*. V*i = Vi-1 {v*};
V*i = V‘i-1\{v*}.
39
4. Если pi=vk, то перейти к п.5.
5. Кратчайший маршрут определяется метками :
(v0 ,..., v k )min
3
(v0 ,..,
2
(v k ),
(v k ), (v k ), v k ) .
3.1.2 Решение задачи вручную
Конфигурация взвешенного графа приведена на рисунке.
v4
3
6
v1
5
1
v8
2
v3
v5
7
1
1
v2
1
4
v7
1
3
1
v6
2
Задаем начальную и конечные вершины:
v0 : v1 ;
vk : v8 ;
Записываем матрицу весов дуг:
v1
v2
v3 v4
v1 0
1
5
v2
0
1
0
v3
v4
v7
v8
1
v7
v8
6
2
2
7
0
1
0
v5
v6
v5 v6
3
2
0
4
3
0
1
0
40
3.1.3 Определение таблицы минимальных путей
0)
v1
v2
v3
v4
v5
v6
v7
v8
0
*
p
1)
v1
Г (v1 ) {v2 , v3 , v4 }
M (v2 ) min(M (v2 ), M * (v1 ) L(v1, v2 ) ) min( , 0
1) 1
M (v3 ) min(M (v3 ), M * (v1 ) L(v1, v3 ) ) min( , 0
5) 5
M (v4 ) min(M (v4 ), M * (v1 ) L(v1 , v4 ) ) min( , 0
6) 6
M * (v) min(M (v2 ), M (v3 ), M (v4 )) min(1,5,6) 1
v v2
p v2
v1
v2
v3 v4
0
1
5
*
*
v5
v6
v7
v8
v7
v8
6
2 ) Г (v2 ) {v3 , v7 }
M (v3 ) min(M (v3 ), M * (v2 ) L(v2 , v3 ) ) min(5, 1 1) 2
M (v7 ) min(M (v7 ), M * (v2 ) L(v2 , v7 ) ) min( , 1
M * (v) min(M (v3 ), M (v7 )) min(2,3) 2
2) 3
v v3
p v3
v1
v2
v3 v4
0
1
2
*
*
*
v5
v6
6
3
3 ) Г (v3 ) {v4 , v5}
M (v4 ) min(M (v4 ), M * (v3 ) L(v3 , v4 ) ) min(6, 2
2) 4
M (v5 ) min(M (v5 ), M * (v3 ) L(v3 , v5 ) ) min(6, 2
7) 6
M * (v) min(M (v4 ), M (v5 )) min(4,6) 4
v v4
41
p v4
v1
v2
v3 v4
v5 v6
v7
0
1
2
4
6
3
*
*
*
*
v8
4 ) Г (v4 ) {v5 , v8}
M (v5 ) min(M (v5 ), M * (v4 ) L(v4 , v5 ) ) min(6, 4
1) 5
M (v8 ) min(M (v8 ), M * (v4 ) L(v4 , v8 ) ) min( , 4
3) 7
M * (v) min(M (v5 ), M (v8 )) min(5,7) 5
v v5
p v5
v1
v2
v3 v4
v5 v6
v7
v8
0
1
2
4
5
3
7
*
*
*
*
*
5 ) Г (v5 ) {v6 , v8}
M (v6 ) min(M (v6 ), M * (v5 ) L(v5 , v6 ) ) min( , 5
1) 6
M (v8 ) min(M (v8 ), M * (v5 ) L(v5 , v8 ) ) min(7, 5
4) 7
M * (v) min(M (v5 ), M (v8 )) min(6,7) 6
v v6
p v6
v1
v2
v3 v4
v5 v6
v7
v8
0
1
2
4
5
6
3
7
*
*
*
*
*
*
6 ) Г (v6 ) {v7 }
M (v7 ) min(M (v7 ), M * (v6 ) L(v6 , v7 ) ) min(3, 6
3) 3
p v7
v1
v2
v3 v4
v5 v6
v7
v8
0
1
2
4
5
6
3
7
*
*
*
*
*
*
*
5 ) Г (v7 ) {v8}
42
M (v8 ) min(M (v8 ), M * (v7 ) L(v7 , v8 ) ) min(7, 3
1) 4
p v8
v1
v2
v3 v4
v5 v6
v7
v8
0
1
2
4
5
6
3
4
*
*
*
*
*
*
*
*
43
3.1.4 Определение минимального пути методом «отката»
0) Path(v1v8 ) {v8}
1) P(v8 ) {v4 , v5 , v7 }
M * (v4 ) L(v4 , v8 ) 4 3 (7 4)
M * (v5 ) L(v5 , v8 ) 5 4 (9 4)
M * (v7 ) L(v7 , v8 ) 3 1 (4 4) => Path(v1v8 ) {v7 , v8 }
2) P(v7 ) {v2 , v6 }
M * (v2 ) L(v2 , v7 ) 1 2 (3 3) => Path(v1v8 ) {v2 , v7 , v8 }
M * (v6 ) L(v6 , v7 ) 6 3 (9 3)
3) P(v2 ) {v1}
M * (v1 ) L(v1 , v2 ) 0 1 (1 1) => Path(v1v8 ) {v1 , v2 , v7 , v8 }
Ответ:
Path(v1v8 ) {v1 , v2 , v7 , v8 }
44
3.1.5 Программирование
{Find way with minimum length}
uses CRT, mStack, TextScr, Graphs;
программы
// Эти модули нужны для работы
// Модуль CRT предназначен для работы с экраном монитора (Паскалевский)
// Модуль mSack содержит описание и реализацию класса Stack
// Модуль TextScr содержит ряд сервисных функций
// Модуль Graphs содержит описание некоторых типов
var
head, position : ElementPosition;
SizeMatrix : NumberTop;
MinPath, Child, Parent: stack;
Metka : array [1..MaxNumberTop] of WeightValue;
Flag : array [1..MaxnumberTop] of 0..2 ;
{
Flag Value
-------------------------------------------------------------------------------------------------------0 – вершина ни разу не рассматривалась
1 – вершина рассматривалась, но метку не получила
2 – вершина рассматривалась и получила метку
--------------------------------------------------------------------------------------------------------}
MatrixWeight : array [1..MaxNumberTop,1..MaxNumberTop] of WeightValue;
summa
: WeightValue;
mother, dother: TopValue;
45
start_top, finish_top : TopValue;
newtop, index, top : TopValue;
procedure DisableNegativeWeights(weight:WeightValue);
// Эта процедура предназначена для проверки веса на отрицательность
// Если обнаружиться, что пользователь ввел отрицательный вес – программа
прервется
// Возвратив операционной системе 1.
begin
if weight<0 then
begin
writeln;
Writeln('Negative weights is prohibition.');
Halt(1);
end;
end;
procedure Input_MatrixWeight_for_Orgraph(SizeMatrix:NumberTop);
// Эта процедура для ввода орграфа.
var i,j : ElementPosition;
begin
writeln;
Writeln('Input elements of matrix weight.');
writeln;
for i:=1 to SizeMatrix do
for j:=1 to SizeMatrix do
if i=j
then
MatrixWeight[i,j]:=0
// Диагональные элементы всегда нулевые
else
begin
Write('[ ',i,' ,',j,' ] = ');
46
Readln(MatrixWeight[i,j]);
DisableNegativeWeights(MatrixWeight[i,j]); // Проверка на отрицательность
OutputIgnore; // Стирает строку вывода
end;
OutputIgnore;
OutputIgnore;
end;
procedure
Input_MatrixWeight_for_Graph(SizeMatrix:NumberTop);
var i,j: ElementPosition;
begin
writeln;
Writeln('Input elements of matrix weight.');
writeln;
for i:=1 to SizeMatrix do
for j:=i to SizeMatrix do
if i=j
then
MatrixWeight[i,j]:=0 // Диагональные элементы всегда нулевые
else
begin
Write('[ ',i,' ,',j,' ] = ');
Readln(MatrixWeight[i,j]);
DisableNegativeWeights(MatrixWeight[i,j]);
OutputIgnore;
MatrixWeight[j,i]:=MatrixWeight[i,j]; // Помощь Userу
end;
OutputIgnore;
OutputIgnore;
end;
47
procedure RecognitionGraph;
// Распознавание вида графа
var UserAnsver: char;
begin
Write('You want to enter Orgraph [Y(yes)/N(no)]? ');
Readln(UserAnsver);
writeln;
UserAnsver:=UpCase(UserAnsver);
case UserAnsver of
'N': Input_MatrixWeight_for_Graph(SizeMatrix);
'Y': Input_MatrixWeight_for_Orgraph(SizeMatrix);
else
begin
writeln;
Writeln('Wrong entering.');
Halt(1);
end;
end;
end;
procedure GetChild(var Childrens: stack; mother:TopValue);
// Эта процедура вычисляет и сохраняет для каждой вершины
// дочерние вершины
{Rows Analis}
var j : ElementPosition;
var head: Elementposition;
begin
Childrens.InitStack ;
for j:=1 to SizeMatrix do
if (MatrixWeight[mother,j]<>0)and(flag[j]<>2)
then Childrens.Push(j);
begin
48
head := Childrens.GetHead;
if head=0 then
begin
writeln('Error: Net Potomkov'); // На всякий случай
halt(1);
end;
end;
end;
procedure GetParents(var Parents:stack; dother:Topvalue);
// Процедура вычисляет и запоминает для каждой вершины
// родительские вершины
{Columns Analis}
var j : ElementPosition;
var head : ElementPosition;
begin
Parents.InitStack; // Сброс стека
for j:=1 to SizeMatrix do
if (MatrixWeight[j,dother]<>0) and (flag[j]<>2)
then Parents.Push(j); // Засунуть элемент в стек
begin
head := Parents.GetHead; // Получить голову стека
if head=0 then
begin
writeln('Error: Nety Predkov'); // Вдруг Это случиться..?
halt(1);
end;
end;
end;
{----------------------------------}
procedure PrintMinPath(MinPath:stack);
49
// Название процедуры говорит само за себя.
var head:ElementPosition;
begin
Write('Path with minimum weight = ');
repeat
Write(' ',MinPath.Pop);
head:=MinPath.GetHead; // Получить голову стека
until head=0;
writeln;
end;
Begin
{/////////////////////////////////////////}
clrscr;
Writeln('Welcome to program Dijkstra');
writeln;
InsertLineSymbvols('='); // Название говорящее
writeln;
Writeln('You must input matrix weght.');
writeln;
Writeln('To input infinity value enter 0.');
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('Point size matrix of weight.');
writeln;
Write('Matrix size = ');
Readln(SizeMatrix);
writeln;
writeln;
50
RecognitionGraph;
writeln;
Writeln('Input start top.');
writeln;
Write('Start top = ');
Readln(start_top);
writeln;
Writeln('Input finish top.');
writeln;
Write('Finish top = ');
Readln(finish_top);
writeln;
{************************
Помечивание
*******************************}
всех
вершин
mother:=start_top;
Metka[mother]:=0;
Flag[mother]:=2;
repeat
GetChild(Child,mother);
{
***************
Пересчет
********************************}
временных
меток
head:=Child.GetHead;
for position:=1 to head do
begin
51
top:=Child.GetStackValue(position);
summa:=Metka[mother]+MatrixWeight[mother,top];
if (Metka[top]>summa) or (flag[top]=0) then Metka[top]:=summa;
end;
flag[top]:=1; {Now top is Not virges}
{**********Получение постоянной
«материнской» вершины****}
метки,
вычисление
очередной
if head=1 then top:=Child.GetStackValue(1)
else
begin
top:=Child.GetStackValue(1);
for position:=2 to head do
begin
newtop:=Child.GetStackValue(position);
if Metka[newtop]<Metka[top] then top:=newtop;
end;
end;
flag[top]:=2;
mother:=top;
until flag[finish_top]=2;
{****************
Откат
–
******************************}
определение
минимального
пути
dother:=finish_top;
MinPath.InitStack;
MinPath.Push(dother);
52
{Reset Flag}
for position:=1 to SizeMatrix do flag[position]:=0;
flag[dother]:=2; {Init flag}
while dother<>start_top do
begin
GetParents(Parent,dother);
head:=Parent.GetHead;
for position:=1 to head do
begin
index:=Parent.GetStackValue(position);
summa:=Metka[index]+MatrixWeight[index,dother];
if summa=Metka[dother] then
begin
dother:=index;
flag[dother]:=2;
MinPath.Push(dother);
end;
end;
end;
PrintMinPath(MinPath);
writeln;
Writeln('Legth of the path with minimum weitgh : ',Metka[finish_top]:3:5);
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('The program was terminated.');
writeln;
Writeln('Press Enter...');
53
readln;
{//////////////////////////////////////////////////////}
End.
3.1.6
Результаты работы программы
Welcome to program Dijkstra
=============================================================
==============
You must input matrix weght.
To input infinity value enter 0.
=============================================================
=============
Point size matrix of weight.
Matrix size = 8
You want to enter Orgraph [Y(yes)/N(no)]? y
Input start top.
Start top = 1
Input finish top.
Finish top = 8
Path with minimum weight = 1 2 7 8
Lengths of the path with minimum weight: 4.00000
=================================================
The program was terminated.
Press Enter...
Вывод: в данном разделе пособия мы познакомились с алгоритмом поиска
минимального пути в нагруженном графе. Этот алгоритм, по сути, является
оптимизационным и позволяет минимизировать затраты, которые мы
ассоциировали с прохождением по дуге заданного веса.
54
3.2
Метод Флойда
3.2.1 Теоретическая часть
Метод Флойда позволяет найти кратчайшие пути между всеми парами
вершин графа.
Пусть G(V,X) [D(V,R)] – нагруженный граф (орграф), содержащий n
вершин, для которого задана матрица весов ребер (дуг):
С(G) = [cij] - n n размера.
c( v i , v j ), v i v j
R
;
cij
,
viv j
R
С(vi,vj) – вес дуги, соединяющей вершину vi с vj. На графе допускаются
отрицательные
весы дуг, однако не допускается наличие циклов
отрицательного веса.
Дуги, имеющие отрицательные весы cij < 0, можно рассматривать как
приносящие некоторый доход при их прохождении. Если сij
0
(положительный вес), то прохождение по этой дуге связанно с затратами.
Обозначим Vm={v1, v2,…,vm} – множество первых вершин графа (m n).
Длину кратчайшего пути из вершины vi в vj, содержащего в качестве
промежуточных только вершины из множества Vm, обозначим lij(m). Если
между вершинами vi в vj не существует ни одного указанного пути, то будем
считать, что lij(m) = .
Пусть известны:
1) кратчайший путь из вершины vi в вершину vj, который в качестве
промежуточных содержит только вершины из множества Vm-1;
вершины vm Vm ;
2) кратчайший путь из вершины vm в вершину vj, который в качестве
промежуточных также содержит вершины из множества Vm-1
3) кратчайший путь из вершины vi в вершину vj , проходящей как и два
предыдущих только через вершины множества Vm-1.
Объединяя все три пути, получим путь <vi vj>, проходящей через вершину
vm.
Объединяя все три пути, получим цикл в исходном графе. Так как по
условию исходный граф не может содержать циклов отрицательного веса, один
из двух путей <vi vj> или <vj vi> должен быть более коротким (в крайнем
случае, они могут быть равны).
Более короткий из этих путей является условно кратчайшим путем из
вершины vi в vj, в которых в качестве промежуточных используются только
вершины из множества Vm.
Таким образом, выполняется соотношение
55
lij(m)=min{ lij(m-1), lim(m-1) + lmj(m-1) }
Очевидно, что lij(m) определяют верхние границы для длин кратчайших
путей.
По мере расширения множества Vm значения lij(m) могут уменьшаться,
пока не достигнут минимума. Уменьшение lij(m) связано с выделением более
коротких путей, ранее не учитываемых.
Введем обозначение матрицы Lm=[ lij(m)]n*n.
3.2.2 Формальное описание алгоритма
1. Подготовительный шаг Определить матрицу L0, положив величину
каждого еѐ элемента lij(0) , равной длине дуги, соединяющей вершину vi c
вершиной vj: lij(0)=c(vi,vj) – вес дуги.
2. Общий шаг (m-й шаг) ( m 1, n ).
По матрице Lm-1 определить матрицу Lm, используя рекуррентное
соотношение (10).
Диагональные элементы пересчитывать не нужно, так как lii(m)=0.
Кроме того, при определении матрицы Lm нет необходимости в пересчете
элементов m-ой строки и m-го столбца, так как вершина vm не может служить в
качестве промежуточной для путей, или заканчивающихся в ней самой.
По окончанию данного алгоритма (на шаге n) матрица Lm=[ lij(n)]
определяет длины кратчайших путей, ведущих из вершины Vi(i=1,n) в вершины
Vj(i j= 1, n ).
Для определения самых кратчайших путей наряду с матрицей весов
используется матрица путей Pm=[pij(m)].
в Vj.
Элемент pij(m) указывает номер второй вершины на кратчайшем пути из Vi
В начале выполнения алгоритма помечаем:
pij
J , lij
( 0)
0, lij
(0)
(11)
( 0)
На m-м шаге каждый раз при использовании соотношения (10)
проверяется, какие из вершин l(m-1) или lim(m-1) + lmj(m-1) меньше.
Если меньше оказывается вторая из этих величин, то полагается pij(m) =
pim(m-1). В противном случае pij(m) = pij(m) , т.е. соответствующий элемент
не меняется.
Эти условия можно записать так:
pij
( m)
pim
pij
( m 1)
( m 1)
, lim
, lij
( m 1)
( m 1)
lmj
lim
( m 1)
( m 1)
lij
lmj
( m 1)
( m 1)
56
После окончания алгоритма кратчайшие пути могут быть получены
непосредственно из заключительной матрицы Pn.
3.2.3 Пример решения задачи
С помощью алгоритма Флойда определить кратчайшие пути между вершинами
нагруженного орграфа, заданного схемой.
Граф задания:
v5
3
3
3
3
4
3
3
v1
v4
1
3
6
5
3
3
v3
3
3
2
4
v2
Примечание:
1. символ $ означает бесконечность.
3. в левой части выражения всегда имеют индекс предыдущего шага.
4. в скобках указываем шаг.
5. некоторые формулы, для удобства, переписаны.
(m=0)
0 3 $ $ 4
1 2 0 0 5
5 0 2 $ $
D0
$ 4 0 1 $
$ $ 3 0 3
1 2 3 0 0
,
3 6 $ 3 0
P0
0 2 3 4 0 .
0 0 3 4 5
1 2 0 4 5
//============================================
(m=1).
Определяем матрицу весов:
l23 = min(l23;l21+l13) = min(2;5+$) = 2 ;
l24 = min(l24;l21+l14) = min($;5+$)=$;
57
l25 = min(l25;l21+l15) = min($;5+4)=9;
l32 = min(l32;l31+l12) = min(4;$+3) = 4;
l34 = min(l34;l31+l14) = min(1; $ + $) = 1;
l35 = min(l35;l31+l15) = min($;$+4) = $;
l42 = min(l42;l41+l12) = min($;$+3) = $;
l43 = min(l43;l41+l13) = min(3;$+$) = 3;
l45 = min(l45;l41+l15) = min(3;$+4) = 3;
l52 = min(l52;l51+l12) = min(6;3+3) = 6;
l53 = min(l53;l51+l14) = min(3;3+$) = 3.
0 3 $ $ 4
5 0 2 $ 9
D1
$ 4 0 1 $
$ $ 3 0 3
3 6 $ 3 0
Определяем матрицу путей:
p23 = (l23 <= l21+l13)?p23:p21 = (2 <= 5+$)?3:1 = 3;
p24 = (l24 <= l21+l14)?p24:p21 = ($ <= 5+$)?0:1 = 0;
p25 = (l25 <= l21+l15)?p25: p21 = ($ <= 5+4)?0:1=1;
p32 = (l32 <= l31+l12)?p32:p31 = (4 <= $)?2:0 = 2;
p34 = (l34 <= l31+l14)?p34:p31 = (1<=$)?4:0 = 4;
p35 = (l35 <= l31+l15)?p35:p31 = ($<=$)?0:0 = 0;
p42 = (l42 <= l41+l12)? p42:p41 = ($<=$)?0:0 = 0;
p43 = (l43 <= l41+l13)?p43:p41 = (3<=$)?3:0 = 3;
p45 = (l45 <= l41+l15)?p46:p41 = (3<=$)?5:0 = 5;
p52 = (l52 <= l51+l12)? p52:p51 = (6<=6)?2:1 = 2;
p53 = (l53 <= l51+l13)?p53:p51 = ($<=$)?0:1 = 0;
p54 = (l54 <= l51+l14)?p54:p51 = (3<=$)?4:1=4.
1 2 0 0 5
1 2 3 0 1
P1
0 2 3 4 0
0 0 3 4 5
1 2 0 4 5
//=====================================
(m = 2)
Определяем матрицу весов:
58
l12 = min(l12;l12+l22) = min(3;3+0) = 3;
l13 = min(l13;l12+l23) = min($;3+2) = 5;
l14 = min(l14;l12+l24) = min($;3+$) = $;
l15 = min(l15;l12+l25) = min(4;3+9) = 4;
l31 = min(l31;l32+l21) = min($;4+5) = 9;
l34 = min(l34;l32+l24) = min(1;4+$) = 1;
l35 = min(l35;l32+l25) = min($;4+9) = 13;
l41 = min(l41;l42+l21) = min($;$+5) = $;
l42 = min(l42;l42+l22) = min($;$+0) = $;
l43 = min(l43;l42+l23) = min(3;$+2) = 3;
l45 = min(l45;l42+l25) = min(3;$+9) = 3;
l51 = min(l51;l52+l21) = min(3;6+5) = 3;
l53 = min(l53;l52+l23) = min($;6+2) = 8;
l54 = min(l54;l52+l24) = min(3;6+$) = 3.
0 3 5 $
5 0 2 $
D2
4
9
9 4 0 1 13
$ $ 3 0 3
3 6 8 3
0
Определяем матрицу путей:
p14 = (l12 <= l12 + l22)?p12:p12 = 2;
p13 = (l13 <= l12 + l23)?p13:p12 = ($<=5)?0:2 = 2;
p14 = (l14 <= l12 + l24)?p14:p12 = ($<=$)?0:2 = 0;
p15 = (l15 <= l12 + l25)?p15:p12 = (4<=12)?5:2 = 5;
p31 = (l31 <= l32 + l21)?p31:p32 = ($<=9)?0:2=2;
p34 = (l34 <= l32 + l24)?p34:p32 = (1<=$)?4:2 = 4;
p35 = (l35 <= l32+l25)?p35:p32 = ($<=13)?0:2 = 2;
p41 = (l41 <= l42+l21)?p41:p42 = ($<=$)?0:0 = 0;
p43 = (l43 <= l42+l23)?p43:p42 = (3<=$)?3:0 = 3;
p45 = (l45 <= l42+l25)?p45:p42 = (3<=$)?5:0 = 5;
p51 = (l51 <= l52+l21)?p51:p52 = (3<=11)?1:2 = 1;
p53 = (l53 <= l52+l23)?p53:p52 = ($<=8)?0:2 =2 ;
p54 = (l54 <= l52+l24)?p54:p52 = (3<=$)?4:2 =4 .
59
1 2 2 0 5
1 2 3 0 1
P2
2 2 3 4 2
0 0 3 4 5
1 2 2 4 5
//====================================
(m = 3)
Определяем матрицу весов:
l12 = min(l12;l13+l32) = min(3;5+4) = 3;
l14 = min(l14;l13+l34) = min($;5+1) = 6;
l15 = min(l15;l13+l35) = min(4;5+13) = 4;
l21 = min(l21;l23+l31) = min(5;2+9) = 5;
l24 = min(l24;l23+l34) = min($;2+1) = 3;
l25 = min(l25;l23+l35) = min(9;2+13) = 9;
l41 = min(l41;l43+l31) = min($;3+9) = 12;
l42 = min(l42;l43+l32) = min($;3+4) = 7;
l45 = min(l45;l43+l35) = min(3;3+13) = 3;
l51 = min(l51;l53+l31) = min(3;8+9) = 3;
l52 = min(l52;l53+l32) = min(6;8+4) = 6;
l54 = min(l54;l53+l34) = min(3;8+1) = 3.
0
5
D3
3 5 6
0 2 3
4
9
9 4 0 1 13
12 7 3 0 3
3
6 8 3
0
Определяем матрицу путей:
p12 = (l12<=l13+l32)?p12:p13 =(3<=9)?2:2=2;
p14 = (l14<=l13+l34)?p14:p13 =($<=6)?0:2=2;
p15 = (l15<=l13+l35)?p15:p13 =(4<=18)?5:2=5;
p21 = (l21<=l23+l31)?p21:p23 =(5<=11)?1:3=1;
p24 = (l24<=l23+l34)?p24:p23 = ($<=3)?0:3=3;
p25 = (l25<=l23+l35)?p25:p23 = (9<=15)?1:3=1;
p41 = (l41<=l43+l31)?p41:p43 = ($<=12)?0:3=3;
p42 = (l42<=l43+l32)?p42:p43 = ($<=7)?0:3=3;
p45 = (l45<=l43+l35)?p45:p43 = (3<=16)?5:3=5;
60
p51 = (l51<=l53+l31)?p51:p53 = (3<=17)?1:2=1;
p52 = (l52<=l53+l32)?p52:p53 = (6<=12)?2:2=2;
p54 = (l54<=l53+l34)?p54:p53 = (3<=9)?4:2=4.
1 2 2 2 5
1 2 3 3 1
P3
2 2 3 4 2
3 3 3 4 5
1 2 2 4 5
//=====================================
(m = 4)
l12 = min(l12;l14+l42) = min(3;6+7) = 3;
l13 = min(l13;l14+l43) = min(5;6+3) = 5;
l15 = min(l15;l14+l45) = min(4;6+3) = 4;
l21 = min(l21;l24+l41) = min(5;3+12) = 5;
l23 = min(l23;l24+l43) = min(2;3+3) = 2;
l25 = min(l25;l24+l45) = min(9;3+3) = 6;
l31 = min(l31;l34+l41) = min(9;1+12) = 9;
l32 = min(l32;l34+l42) = min(4;1+7) = 4;
l35 = min(l35;l34+l45) = min(13;1+3) = 4;
l51 = min(l51;l54+l41) = min(3;3+12) = 3;
l52 = min(l52;l54+l42) = min(6;3+7) = 6 ;
l53 = min(l53;l54+l43) = min(8;3+3) = 6 .
0
5
D4
3 5 6 4
0 2 3 6
9 4 0 1 4
12 7 3 0 3
3
6 6 3 0
Определяем матрицу путей:
p12 = (l12<=l14+l42)?p12:p14 = (3<=13)?2:2=2;
p13 = (l13<=l14+l43)?p13:p14 = (5<=9)?2:2=2;
p15 = (l15<=l14+l45)?p15:p14 = (4<=9)?5:2=5;
p21 = (l21<=l24+l41)?p21:p24 = (5<=15)?1:3 = 1;
p23 = (l23<=l24+l43)?p23:p24= (2<=6)?3:3 = 3;
p25 = (l25<=l24+l45)?p25:p24= (9<=6)?1:3 =3;
p31 = (l31<=l34+l41)?p31:p34 = (9<=13)?2:4 = 2;
61
p32 = (l32<=l34+l42)?p32:p34 = (4<=8)?2:4 = 2;
p35 = (l35<=l34+l45)?p35:p34 = (13<=4)?2:4 =4 ;
p51 = (l51<=l54+l41)?p51:p54 = (3<=15)?1:4=1;
p52 = (l52<=l54+l42)?p52:p54 = (6<=10)?2:4=2;
p53 = (l53<=l54+l43)?p53:p54 = (8<=6)?2:4=4.
1 2 2 2 5
1 2 3 3 3
P4
2 2 3 4 4
3 3 3 4 5
1 2 4 4 5
//=====================================
(m = 5)
Определяем матрицу весов:
l12 = min(l12;l15+l52) = min(3;4+6) = 3;
l13 = min(l13;l15+l53) = min(5;4+6) = 5;
l14 = min(l14;l15+l54) = min(6;4+3) = 6;
l21 = min(l21;l25+l51) = min(5;6+3) = 5;
l23 = min(l23;l25+l53) = min(2;6+6) = 2;
l24 = min(l24;l25+l54) = min(3;6+3) = 3;
l31 = min(l31;l35+l51) = min(9;4+3) = 7;
l32 = min(l32;l35+l52) = min(4;4+6) = 4;
l34 = min(l34;l35+l54) = min(1;4+3) = 1;
l41 = min(l41;l45+l51) = min(12;3+3) = 6 ;
l42 = min(l42;l45+l52) = min(7;3+6) = 7 ;
l43 = min(l43;l45+l53) = min(3;3+6) = 3 .
0 3 5 6 4
5 0 2 3 6
D5
7 4 0 1 4
6 7 3 0 3
3 6 6 3 0
Определяем матрицу путей:
p12 = (l12<=l15+l52)?p12:p15 = (3<=10)?2:5 = 2;
p13 = (l13<=l15+l53)?p13:p15 = (5<=10)?2:5 = 2;
p14 = (l14<=l15+l54)?p13:p15 = (6<=7)?2:5 = 2;
p21 = (l21<=l25+l51)?p21:p25 = (5<=9)?1:3 = 1;
p23 = (l23 <= l25 + l53)?p23:p25 = (2<=12)?3:3 = 3;
p24 = (l24<=l25+l54)?p24:p25 = (3<=9)?3:3 = 3;
62
p31 = (l31<=l35+l51)?p31:p35 = (9<=7)?2:4 =4 ;
p32 = (l31<=l35+l52)?p32:p35 = (4<=10)?2:4 = 2;
p34 = (l34<=l35+l54)?p34:p35 = (1<=7)?4:4 = 4;
p41 = (l41<=l45+l51)?p41:p45 = (12<=6)?3:5 =5;
p42 = (l42<=l45+l52)?p42:p45 = (7<=9)?3:5 =3;
p43 = (l43<=l45+l53)?p43:p45 = (3<=9)?3:5 =3.
1 2 2 2 5
1 2 3 3 3
P5
4 2 3 4 4
5 3 3 4 5
1 2 4 4 5
Используя последнее значение матрицы путей, вычисляем минимальные пути:
В скобках указана длина пути, она определяется по матрице весов.
v1-v2 : v1v2 - [3]
v1-v3 : v1v2 v3 - [5]
v1-v4 : v1v2 v3 v4 – [6]
v1-v5 : v1v5 - [4]
v2-v1 : v2v1 - [5]
v2-v3 : v2v3 - [2]
v2-v4 : v2v3 v4 - [3]
v2-v5 : v2v3 v4 v5 - [6]
v3-v1 : v3v4 v5v1 – [7]
v3-v2 : v3v2 - [4]
v3-v4 : v3v4 - [1]
v3-v5 : v3v4 v5 - [4]
v4-v1 : v4v5v1 – [6]
v4-v2 : v4v3v2 – [7]
v4-v3 : v4v3 – [3]
v4-v5 : v4v5 – [3]
v5-v1: v5v1 – [3]
v5-v2: v5v2 – [6]
v5-v3: v5 v4v3 – [6]
v5-v4: v5v4 – [3].
3.2.4 Программирование
uses CRT, TextScr, Graphs;
type MatrixValue = word;
63
type matrix = array [1..MaxNumberTop,1..MaxNumberTop] of MatrixValue;
var
MatrixPath : matrix;
MatrixWeight : matrix;
m,i,j : ElementPosition;
x,y,z,p1,p2 : MatrixValue;
SizeMatrix : NumberTop ;
{----------------------Proc & Fun ----------------}
function Sum_with_Inf (a,b:MatrixValue):MatrixValue;
// Эта функция позволяет сложить два числа
// При условии, что 0 ассоциирован с бесконечностью
begin
if (a=0) or (b=0)
then Sum_with_Inf:=0
else Sum_with_Inf:=a+b;
end;
function NewElementMatrixPath (x,y,z,p1,p2: MatrixValue):MatrixValue;
// Эта функция вычисляет новый элемент матрицы путей
// Здесь практически дословно запрограммирована формула.
var d: MatrixValue;
begin
d:=Sum_with_Inf(y,z);
if (x<=d) and (x<>0) or (d=0)
then NewElementMatrixPath := p1
else NewElementMatrixPath := p2;
end;
function NewElementMatrixWeight (x, y, z : MatrixValue) : MatrixValue;
// Эта функция вычисляет новое значение матрицы весов.
var d: MatrixValue;
begin
d:=Sum_with_Inf(y,z);
if (x<=d) and (x<>0) or (d=0)
then NewElementMatrixWeight := x
else NewElementMatrixWeight := d;
64
end;
procedure InputMatrixWeight;
var i,j : ElementPosition;
begin
writeln;
Writeln('Input elements of matrix weight.');
writeln;
for i:=1 to SizeMatrix do
for j:=1 to SizeMatrix do
if i=j
then
MatrixWeight[i,j]:=0
else
begin
Write('[ ',i,' ,',j,' ] = ');
Readln(MatrixWeight[i,j]);
OutputIgnore;
end;
OutputIgnore;
OutputIgnore;
end;
procedure MakeMatrixPath(mWeight:matrix;var mPath:matrix);
// Эта процедура служит для получения матрицы путей
// по матрице весов, таким образом, отпадает необходимость еѐ вводить
var
i,j: ElementPosition;
begin
for i:=1 to SizeMatrix do
for j:=1 to SizeMatrix do
if (mWeight[i,j]<>0) or (i=j) then mPath[i,j]:=j
else mPath[i,j]:=0;
end;
procedure Print_all_paths(MatrixPath:matrix);
// Эта процедура выводит для каждой пары разных вершин
// минимальный путь и его величину.
var
i, j : ElementPosition;
ot, d0 : ElementPosition;
Prow, Pcolumn : ElementPosition;
WeightPath : MatrixValue;
65
begin
for i:=1 to SizeMatrix do
for j:=1 to SizeMatrix do
begin
WeightPath := 0;
if i<>j then
begin {i}
Write(i,' - ',j,' : ');
Prow:= i;
Pcolumn:=j;
Write(' ',Prow);
repeat
begin{w}
ot := Prow;
Prow := MatrixPath[Prow,Pcolumn];
d0 := Prow ;
WeightPath := WeightPath + MatrixWeight [ot,d0] ;
write(' ',Prow);
end;{/w}
until Prow=j;
Write(' >> ',WeightPath);
end;{/i}
writeln;
end;
end;
{------------------Proc & Fun ---------------------------}
Begin
clrscr;
Writeln('Welcome to program Floid');
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('Point size of matrix weight.');
writeln;
Write('Matrix size = ');
Readln(SizeMatrix);
writeln;
66
InputMatrixWeight;
MakeMatrixPath(MatrixWeight,MatrixPath);
for m:=1 to SizeMatrix do
begin
for i:=1 to SizeMatrix do
for j:=1 to SizeMatrix do
begin
if (i<>j) and (i<>m) and (j<>m) then
begin
x:=MatrixWeight[i,j];
y:=MatrixWeight[i,m];
z:=MatrixWeight[m,j];
p1:=MatrixPath[i,j];
p2:=MatrixPath[i,m];
{***********
Выполняем
*****************************}
пересчет
по
формуле
MatrixWeight [i,j] := NewElementMatrixWeight (x,y,z);
MatrixPath [i,j] := NewElementMatrixPath (x,y,z,p1,p2);
end;
end;
end;
Writeln('All paths with minimum weights: ');
writeln;
Print_all_paths(MatrixPath);
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('The program was terminated.');
writeln;
Writeln('Press Enter...');
readln;
End.
67
3.2.5 Результат работы программы
2-3:
2-4:
2-5:
3-1:
3-2:
2 3 >> 2
2 3 4 >> 3
2 3 4 5 >> 6
3 4 5 1 >> 7
3 2 >> 4
3-4:
3-5:
4-1:
4-2:
4-3:
3 4 >> 1
3 4 5 >> 4
4 5 1 >> 6
4 3 2 >> 7
4 3 >> 3
4-5:
5-1:
5-2:
5-3:
5-4:
4 5 >> 3
5 1 >> 3
5 2 >> 6
5 4 3 >> 6
5 4 >> 3
=============================================
The program was terminated.
Press Enter...
Вывод: в данном разделе мы познакомились с алгоритмом Флойда. Этот
алгоритм оптимизационный, он позволяет определить минимальные расстояния
между всеми парами вершин графа и минимальные пути, соединяющие эти
вершины.
68
Метод Форда-Фолкерсона (Ford-Falkerson)
3.3
3.3.1 Теоретическая часть
Транспортной сетью называется нагруженный орграф, имеющий следующие
особенности:
1) орграф не имеет петель;
2) существует одна и только одна вершина v0 c нулевой полустепенью
захода, называемая источником сети ( -1(v0)= , т.е. ни одна дуга не
заходит в v0);
3) существует одна и только одна вершина vk с нулевой полустепенью
исхода, называемая стоком сети (для неѐ (vk)= , т.е. ни одна дуга не
выходит из vk);
4) каждой дуге орграфа
rij отнесено целое число c(rij), называемое
пропускной способностью дуги, ведущей из вершины vi в вершину vj.
Остальные вершины орграфа называются промежуточными.
Множество дуг, заходящих в вершину vi, обозначается Rvi(-).
Множество дуг, выходящих из вершины vi, обозначается Rvi(+).
Потоком по дуге rij транспорт сети называется функция (rij), удовлетворяющая
условиям:
0 ( rij) c(rij), rij R;
(13)
p
n
( rij ) 0 ;
( rij )
k 1
v
k 1
Условие (13) означает, что поток по дуге rij не превосходит пропускную
способность дуги.
Условие (14) означает непрерывность потока. Функцию (rij) можно
рассматривать как количество некоторого продукта, поступающего за единицу
времени по дуге rij из вершины vi в вершину vj .
Продукт поступает в сеть только из источника v0 . В сети продукт не
создается дополнительно, не исчезает и не накапливается в промежуточных
вершинах. Поэтому количество продукта, поступившего в сеть из источника v0,
равно количеству продукта, выходящего из сети через сток vk :
( r0 j )
r0 j R v i (
)
Величина
( rik )
rik R v k (
t . c.
t .c.
(14)
)
называется величиной потока транспортной сети.
Каждой дуге сопоставлено два числа:
первое – пропускная способность,
второе – поток по дуге.
Дуга, по которой поток равен еѐ пропускной способности, называется
насыщенной.
69
Из всего множества вершин орграфа выделим подмножество A V такое,
что:
1) v0 A
2) vk A
RA
( )
- множество дуг, заходящих в вершины А
RA
( )
- множество дуг, выходящих из вершин А.
Полная совокупность дуг называется сечением А транспортной сети.
Так как продукты, движущиеся от источника к стоку, обязательно пройдут
по какой-нибудь дуге сечения, то общий поток через сечение будет равен
величине потока транспортной сети:
( rij )
rij R A (
( rij )
)
rij R A (
(15)
t .c.
)
Пропускной способностью сечения А называется сумма пропускных
способностей дуг, исходящих из этого сечения;
c( A )
c( rij )
rij R A (
(16)
)
Так как для любой дуги справедливо неравенство (rij) c(rij), то
t.c.
c(A).
Одной из наиболее распространенных задач о транспортных сетях
является задача о максимальном потоке.
Она состоит в следующем:
при заданной конфигурации транспортной сети и известной пропускной
способности дуг найти максимальную величину потока, который может
пропустить транспортная сеть.
Эта задача решается на основании следующей теоремы Форда-Фалкерсона.
Теорема. Если для некоторой величины потока транспортной сети
некоторого сечения А* имеет место равенство
t.c. =с(А
t.c.
и
*
),
то поток t.c. является максимальной для данной сети, а сечение А* имеет
наименьшую пропускную способность среди любых сечений данной сети.
Доказательство.
Величина потока для любого сечения А должна
удовлетворять условию
t.c.
с(А).
Обозначим А* - сечение с минимальной пропускной способностью
с(А*) = min[c(A)],
70
Так как величина потока t.c. одна и та же для любого сечения
транспортной сети, то увеличивать поток t.c. возможно лишь до тех пор, пока
он не достигнет значения с(А*). Следовательно,
max
t.c.
= c(A*).
Поток транспортной сети называется полным, если каждый путь от
источника сеи до его стока содержит, по крайней мере, одну насыщенную
дугу.
Величина полного потока для данной транспортной сети зависит не только
от пропускной способности дуг, но и от направления потока в разных дугах.
Поэтому полный поток в данной транспортной сети не обязательно
является максимальным.
Непосредственно пользоваться теоремой Форда-Фалкерсона для
нахождения максимального потока нельзя. Но теорема полезна тем, что сводит
задачу о нахождении максимального потока к задаче определения сечения.
3.3.2 Алгоритм Форда-Фалкерсона нахождения множества вершин А V,
определяющих минимальное сечение
1. Присвоить всем дугам нулевые значения потоков
(rij) = 0 , rij R.
2. Положить h(v0) =
и присвоить вершине-истоку метку M(v0) = <-, >.
Положить p=v0.
3. Для каждой дуги rpq = <p,q>, такой, что вершина q не помечена,
вычислить где с=с(rij) – пропускная способность дуги <p,q> ; pq - поток по
дуге <p,q>.
Если d(p,q) > 0 , присвоить вершине метку M(vq) = <p+,h(q)>.
где
h(q) = min(h(p);d(p,q)).
Если d(p,q) = 0 , то дуга <p,q> насыщенна. Метка для вершины q по этой
дуге не определяется .
4. Для каждой дуги <q,p>, такой что q ещѐ не снабжена меткой и
0 присоединить к вершине q метку M(q) = <p-,h(q)>,
(q,p) >
где
h(q) = min(h(p);
(q,p)).
Вершина p обработана.
5.
Если вершина-сток vk снабжена меткой, то перейти к п.7.
6.
Выбрать помеченную вершину vi , которая ещѐ не обработана, и
присвоить p=vi . Перейти к п.3.
71
Если таких вершин не осталось, то конец алгоритма нахождения
множества вершин, определяющих минимальное сечение.
Помеченные вершины на последней итерации составляют множество
А V, определяющих минимальное сечение.
Максимальный поток определяется как сумма пропускных способностей
дуг, исходящих из вершин множества А:
max
c( rij )
t .c.
rij R A (
)
7. После каждой итерации определяется путь, проходящий через
помеченные вершины от источника к стоку = v0,…,vk .
8. Корректируется поток. Идя в обратном направлении от стока vk к
источнику v0, для каждой дуги, входящей в путь определяется значение
потока
(p,q) = (p,q) + h(vk), если метка q имеет вид M(q) = <p+,h(q)>, и
(p,q) = (p,q) + h(vk), если метка q имеет вид M(q) = <p, h(q)>.
9. Убрать все метки и перейти к п.2.
3.3.3 Решение задачи вручную
Для заданной схемы найти полный и максимальный поток.
Схема.
v1
3,0
v0
4,0
v2
2,0
1,0
5,0
v5
3,0
1,0
4,0
v3
6,0
2,0
v4
Итерация-1
Метим v0 M(v0) = <-, >
Переходим к v1
(v0,v1): [+]
d(v0,v1) = c(v0,v1) – f(v0,v1) = 3 – 0 =3;
h(v1) = min(h(v0), d(v0,v1)) = min( ,3) = 3;
M(v1) = <+v0,3>.
Переходим к v2
(v1,v2): [+]
d(v1,v2) = c(v1,v2) – f(v1,v2) = 4 – 0 =4;
h(v2) = min(h(v1), d(v1,v2)) = min(3,4) = 3;
M(v2) = <+v1,3>.
Переходим к v3
72
(v0,v3): [+]
d(v0,v3) = c(v0,v3) – f(v0,v3) = 4 – 0 =4;
h(v3) = min(h(v0), d(v0,v2)) = min( ,4) = 4;
M(v3) = <+v0,4>.
Переходим к v4
(v3,v4): [+]
d(v3,v4) = c(v3,v4) – f(v3,v4) = 2 – 0 =2;
h(v4)= min(h(v3), d(v3,v4)) = min(4,2) = 2;
M(v4) = <+v3,2>.
Переходим к v5
(v4,v5): [+]
d(v4,v5) = c(v4,v5) – f(v4,v5) = 6 – 0 = 6;
h(v5)= min(h(v4), d(v4,v5)) = min(2,6) = 2;
M(v5) = <+v4,2>.
Вершина v5 получила метку – переходим к определению пути.
M(v5) = <+v4,2>. M(v4) = <+v3,2>. M(v3) = <+v0,4>.
= v0v3v4v5
Корректируем потоки.
f(v0,v3) = f(v0,v3) + h(v5) = 0 + 2 = 2;
f(v3,v4) = f(v3,v4) + h(v5) = 0 + 2 = 2;
f(v4,v5) = f(v4,v5) + h(v5) = 0 + 2 = 2.
Итерация-2
v1
4,0
v2
2,0
3,0
1,0
v5
3,0
5,0
v0
1,0
4,2
6,2
v3
2,2
v4
Метим v0 M(v0) = <-, >
Переходим к v1
(v0,v1): [+]
d(v0,v1) = c(v0,v1) – f(v0,v1) = 3 – 0 =3;
h(v1) = min(h(v0), d(v0,v1)) = min( ,3) = 3;
M(v1) = <+v0,3>.
Переходим к v2
(v1,v2): [+]
73
d(v1,v2) = c(v1,v2) – f(v1,v2) = 4 – 0 =4;
h(v2) = min(h(v1), d(v1,v2)) = min(3,4) = 3;
M(v2) = <+v1,3>.
Переходим к v3
(v0,v3): [+]
d(v0,v3) = c(v0,v3) – f(v0,v3) = 4 – 2 =2;
h(v3) = min(h(v0), d(v0,v2)) = min( ,2) = 2;
M(v3) = <+v0,2>.
Переходим к v4
(v1,v4): [+]
d(v1,v4) = c(v1,v4) – f(v1,v4) = 1 – 0 =1;
h(v4)= min(h(v1), d(v1,v4)) = min(3,1) = 1;
M(v4) = <+v1,1>.
Переходим к v5
(v4,v5): [+]
d(v4,v5) = c(v4,v5) – f(v4,v5) = 6 – 2 = 4;
h(v5)= min(h(v4), d(v4,v5)) = min(1,4) = 1;
M(v5) = <+v4,1>.
Вершина v5 получила метку – переходим к определению пути.
M(v5) = <+v4,1>. M(v4) = <+v1,1>. M(v1) = <+v0,3>.
= v0v1v4v5
Корректируем потоки.
f(v0,v1) = f(v0 ,v1) + h(v5) = 0 + 1 = 1;
f(v1,v4) = f(v1 ,v4) + h(v5) = 0 + 1 = 1 ;
f(v4,v5) = f(v4 ,v5) + h(v5) = 2 + 1 = 3.
Итерация-3
v1
4,0
v2
3,1
2,0
1,0
v0
v5
3,0
5,0
1,1
4,2
v3
2,2
6,3
v4
Метим v0 M(v0) = <-, >
Переходим к v1
(v0,v1): [+]
d(v0,v1) = c(v0,v1) – f(v0,v1) = 3 – 1 =2;
h(v1) = min(h(v0), d(v0,v1)) = min( ,2) = 2;
M(v1) = <+v0 ,2>.
74
Переходим к v2
(v1,v2): [+]
d(v1,v2) = c(v1,v2) – f(v1,v2) = 4 – 0 =4;
h(v2) = min(h(v1), d(v1,v2)) = min(2,4) = 2;
M(v2) = <+v1,2>.
Переходим к v3
(v0,v3): [+]
d(v0,v3) = c(v0,v3) – f(v0,v3) = 4 – 2 =2;
h(v3) = min(h(v0), d(v0,v2)) = min( ,2) = 2;
M(v3) = <+v0,2>.
Переходим к v4
На данном шаге эта вершина помечена быть не может.
Переходим к v5
(v2,v5): [+]
d(v2,v5) = c(v2,v5) – f(v2,v5) = 2 – 0 = 2;
h(v5)= min(h(v2), d(v4,v5)) = min(2,2) = 2;
M(v5) = <+v2,2>.
Вершина v5 получила метку – переходим к определению пути.
M(v5) = <+v2,2>. M(v2) = <+v1,2>. M(v1) = <+v0,2>.
= v0v1v2v5
Корректируем потоки.
f(v0,v1) = f(v0,v1) + h(v5) = 1 + 2 = 3;
f(v1,v2) = f(v1,v2) + h(v5) = 0 + 2 = 2 ;
f(v2,v5) = f(v2,v5) + h(v5) = 0 + 2 = 2.
Итерация-4
Метим v0 M(v0) = <-, >
v1
4,2
v2
2,2
3,3
1,0
v0
1,1
4,2
v3
v5
3,0
5,0
2,2
6,3
v4
Переходим к v1
На данном шаге эта вершина помечена быть не может.
Переходим к v2
На данном шаге эта вершина помечена быть не может.
75
Переходим к v3
(v0,v3): [+]
d(v0,v3) = c(v0,v3) – f(v0,v3) = 4 – 2 =2;
h(v3) = min(h(v0), d(v0,v2)) = min( ,2) = 2;
M(v3) = <+v0,2>.
Переходим к v4
На данном шаге эта вершина помечена быть не может.
Переходим к v5
На данном шаге эта вершина помечена быть не может.
Переходим к v1
На данном шаге эта вершина помечена быть не может.
Переходим к v2
(v3,v2): [+]
d(v3,v2) = c(v3,v2) – f(v3,v2) = 1 - 0 = 1;
h(v2) = min(h(v3), d(v2,v3)) = min(2,1) = 1;
M(v2) = <+v3 ,1>.
Переходим к v1
(v2,v1): [-]
h(v1) = min(h(v2), f(v2,v1)) = min(1,2) = 1;
M(v1) = <-v2,1>.
После этого шага ни одну вершину нельзя пометить.
Вершины, помеченные на этом шаге, составляют множество А.
А = {v0,v1,v2,v3}
Рисуем сечение на схеме.
v1
4,2
v2
3,3
2,2
1,0
v0
v5
3,0
5,0
1,1
4,2
v3
2,2
6,3
v4
Полный поток:
ft.c.= f(v0,v1) + f(v0,v2) = 3 + 2 = 5 ;
Максимальный поток:
76
max(f) = c(v3,v4) + c(v1,v4) + c(v2,v5) = 2 + 1 + 2 = 5.
3.3.4 Программа
uses CRT, Graphs, TextScr, mStack, ServCalc;
type FlowValue = word;
type TDirection = -1..1 ;
type
FieldMark = record
Before : TopValue;
Value : FlowValue;
Direction : TDirection;
{---------------------Direction Value----------------------Direction = -1 -- Direcction = 0 -- not difinitely
Direction = 1 -- +
------------------------------------------------------------}
end;
type TMarks = array [1..MaxNumberTop] of FieldMark;
var
Flow, Skip : matrix;
Marks : TMarks;
SizeMatrix: NumberTop;
value_sewer : FlowValue;
MaxTry, TryLoseCounter: NumberTop;
Sewer, Headwaters : TopValue;
top, adjacent_top : TopValue;
iPath : stack;
max_flow : FlowValue;
77
{ - - - Get Fields - - - -}
function GetTopBefore(const Marks:Tmarks; top:TopValue):TopValue;
begin
GetTopBefore := Marks[top].Before;
end;
function GetTopValue(const Marks:Tmarks; top :TopValue):FlowValue;
begin
GetTopValue := Marks[top].Value;
end;
function GetTopDirection(const Marks:TMarks; top:TopValue):FlowValue;
begin
GetTopDirection :=Marks[top].Direction;
end;
{- - - ///Get Fields - -- -- -}
{ - - - Set Fields - - - - - }
procedure SetTopBefore(var Marks:TMarks; top:TopValue; content:TopValue);
begin
Marks[top].Before := content;
end;
procedure SetTopDirection(var Marks:TMarks; top:TopValue; content:TDirection);
begin
Marks[top].Direction := content;
end;
procedure SetTopValue(var Marks:TMarks; top:TopValue; content:FlowValue);
begin
Marks[top].Value := content;
end;
{- - - - ///Set Fields -- - - }
{ - - - - Initialization - -- - -}
procedure InitialFlow(var Flow:matrix; SizeMatrix:NumberTop);
var column, row : ElementPosition;
begin
for row:=1 to SizeMatrix do
78
for column:=1 to SizeMatrix do
Flow[row,column]:= 0 ;
end;
procedure
InitialValueHeadwaters(var
Marks:TMarks;Headwaters:TopValue;SizeMatrix:NumberTop);
var content : FlowValue;
begin
content := SizeMatrix + 13 ;
SetTopValue(Marks,Headwaters,content);
end;
{- - - - ///Initialization - - - -}
{-- -}
procedure ClearMarks(var Marks:TMarks; SizeMatrix:NumberTop);
var i : ElementPosition;
begin
for i:=1 to SizeMatrix do
begin
SetTopValue(Marks,i,0);
SetTopDirection(Marks,i,0);
SetTopBefore(Marks,i,0);
end;
end;
{ -- - - Search -- - - - - - }
function SearchSewer(const Skip : matrix; SizeMatrix:NumberTop):TopValue;
var row : ElementPosition;
var Sewer : TopValue;
begin
Sewer := 0;
for row:=1 to SizeMatrix do
if AllColumnsZero(Skip,row,SizeMatrix)=true then
begin
Sewer:=row;
break;
end;
if Sewer=0 then
begin
79
writeln;
Writeln('Error: Net Stoka');
Halt(1);
end;
SearchSewer := Sewer;
end;
function SearchHeadwaters(const Skip : matrix; SizeMatrix:NumberTop):TopValue;
var column : ElementPosition;
var Headwaters : TopValue;
begin
Headwaters:= 0;
for column:=1 to SizeMatrix do
if AllRowsZero(Skip,column,SizeMatrix)=true then
begin
Headwaters := column;
break;
end;
if Headwaters=0 then
begin
writeln;
Writeln('Error: Net Istoka');
Halt(1);
end;
SearchHeadwaters := Headwaters ;
end;
{- - - - ///Search - - - -}
function
HasGotMark(const
SizeMatrix:NumberTop):boolean;
var before : TopValue;
begin
Marks:TMarks;
top,Headwaters:TopValue;
before := GetTopBefore(Marks,top) ;
80
if ( (before<>0) or (top=Headwaters) )
then HasGotMark := true
else HasGotMark := false;
end;
function
TopDirectMark(const
top:TopValue;SizeMatrix:NumberTop):TopValue;
Skip:matrix;
var row, column: ElementPosition;
var LabeledTop : boolean;
var delta : FlowValue;
begin
{$B-}
TopDirectMark := 0;
column := top;
for row:=1 to SizeMatrix do
begin
LabeledTop := HasGotMark(Marks,row,Headwaters,SizeMatrix) ;
delta := Skip[row,column] -Flow[row,column];
if ( Skip[row,column]<>0 )
then
if ( LabeledTop=true )
then
if ( delta > 0 )
then
begin
TopDirectMark := row;
Break;
end;
end;
{$B+}
end;
function
TopInverseMark(const
SizeMatrix:NumberTop):TopValue;
var row, column: ElementPosition;
var LabeledTop : boolean;
begin
{$B-}
TopInverseMark := 0;
row := top;
Skip:matrix;
top:TopValue;
81
for column:=1 to SizeMatrix do
begin
LabeledTop := HasGotMark(Marks,column,Headwaters,SizeMatrix);
if ( Skip[row,column]<>0 )
then
if (LabeledTop=true)
then
if ( (Flow[row,column] > 0) and (column<>Sewer) )
then
begin
TopInverseMark := column;
Break;
end;
end;
{$B+}
end;
procedure FindPath(var Path:stack; const Marks: TMarks; Sewer:TopValue);
var top: TopValue;
begin
Path.InitStack;
top := Sewer;
Path.Push(top);
repeat
top := GetTopBefore(Marks,top);
Path.Push(top);
until top=Headwaters;
end;
{ - - - Correction - -- - - -}
procedure CorrectFlow (var Flow: matrix; var Path:stack;
const Marks:TMarks; value_sewer: FlowValue);
var ot, d0 : ElementPosition;
var head : ElementPosition;
var direction : TDirection;
begin
ot := Path.Pop;
d0 := Path.Pop;
direction := GetTopDirection(Marks,d0);
Flow[ot,d0] := Flow[ot,d0] + direction * (value_sewer);
head := Path.GetHead;
while (head<>0) do
82
begin
ot:= d0;
d0 := Path.Pop;
direction := GetTopDirection(Marks,d0);
Flow[ot, d0] := Flow[ot, d0] + direction * (value_sewer);
head := Path.GetHead;
end;
end;
{- - - ///Corection - - - -}
procedure DirectMark(var Marks:TMarks; top, dtop: TopValue);
var value_dtop : FlowValue;
var delta : FlowValue;
var
value : FlowValue;
var direction : TDirection;
var
Before : TopValue;
begin
value_dtop := GetTopValue(Marks,dtop);
delta := Skip[dtop,top] - Flow[dtop,top];
value := min (value_dtop, delta);
direction := 1;
before := dtop;
SetTopValue(Marks,top,value);
SetTopDirection(Marks,top,direction) ;
SetTopBefore(Marks,top,before);
end;
procedure InverseMark(var Marks:TMarks; top, itop:TopValue);
var flow_top : FlowValue;
var value_itop : FlowValue;
var
value : FlowValue;
var direction : TDirection;
var
Before : TopValue;
83
begin
value_itop := GetTopValue(Marks,itop);
flow_top := Flow[top,itop];
value := min (value_itop, flow_top);
direction := -1 ;
before := itop ;
SetTopValue(Marks,top,value);
SetTopDirection(Marks,top,direction) ;
SetTopBefore(Marks,top,before);
end;
function MaxFlow(const Skip,Flow:matrix; Headwaters:TopValue;
SizeMatrix:NumberTop):FlowValue;
var summa : FlowValue;
var row, column : ElementPosition;
begin
row := Headwaters;
summa := 0;
for column:=1 to SizeMatrix do
if ( Skip[row,column] <> 0 )
then summa:= summa + Flow[row,column];
MaxFlow := summa ;
end;
{ - - - TopOperation - - - -}
procedure InitialTop(var top:TopValue);
begin
top := 1;
end;
84
procedure GotoNextTop(var top:TopValue);
begin
top := top + 1 ;
end;
{ - - - - ///TopOperation - - - - }
procedure
TryMarkTop
(const
Skip:matrix;
SizeMatrix:NumberTop;
var MaxTry, TryLoseCounter: NumberTop);
var
top:TopValue;
var adjacent : TopValue;
begin
adjacent_top := TopDirectMark(Skip,top,SizeMatrix);
if (adjacent_top<>0) then
begin
DirectMark(Marks,top,adjacent_top);
MaxTry := MaxTry - 1;
TryLoseCounter := 0;
InitialTop(top);
end
else
begin
adjacent_top := TopInverseMark(Skip,top,SizeMatrix);
if (adjacent_top <> 0) then
begin
InverseMark(Marks,top,adjacent_top);
MaxTry := MaxTry - 1;
TryLoseCounter := 0;
InitialTop(top);
end
else
begin
TryLoseCounter := TryLoseCounter + 1 ;
GotoNextTop(top);
end;
85
end;
end;
Begin
ClrScr;
Writeln('Welcome to program Ford-Falk');
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('Point size of matrix skip.');
writeln;
Write('Matrix size = ');
Readln(SizeMatrix);
writeln;
Writeln('Input matrix of skip.');
writeln;
InputMatrix(Skip,SizeMatrix);
{///////////////////////////////////////////////////////}
Headwaters := SearchHeadwaters(Skip,SizeMatrix);
Sewer := SearchSewer(Skip,SizeMatrix);
MaxTry := SizeMatrix - 1 ;
TryLoseCounter := 0;
InitialFlow(Flow,SizeMatrix);
while ( TryLoseCounter <> MaxTry ) do
begin
ClearMarks(Marks,SizeMatrix);
InitialValueHeadwaters(Marks,Headwaters,SizeMatrix);
InitialTop(top);
86
while
(
(TryLoseCounter
<>
MaxTry)
HasGotMark(Marks,Sewer,Headwaters,SizeMatrix) = false)) do
and
(
begin
if ( HasGotMark(Marks,top,Headwaters,SizeMatrix) = true ) or (top = Headwaters)
then
begin
GotoNextTop(top);
continue;
end
else
TryMarkTop(Skip,top,SizeMatrix,MaxTry,TryLoseCounter);
end;
if ( HasGotMark(Marks,Sewer,Headwaters,SizeMatrix) = true) then
begin
FindPath(iPath,Marks,Sewer);
value_sewer := GetTopValue(Marks,Sewer);
CorrectFlow(Flow,iPath,Marks,value_sewer);
MaxTry := SizeMatrix - 1 ;
end;
end;
{///////////////////////////////////////////////////////////}
writeln;
Writeln('Matrix Flow =');
writeln;
writeln;
PrintMatrix(Flow,SizeMatrix);
writeln;
max_flow := MaxFlow(Skip,Flow,Headwaters,SizeMatrix);
writeln;
87
Write('Maximum flow = ',max_flow);
writeln;
writeln;
InsertLineSymbvols('=');
writeln;
Writeln('The program was terminated.');
writeln;
Writeln('Press Enter...');
readln;
End.
88
3.4
Метод поиска маршрута в связном графе (алгоритм Терри)
Решение задачи вручную и на ПВМ.
3.4.1
Теоретическая часть
Метод Терри – это алгоритм поиска маршрута в связном графе.
Существует две формы алгоритма Терри:
на основании правил метода
и с использованием матрицы смежности.
Исходя из начальной вершины и осуществляя последовательный переход
от каждой достигнутой вершины к смежной вершине, следовать следующим
правилам.
1. Отмечать направление, в котором проходится ребро, как в прямом, так и
в обратном направлениях.
2. Исходя из любой вершины, всегда следовать только по тому ребру,
которое еще не было пройденно или было пройденно в противоположном
направлении.
3. Для всякой вершины отмечать первое входящее ребро, если вершина
встречается впервые.
4. Из всякой вершины идти по ребру, по которому пришли в эту вершину (в
обратном направлении) лишь тогда, когда нет другой возможности.
В данном случае нас интересует форма представления, активно
использующая матрицу смежности.
Здесь и далее считаем вершины графа занумерованными.
Матрица смежности это квадратная матрица, элементы которой
способны принимать всего два значения – ноль или единица.
Если на пересечении строки и столбца стоит единица, то это значит что
вершина, соответствующая номеру строки, непосредственно соединена с
вершиной, сответсвующей номеру столбца.
Если на пересечении строки и столбца стоит ноль, то это значит, что
вышеописанные вершины не соединяются.
Маршрутом из вершины v0 в vk называется последовательность вершин.
При этом каждая пара вершин непосредственно соединяется между собой.
3.4.2
Алгоритм Терри
1. Составить матрицу смежности. MG[i,j].
2. Задать начальную и конечную вершины vS и vF.
3. Задать две переменные:
89
4. row - текущая строка MG[i,j];
5. column – текущий столбец MG[i,j].
6. row:= vS; column := 1.
7. 6. Если (i,j) элемент матрицы MG[i,j] единичный, то обнуляем этот
элемент и элемент (j,i) (если он единичный).
8. Заносим номер i-ой строки в стек. Переходим в строку с номером j.
9. Если (i,j) элемент нулевой, то переходим к анализу следующего столбца iой строки.
10.Если оказалось, что все элементы анализируемой строки нулевые, то
достаем из стека
11.номер вершины и переходим в строку с этим номером.
12.Если мы переходим из одной строки в другую, то номер столбца делаем
единичным.
13.Анализ матрицы заканчивается, когда попадаем в строку с vF –м
номером.
14.Содержимое стека – маршрут из vS в vF.
Решение задачи вручную
3.4.3
Зададимся графом.
Ниже приведена схема графа.
Задание:
v6 – начальная вершина;
v7 – конечная вршина;
Найти путь из v6 в v7.
1
2
6
5
4
3
7
Решение:
90
0)
1
2
3
4
5
6
7
1)
1 2 3 4 5 6 7
1
1
1
1
1
1
1
1
1
1
1
1
1 1
Переходим к строке 6 столбцу 1.
Элемент (6,1) нулевой, переходим к (6,2) элементу.
2)
Элемент (6,2) нулевой, переходим к (6,3).
3)
Элемент (6,3) нулевой, переходим к (6,4).
4)
Элемент (6,4) единичный. Заполняем стек : {6}.
матрицу.
1
2
3
4
5
6
7
Переписываем
1 2 3 4 5 6 7
1
1
1
1
1
1
1
1
1
0
1
0
1 1
5) Переходим к анализу строки 4 и столбца 1. Содержимое стека : {6}.
6) Элемент (4,1) единичный. Заполняем стек : {6,4}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
1
1
1
1
1
1
1
1
0
0
1
0
1 1
7) Переходим к анализу строки 1 и столбца 1. Содержимое стека : {6,4}.
91
Элемент (1,1) нулевой, переходим к элементу (1,2).
8) Элемент (1,2) единичный. Заполняем стек : {6,4,1}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
0
1
0
1
1
1
1
1
0
0
1
0
1 1
9) Переходим к анализу строки 2 и столбца 1. Содержимое стека : {6,4,1}.
Элемент (2,1) нулевой, переходим к элементу (2,2).
10)Элемент (2,2) нулевой, переходим к элементу (2,3).
11)Элемент (2,3) нулевой, переходим к элементу (2,4).
12)Элемент (2,4) единичный. Заполняем стек : {6,4,1,2}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
0
1
0
0
1
1
1
1
0
0
1
0
1 1
13)Переходим к анализу строки 4 . Содержимое стека : {6,4,1,2}.
Строка 4 нулевая, вынимаем из стека элемент. Содержимое стека :
{6,4,1}.
14)Переходим к анализу строки 2 и столбца 1 . Содержимое стека : {6,4,1}.
Элемент (2,1) нулевой, переходим к элементу (2,2).
15)Элемент (2,2) нулевой, переходим к элементу (2,3).
16)Элемент (2,3) нулевой, переходим к элементу (2,4).
17)Элемент (2,4) нулевой, переходим к элементу (2,5).
18)Элемент (2,5) нулевой, переходим к элементу (2,6).
92
19)Элемент (2,6) единичный. Заполняем стек : {6,4,1,2}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
0
1
0
0
0
1
1
1
0
0
1
0
1 1
20)Переходим к анализу строки 6. Содержимое стека : {6,4,1,2}.
Строка 6 нулевая, вынимаем из стека элемент. Содержимое стека :
{6,4,1}.
21)Переходим к анализу строки 2 Содержимое стека : {6,4,1}.
Строка 2 нулевая, вынимаем из стека элемент. Содержимое стека : {6,4}.
22)Переходим к анализу строки 1 и столбца 1. Содержимое стека : {6,4}.
Элемент (1,1) нулевой, переходим к элементу (1,2).
23)Элемент (1,2) нулевой, переходим к элементу (1,3).
24)Элемент (1,3) нулевой, переходим к элементу (1,4).
25)Элемент (1,4) нулевой, переходим к элементу (1,5).
26)Элемент
матрицу.
1 2
1
0
2 0
3 1
4 0
5
6
7
(1,5) единичный. Заполняем стек : {6,4,1}. Переписываем
3 4 5 6 7
0
0
0
1
1
0
1
0
1 1
27)Переходим к анализу строки 5 и столбца 1. Содержимое стека : {6,4,1,2}.
Элемент (5,1) нулевой, переходим к элементу (5,2).
28)Элемент (5,2) нулевой, переходим к элементу (5,3).
29)Элемент (5,3) единичный. Заполняем стек : {6,4,1,5}. Переписываем
матрицу.
1 2 3 4 5 6 7
1
0
0
93
2 0
0
0
3 1
1
1
4 0
0
5
0
6
0
7
1 1
30)Переходим к анализу строки 3 и столбца 1. Содержимое стека : {6,4,1,5}.
Элемент (3,1) единичный. Заполняем стек : {6,4,1,5,3}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
0
0
0
0
0
0
1
1
0
0
0
0
1 1
31)Переходим к анализу строки 1. Содержимое стека : {6,4,1,5,3}.
Строка 1 нулевая, вынимаем из стека элемент. Содержимое стека :
{6,4,1,5}.
32)Переходим к анализу строки 3 и столбца 1. Содержимое стека : {6,4,1,5}.
Элемент (3,1) нулевой, переходим к элементу (3,2).
33)Элемент (3,2) нулевой, переходим к элементу (3,3).
34)Элемент (3,3) нулевой, переходим к элементу (3,4)
35 ) Элемент (3,4) единичный. Заполняем стек : {6,4,1,5,3}. Переписываем
матрицу.
1
2
3
4
5
6
7
1 2 3 4 5 6 7
0
0
0
0
0
0
0
1
0
0
0
0
1 1
35) Переходим к анализу строки 4. Содержимое стека : {6,4,1,5,3}.
Строка 4 нулевая, вынимаем из стека элемент. Содержимое стека :
{6,4,1,5}.
36)Переходим к анализу строки 3 и столбца 1. Содержимое стека : {6,4,1,5}.
94
Элемент (3,1) нулевой, переходим к элементу (3,2).
37)Элемент (3,2) нулевой, переходим к элементу (3,3).
38)Элемент (3,3) нулевой, переходим к элементу (3,4).
39)Элемент (3,4) нулевой, переходим к элементу (3,5).
40)Элемент (3,5) нулевой, переходим к элементу (3,6).
41)Элемент (3,6) нулевой, переходим к элементу (3,7).
42)Элемент (3,7) единичный. Заполняем стек : {6,4,1,5,3}.
Ответ: {6,4,1,5,3,7}.
3.4.4 Программирование
program Terri;
uses crt;
const m=100; // Максимальный размер массива
var
mg:array[1..m,1..m] of byte; // Матрица смежности
stack:array[1..m-1] of word; // Стек
i,j:word;
column,row:word;
sp:word; // номер последнего элемента в стеке
vs,vf:word;
n: word; // Реальный размер матрицы смежности
begin
clrscr;
write('Input size matrix: ');
read(n);
clrscr;
for i:=1 to n do
for j:=1 to n do
if i=j then
mg[i,j]:=0 // Диагональным элементам присваивается ноль
else
begin
write('mg(',i,',',j,') = ');
read(mg[i,j]);
clrscr;
end;
write('Input Start: ');
// Вводим начальную вершину
read(vs);
write('Input Finish: '); // Вводим конечную вершину
read(vf);
row:=vs;
// Начальное значение строки
95
column:=1;
sp:=0;
// Стек пустой
while row<>vf do
if mg[row,column]=1 then // Если элемент единичный
begin
mg[row,column]:=0; // то заменить его
if mg[column,row]=1 then // ,а, если надо, то и симметричный ему
mg[column,row]:=0;
sp:=sp+1;
// указатель на вершину стека сместить
stack[sp]:=row; // положить в стек номер строки
row:=column; // строка принимает значение столбца
column:=1; // столбец сбрасывается
end
else
if column=n then // Если все элементы нулевые
begin
row:=stack[sp]; // вытащить из стека
sp:=sp-1; // сместить указатель
column:=1; // сбросить столбец
end
else
column:=column+1; // перейти к другому столбцу
sp:=sp+1;
stack[sp]:=row; // положить в стек конечный элемент
writeln;
write('Path : ');
for i:=1 to sp do
write(' ',stack[i]); // Вывести на экран содержимое стека
readln;
end.
Недостатки программы,
Никакой защиты от неверного ввода.
Ввод одинаков для графа и орграфа, что нерационально.
Стек не является объектом.
Неэкономное использование оперативной памяти, реализовать стек
можно и через указательный тип. При этом память будет использоваться
рациональнее.
5. Неинформативная обработка ввода-вывода.
1.
2.
3.
4.
Это не недостаток, а так, особенность алгоритма. Если существует два
пути из начальной вершины в конечную, то алгоритм Терри, все равно, найдет
только один из них.
96
3.4.5 Решение задачи на ПВМ
Input Start: 6
Input Finish: 7
Path : 6 4 1 5 3 7
Как видим, результат верный.
97
4 Структурный анализ сети
Структура сети. Основные понятия.
4.1
Одной из основных характеристик сети является ее структура, которая во
многом определяет все основные показатели сети.
Под структурой сети понимается совокупность узлов коммутации (УК) и
оконечных пунктов (ОП) сети и соединяющих их каналов связи в их взаимном
расположении и с характеристиками по передаче и распределению сообщений.
Структура сети отражает способность сети к обеспечению доставки
информации в различные оконечные пункты и характеризуется географией
сети, т. е. месторасположением УК и ОП сети.
В качестве математической модели структуры сети широко используется
графовая модель, т. е. модель сети, заданная в виде графа. Основоположниками
такого описания считают Л. Форда и Д. Фолкерсона.
В подобной модели:
- вершины графа сопоставляются с узлами коммутации и/или оконечными
пунктами,
- а ребра графа – с каналами связи.
Ребра графа могут быть ориентированными. В этом случае они
сопоставляются с симплексными каналами.
Если ребра неориентированные,
дуплексными каналами связи.
тогда
они
сопоставляются
с
В рамках графовой модели сеть может быть описана либо:
- графически – в форме графа;
- либо в виде множества вершин и ребер. Варианты описания сети
представлены на рисунке.
Обычно вершины графа обозначаются цифрами, а ребра – буквами.
2
●
b
a
e
1●
3
d
c
●
4
G ═ {A, B};
A═ {a1, …aN}; B═ {bij};
A - множество вершин графа;
B - множество ребер между
вершинами графа ai и aj.
Рис.4.1 Варианты описания графа сети
Так ребра a, b, c, d – являются неориентированными, а ребро e –
ориентированное (направленное) соответственно и граф называется
ориентированным или неориентированным.
98
Для вычисления различных количественных характеристик сети каждому
ребру графа может быть приписан некоторый вес – число или совокупность
чисел, которые характеризуют какое – либо свойство данного ребра как
элемента пути для передачи сообщений.
Таким весом чаще всего являются:
- длина канала,
- пропускная способность,
- количество информации, передаваемое в единицу времени,
- емкость – число стандартных каналов ,
- надежность,
- стоимость и т. д.
Узлам (вершинам графа) также могут быть приписаны веса, например,
- пропускная способность узла,
- емкость ЗУ и т. п.
- Число ребер, инцидентных (т. е. входящих и исходящих) называют
рангом узла r ai .
В нашем случае: r(a1) = 2, r(a2) = 3 и т. д.
- Узел ранга r(ai) = 1 является тупиковым. Через него не могут проходить
никакие пути.
- Узлы, соединенные ребром, называются смежными.
Для осуществления доставки сообщения получателю сеть должна обеспечить
возможность организации не менее одного пути.
Путь μij из узла ai в узел aj – есть упорядоченный набор ребер, начинающийся
в узле ai и заканчивающийся в узле aj.
Для существующего пути конец каждого предыдущего ребра совпадает (в
промежуточном узле) с началом последующего. Кроме того, путь должен быть
несамопересекающимся, т. е. не проходящим дважды через один и тот же
узел.
Например, путь μ13 = {ab, cd, aed}.
Пути, как и ребра, могут быть направленными и ненаправленными.
Рангом пути, r(μij) называется число ребер, входящих в данный путь.
Минимальный ранг пути r(μij) = 1.
Максимальный ранг пути r(μij) = N-1, где N – число узлов графа. В этом
случае путь проходит через все узлы.
99
Каждый путь ijk от узла ai к узлу aj , где k – порядковый номер пути, может
быть записан тремя способами:
1- упорядоченным перечнем ребер и узлов в порядке расположения их на
данном пути. Однако, такая запись является избыточной.
2- перечнем входящих в данный путь ребер;
3- упорядоченным перечнем входящих в данный путь узлов.
Все возможные пути от узла от узла ai к узлу aj образуют множество
путей mij .
Однако на практике важно знать не все возможные пути, а лишь те из них,
которые обладают определенными свойствами или выделены по какому либо
признаку (правилу).
Например, множество путей ранга не выше t, т.е
{mij} = {μij; r(μij ≤ t)}.
Чаще всего для записи пути используют второй способ записи, т.е.
упорядоченным перечнем ребер, причем ребрам приписывают символы по
следующему правилу:
bij
c, åñëèi
j
c, åñëèi
j
.
Например, запишем пути для приведенного графа сети между узлами 1и 3:
1
13
ab
1
31
ba
2
13
cd
2
31
dc
3
13
aed
m13
ab c d
3
31
aed
bec
m31
ba
d c bec
Обратите внимание, что множество
направленности графа - (ребро e).
m13
≠
m31
–
это
следствие
Например, пути
между узлами 1 и 3 ранга не выше 2
2
2
m13 ab cd
è m31 ba d c ,
есть:
а путей ранга ≤ 1 между узлами 1 и 3 не существует.
В итоге, аналитическая запись пути и множества путей позволяет проводить
структурный анализ свойств сети чисто формально, например, с помощью
ЭВМ.
Путь, начинающийся и заканчивающийся в одном и том же узле, называется
контуром (циклом).
Связностью сети h называется минимальное число независимых путей,
которые можно сформировать между каждой парой узлов сети.
Для нашего примера h = 2.
100
4.2
Основные сетевые топологии
Существующие типы структур сети (топологии) можно разделить на
следующие виды:
древовидная топология – между каждой парой узлов существует только
один путь, т. е.
- Связность такой сети h = 1.
- число ребер в такой сети равно N-1.
4.2.1 Разновидности древовидной топологии
В настоящее время широкое распространение получили локальные сети с
древовидной (рис. a) топологией.
В качестве узлов в таких сетях чаще всего выступают высокоскоростные
концентраторы (хабы).
Название «хаб» происходит от английского слова – hub. Наиболее
характерным представителем сетей с подобной топологией является сеть
100VG-AnyLan.
Следует отметить также, что высокоскоростной вариант магистральной сети
Ethernet – Fast Ethernet также имеет древовидную структуру.
г
а
3
3
- дерево
3
- узловая
2
3
3
1
3
2
2
3
3
б
3
- звезда
3
С иерархией узлов
д
в
- снежинка
- линейная
(шина)
Рис.4.2 Основные топологии сетей
Сети с древовидной топологией имеют повышенную живучесть.
Отключение или выход из строя одной из линий или концентратора, как
101
правило, не оказывает существенного влияния на работоспособность остальной
части локальной сети.
Кроме того, одной из причин широкого распространения сетей с
древовидной топологией является то, что эта структура, как правило, более
всего соответствует структуре информационных потоков между абонентами
сети.
Звездообразная сеть (рис.б) характеризуется наличием центрального узла
коммутации – сетевого сервера, к которому (или через который) посылаются
все сообщения.
На сетевой сервер, кроме основных могут быть возложены
дополнительные обязанности (функции) по согласованию скоростей работы
станций и преобразованию протоколов обмена. Это позволяет в рамках одной
сети объединять разнотипные рабочие станции.
Недостатки звездообразных топологий
Наряду с определенными преимуществами, подобные локальные сети с
звездообразной топологией имеют ряд недостатков.
В частности, при подключении большого числа рабочих станций
поддержание высокой скорости коммутации требует значительных
аппаратных затрат .
Кроме того, значительная функциональная нагрузка центрального
узла определяет его сложность, что, естественно, сказывается на надежности
сети.
В связи с этим в большинстве современных звездообразных сетей
функции коммутации рабочих станций и управления сетью распределены
между сетевым сервером и коммутатором.
При этом сетевой сервер подключается к коммутатору как рабочая
станция, но с максимальным приоритетом. В этом случае структура
центрального узла существенно упрощается, что в сочетании с использованием
высокоскоростных каналов позволяет достичь достаточно высокой скорости
передачи данных.
Так, например, в звездообразной сети Ultra Net скорость передачи
данных достигает 1,4 Гбит/с.
В локальных сетях с шинной топологией (рис. д) все рабочие станции с
помощью сетевых адаптеров подключаются к общей магистрали (шине).
Конструктивно адаптер, как правило, представляет собой плату, которая
встраивается в компьютер, хотя возможно и автономное его исполнение.
В качестве передающей среды может использоваться коаксиальный
кабель или витая пара.
102
В процессе работы сети информация от передающей рабочей станции
поступает на адаптеры всех рабочих станций, однако воспринимается
только адаптером той рабочей станции, которой она адресована.
Передаваемая информация в сети с топологией «общая шина» может
распространяться в обе стороны.
Достоинства общей шины
1- применение общей шины снижает стоимость проводки,
2- унифицирует подключение различных модулей,
3- обеспечивает возможность почти мгновенного широковещательного
обращения ко всем станциям сети.
Недостатки шинной топологии.
1- Самый серьезный недостаток обшей шины заключается в ее низкой
надежности: любой дефект кабеля или какого-нибудь из многочисленных
разъемов полностью парализует всю сеть. К сожалению, дефект коаксиального
кабеля или разъема редкостью не является.
2- Другим недостатком общей шины является ее невысокая
производительность, так как при таком методе подключения в каждый
момент времени только один компьютер может передавать данные в сеть.
Поэтому при шинной топологии пропускная способность канала связи всегда
делится здесь между всеми узлами сети.
4.2.2 Сетевидные топологии
Это такие структуры, в которых каждый узел является смежным с
несколькими другими узлами. Связность такой сети h > 1
Сетевидная топология (или просто «сетка») может быть:
- плоской (планарной). В этом случае она может быть изображена на
плоскости без пересечения ребер (рис.а).
- может быть неплоской (не планарной). В этом случае граф на
плоскости изобразить без пересечения ребер нельзя (рис.б).
Простейшей сетевидной топологией является кольцевая топология.
Связность кольцевой топологии h = 2.
Сеть с кольцевой топологией (рис.в.) характеризуется наличием замкнутого
однонаправленного канала передачи данных в виде кольца или петли.
В этом случае информация передается последовательно между
адаптерами рабочих станций до тех пор, пока не будет принята адресатом, а
затем удалена из сети.
Обычно за
отправитель.
удаление
информации
из
сети
отвечает
ее
103
Планарная плоская
Непланарная (неплоская)
Радиально-кольцевая
Связность h = 3
Кольцевая
Связность h = 2
Решетка
ранг узла r = 4
Связность h = 2
Сотовая
ранг узла r = 3
Связность h = 2
Полносвязная топология
ранг узла r = 8; число ребер
Двойная решетка
ранг узла r = 8
Связность h = 2
у
р
у
2
1
;
ранг узла r = Nу – 1.
Рис.4.3 Сетевидные топологии
Существенным достоинством кольцевой сети является возможность
организации обратной связи – данные, сделав полный оборот по кольцу,
возвращаются к узлу – источнику. Следовательно, узел – источник имеет
возможность контролировать процесс доставки данных адресату. Часто это
свойство кольцевой сети используется для тестирования связности сети и
поиска узла, работающего некорректно. Для этого в сеть посылаются
специальные тестовые сообщения.
Управление
работой
кольцевой
сети
может
осуществляться
централизованно (с помощью специальной мониторной станции), либо
децентрализовано (за счет распределения функций управления между сетевыми
рабочими станциями).
Существенным недостатком кольцевой сети является выход ее из строя
при разрыве кольца. Исключается этот недостаток, как правило, применением
«двойного» кольца. Для этого в состав сети включают дополнительные линии
104
связи и устройства реконфигурации, которые представляют собой специальные
переключательные устройства простые и надежные.
Полносвязная топология (см. рис.)
В такой сети узлы соединены по принципу «каждый с каждым».
Число ребер в полносвязном графе сети равно
Nð
N ó Nó 1
2
,
где Nр – число ребер; Nу – число узлов в графе.
Ранг узла r = Nу – 1;
В полносвязной топологии может быть исключено Nу–2 без нарушения
связности.
Полносвязная топология соответствует сети, в которой каждый
компьютер сети связан со всеми остальными. Несмотря на логическую
простоту этот вариант сети оказывается громоздким и неэффективным.
Действительно:
- каждый компьютер в сети должен иметь большое количество
коммуникационных портов, достаточное для связи с каждым из остальных
компьютеров сети.
- Для каждой пары компьютеров должна быть выделена отдельная
электрическая линия связи.
Полносвязные топологии применяются редко в силу низкой
эффективности. Чаще всего этот вид топологии применяется в базовых сетях
передачи данных глобальных информационно- вычислительных сетей и в
многомашинных вычислительных комплексах.
Рассмотренные выше сетевые топологии являются базовыми, так как на их
основе формируется конкретная структура реальных сетей. В настоящее время
структура, по крайней мере, глобальных сетей представляет собой
взаимоувязанное объединение сетей различных базовых топологий.
Оптимальной, естественно будет та структура сети, которая в наибольшей
степени соответствует структуре обслуживаемой организации.
Учитывая это, фирмы–производители сетевого оборудования поставляют на
рынок достаточно широкий спектр устройств, используемых для объединения
сетей различных топологий.
Из вышеизложенного следует – топология (структура) сети оказывает
значительное влияние на основные показатели сети и, особенно на надежность
и живучесть.
Чем выше связность сети, тем она более надежна и живуча. Очевидно, что
наибольшей связностью обладает полносвязная сеть, однако для ее
105
реализации требуется (при одинаковом числе узлов) наибольшее число ребер
(каналов), следовательно, стоимость такой сети будет максимальной.
Топология реальных сетей строится по иерархическому принципу:
крупные узлы (обычно базовой сети) соединяются по принципу «каждый с
каждым», а на низших уровнях используются базовые топологии: дерево, шина,
кольцо, звезда.
Структурная матрица сети
4.3
Для анализа свойств сети (нахождения путей различных рангов, свойств
топологии сети и т. д.) целесообразно записать граф сети некоторым
формальным образом.
Для этой цели используют структурную матрицу сет и – B.
Структурной матрицей сети с N узлами называется квадратная матрица
порядка N, в которой каждому узлу ai соответсвует i – я строка и i – ый
столбец:
bij , где
i, j 1, N .
Элементы этой матрицы называются вхождениями.
Определяются вхождения следующим образом:
1 при i
bij
j диагональматрицы
bij , когда есть реброот ai к a j
.
0, если ребра нет
Если ребра графа записываются буквами, тогда вхождения матрицы
определяются следующим образом:
1, если i
x, если i
bij
j
j
x, если i j
0, если ребра нет
.
Если ребра графа ненаправленные, то в этом случае структурная матрица
графа будет симметричной относительно главной диагонали.
Если в структуре графа присутствует хотя бы одно направленное
(ориентированное) ребро, матрица будет несимметричной.
Пример:
106
2
1
a
0
0
b
a
1
0
d
c
g
0
e
1
g
f
h
0 d
b 0
g
f
1
h
h
1
d
a
e
1
c
3
f
b
4
5
Рис. 4.4 Структурная матрица сети
Поскольку элементы (вхождения) структурной матрицы есть ребра графа,
то они могут принимать всего два значения:
1 - если ребро есть и
0 – если ребра нет.
Следовательно, структурную матрицу можно рассматривать как булеву
матрицу и применять к ней аппарат булевой алгебры.
Некоторые свойства булевой алгебры.
1. в булевой алгебре используются 3 операции:
- логическое произведение (конъюнкция) - (• ─ );
- логическое сложение (дизъюнкция) - (+ - );
- инверсия – черта над переменной .
1 = 1, отсюда следует закон повторения:
2. 1
x
x = x; x
x=x
3. закон поглощения :
x
x•y = x.
Трактовка формулы – более короткий путь - (x) поглощает более длинный
путь (x•y), в котором y представляет контур.
Отсюда следует, что
1
x = 1; 1
x = x; x
0 = 0.
4. из закона инверсии следует :
x
x
0;
что соответствует исключению пути, проходящему дважды по одному и
тому же ребру, но в разных направлениях..
4.3.1 Результаты операций над структурными матрицами.
возведение структурной матрицы B в q – ю степень приводит к новой
матрице Bq , элементы которой будут содержать все возможные пути от
узла ai к узлу aj ранга не выше q, т. е.
107
q
mijr
q
.
Следовательно, структурная матрица B q содержит
возможные пути ранга q между всеми узлами сети.
все
При этом существует некоторое значение ранга qmax , при котором
дальнейшее возведение матрицы в степень не меняет элементов матрицы.
Такая матрица Bqmax называется характеристической и содержит все
возможные пути в сети между каждой парой узлов.
Поскольку максимальный ранг пути r(μij) = N-1, где N – число узлов сети,
следовательно, максимальная степень характеристической матрицы не
превышает N-1.
Напомню, что произведение квадратной матрицы A на квадратную матрицу
C есть квадратная матрица D, элементы которой есть сумма произведений i –
ой строки матрицы A и j – го столбца матрицы C:
D =A•C = ║dij = ai1•c1j ai2•c2j … aiN•cNj║.
Подобная структура элемента матричного произведения и позволяет
получать пути заданного ранга при возведении структурной матрицы в степень.
Пример Найдем пути второго ранга и менее для нашего примера,
например, между первым и пятым узлами. Для этого, очевидно, необходимо
возвести структурную матрицу во вторую степень.
Мы сделаем это только для одного элемента матрицы B2 μ15.
Умножим для этого элементы первой строки матрицы на элементы пятого
столбца:
1a00b
х
bcfh1
──────
μ15=b ac 0 0 b = b
ac.
Корректность полученных результатов можно проверить по графу сети.
Других путей ранга не выше двух в данной сети нет.
Для нахождения путей точно заданного ранга структурную матрицу
необходимо преобразовать, а именно:
- заменить единицы на главной диагонали на нули,
- а затем возвести преобразованную матрицу в требуемую степень. В
результате получим пути, точно заданного ранга.
Для графа сети, представленного рисунком имеем:
108
1 a 0 0 b
0 a 0 0 b
a 1 0 d
c
a 0 0 d
c
0 e 1 g
f
0 e
f
0
0 d g 1 h
b 0 f h 1
первая строка матрицы
0
h 0 пятый столбецматрицы
0
0 a 0 0 b
f
0 d g 0 h
b 0 f h 0
2
15
для пути
b c
0 g
__________
__________
__________
_______
между
множествопутей ранга r
ac m152
0 ac 0 0 0
2
узлами графа a1 и a5
Для пути
2
14
0 a 0 0 b первая строка матрицы
0 d
0
четвертый столбец матрицы
g 0 h
0
__________
__________
__________
__________
0 ad 0 0 bh ad bh m 2 множество
14
ранга r 2 между узлами графа a и a
1
4
путей
Для примера найдем множество путей третьего ранга m153 между узлами
a1 и a5 графа сети, представленного на рисунке.. Очевидно, что для нахождения
множества путей mij ранга r = 3 между всеми парами узлов, необходимо
матрицу B0 возвести в третью степень.
Мы же, (для упрощения выкладок) при нахождении множества путей
2
m153 умножим первую строку матрицы 0 на пятый столбец матрицы B0
0
0
bf
b
c
f
ad
bh
h
ac первая строка
0
пятый
2
0
столбец
0
__________
__________
__________
__________
_
0
0
bf f
ad
bh h
0
преобразуе
м результатыумножения
с использованием
булевой
ad
в
bh h
законов
алгебры: bf f
adh bhh
b0
adh b0
0;
adh
adh.
результате получим
Таким образом, множество путей ранга r = 3 между узлами a1 и a5 содержит
один путь m153 adh.
109
4.3.2
Результаты,
получаемые
структурной матрицы
преобразованием
определителя
Определителем (детерминантом) n – го порядка называется число D,
образованное из n2 чисел aij расположенных в табличку следующим образом:
D
aij
a11
a21
a12
a22
a1n
a2 n
a31
a32
a3n
an1
an 2
ann
k
1 a1 a2  an ,
где α, β,γ, . . .,ω пробегают все возможные n! перестановок из чисел 1,2,…‚ n:
знак «+» или «-» перед каждым членом определителя (т. е. Каждым слагаемым)
определяется числом k инверсий - «беспорядков» в каждой перестановке.
например, член a13 a21 a34 a42 в определителе 4 – го порядка имеет знак «минус»,
так как расположение 3. 1. 4. 2 вторых индексов у букв имеет три инверсии:
3.1, 4.2, и 3.2
4.4 Основные свойства булевых определителей
а) если в определителе (но не в матрице) поменять местами две строки или
два столбца, то значение определителя не изменится;
б) если осуществить транспонирование определителя (поменять местами
строки и столбцы), то значение определителя не изменится;
в) если в каждой строке и столбце определителя имеется хотя бы одна
единица, то определитель равен единице;
г) если в определителе строка или столбец состоят из нулей, то
определитель равен нулю;
д) если перед определителем имеется множитель X , то во всех элементах
определителя X может быть заменен на единицу, а
- на нуль, исходя из
свойств булевой алгебры.
Определитель второго порядка вычисляется следующим образом:
a b
c d
D
ad bc
_
 ̄
Определитель третьего порядка вычисляется следующим образом:
D3
x
a1 a2 a3 a1 a2
b1 b2 b3 b1 b2
c1 c2 c3 c1 c2
.
a1b2 c3 a2b3c1 a3b1c2 a3b2 c1 a1b3c2 a2b1c3
110
Вычисление определителя порядка выше третьего производится
разложением определителя по элементам какой-либо строки или столбца. Это
дает возможность за каждый шаг снизить порядок определителя на единицу.
Например, разложение определителя матрицы А с элементами aij i,
j (1,…‚n) по i - й строке будет:
ai1
ai 2
i1
i2
 ain
in
,
где Aij – подматрица матрицы A, полученная вычеркиванием в матрице A i –
й строки и j – го столбца.
4.5 Применение определителей характеристической матрицы
Определители характеристической матрицы могут использоваться для
нахождения всех путей.
Возведение структурной матрицы в степень дает все пути заданного
ранга для всей сети.
Для нахождения всех путей от узла ai к aj необходимо раскрыть
определитель подматрицы Bij , полученной из матрицы B вычеркиванием
j –й строки и i – го столбца:
mij
ji
.
4.5.1 Сечения и разрезы. Дерево путей.
При анализе топологии сети по критерию связности очень важную роль
играют такие характеристики как сечения и разрезы.
Сечением сети (графа) S называется неизбыточная совокупность
ребер, которые надо удалить из сети, чтобы нарушить ее
связность.
В сети с направленными ребрами различают направленные сечения ,
нарушающие связи от от узла ai к aj или наоборот.
Выделяют также ненаправленные сечения, полностью нарушающие
связи между ai и aj.
Каждое сечение может быть записано множеством входящих в него ребер.
Рангом сечения r(S) называется число входящих в него ребер .
- кроме сечений для всей сети, находят также сечения Sij, т. е. разрывающие
связи от узла ai к aj , либо все пути между узлами ai и aj.
- наконец, можно найти сечения, разрывающие пути заданного свойства
(например, заданного ранга).
Такие сечения называют квазисечениями Sij r . При этом пути более
высоких рангов могут оставаться и сеть останется связной.
111
Разрезом сети R называется минимальная совокупность узлов (узлов и
ребер), которые надо удалить из сети, чтобы сеть стала несвязной.
- интерес представляют также разрезы Rij по отношению к узлам ai и aj,
исключающие все пути между этими узлами.
Вводятся также понятия квазиразрезов Rij r , исключающие пути заданного
свойства (рангом r и меньше). Поясним введенные понятия на примере.
Рис. 4.5 к примеру понятия квазиразрезов
2
●
b
a
●3
e
1 ●
c
d
●
4
Пример
Для графа, представленного на рисунке 4.5:Сечение S13 = {ac , ad, bec, bd} –
т. е. множество всех сечений, разрывающих связь между узлами 1 и 3. Следует
обратить внимание на то, что сечение aed не входит в множество S13 ,
поскольку является избыточным и поглощается сечением ad.
Квазисечение ранга r
S132
2 есть:
ac, ad, bc, bd ,
однако связность между узлами 1 и 3 остается – это путь aed , но это путь
третьего ранга.
Разрез по узлам – от узла 1 к узлу 3  R13 = {a2, a4}.
Разрез по узлам и ребрам.
R13={a2c, a2d, a4d, a4b}.
Для нахождения сечений и квазисечений
следующий формализованный алгоритм..
пр именяется
1. находятся пути в сети:
- если требуются пути для всей сети, тогда находится характеристическая
матрица, содержащая все пути для всей сети (путем возведения структурной
матрицы в степень qmax – когда элементы матрицы перестают изменяться);
- если требуются пути ранга не выше заданного, тогда структурная матрица
возводится в степень, равную требуемому рангу;
- если требуются пути между заданной парой узлов, то в этом случае они
находятся путем раскрытия определителя структурной для соответствующих
строки и столбца.
112
2. полученное множество путей представляет собой сумму произведений
символов ребер, образующих данный путь. При этом каждое слагаемое
заключается в скобки.
3. все знаки сложения заменяются знаками умножения , а знаки умножения
– знаками сложения.
4. раскрываются скобки и выражение преобразуется к сумме произведений.
5. каждое из слагаемых полученного выражения будет представлять одно из
возможных сечений (или квазисечений).
2
1
a
0
0
b
a
1
0
d
c
g
0
e
1
g
f
h
0 d
b 0
g
f
1
h
h
1
d
a
e
1
c
4
3
f
b
5
Пример: обратимся вновь к рассмотренному ранее графу. Для иллюстрации
применения формализованного алгоритма найдем все пути между узлами 1 и
5 графа сети с использованием определителя:
вычеркиваем в структурной матрице B пятую строку и первый столбец.
Получаем подматрицу B51 , т. е.
m15
a
1
e
0
0
1
0
d
g
b
c
f
раскрываем
определитель
по первой
d
g
1
h
строке
0
d
c
1
0
d
a 1
g
g
1
f
h
b e
d
1
g
g
1
Второй определитель в этой формуле по свойству определителей равен 1, а
первый вычислим, пользуясь правилом вычисления определителя третьего
порядка:
m15
b a
b adf g
0 d
c
0 d
1
g
f
1
g
g
1
h
g
1
b a df g c dh
В
результате
вычислений
adh ac
получили :
113
- путь 1 – го ранга
1
15
- путь 2 – го ранга
2
15
ac;
- путь 3 – го ранга
3
15
adh;
b;
4
- путь 4 – го ранга 15 adf g.
- найдем квазисечения между узлами 1 и 5 для путей ранга не выше 2. Это
пути:
m15r 2
S15r 2
b ac .
b a c
ba bc .
Следует помнить, что пути более высокого ранга остаются.
- для квазисечения между узлами 1 и 5 ранга не выше 3 – го множество
путей можно представить выражением:
m15r 3 b ac adh.
Для нахождения сечений и квазисечений в соответствии с
формализованным алгоритмом в полученном множестве путей :
- все знаки сложения заменяются знаками умножения,
- а знаки умножения – знаками сложения;
- затем раскрываются скобки, и выражение преобразуется к сумме
произведений;
- в результате преобразований каждое слагаемое полученного выражения
будет представлять одно из возможных сечений (или квазисечений).
Итак, в соответствии с алгоритмом:
m15r 3 b ac adh
b a c
a d
h .
r 3
Раскрывая скобки в формуле для множества путей m15 , получим
квазисечения между узлами 1 и 5 ранга не выше третьего:
S15r 3
b a c
a d
h
ba bc
a d
h
.
ba bca bad bcd bah bch
Рассмотренный формализованный алгоритм нахождения
квазисечений можно применить и для нахождения разрезов:
сечений
и
- только по узлам;
- или по ребрам и узлам.
Для этого необходимо записать множество путей с использованием узлов
или ребер и узлов соответственно.
114
Например, множество путей ранга не выше третьего по узлам (от узла 1 к
узлу 3):
m13r 3
a5
a2 a4
a5 a4
a2 a5 .
Отсюда в соответствии с алгоритмом получим
после
r 3
13
R
a5 a2
a4
a5
a4
a2
a5
преобразований
получим
a5 a2
a5 a4
Отсюда следует, что существует два разреза ранга r ≤ 3 по узлам:
a5; a2 и a5; a4.
Аналогично, можно найти разрезы по узлам и ребрам.
4.5.2 Дерево путей
Часто при структурном анализе сетей ставится задача нахождения всех
путей от данного узла ко всем остальным узлам сети.
В общем виде эта задача решается нахождением характеристической
матрицы, но при этом решается задача нахождения для всех узлов.
Для одного узла эта задача решается проще – построением дерева
путей, которое строится по структурной матрице сети.
Используется следующий алгоритм:
1. выделяем исходный узел ai, который является корнем дерева путей, и
просматриваем строку в структурной матрице B, соответствующую узлу ai
. выбираем те узлы, где ребра существуют, т. е.
bij ≠ 0 и bij ≠ 1.
Полученные узлы образуют множество узлов 1–го ранга (узлы первого
яруса).
2. просматриваем строки структурной матрицы сети, соответствующие
узлам первого яруса и выбираем узлы следующего яруса.
3. продолжаем выполнять пункт 2 до тех пор, пока для данного пути
перестают встречаться новые узлы.
Если граф сети ориентированный, то деревья путей от узла ai и к узлу ai
могут быть различными.
Проиллюстрируем применение алгоритма нахождения всех путей от
данного узла ко всем остальным на примере графа сети, уже
рассматривавшегося ранее.
115
2
1
a
0
0
b
a
1
0
d
c
g
0
e
1
g
f
h
0 d
b 0
g
f
1
h
h
1
d
a
e
1
c
3
f
b
4
5
Пусть задана сеть, которая описывается направленным графом, в состав
которого входит пять узлов и два направленных ребра.
Построим дерево путей от узла 1 (корень дерева) ко всем остальным
1.
просматриваем строку «1». – Есть пути к узлам 2 и 5. это пути 1-го
ранга a и b соответственно.
2.
просматриваем строки 2 и 5:
- для второго узла (строки) существуют пути к узлам 4 и 5, - это пути d и c
-для узла 5 пути существуют к узлам 3 и 4, - это пути f è h
3.
далее просматриваем строки 3, 4 и 5.
- Для узла 3: пути существуют к узлам 2 и 4, - это пути e è g
- для узла 4: через узел 5 пути существуют к узлам 2 и 3 – это пути d è g
или через узел 2 к узлам 3 и 5 – это пути g è h
4.
далее просматриваем строки 2, 3, 4 и 5.
- для узла 2 (через узел 4) – тупик.
- для узла 2 (через узел 3) – путь к узлу 4 - d .
- для узла 3 (через узел 5) - путь к узлу 4 - g
- для узла 3 (через узел 4) - путь к узлу 5 - f
- для узла 3 (через узел 5 и 4) - путь к узлу 2 - g
- для узла 4 (через узел 5) - путь к узлу 3 - g
- для узла 4 (через узел 3) - путь к узлу 2 - d
- для узла 5 (через узел 2 и 4) - путь к узлу 3 - f
116
r=0
r=1
r=2
r=3
g
d
a
3
f
3
g
3
5
4
g
h
1
d
2
f
5
h
c
b
r=4
f
5
4
2
f
3
e
4
3
4
d
g
5
h
2
4
d
2
4
g
e
3
2
Рис.4.6 дерево путей для узла 1
Используя дерево путей легко записать множество путей от корневого
узла до любого другого узла сети.
m13
Например, запишем все пути от узла 1 до узла 5:
m15 b a c a d h a d g f .
Или от узла 1 до узла 3:
b f a d g a c f b h g a d h f a c h g
117
4.6 Нахождение путей с минимальным весом
Для минимизации времени доставки сообщений по сети их распределение
(маршрутизация) производится с учетом «длины» (веса) пути.
Естественно, что транспортировка сообщений по сети должна
производится по маршрутам (путям), гарантирующим минимальное время
доставки.
Для оценки «длины» пути могут быть использованы различные
показатели:
- число транзитных узлов;
- протяженность (физическая длина) пути;
- пропускная способность пути;
- качество передачи для данного пути;
- надежность пути;
- стоимость пути и т. д.
Например, в мультисервисных сетях большое значение имеет время
задержки при доставке сообщений.
Кратчайшим путем (путем с минимальным весом) называется путь, для
которого критерий длины пути (вес) имеет наименьшее значение по сравнению
с другими возможными путями.
Все методы выбора путей с минимальным весом основаны на
свойстве аддитивности:
если путь от узла a i к узлу a j является кратчайшим, то кратчайшие пути между
промежуточными узлами являются частями кратчайшего пути от узла от узла
a i к узлу a j .
Минимальные веса путей будем находить путем последовательного
возведения в степень матрицы весов графа сети.
1. Матрица весов получается из структурной матрицы заменой:
- буквенного обозначения ребер соответствующими весами;
- «нулей» - на « »;
- «1» на главной диагонали - на «0».
2. процедура перемножения матриц весов при возведении в степень
заменяется специальной операцией Δ.
Содержание операции Δ заключается в следующем:
Если имеются квадратные матрицы A aij è B
порядка N , то
ij
получим новую матрицу
A B
ij , элементы которой
ij – определяются
как минимум из почленной суммы i-ой строки матрицы A и j-го столбца
матрицы B :
ij
i1
1j
;
i2
2j
;
iN
Nj
.
Возведение в степень с помощью операции заканчивается на шаге qmax ,
после которого элементы матрицы весов Lq перестают меняться (в этом случае
118
все элементы вида « » заменяются на числовые значения, которые не
меняются при возведении матрицы L в степень q qmax .
Таким образом, матрица Lq
является матрицей минимальных
весов или кратчайших путей.
Пример:
Сеть описывается направленным (ориентированным) графом с пятью
узлами и шестью ребрами.
Граф сети и структурная матрица B представлены на рис.
max
2
b;25
a;50
f;20
1
3
c;6
d;10
e;8
5
4
Рис.4.7 К примеру нахождения путей минимального веса
(кратчайших путей)
1 a 0
a 1 b
0 b 1
0 0 c
0
f
c
1
e
0
0
d
8
первая строка матрицы L
0 50
8
50 0 25 20
B
L
25 0 6
6 0 10
8
10 0
e 0 0 d 1
Возведем во вторую степень матрицу L , т.е.
L2 L L .
Например, элемент этой матрицы l142 получается применением операции
к первой строке и к четвертому столбцу матрицы L :
0 50
20 6 0 10
четвертыйстолбецматрицы L .
__________
_______
70
18
В результате получим
l142 min , 70, , , 18 18 .
Применяя операцию
при возведении матрицы L во вторую степень
получим:
119
0
2
L
L L
50 75 18
8
50 0 25 20 30
75 25 0 6 16 .
18 31 6 0 10
8 58 16 10 0
Возведем матрицу L в третью степень:
0 49 24 18 8
3
L
2
L
L
38 0 25 20 30
24 25 0 6 16 .
18 31 6 0 10
8 41 16 10 0
В общем случае количество шагов возведения в степень равно
максимально возможному рангу пути , т.е. qmax rmax N 1.
Для нашего примера N 5 , и rmax 4 . Следовательно, в общем случае,
после возведения матрицы L в четвертую степень qmax 4 с применением
операции элементы матрицы Lq меняться не будут.
q
Однако в нашем примере элементы матрицы L перестают меняться
уже после q 3 .
max
Следовательно,
минимального веса.
матрица
L3
и
будет
матрицей
путей
120
5
Анализ временных параметров звена данных сети с пакетной
коммутацией
5.1 Модель звена передачи данных как системы массового
обслуживания (СМО).
Звено передачи данных в сети с пакетной коммутацией представляет
2-ой уровень иерархии в ЭМВОС, т.е. канал передачи данных (КПД) .
Звено ПД как СМО характеризуется следующими параметрами:
1. Верность передачи;
2. Скорость передачи данных;
3. Время доставки сообщения;
4. Длина очередей в буферных устройствах;
5. Время пребывания в звене данных;
Все перечисленные параметры случайны. Для их оценки используют
методы теории массового обслуживания (ТМО).
В рамках этой теории можно рассматривать:
потоки сообщений - как заявки на обслуживание,
а технические средства звена передачи данных – как приборы
обслуживания.
Рассмотрим процесс передачи сообщений.
Передача сообщений по звену данных осуществляется обычно в порядке
поступления.
Сообщения, поступающие на прибор обслуживания, в промежуток
времени, когда он обрабатывает предыдущий кадр, необходимо записать в ЗУ и
поставить в очередь.
При большой интенсивности поступления кадров ЗУ может
переполняться, что, в свою очередь, может привести либо: к отказам, либо
время передачи резко возрастает (длинная очередь).
В этой связи возникает необходимость оценки следующих параметров:
Время передачи кадра по звену и распределение этого времени. Если
оценка самого параметра невозможна - то основных моментов распределения
времени передачи.
Степень загрузки канала связи.
Средний объем необходимой буферной памяти в маршрутизаторах и
коммутаторах.
Аналитический анализ и выбор варианта построения звена данных.
Для решения перечисленных задач чаще всего используются методы
ТМО.
Любая СМО описывается своей структурой и функциональными связями
между элементами этой структуры.
Наиболее общая структура СМО имеет вид:
121
Очередь
Приборы
обслуживания
Входящий
поток
Выходящий
поток
Рис. 5.1 общая структура СМО
Для описания СМО Кендаллом в 1953 была предложена система
обозначений, которая имеет вид: А/B/C/D, где
А – вид распределения входящего потока
В – вид распределения времени обслуживания
С – количество обслуживаемых приборов
D – допустимая длина очереди.
Кроме того,
Кендалл ввел специальные обозначения законов
распределения для входящего потока и времени обслуживания.
В частности:
М – Пуассоновское распределение
Д – детерминированное распределение
Ек – Эрланговское распределение к-го порядка
Кn – распределение χ2 с n – степенями свободы.
G – произвольное распределение
Например, запись М/M/S/ обозначает:
- входящий поток – пуассоновский;
- время обслуживания – экспоненциальное;
- S – число обслуживающих приборов;
- Очередь может быть .
Звено передачи данных чаще всего анализируется при использовании
следующей модели M/G/1
5.2 Входящий поток
В большинстве используемых моделей СМО распределение входного
потока считается пуассоновским или простейшим.
Простейший поток обладает следующим свойствами:
Пуассоновское распределение числа заявок в фиксированном
промежутке времени :
(
)k
(1.1)
e ,
0, k 0, 1, 2...
k!
где
- плотность (интенсивность) потока или среднее число событий в
потоке за единицу времени.
- среднее число событий в потоке, приходящееся на интервал
длительностью ;
P( k , )
122
Если заявки поступают в случайные моменты времени, то, очевидно,
промежутки времени между этими моментами являются случайными
величинами.
Для пуассоновского потока (1.1) промежутки времени между любыми
двумя непосредственно следующими друг за другом моментами поступления
заявок на обслуживание являются независимыми случайными величинами с
одной и той же плотностью вероятности
e t, 0 t
W1 (t )
.
Это означает, что для пуассоновского потока промежутки времени
между двумя последовательными моментами поступления заявок подчиняются
показательному закону распределения.
Таким образом, имеем экспоненциальное распределение времени Т
между заявками с характеристиками:
F1 (t ) P(T t ) 1 e t - интегральная функция распределения;
.- плотность вероятности;
W1 (t )
e t, 0 t
1
- математическое ожидание;
mt
2
t
1
2
- дисперсия.
Стационарный пуассоновский поток (простейший поток) должен
обладать следующими тремя специальными свойствами:
- стационарностью;
- отсутствием последействия;
- ординарностью.
Поток событий называется стационарным, если все его вероятностные
характеристики не меняются во времени.
В частности, для стационарного потока его интенсивность
постоянна
t
t
const
Поток событий называется потоком без последействия, если для
любых непересекающихся интервалов времени 1 , 2 , , n ,
τ1
τ2
t
0
t1
X1
t2
X2
числа событий X1 X t1, 1 , X 2 X t2 , 2 , , попадающих на эти участки,
представляют собой независимые случайные величины, т.е. вероятность
123
попадания любого числа событий на один из участков не зависит от того
сколько их попало на другие участки.
Ординарным называется поток – в котором события появляются
поодиночке, а не «пачками»:
Рассмотрим элементарный интервал
t , примыкающей к точке t (см. рис.)
Δt
t
0
t
t+Δt
Ординарность потока означает, что вероятность попадания на
интервал t двух или более событий пренебрежимо мала по сравнению с
вероятностью попадания на него ровно одного события.
Широкое применение в качестве модели входного потока событий
простейшего потока обусловлено следующим:
Простейший поток в ТМО играет ту же роль, что и нормальное
распределение в теории вероятностей.
В частности, при сложении нескольких потоков с произвольным
распределениями получаем поток, близкий к простейшему
К простейшему потоку труднее приспособиться обслуживающему
прибору.
При этом если прибор имеет достаточно хорошие характеристики
обслуживания простейшего потока, то обслуживание потоков с другими
распределениями будет надежнее.
Для других моделей потоков не получены простые аналитические
зависимости, что затрудняет математический анализ существующих СПДС, а
также разработку и оптимизацию новых.
По причинам, изложенным выше, при анализе и синтезе звена данных в
подавляющем большинстве используется в качестве входного модель
простейшего потока.
5.3 Время обслуживания
Для идеального случая время обслуживания соответствует времени
передачи кадра по звену:
ТК=L\C,
где L – длина кадра в битах;
С – пропускная способность канала ПД (бит/с).
В реальных условиях время передачи по звену в является величиной
случайной за счет применения алгоритмов повышения верности. Так как
124
ошибки в канале возникают в случайные моменты времени, следовательно, и
количество переспросов (при использовании РОС) будет случайным.
Обозначим время передачи по звену через
и найдем распределение
времени передачи по звену (по дискретному каналу без памяти) при
использовании для повышения верности алгоритм РОС-НП).
Такой канал удовлетворительно описывается биномиальной моделью,
что обусловлено следующими причинами:
Длина кадра, как правило, превышает длину пакета ошибок, поэтому
запросы повторных передач можно считать независимыми.
Оптимальная длина кадра превышает интервал корреляции ошибок.
а) Если при приеме кадра ошибки не обнаруживаются с вероятностью P1 ,
то время передачи кадра будет равно Tk , т.е. P
Tk P1
б) При обнаружении ошибки в кадре по обратному каналу передается
запрос, по которому передатчик прямого канала повторяет h кадров.
Tn
Время передачи дополнительных кадров Tn по сигналу запроса равно
h Tk
Тогда, с учетом введенного обозначения, время передачи кадра после i-го
запроса на повтор определяется выражением:
Tk i Tk i 1 Tn
Или с учетом выражения для Tn получим
Tk i Tk
h i 1 Tk
Вероятность этого события (что для передачи кадра потребуется время Tk i )
равна
P
Tk i
P1 P2i 1
Где P2 – вероятность обнаружения ошибки в передаваемом кадре.
Очевидно, что P2 1 P1
Так как случайная величина Tk i может принимать только дискретные
значения, поэтому для получения интегральной функции распределения этой
С.В. введем понятие единичной функции:
1(t )
0, для t 0
1, для t 0
В результате функция распределения F(t Т k i
имеет вид:
времени передачи кадра
125
F (t Т k i
P1 P2i
1
1(t Т k i )
i 1
Плотность распределения вероятностей W t определим осуществляя
формальное дифференцирование интегральной функции распределения
F(t Т k i
В результате получим:
P1 P2i
W (t )
1
(t Tk i )
i 1
0, при х 0
,
при х 0
где (t Tk i ) – дельта функция: ( x)
а Tk i
Tk
h i 1 Tk
W(t)
i=2
i=1
i=3
TK+hTK
TK
t
TK+2hTK
Рис.5.2 распределение времени обслуживания заявок в звене данных при
использовании РОС-НП.
5.3.1 Параметры распределения времени передачи по звену данных при
использовании РОС-НП.
Математическое ожидание.
М[ ]
0
t dF(t ) - (интеграл Стилтьеса)
или с учетом F (t Т k i
P1 P2i
1
1(t Т k i )
i 1
М[ ]
0
P1 P2i
t
1
{t [(i 1)hTK TK ]}dt
i 1
После интегрирования (с учетом фильтрующего свойства
получим:
М[ ] Тk
P1 P2
i 1
i 1
h TK
(i 1)P1 P2
- функции)
i 1
i 1
Используя свойства геометрической прогрессии:
126
S
a1 1 q
a1
P1 ; q
P2
получаем
h P2
] -среднее время передачи кадра по звену.
P1
M [ ] Tk [1
Дисперсия времени передачи кадра по звену данных.
2
M[  2 ] M[
где М [ 2 ]
2
] M
2
2
M
2
M
2
,
t 2 dF(t ) ,
0
или М [ 2 ]
t2
P1 P2
i 1
{t [Tk
(i 1)hTk ]}dt
i 1
0
После интегрирования этого выражения с учетом фильтрующего свойства
- функции получаем
М [ 2 ] T 2 2Tk2
h P2
h 2 (1 P2 )
Tk2
(1 P2 )
(1 P2 ) 2
или М [ ] (М [ ])
2
2
2
K
T
h 2 P2
P1
2
В результате получаем:
2
[ ] (Ì [  2 ]) TK2
h2 P2
2
P1
Коэффициент вариации C[ ]
Показывает
ожидания
отклонение
[ ]
M[ ]
C[ ]
случайной
величины
от
математического
h P2
P1 hP2
Свойства коэффициента вариации
Если С=0 - имеем детерминированный случай.
5.3.2 Параметры распределения времени передачи по звену данных при
использовании РОС-ОЖ
Параметры распределения времени передачи кадра по звену данных
M ; 2 ; C[ ] для алгоритма РОС-ОЖ можно получить положив h 1 :
M [ ] Tk [1
2
( ) Tk
C( )
2
P2
1 P2 P2
] Tk
P1
1 P2
Tk
1 P2
P2
P12
Tk P2 (1 P2 )
(1 P2 ) Tk
P2
127
Из этих соотношений видно, что при вероятности неудачной передачи
кадра P2 0 параметры распределения C
0; M
Tk .
Следовательно, в хорошем канале, время передачи
детерминированным.
TK, т.е. становится
5.4 Среднее время задержки сообщения
Этот параметр определяет длину очереди в звене ПД и зависит от
следующих факторов:
1.
Количества сообщений в очереди;
2.
Времени окончания предыдущих кадров;
3.
Интенсивности входного потока.
На практике анализируют, как правило, установившийся режим работы
СМО (в нашем случае звена передачи данных), так как расчет переходных
режимов затруднен.
Признаком установившегося режима служит неравенство
1,
где
- коэффициент нагрузки, или коэффициент использования системы:
M ,
где
- интенсивность входного потока сообщений.
1 , то установившегося режима быть не может, так как очереди
Если же
будут расти бесконечно.
Поскольку получение аналитического выражения для распределения
времени задержки кадра достаточно сложно, то обычно ограничиваются
вычислением моментов этого распределения.
Пусть время задержки кадра , тогда для модели СМО вида M/G/1
известна формула Поллачека-Хинчина.
М[ ]
M[ 2 ]
2(1 )M [ ]
Зная задержку, можно оценить общее время пребывания кадра в
звене данных.
Обозначив время пребывания кадра в звене данных через , тогда
M[ ]
M[ ] M[ ]
Используя формулу Литтла можно определить среднее количество
кадров в очереди, т.е. среднюю длину очереди (в установившемся
режиме).
Обозначив длину очереди через N, тогда M N
где
M
,
-интенсивность входящего потока сообщений.
128
Определим средний объем накопителя для хранения кадров в
очереди на передаче: M H L M N .
где H - объем накопителя [Байт]
L
– длина кадра [Байт]
M H – средняя длина очереди [в кадрах]
5.5 Выходящий поток.
Передачу сообщений в любой связной системе или сети можно
рассматривать как многофазное обслуживание, когда сообщение сначала
обслуживается в одной СМО, а затем переходит в другую СМО. Поэтому
целесообразно
оценивать
характер
выходящего
потока
после
обслуживания.
Можно предположить, что поток, выходящий из СМО, будет совпадать по
характеру с входящим потоком сообщений.
Пусть в выходящем потоке кадры следуют друг за другом через
интервалы времени x1 , x2 , , xn .
Эти интервалы времени определяются:
- свойствами входящего потока
- и распределением времени обслуживания.
Имеет место следующая зависимость для математического ожидания
простейшего потока:
M x
,
1
которая справедлива для простейшего
установившемся режиме обслуживания.
выходящего
потока
в
Таким образом, интенсивности входящего и выходящего потоков (для
случая простейшего выходящего потока и установившегося режима
обслуживания) равны.
Дисперсия для выходящего потока х определяется выражением:
2
где
[ x]
2
[ ]
2
[ ]
2
[ ],
- интервал времени между кадрами во входящем потоке.
Из выражения для 2[ x] видно, что дисперсия интервалов времени между
кадрами выходящего потока отличается от дисперсии интервалов
времени между кадрами входящего потока.
Эта зависимость справедлива для любого алгоритма с обратной связью.
129
Коэффициент вариаций для интервалов времени между кадрами
выходящего потока определяется выражением:
C[ x]
[ x]
M [ x]
1 (1 C 2 )
2
Коэффициент вариации определяет последействие потока и показывает,
что выходящий поток, скорее всего, будет не простейшим и обладать
последействием (памятью).
Этот факт существенно затрудняет последующий анализ сетей передачи
данных и сетей ЭВМ, поскольку выходящий поток звена данных, поступает
затем на 3-ий (сетевой) уровень.
130
5.6 Достоверность работы звена данных.
Статистические характеристики звена передачи данных во многом
определяется верностью
передачи
дискретного
канала , т.е.
вероятностью ошибки на единичный элемент (е.э.)
Верность
же
звена
вероятностями P1 и P2 1 P1 .
передачи
данных
характеризуется
Вероятность P1 определяется как вероятность удачной передачи
кадра, т.е. кадр принят без обнаруженной ошибки и, кроме того, сигнал
подтверждения также принят правильно.
Вероятность P2 – вероятность неудачной передачи кадра, т.е. кадр
принят с обнаруженной ошибкой и, кроме того, сигнал запроса принят
правильно.
Дли систем с алгоритмом РОС-ОЖ и РОС-НП справедливо соотношение:
P1
1 Poo Pпод Poo P21

 
 
2
1
где 1 – вероятность приема кадра с не обнаружением ошибки и вероятностью
правильного приема сигнала подтверждения передатчиком прямого канала.
2 – вероятность того, что приемник прямого канала обнаружил ошибку в
принимаемом кадре, но сигнал запроса на повторную передачу в процессе
передачи по обратному каналу трансформировался в сигнал подтверждения.
Pоо – вероятность обнаружения ошибки в принимаемом кадре.
Pпод – вероятность правильного приема сигнала подтверждения.
P21 – вероятность перехода сигнала «запрос повторной передачи
кадра» в сигнал подтверждения, т.е. это вероятность потери кадра.
Вероятность
соотношением:
P2
неудачной
Poo Pзап 1 Poo1 P12 ,


 
1
передачи
кадра
определяется
2
2
где 1 – вероятность события, состоящего том, что на приеме ошибка в кадре
обнаружена, и сигнал запроса на повторную передачу принят правильно.
2 – вероятность события, состоящего в том, что в принимаемом кадре
ошибка не обнаружена, но сигнал подтверждение в процессе распространения
перешел в сигнал запроса.
Pзап - вероятность правильного приема сигнал «запрос».
P12 – вероятность перехода сигнал подтверждения в сигнал «запрос»:
иными словами – это вероятность вставки лишнего кадра.
131
Для определения перечисленных вероятностей используются модели
дискретного канала, связывающие вероятность ошибки на единичный
элемент с вероятностью ошибки на кодовую комбинацию (кадр).
Простейшей моделью дискретного канала (как известно) является
биномиальная модель, для описания которой достаточно одного параметра
– вероятности ошибки на единичный элемент Po .
Данная модель широко применяется на практике.
В рамках биномиальной модели дискретного канала:
- вероятность появления в n-разрядной кодовой комбинации вектора
ошибок кратности t определяется соотношением:
Cnt Pot 1 Po
P t, n
n t
.
- а вероятность безошибочного приема n-разрядной кодовой комбинации
равна:
P 0, n
1 Po
n
Вероятность обнаружения в кодовой комбинации вектора ошибок
заданной кратности зависит от используемого помехоустойчивого кода.
Если помехоустойчивое кодирование используется для защиты одной
кодовой комбинации (символа) и в кадре содержится m таких символов,
тогда:
- вероятность обнаружения ошибки в кадре
Pоб.к 1 1 Pоос
m
,
где Pоос – вероятность обнаружения ошибки в символе.
Если, например, используется код МТК-5, тогда вероятность
определяется соотношением:
Pоос
Сn1 Po 1 Po
n 1
Cn3 Po3 1 Po
n 3
Pоос

где n=8
Если помехоустойчивому кодированию подвергается весь кадр, как
например, в протоколе HDLC, тогда можно сразу рассчитать вероятность
обнаружения ошибки в кадре:
Роок
t0
СLi Poi (1 Po ) L i ,
i 1
где L – длина кадра.
В частности для кода БЧХ минимальное кодовое расстояние d0=5,
следовательно, код гарантированно обнаруживает ошибки кратности t0 4
- вероятность правильного приема (без ошибок) кадра:
132
Pппк
1 Po
m n
1 Po
L
- вероятность полной группы событий при приеме кадра:
Роок
Pппк
Pнок
1
Отсюда
Pнок
1
Роок
Pппк
Другой распространенной моделью частичного описания дискретного
канала с группированием ошибок является модель Пуртова.
Эта модель является 2-х параметрической – для описания используются 2
параметра:
Ро - вероятность ошибки на е.э.
- коэффициент группирования ошибок.
В рамках модели Пуртова характеристики канала определяются
формулами:
P( 1, n) n1
Po
n
n 1
( )1 Po (
)
t
t 1
P(t , n)
Po
- вероятность обнаружения ошибки в кадре (при использовании модели
Пуртова)
Рнок
L1
1
Po r
2
(
to 1) 1
t 1
)
(o )
L
L
to 1
to 1)
( )
(
)
L
L
Однако на практике чаще всего используется биномиальная модель.
5.7 Достоверность принятия сообщений.
Рассмотренные выше зависимости не позволяют сравнивать между собой
анализируемые системы при использовании различной длины кадра , так
как все рассмотренные вероятности зависят от длины кадра.
Пример: Пусть необходимо передать
использующими кадры различной длины.
400
разрядов
системами,
Первая система: сообщение передается кадрами длиной L1=5 е.э. и
обеспечивает вероятность правильного приема кадра Рппк=0,999
Вторая система: передает сообщение кадрами длиной L2=200 е.э. и
Рппк=0,99.
На первый взгляд 1-я система ПД обеспечивает лучшие показатели
верности.
Рассчитаем вероятность правильного приема всего сообщения из 400
е.э. для биномиальной модели дискретного канала
133
Pпрсооб
Pппк
Nk
где Nk Lсооб Lk .
1-я система:
80
Pпрс1 =[0,999] =0,923 (NK`=400/5=80 кадров)
2-я система:
2
Pпрс2 =[0,99] =0,998 (NK`=400/200=2 кадров)
Сравнение различных систем по критерию верности можно
осуществить используя понятие эквивалентной вероятности ошибки Рэ
которая для нашего случая определяется выражением:
Рэ 1
P1
1mk
,
где Р1 – вероятность удачной передачи кадра;
k – число информационных разрядов в кодовой комбинации;
m – количество кодовых комбинаций (символов) в кадре.
Получим соотношение для Рэ
1.
Пусть вероятность удачной передачи кадра по звену данных с
первой попытки
Р11
Pпп Pпод ,
где Pпп – вероятность правильного приема кадра;
Pпод
–
вероятность правильного декодирования сигнала подтверждения.
Если для удачной передачи кадра потребуется 2 попытки, тогда:
2.
Р12
Pоо Pзап Pпп Pпод .
где Pоо – вероятность обнаружения ошибки в кадре;
Pзап – вероятность правильного декодирования сигнала запроса.
Если для удачной передачи кадра потребуется i попыток, тогда
3.
Р1i
Pоо Pзап
i 1
Pпп Pпод
Тогда
Р1
Рпп Рпод
.
1 Роо Рзап
Р1(i )
i 1
С другой стороны
Р1
1 Pэ
mk
Следовательно (приравнивая эти выражения)
134
Рпп Рпод
1 Роо Рзап
(1 Рэ ) m k
1
Отсюда получаем: Рэ
1 m k PЭ .
Рпп Рпод
1 Роо Рзап
для системы РОС-ОЖ
m k
Вероятность вставки/выпадения кадров в зависимости от вероятности
ошибки в обратном канале.
- Вероятность потери кадра при однократной передаче:
1
Рпот
Pоо P21 ,
где P21 – вероятность перехода сигнала «запрос» в сигнал подтверждение.
- Вероятность потери кадра при использовании i попыток:
i
Рпот
Pоо Pзап
i 1
Pоо P21 ,
где Pзап – вероятность правильного декодирования сигнала запроса.
В итоге получаем: Рпот
(i )
Рпот
i 1
Pоо Р21
1 Роо Рзап
Для определения вероятности вставки кадра проанализируем, чем
может заканчиваться передача кадра по звену.
(1)
Запись кадра в накопитель и выдача его получателю, т.е.
регистрация кадра с вероятностью Pрег .
(2)
Потеря кадра с вероятностью Pпот .
(3)
Вставка лишнего кадра – с вероятностью Pвст .
Следовательно:
Pрег
Pвст Pпот
1
с учетом вероятности ошибки в обратном канале определяется
выражением:
Pрег
Ррег
(1 Роо ) Рпод Роо Р21
1 [ Роо Рзап (1 Роо ) Р12 ]
Зная Pпод , Pзап , а также Pрег можно определить Pвст .
Если P21 P12 и Pпод Pзап ,
тогда Pпот
Pвст .
135
6 Анализ надежности системы передачи данных
6.1
Основные понятия надежности систем ПД.
Система ПДС, как и вообще любая система, характеризуется рядом
эксплутационно-технических характеристик, а именно:
- верность доставки сообщения пользователю;
- скорость доставки сообщений;
- надежность;
- энергоемкость;
- массогабаритные показатели;
- стоимостные характеристики и т.п.
Надежностью называют свойство некоторой системы выполнять свои
функции в течение заданного интервала времени при сохранении всех
качественных показателей.
Основным, понятием теории надежности является понятие отказа.
Отказом называется событие, заключающиеся в полном или
частичном
нарушении
работоспособности
системы,
вследствие
недопустимого изменения ее эксплутационно-технических характеристик.
Обычно отказом для системы ПД считается превышение максимального
допустимого времени передачи сообщения.
Разность между допустимым и реальным временем доставки сообщения
называется критерием отказа.
Норма на величину критерия отказа устанавливается с учетом скорости
старения сообщения и представляет некоторый резерв времени на
допустимые задержки в передаче сообщения, возникающие из-за:
- нестабильность параметров канала связи;
- действие импульсных помех;
- занижение уровня сигнала;
- неполадок (сбоев) в коммутационном оборудовании;
- неправильные действия обслуживающего персонала.
Если реальные значения параметров превышают норму, то регистрируется
отказ системы.
Различают отказы:
- постепенные;
- внезапные;
- устойчивые;
- самоустраняющиеся.
Постепенные отказы в значительной мере выявляются при проведении
технического обслуживания, поэтому они не оказывают существенного
136
влияния на надежность работы систем связи. Значительно большее влияние
оказывают внезапные отказы.
Устойчивые отказы по продолжительности можно разделить на:
- длительные >30 мин.
- Средней продолжительности от 3 до 30 мин.
- Кратковременные < 3 мин.
Наиболее многочисленными являются кратковременные отказы
(действия персонала, импульсные помехи, дребезг контактов и т.п.), которые,
как правило, являются самовосстанавливающимися. 80% таких отказов
вызываются неправильными действиями персонала и 20% - импульсными
помехами.
Основные показатели надежности
6.2
Система ПД и ее составные элементы могут находиться в 2-х состояниях:
- работоспособности;
- отказа.
Поэтому для количественной оценки надежности системы используются 2
набора параметров, а также обобщенные показатели надежности.
Состояние работоспособности
Время наработки на отказ – Т0 – есть среднее значение длительности
непрерывной работы оборудования между двумя последовательными отказами:
Т0
1
N
N
Toi ,
i 1
где Toi – время нормальной работы между i-1 и i отказами.
N – общее число отказов за время испытаний.
Интенсивность отказов - плотность вероятности возникновения
отказа в заданный интервал времени или среднее количество отказов в единицу
времени.
1 To характеризует число отказов в единицу времени.
Вероятность безотказной работы – Р(t) – вероятность того, что за
заданный отрезок времени t не произойдет ни одного отказа:
Pt
e
t
.
Это экспоненциальное распределение (т.е. чем больше отрезок времени,
тем меньше вероятность безотказной работы).
Состояние отказа:
137
Среднее время восстановления – Tв есть среднее время простоя
оборудования, вызванное отысканием и устранением данного отказа:
Tв
1
N
N
Tвi ,
i 1
где Tвi – длительность i-го отказа;
N – общее число отказов за время испытаний.
Интенсивность восстановления восстановления в единицу времени:
- характеризует среднее число
1 TВ
Обобщенным показателем надежности является коэффициент готовности
– K Г , который характеризует вероятность того, что оборудование находится в
исправном состоянии в произвольный момент времени:
KГ
ТО
ТО Т В
Для расчета параметров надежности всей системы необходимо
использовать математическую модель, которая должна учитывать:
- надежность отдельных блоков, входящих в состав системы;
- структуру аппаратуры с точки зрения надежности, т.е. определяющую
зависимость вероятности безотказной работы всей системы от вероятности
безотказной работы составляющих ее блоков.
В теории надежности различают 2 базовых типа соединений блоков
(элементов) с точки зрения надежности:
- последовательное;
- параллельное.
Последовательное соединение – когда отказ одного элемента или блока
приводит к отказу всей систему в целом. Поскольку так обычно и происходит
на практике, то последовательное соединение называется основным.
Схема подобного соединения представлена на рисунке.
P1
1
P2
2
Pn
М
n
рис.6.1 Последовательное соединение компонентов
Обычно считается, что отказы отдельных блоков (элементов) являются
независимыми (т.е. отказ одного блока не ведет к отказу других блоков) и
случайными. В рамках сделанных допущений:
138
Вероятность безотказной работы:
n
Р(t )
Pj (t ) ,
j i
где P t – вероятность безотказной работы всей системы;
Pj t – вероятность безотказной работы j-го блока системы.
Интенсивность отказов
n
j
,
j i
Где
- интенсивность отказов всей системы;
j
– интенсивность отказов j-го блока системы.
Коэффициент готовности
n
K Гj ,
KГ
i j
где K Г – коэффициент готовности всей системы.
K Гj – коэффициент готовности j-го блока системы.
Время наработки на отказ
То
n
1
j
1
,
i Toj
где Т о – время наработки на отказ всей системы
Toj – время наработки на отказ j-го блока системы.
Анализ
приведенных
выражений
показывает,
что
при
последовательном соединении блоков надежность всей системы всегда
меньше надежности любого из ее элементов.
Параллельное соединение – отказ всей системы наступает только при
одновременном отказе всех ее элементов (блоков).
Схема параллельного соединения представлена на рисунке:
P1
P2
Pm
рис.6.2 Параллельное соединение компонентов
139
При такой структуре соединения, чтобы отказала вся система необходимо,
чтобы отказали все ее m элементов.
Предположим, что отказы отдельных блоков (элементов системы)
являются независимыми и случайными. В этом случае:
Вероятность безотказной работы всей системы
m
Р(t ) 1
(1 Pj (t )) ,
j 1
где Pj (t ) – вероятность безотказной работы j-го элемента.
Коэффициент готовности системы:
m
KГ
(1 K Гj ) ,
1
j 1
где K Гj – коэффициент готовности j-го элемента системы.
Вероятность наработки на отказ всей системы:
KГ
То
1
Т oj TBj
,
m
(1 K ГS )
S 1
S j
где Тoj – время наработки на отказ j-го блока системы
ТBj – время восстановления j-го блока системы
КГS – коэффициент готовности S-го блока системы
Анализ приведенных соотношений показывает, что при параллельном
соединении элементов системы надежность всего устройства будет выше
надежности его элементов. Поэтому параллельное соединение применяют для
создания надежных систем из недостаточно надежных элементов.
В реальных системах блоки и элементы соединены по разному (в
отношении надежности), т.е. имеет место смешанное соединение:
P11
Pn1
Pi1
P12
Pn2
Pi2
P1m
Pnk
Рис.6.3 Смешанное соединение компонентов
Расчет надежности подобной системы производится следующим образом:
140
(1)
сначала вычисляется
параллельных элементов;
надежность
групп
соединенных
из
(2)
затем вычисляется надежность последовательно соединенных
эквивалентных элементов.
При расчете надежности величину надежности отельных элементов
(резисторов, емкостей, м/схем и т.п.) берут из специальных таблиц.
6.3
Основные пути повышения надежности
Основные методы и пути повышения надежности представлены в виде
классификации – рис.4.
Одним из основных средств повышения надежности систем ПД является
использование различных видов резервирования отдельных блоков.
Различают 2 вида резервирования:
- постоянное;
- замещением.
При постоянном резервировании резервный элемент постоянно
подключен к основному. При этом резервный элемент может находиться в
следующих состояниях:
- холодный резерв;
- облегченный резерв;
- горячий резерв.
141
Направления повышения
надежности
1.
2.
Схемные методы
3.
4.
5.
При
разработке
1.
2.
Конструктивные
методы
3.
4.
5.
6.
1.
2.
3.
При изготовлении
4.
5.
1.
В процессе
технической
эксплуатации
2.
3.
4.
Упрощение схем
Схемы с ограниченными
последствиями отказов
Резервирование
Схемы с широкими допусками на
параметры элементов
Введение эффективного контроля
Применение надежных элементов
Унификация элементов и
конструкций
Микро миниатюризация
Нормальные режимы работы
Отбор параметров элементов
Высокая ремонтопригодность
Совершенная технология
Автоматизация произаводства
Тренировка элементов и системы
в целом
Статистический контроль
качества продукции
Повышение квалификации
производственного персонала
Внедрение научно-обоснованных
методов эксплуатации
Сбор и обобщение опыта
эксплуатации
Тесная связь с разработчиками и
изготовителями
Повышение квалификации
обслуживающего персонала
Рис.6.4. Классификация
методов повышения надежности
При замещении резервный элемент подключается взамен отказавшего.
Резервирование замещением может быть закрепленным, если основной
элемент резервируется постоянно закрепленным резервным элементом.
Резервирование замещением может быть скользящим, если любой
элемент из группы резервных может заменить любой отказавший основной
элемент.
Однако при резервировании замещением необходимы переключающие
элементы, которые тоже обладают конечной надежностью. Поэтому достаточно
трудно оценить общую надежность систем при резервировании замещением.
Если установлены очень жесткие критерии отказа,
постоянное резервирование с горячим резервом .
применяют
142
Список литературы
4. Современные компьютерные сети. 2-е изд./ В. Столлингс. – Спб.: Питер.
2003. – 783 с.
5. Компьютерные сети. 4-е изд./ Э.Таненбаум. – Спб.: Питер. 2006. – 992с.
6. http://www.compnets.narod.ru
7. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. – М.:
Мир, 1981, - 323 с.
8. Кѐниг Д., Штоян Д. Методы теории массового обслуживания: Пер. с
нем./Под. Ред. Г.П. Климова. – М.: Радио и связь, 1981.- 128с.
9. Саульев В.К. Математические модели массового обслуживания. – М.:
Статистика, 1979. – 96с.
10. Белов Теория Графов, Москва, «Наука»,1968.
11. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для
инженера. – М.: Энергоатомиздат, 1988.
12. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
13. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.:
Издательство МАИ, 1992.
14. Оре О. Теория графов. – М.: Наука, 1980.
15. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по
куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.:
МГТУ, 1995
16. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992
17. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и
сетях. - Hовосибиpск: Hаука, 1990
18. Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992
19. Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН,
1994
15. Липатов И.Н. Решение задач по курсу "Прикладная теория надежности":
Учебное пособие. - Пермь: Перм. гос. техн. ун-т, 1996. - 55 с.
16. Половко А.М., Гуров С.В. Основы теории надежности. Практикум. –
Спб.: БХВ-Перербург,2006. – 560 с.
17. Шапорев С.Д. Дискретная математика. Курс лекций и практических
занятий. – Спб.: БХВ-Петербург, 2006. – 260 с.
18. Черкесов Г.Н. Надежность аппаратно-программных комплексов. Учебное
пособие. – Спб.: Питер, 2005. - 479
143
Документ
Категория
Без категории
Просмотров
0
Размер файла
2 559 Кб
Теги
zaiki, apparat, parametrov, paket, algoritm, sredstv, metod, analiz, setyam, marshrut, kommu
1/--страниц
Пожаловаться на содержимое документа