Канальный сообщение. Способы коммутации. Цифровая обработка сигналов

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

Физический уровень :

передача битов по физическим каналам ;

формирование электрических сигналов ;

кодирование информации;

синхронизация ;

модуляция .

Реализуется аппаратно.

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

Примером протокола физического уровня может служить спецификация 10Base-T технологии Ethernet, которая определяет в качестве используемого кабеля неэкранированную витую пару категории 3 с волновым сопротивлением 100 Ом, разъем RJ-45, максимальную длину физического сегмента 100 метров, манчестерский код для представления данных в кабеле, а также некоторые другие характеристики среды и электрических сигналов .

Канальный уровень

На физическом уровне просто пересылаются биты . При этом не учитывается, что в тех сетях, в которых линии связи используются (разделяются) попеременно несколькими парами взаимодействующих компьютеров, физическая среда передачи может быть занята. Поэтому одной из задач канального уровня (Data Link layer ) является проверка доступности среды передачи . Другая задача канального уровня - реализация механизмов обнаружения и коррекции ошибок . Для этого на канальном уровне биты группируются в наборы, называемые кадрами (frames ). Канальный уровень обеспечивает корректность передачи каждого кадра помещая специальную последовательность бит в начало и конец каждого кадра , для его выделения, а также вычисляет контрольную сумму , обрабатывая все байты кадра определенным способом, и добавляет контрольную сумму к кадру . Когда кадр приходит по сети, получатель снова вычисляет контрольную сумму полученных данных и сравнивает результат с контрольной суммой из кадра . Если они совпадают, кадр считается правильным и принимается. Если же контрольные суммы не совпадают, то фиксируется ошибка. Канальный уровень может не только обнаруживать ошибки, но и исправлять их за счет повторной передачи поврежденных кадров . Необходимо отметить, что функция исправления ошибок для канального уровня не является обязательной, поэтому в некоторых протоколах этого уровня она отсутствует, например в Ethernet и frame relay.

Функции канального уровня

Надежная доставка пакета :

Между двумя соседними станциями в сети с произвольной топологией.

Между любыми станциями в сети с типовой топологией:

проверка доступности разделяемой среды;

выделение кадров из потока данных, поступающих по сети; формирование кадров при отправке данных;

подсчет и проверка контрольной суммы .

Реализуются программно-аппаратно.

В протоколах канального уровня , используемых в локальных сетях, заложена определенная структура связей между компьютерами и способы их адресации . Хотя канальный уровень и обеспечивает доставку кадра между любыми двумя узлами локальной сети, он это делает только в сети с определенной топологией связей, именно той топологией, для которой он был разработан. К таким типовым топологиям, поддерживаемым протоколами канального уровня локальных сетей, относятся "общая шина", "кольцо" и "звезда", а также структуры, полученные из них с помощью мостов и коммутаторов . Примерами протоколов канального уровня являются протоколы Ethernet, Token Ring, FDDI, 100VG-AnyLAN.

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

В глобальных сетях, которые редко обладают регулярной топологией, канальный уровень часто обеспечивает обмен сообщениями только между двумя соседними компьютерами, соединенными индивидуальной линией связи. Примерами протоколов "точка-точка" (как часто называют такие протоколы) могут служить широко распространенные протоколы PPP и LAP-B. В таких случаях для доставки сообщений между конечными узлами через всю сеть используются средства сетевого уровня . Именно так организованы сети X.25. Иногда в глобальных сетях функции канального уровня в чистом виде выделить трудно, так как в одном и том же протоколе они объединяются с функциями сетевого уровня . Примерами такого подхода могут служить протоколы технологий ATM и frame relay.

В целом канальный уровень представляет собой весьма мощный набор функций по пересылке сообщений между узлами сети. В некоторых случаях протоколы канального уровня оказываются самодостаточными транспортными средствами, и тогда поверх них могут работать непосредственно протоколы прикладного уровня или приложения, без привлечения средств сетевого и транспортного уровней. Например, существует реализация протокола управления сетью SNMP непосредственно поверх Ethernet, хотя стандартно этот протокол работает поверх сетевого протокола IP и транспортного протокола UDP. Естественно, что применение такой реализации будет ограниченным - она не подходит для составных сетей разных технологий, например Ethernet и X.25, и даже для такой сети, в которой во всех сегментах применяется Ethernet, но между сегментами существуют петлевидные связи. А вот в двухсегментной сети Ethernet, объединенной мостом , реализация SNMP над канальным уровнем будет вполне работоспособна.

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

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

