автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Метод и алгоритм быстрой коммутации каналов устройств асинхронной передачи данных

РГ6 од

На правах рукописи

~ /

а:.:- ¿Л

Десятое Владимир Борисович

Метод и алгоритм быстрой коммутации каналов устройств асинхронной передачи данных.

Специальность: 05.13.16- Применение вычислительной техники, математического моделирования и математических методов в научных

исследованиях.

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических наук

Тверь 1999

Работа выполнена на кафедре Информационных технологий Тверского Государственного университета

Научный руководитель:

Доктор технических наук, профессор JL М. Местецкий . Официальные оппоненты:

Доктор технических наук, профессор H.A. Семенов, Кандидат физико-математических наук, доцент С;И. Гуров.

Ведущая организация: Вычислительный центр РАН

Защита диссертации состоится ^ £ ¿Г-/ Ж С С С-з в 14:00 на заседании диссертационного совета Д.063.97.01 при ТвГУ по адресу: 170013, Тверь, ул. Желябова 33

С диссертацией можно ознакомиться в научной библиотеке Тверского государственного университета.

Автореферат разослан ¿.^fä

Ученый секретарь диссертационного

совета Д.063.97.01 кандидат физ.-мат. наук, доцент

,345. m-oisß

/

т В.А. Хижняк

Общая характеристика работы

ктуальность темы и цель работы

В настоящее время число объединенных в локальные вычислительные ти (Local Area Network - LAN) компьютеров неуклонно растет. Для многих >ганизаций становится характерным наличие нескольких LAN. Все более юущной задачей становится объединение отдельных LAN в одну систему >мена информацией.

Традиционные сетевые адаптеры позволяют объединять в сеть >мпьютеры, удаленные максимум на несколько километров (1-2 км). Для ¡ъединения LAN, отстоящих друг от друга на большем расстоянии применяют □личные глобальные сети (Wide Area Network - WAN). Одной из важных юблем в объединении LAN является разница между скоростями LAN и WAN >ед. В подавляющем большинстве скорости LAN на 1-3 порядка больше :оростей WAN. Большие задержки передачи данных в WAN не позволяют )фективно использовать многие сетевые приложения. Постоянное увеличение эщности компьютерных систем, появление новых клиент-серверных и /льтнмедийных приложений, работающих в сети, требуют увеличения оростей WAN.

Предпринимаются попытки радикального решения этой проблемы путем йработки новых технологий WAN, скорости сред передачи которых >евосходят даже скорости LAN сред. Однако стоимость этих технологий WAN 1ень велика, что обусловлено высокой стоимостью как самого оборудования, к и каналов. Вместе с тем, существующее оборудование и каналы данных юдолжают широко использоваться для сетевых взаимодействий. Поэтому сьма актуальной задачей является разработка новых эффективных и недорогих ;годов объединения LAN на основе существующего оборудования и каналов. В [стоящее время наиболее используемой средой для объединения LAN, веющей приемлемую стоимость, остается телефонная сеть.

Целью диссертационной работы является повышение эффективности ¡ъединения LAN посредством каналов телефонной сети.

ручная новизна

Одним из наиболее значимых факторов, определяющих время передачи нных в сети, является количество каналов, которые должен пройти пакет, )ежде чем он достигнет компьютерной системы адресата. Традиционный >дход к сокращению времени передачи, основан на оптимизации маршрутов !кетов в сети, имеющей сложную топологическую структуру. Этот подход не трагивает главной причины задержек пакетов - использование принципа 'ммутации пакетов, состоящего в применении статических каналов и передачи ресованных пакетов по ним для соединения компьютерных систем в сети, что t позволяет решить проблему в корне.

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

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

В данной работе предлагается создать и исследовать новый метод построения объединительной сети LAN, основанный на идее быстрой коммутации каналов.

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

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

Необходимость в научном исследовании возникает при решении следующих задач:

• определение критерия эффективности метода быстрой коммутации;

• определение принципов коммутации;

• определение структуры и компонент коммутатора;

• построение алгоритма коммутации.

Основным инструментом для решения этих задач является построение натурной и имитационной математической моделей коммутационной сети и проведение экспериментов с разработанными моделями.

На защиту выносятся :

• обоснование нового подхода к повышению эффективности сети, основанного на применении метода быстрой коммутации каналов устройств асинхронной передачи данных;

• разработка и обоснование метода быстрой коммутации каналов устройств асинхронной передачи данных, определяющего физический

уровень и подуровень доступа к среде канального уровня семиуровневой модели взаимодействия открытых систем (Open System Interconnect -OSI);

• выявление и исследование эффекта блокирования в сетях быстрой коммутации каналов и создание алгоритма, исключающего эффект блокирования;

• разработка натурной и имитационной моделей сети с быстрой коммутацией каналов.

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

