Повышение эффективности функционирования локальных вычислительных сетей при использовании логических свойств их структур

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

Коммутация в последние годы считается одной из самых популярных современных технологий. Коммутаторы являются протоколонезависимыми устройствами. Они работают на уровне 2 модели OSI/OSI, что дает им очень ограниченные возможности по управлению трафиком, однако, благодаря аппаратной реализации обработки пакетов, они достигают достаточно высокой производительности. Аппаратная технология коммутации может быть либо централизованной, либо распределенной. При централизованной коммутации все пакеты, вне зависимости от того, в какой порт какого модуля они пришли, обрабатываются центральным процессорным блоком, что плохо, потому что с ростом числа портов увеличивается нагрузка на центральный модуль и падает производительность. Кроме того, имеется центральная точка выхода всей системы из строя. В распределенной сети каждый модуль или группа портов обрабатывают свои пакеты сами, вне зависимости от трафика других модулей. Основной трафик группы замкнут внутри группы, и лишь при необходимости связаться с рабочей станцией из другой группы будет осуществляться передача данных через коммутатор. В этом случае с ростом числа портов производительность всей системы растет. Главным недостатком сетевых технологий на основе коммутаторов является то, что все их базовые функции работают при существовании только одного логического пути между двумя любыми устройствами в сети. Таким образом, объединение ЛВС или сетевых сегментов с помощью коммутаторов возможно только при использовании сетевой топологии остовного дерева, которая исключает наличие альтернативных путей и характеризуется низкой структурной надежностью.

Идея маршрутизации заключается в возможности передавать пакеты данных между сетями любых типов. У маршрутизаторов намного больше сведений для управления трафиком, т.к. они работают на третьем и даже четвертом уровнях, на которых в основном и осуществляются все продвинутые функции защиты. Кроме того, применение маршрутизаторов позволяет использовать ячеистые сетевые топологии, которые обеспечивают альтернативные пути доставки сообщений. Используя свои маршрутные таблицы, маршрутизатор способен выбирать оптимальные пути для передачи пакетов данных. Большим недостатком современных маршрутизаторов является то, что они достаточно дороги и работают, по сути, как обычные оптимизированные компьютеры под управлением специальных программ. Процесс обработки пакетов данных маршрутизатором сложен и длителен, он требует затрат процессорного времени и памяти. Если раньше использование маршрутизаторов экономически оправдывалось достаточно низким межсетевым трафиком, то в последние годы в связи с резким увеличением межсетевого трафика широкое использование маршрутизаторов стало невыгодным. Однако во многих случаях маршрутизаторы просто незаменимы.

Идея объединить достоинства коммутаторов и маршрутизаторов была реализована в маршрутизирующих коммутаторах. Эти устройства снабжены множеством интерфейсных портов локальных и глобальных сетей. С помощью маршрутизирующих коммутаторов станции могут устанавливать соединение с пересылкой пакетов в соответствии с уровнем 2, действуя, как обычный коммутатор, либо выступать в роли маршрутизатора, обрабатывая пакеты на третьем уровне. Практически это определяется тем, где находится станция назначения: в той же самой подсети или в другой. Аппаратная реализация коммутатора третьего уровня представляет собой непростую задачу, поэтому производители в основном ограничиваются для реализации механизма маршрутизации достаточно узким спектром наиболее часто используемых протоколов: IP, IPX, RIP, OSPF.

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

Альтернативным решением, позволяющим использовать преимущества маршрутизаторов, является повышение эффективности функционирования сетей на основе маршрутизаторов. Этого можно добиться, если изменить топологию сети так, чтобы она стала логически регулярной. Предлагается подход, который позволяет использовать в качестве основы для построения подобной структуры графы кодовых пересечений ( Кузнецова , 1984б; Борисова , 1993а). Использование логических свойств подобных топологий позволяет избавить маршрутизатор от его основного недостатка – необходимости хранения и обработки маршрутных таблиц, величина которых находится в квадратичной зависимости от числа узлов в сети. По существу, это путь программной оптимизации функций маршрутизатора. Освобожденная память маршрутизатора может быть использована, например, для реализации продвинутых функций из уровня 4. Достоинством данного подхода, по сравнению с использованием маршрутизирующих коммутаторов, является то, что предлагаемый метод не требует дополнительного оборудования и является экономически выгодным.