Другой областью действия протоколов канального уровня являются связи типа "точка-точка" глобальных сетей, когда протокол канального уровня ответственен за доставку кадра непосредственному соседу. Адрес в этом случае не имеет принципиального значения, а на первый план выходит способность протокола восстанавливать искаженные и утерянные кадры , так как плохое качество территориальных каналов, особенно коммутируемых телефонных, часто требует выполнения подобных действий. Если же перечисленные выше условия не соблюдаются, например связи между сегментами Ethernet имеют петлевидную структуру, либо объединяемые сети используют различные способы адресации , как в сетях Ethernet и X.25, то протокол канального уровня не может в одиночку справиться с задачей передачи кадра между узлами и требует помощи протокола сетевого уровня .

Сетевой уровень

Сетевой уровень (Network layer ) служит для образования единой транспортной системы, объединяющей несколько сетей, причем эти сети могут использовать различные принципы передачи сообщений между конечными узлами и обладать произвольной структурой связей. Функции сетевого уровня достаточно разнообразны. Рассмотрим их на примере объединения локальных сетей.

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

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

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

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

Сетевой уровень - доставка пакета :

между любыми двумя узлами сети с произвольной топологией;

между любыми двумя сетями в составной сети ;

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

маршрут - последовательность прохождения пакетом маршрутизаторов в составной сети .

На рис. 11.8 показаны четыре сети, связанные тремя маршрутизаторами . Между узлами А и В данной сети пролегает два маршрута : первый - через маршрутизаторы 1 и 3, а второй - через маршрутизаторы 1, 2 и 3.

Рис. 11.8. Пример составной сети.

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

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

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

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

На сетевом уровне работают протоколы еще одного типа, которые отвечают за отображение адреса узла, используемого на сетевом уровне , в локальный адрес сети. Такие протоколы часто называют протоколами разрешения адресов - Address Resolution Protocol , ARP . Иногда их относят не к сетевому уровню , а к канальному , хотя тонкости классификации не изменяют сути.

Примерами протоколов сетевого уровня являются протокол межсетевого взаимодействия IP стека TCP/IP и протокол межсетевого обмена пакетами IPX стека Novell.

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

Процесс передачи информации

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

Информационные сообщения

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

Информационные сигналы

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

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

Аналоговые и цифровые сигналы

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

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

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

Каналы передачи информации

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

ИИ - ПС - (КИ) - КК - М - ЛПИ - ДМ - ДК - ДИ - ПС

ИИ - источник информации: человек либо иное живое существо, книга, документ, изображение на неэлектронном носителе (холст, бумага) и т.д.

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

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

КК - канальный кодер для повышения помехозащищённости информсигнала.

М - сигнальный модулятор для изменения характеристик промежуточных сигналов-носителей в зависимости от величины информсигнала. Типичный пример - амплитудная модуляция сигнала-носителя высокой несущей частоты в зависимости от величины низкочастотного информсигнала.

ЛПИ - линия передачи информации, представляющая совокупность физической среды (например, электромагнитное поле) и технических средств для изменения ее состояния с целью передачи сигнала-носителя к приемнику.

ДМ - демодулятор для отделения информсигнала от сигнала-носителя. Присутствует только при наличии М.

ДК - канальный декодер для выявления и/или исправления ошибок в информсигнале, возникших на ЛПИ. Присутствует только при наличии КК.

ДИ - декодер информации. Присутствует только при наличии КИ.

ПИ - приемник информации (компьютер, принтер, дисплей и т. д.).

Если передача информации двусторонняя (канал дуплексный), то по обе стороны ЛПИ имеются блоки-модемы (МОдулятор-ДЕМодулятор), объединяющие в себе звенья М и ДМ, а также блоки-кодеки (КОдер-ДЕКодер), объединяющие кодеры (КИ и КК) и декодеры (ДИ и ДК).

Характеристики каналов передачи

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

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

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