[остоверность результатов диссертационной работы обосновывается:

• полнотой анализа существующей технологии объединения LAN;

• принципиальной работоспособностью натурного макета;

• полнотой и корректностью исходных данных для имитационного моделирования, полученных с помощью натурного макета;

• полнотой учета основных факторов и объектов коммутационной сети в имитационной модели;

• согласованностью результатов моделирования с результатами экспериментов, полученных на натурном макете;

• реализацией метода при построении реальной одноранговой коммутационной сети и полученными оценками эффективности в ней.

недрение результатов работы.

езультаты диссертационной работы были использованы в изделии Альфа-HUB НПП Альфа-Телекс (Тверь). В настоящее время это изделие находится в списке редлагаемых изделий НПП Альфа-Телекс. Методика обоснования проектных ешений в области сетевого оборудования на основе имитационного оделирования также внедрена в НПП Альфа-Телекс.

пробация работы.

основные положения и результаты диссертации неоднократно докладывались и осуждались на кафедре информационных технологий Тверского кударственного университета в 1996-1999 г., на кафедре Автоматизации роцессов в химических производствах Тверского технического университета в ?99г., на Научной конференции, посвященной 25-летию ТвГУ в 1996г., на гминарах, проводимых в НПП Альфа-Телекс.

убликации.

о материалам диссертационной работы опубликованы четыре печатные 1боты[1-4].

Структура и объем работы.

Диссертационная работа состоит из введения, 4-х глав с выводами, заключения, списка литературы. Основная часть работы изложена на 138 страницах машинного текста. Работа содержит 50 рисунков и 20 таблиц.

Основное содержание работы

ПЕРВАЯ ГЛАВА-Состояние вопроса и постановка задачи исследования.

Критерий эффективности коммутационной сети определяется при сравнении двух типов сетей (Рис.1) как достижение следующих соотношений:

Т/св<Тр* (1.1)

где,

Т[с5 - среднее время передачи пакета в коммутационной сети; Трэ - среднее время передачи пакета в сети с коммутацией пакетов;

С/« < Сра (1.2)

где,

С/« - стоимость оборудования коммутационной сети; С/к - стоимость оборудования сети с коммутацией пакетов.

Рис.1 Примеры сетей

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

Tps — Texchg ' Nhops (1-3)

-де,

Tps - среднее время передачи пакета в сети с коммутацией пакетов;

Texchg - время передачи пакета по одному каналу;

Nhops - среднее количество каналов, которое проходит пакет.

Tfcs = Texchg + Tsw (1.4)

•де,

Tfcs - среднее время передачи пакета в коммутационной сети;

Texchg - время передачи пакета по одному каналу;

Tsw - среднее время коммутации каналов в коммутационной сети.

Зтсюда условие (1.1) можно записать в виде

Texchg + Tsw < Texchg • Nhops 0-5)

Nhops определяется интенсивностями потоков между станциями сети и •опологией сети, но всегда Nhops > 1. Для определения степени приближения :оммутационной сети к идеальному случаю, т.е. когда Nhops ~ 1, используем ледующее выражение

Теле

(,Switch Efficiency)SE =- (l .6)

Texchg + Tsw

SE показывает долю затрат на коммутацию в общем времени задержки [ередачи пакета. Чем ближе SE к единице, тем меньшая доля Tsw в Tfcs и оответственно тем выше эффективность коммутации. В дальнейшем SE □меряется в процентах. SE всегда будет меньше 100% из-за временных затрат ia коммутацию, но если доля Tsw в Tfcs будет небольшая, оно может быть ¡лизко к 100%.

Texchg не зависит от коммутации и в общем случае определяется как Texchg = W-L (1.7)

де,

V - время передачи одного байта (секунды); L - средний размер пакета (байт).

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

Средний размер пакетов Z, передаваемых в сети, определяется типами

работающих приложений. Поэтому необходимо измерять SE на диапазоне Z. Например, для выбора диапазона изменения L возьмем диапазон длины пакета в самом распостраненном типе LAN - Ethernet (64 < L < 1500 ).

Tsw определяется как общее время коммутации канала. Tsw зависит как от времени выполнения алгоритма коммутации канала, так и от времени ожидания станцией занятого канала, которое определяется конкуренцией станций за общий канал.

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

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

Стоимость оборудования любой сети прямо пропорциональна количеству используемых в ней каналов. Количество каналов в коммутационной сети на один канал больше, чем в традиционной сети с коммутацией пакетов с минимальным количеством каналов (сети с самыми длинными путями движения пакетов - минимальной сети). Тогда стоимость оборудования коммутационной сети C/cs за вычетом стоимости коммутатора Csw сравнима со стоимостью минимальной сети с коммутацией пакетов Cps. Если Csw« C/cs,

то Cps w Cfcs. Поскольку на каждом канале коммутационной сети устанавливается по два физических модема, их количество по сравнению с другими типами оборудования в сети максимальное. Тогда условие

Csw « Cfcs , а следовательно и выражение (1.2) можно представить как

Csw < Cdce (1.8)

где,

Cdce - стоимость физического модема.

Задержки пакетов, связанные с конкуренцией, определяются не только самим фактом разделения общего канала, но и тем каким образом это разделение происходит. Поясним это на следующем примере. Допустим, что две станции передают многопакетные сообщения в третью станцию коммутационной сети, конкурируя между собой за доступ к общему каналу (Рис. 2). Если процесс коммутации конкурирующих станций с последующей передачей пакетов происходит случайным образом (без какой-либо диспетчеризации), то может возникнуть ситуация когда одна станция будет более часто занимать общий канал к третьей станции, чем это будет делать другая. Это может привести к более длительным задержкам передачи пакетов одной станции по отношению к другой. Чтобы избежать этого, необходимо ввести некоторый механизм,

определяющий некоторый справедливый порядок* разделения общих ресурсов. Этот механизм называется алгоритмом совместного использования среды. Как правило в качестве меры справедливости н алгоритмах совместного использования среды в сетях используется равноправное деление общего ресурса.

Очередь Очередь

пакетов на передачу в Z. ) пакетов на передачу в

станцию2 .Т . станцию 2

П...ПГП . _ i ¡; ...

^ Коммутатор Рис.2 Конкуренция станций 1 и 3 за общий канала к станции 2

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

Tsw<Tnr.ix (i.У)

Tie,

Тmax - некоторое заранее определенное максимальное время ожидания

;танции.

Цля задания величины Ушах используем следующий подход. Любая станция в ;ети должна иметь гарантированную возможность образовать соединение и ;оответственно передать пакет хотя бы после образования соединения и госледующей передачи пакета всеми остальными станциями сети. Тогда

Т max = (lTexchg + Tp/i) ■ (/V - 1) (1.10)

'Де,

Texchg - время передачи пакета .максимальной длины, Tph - время установления физического соединения, N - количество станции г. коммутационной сети.

Таким образом выражения (1.6, 1.8, 1.9, 1.10) определяют следующую »птимизационную задачу проектирования коммутаппопиои сети:

SE* = max [SE(Xl}X2,X3)\ Tsw < Tmax ,Csw < Cmax]