2.    Основные понятия и определения

Прежде всего, дадим основные понятия и определения, используемые в данной работе. Будем говорить, что две кодовые комбинации с длиной n и основанием k пересекаются по n – r элементам, если n – r последних элементов одной кодовой комбинации совпадают с n – r первыми элементами другой (0 <  i <  n ). Иными словами, кодовая комбинация ε ₁ , ε ₂ ,…, ε _n ( ε _i = 0, 1, 2,…, k - 1, i = 1, 2, 3,…, n ) пересекается с кодовой комбинацией ε′ 1 , ε′ 2 ,…, ε′ n ( ε′ i = 0, 1, 2,…, k - 1, i = 1, 2, 3,…, n ), если ε′ i+r = ε i или ε′ _i = ε _i+r ( i = 1, 2, 3,…, n – r ). Каждой кодовой комбинации ε ₁ , ε ₂ ,…, ε _n будем ставить в соответствие номер N = ∑ ⁿ i=1 ε i k^n–i . Очевидно, что 0 ≤ N ≤ kⁿ– 1.

Обозначим множество кодовых комбинаций длиной n и основанием k через А . Отображение Г множества А в себя зададим так, чтобы каждой кодовой комбинации a ∈ A ставились в соответствие те кодовые комбинации из А , у которых первые n – r элементов совпадают с последними n – r элементами кодовой комбинации a . Параметр r будем называть зацеплением кодовых комбинаций. Обозначим множество кодовых комбинаций, поставленных в соответствие a через Г_a . Отображение Г_a будем называть прямым. Отображение Г_a ^-1 будем называть обратным, если оно определяет такое соответствие кодовых комбинаций, при котором каждой кодовой комбинации a ∈ A ставились в соответствие те кодовые комбинации из А , у которых последние n – r элементов совпадают с первыми ( n – r ) элементами кодовой комбинации a . Множество А и отображение Г множества А в себя задают псевдограф ( А , Г ). Будем называть его псевдографом кодовых пересечений с параметрами n , k , r и обозначать ПКП( n , k , r ). Элементы множества А (кодовые комбинации) можно изобразить точками плоскости, а пары точек a ′ и a ′′ соединить непрерывной линией (дугой) со стрелкой, направленной от a ′ к a ′′ , если a ′′ ∈ Г a ′ . Уберем из множества дуг ПКП( n , k , r ) все пары ( aa ), a ∈ Г_a , т.е. петли. Оставшееся множество дуг обозначим через V . Полученный граф назовем графом кодовых пересечений с параметрами n , k , r и обозначим ГКП( n , k , r ). Граф кодовых пересечений, построенный в соответствии с прямым (или обратным) отображением, является ориентированным (рис. 1). Граф кодовых пересечений, в котором используются оба типа отображений, является неориентированным (рис. 2).

Рис. 2. НеорГКП (3, 2, 1)

ПКП и ГКП однозначно задаются своими матрицами смежности. В матрице смежности графа элемент ( i, j ), находящийся на пересечении i -той строки и j -того столбца равен 1, если в графе дуга исходит из вершины с номером i и входит в вершину с номером j. Матрица смежности ПКП( n , k , r ) имеет размер kⁿ х kⁿ , в каждой строке содержит k единиц, сдвинутых относительно единиц предыдущей строки на k позиций. Матрица смежности ГКП( n , k , r ) отличается от матрицы смежности ПКП( n , k , r ) отсутствием диагональных единиц. Свойства графов кодовых пересечений и их матриц смежности исследованы в работе ( Кузнецова , 19846; Борисова , 1993а).

3.    Определение путей в локальных вычислительных сетях

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

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

• 2.    Пропускные способности узлов равны. На практике это можно рассматривать с точки зрения унификации оборудования и считать полезным.

• 3.    Равномерное размещение узлов на территории. Такое допущение на практике можно использовать, когда стоимость каналов не является определяющей. В этом случае вместо конкретной топологии можно рассматривать структуру сети.

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

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

