Файл: Проектирование маршрутизации в двух трехуровневых сетях с использованием протокола RIP.pdf

Маршрутизация по наикратчайшему пути

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

Маршрутизация лавиной

Другим примером статического алгоритма может служить следующий алгоритм: каждый поступающий пакет отправляют по всем имеющимся линиям, за исключением той, по которой он поступил. Ясно, что если ничем не ограничить число повторно генерируемых пакетов, то их число может расти неограниченно. Время жизни пакета ограничивают областью его распространения. Для этого в заголовке каждого изначально генерируемого пакета устанавливается счетчик переходов. При каждой пересылке этот счетчик уменьшается на единицу. Когда он достигает нуля, пакет сбрасывается и далее не посылается. В качестве начального значения счетчика выбирают наихудший случай, например, диаметр транспортной подсети. Другим приемом, ограничивающим рост числа дублируемых пакетов, является отслеживание на каждом маршрутизаторе тех пакетов, которые через него однажды уже проходили. Такие пакеты сбрасываются и больше не пересылаются. Для этого каждый маршрутизатор, получая пакет непосредственно от абонентской машины, помечает его надлежащим числом. В свою очередь, каждый маршрутизатор ведет список номеров, сгенерированных другим маршрутизатором. Если поступивший пакет уже есть в списке, то этот пакет сбрасывается. Для предотвращения безграничного роста списка вводят ограничительную константу k. Считается, что все номера, начиная с k и далее, уже встречались. Несмотря на кажущуюся неуклюжесть, этот алгоритм применяется, например, в распределенных базах данных, когда надо параллельно обновить данные во всех базах одновременно. Этот алгоритм всегда находит наикратчайший маршрут за самое короткое время, поскольку все возможные пути просматриваются параллельно.

---

Маршрутизация на основе потока

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

Для реализации этой идеи нам нужно о каждой транспортной среде заранее знать следующее:

• топологию
• матрицу трафика F^ij
• матрицу пропускных способностей каналов C^ij
• алгоритм маршрутизации

Маршрутизация по вектору расстояния

Алгоритм маршрутизации по вектору расстояния устроен следующим образом: у каждого маршрутизатора в транспортной подсети есть таблица расстояний до каждого маршрутизатора, принадлежащего подсети. Периодически маршрутизатор обменивается такой информацией со своими соседями и обновляет информацию в своей таблице. Каждый элемент таблицы состоит из двух полей: первое - номер канала, по которому надо отправлять пакеты, чтобы достичь нужного места, второе - величина задержки до места назначения. Величина задержки может быть измерена в разных единицах: числе переходов, миллисекундах, длине очереди на канале и т.д. Фактически в протоколе использовалась версия алгоритма, где эту задержку определяли не на основе пропускной способности канала, а на основе длины очереди к каналу. Каждые Т секунд маршрутизатор шлет своим соседям свой вектор задержек до всех маршрутизаторов в подсети. В свою очередь, он получает такие же вектора от своих соседей. Кроме этого, он постоянно замеряет задержки до своих соседей. Поэтому, имея вектора расстояний от соседей и зная расстояние до них, маршрутизатор всегда может вычислить кратчайший маршрут до определенного места в транспортной среде. Рассмотрим, как маршрутизатор J с помощью этой таблицы вычислит маршрут до G. J знает, что он может достичь А за 8 мсек., А объявляет, что от него до G 18 мсек. Таким образом, J может достичь G за 26 мсек. через A. Аналогично можно подсчитать, что достичь G через I, H и K можно за 41 (31+10), 18 (6+12) и 37 (31+6) мсек. соответственно. Наилучшее значение – 18, поэтому это и есть наилучший маршрут.

---

Разделение направлений (Split Horizon Hack)

Одним из решений этой проблемы является следующий прием. Алгоритм работает так, как было описано, но при передаче вектора по линии, по которой направляются пакеты для маршрутизатора Х, т.е. по которой достижим маршрутизатор Х, расстояние до Х указывается как бесконечность. Если теперь рассмотреть то, как будет работать подсеть на рисунке 5-11(b), то там проблем возникать не будет. Действительно, когда А «упадет», при первом же обмене В это обнаружит, но С также будет слать В вектор, согласно которому А не достижимо (∞). На следующем обмене С увидит, что А недостижим из обоих его соседей, и также отметит его как недостижимый узел.

Однако и в алгоритме разделения направлений есть «дыры». Рассмотрим подсеть на рисунке 5-12. Если линия между С и D будет разрушена, то С сообщит об этом А и В. Однако А знает, что у В есть маршрут до D, а В знает, что такой маршрут есть и у А. И опять мы «сваливаемся» в проблему бесконечного счетчика.

Маршрутизация по состоянию канала

Основная идея построения этого алгоритма проста и состоит из пяти основных шагов:

1. Определить своих соседей и их сетевые адреса.
2. Измерить задержку или оценить затраты на передачу до каждого соседа.
3. Сформировать пакет, где указаны все данные, полученные на шаге 2.
4. Послать этот пакет всем другим маршрутизаторам.
5. Вычислить наикратчайший маршрут до каждого маршрутизатора.

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

При проектировании корпоративной сети весь процесс разработки разбивают на три части в соответствии с предложенным фирмой Cisco Systems подходом. Компьютерные сети удобно представлять в виде трехуровневой иерархической модели (рисунок 1), которая содержит следующие уровни:

– уровень ядра;

– уровень распределения;

– уровень доступа.

Рисунок 1. Трехуровневая модель сети

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

---

Уровень распределения используется для суммирования маршрутов. Суммирование проводится для уменьшения сетевого трафика на верхних уровнях сети и представляет собой объединение нескольких сетей в одну общую, имеющую короткую маску.

На уровне доступа формируется сетевой трафик, а также производится контроль доступа к сети. Маршрутизаторы уровня доступа служат для подключения отдельных пользователей (серверы доступа) или отдельных локальных сетей к глобальной вычислительной сети. Самым простым коммутирующим оборудованием уровня доступа являются коммутаторы подразделений, к которым присоединяются автоматизированные рабочие места сотрудников организации (АРМы). Коммутаторы подразделений объединяются в единую сеть с помощью коммутаторов зданий, которые в рамках одного кампуса соединяются в кольцо оптоволоконными линиями связи. В каждом кампусе содержится по четыре здания, а следовательно и коммутаторов зданий в них тоже будет четыре. Через коммутатор кампуса сеть соединена с маршрутизатором кампуса. Маршрутизатор кампуса соединяет все подразделение кампуса с центральным офисом.

Проектируемая сеть должна отвечать требованиям структурированности и избыточности.

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

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

Выбрана смешанная топология, в которую входят следующие топологии:

– «иерархическая звезда»;

– кольцо;

– «каждый с каждым».[3]

Корпоративная сеть основывается на двухуровневой иерархической модели (верхний уровень – ядро (core), нижний – уровень доступа (access)).

На уровне ядра располагаются три центральных офиса организации, расположенные в разных городах. Они составляют три узла ядра глобальной сети. Центральные маршрутизаторы узлов A, B, C соединены между собой (каждый – с каждым) по технологии MPLS VPN на канальном уровне и Ethernet на физическом, образуя кольцевое ядро сети. К узловым маршрутизаторам через коммутаторы демилитаризованной зоны подключены маршрутизаторы Х с использованием технологии Gigabit Ethernet. Коммутаторы внешних серверов (FTP, mail и web)образует демилитаризованную зону, через которую осуществляется выход в Интернет. К узловому маршрутизатору С через коммутатор подключены корпоративные серверы с использованием технологии Gigabit Ethernet.

---

К каждому узловому маршрутизатору подключаются региональные подразделения. Кампусные сети подразделений (кампусы) составляют уровень доступа. Маршрутизаторы кампусов подключаются к маршрутизаторам регионов по технологии Wi-Fi. Каждый кампус состоит из четырех зданий.

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

На уровне ядра была выбрана технология MPLS VPN (многопротокольная коммутация с помощью меток при организации виртуальных частных сетей), т.к. на сегодняшний день это наиболее перспективная технология передачи данных, она обеспечивает возможность передачи трафика по наименее загруженным маршрутам IP-сети и легкость конфигурирования VPN с одновременной поддержкой гарантии качества передачи, а также присвоения приоритетов различным видам трафика. Выбранная технология способна обеспечить наибольшую скорость, надежность и качество передачи данных по сравнению с технологиями АТМ и Frame Relay.

Технология Gigabit Ethernet на уровне ядра способна обеспечивать работу MPLS VPN на канальном уровне.

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

На канальном уровне для города VPN обеспечивается технологией Wi-Fi.Wi-Fi– это семейство протоколов беспроводной передачи данных IEEE 802.11x (802.11a, 802.11b, 802.11g, 802.11n и т.д.). Сети Wi-Fi работают на частотах 2,4 ГГц или 5 ГГц. В пределах прямой видимости беспроводная связь обеспечивается в радиусе до 300 метров от точки доступа. В закрытых помещениях беспроводная связь обеспечивается в пределах 50 метров.Технология ADSL обеспечивает доступ в Интернет.

Адресная схема должна быть разработана в соответствии с иерархическим принципом проектирования компьютерных сетей. Схема адресации должна позволять агрегирование адресов. Это означает, что адреса сетей более низких уровней (например, сеть кампуса по сравнению с сетью региона) должны входить в диапазон сети более высокого уровня с большей маской. Кроме того, необходимо предусмотреть возможность расширения адресного пространства на каждом уровне иерархии.

---