Где,

ХьХ2,Хз — управляемые факторы: Xi~ множество принципов управления коммутатором; Хг - множество вариантов построения схемотехники коммутатора; Хз - множество алгоритмов коммутации.

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

SE > SEmin, Tsw < Tmax, Csw < Cmax . Если множесто таких решений не

пусто, то проводится оптимизация SE —» max.

Для определения Стах и Т max используем выражения (1.8) и (1.9,1.10)

соответственно, а в качестве SEmin возьмем 50%, что соответствует эффективности продвижения пакета в традиционной сети с коммутацией пакетов при минимальной длине косвенного маршрута, т.е. длине маршрута равной 2-м каналам (Nhops — 2).

ВТОРАЯ ГЛАВА - Построение и исследование натурной модели.

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

В основу построения макета'.были заложены принципы телефонной коммутации:

жесткая коммутация каналов; отсутствие линий управления;

наличие функций поднятия трубки, набора, вызова, занятости;

В качестве станций коммутационной сети и устройств асинхронной передачи данных в натурной модели используются два персональных компьютера IBM PC и их асинхронные порты. Асинхронные порты посредством физических линий соединяются с коммутатором. При этом применяются только линии передачи и приема данных асинхронного порта.

( Начало"^)

——И

Прослушать CurrStat

Ci.rrStat - номер канала текущей, нвОлгодаемой коммутатором станцией

DestCurrStat - номер канала станции с которой требует соединение станция нз канплз CurrStat

Принять , DestCurrSai |

Да

! Соединить i CurrStat с

! DeslCurrStat

Перейти к следующему »а налу_

Конец )

Рис.З Алгоритм коммутации

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

Основная функция коммутатора - соединение линий данных TxD и RxD мутируемых асинхронных портов. По аналогии с телефонном коммутацией управление коммутатором происходит со стороны асинхронных портов по же линиям, по которым передаются данные TxD и RxD. Коммутатор рерывно сканирует мгновенное состояние линии TxD подключенных портов, еляя сигналы управления и общем потоке данных. Для того чтобы мутатор смог

;лшъ сигналы управления от сигналов передаваемых данных, выдача алов управления осуществляется с большими длительностями, чем тельности сигналов передачи данных.

Начальный алгоритм коммутации был построен методом аналогии -1изации основных этапов алгоритма телефонной коммутации (поднятие Зки, гудок, набор номера, соединение) в среде устройств асинхронной гдачи данных. По аналогии с телефонной коммутацией, коммутация каналов горитме происходит по первому требованию (Рис 3).