Рис. 3. Объединение ЛВС с помощью маршрутизаторов CCG

Если топология ЛВС соответствует ГКП, то задача маршрутизации существенно упрощается. В этом случае, благодаря наличию логической регулярности в структуре, информация о маршрутах в сети заложена в системе нумерации узлов. Алгоритмы нумерации узлов в различных сетях в подграфы ГКП разработаны в работах ( Кузнецова , 1984а; Кузнецова , 1989; Борисова , 1992; Борисова , 1993б).

Один из возможных вариантов объединения ЛВС с помощью маршрутизаторов CCG (Code Cross Graph – граф кодовых пересечений), построенный на основе ГКП(3, 2, 1) (рис. 1, 2), изображен на рис. 3.

Использование моделей ГКП при объединении ЛВС позволяют получить ряд дополнительных преимуществ по сравнению с традиционным подходом, которые являются следствием оригинального алгоритма маршрутизации. Определение минимального по числу транзитов путей в ГКП производится в соответствии с правилами, разработанными в работах (Кузнецова, 1985; Борисова, Борисов, 1995). Суть алгоритма маршрутизации сводится в общем случае к выполнению ряда процедур над номерами узлов отправителя и получателя. Для реализации алгоритма маршрутизации необходимо специальным образом закодировать номера узлов сети. Для определения пути длиной l в ГКП(n, k, r) надо, используя кодовые последовательности символов в записи номеров узлов отправителя и получателя, составить кодовую последовательность символов, которая представляет собой сокращенную запись пути (Борисова, 1993в). При чтении этой последовательности по n символов с шагом r символов получается последовательность номеров узлов, которые составляют кратчайший путь для передачи пакетов длиной в l переприемов. Как показано в работе (Кузнецова, 1985), процедура определения кратчайшего пути в сети проста по технологии, экономична в отношении используемой памяти и может быть выполнена как любой рабочей станцией, так и любым маршрутизатором.

Для практической реализации алгоритма маршрутизации в состав программных средств каждого узла (маршрутизатора) сети должна входить программа определения кратчайшего пути в графе кодовых пересечений CCGR (Code Cross Graph Route). Рассмотрим работу сети (рис. 5) при нормальной передаче пакетов данных и в случае обнаружения отказа. При передаче пакетов из рабочей станции А сети LAN2 в рабочую станцию В сети LAN8 будут выполнены следующие операции.

• 1.    Рабочая станция А сети LAN2 формирует дейтаграмму, инкапсулирует ее в кадр и посылает в сеть.

• 2.    Используя программу CCGR, маршрутизатор CCG001 определяет, что минимальный путь из сети LAN2 в LAN8 проходит через маршрутизаторы с номерами 001-011-110. Сокращенная запись кратчайшего пути записывается в дополнительное поле служебной части пакета данных.

• 3.    Маршрутизатор CCG001 проверяет наличие связи с соседним маршрутизатором CCG011.

• 4.    При наличии связи маршрутизатор CCG001 посылает пакет в маршрутизатор CCG011.

• 5.    Используя программу CCGR, маршрутизатор CCG011 считывает кодовую комбинацию записи кратчайшего пути и определяет, что минимальный путь для принятого пакета из сети LAN2 в LAN8 проходит через маршрутизаторы с номерами 001-011-110.

• 6.    Маршрутизатор CCG011 проверяет наличие связи с соседним маршрутизатором CCG110.

• 7.    При наличии связи маршрутизатор CCG011 посылает пакет в маршрутизатор CCG110.

• 8.    Маршрутизатор CCG110 получает пакет, деинкапсулирует его и посылает в сеть LAN8.

• 9.    Рабочая станция В получает кадр из сети.

• 10.    Если маршрутизатор CCG011 обнаружил, что линия связи с маршрутизатором CCG110 не может быть использована, например, по причине переполнения, он обращается к программе CCGR и определяет минимальный обходной путь 011-111-110, формирует кодовую комбинацию сокращенной записи обходного пути и записывает ее в дополнительное поле служебной части пакета данных.

• 11.    Маршрутизатор CCG011 проверяет наличие связи с соседним маршрутизатором CCG111.