Пропускная способность канала равна максимальному количеству двоичных символов (кбит), передаваемых им при отсутствии помех за одну секунду. Для различных каналов она варьируется от нескольких кбит/с до сотен Мбит/с и определяется их физическими свойствами.

Теория передачи информации

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

Цифровая обработка сигналов

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

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

На этом уровне работают концентраторы (хабы), повторители (ретрансляторы) сигнала и медиаконверторы...

Функции физического уровня реализуются на всех устройствах, подключенных к сети. Со стороны компьютера функции физического уровня выполняются сетевым адаптером или последовательным портом. К физическому уровню относятся физические, электрические и механические интерфейсы между двумя системами. Физический уровень определяет такие свойства среды сети передачи данных как оптоволокно, витая пара, коаксиальный кабель, спутниковый канал передачи данных и т. п. Стандартными типами сетевых интерфейсов, относящимися к физическому уровню, являются: V.35, RS-232C, RJ-11, RJ-45, разъемы AUI и BNC.

Особенности физического уровня модели OSI удобно рассматривать с использованием следующего рисунка:

Можно выделить следующие подуровни:

Reconciliation - подуровень согласования. Служит для перевода команд МАС-уровня в соответствующие электрические сигналы физического уровня.
MII - Medium Independent Interface, независимый от среды интерфейс. Обеспечивает стандартный интерфейс между МАС-уровнем и физическим уровнем.
PCS - Physical Coding Sublayer, подуровень физического кодирования. Выполняет кодирование и декодирование последовательностей данных из одного представления в другое.
PMA - Physical Medium Attachment, подуровень подсоединения к физической среде. Преобразует данные в битовый поток последовательных электрических сигналов, и обратно. Кроме того, обеспечивает синхронизацию приема/передачи.
PMD - Physical Medium Dependent, подуровень связи с физической средой. Отвечает за передачу сигналов в физической среде (усиление сигнала, модуляция, формирование сигнала).
AN - Auto-negotiation, согласование скорости. Используется для автоматического выбора устройствами протокола взаимодействия.
MDI - Medium Dependent Interface, зависимый от среды интерфейс. Определяет различные виды коннекторов для разных физических сред и PMD-устройств.

Среда передачи данных

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

Коаксиальный кабель был первым типом кабеля, использованным для соединения компьютеров в сеть. Кабель данного типа состоит из центрального медного проводника, покрытого пластиковым изолирующим материалом, который, в свою очередь, окружен медной сеткой и/или алюминиевой фольгой. Этот внешний проводник обеспечивает заземление и защиту центрального проводника от внешней электромагнитной интерференции. При прокладке сетей используются два типа кабеля - "Толстый коаксиальный кабель" (Thicknet) и "Тонкий коаксиальный кабель" (Thinnet). Максимальная длина сегмента лежит в диапазоне от 185 до 500 м в зависимости от типа кабеля.

Кабель типа "витая пара" (twisted pair), является одним из наиболее распространенных типов кабеля в настоящее время. Он состоит из нескольких пар медных проводов, покрытых пластиковой оболочкой. Провода, составляющие каждую пару, закручены вокруг друг друга, что обеспечивает защиту от взаимных наводок. Кабели данного типа делятся на два класса - "экранированная витая пара " ("Shielded twisted pair") и "неэкранированная витая пара " ("Unshielded twisted pair"). Отличие этих классов состоит в том, что экранированная витая пара является более защищенной от внешней электромагнитной интерференции, благодаря наличию дополнительного экрана из медной сетки и/или алюминиевой фольги, окружающего провода кабеля. Сети на основе "витой пары" в зависимости от категории кабеля обеспечивают передачу со скоростью от 10 Мбит/с – 1 Гбит/с. Длина сегмента кабеля не может превышать 100 м (до 100 Мбит/с) или 30 м (1 Гбит/с).

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

Канальный уровень

