Исследование эффективности алгоритмов маршрутизации в сетях с кп в датаграммном режиме
| Вид материала | Исследование |
- Применение алгоритмов адаптивной маршрутизации в протоколе igrp, 37.51kb.
- Примеры тем дипломных проектов и работ, 73.48kb.
- 2 семестр 2 курса, 56.57kb.
- Метод уменьшения размера таблиц маршрутизации в ip-сетях, 276.46kb.
- Реферат По дисциплине: «Сети ЭВМ и средства коммуникаций» На тему: «Маршрутизация, 283.88kb.
- М. В. Ломоносова Мехманико математический факультет Кафедра математической логики, 909.95kb.
- Заключение, 9.45kb.
- «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
- Протоколы маршрутизации, 61.97kb.
- А. А. Берестов московский инженерно-физический институт (государственный университет), 32.63kb.
___________________________________________________
Исследование эффективности алгоритмов маршрутизации
в сетях с КП в датаграммном режиме
___________________________________________________
Санкт-Петербург
2003
Оглавление
Введение
Введение
В 80-е годы для надежного объединения локальных сетей и крупных компьютеров в корпоративную сеть использовалась практически одна технология глобальных сетей с коммутацией пакетов - Х.25. Эти сети обслуживали в основном терминальный трафик, и скорость доступа в них не превышала 64 Кбит/c . Протоколы X.25 обладали большой избыточностью, что позволяло хорошо работать на каналах низкого качества.
Сегодня выбор стал гораздо шире, помимо сетей на основе Х.25 появились такие технологии, как Frame relay, SMDS и АТМ. Кроме этих технологий, разработанных специально для глобальных компьютерных сетей, широко распространились сети, на основе протоколов TCP/IP. Сегодня они доступны как в виде коммерческих глобальных сетей ТСР/IР, изолированных от Internet и предоставляемых в аренду телекоммуникационными компаниями, так и в виде недорогой и очень распространенной сети Internet, качество транспортных услуг которой пока практически не регламентируется.
В своей дипломной работе я буду рассматривать именно последний случай – маршрутизацию в сети Интернет, как получившую наибольшее развитие, и в следствии своей открытости лучше всего отражающую реальные задачи.
Глава 1
На сегодняшний день по сведениям ics.org Интернет насчитывает 171,638,297 хостов. Функционирование такой огромной сети было бы невозможно без механизмов определения оптимального пути следования информации между удаленными хостами.
Маршрутизация - это процедура определения пути следования пакета из одной сети в другую. В первые годы появления межкомпьютерной связи программное обеспечение организации сетей создавалось бессистемно, для каждого отдельного случая. После того, как сети приобрели достаточную популярность, некоторые из разработчиков признали необходимость стандартизации сопутствующих изделий программного обеспечения и разработки аппаратного обеспечения. Считалось, что стандартизация позволит поставщикам разработать системы аппаратного и программного обеспечения, которые смогут сообщаться друг с другом даже в том случае, если в их основе лежат различные архитектуры. Поставив перед собой эту цель, ISO начала разработку эталонной модели Open Systems Interconnections (OSI) (Взаимодействие открытых систем). Эталонная модель OSI быстро стала основной архитектурной моделью для передачи межкомпьютерных сообщений.
Семиуровневая модель OSI делит проблему перемещения информации между компьютерами через среду сети на семь менее крупных, и следовательно, более легко разрешимых проблем. Каждая из этих семи проблем выбрана потому, что она относительно автономна, и следовательно, ее легче решить без чрезмерной опоры на внешнюю информацию.
Рисунок 1
Рисунок 1 иллюстрирует основные принципы, заложенные в модели OSI. Каждый уровень модели логически связан с уровнями, расположенными выше и ниже его. Когда система подготавливает данные для отправки по сети, каждый ее уровень воспринимает данные , полученные от верхнего уровня как однородную абстрактную информацию , добавляет свой заголовок и управляющую информацию для соответствующего уровня на удаленном хосте, и передает полученный блок данных на уровень ниже.
Большинство устройств сети реализует все семь уровней. Однако в режиме потока информации некоторые реализации сети пропускают один или более уровней. Два самых низших уровня OSI реализуются аппаратным и программным обеспечением; остальные пять высших уровней, как правило, реализуются программным обеспечением.
Когда протоколы OSI были реализованы, выявился ряд проблем:
- Протоколы основаны на концепциях, не имеющих в современных сетях никакого смысла.
- Спецификации в некоторых случаях были неполными.
- По функциональным возможностям протоколы OSI уступали другим протоколам.
- Наличие большого числа уровней привело к низкой производительности.
В настоящий момент наибольшее развитие получил стек протоколов TCP/IP, который был разработан по инициативе Министерства обороны США (Department of Defence, DoD) более 20 лет назад для связи экспериментальной сети ARPAnet с другими сателлитными сетями как набор общих протоколов для разнородной вычислительной среды. В сети ARPA связь между двумя компьютерами осуществлялась с использованием протокола Internet Protocol (IP), который и по сей день является одним из основных в стеке TCP/IP и фигурирует в названии стека.
Большой вклад в развитие стека TCP/IP внес университет Беркли, реализовав протоколы стека в своей версии ОС UNIX. Широкое распространение ОС UNIX привело и к широкому распространению протокола IP и других протоколов стека. На этом же стеке работает всемирная информационная сеть Internet, чье подразделение Internet Engineering Task Force (IETF) вносит основной вклад в совершенствование стандартов стека, публикуемых в форме спецификаций RFC.
Лидирующая роль стека TCP/IP объясняется следующими его свойствами:
- Это наиболее завершенный стандартный и в то же время популярный стек сетевых протоколов, имеющий многолетнюю историю.
- Почти все большие сети передают основную часть своего трафика с помощью протокола TCP/IP.
- Это метод получения доступа к сети Internet.
- Этот стек служит основой для создания intranet- корпоративной сети, использующей транспортные услуги Internet и гипертекстовую технологию WWW, разработанную в Internet.
- Все современные операционные системы поддерживают стек TCP/IP.
- Это гибкая технология для соединения разнородных систем, как на уровне транспортных подсистем, так и на уровне прикладных сервисов.
- Это устойчивая масштабируемая межплатформенная среда для приложений клиент-сервер.
Так как стек TCP/IP был разработан до появления модели взаимодействия открытых систем ISO/OSI, то, хотя он также имеет многоуровневую структуру, соответствие уровней стека TCP/IP уровням модели OSI достаточно условно.
Структура стека TCP/IP, она включает в себя всего 4 уровня. Примерное соответствие c уровнями модели OSI представлено на рисунке 2.
Рисунок 2
Верхний уровень (Application) называется прикладным. За долгие годы использования в сетях различных стран и организаций стек TCP/IP накопил большое количество протоколов и сервисов прикладного уровня. К ним относятся такие широко используемые протоколы, как протокол копирования файлов FTP, протокол эмуляции терминала telnet, почтовый протокол SMTP, используемый в электронной почте сети Internet, гипертекстовые сервисы доступа к удаленной информации, такие как WWW и многие другие.
Следующий уровень (Transmission) называется транспортным. На этом уровне функционируют протокол управления передачей TCP (Transmission Control Protocol) и протокол дейтаграмм пользователя UDP (User Datagram Protocol). Протокол TCP обеспечивает надежную передачу сообщений между удаленными прикладными процессами за счет образования виртуальных соединений. Протокол UDP обеспечивает передачу прикладных пакетов дейтаграммным способом, как и IP, и выполняет только функции связующего звена между сетевым протоколом и многочисленными прикладными процессами.
Следующий уровень (Internetwork) - это уровень межсетевого взаимодействия, который занимается передачей пакетов с использованием различных транспортных технологий локальных сетей, территориальных сетей, линий специальной связи и т. п.
В качестве основного протокола сетевого уровня (в терминах модели OSI) в стеке используется протокол IP, который изначально проектировался как протокол передачи пакетов в составных сетях, состоящих из большого количества локальных сетей, объединенных как локальными, так и глобальными связями. Поэтому протокол IP хорошо работает в сетях со сложной топологией, рационально используя наличие в них подсистем и экономно расходуя пропускную способность низкоскоростных линий связи.
К уровню межсетевого взаимодействия относятся и все протоколы, связанные с составлением и модификацией таблиц маршрутизации, такие как протоколы сбора маршрутной информации RIP (Routing Internet Protocol) и OSPF (Open Shortest Path First), а также протокол межсетевых управляющих сообщений ICMP (Internet Control Message Protocol). Последний протокол предназначен для обмена информацией об ошибках между маршрутизаторами сети и узлом - источником пакета. С помощью специальных пакетов ICMP сообщается о невозможности доставки пакета, о превышении времени жизни или продолжительности сборки пакета из фрагментов, об аномальных величинах параметров, об изменении маршрута пересылки и типа обслуживания, о состоянии системы и т.п.
Самый нижний уровень (Network) соответствует физическому и канальному уровням модели OSI. Этот уровень в протоколах TCP/IP не регламентируется, но поддерживает все популярные стандарты физического и канального уровня: для локальных сетей это Ethernet, Token Ring, FDDI, Fast Ethernet, 100VG-AnyLAN, для глобальных сетей - протоколы соединений "точка-точка" SLIP и PPP, протоколы территориальных сетей с коммутацией пакетов X.25, frame relay. Разработана также специальная спецификация, определяющая использование технологии ATM в качестве транспорта канального уровня. Обычно при появлении новой технологии локальных или глобальных сетей она быстро включается в стек TCP/IP за счет разработки соответствующего RFC, определяющего метод инкапсуляции пакетов IP в ее кадры.
Краеугольным камнем всей архитектуры является межсетевой протокол IP (Internet Protocol). С его помощью реализуется адресация узлов сети и доставка данных.
Межсетевой протокол IP специфицирован в RFC 791. Его основные характеристики перечислены ниже:
- реализует обмен информации пакетами, которые будем называть IP-сегментами (максимальный размер IP-сегмента - 65535 байт);
- является протоколом взаимодействия без установления логического соединения;
- для адресации узлов сети используется адрес длиной 4 байта;
- обеспечивает в случае необходимости фрагментацию IP-сегментов;
- IP-сегменты имеют конечное время жизни в сети;
- не гарантирует надежность доставки IP-сегментов адресату;
- не имеет средств управления интенсивностью передачи IP-сегментов посылающей стороной (flow control);
- не гарантирует правильную последовательность IP-сегментов на принимающей стороне.
Главными особенностями протокола IP является отсутствие ориентации на физическое или виртуальное соединение. Это значит, что прежде чем послать пакет в сеть, модуль операционной системы, реализующий IP, не проверяет возможность установки соединения, т.е. никакой управляющей информации кроме той, что содержится в самом IP-пакете, по сети не передается.
Таким образом, вся информация о пути, по которому должен пройти пакет берется из самой сети в момент прохождения пакета. Именно эта процедура и называется маршрутизацией в отличие от коммутации, которая используется для предварительного установления маршрута следования данных, по которому потом эти данные отправляют.
Принцип маршрутизации является одним из тех факторов, который обеспечил гибкость сети Internet и ее победу в соревновании с другими сетевыми технологиями. Надо сказать, что маршрутизация является довольно ресурсоемкой процедурой, так как требует анализа каждого пакета, который проходит через шлюз или маршрутизатор, в то время как при коммутации анализируется только управляющая информация, устанавливается канал, физический или виртуальный, и все пакеты пересылаются по этому каналу без анализа маршрутной информации. Однако, эта слабость IP одновременно является и его силой. При неустойчивой работе сети пакеты могут пересылаться по различным маршрутам и затем собираться в единое сообщение. При коммутации путь придется каждый раз вычислять заново для каждого пакета, а в этом случае коммутация потребует больше накладных затрат, чем маршрутизация.
Формат IP пакета протокола представлен на рисунке 3
Формат пакета Ipv4
Рисунок 3
Фактически, в этом заголовке определены все основные данные, необходимые для перечисленных выше функций протокола IP: адрес отправителя (4-ое слово заголовка), адрес получателя (5-ое слово заголовка), общая длина пакета (поле Total Length) и тип пересылаемой датаграммы (поле Protocol).
Используя данные заголовка, машина может определить на какой сетевой интерфейс отправлять пакет. Если IP-адрес получателя принадлежит одной из ее сетей, то на интерфейс этой сети пакет и будет отправлен, в противном случае пакет отправят на другой шлюз.
Если пакет слишком долго "бродит" по сети, то очередной шлюз может отправить ICMP-пакет на машину-отправитель для того, чтобы уведомить о том, что надо использовать другой шлюз. При этом, сам IP-пакет будет уничтожен. На этом принципе работает программа ping, которая используется для деления маршрутов прохождения пакетов по сети.
Зная протокол транспортного уровня, IP-модуль производит раскапсулирование информации из своего пакета и ее направление на модуль обслуживания соответствующего транспорта.
При обычной процедуре инкапсулирования пакет просто помещается в поле данных фрейма, а в случае, когда это не может быть осуществлено, то разбивается на более мелкие фрагменты. Размер максимально возможного фрейма, который передается по сети, определяется величиной MTU (Maximum Transmission Unit), определенной для протокола канального уровня. Для того, чтобы потом восстановить пакет IP должен держать информацию о своем разбиении. Для этой цели используется поля "flags" и "fragmentation offset". В этих полях определяется, какая часть пакета получена в данном фрейме, если этот пакет был фрагментирован на более мелкие части.
Принципы построения IP-адресов
IP-адрес это уникальное 32-битовое значение, имеющее 2-уровневую структуру, один уровень определяет локальную сеть, а другой – хост, принадлежащий этой сети.IP-адреса принято записывать в виде 4х десятичных цифр, разделенных точками (например, 195.19.221.65). Принцип иерархии был применен для логического разделения IP-адреса как минимум на две части, одна из которых идентифицирует сеть, а вторая – устройство, например маршрутизатор. Возможно еще и включение третей части – для описания подсетей.
Адрес узла уникально идентифицирует индивидуальное устройство в данной сети или подсети; адрес сети, назначаемый какой-либо организации, идентифицирует эту сеть в Internet. Если сеть организации имеет несколько сегментов, целесообразно будет присвоить каждому сегменту адреса, принадлежащие разным подсетям. При этом каждой подсети присваивается собственный логический адрес. Все хосты принадлежащие одному сегменту, будут иметь один и тот же адрес подсети.
Существует 5 основных классов логических адресов(A, B, C, D и E). Эти классы отличаются друг от друга количеством битов, отведенных на адрес сети и адрес хоста в сети. На рисунке 4 показаны эти пять классов.
Классы IP-адресов
Рисунок 4
Опираясь на эту структуру, можно подсчитать характеристики каждого класса в терминах числа сетей и числа машин в каждой сети.
Таблица 1. Характеристики классов IP-адресов
| Класс | Значение битов | Диапазон значений первого октета | Возможное количество сетей | Возможное количество узлов |
| А | Первый бит – 0 | 1 - 126 | 126 | 16777214 |
| B | Первые 2 бита –1,0 | 128 – 191 | 16382 | 65534 |
| C | Первые три бита – 1,1,0 | 192 – 223 | 2097150 | 254 |
| D | Первые четыре бита – 1,1,1,0 | 224 – 239 | - | 228 |
| E | Первые пять бит – 1,1,1,1,0 | 240 – 247 | - | 227 |
Адреса класса A предназначены для использования в больших сетях общего пользования.
Адреса класса B предназначены для использования в сетях среднего размера (сети больших компаний, научно-исследовательских институтов, университетов).
Адреса класса C предназначены для использования в сетях с небольшим числом компьютеров (сети небольших компаний и фирм).
Адреса класса D используют для обращения к группам компьютеров(multicasting).
Адреса класса E – зарезервированы лдя будущего использования.
Среди всех IP-адресов имеется несколько зарезервированных под специальные нужды. Ниже приведена таблица зарезервированных адресов.
Таблица 2 Выделенные IP-адреса
| IP-адрес | Значение |
| Все нули | Данный узел сети |
| номер сети | все нули | данная IP-сеть |
| все нули | номер узла | узел в данной (локальной) сети |
| все единицы | все узлы в данной локальной IP-сети |
| номер сети | все единицы | все узлы указанной IP-сети |
| 127.0.0.1 | "петля" |
Адрес 127.0.0.1 предназначен для тестирования программ и взаимодействия процессов в рамках одного компьютера. В большинстве случаев в файлах настройки этот адрес обязательно должен быть указан, иначе система при запуске может зависнуть (как это случается в SCO Unix). Наличие "петли" чрезвычайно удобно с точки зрения использования сетевых приложений в локальном режиме для их тестирования и при разработке интегрированных систем. Вообще, зарезервирована вся сеть 127.0.0.0. Эта сеть класса A реально не описывает ни одной настоящей сети.
Некоторые зарезервированные адреса используются для широковещательных сообщений. Например, номер сети (строка 2) используется для посылки сообщений этой сети (т.е. сообщений всем компьютерам этой сети). Адреса, содержащие все единицы, используются для широковещательных посылок (для запроса адресов, например).
Реальные адреса выделяются организациями, предоставляющими IP-услуги, из выделенных для них пулов IP-адресов. Первичное же распределение IP-адресов осуществляется так называемыми «RIR» - региональными реестрами сети Интернет. Это American Registry Internet Numbers (ARIN) Северная Америка, Reseaux IP Europeens Network Coordination Center (RIPE NCC) Европа, Asian Pacific Network Information Center (APNIC) Азия и Океания, Latin American and Caribbean Internet Addresses Registry (LACNIC) Латинская Америка и Карибы, African Network Information Center (AfriNIC) Африка. Всё это некоммерческие организации, основными источниками финансовых поступлений являются регистрационные взносы за назначение и обслуживание блоков IP-адресов.
Сегодня сеть Интернет представляет собой конгломерат автономных систем (AS – Autonomous Systems), которые делят между собой зоны административной ответственности и определяют для различных организаций правила маршрутизации. Автономные системы создаются на основе маршрутизаторов, которые могут работать с протоколами внутреннего шлюза Interior Gateway Protocols(IGP), такими как: протокол информации о маршрутах Routing Information Protocol (RIP), расширенный протокол внутреннего шлюза Exchanged Interior Gateway Protocol (EIGP), протокол предпочтительного выбора кратчайшего пути Open Shortest Path First (OSPF) и протокол обмена маршрутной информацией между промежуточными системами Intermediate System-to-Intermediate System (IS-IS). Все эти протоколы и граничные с ними взаимодействуют посредством протокола внешнего шлюза Exterior Gateway Protocol (EGP). В настоящее время стандартом де-факто для сети Internet является протокол граничного шлюза версии 4 (Border Gateway Protocol Version 4 – BGP-4), описанный в RFC 1771.
Маршрутизация
Маршрутизация – это процесс, при котором осуществляется передача единиц информации. В компьютерных сетях трафик, создаваемый пользователями (будь то электронная почта, графические или текстовые документы), от логического отправителя передаются логическому получателю. Устройства в сети имеют логические адреса, таким образом, к ним можно получить доступ как индивидуально, так и в составе групп устройств.
Чтобы маршрутизатор мог работать эффективно как коммутирующее устройство, ему должна быть известна логическая топология сети и должна иметься возможность обмена данными со всеми соседними устройствами.
Механизм получения и поддержки данных о топологии называется функцией маршрутизации. Ретрансляция трафика через маршрутизатор от входного интерфейса на выходной представляет собой отдельную функцию коммутации.
Коммутация относительно проста. С другой стороны, определение маршрута может быть очень сложным процессом.
Определение маршрута
Определение маршрута может базироваться на различных показателях (величинах, результирующих из алгоритмических вычислений по отдельной переменной - например, длина маршрута) или комбинациях показателей. Программные реализации алгоритмов маршрутизации высчитывают показатели маршрута для определения оптимальных маршрутов к пункту назначения.
Для облегчения процесса определения маршрута, алгоритмы маршрутизации инициализируют и поддерживают таблицы маршрутизации, в которых содержится маршрутная информация. Маршрутная информация изменяется в зависимости от используемого алгоритма маршрутизации.
Алгоритмы маршрутизации заполняют маршрутные таблицы неким множеством информации. Ассоциации "Пункт назначения/следующая пересылка" сообщают роутеру, что определенный пункт назначения может быть оптимально достигнут путем отправки пакета в определенный роутер, представляющий "следующую пересылку" на пути к конечному пункту назначения. При приеме поступающего пакета роутер проверяет адрес пункта назначения и пытается ассоциировать этот адрес со следующей пересылкой. На рис. 5 приведен пример маршрутной таблицы "место назначения/следующая пересылка".
Рисунок 5
В маршрутных таблицах может содержаться также и другая информация. "Показатели" обеспечивают информацию о желательности какого-либо канала или тракта. Роутеры сравнивают показатели, чтобы определить оптимальные маршруты. Показатели отличаются друг от друга в зависимости от использованной схемы алгоритма маршрутизации. Далее в этой главе будет представлен и описан ряд общих показателей.
Роутеры сообщаются друг с другом (и поддерживают свои маршрутные таблицы) путем передачи различных сообщений. Одним из видов таких сообщений является сообщение об "обновлении маршрутизации". Обновления маршрутизации обычно включают всю маршрутную таблицу или ее часть. Анализируя информацию об обновлении маршрутизации, поступающую ото всех роутеров, любой из них может построить детальную картину топологии сети. Другим примером сообщений, которыми обмениваются роутеры, является "объявление о состоянии канала". Объявление о состоянии канала информирует другие роутеры о состоянии каналов отправителя. Канальная информация также может быть использована для построения полной картины топологии сети. После того, как топология сети становится понятной, роутеры могут определить оптимальные маршруты к пунктам назначения.
Коммутация
Алгоритмы коммутации сравнительно просты и в основном одинаковы для большинства протоколов маршрутизации. В большинстве случаев главная вычислительная машина определяет необходимость отправки пакета в другую главную вычислительную машину. Получив определенным способом адрес роутера, главная вычислительная машина-источник отправляет пакет, адресованный специально в физический адрес роутера (уровень МАС), однако с адресом протокола (сетевой уровень) главной вычислительной машины пункта назначения.
После проверки адреса пункта назначения пакета роутер определяет, знает он или нет, как передать этот пакет к следующему роутеру. Во втором случае (когда роутер не знает, как переслать пакет) пакет, как правило, игнорируется. В первом случае роутер отсылает пакет к следующему роутеру путем замены физического адреса пункта назначения на физический адрес следующего роутера и последующей передачи пакета.
Следующая пересылка может быть или не быть главной вычислительной машиной окончательного пункта назначения. Если нет, то следующей пересылкой, как правило, является другой роутер, который выполняет такой же процесс принятия решения о коммутации. По мере того, как пакет продвигается через сеть, его физический адрес меняется, однако адрес протокола остается неизменным. Этот процесс иллюстрируется на Рис. 6
Рисунок 6
В изложенном выше описании рассмотрена коммутация между источником и системой конечного пункта назначения. Международная Организация по Стандартизации (ISO) разработала иерархическую терминологию, которая может быть полезной при описании этого процесса. Если пользоваться этой терминологией, то устройства сети, не обладающие способностью пересылать пакеты между подсетями, называются конечными системами (ES), в то время как устройства сети, имеющие такую способность, называются промежуточными системами (IS). Промежуточные системы далее подразделяются на системы, которые могут сообщаться в пределах "доменов маршрутизации" ("внутридоменные" IS), и системы, которые могут сообщаться как в пределах домена маршрутизации, так и с другими доменами маршрутизации ("междоменные IS"). Обычно считается, что "домен маршрутизации" - это часть сети, находящейся под общим административным управлением и регулируемой определенным набором административных руководящих принципов. Домены маршрутизации называются также "автономными системами" (AS). Для определенных протоколов домены маршрутизации могут быть дополнительно подразделены на "участки маршрутизации", однако для коммутации как внутри участков, так и между ними также используются внутридоменные протоколы маршрутизации.