• 12.    При наличии связи маршрутизатор CCG011 посылает пакет в маршрутизатор CCG111.

• 13.    Используя программу CCGR, маршрутизатор CCG111 считывает кодовую комбинацию обходного пути и определяет, что минимальный путь для принятого пакета в сеть LAN8 проходит через него по пути: 011-111-110.

• 14.    Маршрутизатор CCG111 проверяет наличие связи с соседним маршрутизатором CCG110.

• 15.    При наличии связи маршрутизатор CCG111 посылает пакет в маршрутизатор CCG110.

• 16.    Маршрутизатор CCG110 получает пакет, деинкапсулирует его и посылает в сеть LAN8.

• 17.    Рабочая станция В получает кадр из сети.

4.    Повышение производительности маршрутизатора

Таким образом, использование моделей ГКП при объединении сетей позволяет получить следующие преимущества. Во-первых, отпадает необходимость в использовании маршрутных таблиц для определения путей в сети. Это позволяет существенно упростить функции маршрутизаторов и удешевить их, а также увеличить скорость обработки пакетов данных и сократить время доставки пакетов адресату. Алгоритм ГКП-маршрутизации прост в реализации и может быть исполнен практически любым микропроцессором. Данное обстоятельство приближает сети с маршрутизаторами по техникоэкономическим показателям к сетям с коммутаторами, позволяя вместе с тем использовать основное их достоинство – возможность конструирования компактных в структурном отношении и надежных ячеистых топологий с альтернативными путями для рассылки пакетов данных.

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

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

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

Оценим, как изменится быстродействие маршрутизатора в результате принятия процедуры бестабличной маршрутизации на примере маршрутизатора Freeway компании National. Freeway относительно дешевый маршрутизатор, обеспечивающий скорость трансляции 12000 пакет/с ( Brian Edem et al ., 1992). Сравнительно небольшую скорость трансляции обеспечивает лишь один процессор, что в свою очередь и определяет небольшую стоимость Freeway.

Процессор

Память процессора

Ядро ЦП

* Б афер ^—^^

Буфер

Сетевое ядро

§ в

Мультиплексор адресов

Регистр адресов

I

Сетевая шина

Sonic 1

Sonic 2

Sonic 3

Sonic 4

ИС ВОИ ЛВС

Рис. 4. Архитектура аппаратных средств маршрутизатора Freeway

Ядро ЦП маршрутизатора Freeway составляет микроконтроллер NS32GX320 компании National и его подсистема памяти (рис. 4). Ядро работает с тактовой частотой до 25 МГц, что соответствует пиковому быстродействию 12 млн операция/с. Подсистема памяти ЦП представляет собой один банк из 32 ДЗУПВ емкостью 4 или 16 Мбайт в зависимости от того, используется ли 1- или 4-Мбайт модуль памяти. В памяти ЦП хранится код процессора, размещается стек и находятся статические переменные. Память работает в страничном режиме, размер страницы составляет 4 Кбайт.

Сетевое ядро маршрутизатора Freeway служит для организации фактического трафика данных. Оно состоит из подсистемы памяти (памяти пакетов), процессорного интерфейса (буфера данных), набора ИС ВОИ ЛВС компании National и четырех контроллеров сети Ethernet (Sonic) компании National. Доступ к сетевой шине со стороны главных абонентов шины осуществляется под управлением центрального арбитра сетевого ядра. Подсистема памяти сетевого ядра по размеру и принципу работы аналогична подсистеме памяти процессорного ядра.

Интерфейс, связывающий процессор NS32GX320 с сетевой шиной данных, позволяет процессору получать доступ как к сетевой памяти, так и к программируемым регистрам каждого из контроллеров Sonic. Эти контроллеры вместе с соответствующими пассивными компонентами представляют четыре интерфейса ЛВС Ethernet. Набор ИС ВОИ ЛВС вместе с парой оптических приемопередатчиков реализует двухканальную связь с кольцом ВОИ ЛВС (FDDI).

