Программное обеспечение систем телеобработки данных. Создание логической сети в VMM

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

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

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

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

Дадим более четкое определение понятия логической сети. Пусть мы имеем конечное множество А

И пусть нам задано множество В, элементами которого являются упорядоченные пары элементов множества А

Здесь - любые из элементов множества

Пусть, наконец, нам задано некоторое множество элементами которого являются логические функции

Установим однозначное отображение множества А на т. е. сопоставим каждому элементу множества А один из элементов множества

Определение 3-1. Совокупность множества А и В совместно с однозначным отображением множества А на множестве называется логической сетью.

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

Рис. 3-1. (см. скан)

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

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

Пример 3-1. Пусть

и отображение А на задано как

Соответствующая схема заданной логической сети показана на рис. 3-1,а.

Рассмотрим множество аргументов

Произведем теперь отображение некоторых подмножеств множества X на некоторые элементы множества А

где X - некоторое подмножество множества X.

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

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

Пример 3-2. Для логической сети рис. 3-1,а заданы:

Соответствующая схема логической сети чриведеиа на рис. 3-1,б.

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

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

Определение 3-2. Упорядоченная и правильная логическая сеть называется регулярной логической сетью (РЛС).

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

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

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

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

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

Контрольные вопросы:

Какие частные задачи необходимо решить для обеспечения коммутации в сети?

Какие критерии оптимальности нашли применение при определении маршрута?

Поясните сущность операций мультиплексирования и демультиплексирования.

Основные достоинства и недостатки сетей с коммутацией каналов (пакетов).

Сущность дейтаграммного способа передачи данных.

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

Сегодня на занятии мы продолжим изучение темы №1: « Архитектура сетей ЭВМ » и рассмотрим тему:« Структуризация и характеристики сетей ЭВМ ».

Основная часть

1. Физическая и логическая структуры сети

1.1. Причины структуризации сетей

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

ограничения на длину связи между узлами;

ограничения на количество узлов в сети;

ограничения на интенсивность трафика, порождаемого узлами сети.

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

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

1.2. Физическая структуризация сети

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

В работе концентраторов любых технологий много общего - они повторяют сигналы, пришедшие с одного из своих портов, на других своих портах (см. рис. 1). Концентраторы характерны практически для всех базовых технологий локальных сетей - Ethernet , ArcNet , Token Ring , FDDI , Fast Ethernet , Gigabit Ethernet . Добавление в сеть концентратора всегда изменяет ее физическую топологию, но при этом оставляет без изменения логическую топологию. Во многих случаях физическая и логическая топологии сети совпадают.

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

Рис. 1. Концентраторы технологий EthernetиTokenRing.

6 . СТРУКТУРИЗАЦИЯ КАК СРЕДСТВО ПОСТРОЕНИЯ БОЛЬШИХ СЕТЕЙ

6.3. Логическая структуризация сети

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

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

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

Рис. 17. Противоречие между логической структурой сети и структурой информационных потоков

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

ВНИМАНИЕ

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

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

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

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

от коэффициента использования

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

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

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

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

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

В целом логическая структуризация сети приводит к следующему.

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

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

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

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

Рис. 8.5.

Рис. 8.6. Логическая структура продолжает соответствовать "общей шине".

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

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

Рис. 8.7.

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

Для логической структуризации сети используются коммуникационные устройства:

мосты ;
коммутаторы ;
маршрутизаторы ;
шлюзы .

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

На рис. 8.8 показана сеть , которая была получена из сети с центральным концентратором (см. рис. 8.5) путем его замены на мост . Сети 1-го и 2-го отделов состоят из отдельных логических сегментов, а сеть отдела 3 - из двух логических сегментов. Каждый логический сегмент построен на базе концентратора и имеет простейшую физическую структуру , образованную отрезками кабеля, связывающими компьютеры с портами концентратора . Если пользователь компьютера А пошлет данные пользователю компьютера В, находящемуся в одном с ним сегменте, то эти данные будут повторены только на тех сетевых интерфейсах , которые отмечены на рисунке заштрихованными кружками.

Рис. 8.8.

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

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

Ограничения, связанные с применением мостов и коммутаторов - по

Введение

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

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

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

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

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

Логические сети

Определение и реализация булевых функций

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

На рисунке 1 приведен пример контактной схемы с двумя полюсами а1 и а6.

Рисунок 1

(k+1) - полюсная схема, в которой один полюс выделен (он называется входным), а остальные полюса (выходные) равноправны, называется (1,k)-полюсником. Таким образом, если в приведенной на рисунке 1 двухполюсной схеме рассматривать, например, полюс а1 как входной, а полюс а6, как выходной, то получаем (1, 1)-полюсник.

Ребра контактной схемы называются контактами. Контакт, соответствующий логической переменной называется замыкающим и обозначается через. Замыкающий контакт пропускает ток при Контакт, соответствующий литере называется размыкающим и обозначается как. Через него ток проходит при Таким образом, значение 1 интерпретируется как состояние переключателя “ток проходит”, а 0 -- “ток не проходит”. Функции соответствует последовательное соединение контактов, а функции -- параллельное соединение контактов

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

Рисунок 2

Рисунок 3

Пусть a, b -- полюса контактной схемы, -- некоторая цепь из а в b, -- конъюнкция литер, приписанных ребрам цепи. Функция, определяемая формулой в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса a и b, называется функцией проводимости между полюсами a и b схем Говорят, что функция реализуется (1, k)-полюсником, если существует такой выходной полюс что где а -- входной полюс. (1,1)-полюсники называются эквивалентными, если они реализуют одну и ту же булеву функцию. Сложностью (1,1)-полюсника называется число контактов. (1,1)-полюсник, имеющий наименьшую сложность среди эквивалентных ему схем, называется минимальным. Сложность минимального (1,1)-полюсника, реализующего функцию называется сложностью функции в классе (1,1)-полюсников и обозначается через.

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

математический метод логический матрица задача

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

Эффективное уменьшение числа контактов достигается с помощью нахождения минимальной ДНФ булевой функции.

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

С помощью таблицы истинности определим совершенную ДНФ:

Используя один из методов нахождения минимальной ДНФ, получаем формулу эквивалентную формуле (1) и соответствующую схеме, состоящей из семи контактов (рисунок 4а).

Рисунок 4

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