Канальный уровень (англ. Data Link layer) - уровень сетевой модели OSI, который предназначен для обеспечения взаимодействия сетей на физическом уровне и контроля за ошибками, которые могут возникнуть. Полученные с физического уровня данные он упаковывает во фреймы, проверяет на целостность, если нужно исправляет ошибки (посылает повторный запрос поврежденного кадра) и отправляет на сетевой уровень. Канальный уровень может взаимодействовать с одним или несколькими физическими уровнями, контролируя и управляя этим взаимодействием. Спецификация IEEE 802 разделяет этот уровень на 2 подуровня - MAC (Media Access Control) регулирует доступ к разделяемой физической среде, LLC (Logical Link Control) обеспечивает обслуживание сетевого уровня.

На этом уровне работают коммутаторы, мосты.

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

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

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

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

Информационное взаимодействие на канальном уровне сетей стандарта Ethernet так же, как и на физическом, принято разделять на дополнительные подуровни, которые не были предусмотрены стандартом OSI-7.

LLC (Logical Link Control). Уровень управления логическим каналом;
MAC (Media Access Control). Уровень доступа к среде.

Подуровень MAC

В идеология множественного доступа к среде Ethernet передачу данных приходится реализовать по широковещательному принципу "каждый для всех" (broadcasting). Это не может не наложить отпечаток на процесс формирования и распознавания кадров. Рассмотрим строение кадра Ethernet DIX, как наиболее часто используемого для передачи IP трафика.

Для идентификации устройств используются 6-ти байтовые MAC-адреса, которые отправитель обязательно должен указать в передаваемом кадре. Старшие три байта представляют собой идентификатор производителя оборудования (Vendor codes), младше - индивидуальный идентификатор устройства.

За уникальность последних несет ответственность производитель оборудования. С идентификаторами производителя дело обстоит сложнее. Существует специальная организация в составе IEEE, которая ведет список вендоров, выделяя каждому из них свой диапазон адресов. Кстати, занести туда свою запись стоит совсем не дорого, всего US 50. Можно отметить, что создатели технологии Ethernet, Ксерокс и DEC, занимают первую и последнюю строчку списка соответственно.

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

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

MAC-адрес может быть записан в различной форме. Наиболее часто используется шестнадцатеричная, в которой пары байтов отделяются друг от друга символами "-" или ":". Например, сетевая карта Realtek, установленная в моем домашнем компьютере, имеет адрес 00:C0:DF:F7:A4:25.

МАС-адрес позволяет выполнять единичную (Unicast), групповую (Multicast) и широковещательную адресацию кадров (Broadcast).

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

В режиме групповой адресации кадр будет обработан теми станциями, которые имеют такой же Vendor Code, как и у отправителя. Признаком такой посылки является "1" в младшем бите старшего байта МАС-адреса (X1:XX:XX:XX:XX:XX). Такой формат достаточно удобен для "фирменного" взаимодействия устройств, но на практике используется достаточно редко.

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

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

Преамбула (Preamble). Состоит из 8 байтов. Первые семь содержат одну и ту же циклическую последовательность битов (10101010), которая хорошо подходит для синхронизации приемопередатчиков. Последний (Start-of-frame-delimiter, SFD), 1 байт (10101011), служит меткой начала информационной части кадра. Это поле не учитывается при определении длины кадра и не рассчитывается в контрольной сумме.
МАС-адрес получателя (Destination Address, DA).
МАС-адрес отправителя (Source Address, SA). Первый бит всегда равен нулю.
Поле длины либо тип данных (Length/Type, L/T). Два байта, которые содержат явное указание длины (в байтах) поля данных в кадре или указывают на тип данных. Ниже, в описании LLC будет показано, что возможно простое автоматическое распознавание разных типов кадров.
Данные (Data). Полезная нагрузка кадра, данные верхних уровней OSI. Может иметь длину от 0 до 1500 байт.
Для корректного распознавания коллизий необходим кадр не менее чем из 64 байт. Если поле данных менее 46 байт, то кадр дополняется полем заполнения (Padding).
Контрольная сумма (Frame Check Sequence, FCS). 4 байта, которые содержит контрольную сумму всех информационных полей кадра. Вычисление выполняется по алгоритму CRC-32 отправителем и добавляется в кадр. После приема кадра в буфер, приемник выполняет аналогичный расчет. В случае расхождения результата вычислений, предполагается ошибка при передаче, и кадр уничтожается.

Подуровень LLC

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

Сетевые адаптеры