В схеме маршрутизатора предусматривается СППЗУ емкостью до 1 Мбайт для хранения кода процессора. Эта емкость достаточна для реализации небольших прикладных задач или для обеспечения инициализации сети. Порт управления/состояния позволяет воспроизводить информацию состояния на ЖК-дисплее. Этот порт соединяется также с 1-Кбит ЭСППЗУ, которое используется для хранения физических сетевых адресов каждого сетевого интерфейса и другой информации, которая служит для управления конфигурацией и инициализацией маршрутизатора.

Маршрутизатор Freeway реализует широко распространенные протоколы TCP (протокол управления передачей) и IP (протокол межсетевого обмена) в качестве своих функций уровня 4 и уровня 3 соответственно. Программные средства TCP/IP обрабатывают поступающие кадры и транслируют их в направлении к получателю. Эти программные средства получают необходимую информацию их таблиц маршрутизации, которые ведет отдельный программный модуль Routed. Модуль Routed формирует информацию о сетевых соединениях при помощи протокола информации о маршрутизации RIP. Модуль Routed, совместимый с небольшой резидентной программой операционной системы BSD 4.3 Unix, взаимодействует с другими главными машинами и маршрутизаторами, передавая им информацию о том, к каким сетям имеется доступ. Эта информация используется затем для обновления таблиц маршрутизации на уровне IP.

При обработке 1 пакета маршрутизатор Freeway выполняет около 600 команд. Следовательно, с учетом быстродействия ЦП NS32GX320 на обработку 1 пакета уходит приблизительно (600/12 ⋅ 10⁶) = 50 мкс в пиковом режиме. Реально в среднем затрачивается приблизительно 70 мкс, т.е. в 1,4 раза больше. Такое время обработки обеспечивает максимальную скорость передачи пакетов (1/70 ⋅ 10^-6) = 14000 пакет/с. Гарантируемая скорость маршрутизатора Freeway в 1,2 раза ниже – приблизительно 12000 пакет/с.

Код BSD предусматривает ведение двух таблиц маршрутизации – для главных ЭВМ и для сетей. В коде BSD поиск маршрута осуществляется вначале по главной таблице, а затем по сетевой. Такой порядок обработки пакетов в первоначальном варианте Freeway не мог обеспечить требуемую скорость передачи, поэтому разработчики маршрутизатора Freeway изменили порядок обработки пакетов. Маршрутизатор имеет дело преимущественно с сетями, поэтому Freeway вначале обращается к сетевой таблице, а затем к главной. Такое изменение порядка определения маршрута и поиска по таблицам маршрутизации позволило сократить число команд при обработке 1 пакета на 300. Следовательно, отказ от просмотра маршрутных таблиц для одной сети сокращает поиск приблизительно на (300/3) = 100 команд.

Учитывая сказанное, полный отказ от использования маршрутных таблиц при реализации бестабличной маршрутизации в маршрутизаторе Freeway сократит обработку 1 пакета еще на 100 команд по сравнению с принятым порядком обработки. Тогда обработка одного пакета составит около (600100) = 500 команд. С учетом быстродействия ЦП на это в пиковом режиме работы будет затрачено (500/12 ⋅ 10⁶) = 41 мкс. В среднем получаем (41 ⋅ 1,4) = 57 мкс. Таким образом, среднее время обработки 1 пакета сокращается на (70-57) = 13 мкс. Такое время обработки 1 пакета может обеспечить скорость передачи пакетов (1/57 ⋅ 10^-6) = 17000 пакет/с. Или с учетом реального фактора в среднем получаем: (17 ⋅ 10³/1,2) = 14000 пакет/с. Таким образом, скорость обработки пакетов в маршрутизаторе возрастает на 18 %.

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

Номер версии (4бит)	Длина заголовка (4биг)		Т ип сервиса (8 бит]		Общая длина (16 бит)
Идентификатор (1 Ббит]		Флаги (Збит)		Смещение Фрагмента (1 Збит)
Время жизни (Вбит)		Протокол (Вбит)		Контрольная сумма заголовка (1 Вбит]
Адрес отправителя (Э2бит)
Адрес получателя (32бит)
Опции (поле переменной длины]				Выравнивание до 32-битной границы

Рис. 5. Формат заголовка дейтаграммы формата IP

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

