Коммутатор локальной сети

1. Понятие асинхронного процесса (АП)

2. Коммутаторы локальной сети

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

4. Репозиция

5. Редукция

6. Композиция

7. Сеть Петри

Заключение

Список использованной литературы

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

— построить метамодель «асинхронный процесс» и определить свойства исходного процесса на основе анализа метамодели;

— выполнить операции над процессом: репозиция, редукция, композиция, и оценить полученные результаты с практической точки зрения;

— построить предметную интерпретацию метамодели на основе сети Петри и сделать вывод о динамических характеристиках исходного процесса.

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

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

Структурная схема коммутатора EtherSwitch, предложенного фирмой Kalpana, представлена на рисунке.

Каждый из 8 портов 10Base-T обслуживается одним процессором пакетов Ethernet — ЕРР (Ethernet Packet Processor). Кроме того, коммутатор имеет системный модуль, который координирует работу всех процессоров ЕРР. Системный модуль ведет общую адресную таблицу коммутатора и обеспечивает управление коммутатором по протоколу SNMP (Simple Network Management Protocol). Для передачи кадров между портами используется коммутационная матрица, подобная тем, которые работают в телефонных коммутаторах или мультипроцессорных компьютерах, соединяя несколько процессоров с несколькими модулями памяти.

Коммутационная матрица работает по принципу коммутации каналов. Для 8 портов матрица может обеспечить 8 одновременных внутренних каналов при полудуплексном режиме работы портов и 16 — при полнодуплексном, когда передатчик и приемник каждого порта работают независимо друг от друга.

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

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

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

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

После того как нужный путь установлен, в него направляются буферизованные байты кадра, которые принимаются процессором выходного порта. Как только процессор выходного порта получает доступ к подключенному к нему сегменту Ethernet по алгоритму CSMA/CD (carrier-sense-multiply-access with collusion detection — метод коллективного доступа с опознаванием несущей и обнаружением коллизий), байты кадра сразу же начинают передаваться в сеть. Процессор входного порта постоянно хранит несколько байт принимаемого кадра в своем буфере, что позволяет ему независимо и асинхронно принимать и передавать байты кадра.

Описанный способ передачи кадра без его полной буферизации получил название коммутации «на лету» («on-the-fly») или «напролет» («cut-through»). Этот способ представляет, по сути, конвейерную обработку кадра, когда частично совмещаются во времени несколько этапов его передачи.

3. Построение метамодели «асинхронный процесс»

Составим асинхронный процесс P= передачи кадра через коммутатор. Множество ситуаций S определим следующим образом:

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

S2. Поиск адреса назначения в адресной таблице коммутатора (в кэше процессора или в общей таблице системного модуля).

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

S4. Невозможность коммутации матрицы (выходной порт уже занят). Ошибка установления соединения.

S5. Прием остальных байт кадра процессором входного порта.

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

S7. Передача байт кадра процессором выходного порта в сеть.

Опишем компоненты, которые контролируют данные ситуации:

P1 — идет прием данных на входном порте

P2 — идет поиск адреса назначения

P3 — коммутация матрицы (установление пути)

P4 — входной порт передает данные кадра

P5 — идет прием данных на выходном порте

P6 — выходной порт передает данные кадра в сеть Теперь можно провести структурирование ситуаций, представив их в виде двоичных векторов:

Граф отношения F для данного процесса:

Множество инициаторов и результантов:

I = { S1}

Инициаторы активизируют процесс.

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

R = { S4, S7}

Результанты — это финальные ситуации.

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

Траектории выполнения процесса:

1: (S1, S2, S4)

2: (S1, S2, S3, S5,S6,S7)

Данный асинхронный процесс является эффективным, т.к. он удовлетворяем следующим свойствам:

1)

2)

3) ,

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

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

Данный АП является простым, т.к. выполняются условия:

1)

2) ,

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

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

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

Рассмотрим процесс P' = :

S'={S1, S7, S8}, где

S7 — передача в сеть с выходного порта последней порции данных текущего кадра

S1 — передача на входной порт концентратора первых байт следующего кадра

S8 ={1}- разрыв установившейся связи между входным и выходным портами

F' будет выглядеть следующим образом:

I' = {S7}

R' = {S1}

Составленная репозиция является частичной, т.к. (I' = R)

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

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

АП P (X*) =

S = {S1,S2,S3,S4,S5,S6,S7} = {100 000, 110 000, 101 110, 10, 101 000, 1 110, 1 001}

I = {S1} = {100 000}

R = {S4,S7} = {10,001001}

Траектории процесса P:

1: (S1,S2,S4) = (100 000, 110 000, 10)

2: (S1,S2,S3,S5,S6,S7) = (100 000, 110 000, 101 110, 101 000, 1 110, 1 001)

Выделение входных и выходных компонент:

Множество входных компонент X = {P1}

т.к. на входной порт передаются данные из сети (P1)

Множество выходных компонент Y = {P5,P6}

т.к. данные принимаются на выходном порте и передаются в сеть.

Множество остальных компонент Z = {P2,P3,P4}

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

Множество значений выходных компонент Y = {01, 10, 00}

Рассмотрим два возможных значения: Y* = {10, 00}

S* = {100 000,110000,101 110,000010,101 000,001110}

В S (Y*) попадают ситуации из S* из траекторий, которые полностью состоят из ситуаций S*.

S (Y*) = {100 000,110000,10} = {S1,S2,S4}

F (Y*):

I (Y*) = {S1} = {100 000}

R (Y*) = {S4} = {10}

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

6. Композиция В данном случае композиция представляет собой «объединение» процесса подачи звукового сигнала в случае ошибки коммутации матрицы и процесса ответственного за обработку ошибки коммутации матрицы (ошибки соединения) .

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

Процесс P1 — подача звукового сигнала:

P1 =

Компоненты:

1) P5 — идет прием данных на выходном порте

