Несимметричнаямногомаркерная кольцевая локальная сеть с буферами конечной емкости иординарной дисциплиной обслуживания
Содержание
Введение
1 Математические моделифункционирования несимметричных, многомаркерных КЛВС с конечными буферамиразличной емкости и ординарной дисциплиной обслуживания
1.1 Математическаямодель функционирования многомаркерной, несимметричной КЛВС с N АС, с k маркерами (1
буферами различнойемкости />
1.2 Математическая модельфункционирования многомаркерной, несимметричной КЛВС с буферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
1.3 Математическая модельфункционирования многомаркерной, несимметричной КЛВС с N АС, с k маркерами (k=N) и буферами
различной емкости />
2 Определениестационарных вероятностей состояний
несимметричных,многомаркерных КЛВС
2.1 Определениестационарных вероятностей состояний многомаркерной,
несимметричной КЛВС сбуферами различной емкости, с N АС и k
маркерами, с ординарнойдисциплиной обслуживания
2.2 Определениестационарных вероятностей состояний многомаркерной,
несимметричной КЛВС сбуферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
2.3 Определениестационарных вероятностей состояний многомаркерной,
несимметричной КЛВС сбуферами различной емкости, с N АС и
k=N маркерами, с ординарнойдисциплиной обслуживания
3 Характеристикифункционирования несимметричных, многомаркерных КЛВС
3.1 Характеристикифункционирования многомаркерной, несимметричной КЛВС с буферами различнойемкости, с NАС и kмаркерами (1
3.2 Характеристикифункционирования состояний многомаркерной, несимметричной КЛВС с буферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
3.3 Характеристикифункционирования состояний многомаркерной, несимметричной КЛВС с буферамиразличной емкости, с N АС и k=N маркерами, с ординарной дисциплиной обслуживания
Заключение
Cписок используемыхисточников
Введение
Одним из важнейших направлений развития вычислительнойтехники является разработка методов и средств распределенной обработкиинформации. Термин распределенная обработка информацииозначает применение множества связанных друг с другом компьютеров с целью скоординированноговыполнения одной или нескольких задач. Таким образом, распределенная обработкаинформации предполагает наличие двух и более компьютеров и средств коммуникациимежду ними. В настоящее время она осуществляется, как правило, посредством вычислительныхсетей, или сетей компьютеров.
Средиразличных классов вычислительных сетей особый интерес для автоматизациипроизводства, а также и ряда других областей, например автоматизации в областиобразования, научных исследований и разработок, учрежденческой деятельности,представляют локальные вычислительные сети.
Локальнойвычислительной сетью называется совокупность взаимосвязанных и распределенных посравнительно небольшой территории вычислительных ресурсов (микро- и мини – ЭВМ,терминалов и т.д.), взаимодействие которых обеспечивается специальной системойпередачи данных. Такая сеть обычно предназначается для сбора, передачи,рассредоточенной и распределенной обработки информации в пределах одногопредприятия, организации и т.д.
К основнымхарактеристикам ЛВС относятся следующие:
·территориальная протяженность сети (длина общего канала);
·максимальная скорость передачи данных;
·максимальное число узлов в сети (оно может быть от нескольких десятков донескольких сотен);
·максимально возможное расстояние между узлами сети;
·физическая структура или топология сети;
·физическая среда передачи и данных;
·метод доступа абонентов в сеть;
·условия надежной работы сети и др.
Абонентскиеустройства сети (узлы, станции), к которым относятся ЭВМ и различноетерриториальное оборудование (дисплеи, внешние запоминающие устройства,печатающие устройства и др.), связаны между собой передающей средой, называемойканалом, моноканалом или магистралью, с помощью сетевых адаптеров, состоящих изприемопередатчиков и контролеров адаптера. Контролеры адаптера, называемыетакже блоками доступа, выполняют следующие основные функции: прием данных изканала и выдачу их в канал. Приемопередатчики осуществляют согласованиеэлектрических сигналов канала и абонентских станций.
Под физическойструктурой или топологией ЛВС понимают структурусоединения узлов сети используемой средой передачи (линиями связи). В ЛВС могутбыть реализованы различные виды топологии: шинная, кольцевая, звездообразная,древовидная (рис. 1). Однако наиболее распространенными являются два первыхтипа структур, отличающихся простотой методов управления, возможностьюрасширения и изменения конфигурации сети без заметного усложнения средствуправления сетью, высокой эффективностью />/>использования каналов связи.
/>/>/>/>/>/> />
/>/> /> /> /> /> /> />
Древовиднаяструктура
/>
/> /> /> /> /> /> /> /> /> /> />
/> /> /> /> /> /> /> /> /> />
/> />
Кольцевая структура/> /> /> /> /> /> /> /> /> />
/>/>
/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
Звездообразнаяструктура
/>
/>/> /> /> /> /> /> /> /> /> />
/> />
Шинная структура
Другой важнойхарактеристикой ЛВС является физическая среда передачи,представляющая собой одну или несколько линий связи, по которым осуществляетсяинформационный обмен между узлами (станциями) ЛВС. Выбор физической средыпередачи зависит от пропускной способности ЛВС, или, другимисловами, от максимальной скорости информационного обмена, которая может бытьдостигнута в ЛВС.
Под методомдоступа к физической среде передачи понимают совокупность правил(алгоритмов), диктующих порядок посылки и приема пакетов, или кадров,данных узлами сети. Следует отметить, что о методе доступа имеет смысл говоритьлишь в том случае, когда узлы сети используют общую для них физическую средупередачи. При этом необходимо, чтобы в каждый момент времени эта средаобслуживала передачу не более одного узла. Чаще всего вопрос о методе доступарассматривается применительно к ЛВС с шинной или кольцевой топологией.
Различают дваосновных класса методов доступа – детерминированные и случайные. Случайныйметод доступа характеризуется тем, что любой узел может сделать попыткупередать информацию в сеть в произвольный момент времени, Однако в этом случаевозможно столкновение передач двух узлов и более. В случае столкновения узлы,начавшие передачу, должны прекратить ее и возобновить попытку передачи посленекоторой случайной задержки времени. Этот метод применяется лишь внезагруженных сетях, его основной недостаток – низкий коэффициент использованияобщего канала.
Детерминированныеметоды доступа позволяют полностью использовать каналы связи. Они обеспечиваютгарантию каждому абоненту определенного времени выхода в сеть. При этом могутустанавливаться приоритеты абонентам. Конфликтные ситуации, вызванные одновременнымобращением к каналу нескольких абонентов, отсутствуют. Все это достигается засчет невозможности доступа абонентов в сеть в любой момент времени. Издетерминированных методов доступа наибольшее распространение получил маркерныйметод.
При использованиимаркерного метода передачу производит только та абонентская станция, у которойв данный момент имеется маркер (эстафетная палочка). Остальные станции в этовремя осуществляют только прием. Последовательность передачи маркера от однойстанции к другой, т.е. последовательность подключения станций для передачиинформации, задается управляющей станцией сети. Абонентская станция, получившаямаркер (полномочия на передачу информации), передает свой подготовленный кадр вшину, если кадра для передачи нет, АС сразу посылает маркер другой станциисогласно установленному порядку передачи полномочий. Так продолжается до техпор, пока управляющая станция не инициирует новую последовательность передачмаркера. ЛВС с циркулирующим маркером позволяет передавать сообщенияпроизвольной длины.
В 1980 г.в рамках Института инженеров по электротехнике и радиоэлектронике (IEEE) был образован комитет802 по стандартизации ЛВС, задачей которого являлось определение наборапроцедур, посредством которых различные устройства могут взаимодействовать. Дляподготовки проектов отдельных стандартов были учреждены подкомитеты. Стандартоммаркерного кольца занимался подкомитет 802.5. Разработка этого стандарта былазавершена в 1984 г., а в 1985 г. Американский национальный институтстандартов (ANSI) утвердил стандарт ANSI/IEEE 802.5 в качестве национального стандарта США. В1986 г. этот стандарт был утвержден в качестве международного. В Европе в1982 г. Европейская ассоциация производителей ЭВМ (ECMA) независимо от ANSI выпустила стандартмаркерного кольца ECMA-89. Стандарт ANSI/IEEE 802.5 совместим со стандартом ECMA-89.
КЛВС смаркерным доступом относится к протоколам детерминированного множественногодоступа циклического типа. ЛВС «маркерное кольцо» представляет собойсовокупность станций, соединенных последовательно двухточечными линиями. Каждаястанция действует как активный повторитель, регенерирует сигналы, поступающиеиз входящей линии, и выдает их в исходящую линию. Станции имеют право напередачу кадра при получении специального кадра-маркера, циркулирующего покольцу в промежуток между передачей информации, станция, имеющая кадр дляпередачи, удерживает поступивший маркер, преобразует его в кадр (для передачи,удерживает поступивший маркер), добавлением адресной информации, данных идругих необходимых полей и выдает в исходящую линию. Каждая станция анализируетадресную информацию кадра и при несовпадении адреса назначения и собственногоадреса копирует кадр в исходящую линию. Станция, обнаружившая адресованный ейкадр, копирует его в приемный буфер, устанавливает в нем признак того, чтопакет принят, обнаружив вернувшийся кадр, анализирует признак приема пакета и вслучае, если пакет принят, удаляет его из кольца и из своей очереди пакетов напередачу. Если пакет не принят, станция удаляет его из кольца и оставляет всвоей очереди для передачи при получении маркера. Одна из станций кольцавыполняет функции активного монитора, обеспечивая нормальное функционированиесети. Другие станции выполняют функции неактивного монитора, и в случае егоотказа готовы перейти в состояние активного монитора. Кроме того, станцииопределяют ошибки функционирования сети и информируют о них все остальныестанции для восстановления нормального функционирования.
ПреимуществаКЛВС с маркерным доступом:
·гарантируется доступ каждого абонента в сеть через определенные промежуткивремени независимо от нагрузки сети;
·отсутствие проблемы маршрутизации сообщений, т. к. маршруты передачисообщений фиксированы;
·возможность расширения;
·низкая стоимость подключения новых узлов в сеть;
·невысокая стоимость сетевых интерфейсов, реализующих прямые методы передач иуправления доступа в сеть;
НедостаткиКЛВС:
·сложное управление;
·при добавлении или замене узла необходимы остановка в работе сети и временныйразрыв кольца;
·выход из строя узла сети прерывает работу всей сети.
Вматематических моделях, описывающих функционирование ЛВС, принимаютсяпредложения о числе станций в сети (конечное или бесконечное), наличии(размере) буферов у станции, содержащих ожидающие передачу сообщения,предложения о входящем потоке сообщения, времени перехода маркера междустанциями и некоторые другие.
Математическимимоделями описанной ЛВС «маркерное кольцо» являются циклические СМО. Теорияциклических СМО получила развитие в работах иностранных ученых, обзор которыхнасчитывает более 200 наименований.
Под циклическойпонимается СМО с N очередями и одним прибором, обслуживающим очереди в циклическомпорядке. Емкость накопителей (буферов) может быть конечной или бесконечной. Вциклических СМО существует несколько дисциплин обслуживания, регламентирующихпребывание прибора у каждой очереди. Наиболее распространенными являютсяследующие:
1) исчерпывающиеили с опустошением, когда прибор отключается от очереди в момент, когда в нейнет сообщений;
2) вентильное,когда прибор отключается от очереди, обслужив все сообщения, находящиеся в нейк моменту подключения прибора к очереди;
3) сограничением k, когда прибор отключается от очереди, обслужив вней не более k сообщений (если в системе не осталось сообщений,то прибор отключается, обслужив менее k сообщений);
4) ординарное,когда прибор обслуживает по одному сообщению в каждой очереди;
5) Бернулли,когда прибор обслуживает одно сообщение в очереди (если оно там есть), а затемотключается с вероятностью p, и берет следующее с вероятностью 1-р (если сообщений всистеме нет, то прибор отключается с вероятностью 1);
6) ссокращением k, когда прибор отключается от очереди, обслужив r сообщений, где r=min(x,k), где x – это число сообщений в очереди в момент подключения к нейприбора.
Обслуживаниесообщения в КЛВС эквивалентно передаче пакета, время переналадки прибора сочереди на очередь – времени передачи маркера от одной станции к другой.Имитационное моделирование, учитывающее подробности функционирования КЛВС,показало адекватность этой математической модели.
Наиболеераспространенным подходом к анализу функционирования ЛВС является исследованиесредних значений таких вероятностно-временных характеристик как временазадержки сообщений (заявок), длины очередей, коэффициентов загрузки сообщений инекоторые другие.
1 Математическиемодели функционирования несимметричных, многомаркерных КЛВС с конечнымибуферамиразличной емкости и ординарной дисциплиной обслуживания
1.1 Математическаямодель функционирования многомаркерной, несимметричной КЛВС с NАС, с kмаркерами (1kN) и буферами различнойемкости />
Рассмотримнесимметричную КЛВС с протоколом маркерного доступа, которая состоит из N абонентских станций, на i-тую АС поступаетпростейший поток сообщений интенсивности />
На каждой АСимеется буфер с емкостью />,который служит для отправки сообщений по кольцу, а также есть приемный буфер,который позволяет принимать любое количество сообщений. АС пронумерованы такимобразом, что номер АС увеличивается по направлению движения свободных маркеров,причем после прохождения N-ой АС свободный маркер поступает на первую АС. Для передачисообщений используются k маркеров, 1
Буфер на i-той станции назовемполностью свободным, если на АС нет сообщений для передачи и полностью занятым,если на АС имеется />сообщений,подлежащих передаче.
Еслисвободный маркер поступает на свободную АС (не содержащую ни одного сообщения),то он немедленно отправляется на очередную АС. Если маркер поступает на АС, гдеимеется хотя бы одно сообщение, то немедленно начинается передача имеющихсясообщений в соответствии с дисциплиной обслуживания.
Дисциплинаобслуживания – ординарная, т.е. при поступлении маркера на АС обслуживается неболее одного сообщения, стоящего в очереди в момент прихода маркера.
Будемсчитать, что во время передачи сообщения все поступающие на эту АС сообщения,подлежащие передаче, теряются. Т.е. в этом случае на АС, с которой передаютсясообщения, происходит блокировка буфера, в котором находились сообщения вмомент прихода маркера. Время блокировки равно времени передачи сообщения,находившихся на АС-отправителе в момент прихода маркера.
Времяперехода свободного маркера между соседними АС будем считать одинаковым длявсех станций и равно d. Скорость движения сообщения по кольцу такая же,как и скорость движения свободного маркера. Время, необходимое для передачи иприема сообщения в кольце, обозначим через a.
Интервалвремени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя быодного сообщения для передачи на АС кольца, либо d, если ни на одной АС нетни одного сообщения для передачи.
После того,как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу наАС-отправитель этого сообщения. При получении квитанции о приеме АС-отправительосвобождается от переданного сообщения, отправляет маркер на очередную АС.
1.2 Математическаямодель функционирования многомаркерной, несимметричной КЛВС с буферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
Рассмотримнесимметричную КЛВС с протоколом маркерного доступа, которая состоит из 3абонентских станций, на i-тую АС поступает простейший поток сообщений интенсивности />
На первой АСимеется буфер емкостью />на второй АСбуфер емкостью />, на третьей АСбуфер />, которые служат дляотправки сообщений по кольцу, а также есть приемные буфера, которые позволяютпринимать любое количество сообщений. АС пронумерованы таким образом, что номерАС увеличивается по направлению движения свободных маркеров, причем послепрохождения третьей АС свободный маркер поступает на первую АС. Для передачисообщений используются 2 маркера.
Буфер на i-той станции назовемполностью свободным, если на АС нет сообщений для передачи и полностью занятым,если на АС имеется />сообщений,подлежащих передаче.
Еслисвободный маркер поступает на свободную АС (не содержащую ни одного сообщения),то он немедленно отправляется на очередную АС. Если маркер поступает на АС, гдеимеется хотя бы одно сообщение, то немедленно начинается передача имеющихсясообщений в соответствии с дисциплиной обслуживания.
Дисциплинаобслуживания – ординарная, т.е. при поступлении маркера на АС обслуживается неболее одного сообщения, стоящего в очереди в момент прихода маркера.
Будемсчитать, что во время передачи сообщения все поступающие на эту АС сообщения,подлежащие передаче, теряются. Т.е. в этом случае на АС, с которой передаютсясообщения, происходит блокировка буфера, в котором находились сообщения вмомент прихода маркера. Время блокировки равно времени передачи сообщения,находившихся на АС-отправителе в момент прихода маркера.
Времяперехода свободного маркера между соседними АС будем считать одинаковым длявсех станций и равно d. Скорость движения сообщения по кольцу такая же,как и скорость движения свободного маркера. Время, необходимое для передачи иприема сообщения в кольце, обозначим через a.
Интервалвремени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя быодного сообщения для передачи на АС кольца, либо d, если ни на одной АС нетни одного сообщения для передачи.
После того,как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу наАС-отправитель этого сообщения. При получении квитанции о приеме АС-отправительосвобождается от переданного сообщения, отправляет маркер на очередную АС.
1.3 Математическаямодель функционирования многомаркерной, несимметричной КЛВС с NАС, с kмаркерами (k=N) и буферами различнойемкости />
Рассмотримнесимметричную КЛВС с протоколом маркерного доступа, которая состоит из N абонентских станций, на i-тую АС поступаетпростейший поток сообщений интенсивности />
На каждой АСимеется буфер с емкостью />,который служит для отправки сообщений по кольцу, а также есть приемный буфер,который позволяет принимать любое количество сообщений. АС пронумерованы такимобразом, что номер АС увеличивается по направлению движения свободных маркеров,причем после прохождения N-ой АС свободный маркер поступает на первую АС. Для передачисообщений используются k маркеров, k=N.
Буфер на i-той станции назовемполностью свободным, если на АС нет сообщений для передачи и полностью занятым,если на АС имеется />сообщений,подлежащих передаче.
Еслисвободный маркер поступает на свободную АС (не содержащую ни одного сообщения),то он немедленно отправляется на очередную АС. Если маркер поступает на АС, гдеимеется хотя бы одно сообщение, то немедленно начинается передача имеющихсясообщений в соответствии с дисциплиной обслуживания.
Дисциплинаобслуживания – ординарная, т.е. при поступлении маркера на АС обслуживается неболее одного сообщения, стоящего в очереди в момент прихода маркера.
Будемсчитать, что во время передачи сообщения все поступающие на эту АС сообщения,подлежащие передаче, теряются. Т.е. в этом случае на АС, с которой передаютсясообщения, происходит блокировка буфера, в котором находились сообщения вмомент прихода маркера. Время блокировки равно времени передачи сообщения,находившихся на АС-отправителе в момент прихода маркера.
Времяперехода свободного маркера между соседними АС будем считать одинаковым для всехстанций и равно d. Скорость движения сообщения по кольцу такая же,как и скорость движения свободного маркера. Время, необходимое для передачи иприема сообщения в кольце, обозначим через a.
Интервалвремени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя быодного сообщения для передачи на АС кольца, либо d, если ни на одной АС нетни одного сообщения для передачи.
После того,как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу наАС-отправитель этого сообщения. При получении квитанции о приеме АС-отправительосвобождается от переданного сообщения, отправляет маркер на очередную АС.
Данная модельинтересна тем, что любая станция может передавать сообщение (если оно имеется).Это объясняется тем, что количество маркеров совпадает с количеством станций.Это модель имеет также особенности и в виде матрицы переходов из одногопериодического класса в другой.
2. Определениестационарных вероятностей состояний несимметричных, многомаркерных КЛВС
2.1 Определениестационарных вероятностей состояний многомаркерной, несимметричной КЛВС сбуферами различной емкости, с NАС и kмаркерами, с ординарнойдисциплиной обслуживания
Будемрассматривать поведение КЛВС в моменты поступления маркеров на АС. В этомслучае изменение состояний КЛВС образуют конечную цепь Маркова.
Под состояниемКЛВС будем понимать состояние всех АС кольца в момент поступления на нихмаркеров. Каждая АС может находиться всегда в одном из />/>состоянии.
Все состоянияКЛВС делятся на N периодических классов, каждый из которых содержит врассматриваемом случае />состояние.
Особенностипротокола приводят к тому, что указанная цепь Маркова является неприводимой,периодической с периодом, равным N.
Некоторый j-тый класс (j/>{1,2,…, N}) соответствуетпоступлению некоторого фиксированного маркера на j-тую АС. Вероятностипереходов из j-тогопериодического класса в (j+1) – ый образуют (/>/>/>)матрицу.
Закодируемсостояния КЛВС парами чисел (i, r), i=(/>), 0/>/>.Здесь i определяет класссостояний, т.е. равно номерам тех станций, на которых находятся маркеры, r определяет номерсостояния.
Введемобозначение M=(/>) – множество номеров техстанций, на которых находятся маркера, R=(/>), />, l/>{1,…, N}, /> — обозначает количествосообщений на l-тойАС. Также обозначим через P(/>) – вектор-строкувероятностей состояний КЛВС.
Обозначимчерез /> — вероятность того, что завремя /> на i-тую АС не поступит ниодного сообщения; /> — вероятностьтого, что за время />на i-тую АС поступит m сообщений; /> — вероятность того, что завремя /> на i-тую АС поступит m и более сообщений.
Так как потоксообщений пуассоновский, то имеем:
/>=/>
/>=/>
/>, i/>{1,2,…, N}
Изучаяповедение КЛВС во вложенные Марковские моменты, получим следующую процедуруопределения стационарных вероятностей сети.
Теорема.Стационарные вероятности рассматриваемой КЛВС вычисляются из соотношений:
P(/>)=P(/>) A(/>;/>)
/> (1)
где А -/> матрица вероятностейпереходов из i-тогопериодического класса в состояние (i+1) – го класса, элементы которойвычисляются по формуле:
a(/>)=/>/>+/>/>/>+/>, времена вычисляются последующим формулам:
/> />
/> />/>
а такжевероятность перехода равна нулю, если:
1) />>0 />, Q={1,2,3,…, N}
2) /> />
Доказательство:
P(/>) – вектор-строкавероятностей состояний i-того периодического класса; матрица А размерности />, элементами которойявляются вероятности переходов из i-того периодического класса в (i+1) – ый.
Вследствиепериодичности цепи Маркова /> если /> либо (i, j)/>(N, 1). Из этих рассужденийимеем Р(1)=Р(N)/>
Р(J)=P (J-1)/> J/>{2,3,…, N}, J определяет периодическийкласс.
J определяет те, станциина которых находятся маркеры в данном периодическом классе, с учетом постановкиматематической модели любой маркер может переходить только на соседнюю станцию.Это и обуславливает то, что маркер с N-ной станции переходит на первую АС.
Такимобразом, учитывая условие нормировки, имеем процедуру (1) определения векторовстационарных вероятностей КЛВС.
Доказано.
Дляобоснования правильности формул времени необходимо учитывать следующиеположения:
1) еслипоступает сообщение, а соответствующий буфер занят полностью, то сообщениетеряется, и при подсчете поступивших сообщений оно не учитывается;
2) еслисообщение не передается, то из данного буфера оно никуда не может исчезнуть,поэтому если при переходе из некоторого состояния в соседнее какое-то сообщениетеряется, то вероятность данного перехода равна 0;
3) припередаче сообщения из АС, на которой есть маркер, буфер данной станцииблокируется;
4) состанции с маркером может передаваться не более одного сообщения.
5) натех станциях, на которых нет маркеров, может быть вероятность равна единице втом случае, если в i-том периодическом классе и в (i+1) – вом буферстанции был полностью занят.
2.2/> Определениестационарных вероятностей состояний многомаркерной, несимметричной КЛВС сбуферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
Будемрассматривать поведение КЛВС в моменты поступления маркеров на АС. В этомслучае изменение состояний КЛВС образуют конечную цепь Маркова.
Подсостоянием КЛВС будем понимать состояние всех АС кольца в момент поступления наних маркеров. Каждая АС может находиться всегда в одном из />состоянии.
Все состоянияКЛВС делятся на 3 периодических классов, каждый из которых содержит врассматриваемом случае 12 состояний.
Особенностипротокола приводят к тому, что указанная цепь Маркова является неприводимой,периодической с периодом, равным 3.
Некоторый j-тый класс (j/>{1,2,3}) соответствуетпоступлению некоторого фиксированного маркера на j-тую АС. Вероятностипереходов из j-тогопериодического класса в (j+1) – ый образуют /> матрицу.
Закодируемсостояния КЛВС парами чисел (i, r), i=(/>), 0/>11. Здесь i определяет класссостояний, т.е. равно номерам тех станций, на которых находятся маркера, r определяет номерсостояния.
Введемобозначение M=(/>) – множество номеров техстанций, на которых находятся маркера, R=(/>), />, l/>{1,2,3}, /> — обозначает количествосообщений на l-тойАС. Также обозначим через P(/>) – вектор-строкувероятностей состояний КЛВС.
Обозначимчерез /> — вероятность того, что завремя /> на i-тую АС не поступит ниодного сообщения; /> — вероятностьтого, что за время />на i-тую АС поступит m сообщений; /> — вероятность того, что завремя /> на i-тую АС поступит m и более сообщений.
Так как потоксообщений пуассоновский, то имеем:
/>=/>
/>=/>
/>, i/>{1,2,3}
Изучаяповедение КЛВС во вложенные Марковские моменты, получим следующую процедуруопределения стационарных вероятностей сети, которая является частным случаемтеоремы из пункта 2.1: стационарные вероятности рассматриваемой КЛВСвычисляются из соотношений:
P (2,3)=P (1,2) A (1,2);
P (3,1)=P (2,3) A (2,3);
P (1,2)=P (3,1) A (3,1);
/>
А –/> матрица вероятностейпереходов из i-тогопериодического класса в состояние (i+1) – го класса, элементы которойвычисляются по формуле:
a(/>)=/>
/>/>
временавычисляются по следующим формулам:
/>/>
/>/>/>
а такжевероятность перехода равна нулю, если:
1) />>0 />, Q={1,2,3}
2) />
Дляобоснования правильности формул времени необходимо учитывать следующиеположения:
1) еслипоступает сообщение, а соответствующий буфер занят полностью, то сообщениетеряется, и при подсчете поступивших сообщений оно не учитывается;
2) еслисообщение не передается, то из данного буфера оно никуда не может исчезнуть,поэтому если при переходе из некоторого состояния в соседнее какое-то сообщениетеряется, то вероятность данного перехода равна 0;
3) припередаче сообщения из АС, на которой есть маркер, буфер данной станцииблокируется;
4) состанции с маркером может передаваться не более одного сообщения;
5) натех станциях, на которых нет маркеров, может быть вероятность равна единице втом случае, если в i-том периодическом классе и в (i+1) – вом буферстанции был полностью занят.
В приложениибудет предоставлены матрицы переходов для рассматриваемой КЛВС. Обозначение /> означает, что маркеры находилисьна первой и второй станциях.
2.3Определение стационарных вероятностей состояний многомаркерной, несимметричнойКЛВС с буферами различной емкости, с NАС и k=Nмаркерами, с ординарнойдисциплиной обслуживания
Будемрассматривать поведение КЛВС в моменты поступления маркеров на АС. В этомслучае изменение состояний КЛВС образуют конечную цепь Маркова.
Подсостоянием КЛВС будем понимать состояние всех АС кольца в момент поступления наних маркеров. Каждая АС может находиться всегда в одном из />/>состоянии.
Все состоянияКЛВС делятся на N периодических классов, каждый из которых содержит врассматриваемом случае />состояние.
Особенностипротокола приводят к тому, что указанная цепь Маркова является неприводимой,периодической с периодом, равным N.
Некоторый j-тый класс (j/>{1,2,…, N}) соответствуетпоступлению некоторого фиксированного маркера на j-тую АС. Вероятностипереходов из j-тогопериодического класса в (j+1) – ый образуют (/>/>/>)матрицу. Зафиксируем некоторый маркер и будем рассматривать поведение сети вмоменты поступления этого маркера АС.
Закодируемсостояния КЛВС парами чисел (i, r), i=(/>), 0/>/>.Здесь i определяет класссостояний, т.е. равно номеру станции, на которой находятся маркеры, r определяет номерсостояния.
Введемобозначение M=(/>) – множество номеров техстанций, на которых находятся маркера, R=(/>), />, l/>{1,…, N}, /> — обозначает количествосообщений на l-тойАС. Также обозначим через P(/>) – вектор-строкувероятностей состояний КЛВС.
Обозначимчерез /> — вероятность того, что завремя /> на i-тую АС не поступит ниодного сообщения; /> — вероятностьтого, что за время />на i-тую АС поступит m сообщений; /> — вероятность того, что завремя /> на i-тую АС поступит m и более сообщений.
Так как потоксообщений пуассоновский, то имеем:
/>=/>
/>=/>
/>, i/>{1,2,…, N}
Изучаяповедение КЛВС во вложенные Марковские моменты, получим следующую процедуруопределения стационарных вероятностей сети, которую можно записать в виде:
P(/>)=P(/>) A/>
/>
где А -/> матрица вероятностейпереходов из i-тогопериодического класса в состояние (i+1) – го класса, элементы которойвычисляются по формуле:
a(/>)=/>/>+/>/>/>+/>,
временавычисляются по следующим формулам:
/> />
/> />/>
а такжевероятность перехода равна нулю, если:
1) />>0 />, Q={1,2,3,…, N}
2) /> />
Дляобоснования правильности формул времени необходимо учитывать следующиеположения:
1) еслипоступает сообщение, а соответствующий буфер занят полностью, то сообщениетеряется, и при подсчете поступивших сообщений оно не учитывается;
2) еслисообщение не передается, то из данного буфера оно никуда не может исчезнуть,поэтому если при переходе из некоторого состояния в соседнее какое-то сообщениетеряется, то вероятность данного перехода равна 0;
3) припередаче сообщения из АС, на которой есть маркер, буфер данной станцииблокируется;
4) состанции с маркером может передаваться не более одного сообщения.
5) натех станциях на которых нет маркеров может быть вероятность равна единице в томслучае, если в i-том периодическом классе и в (i+1) – вом буферстанции был полностью занят.
3 Характеристикифункционирования несимметричных, многомаркерных КЛВС
3.1Характеристики функционирования многомаркерной, несимметричной КЛВС с буферамиразличной емкости, с NАС и kмаркерами (1Nk), с ординарнойдисциплиной обслуживания
Следующиехарактеристики определяют эффективность функционирования рассматриваемой КЛВС:
1) вероятность того, что всети нет сообщений (все АС свободны) />:
/>
Верностьданной формулы очевидна, т. к. чтобы в сети не было сообщений, необходимо,чтобы на любой станции не было ни одного сообщения в любом периодическомклассе, т.е. при любом расположении маркеров в КЛВС на станциях буфера должныбыть пусты.
2) вероятность того, что всеАС заняты (т.е. на каждой станции имеется хотя бы одно сообщение) />:
/>
Справедливостьданной формулы следует из того, что АС занята, когда на ней есть хотя бы односообщение, т.е. />. Сумма по i от 0 до N-1 означает, что мы любымфиксированным маркером прошли все кольцо и вернулись в начальное состояние.
3) вероятность того, что всеАС полностью заняты (т.е. на каждой АС все буфера полностью заняты) />:
/>
Справедливостьданной формулы следует из того, что АС полностью занята, когда на ней естьровно />сообщений. Сумма по i от 0 до N-1 означает, что мы любымфиксированным маркером прошли все кольцо и вернулись в начальное состояние.
4) среднее число занятыхстанций />:
/>
Выражение />означает, что мы суммируемте вероятности при которых на станциях буфер не пустой. Если же на станции нетсообщений для передачи, то индикатор равен 0 и вероятность обнуляется.
5) вероятность того, что l-тая АС занята />:
/>
Эта формуласправедлива для любой фиксированной АС.
6) коэффициент загрузки l-той АС />:
/>/>
Справедливостьданной формулы следует непосредственно из формулы (6) и того факта, чтозагрузка АС означает разницу между единицей и вероятностью того, что онасвободна.
7) среднее времяобслуживания сообщений на l-той АС />:
/>
Намнеобходимо для отыскания этой характеристики посмотреть время обслуживаниясообщений в каждом конкретном периодическом классе для заданной АС, очевидностьформулы вытекает из предыдущих рассуждений.
8) среднее времяобслуживания в сети />.
/>
Верностьследует из формулы (7).
3.2Характеристики функционирования состояний многомаркерной, несимметричной КЛВС сбуферами />, с 3 АС и 2-мя маркерами,с ординарной дисциплиной обслуживания
Следующиехарактеристики определяют эффективность функционирования рассматриваемой КЛВС:
1) вероятность того, что всети нет сообщений (все АС свободны) />:
/>
2) вероятность того, что всеАС заняты (т.е. на каждой станции имеется хотя бы одно сообщение) />:
/>
3) вероятность того, что всеАС полностью заняты (т.е. на каждой АС все буфера полностью заняты) />:
4)
/>
5) среднее число занятыхстанций />:
6)
/>
7) вероятность того, что l-тая АС занята />:
8)
/>
9) коэффициент загрузки l-той АС />:
10)
/>/>
11) среднеевремя обслуживания сообщений на l-той АС />:
12)
/>
8) среднеевремя обслуживания в сети />:
/>
Верностьданных формул была показана в пункте 3.1.
3.3Характеристики функционирования состояний многомаркерной, несимметричной КЛВС сбуферами различной емкости, с NАС и k=Nмаркерами, с ординарнойдисциплиной обслуживания
Следующиехарактеристики определяют эффективность функционирования рассматриваемой КЛВС:
1)вероятность того, что в сети нет сообщений (все АС свободны) />:
/>
2) вероятность того, что всеАС заняты (т.е. на каждой станции имеется хотя бы одно сообщение) />:
3)
/>
4) вероятность того, что всеАС полностью заняты (т.е. на каждой АС все буфера полностью заняты) />:
/>
5) среднеечисло занятых станций />:
/>
6) вероятностьтого, что l-таяАС занята />:
/>
7) коэффициентзагрузки l-тойАС />:
/>/>
Заключение
Кольцевыелокальные вычислительные сети с маркерным доступом широко используются нетолько в радиоэлектронной и аэрокосмичной промышленности, но также и всовременных системах связи. Многомаркерные КЛВС дают возможность передачиинформации сразу с нескольких станций одновременно. Кольцевые локальныевычислительные сети (КЛВС) с маркерным доступом являются одним из наиболеераспространенных и стандартизированных международными организациями.
МногомаркерныеКЛВС с одной линией связи, ординарной дисциплиной обслуживания и конечнымибуферами в постановке, приведенной в дипломной работе, в известной литературене встречались.
В дипломнойработе разработаны математические модели, описывающие функционированиенесимметричных КЛВС с несколькими маркерами, конечными буферами и ординарнымобслуживанием сообщений на АС; предложен аналитический аппарат, позволяющийопределить вероятности состояний КЛВС из векторно-матричных систем уравнений,выведены формулы для характеристик, описывающих особенности функционированиясетей.
Списокиспользуемых источников
1. Бакс В. Кольцевые локальные сети смаркерным доступом и их производительность // ТИИЭР. – т. 77, №2. –С. 121–142.
2. Бураковский В.В., Медведев Г.А. Кольцеваялокальная сеть с протоколом маркерного доступа // Техника средств связи.Сер. Системы связи. – 1990. – Вып. 7. – С. 9–16.
3. Бураковский В.В., Медведев Г.А. Характеристикилокальных вычислительных сетей с протоколами маркерного доступа //Материалы всесоюзной научно-технической конференции Микросистема-92: Тез.докладов. – Томск, 1992. – С. 44–46.
4. Гнеденко Б.В., Коваленко И.Н. Введениев теорию массового обслуживания. – М.: Наука, 1987. – 336 с.
5. Протоколы информационно-вычислительныхсетей: Справочник / Под ред. Мизина И.А., Кулешова А.П. – М.: Радио исвязь, 1990. – 504 с.
6. Пятибратов А.П., Беляев С.Н., Козырева Г.М.и др. Вычислительные машины, системы и сети: Учебник / Под ред. проф. А.П. Пятибратова. –М.: Финансы и статистика,1991. – 400 с.
7. Феллер В. Введение в теорию вероятностей иее приложения. – М.: Мир, 1984. – т. 1. – 527 с.