Сетевые адаптеры преобразуют пакеты данных в сигналы для передачи по сети. В ходе изготовления фирмой-производителем каждому сетевому адаптеру присваивается физический адрес, который заносится в специальную микросхему, устанавливаемую на плате адаптера. В большинстве сетевых адаптеров МАС-адрес зашивается в ПЗУ. Когда адаптер инициализируется, этот адрес копируется в оперативную память компьютера. Поскольку МАС-адрес определяется сетевым адаптером, то при замене адаптера изменится и физический адрес компьютера; он будет соответствовать МАС-адресу нового сетевого адаптера.
Для примера можно представить себе гостиницу. Предположим далее, что комната 207 имеет замок, открывающийся ключом А, а комната 410 - замок, открывающийся ключом F. Принято решение поменять замки в комнатах 207 и 410. После замены ключ А будет открывать комнату 410, а ключ F- комнату 207. В этом примере замки играют роль сетевых адаптеров, а ключи - роль МАС-адресов. Если адаптеры поменять местами, то изменятся и МАС-адреса.

ЗЫ. продолжение следует..

------
Основы организации сетей
wiki
nag.ru

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

Рис. 8.1. Пути передачи данных: а – виртуальный; б – фактический

Протоколы канального уровня описывают, каким образом логические биты или символы, передаваемые физическим уровнем, объединяются в более крупные единицы – кадры . Обобщенная структура кадра показана на рис. 8.2. В общем случае, каждый кадр содер­жит заголовок, поле данных и трейлер (или так называемый «концевик» ). Управление кадрами – одна их главнейших функций работы канального уровня.

Рис. 8.2. Обобщенная структура кадра протокола канального уровня

Канальный уровень может предоставлять различные сервисы и их на­бор может быть разным для разных систем. Обычно рассматриваются следующие возможные вари­анты:

1) сервис без подтверждений приема кадров и без установления соединения;

2) сервис с подтверждениями приема кадров и без установления соединения;

3) сервис с подтверждениями приема кадров и с установлением соединения.

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

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

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

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

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

1) подсчет количества символов;

2) применение сигнальных байтов с символьным заполнением;

3) использование стартовых и стоповых битов с битовым заполнением;

4) использование запрещенных сигналов физического уровня.

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

Второй метод формирования кадров решает проблему восстановления син­хронизации после сбоя при помощи маркировки начала и конца каждого кадра специальными байтами. В последнее время большинство протоколов перешло на использова­ние в обоих случаях одного и того же байта, называемого флаговым . Таким образом, если приемник теряет синхронизацию, ему необходимо просто найти флаговый байт, с помощью которого он распозна­ет конец текущего кадра. Два соседних флаговых байта говорят о том, что кон­чился один кадр и начался другой. Однако этот метод иногда приводит к серьезным проблемам при передачи бинарных данных, таких как объектные коды программ или числа с плавающей запятой. В передаваемых данных вполне может встретиться последовательность, исполь­зуемая в качестве флагового байта. Возникновение такой ситуации, скорее всего, собьет синхронизацию. Одним из способов решения проблемы является добав­ление специального escape-символа (знака переключения кода – ESC ) непосред­ственно перед байтом, случайно совпавшим с флаговым байтом внутри кадра. Канальный уровень получателя вначале убирает эти escape-символы, затем переда­ет кадр на сетевой уровень. Этот метод называется символьным заполнением. Таким образом, настоящий флаг можно отличить от «случайно совпавшего» по наличию или отсутствию перед ним символа ESC. Если же и символ ESC случайно окажется среди прочих данных, то перед этим фиктивным escape-символом также вставляется настоящий. Тогда любой одиночный ESC будет частью escape-после­довательности, а двойной будет указывать на то, что служебный байт случайно оказался в потоке данных. После очищения от вставных символов байтовая последовательности в точности совпадает с исходной. Главный недостаток этого метода заключается в том, что он тесно связан с 8-битными символами. Между тем не во всех кодировках один символ соответ­ствует 8 битам. Например, кодировка UNICODE использует 16-битное кодирование.

