Содержание к диссертации
Введение
ГЛАВА 1. Определение модели для исследования и разработки алгоритмов передачи мультимедийного трафика в современных IP-сетях 10
1.1. Применение объектно-ориентированного проектирования для моделирования сетей ЭВМ 10
1.2. Проблема качественной передачи мультимедийного трафика в ІР-сетях 16
1.3. Методы оптимизации качества передачи мультимедийного трафика в современных ІР-сетях 22
Выводы 35
ГЛАВА 2. Исследование и разработка адаптивных алгоритмов маршрутизации в мультисервисных ІР-сетях 36
2.1. Распределенный адаптивный алгоритм IP-маршрутизации с обратной связью 36
2.2. Механизм расчета метрики алгоритма маршрутизации DARL 48
2.3. Реализация алгоритма маршрутизации DARL в операционной системе Linux 52
Выводы 56
ГЛАВА 3. Разработка программы объектно-ориентированного имитационного моделирования мультисервисной IP-сети 57
3.1. Обобщенная объектно-ориентированная имитационная модель мультисервисной IP-сети 57
3.2. Программная реализация объектно-ориентированной имитационной модели мультисервисной сети 77
3.3. Оценка адекватности имитационной модели 82
Выводы 90
ГЛАВА 4. Оценка эффективности работы распределенного адаптивного алгоритма ip-маршрутизации с обратной связью 91
4.1. Аналитическая оценка эффективности работы системы маршрутизации 91
4.2. Аналитическая модель оценки эффективности работы алгоритмов маршрутизации 97
4.3. Интегральная оценка качества работы системы маршрутизации 104
4.4. Оценка эффективности работы алгоритма DARL на основе результатов имитационного
моделирования 107
Выводы 112
Заключение 113
Библиографический список
- Проблема качественной передачи мультимедийного трафика в ІР-сетях
- Механизм расчета метрики алгоритма маршрутизации DARL
- Программная реализация объектно-ориентированной имитационной модели мультисервисной сети
- Аналитическая модель оценки эффективности работы алгоритмов маршрутизации
Введение к работе
Характерной тенденцией современного этапа развития компьютерных сетей является принципиальное изменение структуры передаваемого трафика. Причиной тому является бурный рост разработок новых Интернет-приложений, изменение пропорций между уже существующими и вновь создаваемыми сетевыми услугами, а также конвергенция телекоммуникационных систем (традиционная телефония, сотовые сети связи, кабельное телевидение и т.д.) с сетью Интернет.
Анализ статистики агрегированного трафика большинства сетей доступа в Интернет, а также корпоративных сетей крупных предприятий явно показывает высокую долю в нем аудио- и видео- потоков данных. IP-телефония, IP-телевидение и видеоконференции являются самыми стремительно развивающимися сетевыми услугами нового поколения /11, 90/. Таким образом, можно определенно утверждать, что трафик сетей доступа в Интернет, а также сетей крупных предприятий, стал мультимедийным, если под этим термином понимать относительно равномерное распределение долей аудио, видео и других типов потоков данных.
При этом постоянно разрабатываются и внедряются новые алгоритмы, протоколы и технологии, которые в определенной степени улучшают качество передачи трафика реального времени в IP-сетях. Следствием этого является существенное усложнение архитектуры сетей TCP/IP, которые теперь характеризуется не просто как сети передачи данных, а как мультисервисные, делая в этом определении акцент на на разнообразность сетевых приложений.
Все это делает применение аппарата аналитического моделирования для исследования вновь создаваемых алгоритмов и протоколов достаточно сложным, а зачастую и невозможным. Альтернативным подходом являются имитационные модели компьютерных сетей, которые могут быть сколь угодно близки к моделируемой системе. В числе научных школ, внесших серьезный вклад в проблематику разработки имитационных моделей мультисервисных
5 сетей, следует перечислить многие исследовательские центры. В США - это Колумбийский университет (Н. Schulzrinne и W. Jiang), Национальная лаборатория им. Лоуренса (S. Floyd) и Калифорнийский университет в г. Беркли (С. Chuah), в Германии - Институт открытых систем FOKUS (Н. Sanneck), в Великобритании - Лондонский университет UCL (J. Crowcroft), во Франции - Национальный институт INRIA (J-C. Bolot), в Италии -Политехнический институт в г. Турине (J. С. de Martin), в Финляндии -Технологический университет в г. Хельсинки. Среди отечественных центров, в первую очередь, следует отметить Санкт-Петербургскую научную школу: ЛОНИИС (Б. С. Гольдштейн) и Университет телекоммуникаций им. Бонч-Бруевича, а также ряд исследовательских институтов РАН: Московский институт проблем передачи информации РАН (С. Н. Степанов), Институт проблем информатики РАН (С. Я. Шоргин) и др.
При этом в большинстве существующих сетевых симуляторов создание и внедрение модуля вновь разрабатываемого протокола затрагивает если не всю, то большую часть архитектуры имитационной модели сети, так как возникает необходимость модификации других модулей. Таким образом, при внедрении новых и замены существующих сетевых объектов возникает необходимость изменения концептуальной структуры модели. Как следствие, возникает зависимость между разработчиками, что нежелательно.
Более того, существует проблема обработки данных, получаемых на выходе работы модели. Зачастую они представляют собой трассировочный дамп, отражающий историю прохождения пакетов по сети, и в общем случае для его анализа необходимо создание дополнительной программы.
Ярким примером наличия указанных проблем является безусловный лидер среди симуляторов с открытым кодом network simulator-2 (ns-2). Большинство результатов в научных публикациях, связанных с исследованием сетей связи, апробируются с привлечением именно этого инструмента. При этом, как показывает анализ почтовой переписки пользователей данного симулятора 121,
большинство проблем связано именно с программной реализацией новых алгоритмов и протоколов сетей связи в рамках пакета ns-2.
В этой связи актуальной является задача применения концепции объектно-ориентированного проектирования и анализа для построения имитационной модели мультисервисной сети.
Целью данной работы является разработка и реализация объектно-ориентированной имитационной модели мультисервисной сети и создание с ее использованием алгоритма, улучшающего качественные характеристики передачи мультимедийного трафика. В рамках диссертационной работы решались следующие основные задачи:
Анализ математических моделей источников основных типов трафика мультисервисных сетей связи
Анализ топологий сетей современных Интернет-провайдеров.
Разработка объектно-ориентированной имитационной модели мультисервисной сети.
Выбор программного обеспечения для реализации разработанной имитационной модели.
Разработка распределенного адаптивного алгоритма IP-маршрутизации с обратной связью и включение его программно реализующего модуля в состав сетевого симулятора.
Оценка адекватности разработанной модели с использованием стенда натурного моделирования.
Оценка эффективности работы разработанного алгоритма с использованием полученной имитационной модели.
Основные научные результаты диссертации заключаются в следующем: 1. Предложена новая имитационная модель мультисервисной IP-сети с адаптивной маршрутизацией, разработанная и формализованная средствами языка UML. Основным отличием модели является использование объектно-ориентированного подхода для представления составляющих её
7 компонентов и связи между ними. Данный подход обеспечивает архитектурное и функциональное соответствие модели стеку протоколов TCP/IP, простоту внедрения новых и замены существующих классов сетевых объектов без изменения концептуальной структуры модели; возможность независимой работы нескольких исследователей и разработчиков новых сетевых протоколов и алгоритмов; возможность настройки выходных данных модели под задачи исследования.
Предложена новая модель сетевой топологии - «многоканальность», которая, как показал анализ сетей Интернет-провайдеров, является наиболее актуальной при моделировании современных сетей передачи данных.
Разработан новый распределенный адаптивный алгоритм IP-маршрутизации DARL, который учитывает особенности типовой топологии Интернет-сетей. Новизна алгоритма заключается в наличии обратной связи между узлами маршрутизации, а также в том, что пакеты данных одновременно являются служебными сообщениями о состоянии каналов и в рамках процедуры маршрутизации учитывается вероятность сброса пакета на том или ином сетевом интерфейсе.
Предложена новая интегральная методика, существенно упрощающая сравнительную оценку качества алгоритмов маршрутизации на основе следующих базовых характеристик: производительность системы маршрутизации, стоимость доставки данных, процент потерь, задержка при передаче и джиттер. Новизна методики заключается в том, что оценка производится всего лишь по одному комплексному критерию.
К практическим результатам работы можно отнести следующее: 1. Программная реализация разработанной имитационной модели в среде AnyLogic. Модель позволяет эмулировать сети с произвольными топологиями. Данную модель можно применять как в учебном процессе, так и для исследования работы сети любой организации.
Натурный стенд измерений качественных характеристик мультимедийного трафика для проверки адекватности модели. Данный стенд использовался для получения выборок таких величин как процент потерь трафика, задержка передачи и джиттер. Стенд может применяться в учебных целях и для отладки механизма работы сетевых алгоритмов и протоколов.
Реализация распределенного адаптивного алгоритма маршрутизации с обратной связью DARL в операционной системе Linux на базе пакета Click Modular Router. Экспериментальная проверка эффективности предложенного алгоритма показала, что при его использовании достигается улучшение следующих параметров - потери трафика и производительность системы маршрутизации.
Основные результаты диссертационной работы внедрены в учебном процессе кафедры ЭВМ Южно-Уральского государственного университета, а также в сети Интернет-провайдера "Интерсвязь" (г. Челябинск). Копии актов внедрения представлены в приложении к диссертационной работе.
Апробация работы. Основные положения диссертационной работы докладывались на:
совещании научно-методического совета по информатике при Министерстве образования и науки РФ «Актуальные проблемы информатики в современном российском образовании», Москва, 27-29 июня 2005 г.;
международной конференции «Computer Science and Information Technologies CSIT'2005», Уфа, 18-21 сентября 2005 г.;
международной конференции «Современные информационные технологии и ИТ-образование», Москва, 20-22 сентября 2005 г.;
расширенном заседании кафедры ЭВМ Южно-Уральского государственного университета, Челябинск, 2 июня 2006 г.;
всероссийской научной конференции «Математика. Механика. Информатика», Челябинск, 19-22 сентября 2006 г.;
расширенном заседании кафедры СП Челябинского государственного университета, Челябинск, 25 января 2007 г.;
расширенном заседании кафедры СП Южно-Уральского государственного университета, Челябинск, 16 марта 2007 г.
Публикации. По материалам диссертации опубликовано 9 печатных работ, в том числе 1 в рецензируемом журнале из списка периодических изданий, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографии и приложения. Текст диссертации изложен на 126 листах, включая 114 листов машинописного текста, 36 рисунков, 11 таблиц, список литературы (101 название).
На защиту выносятся следующие основные результаты:
1. Объектно-ориентированная имитационная модель мультисервисной сети
с адаптивной маршрутизацией.
Программная реализация предложенной модели на базе пакета имитационного моделирования AnyLogic.
Распределенный адаптивный алгоритм IP-маршрутизации с обратной связью.
Интегральная методика оценки эффективности работы системы маршрутизации.
Проблема качественной передачи мультимедийного трафика в ІР-сетях
Ни один проект крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети /10/. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. На модели можно опробовать влияние всплесков широковещательных запросов или реализовать режим коллапса (для Ethernet), что вряд ли можно позволить в работающей сети.
Существующие методы моделирования сетей ЭВМ представлены на рис. 1.1 /4/.
При натурном моделировании исследуемая система заменяется соответствующей ей другой материальной системой, которая воспроизводит свойства изучаемой системы с сохранением ее физической природы /21/. Примером этого вида моделирования может служить пилотная сеть, с помощью которой изучается принципиальная возможность построения сети на основе тех или иных компьютеров, коммуникационных устройств, операционных систем и приложений. Возможности натурного моделирования довольно ограничены. Оно позволяет решать отдельные задачи при задании небольшого количества сочетаний параметров системы.
Поэтому во многих случаях предпочтительным оказывается использование математического моделирования /22/. Математическая модель представляет собой совокупность соотношений (формул, уравнений, неравенств, логических условий), определяющих процесс изменения состояния системы в зависимости от ее параметров, входных сигналов, начальных условий и времени. Важнейшим свойством математического моделирования является его принципиальная универсальность. Этот метод в принципе не требует создания специальной аппаратуры для каждой новой задачи, он позволяет относительно просто изменять числовые значения параметров, начальных условий и режимов работы исследуемых телекоммуникационных систем (ТС). Методологически математическое моделирование разбивается на два вида: аналитическое и имитационное моделирование /22/.
При аналитическом моделировании математическая модель реализуется в виде такой системы уравнений относительно искомых величин, которая допускает получение нужного результата аналитически (в явном виде) или численным методом. Аналитическое решение дает более полную и наглядную картину, позволяющую получать зависимость результатов моделирования от совокупности исходных данных. С точки зрения задач оптимизации параметров сети аналитическое моделирование практически незаменимо /4/. Аналитическое моделирование обладает определенными недостатками, которые становятся особенно существенными на заключительных этапах создания системы, когда уже приняты стратегические решения, и речь идет об оценке характеристик некоторого сравнительно небольшого числа вариантов окончательного построения системы, причем на этих этапах при моделировании требуется учитывать достаточно детальное описание системы. В этом случае аналитическое описание системы становится чрезмерно сложным, что затрудняет получение требуемых результатов /4/. В данной ситуации следует переходить к использованию имитационных моделей.
Имитационные модели - это машинные программы, алгоритмы которых воспроизводят функционирование объекта (сети) с некоторым упрощением и выходные характеристики которых определяются статистикой, собираемой с этих моделей во время их прогонов /22/. Имитационное моделирование позволяет учесть большое количество реальных деталей функционирования моделируемого объекта и является незаменимым на финальных стадиях создания системы, когда все стратегические вопросы уже решены, и речь идет лишь об отборе одного из конкретных вариантов реализации ТС, причем описание этих вариантов должно быть весьма детальным (вплоть до описания конкретного оборудования и конкретных протоколов, реализуемых в системе). Принципиальной особенностью имитационного моделирования является тот факт, что для получения содержательных результатов необходимо использовать статистические методы. Данный подход требует многократного повторения имитируемого процесса при изменяющихся значениях случайных факторов с последующим статистическим усреднением (обработкой) результатов отдельных однократных расчетов. Применение статистических методов, неизбежное при имитационном моделировании, требует больших затрат машинного времени и вычислительных ресурсов. Другим недостатком метода имитационного моделирования является тот факт, что для создания достаточно содержательных моделей ТС требуются значительные концептуальные и программистские усилия.
Несмотря на указанные недостатки в настоящее время для моделирования сетей ЭВМ в основном используются имитационные модели, так как получение некоторых характеристик (например, процент потерь переданных пакетов) с использованием аналитического аппарата зачастую не просто сложно, а невозможно /58/.
Механизм расчета метрики алгоритма маршрутизации DARL
В случае алгоритма DARL метрика является многокритериальной. Поэтому необходимо введение новых полей в таблицу маршрутизации: «Загруженность» и «Граничное время» (рис. 2.4).
Поле «Загруженность» содержит количество пакетов, возвращенных шлюзом на данном маршруте за определенный промежуток времени, при вычислении которого используется значение в поле «Граничное время». Итоговая метрика рассчитывается по следующей формуле: м = [О, еслир=1; ,2 j. [P + L + C, еслир 1, где/? - загруженность сетевого интерфейса маршрута; Р - нормированная загруженность сетевого интерфейса; L - нормированная загруженность маршрута; С - нормированная стандартная метрика маршрута.
Нормирование производится для того, чтобы каждая компонента в формуле (2.1) имела одинаковый вес в значении итоговой метрики. Значения составляющих формулы (2.1) изменяются в диапазоне от 0 до 1. Таким образом, значение итоговой метрики изменяется в диапазоне от 0 до 3. Более приоритетным считается большее значение. (2.2)
Нормированная загруженность сетевого интерфейса рассчитывается по следующей формуле: Р = \-р.
Отдельным вопросом является получение показателя загруженности сетевого интерфейса р. При этом приоритетные очереди не рассматриваются, и считается, что очередь организована по принципу FIFO с привлечением алгоритма AQM или без него. В первом случае загруженность очереди определяется вероятностью сброса обрабатываемого пакета (рассмотрено в разделе 1.2), во втором случае - ее длиной.
Вероятность сброса пакета алгоритмы AQM вычисляют, когда новый пакет (уже прошедший стадию маршрутизации) поступает на интерфейс. В рамках разрабатываемого алгоритма значение функции сброса для каждого интерфейса необходимо знать до начала маршрутизации пакета.
Поэтому в ходе работы данной секции алгоритм DARL посылает сигнал «псевдо-пакет» механизму активного управления очередями. На основе этого сигнала механизм рассчитывает новые значения функции сброса для тех сетевых интерфейсов, которые присутствуют в выбранном множестве маршрутов-кандидатов.
Рассмотрим псевдокод алгоритма RED /51/. По прибытию пакета do
Вычисляем средний размер очереди avg_q ifavgjj = maxjh then сброс пакета else if minjh = avg_q maxjh then сброс пакета с вероятностью Pa end if end do Для работы механизма, подобного RED, в рамках разрабатываемого алгоритма DARL необходимо добавить следующий псевдокод. По прибытию сиганала "псевдо-пакет " do Вычисляем средний размер очереди avg_q_pseudo Вычисляем функцию сброса Pa_pseudo = f(avg_q_pseudo) Модифицируем поле «Загруженность» таблицы маршрутизации end do
Значение функции сброса есть не что иное, как вероятность сброса. Поэтому значение показателя загруженности сетевого интерфейса/? будут варьироваться от 0 до 1. При этом, как видно из формулы (2.1), если сброс пакета является событием достоверным, то итоговая метрика М маршрута принимается равным О, а сам маршрут выбывает из списка потенциальных кандидатов для дальнейшей пересылки пакета.
Если очередь не контролируется алгоритмом AQM, то необходимо анализировать текущую длину очереди на предмет ее переполнения. Если очередь не достигла лимита, то показатель/» принимается равным 0, иначе - 1.
Нормированная загруженность маршрута рассчитывается по следующей формуле: 1, если 1=0; = 1 (2 3) у если\ 1, где / - загруженность маршрута.
Само значение загруженности маршрута рассчитывается как отношение количества возвращенных пакетов за интервал времени. Количество пакетов берется равным значению поля «Загруженность» таблицы маршрутизации. Временной интервал (с) рассчитывается как разность текущего времени и значения поля «Граничное время» таблицы маршрутизации.
Для того, чтобы значение показателя загруженности маршрута / было адекватно ситуации в сети, необходимо правильно выбрать длительность временного интервала. Известно, что интенсивность мультимедийного трафика неравномерна, а разбросана по времени с резкими всплесками профиля нагрузки. Среднее значение длительности подобных всплесков и интервалов между ними составляет 0,5 с. /31/.
Программная реализация объектно-ориентированной имитационной модели мультисервисной сети
Изначально для разработки модели не предусматривалось использование языков имитационного программирования, таких как GPSS /24/ и др., и предполагалось использовать готовые специализированные симуляционные пакеты. Данное сужение проблематики было вызвано свойством низкоуровневости универсальных языков моделирования. То есть использование какого-либо языка имитационного моделирования для построения модели мультисервисной сети заняло бы слишком много времени, поэтому было принято решение базироваться на решениях, имеющихся в настоящее время в области имитационного сетевого моделирования.
Среди готовых решений выбор был сделан в пользу сетевого симулятора ns-2, разработанного в рамках проекта VINT /18/. Причины данного выбора были следующие:
1. Симулятор ns-2 по спектру функциональных возможностей (топология, производительность, поддержка сетевых протоколов и пр.) не уступает подавляющему большинству коммерческих продуктов. Среди наиболее известных коммерческих программных пакетов можно отметить BONES (разработка компании CADENS), COMNET (CACI), OPNET (MIL3), NETMAKER (OPNET).
2. Симулятор ns-2 относится к классу так называемых "open source" программ, то есть программ с открытым кодом и свободно распространяемых в Интернет-сообществе. Стоимость же любого из указанных коммерческих пакетов составляет несколько десятков тысяч долларов.
3. Одним из важнейших свойств симулятора ns-2 является возможность расширения его функциональных возможностей (включение новых протоколов, методов управления трафиком и др.) пользователями этих пакетов.
4. Симулятор ns-2 является безусловным лидером среди open source симуля-торов. Данный продукт создавался в конце 90-х годов, в основном, силами американской национальной лаборатории им. Лоуренса в г. Беркли, непосредственно связанной с историей разработки Интернета, и сегодня особенно широко используется именно научным сетевым мировым сообществом. Но анализ пакета ns-2 показал нецелесообразность его использования по следующим причинам /97/: 1. Отсутствие в пакете протокола IP и как следствие системы IP-маршрутизации. Сетевой уровень представлен примитивным протоколом, ограниченным только функциями адресации и инкапсуляции. Причем для узла можно назначить только один сетевой адрес вне зависимости, к скольким каналам передачи данных он подключен. 2. По умолчанию в модели используется централизованная статическая маршрутизация. Реализации протоколов маршрутизации типа вектора расстояния и состояния канала работают в большинстве случаев некорректно. 3. Несоответствие архитектур и логики работы стека TCP/IP модели и реальных сетей. 4. Сложная архитектура самого симулятора, реализованного на двух языках: C++ и OTcl.
Поэтому для разработки модели пришлось в конечном итоге обратиться к языкам имитационного моделирования. При этом при выборе среды разработки делался упор на продукты, поддерживающие агентное моделирование. Оно особенно эффективно при моделировании систем, содержащих большие количества активных объектов. Также при использовании агентного моделирования облегчается процесс отображения объектов реального мира в объекты имитационной модели, и упрощается процедура преобразования логических объектов модели в их программные сущности.
Для агентного моделирования до последнего времени не существовало ни одного инструмента, только библиотеки на Java или C++, разработанные в различных университетах /4/. Единственным продуктом, не только поддерживающим все подходы имитационного моделирования, но также позволяющим сочетать их в одной модели, на сегодняшний день является среда разработки имитационных моделей AnyLogic /16/. Данный продукт является совместной разработкой компании «XJ Technologies» и Санкт-Петербургского государственного политехнического университета. Вначале кратко опишем основные свойства пакета.
Аналитическая модель оценки эффективности работы алгоритмов маршрутизации
В методике, предложенной в /1/ (рассмотрено в разделе 4.1), необходимо расширить систему оценки накладных расходов, в качестве которых принимается только служебный трафик протоколов маршрутизации. Вместе с тем, накладные расходы - любая информация (в том числе полезная), без передачи которой можно было бы обойтись. Следовательно, к подобной информации можно отнести: 1. Служебные сообщения протоколов маршрутизации. 2. Служебные сообщения протоколов транспортного уровня. 3. Полезные данные, передаваемые повторно вследствие их потери при предыдущей передаче.
Таким образом, составляющую F (формула 4.9) можно расширить и представить следующим образом: р =f +F +F (4.14) 1 Ш л RNN т L RNP RND ч где FmN - накладные расходы, привносимые алгоритмом маршрутизации; FMP - накладные расходы, привносимые протоколом транспортного уровня; FmD - накладные расходы, привносимые повторной передачей полезных данных.
Накладные расходы, вносимые компонентой Fmp, зависят от используемого протокола транспортного уровня и в случае UDP отсутствуют. Поэтому имеет смысл рассматривать эту составляющую только для TCP-протокола. При этом основным служебным сообщением, количество передач которого может варьироваться, является сообщение, подтверждающее получение окна данных, так как процедуры установления и разрыва производятся для конкретного соединения только один раз. Таким образом, накладные расходы, привносимые прото колом транспортного уровня, аналитически можно представить следующим образом: F = - RNP Г —-JL Я АСК р иАСК (4.15) где САСК - количество переданных сообщений-квитанций; SF - размер сообщения Прикладного уровня (бит); Sw - размер окна TCP-протокола (бит); SACK - размер пакета подтверждения (бит);
Накладные расходы, вносимые компонентой FRND, также зависят от используемого протокола транспортного уровня. Только в случае TCP-протокола потерянные данные будут запрошены и переданы еще раз. В случае же UDP-протокола механизм повторный передачи потерянной информации возлагается на Прикладной уровень и не обязательно реализуется, например, в случае IP-телефонии. В любом случае накладные расходы, привносимые повторной передачей полезных данных, аналитически можно представить следующим образом: ГRND TR Jf» М 5) где Sm - размер переданных данных (бит).
Стоит отметить, что в оригинальной методике /1/ автор для получения итогового значения функции складывает величины различных размерностей: накладные расходы (бит/с) и временные характеристики (с). Необходимо устранить это упущение. В рамках расширение аналитической модели предлагается накладные расходы алгоритма маршрутизации также представлять временной характеристикой. Поэтому, обозначив накладные расходы, привносимые алгоритмом маршрутизации за TSN, предлагается следующая итоговая формула: (4i7) F = Vc где Vc - пропускная способность самого медленного канала сети (бит/с).
Таким образом, в результате произведенных изменений получена аналитическая модель оценки эффективности работы алгоритмов 1Р-маршрутизации.
Оценим эффективность работы алгоритма DARL и стандартного алгоритма маршрутизации на основе полученной модели. За основу возьмем формулу (4.1). Изначально основная цель методики - оптимизация эффективности системы маршрутизации. Коэффициенты kR и ks в формуле (4.1) используются для определения влияния режимов построения таблиц маршрутизации и обработки пакетов в общей цели оптимизации. Задача же данного раздела иная -оценить, а не оптимизировать эффективность работы алгоритмов маршрутизации, поэтому примем весовые коэффициенты kR, ks равными 1. Подставив в
формулу (4.1) значение количественного критерия FR(QR) из формулы (4.2), а критерия FS(QS) из формулы (4.13) получим следующий вид искомой оценочной функции:
F(QRxQs) = kRCFRC(nR) + kRNFRN(QR) + kROFRO(nR) + Tpp. (4.18)
Следует сразу отметить, что логика методики является обратно пропорциональной, - чем больше значение полученной оценочной функции - тем меньше эффективность. В рамках расширения данной методики предлагается изменить логику методику на прямо пропорциональную. Тогда формула (4.18) примет вид:
Будем считать, что показатели времени сходимости, накладных расходов и оптимальности выбранных маршрутов имеют одинаковый приоритет при оценке алгоритмов маршрутизации. Поэтому коэффициенты кюс примем равными 1. Тогда формула (4.19) примет следующий вид: F(QJ,xfls) = (FK(flJl) + Fw(nil) + FJ10(nj,) + 7 e,)-1. (4.20)
Выведем вид оценочной функции отдельно для алгоритма DARL и стандартного алгоритма маршрутизации. Алгоритм маршрутизации DARL Алгоритм DARL не осуществляет перестройку таблиц маршрутизации, поэтому время сходимости FRC принимается равным 0.
Накладные расходы алгоритма DARL, следуя формуле (4.14), будут включать все три компоненты. Отдельно необходимо оценить накладные расходы TSN, привносимые служебными сообщениями самого алгоритма, так как аналитическое представление компонент Ршр и FRND одинаково для любой системы маршрутизации.
В качестве служебных сообщений алгоритм DARL использует пакеты данных, возвращаемые назад маршрутизатору. Эти пакеты проходят один и тот же канал дважды, создавая тем самым накладные расходы. Поэтому накладные расходы TSN алгоритма можно представить как удвоенный размер возвращенных пакетов: SN_DARL= ВАСК- V+-21) Третье слагаемое формулы (4.20), величина , оценивается для режима построения таблиц маршрутизации /1/ и поэтому в случае алгоритма DARL принимается равным 0.
Четвертое слагаемое формулы (4.20), величина Трр, представляет собой время определения маршрута пересылки пакета. Время Трр можно представить в виде формулы (4.12). Данную величину можно также оценить на основе сложности алгоритма нахождения следующего хопа.
Стандартный алгоритм маршрутизации
Как и в случае алгоритма DARL имеет смысл рассматривать только две компоненты оценочной функции - накладные расходы Fm и время Трр. Алгоритм в своей работе не использует служебных сообщений, поэтому составляющая накладных расходов TSN равна 0. В итоге оценочную функцию для определения эффективности стандартного алгоритма маршрутизации можно представит формулой (4.22).
