Введение
Одними из наиболее перспективных и быстроразвивающихся направлений развития информационных технологий являются системы и устройства телекоммуникаций и, прежде всего, компьютерные сети. Их перспективность определяется всеобщей информатизацией общества, внедрением компьютеров в науку, производство, бизнес, обучение и другие отрасли человеческой деятельности, а также необходимостью интеграции информационных систем. Развитие компьютерных сетей происходит как в плане роста количества подключенных к ним узлов, так и увеличением объемов передаваемого трафика.
Основы сетевых технологий изложены в работах В. Г. Олифер, Н. А. Олифер [78, 79], М. В. Кульгина [64, 65]. Оригинальные научные разработки в исследуемой области приводятся в работах Л.И.Абросимова [1-12], В. М. Вишневского [44] и других. Наибольший вклад в развитие рассматриваемой области науки внесли зарубежные ученые. Прежде всего, стоит отметить университетские центры, такие как Massachusetts Institute of Technology (MIT) [139] и Berkeley University of California [107], а также научные центры крупных фирм производителей, таких как Cisco Systems [108, 108], Nortel Networks [141], Juniper Networks [143], Foundry Networks [130], 3COM [145], Microsoft [138, 140] и других.
Одной из актуальных задач проектирования и администрирования компьютерных сетей является настройка маршрутизаторов, осуществляющих передачу информации в пакетном режиме. При этом большой проблемой является задача анализа и разработки методов конфигурирования маршрутизаторов с помощью количественной оценки их работы. Под конфигурацией маршрутизатора понимается состав и настройка как программного, так и аппаратного обеспечения устройства. Актуальность проблемы определяется высокой сложностью настройки современных сетевых
устройств и необходимостью эффективного использования оборудования и линий связи.
Современные исследования в рассматриваемой области носят качественный характер и сводятся к отдельным рекомендациям. В работающих в настоящее время компьютерных сетях часто используются настройки многих параметров маршрутизаторов по умолчанию, что не всегда является наилучшим решением. В работе сделан акцент на количественную оценку эффективности маршрутизаторов, который позволяет свести процесс оптимальной настройки сетевого оборудования к инженерной задаче.
Целью работы является выбор количественных критериев для определения эффективности работы маршрутизаторов, позволяющих формальным образом сравнивать между собой и выбирать оптимальные варианты их конфигурации, разработка методов оценивания выбранных критериев и принятия на их основе эффективных программно-аппаратных решений.
Для достижения поставленной цели были решены следующие задачи:
1. Выбор и обоснование количественных критериев, позволяющих оценивать эффективность работы маршрутизатора.
2. Анализ существующих алгоритмов, используемых в маршрутизаторах в режимах обработки пакетов и построения таблиц маршрутизации, и выбор параметров оценки их эффективности.
3. Структуризация алгоритмов и получение общей оценки работы маршрутизаторов, исходя из оценки сложности отдельных алгоритмов.
4. Разработка методов аналитического оценивания выбранных параметров.
5. Экспериментальная проверка аналитически полученных выражений в лабораторных условиях.
6. Апробация критериев и методов их расчета на базе конкретных корпоративных компьютерных сетей.
7. Выработка практических рекомендаций по настройке маршрутизаторов.
Теоретические исследования проводились с использованием теории множеств, графов и оценки вычислительной сложности. Структуризация алгоритмов выполнялась методами многоуровневых моделей. Экспериментальная проверка проводилась методами физического моделирования на сетевом оборудовании фирмы Cisco.
Научная новизна работы заключается в следующем:
1. Выбраны и обоснованы количественные критерии оценки эффективности работы маршрутизатора.
2. Разработан упрощенный метод оценки сложности алгоритмов сетевых устройств, учитывающий особенности этих алгоритмов.
3. Расширена многоуровневая модель обработки пакетов маршрутизаторами с учетом выполняемых современными сетевыми устройствами операций.
4. Предложена трехуровневая модель протоколов маршрутизации, позволяющая упростить задачу их анализа и расчета параметров.
Практическую ценность представляют следующие результаты работы:
1. Получены и экспериментально подтверждены аналитические зависимости для практической оценки параметров протоколов маршрутизации и алгоритмов обработки пакетов.
2. Выработаны практические рекомендации по выбору конфигурации маршрутизаторов.
3. Сформулированы предложения по оптимизации настроек сетевого оборудования корпоративной компьютерной сети ОРПО ДИВЦ Зап-Сиб ж.д. -филиала ОАО «РЖД», которые могут быть использованы для других сетей.
4. Результаты работы используются при проведении учебных занятий по дисциплинам, связанным с компьютерными сетями, в Омском государственном университете путей сообщений.
Диссертационная работа выполнялась в рамках госбюджетной НИР «Разработка и исследование автоматизированных методов идентификации, управления и обработки информации в технических системах» (№ государственной регистрации 01.9.60000794), проводимой в ОмГУПС.
По результатам исследований поданы предложения в ОРПО ДИВЦ Зап-Сиб. ж.д. - филиала ОАО «РЖД» по оптимизации настроек сетевого оборудования корпоративной компьютерной сети Омского отделения. Результаты работы используются в учебном процессе в ОмГУПС. Реализация результатов работ подтверждена соответствующими актами о внедрении.
Основные положения работы докладывались на 6 конференциях, по теме диссертации опубликовано 4 статьи, в том числе 1 статья без соавторов, оформлен один отчет по НИР, издано 1 методическое указание, всего 12 работ.
Работа состоит из введения, пяти глав, списка использованных источников из 145 наименований. Основной текст изложен на 131 странице, содержит 3 таблицы и иллюстрируется 24 рисунками.
Основные положения, выносимые на защиту:
1. Количественные критерии оценки эффективности работы маршрутизатора.
2. Многоуровневая модель обработки пакетов маршрутизатором.
3. Трехуровневая модель протоколов маршрутизации.
4. Практические рекомендации по выбору конфигурации маршрутизаторов.
1. Критерии эффективности маршрутизаторов
Для определения оптимальной конфигурации маршрутизатора необходим критерий, который позволял бы сравнивать между собой различные варианты настроек. При известном критерии сам процесс оптимизации, как будет показано ниже, не является сложной задачей.
Для однозначной и объективной оценки конфигураций маршрутизатора этот критерий должен быть количественным, т.е. результатом его оценки должно быть единственное число, указывающее эффективность работы маршрутизатора для анализируемого случая.
Основной задачей диссертационной работы является выбор и обоснование количественного критерия эффективности маршрутизатора и создание методики его оценки.
В текущей главе эта задача рассматривается в общем виде. В ней анализируются предложенные в литературе и применяемые на практике параметры сетевых устройств на основании которых выбирается единый количественный критерий и рассматриваются общие принципы оценки составляющих частей выбранного критерия.
1.1. Работа маршрутизаторов и критерии ее оценки
Маршрутизаторы представляет собой сложные устройства, использующие в своей работе большое количество алгоритмов и выполняющее ряд задач. Их работу нельзя оценивать в отрыве от работы компьютерной сети, объединяющее большое количество маршрутизаторов и других сетевых устройств, также представляющей собой сложную системы. В связи с этим возникают сложности выбора единого критерия оценки их работы.
Существует количественные критерии, оценивающие тот или иной аспект работы сетевых устройств или сети в целом [65, 68, 78]. Универсальный критерий, характеризующий эффективность маршрутизатора в целом, автору
8
обнаружить в доступных литературных источниках не удалось. В связи с этим возникла задачи формулировки такого критерия.
Отметим, что маршрутизатор решает две различные задачи. В неявном виде эта мысль выражена в ряде работ [84, 87].
Первая из них связана с определением оптимального маршрута. Для решения этой задачи используются протоколы маршрутизации.
Вторая задача связана с передачей пакетов по выбранным маршрутам. Ее сложность связана с необходимостью передавать пакеты максимально быстро, а также с тем, что пакеты нужно не просто переправить в нужную сеть, а провести с ним некоторые дополнительные операции (например, фильтрацию пакетов).
Эффективность работы маршрутизатора при решении этих задач слабо коррелированна [38]. Наибольший объем вычислений, выполняемых при работе протоколов маршрутизации, выполняется при изменении топологии сети, т.е. в тот период, когда скорость передачи пакетов не имеет большого значения.
Исключением из выше сказанного является случай, когда маршрутизатор имеет правильные маршруты для большинства передаваемых через него пакетов и, в тоже время, обрабатывает изменение топологии, произошедшие на другом участке сети. В грамотно спроектированной сети, в которой применяется скрытие изменения топологий посредством суммирования [84] такая ситуация маловероятна, поэтому в работе рассматриваться не будет.
Таким образом, для решения поставленной задачи нам необходимо фактически сформулировать два критерия, оценивающих эффективность конфигурации маршрутизатора ~ эффективность протоколов маршрутизации и обработки (передачи) пакетов.
Для удобства изложения в дальнейшем будем говорить о двух режимах работы маршрутизатора - построения таблиц маршрутизации и обработки пакетов. Рассмотрим оба эти критерия в отдельности.
Вопрос об оптимальной настройке протоколов маршрутизации в настоящее время недостаточно изучен. Большинство производителей [105, 108, 129, 130, 143] и авторов научных и учебных работ [64, 78, 87] рекомендуют использовать параметры этих протоколов установленные в сетевом оборудовании по умолчанию. Автору не удалось обнаружить в литературе систематически изложенных параметров протоколов маршрутизации в общем виде.
Рассмотрим параметры (характеристики) протоколов маршрутизации, которые используются при описании протоколов [118, 121, 124, 125]. Такой подход позволяет получить наиболее полный список изучаемых параметров. Отметим, что вопрос их количественной оценки в указанных и других работах в общем случае не освещен и поэтому требует отдельной проработки.
Основной характеристикой протоколов маршрутизации является его быстрая сходимость. Маршрутизаторы сети могут находиться в двух состояниях - с правильными и неправильными таблицами маршрутизации. Неправильные таблицы маршрутизации могут получиться при изменении топологии сети. Сходимостью будем называть процесс приведения в соответствие таблиц маршрутизации и новой топологии сети. Очевидно, что чем быстрее будет проходить сходимость, тем лучше работает сеть.
Другой немаловажной характеристикой протоколов маршрутизации являются накладные расходы. Прежде всего, учитываются накладные расходы связанные с передачей по сети информации о ее топологии. В некоторых случаях (для сложных протоколов, таких как OSPF и BGP) значимым фактором оказываются вычислительные расходы на построение таблиц маршрутизации.
Еще одним параметром является «качество» таблиц маршрутизации, формируемых протоколом. Назовем этот параметр оптимальность протоколов маршрутизации. Некоторые протоколы маршрутизации (прежде всего, RIP) могут выбирать не самые оптимальные пути для передачи пакетов.
Рассмотрим параметры, которые могут использоваться для оценки работы маршрутизаторов в режиме передаче пакетов.
10
Производителями сетевого оборудования в качестве основного указывается пропускная способность устройства или аналогичные параметры [105, 108, 129, 130, 143]. Данная величина определяет количество пакетов, которое устройство может обработать в единицу времени. Пропускная способность может указываться при различных условиях работы. Например, для устройств фирмы Cisco указывается пропускная способность для случая программной и быстрой коммутации.
Данная величина описывает, прежде всего, максимальную производительность устройства. Она не учитывает конфигурацию маршрутизатора (за исключением типа коммутации) и, следовательно, не может служить критерием эффективности конфигурации.
Оценивать эффективность работы маршрутизатора можно и с точки зрения работы всей сети. В этом случае можно использовать параметры, аналогичные параметрам качества обслуживания [70, 144]: (реальная) пропускная способность — объем реально переданного трафика через маршрутизатор, задержка - промежуток времени между поступлением пакета на вход устройства и передачей его в новую сеть и надежность - процент переданных пакетов. Недостатком этих параметров является сложность расчета и их зависимость от профиля передаваемого трафика.
Построение
таблиц маршрутизации
Таблица маршрутизации
Сходимость
Накладные расходы
Оптимальность маршрута
Пропускная способность
Задержка пакетов Надежность передачи
Рисунок 1.1- Режимы и параметры работы маршрутизаторов Схематично режимы и параметры работы маршрутизатора изображены на рисунке 1.1. Исходя из вышеизложенного можно сделать вывод: работа маршрутизатора характеризуется несколькими разнородными параметрами,
11
среди которых нельзя выделить самый главный. Кроме того, в зависимости от задач, стоящих перед компьютерной сетью, важность этих параметров будет меняться.
1.2. Количественный критерий эффективности работы маршрутизаторов
Сформулируем количественный критерий, характеризующий эффективность работы маршрутизатора. Условимся, что, поскольку рассматривается вопрос об оценке эффективности настройки маршрутизации, можно говорить также о эффективности работы маршрутизатора при данной настройке или просто об эффективности работы маршрутизатора (подразумевая, что речь идет о оценке конкретной конфигурации).
В качестве количественного критерия предлагается использовать целевую функцию [22]. Целевая функция представляет собой сумму нормированных параметров, характеризующих тот или иной аспект работы маршрутизатора, с учетом весовых коэффициентов, определяющих значимость сопоставленных с ними параметров в соответствии с целью.
Использование целевой функции является достаточно типичным решением в различных областях науки и техники. В данном случае ее применение обуславливается следующими факторами:
- маршрутизатор может работать в различных режимах имеющих различные количественные критерии оценки эффективности работы устройства;
- в каждом из режимов работа маршрутизатора может описываться различными параметрами для совместного учета которых требуется использование целевой функции;
- значимость параметров может меняться в зависимости от функций, стоящей перед маршрутизатором, например, они различные для маршрутизаторов уровня ядра и уровня доступа.
12
Обозначим целевую функцию через F. Она представляет собой сумму двух слагаемых:
F(Qr х Пв) = krFr(Qr) + ksFg(Qs), (1.1)
где Fr(Qr), FS(QS)-количественные критерии, характеризующие работу
маршрутизаторов в режимах построения таблиц маршрутизации и
обработки пакетов соответственно;
kr, ks - весовые коэффициенты, определяющие влияние режимов
построения таблиц маршрутизации и обработки пакетов в общей цели
оптимизации;
Or, Qe - множества параметров, от которых зависит работа
маршрутизаторов.
Количественный критерий работы маршрутизатора в режиме построения таблиц маршрутизации Fr зависит от таких параметров как сходимость, накладные расходы, оптимальность маршрута (см. 1.1). По указанным выше причинам его также целесообразно оценивать в виде целевой функции. Формула для расчета этого критерия примет следующий вид (после формулы расшифровываются только индексы, сами обозначения аналогичны предыдущей формуле):
Fr = krcFrc + krnFrn + kroFro, (1.2)
В формуле (1.2) индексы относятся к оценкам времени сходимости протоколов маршрутизации (г с), накладных расходов (гп) и оптимальности выбора маршрутов (го) при построении таблиц маршрутизации.
Количественный критерий, характеризующий работу маршрутизатора в режиме обработки пакетов Fs должен характеризовать такие параметры как пропускная способность, задержка и надежность передачи пакетов (см. 1.1). Использование целевой функции в данном случае является неудачным решением. Как показал анализ происходящих при обработке пакетов процессов и экспериментальные данные эти величины сильно коррелированны между собой и имеют одну основу.
13
Исходя из анализа процесса обработки пакетов автором предлагается использовать в качестве количественного критерия эффективности работы маршрутизатора в режиме обработки пакетов время обработки пакета [22].
Время обработки пакета Трр (time packet processing) - процессорное
время, которое тратится на обработку пакета.
Уточним данное определение. Отличие введенного параметра от времени задержки пакетов состоит в том, что он представляет собой чистое время обработки пакетов, а не время, в течение которого пакет находился в маршрутизаторе. Например, время, в течение которого пакет ожидает освобождения линии связи (находится в очереди) учитывается во времени задержки пакета, но при этом процессорное время на его обработку не расходуется.
В том случае, если обработка пакета происходит на нескольких процессорных элементах, например, центральном и интерфейсном процессорах, за время обработки пакета следует принимать максимальное время работы одного из процессоров.
Покажем, что введенный параметр является адекватным количественным критерием эффективности работы маршрутизатора в режиме обработке пакетов, характеризующим параметры, применявшиеся ранее для оценки этого режима.
По данному нами определению, связь между временем обработки пакета и пропускной способностью маршрутизатора выражается следующей формулой:
р Ш
Р = ^Г« (1.3)
рр
где Р - пропускная способность маршрутизатора; L() - длина пакета;
Круглые скобки после символа длины пакета означают, что эта величина зависит от профиля трафика. Обе величины, и пропускная способность, и время
обработки пакета характеризуют скорость обработки пакетов
14
маршрутизатором, при этом пропускная способность также зависит и от распределения длин пакетов передаваемого трафика. Распределение длин пакетов передаваемого трафика не зависит от настроек маршрутизатора и, |» следовательно, не может их характеризовать. Таким образом, можно сформулировать, что время обработки пакетов характеризует эффективность обработки пакетов в «чистом виде», без учета распределения длин трафика.
По данному нами определению, связь между временем обработки пакетов и задержкой пакетов может быть выражена следующей формулой:
Td = Трр + Tq(), (1.4)
где Td (time delay) - задержка пакета;
Tq() (time queue) - время нахождения пакета в очередях.
Время нахождения пакета в очередях, определяется, в первую очередь, интенсивностью передаваемого трафика. Существует также его зависимость и от эффективности обработки пакетов - чем быстрее обрабатываются пакеты, тем меньше очередь и тем меньше пакет в ней находится, но эта зависимость косвенная.
Таким образом, время обработки пакета адекватно характеризует Ў эффективность обработки пакетов. В отличие от применявшихся ранее параметров оно не учитывает распределения трафика. Это свойство является достоинством предложенного параметра с точки зрения универсальности критерия, но, в тоже время и недостатком, поскольку его измерение возможно только косвенным образом.
Для аналитического определения времени обработки пакета необходимо подсчитать время выполнения каждой из операций над пакетом. Рассмотрим в • общем виде особенности анализа эффективности (времени выполнения) алгоритмов сетевых устройств.
15
1.3. Оценка времени выполнения алгоритмов сетевых устройств
В теории рассматривается общий подход к оценке эффективности и времени выполнения алгоритмов [34, 62, 82]. В компьютерных сетях работа алгоритмов имеет ряд особенностей.
Основной вычислительной особенностью рассматриваемых алгоритмов является их распределенный характер. При их выполнении обычно используется несколько вычислительных блоков. В соответствии с двумя режимами работы маршрутизаторов можно выделить два вида распределенных вычислений.
В первом вычислительные блоки расположены на различных сетевых устройствах. Примером такого варианта могут быть протоколы маршрутизации. При этом нужно учитывать, что часть информации передается по линиям связи и может задерживаться или теряться. Алгоритмы подобного типа обычно используются в служебных протоколах и не подходят для непосредственной обработки трафика.
Во втором случае вычислительные блоки расположены в одном устройстве. Скорость работы алгоритмов такого типа сильно зависит от аппаратной платформы. Иллюстрацией к данному случаю служат протоколы управления трафиком (применяются на маршрутизаторах для оптимального использования имеющихся ресурсов линий связи). В современных сетевых устройствах они выполняются, как правило, не центральным процессором, а контроллерами интерфейсов.
Другой особенностью алгоритмов сетевых устройств является многозадачность. Обычно сетевому устройству приходится обрабатывать большое число пакетов. При этом может использоваться два типа многозадачности.
В первом случае происходит пакетная обработка данных. Другими словами, сетевое устройство, обработав один пакет, переходит к обработке другого.
16
Также используется и многозадачность с разделением времени. Сетевые устройства обычно работают под управлением операционных систем реального времени, с указанной многозадачностью, такие, как, например, Cisco IOS [108].
В соответствии с выбранным нами подходом к рассмотрению работы маршрутизатора в двух режимах можно выделить два класса алгоритмов. Алгоритмы первого класса заняты непосредственно обработкой трафика. Они обычно выполняются на вычислительных блоках одного устройства и повторяются много раз для каждого из пакетов. Ко второму классу относятся служебные протоколы. Они обычно выполняются одновременно на нескольких устройствах, но при этом вызываются гораздо меньшее число раз и имеют меньшие требования по скорости.
Особенности выполнения вычислений на сетевом оборудовании обуславливают особенности определения эффективности алгоритмов. Эффективность алгоритмов можно оценивать как по полученным результатам, так и по используемым ресурсам. В первом случае эффективности зависит от характера решаемой задачи, поэтому не существует универсального критерия для ее оценки. Рассмотрим второй случай.
В общем случае различают два вида эффективности по используемым ресурсам - пространственная и временная [62]. Пространственная эффективность характеризует объем памяти, используемой алгоритмом. Временная эффективность определяет время, затрачиваемое на выполнение алгоритма.
С точки зрения рассматриваемых алгоритмов, большее значение имеет временная эффективность [38]. Для алгоритмов, непосредственно занимающихся обработкой трафика, это обуславливается необходимостью обработки большого числа относительно небольших пакетов. Структуры данных, требуемые для служебных протоколов, также обычно занимают относительно небольшой объем памяти. В дальнейшем под эффективностью будет подразумеваться временная эффективность.
17 |
