12 марта 2016г.
Появление и развитие локальных вычислительных сетей (ЛВС) является логической закономерностью эволюции компьютерных технологий. Наблюдается стирание границ между вычислительной и коммутационной техникой, конвергенция технологий. Общими становятся проблемы и опыт разработок, накопленные в этих областях. Использование ЛВС дает ряд преимуществ, в том числе возможность совместно использовать некоторые данные и устройства, что, как следствие, сокращает расходы на оборудование. Сотрудники получают оперативный доступ к обширной корпоративной информации. Использование ЛВС позволяет снизить потребность компаний в других формах передачи информации (телефон, почта), передавать по сети голосовую и видеоинформацию, организовывать аудио- и видеоконференции.
В то же время практическое использование ЛВС связано с рядом трудностей. Объединение в одну сеть нескольких сетей, расположенных зачастую территориально далеко друг от друга, приводит к возрастанию стоимости создания и сложности обслуживания сети, усложняется разработка сетевых приложений. Возникает необходимость обеспечивать совместимость программного обеспечения и требуемый уровень безопасности данных, передаваемых по сети.
Локальные вычислительные сети строят на базе простейших топологий типа «шина», «кольцо», «звезда», базовые функции в которых реализуются на основе алгоритма управления типа «остовное дерево». В результате ЛВС имеют низкую структурную надежность и живучесть. Отсутствие резервных путей передачи данных приводит к тому, что при отказе одного из узлов сети велика вероятность возникновения так называемой «катастрофы на сети», когда даже при наличии исправных компонентов сеть не может выполнять свои функции. Расширение сети имеет существенные ограничения. Бесконечное увеличение числа узлов и длины каналов связи приводит, вопреки ожиданиям, к снижению пропускной способности сети. Изначально все элементы ЛВС разрабатываются в расчете на малочувствительный к задержкам трафик (передача файлов, электронная почта), в то время как в сетях передается информация, обладающая чувствительностью к задержкам (голос, видео, изображения, мультимедийный трафик). При передаче такого трафика часть передаваемых данных может теряться, что приводит к обесцениванию всех остальных успешно переданных данных. При разговоре возникают неожиданные паузы, теряется синхронизация между голосом и изображением в видео.
В глобальных сетях, как правило, используются ячеистые топологии, допускающие наличие альтернативных путей передачи. Благодаря прямым пересылкам данных от узла к узлу в таких сетях передачи ведутся одновременно всеми узлами, параллельно и независимо друг от друга. Однако если узлы соединяются произвольно, то требуются достаточно сложные процедуры управления транспортными потоками.
Упростить процедуры управления в сети можно, если использовать регулярные ячеистые топологии (решетки, гиперкубы, снежинки и другие), в них выполняются формализованные соотношения между управлением потоками и топологией сети. Подобные топологии используются в вычислительных системах (ВС) для соединения микропроцессоров. Они, как правило, отличаются однородностью структур. Недостаток таких топологий заключается в том, что нарушение однородности может привести к невозможности пересылок между модулями ВС.
При использовании регулярных топологий появляется возможность кодирования узлов и использовать кодированные номера для пересылок. Такая маршрутизация в работе [4] названа бестабличной (кодовой) маршрутизацией. В этом случае управление потоками не требует привлечения средств сетевого и транспортного уровней и может выполняться принципиально на канальном уровне.
В качестве математической модели для построения топологий ЛВС предлагается использовать графы кодовых пересечений (ГКП). В области ГКП используются следующие понятия [3]. Две кодовые комбинации a и a’ длиной n и основанием k пересекаются по n – r элементам, если n – r последних элементов одной кодовой комбинации совпадают с n – r первыми элементами другой кодовой комбинации (0 < i < n). Каждой кодовой комбинации ε1, ε2, …, εn соответствует номер N = Sn =1 εikn-i, 0 ≤ N ≤ kn-1. Кодовые комбинации длиной n и основанием k образуют множество A. Отображение Γ множества A в себя ставит в соответствие каждой кодовой комбинации aÎA те кодовые комбинации из A, у которых первые n – r элементов совпадают с последними n – r элементами кодовой комбинации a, где r – мощность пересечения. Кодовые комбинации, поставленные в соответствие a, образуют множество Γa, которое называется прямым. Отображение Γ-1a называется обратным, если оно определяет такое соответствие кодовых комбинаций, при котором каждой кодовой комбинации aÎA ставятся в соответствие те кодовые комбинации из A, у которых последние n – r элементов совпадают с первыми n – r элементами кодовой комбинации a. Множество A и отображение Γ множества A в себя задают псевдограф (A, Γ) кодовых пересечений с параметрами n, k, r – ПКП(n, k, r). Если из множества дуг ПКП(n, k, r) убрать все петли, а оставшееся множество дуг обозначить через V, то получится граф кодовых пересечений с параметрами n, k, r – ГКП (n, k, r). Граф кодовых пересечений, построенный в соответствии с прямым или обратным отображением, является ориентированным, а ГКП, при построении которого использованы оба типа отображений – неориентированным (Рисунок 1.1).
Главной особенностью ГКП является зависимость их структур от параметров n, k и r. Это позволяет на базе формализованного представления упростить решение многих задач, связанных с разработкой и эксплуатацией ЛВС. В частности, кратчайший с точки зрения числа переприемов путь в ГКП определяется с помощью простых арифметических операций над кодовыми номерами его вершин [1].
Для примера определим кратчайший путь из вершины 000 в вершину 010 в ориентированном ГКП, представленном на Рисунке.1.1. Определяем число символов в пересечении двух соседних кодовых комбинаций: n – r = 3 – 1 = 2. Если существует непосредственный путь (путь длиной l = 1) из вершины 000 в вершину 010, то два последних символа кодовой последовательности 000 должны совпадать с двумя первыми символами кодовой последовательности 010. Это условие не выполняется, следовательно, такого пути не существует. Далее выясняем, существует ли путь из узла 000 в узел 010, длина которого была бы равна 2. Для этого один последний символ кодовой комбинации 000 должен совпадать с одним первым символом кодовой комбинации 010. Условие выполняется, следовательно, из узла 000 в узел 010 существует путь длиной l = 2. Для его определения составляем из номеров 000 и 010 последовательность 00010, совместив при этом совпадающие символы. Полученная последовательность является сокращенной записью кода полного пути ранга l = 2 из узла 000 в узел 10. Читаем эту последовательность слева направо по n = 3 с шагом r = 1 символ и получаем кодовую запись пути: 000 – 001 – 010 рангом l = 2. Повторяя описанную выше процедуру, можно определить кодовую запись пути, ранг которой будет равен 3, 4 и т. д.
Вопросам исследования возможности построения ЛВС на базе ГКП и применения в них бестабличных (кодовых) методов маршрутизации посвящен ряд работ [2, 3, 4]. К основным достоинствам структур на базе ГКП относятся гибкость, легкая масштабируемость, возможность простого подключения сетевых компонентов.
В настоящее время нерешенными остаются следующие вопросы:
1. Программная реализация протоколов управления сетью на базе ГКП.
2. Проверка корректности разработанных протоколов и процедур управления потоками.
3. Исследование эффективности функционирования сети, использующей разработанные протоколы управления.
Протоколы управления сетью на базе ГКП могут быть реализованы на двух нижних уровнях – физическом и канальном, а решение второй и третьей задач можно провести с использованием имитационной модели сети.
Имитационная модель должна обеспечивать сбор и обработку статистических данных в различных условиях функционирования сети: при низкой, средней, высокой загруженности, в условиях различной степени отказов компонентов сети. Также имитационная модель должна допускать изменение структуры сети варьированием основных структурных параметров ГКП.
Использование топологий типа ГКП для построения ЛВС позволит повысить их надежность и живучесть.
Список литературы
1. Амосов, А.А., Шарипова М.М. Метод определения путей в сетях связи / А.А. Амосов, М.М. Шарипова // Техника средств связи, сер. Техника проводной связи. – М: Министерство промышленности средств связи, 1977. – выпуск 8 (18). – С. 15-22.
2. Борисова, Л.Ф. Повышение эффективности функционирования локальных вычислительных сетей при использовании логических свойств их структур / Л.Ф. Борисова // Вестник МГТУ, т. 3. – 2000. – № 1, С. 45- 54.
3. Борисова, Л.Ф. Прикладные вопросы теории графов кодовых пересечений / Л.Ф. Борисова // Вестник МГТУ, т. 9. – 2006. – № 2. – С. 291-300.
4. Борисова, Л.Ф. Регулярные топологии в микропроцессорных системах и сетях ЭВМ / Л.Ф. Борисова // Вестник МГТУ, т. 5. – 2002. – № 2. – С. 223-232.