2) P6 — выходной порт передает данные кадра в сеть

3) Flag — True/False (срабатывание звукового сигнала) Ситуации:

1) Начался прием данных на выходном порте s1 = (1 0 0)

2) Прием данных на выходном порте закончился и данные передаются в сеть s2 = (1 1 0)

3) Возникла ошибка коммутации звучит сигнал s3 = (0 0 1)

Отношение непосредственного следования ситуаций F1:

Траектория: (100, 110, 001)

Множество инициаторов I1 = {s1} - процесс начинается с приема данных на выходном порте Множество результантов R1 = {s3} - завершение, звучит звуковой сигнал Входные компоненты X1 = {P5, P6} = {10,11,00}

Выходные компоненты Y1 = {Flag} = {0, 1}

Процесс P2 — редукция исходного процесса P.

Выделим входные компоненты первого процесса и выходные компоненты второго процесса, имеющие сходную семантику:

Y* = { P5, P6}

X* = { P5, P6}

Построим по ним соответствующие редукции процессов:

S1* = S1(Y*) = S1 = {100, 110, 001}

F1* = F1

I1(Y*) = I1

R1(Y*) = R1

Второй процесс уже является редукцией

S (Y*) = {100 000,110000,10} = {S1,S2,S4}

F (Y*):

I (Y*) = {S1} = {100 000}

R (Y*) = {S4} = {10}

Ситуации процесса P3 представимы в виде пар s3 = (s1, s2) /

коммутация сегмент передача буферизация

1)

2) y1 = x2

3)

4) или

или

Таким образом, АП P3 =

S3 = {1 000 000, 1 100 000, 100, 100, 110,0000101}

F3 :

I3 = {1 000 000}

R3 = {101}

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

7. Сеть Петри

N =

Множество условий P = {p1, p2, p3, p4, p5, p6}

Множество событий T = {S1, S2, S3, S4, S5, S6,S7}

Функции инцидентности

F (P1, S2) = F (P2, S3) = F (p3, S4) = F (p4, S4) = F (p5, S4) = F (p1,S4) = F (p1,S6) = F (p5,S5) = F (p4,S7) = F (p5,S7) = 1

H (S2, p1) = H (S2, p2) = H (S4, p5) = H (S7,p6) = H (S3,p3) = H (S3,p4) = H (S3,p5)= H (S5,p3) = H (S5,p1) = H (S6,p4) = H (S6,p5)=1

Начальная разметка М0 = {1, 0, 0, 0, 0, 0}

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

Условие p в сети N называется ограниченным, если существует число n / для любой достижимой в сети разметки N справедливо неравенство M (p)? n.

В данной сети для условий p1, p2, p3, p4,p5,p6 таким числом является 1.

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

Сеть называется ограниченной, если каждое ее место ограничено.

В данной сети все места ограничены, значит и сама сеть ограничена.

Условие p называется безопасным, если для любой разметки М, достижимой в сети N, имеет место условие: М (р)? 1.

В данной сети условия p1, p2, p3, p4,p5,p6 являются безопасными (это хорошо видно по дереву разметок),

Сеть N безопасна, если все ее условия безопасны.

Данная сеть является безопасной, т.к. все ее условия безопасны.

Переход t в сети N называется потенциально живым при разметке M R (N), если существует разметка M' R (N, M) / M'? F (p, t), т. е. существует достижимая от М разметка М', при которой переход t может сработать.

Если М = М0, то переход t называется потенциально живым в сети N.

При начальной разметке М0 для всех переходов существует достижимая разметка, при которой они могут сработать (это видно, например, по дереву разметок). Следовательно, переходы p1, p2, p3, p4,p5,p6 являются потенциально живыми в сети N.

Переход t в сети N называется живым, если, т. е. он потенциально жив при любой достижимой в сети разметке.

В данной сети все переходы не являются живыми в сети N.

Сеть называется живой, если все ее переходы живы.

Данная сеть не является живой, т.к. не все (в данном случае — никакие) ее переходы являются живыми.

Переход t называется устойчивым в сети N, если

,

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

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

Переход t2 может сработать только при разметке {1, 0, 0, 1, 1}. Но при ней может сработать и переход t3, лишив таким образом тот возможности выполниться (т.е. при данной разметке M). Следовательно, переход t2 не является устойчивым.

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

Переход t4 может сработать только при разметке {1, 1, 0, 0, 0}, и никакой другой переход не может сработать при ней. Следовательно, переход t4 является устойчивым.

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

Сеть N называется устойчивой, если все ее переходы устойчивы.

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

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

Заключение

Модель — представление в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Каждая модель отражает те или иные аспекты поведения системы. Наличие общих свойств у таких моделей позволяет предположить некоторую метамодель, которая порождает частные объектные модели. Метамодель — модель, применяемая для исследования и описания некоторого класса моделей. В данном РГЗ в качестве метамодели мы рассмотрели модель «Асинхронный процесс».

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

Список использованной литературы

1. Компьютерные сети: принципы, технологии, протоколы / В. Г. Олифер, Н. А. Олифер. — СПб.: Питер, 2001

2. Конспект лекций Лазаревой И. М. по дисциплине «Теория вычислительных процессов»