Иерархическая декомпозиция и мультифрактальное моделирование компьютерных сетей

8.1. Иерархическая декомпозиция глобальных сетей на автономные подсети

Увеличение числа N узлов и числа М каналов связи ТКС, обслуживаемых одним маршрутизатором, приводит к нежелательным последствиям, а именно:

- увеличивается размер таблицы оптимальных маршрутов и объём памяти для их хранения (порядка О(N²)- О(М²));

- возрастает время вычисления (планирования) и корректировки (адаптации) оптимальных маршрутов;

- увеличивается размер передаваемых пакетов и нагрузка на каналы связи ТКС.

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

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

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

При определённых условиях необходимое число уровней в иерархически связанных маршрутизаторах глобальной ТКС с N узлами пропорционально величине log N. Однако снижение требований к объёму памяти этих маршрутизаторов в общем случае приводит к увеличению стоимости (например, длины) синтезированных (спланированных) маршрутов.

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

- IP-адреса узловых компьютеров (хостов) своей подсети;

- IP-адреса остальных подсетей глобальной ТКС;

- IP-адрес глобальной ТКС.

Используя эту табличную БД и сетевой интерфейс, маршрутизатор получает возможность передачи IP-пакетов как по IP-адресам внутри своей автономной подсети, так и по IP-адресам других (удалённых) подсетей и глобальной ТКС.

После поступления в маршрутизатор IP-пакета указанный в нём IP-адрес узла-получателя (адресата) отыскивается в локальной БД. Если адресат находится в автономной подсети, обслуживаемой своим «персональным» маршрутизатором, то IP-пакет посылается непосредственно к нему. Если же адресат находится в другой подсети, IP-пакет посылается через магистраль другому маршрутизатору по IP-адресу этой подсети.

Таким образом, каждый маршрутизатор использует IP-адреса своих узлов (хостов) и остальных подсетей, а не пары «подсеть-хост», что значительно сокращает объём табличной БД маршрутизатора. Практически он знает, как оптимально передать IP-пакет всем узлам- хостам своей подсети или как получить доступ ко всем остальным подсетям и их маршрутизаторам, а не к их конкретным узлам-хостам.

8.2. Иерархическая адресация и маршрутизация потоков данных в глобальных компьютерных сетях

На рис. 8.1. представлен пример иерархической декомпозиции глобальной ТКС на три «зональные» подсети первого уровня. Эти подсети имеют внутренние (локальные) маршрутизаторы R₁₁ и R₁₂ в подсети 1, R₂₁ и R₂₂ в подсеть 2 и R₃₁ в подсеть 3, которые в свою очередь являются узлами-маршрутизаторами магистральной подсети второго уровня.

Рис. 8.1. Пример декомпозиции глобальной ТКС на три подсети для иерархической

маршрутизации

Узлы-маршрутизаторы R₁₁ и R₁₂, R₂₁ и К₂₂ и R₃₁ осуществляют распределённую оптимальную маршрутизацию как внутри «своих» подсетей 1, 2 и 3 уровня, так и в магистральной подсети второго уровня, каналы связей которой изображены на рис. 8.1. двойными линиями.

Пакет данных с IP-адресом узла-получателя, находящегося в другой («конечной») подсети, сначала посылается в «ближайший» маршрутизатор магистральной подсети второго уровня, находящийся также в своей «начальной» подсети первого уровня. Затем он посылается этим маршрутизатором по оптимальному маршруту к маршрутизатору подсети назначения, который в свою очередь отправляет этот пакет по оптимальному маршруту к узлу-получателю своей («конечной») подсети.

При этом обычно используются 16-разрядные глобальные адреса получателей, состоящие из 6-разрядного кода подсети и 10-разрядного адреса узла внутри подсети. Такая адресация позволяет охватывать 64 подсети и 1022 узла внутри подсети глобальной ТКС.

В каждом узле-хосте подсети первого уровня имеются две табличные БД – таблицы маршрутов (данные об исходящем канале минимальной стоимости) и таблицы стоимостей (данные о стоимости каналов связи). Узлы-маршрутизаторы магистральной подсети второго уровня должны иметь такие БД для каждого уровня глобальной ТКС, а также иметь данные о стоимости маршрутов передачи пакетов к узлу-получателю через каждый исходящий канал.

Для гарантированной доставки пакетов к узлу-получателю ТКС целесообразно иметь счётчик числа каналов (или их стоимостей), входящих в оптимальный маршрут. Если максимальный порог (например, диаметр ТКС) счётчика для данного узла-получателя превышается на любом уровне иерархической маршрутизации, то рассматриваемый маршрут считается нереализуемым и все пакеты сбрасываются или возвращаются к узлу-источнику.

При разделении глобальной ТКС на области или автономные подсети каждый узел-хост получает уникальный IP-адрес и маску, представленные на рис. 8.2. Например, если некоторый узел-хост имеет адрес 128.32.134.56 и 32-битовую маску 255.255.255.00, т.е. 24 единицы в начале и 8 нулей в конце, то глобальная ТКС имеет адрес 128.32., а подсеть – адрес 128.32.134. Подсеть узла-хоста определяется операцией Å побитового сложения IP-адреса и маски.