Исследование натурной модели заключалось в проверке зтоспособности и оценке коэффициента SE ■ Оценка SE в среднем по «рам пакетов ¿составила 70':;., т.е. в среднем ,S'/: > SE min. Однако для 1еров пакетов L < 100 ммеег место SE < SE n .,i.

Дальнейшие исследования коммутационной сети должны решить (ующие задачи:

оценка функционирования коммутационной сети в полномасштабной конфигурации;

снижения времени коммутации 7ли> с целью повышения БЕ; построение алгоритма совместного использования среды;

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

По классификации систем коммутационная сеть представляет собой вариант системы массового обслуживания (СМО). По классификации СМО, коммутационную сеть можно охарактеризовать как замкнутую систему от состояния которой зависит не только поток заявок, но и поток обслуживания. Заявкой является пакет, который какая-либо станция коммутационной сети пытается передать другой станции. Обслуживание каждой заявки состоит из дву> фаз: обслуживание коммутатором, обслуживание станцией назначения. Иг первой фазе обслуживания мы имеем СМО с очередью и ограниченным временем ожидания заявки в очереди. На второй фазе обслуживания представлена И-канальная СМО с отказами и специализированными заявками для каждого канала.

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

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

Для исследования сложных систем данного типа наиболее эффективным является метод имитационного моделирования.

ТРЕТЬЯ ГЛАВА-Построение и исследование имитационной модели.

Модель коммутационной сети представляет собой систему с дискретным! событиями. Состояние системы Б в текущий момент времени определяется

8 = <К,С >

где,

К= {(М,8)1,(М,8)2 ... (М,8)п) - список пар соединений,

М - номер канала станции, которая вызвала соединение,

S - номер канала вызванной на соединение станции,

П - количество установленных соединений;

С = {(M,S)l,(M,S)2 ... (M,S)m}~ список, ожидающих соединения

ЦИЙ,

М - номер канала станции, которая запрашивает соединение,

S - номер канала вызываемой на соединение станции,

m - количество ожидающих соединения станций;

Состояние системы S изменяется под действием событий Z(coeflniieHHe, ;динение,поступление заявки на соединение)

Shob = F(STeK,Z),

События Z связаны друг с другом причинно-следственными связями, упление заявки в конечном счете вызывает событие соединение, которое в ' очередь вызывает событие разъединение. Промежутки времени между и событиями являются случайными величинами.

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

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

Для построения адекватной имитационной модели, которая отражает ауру коммутационной сети, а также процессы, происходящие в ней, тьзовалась концепция, ориентированная на представление сети в виде шельно исполняемых и взаимодействующих между собой объектов-ессов. На основе этой концепции, в рамках диссертационной работы была йотана система имитационного моделирования^]. Главными онентами системы являются модули, реализующие квазипараллельное чнение программных элементов и класс SIMULATE, соответствующий нменному классу языка Симулы-67 и включающий в себя основные итивы для построения имитационных моделей. С помощью этой системы построена модель коммутационной сети.

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

модели были детализированы до передачи отдельных бит. Реализация реальны) алгоритмов работы программ и введение реальных задержек в модель полученных с натурного макета позволили повысить точность модели до 3°Л Оценка точности модели проводилась по мере построения и добавления новы: объектов в модель. Окончательная оценка точности модели была проведена п< показателю БЕ.

Для анализа работы сети использовалось визуальное представление работы сети, показывающее как работу сети в целом, так и одновременнун работу алгоритмов коммутации в станциях и в коммутаторе.

Т) ® (2) (3)

-1) 0 (1) (4) а) ^ б)

(2>\<3) (з) ®

Станции 2 блокирована

Рис. 4 Пример блокирования

Потенциально блокированная станция

Идеальная /схема 1

Идеальная :ема 2 1

Одновременные соединения

Рис.5 Объединение идеальных схем

Исследования коммутационной среды были разделены на два этапа исследование работы сети в полномасштабной конфигурации и повышение коэффициента эффективности коммутации.