T = (B + H) l/ c + T0 (l + 1), где H - длина служебной части пакета, c - скорость передачи пакетов данных по каналу связи, T0 - время обработки 1 пакета в узле.

Пусть решение о выборе оптимального пути принимает рабочая станция. Такая стратегия соответствует маршрутному способу адресования. При маршрутном адресовании рабочая станция определяет оптимальный путь и записывает его в поле "Опции" заголовка пакета. Обычно запись пути включает H = n ( l + 1) бит, где n бит составляет длина номера узла сети. В CCGnet (сети, построенной на основе ГКП) полный маршрут может быть записан с использованием сокращенной записи. При этом код пути состоит из H' = ( n + lr ) бит. Таким образом, при замене обычной сети на CCGnet разница в длине пакета составляет:

A H = H - H' = n ( l + 1) - ( n + lr ) = l ( n - r ).

Если время передачи 1 пакета в CCGnet обозначить T', тогда выигрыш во времени передачи 1 пакета составит:

A T = т - T = ( в + H)l / c + т 0 ( l + 1) - [( в + _Я) l / c + T 0 ( l + 1 )] = ( n - r ) l 2 / c + A T 0 ( l + 1).

Величина AT0 = T0 - T'0 зависит от объема маршрутных таблиц и способа их обработки. Объем маршрутных таблиц растет в квадратичной зависимости от числа узлов сети. Максимально возможная минимальная длина пути в ГКП(n, k, r) определяется, как l = [n/r], где [х ] - наименьшее целое, не меньшее х (Кузнецова, 1984б). Тогда выигрыш во времени передачи 1 пакета по максимальному минимальному пути составит:

A T = [( n - r )/ c ] [ n / r ]² + A T 0 ([ n / r ] + 1).

Таким образом, выигрыш во времени передачи 1 пакета определяется параметрами ГКП и зависит от длины маршрута передачи пакета.

Пусть в результате замены традиционной сети на CCGnet время обработки одного пакета сократилось на 13 мкс, как получено в расчете для маршрутизатора Freeway. Тогда зависимости выигрыша во времени доставки пакетов по путям различной длины в различных по числу узлов ГКП при номинальной скорости протокола Ethernet 10 Мбит/с изображены на рис. 6.

Расчеты показывают, что наиболее предпочтительными для использования ГКП с точки зрения выигрыша во времени передачи пакетов данных являются крупные сети, причем, чем дальше передается пакет, тем выигрыш больше.

Накладные расходы по обработке и передаче пакетов в сети определяются соотношением:

P = H + cT o .

Определим выигрыш в накладных расходах, который может быть получен в результате замены обычной сети на CCGnet. Накладные расходы по обработке и передаче пакетов в CCGnet определяются соотношением:

P' = H' + cT'_o .

Тогда выигрыш в накладных расходах определяются соотношением:

A P = ( H + cT ) - ( H' - cT'_o ) = A H + c A T₀ = l ( n - r ) + c A T₀ .

Выигрыш в накладных расходах при передаче 1 пакета по максимальному минимальному пути определяются соотношением:

A P = [ nIr ] ( n - r ) + c A T₀ .

Пусть среднее время обработки 1 пакета в маршрутизаторе сократилось, как и ранее, на 13 мкс.

Рис. 7. Зависимость выигрыша в накладных расходах от размеров ЛВС

Тогда при номинальной скорости протокола Ethernet 10 Мбит/с получим следующие зависимости выигрыша в накладных расходах по обработке и передаче пакетов от размеров сети при передаче пакетов по путям различной длины (рис. 7). Расчеты показывают, что выигрыш тем больше, чем крупнее сеть и чем длиннее маршрут.

Рассчитаем, как изменится полезная пропускная способность сети в результате ее замены на CCGnet. Под полезной пропускной способностью сети понимается скорость передачи пользовательских данных, которые переносятся полем данных кадра. По стандарту все устройства сети должны быть готовы принимать дейтаграммы длиной 576 байт. Эти ограничения необходимы для передачи дейтаграмм в физических кадрах. При инкапсуляции дейтаграмма становится частью области данных кадра (рис. 8).

	Заголовок IP-дейтаграммы | Область данных IP-дейтаграммы