Здесь R_k – имена соседних узлов-маршрутизаторов, w_{k-1, k} – стоимость (вес) канала связи от R_k-1 до R_k. Маршрутизатор R₀ посылает сообщение по всем своим исходящим каналам связи.

Когда маршрутизатор R_j получает сообщение , он проверяет его источник и, если R_j = R₀, то маршрутизатор R_j отбрасывает пакет. В противном случае маршрутизатор R_j проверяет наибольший порядковый номер n* сообщений от R₀, которые были получены раньше. Если n* < n, то это означает, что R_j получил новое сообщение от R₀. После этого маршрутизатор R_j обновляет значение наибольшего порядкового номера, сохраняет переданное сообщение и посылает его по всем исходящим R₀ каналам связи, кроме канала, по которому оно было передано.

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

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

Алгоритм внутренней (локальной) маршрутизации подсети реализуется с помощью протокола внутреннего шлюза. Сначала в качестве такого протокола в сети Internet использовался протокол дистанционно-векторной маршрутизации (Routing Information Protocol, RIP), основанный на алгоритме маршрутизации Беллмана-Форда (Bellman-Ford)[3]. Однако основным недостатком этого алгоритма, имеющего вычислительную сложность порядка O(N³), является сходимость к оптимальному маршруту при большом числе узлов автономной подсети.

Начиная с 1990 года, многие разработчики маршрутизаторов перешли на новый перспективный протокол открытого выбора первого кратчайшего маршрута (Open Shortest Path First, OSPF), основанный на алгоритме маршрутизации Дейкстры (Dijkstra)[1, 3], имеющего вычислительную сложность порядка O(N²). Этот OSPF-протокол обычно не работает с отдельными узловыми компьютерами (хостами), а поддерживает следующие три типа сетей и линий связи:

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

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

Графовая модель этой сети представляет собой направленный граф, вершинам которого соответствуют маршрутизаторы, а дугам между ними – веса (стоимости) каналов связи, причем эти веса w_sf и w_fs могут быть различными в зависимости от направления передачи данных. На основе этой графовой модели каждый маршрутизатор вычисляет оптимальный маршрут передачи данных внутри автономной или локальной подсети, которую он обслуживает.

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

Таким образом, область является некоторым обобщением автономной подсети или совпадает с ней. Её топология и другие параметры известны внутренним маршрутизаторам. Все области соединены с помощью магистралей (например, с помощью туннелей) так, что из любой области или подсети можно по магистрали попасть в любую другую. Каждый маршрутизатор, соединённый с одной или несколькими областями, является частью магистрали.

Глобальная ТКС имеет магистральную область, называемую обычно областью 0.

Каждый маршрутизатор подсети глобальной ТКС имеет локальную БД (топология, IP-адреса и т.п.) и реализует определенный алгоритм оптимальной маршрутизации. С помощью этого алгоритма он вычисляет оптимальные маршруты от себя до остальных маршрутизаторов, связанных с ним магистралью. Если маршрутизатор является «пограничным», т.е., например, обслуживает «соседние» подсети глобальной ТКС, он должен иметь также БД о каждой из этих подсетей, чтобы иметь возможность вычислять оптимальные маршруты внутри каждой такой подсети.

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

В общем случае при маршрутизации потоков данных в глобальных ТКС могут возникнуть три типа маршрутов:

- внутренние (локальные) маршруты, расположенные целиком внутри соответствующей области или подсети глобальной ТКС;

- внешние (глобальные) маршруты, соединяющие магистральные маршрутизаторы областей или подсети глобальной ТКС;

- межсетевые маршруты, соединяющие маршрутизаторы различных глобальных ТКС.

Внутренние маршруты определяются легко, так как каждому маршрутизатору области или подсети заранее известны (хранятся в его локальной БД) оптимальные маршруты до всех внутренних узлов (хостов) подсети или маршрутизаторов своей области.

OSPF-протокол ориентирован на использование методов и алгоритмов маршрутизации, удовлетворяющих следующим требованиям:

- открытость алгоритма, т.е. алгоритм должен быть опубликован в открытой литературе и не может быть частной собственностью автора или запатентовавшей его фирмы;

- универсальность (многокритериальность) алгоритма, т.е. алгоритм должен допускать возможность определения оптимальных маршрутов для разных критериев качества (стоимости) маршрутов (длина каналов связи, их пропускная способность, задержка времени, надежность и т.п.);

- гибкость (динамичность) алгоритма, т.е. алгоритм должен реагировать на динамику сети и автоматически пересматривать оптимальный маршрут в соответствии с изменением топологии сети или весов каналов связи;

- адаптивность алгоритма, т.е. алгоритм должен автоматически приспосабливаться к изменениям топологии ТКС и к характеру (типу) и объёму (нагрузке на каналы связи) трафика, соответствующим образом перестраивая оптимальный маршрут (например, в зависимости от информации, передаваемой в поле «тип службы» IP-пакета);

- многовариантность (многозначность, альтернативность) алгоритма, т.е. алгоритм должен формировать не один оптимальный маршрут, а несколько оптимальных или субоптимальных маршрутов для управляемого распределения сетевой нагрузки на каналы связи различных маршрутов;

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

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