Следующий метод позволяет использовать кадры и наборы символов, состоящие из любого количества битов. При этом каждый кадр начинается и завершается специальной последовательностью битов 01111110. Битовое заполнение аналогично символьному, при котором в кадр перед случайно встретившимся среди данных флагом вставляется escape-символ. Битовое заполнение, как и сим­вольное, является абсолютно прозрачным для сетевого уровня обеих машин. Если флаговая последовательность битов (01111110) встречается в данных пользователя, она передается в виде 011111010, но в памяти принимающего ком­пьютера сохраняется опять в исходном виде: 01111110. Благодаря битовому заполнению границы между двумя кадрами могут быть безошибочно распознаны с помощью флаговой последовательности. Таким образом, если приемная сторона потеряет границы кадров, ей нужно всего лишь оты­скать в полученном потоке битов флаговый байт, поскольку он встречается толь­ко на границах кадров и не может присутствовать в данных пользователя.

Наконец, последний из рассматриваемых методов формирования кадров приемлем только в сетях, в которых физический носитель обладает некоторой избыточностью. Например, некоторые локальные сети кодируют один бит данных двумя физическими бита­ми. Так в «манчестерском» коде бит 1 кодируется парой высокого и низкого уровней сигналов (от­рицательный перепад), а бит 0 – наоборот, парой низкого и высокого уровней (положительный перепад). В такой схеме каждый передаваемый бит данных со­держит в середине переход, благодаря чему упрощается распознавание границ битов. Комбинации уровней сигналов (низкий–низкий и высокий–высокий) не используются для передачи данных, но используются в качестве ограничителей кадров в некоторых протоколах.

Отметим, что многие современные протоколы пе­редачи данных для повышения надежности применяют комбинированные методы формирования кадра.

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

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

Еще один важный аспект разработки канального уровня (а также более вы­соких уровней) связан с вопросом о том, что делать с отправителем, который по­стоянно желает передавать кадры быстрее, чем получатель способен их получать. Такая ситуация может возникнуть, если у передающей стороны оказывается бо­лее мощная (или менее загруженная) машина, чем у принимающей. При этом отпра­витель будет продолжает посылать кадры на высокой скорости до тех пор, пока получа­тель не окажется, как говорят, «затоплен» ими. Даже при идеально работающей линии связи в определенный момент времени получатель просто не сможет продолжать обработ­ку прибывающих кадров и начнет их терять. Для предотвраще­ния подобной ситуации чаще всего применяются два подхода. При первом, называющемся управлением потоком с обратной связью , получатель отсылает отправителю информацию, разрешающую последнему продолжить передачу или, по крайней мере, сообщающую о том, как идут дела у получателя. При втором подходе – управ­лении потоком с ограничением – в протокол встраивается механизм, ограничи­вающий скорость, с которой передатчики могут передавать данные, а обратная связь с получателем отсутствует. Известны различные схемы управления потоком с обратной связью, но большин­ство из них используют один и тот же принцип. Протокол содержит четко оп­ределенные правила, определяющие, когда отправитель может посылать следую­щий кадр. Эти правила часто запрещают пересылку кадра до тех пор, пока получатель не даст разрешения (явно либо неявно).

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

Рис. 8.7. P/V-система процессов для двух узлов графа вычислений на рис. 8.2.

Рис. 8.8. Добавление P/V-систем в иерархию моделей.

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

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

Пример системы из трех процессов приведен на рис. 8.9. Как видно из примера, описание процессов на ЯМПП является, по существу, схемой. Интерес представляет только деятельность по передаче сообщений в системе. Сообщения являются абстрактными элементами, единственной характеристикой которых является тип. Число типов сообщений в системе может быть только конечным. Сообщения посылаются из или принимаются в буфер сообщений в каждом из процессов. Существует только по одному буферу на процесс. Предложениями ЯМПП являются: Поместить сообщение типа в буфер сообщений. Послать сообщение в буфер сообщений канального процесса Запросить сообщение из канального процесса Ждать (если необходимо) до тех пор, пока не будет получено сообщение. Сообщение помещается в буфер сообщений. Проверить тип сообщения в буфере сообщений и перейти к предложению если сообщение имеет тип, отличный от : Моделировать внутреннюю, зависящую от данных, проверку. Либо продолжать обработку, выполняя следующее предложение, либо перейти к предложению с меткой Передать управление предложению Завершить процесс.

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