Заголовок кадра	Область данных кадра	Контрольная сумма

Рис. 8. Инкапсуляция дейтаграммы в кадр

Параметры протокола Ethernet подобраны таким образом, чтобы при нормальной работе узлов сети коллизии всегда четко распознавались. В стандарте Ethernet принято, что минимальная длина поля данных составляет 46 байт (рис. 9). Вместе со служебными полями это дает минимальную длину кадра 64 байт, а вместе с преамбулой – 72 байт или 576 бит.

57,5 мкс 9.6 мкс                                                67,1 мкс

<--------------х-->                <------------------>

| 8 байт |14 байт|46 байт| 4 байт || Кадр минимальной длины ||                                 |

Рис. 9. К расчету полезной пропускной способности ЛВС

Для скорости передачи данных 10 Мбит/с величина битового интервала равна 0,1 мкс или 100 нс. Поэтому для передачи кадра минимальной длины затрачивается 57,5 мкс. Прибавив межкадровый интервал 9,6 мкс, необходимый для приведения адаптеров в исходное состояние, а также для предотвращения монопольного захвата среды одной станцией, получаем, что период следования кадров минимальной длины составляет 67,1 мкс. Отсюда максимально возможная пропускная способность сегмента Ethernet составляет (1/67,1 ⋅ 10^-6) = 14880 кадр/с. Для кадров Ethernet минимальной длины полезная пропускная способность равна:

С П = 14880 ⋅ 46 ⋅ 8 = 5,48 Мбит/с.

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

Кадры максимальной длины технологии Ethernet имеют поле данных 1500 байт, что вместе со служебной информацией составляет 1518 байт, а с преамбулой – 1526 байт или 12208 бит. Максимально возможная пропускная способность сегмента Ethernet для кадров максимальной длины составляет 813 кадр/с. Очевидно, при работе в большими кадрами нагрузка на узлы сети существенно снижается. Для кадров Ethernet максимальной длины полезная пропускная способность равна:

С П = 813 ⋅ 1500 ⋅ 8 = 9,76 Мбит/с.

Эта величина близка к номинальной скорости протокола. Такие скорости могут быть достигнуты только в том случае, когда двум взаимодействующим узлам в сети Ethernet другие узлы не мешают, что бывает крайне редко.

При использовании кадров среднего размера с полем данных 512 байт пропускная способность сети составляет 9,29 Мбит/с, что тоже достаточно близко к предельной пропускной способности.

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

При замене обычной сети на CCGnet длина пакета, как показано выше, сократится на

∆ H = [ n / r ] ( n – r ) бит.

Для максимальной минимально возможной длины пути это составит:

∆ H = l ( n – r ).

Таким образом, полезная пропускная для кадров Ethernet минимальной длины в 46 байт при пропускной способности сегментов 14880 кадр/с увеличится в соответствии с соотношением:

∆Cпmax = 14880 ⋅ ∆H = 14880 ⋅ l(n – r), для кадров Ethernet максимальной длины в 1500 байт при пропускной способности сегментов 813 кадр/с полезная пропускная увеличится в соответствии с соотношением:

∆Cпmin = 813 ⋅ ∆H = 813 ⋅ l(n – r), для кадров Ethernet средней длины в 512 байт при пропускной способности сегментов 2268 кадр/с полезная пропускная увеличится в соответствии с соотношением:

∆ C пmid = 2268 ⋅ ∆ H = 2268 ⋅ l ( n – r ).

Для максимальной минимально возможной длины пути соответственно получаем:

∆ C пmax = 14880 ⋅ ∆ H = 14880 [ n / r ] ( n – r ),

∆ C_пmin = 813 ⋅ ∆ H = 813 [ n / r ] ( n – r ),

∆ C пmid = 2268 ⋅ ∆ H = 2268 [ n / r ] ( n – r ).

Зависимости роста полезной пропускной способности сети для различных сетей CCGnet при передаче пакетов данных по путям различной длины показаны на рис. 10.

пропускной способности от размеров ЛВС

Рис. 11. Зависимость роста полезной пропускной способности от размеров кадров

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

Полезная пропускная способность сети зависит от величины кадров (рис. 11).

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

6. Заключение

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