При исследовании работы сети в полномасштабной конфигурации был( выявлено что в сети быстрой коммутации, образующей соединения по первом; требованию, возможны ситуации естественного блокирования станций. На (Ри< 4) представлен пример такого блокирования. Станции 1,2,3,4 передают длинны! (многопакетные) сообщения по такой схеме : станция 1 передает в станцию 2 станция 2 в 3, станция 3 в 4. Допустим первым произошло соединение (1,2) (Ри> 4а). Спустя некоторое время установилось соединение (3,4) (Рис 46). Затея произошло разъединение (1,2) (Рис 4в). Ст. 2 не может соединиться со ст. 3 потому что ст.З занята в соединении (3,4) (Рис 4в). Поскольку ст.1 имее следующий пакет для передачи в ст.2, соединение (1,2) вновь образуется. Спуст

;оторое время соединение (3,4) разрывается и ст.З становится свободной, нако ст.2 уже не может образовать соединение со ст.З из-за своей занятости в динении (1,2) (Рис 4г). Поскольку ст. 4 имеет следующий пакет для ст.З динение (3,4) образуется снова (Рис 46) и ситуация с соединением (2,3) (торяется вновь. Предположив, что все станции передают многопакетные Мщения, ст.2 будет долгое время блокирована, т.е. не имеет возможности [тельное время передать пакет, что приведет ее к ошибкам истечения ■дельного времени ожидания передачи пакета.

МахЭЫ - номер канала станции с МАХ(Тжш)

ОеБШахЭЫ • номер канала станции с которой требует соединение станция на канале МахБЫ

СигтЭИ - номер канала текущей, наблюдаемой коммутатором станции

ОеБГСиггБИ - номер канала станции с которой требует соединение станция на канапе СиггЗЫ

Соединить

СиггёЫс

ОезЮиггЭШ

Блок в алгоритме

Преобразуется в блок-схему

Рис.6 Дополнения в алгоритм коммутации

При исследовании этого явления была определена основная причина жирования, которой является возможность асинхронного образования ювременных соединений в объединенных идеальных схемах взаимодействий с 5). Идеальная схема взаимодействий - схема с возможностью никновения только одного соединения в любой момент времени.

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

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

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

соединения Тми. Станция с наибольшей величиной 1\vait считаете; блокированной. Ей создается режим наибольшего предпочтения: всем станциям запрещено соединяться с ней и со станцией, с которой она требует соединения Все остальные станции обслуживаются по-прежнему алгоритму "первого требования".

0 10 20 30 100

64 35 58 60 63 63

128 54 66 66 75 75

256 74 79 85 86 86

512 ВЗ 91 92 92 92

1024 93 94 96 96 96

2048 95 97 98 98 98

Трои - период просмотра неактивных каналов (миллисек) L - размер пакета (байт)

Таб.1 Зависимость SE от периода просмотра неактивных каналов

На (Рис 6) в соответствие с вышеизложенным показаны дополнения, которые необходимо внести в алгоритм, изображенный на (Рис 3).

Построенный алгоритм не только избавляет станции от блокирования, но и обеспечивает выполнение условий (1.9,1.10). Простота алгоритма позволилг реализовать его с минимальными вычислительными затратами, что не повлияло на коэффициент эффективности коммутации SE .

При проведении второго этапа исследования коммутационной сети с целью повышения коэффициента эффективности коммутации SE былс выявлено, что около 80% величиы Tsw составляет время, затраченное нг определение сигнала запроса от станций. Это время нельзя снизить вследствие его прямой зависимости от характеристики времени передачи байта. Однако этс время можно сократить за счет уменьшения частоты наблюдения за каналами, сс стороны которых длительное время не было запросов на соединение Эксперименты, проведенные с простым однопороговым алгоритмом определение неактивности канала, позволили получить существенное повышение коэффициента SE для размеров пакетов £>100 эффективности коммутацш (Таб 1). Таким образом SE > SE min при всех L.

ЧЕТВЕРТАЯ ГЛАВА- Пример реализации метода быстрой коммутации.

На основе разработанного метода и алгоритма быстрой коммутацш каналов устройств асинхронной передачи данных в НПО "Альфа-телекс" г.Твер! было разработано изделие Альфа-HUB, используемое для построения ccti компьютеров с сервисом прозрачного разделения файлового пространства не уровне функций операционной системы (ОС) между всеми станциями сети. Эт; задача возникла из потребности охвата больших, чем охватывает локальная сет!

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

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

• уровень, отвечающий за преобразование и обработку запросов -верхний уровень;

• уровень, отвечающий за доставку запросов - нижний уровень.

Функция верхнего уровня состоит в разборке длинных запросов на

еты для передачи их нижнему уровню, а также в сборке запросов из пакетов, щимаемых с нижнего уровня.

Функция нижнего уровня заключается в доставке пакета определенной нции в коммутационной сети.

При построении нижнего уровня сети использовался разработанный в сертационной работе метод и алгоритм быстрой коммутации каналов. Для троения коммутатора использовались следующие компоненты: сропроцессор Intel 8051 с частотой 10МГц, постоянное запоминающее ройство емкостью 2кБ, оперативная память емкостью 2кБ, коммутационная рица на 16 каналов. Такие же компоненты использовались при изготовлении урного макета коммутатора.

Размер пакета, байт SE при чтения SEpsaoa

255 81 83

Таб. 2 Измерение коэффицента ЭЕ в реальной сети.

Измеренные показатели коэффициента эффективности ££(при ТроИ = [с) построенной сети для операций чтения-записи участков файла приведены Ъб 2).

Как видно из (Таб 1,2) характеристики показателей близки к ультатам экспериментов на имитационной модели.

С учетом стоимости компонент и работ по изготовлению коммутатора в овиях мелкосерийного производства его стоимость составляет $30 Ш. 1Имость асинхронного физического модема М115 (фирма ге1ах г. Зеленоград) 0 иБ. Расчет выполнен в 1998г.

Отсюда следует, что построенная сеть полностью удовлетворяет терию эффективности коммутационной сети.

Основные результаты диссертационной работы

1. Метод быстрой коммутации каналов устройств асинхронной передачи данных, полученный в результате проведенных исследований, позволяет эффективно решить задачу объединения LAN в области действия асинхронных физических модемов. Это решение основано на построении некоторой коммутационной сети, которая является объединяющей средой LAN.

Метод определяет физическую структуру и алгоритм метода доступа сети - физический уровень и подуровень доступа к среде (Media Access Control -MAC) канального уровня сети соответственно.

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

Элементы метода могу г быть реализованы в составе моста, маршрутизатора или межсетевого интерфейса.

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

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

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

Публикации по теме диссертации

1. Десятов В.Б. , Местецкий Л.М. Имитационное моделирование дискретной коммутации устройств асинхронной передачи данных. Ученые записки :ТГУ, Тверь 1996.

2. Десятое В.Б.Местецкий Л.М. Имитационное моделирование в среде BORLAND PASCAL. Программные и технические средства медико-биологических технических систем. Сборник научных трудов. ТГТУ Тверь 1998г.

3. Десятое В.Б. Метод дискретной коммутации устройств асинхронной передачи данных. "Программные средства и системы". Научно-практическое издание. N2,1999.

4. Десятое В.Б. Техническое описание Альфа-HUB. Конструкторская документация фирмы Альфа-Телекс г.Тверь 1997г.

Список сокращений.

Введение.

Глава 1. Состояние вопроса и постановка задачи исследований.

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

1.2 Способы объединения сетей.

1.3 Проблема повышения пропускной способности в объединенных сетях.

1.4 Метод быстрой коммутации каналов асинхронных портов.

1.4.1 Сущность метода.

1.4.2 Критерий эффективности метода.

1.4.3 Постановка задачи исследования.

1.4.4 Стратегия решения задачи.

1.5 Выводы.

Глава 2. Построение и исследование натурной модели.

2.1 Построение натурной модели коммутационной сети.

2.1.1 Определение компонент натурной модели.

2.1.2 Устройства асинхронной передачи данных.

2.1.3 Физические линии и модемы.

2.1.4 Коммутатор.

2.1.4.1 Коммутационная матрица.

2.1.4.2 Структурная схема коммутатора.

2.1.5 Алгоритм коммутации.

2.2 Проведение экспериментов на натурной модели.

2.2.1 Цели проведения экспериментов.

2.2.2 Условия проведения экспериментов.

2.2.3 Результаты проведения экспериментов.

2.3 Обоснование построения имитационной модели для проведения дальнейших исследований.

2.4 Выводы.

Глава 3. Построение и исследование имитационной модели коммутационной сети.

3.1 Выбор языка моделирования.

3.2 Построение и оценка адекватности имитационной модели.

3.3 Проведение имитационных экспериментов и анализ результатов

3.3.1 Планирование экспериментов.

3.3.2 Оптимизация показателя эффективности коммутации.

3.3.3 Оптимизация показателя баланса.

3.4 Выводы.

Глава 4. Пример реализации метода быстрой коммутации.

4.1 Постановка задачи.

4.2 Функциональная схема сети.

4.3 Построение верхнего уровня.

4.4 Построение нижнего уровня.

4.5 Оценка эффективности сети.

4.6 Выводы.

В настоящее время число объединенных в локальные вычислительные сети (LAN - Local Area Network) компьютеров неуклонно растет[39,42]. Для многих фирм становится характерным наличие нескольких LAN. Все более насущной задачей становится объединение отдельных LAN в одну систему обмена информацией[39,42].

Традиционные сетевые адаптеры позволяют объединять в сеть компьютеры, удаленные максимум на несколько километров (1-2 км) [4,29,34,39] Для объединения LAN, отстоящих друг от друга на большем расстоянии применяют различные глобальные сети (WAN -Wide Area Network)[39].

Одной из важных проблем в объединении LAN является разница между скоростями LAN и WAN сред[39,42,43]. В $ подавляющем большинстве скорости LAN на 1-3 порядка больше скоростей WAN[42]. Большие задержки в WAN не позволяют эффективно использовать многие сетевые приложения[39,43,45]. Постоянное увеличение мощности компьютерных систем, появление новых клиент-серверных и мультимедийных приложений, работающих в сети, все больше повышают актуальность проблемы увеличения пропускной способности WAN[42].

Технические предпосылки решения этой проблемы существуют[ 10,17,22,24,28,42]. В настоящее время существует много различных технологий WAN скорости сред передачи которых превосходят даже скорости LAN сред[39]. Однако стоимость этих технологий WAN очень велика, что обусловлено как стоимостью самого оборудования так и стоимостью каналов[ 17,39,42]. Кроме того существуют старые оборудование и каналы данных, которые до сих пор используются[17,39].

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

В настоящее время в связи с большой распостраненностью телефонных каналов, отсутствием других каналов, либо их высокой стоимости, телефонная сеть является одной из самых используемых сред применяемых для объединения LAN[ 17,43].

Целью диссертационной работы является повышение эффективности объединения LAN посредством выделенных каналов телефонной сети.

Для этого в работе предлагается создать и исследовать новый метод построения объединительной сети, основанный на идее быстрой коммутации каналов.

Суть метода состоит в быстрой коммутации каналов устройств асинхронной передачи данных на короткое время, необходимое для передачи одного пакета LAN.

Предлагаемый метод позволяет увеличить скорость передачи пакетов за счет сокращения общего количества переходов, которые проходит пакет от одной LAN до другой.

В качестве устройств асинхронной передачи данных, выполняющих роль оконечного оборудования данных, в методе используются стандартные асинхронные порты. В качестве аппаратуры передачи данных применяются асинхронные физические модемы. Широкое распостранение и низкая стоимость этих устройств[17] вместе с минимально требуемым количеством выделенных телефонных линий, необходимых для построения объединительной сети, повышают актуальность и эффективность этого метода.

Эффективность метода в общем случае определяется показателями времени коммутации и стоимостью коммутатора.

Телефонные коммутаторы образуют большие задержки соединения и поэтому не подходят для быстрой коммутации каналов[4,5,26]. Для реализации метода необходимо построить другой, быстрый коммутатор каналов.

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

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

Построение метода осуществляется натурно-имитационным методом, т.е. с применением натурного и имитационного моделирования.

В качестве натурной модели в данной работе были реализованы физическая среда - коммутатор и алгоритм коммутации. Натурная модель позволила:

• определить физические компоненты и принципы построения коммутатора;

• построить алгоритм коммутации;

• получить грубую оценку показателя эффективности коммутации.

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

• исследовать работу сети в полномасштабной конфигурации при различных схемах взаимодействия;

• наблюдать и анализировать внутреннюю работу коммутатора;

• определить и оптимизировать факторы, влияющие на показатель времени коммутации;

• выявить необходимость алгоритма совместного использования среды;

• построить алгоритм совместного использования среды.

Новыми научными результатами диссертационной работы являются:

1. Обоснование нового способа повышения эффективности сетей передачи данных.

2. Создание метода быстрой коммутации каналов устройств асинхронной передачи данных.

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

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

Практическая значимость работы заключается в том, что созданный метод позволяет повысить эффективность объединения

LAN на основе телефонной сети в области действия асинхронных физических модемов.

Достоверность результатов диссертационной работы обосновывается:

• полнотой анализа существующей технологии объединения LAN;

• принципиальной работоспособностью натурного макета;

• полнотой и корректностью исходных данных для имитационного моделирования, полученных с помощью натурного макета;

• полнотой учета основных факторов и объектов коммутационной сети в имитационной модели;

• согласованностью результатов моделирования с результатами экспериментов, полученных на натурном макете.

С помощью разработанного метода быстрой коммутации устройств асинхронной передачи данных было произведено проектирование одноранговой коммутационной сети на основе операционной системы MS-DOS.

По материалам диссертации опубликованы три печатные работы[12,13,14].

Работа состоит из введения, четырех глав и заключения.

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

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

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

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

В заключении изложены достигнутые результаты и описаны общие варианты применения метода.

4.5 Выводы.

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

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

ЗАКЛЮЧЕНИЕ

Метод быстрой коммутации каналов устройств асинхронной передачи данных, полученный в результате проведенных исследований, позволяет эффективно решить задачу объединения LAN в области действия асинхронных физических модемов(до 40км). Это решение основано на построении некоторой коммутационной сети, которая является объединяющей средой LAN.

Метод определяет полностью физический уровень и подуровень доступа к среде канального уровня.

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

Коммутационная сеть, построенная на основе полученного метода, предоставляет услуги второго уровня модели OSI. Низкий уровень стека сетевых протоколов обеспечивает самый минимальный объем служебной информации в пакетах, переносимых LAN трафик вдоль коммутационной сети. Коммутационная сеть не налагает ограничений на уровень к которому относится переносимый пакет и его размер. В сети могут туннелироваться как пакеты канального уровня, так и сообщения прикладного уровня. Для сокращения времени реакции в интерактивных приложениях и снижения задержек

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

Метод может быть реализован в составе моста, маршрутизатора или межсетевого интерфейса.

1. Андрианов А.Н.,Бычков С.П.,Хорошилов А.И. Программирование на языке Симула-67.-М.: Наука, 1985.-288с.

2. Бейкер Ф., Как работают маршрутизаторы. LAN, 1997,2.

3. Бертсекас Д.,Галлагер Р. Сети передачи данных: Пер. с англ.-М.: Мир, 1989

4. Блэк Ю. Сети ЭВМ. : Пер. с англ. : М. Мир, 1990.

5. Боккер П. Передача данных.: Пер. с нем.: -М. Связь

6. ВентцельЕ.С. Исследование операций. М.: Советское радио, 1972.

7. Вентцель Е.С. Исследование операций; задачи, принципы, методология. М.: Наука, 1988.

8. Вентцель Е.С., Овчаров JI.A. Теория вероятностей и ее инже нерные приложения. М.: Наука, 1988.

9. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания.-М: Наука, 1966.

10. Ю.Ганьжа Д., Маршрутизаторы в распределенных сетях. LAN, 1997,5.

11. Ганьжа Д., Коммутация KaHanoB.LAN, 1997,7.

12. Десятов В.Б. Метод дискретной коммутации устройств асинхронной передачи данных: "Программные продукты и системы" Международное научно-практическое издание. N2,1999.

13. Десятов В.Б., Местецкий J1.M. Имитационное моделирование дискретной коммутации устройств асинхронной передачи данных. Ученые записки :ТГУ , Тверь 1996.

14. И.Десятов В.Б., Местецкий Л.М Имитационное моделирование в среде Borland Pascal. Программные и технические средствамедико-биологических и технических систем : Сборник научных трудов ТГТУ 1999.

15. Дженнингс Ф. Практическая передача данных.: -М.Мир,1989.

16. Джордейн Р. Справочник функций ОС MS-DOS.: Пер. с англ. -М: Радио и связь., 1992.

17. Евдокименко Е., Обзор российского рынка модемов для физических линий. Сети, 1997,7.

18. Кристиан. К. Программирование на языке Модула-2. : Пер. сангл. Мир, 1990.

19. Киндлер Е. Языки моделирования.: Пер. с чеш.-М.:Энергоатомиздат,1985

20. Клейнрок JI. Вычислительные системы с очередями.-М.:Мир. 197921 .Клейнен Дж. Статистические методы в имитационном моделировании, тт. 1,2. : Пер. с англ. -М: Статистика, 1978.

21. Коммутатор или маршрутизатор. PC Magazine, 1997,18.

22. Крейнес А., ARIS-технология коммутации третьего уровня. Сети, 1998,3.

23. Кульгин М., Коммутация как маршрутизация. LAN, 1997,8.

24. Нанс Б. Программирование в локальных сетях. : Пер. с англ. ТОО ИБС, 1992.

25. Мартин Дж. Вычислительные сети и распределенная обработка данных. : Пер. с англ. : М. Финансы и статистика, 1986.

26. Модем для физических линий М-115. фирма Zelax, Россия.

27. Подольный Е.,Модемы для корпоративных магистралей и узлов. Сети, 1998,1.

28. Протоколы информационно-вычислительных сетей. Справочник под ред. Мизина И.А., 1990.

29. Райе JI. Эксперименты с локальными сетями микроЭВМ: Пер. с англ.-М.: Мир, 1990.

30. Саати T.JI. Элементы теории массового обслуживания.: Пер. с англ. М.: Советское радио,1971.

31. Шеннон Р. Имитационное моделирование систем искусство и наука.: Пер. с англ. - М.: Мир, 1978.

32. Шрайбер Т.Дж. Моделирование на GPSS.: Пер. с англ.-М.: Машиностроение, 1980.

33. Щербо В.К. и др. Стандарты по локальным сетям.: М. Радио и связь, 1990.

34. Хаммел Р.Л. Последовательная передача данных. : Пер. с англ. -М. Мир, 1996.

35. Характеристики модемов для физических линий, фирма Zelax, Россия.

36. Флинт Д. Локальные сети ЭВМ: архитектура, принципы построения, реализация.-М: Финансы и статистика. 1986.-359с.,ил.

37. Ямпольский В.З.,Комагоров В.П.,Солдатов В.Н. Моделирование сетей передачи и обработки информации.-Новосибирск.: Наука, 1986.-136с.

38. Internetworking Design Guide. CISCO Syst,1998.

39. Layer 3 Switching. 3Com Technical Papers, 1998.

40. Product Catalog. RAD DATA Communications Ltd., 1998.

41. Internetworking Techology Overview. CISCO Syst., 1997.

42. Celia Joe, Dual Analog Technology. 3Com Techical Papers., 1997.

43. D. Comer, Internetworking with TCP/IP. Prentice Hall, 1993

44. Boundary Routing System Architecture. 3Com Technical Papers., 1996.