Для моделирования процесса сетью Петри используем по одной фишке на процесс в качестве программного счетчика. Присутствие сообщения в канальном процессе также представляется фишкой. Поскольку сообщения идентифицируются типом, то необходимо моделировать каждый тип сообщений в канальном процессе отдельной позицией. Очень важным свойством систем с ЯМПП является то, что число сообщений конечно. Каждый программный процесс также конечен. Только очередь сообщений занимает потенциально неограниченный объем памяти. Таким образом, способность моделировать канальные процессы и правильно представлять предложения send и receive являются наиболее важными аспектами преобразования описания на ЯМПП в сеть Петри. Моделируя

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

Единственным символом в выражении передачи сообщений является тип сообщений для тех сообщений, которые посылаются к или принимаются от канального процесса. Поскольку каждый переход в сети Петри приводит к появлению символа в языке сети Петри для этой сети Петри, то только предложения send и receive в системе с ЯМПП могут быть промоделированы. Таким образом, существуют два вида позиций в сети Петри. Один вид позиций, помеченных действует как счетчик числа сообщений типа в канальном процессе Другой вид позиций представляет предложения send и receive программы ЯМПП. Пусть эти предложения однозначно помечены Мы пометим позицию, представляющую предложение с сообщением типа в буфере сообщений, символом Фишка в позиции, ассоциированной с предложением означает, что предложение уже выполнено. Рис. 8.10 иллюстрирует, как предложения должны моделироваться сетью Петри. На рис. 8.10 позиция представляет позицию, ассоциированную с каким-либо предложением, которое предшествует предложению

Теперь осталось показать, что существует возможность определения предложения, предшествующего другим предложениям в программе на ЯМПП. Отметим, что каждое предложение можно рассматривать как пару, состоящую из типа сообщения и номера предложения, поскольку одно и то же предложение с различными типами сообщений в буфере сообщений будет моделироваться сетью Петри различным образом. Наиболее очевидный способ определения предшественников предложения состоит в запуске в начале каждой программы на ЯМПП специального стартового предложения (которое становится стартовой позицией) и в порождении согласно описанию программ всех возможных последующих предложений send и receive с соответствующим им содержимым буфера сообщений. Этот процесс повторяется для всех появляющихся предложений до тех пор, пока все предложения send и receive не будут порождены, а их последователи не будут идентифицированы. Поскольку число предложений в описании на ЯМПП и число типов сообщений конечно, то порождается только конечное число пар предложение! /тип, сообщение. Эта процедура подобна характеристическим уравнениям, используемым Риддлом для построения выражения передачи сообщений. На рис. 8.11 перечисляются предложения

Рис. 8.10. (см. скан) Преобразование предложений send и receive в переходы сети Петри. вверху - модель предложения sk:send с сообщением типа в буфере сообщений. Канальный процесс внизу - модель предложения sk:receive из канального процесса Возможные типы сообщений в

и их возможные последователи для системы с ЯМПП, изображенной на рис. 8.9.

После того как последователи предложения определены, мы можем, используя эту информацию, идентифицировать возможные предшественники предложения и, следовательно, построить сеть Петри, эквивалентную системе с ЯМПП, используя переходы, подобные приведенным на рис. 8.10. Специальная стартовая позиция является предшественником первого предложения каждого процесса системы. На рис. 8.12 система с ЯМПП, изображенная на рис. 8.9, преобразована в эквивалентную сеть Петри.

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

Поскольку P/V-системы можно моделировать системами передачи сообщений с сообщениями только одного типа, то P/V-системы

Рис. 8.11. (см. скан) Предложения и последователи для системы с ЯМПП, изображенной на рис. 8.9.

включаются в системы передачи сообщений. Легко построить систему с сообщениями для решения задачи о курильщиках сигарет, поэтому включение P/V-систем в системы с сообщениями является собственным. С другой стороны, системы с сообщениями не способны воспринимать входные сообщения от нескольких источников одновременно и поэтому не эквивалентны сетям Петри.

При попытке моделирования перехода с несколькими входами может возникнуть один из следующих двух случаев:

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

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

(кликните для просмотра скана)

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

Рис. 8.13. Добавление систем с сообщениями к иерархии моделей.

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