close

Вход

Забыли?

вход по аккаунту

?

Krylov 0D51C151E4

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ПЕРЕДАЧА ИНФОРМАЦИИ
В ИНТЕГРИРОВАННЫХ
ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
Методические указания
к выполнению лабораторных работ
Санкт-Петербург
2012
Составитель Ю. Д. Крылов
Рецензент кандидат технических наук доцент А. А. Ключарев
Содержатся указания к выполнению лабораторных работ по дисциплинам «Сети ЭВМ и телекоммуникаций» и «Интегрированные
вычислительные сети». Изложены один из основных методов маршрутизации (метод рельефов) и метод распределения потоков информации (метод отклонения потока), применяемые в современных вычислительных сетях.
Материал предложен для студентов, обучающихся по специальности «Вычислительные машины, комплексы, системы и сети» и
«Программное обеспечение вычислительной техники и автоматизированных систем «, но может быть полезным при изучении смежных дисциплин по ряду специальностей.
Подготовлены кафедрой вычислительных систем и сетей и рекомендованы к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического
приборостроения.
Редактор Л. А. Яковлева
Верстальщик С. Б. Мацапура
Сдано в набор 20.07.12. Подписано к печати 03.10.12.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 1,3.
Уч.-изд. л. 1,4. Тираж 100 экз. Заказ № 510.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2012
ВВЕДЕНИЕ
В настоящее время все большее значение приобретают сети ЭВМ
и телекоммуникаций и интегрированные вычислительные сети.
Появились новые информационные технологии, позволяющие соединять локальные и глобальные вычислительные сети и передавать разнородный трафик. Интегрированные вычислительные сети
предоставляют широкий круг услуг пользователям и даже допускают в определенных пределах управление со стороны пользователя.
Маршрутизация – это выбор наилучшего в некотором смысле
пути между двумя любыми абонентскими машинами для передачи
информации при их функционировании в составе территориально
распределенной вычислительной сети [1]. При этом критерии выбора маршрута могут быть различными. Метод рельефов обеспечивает нахождение кратчайшего пути по критерию минимизации
числа так называемых хопов (прыжков) или числа коммуникационных машин между двумя взаимодействующими абонентскими
машинами [2].
В сетях пакетной коммутации применяются различные принципы построения плана распределения информации, т. е. направлений для передачи по ним пакетов. Одним из перспективных методов является метод отклонений потока, который обеспечивает
рассеяние каждого потока по направлениям. При этом достигается
минимизация среднего времени доставки информации по всем потокам [2].
3
УЧЕБНО-ИССЛЕДОВАТЕЛЬСКАЯ
ЛАБОРАТОРНАЯ РАБОТА № 1
МЕТОД РЕЛЬЕФОВ
Цель работы: ознакомить студентов с одним из методов динамического управления передачей данных по сетям – методом рельефов, позволяющим выбирать путь между двумя узлами сети, минимальный с точки зрения числа транзитных участков.
Теоретические пояснения
Метод рельефов относится к групповым распределенным методам динамического управления. Критерием выбора пути является минимизация длины пути, выраженная числом транзитных
участков. На сети связи при применении этого метода должны выполняться операции формирования рельефа и его коррекция. Формирование рельефа осуществляется в начальный момент времени
(в момент пуска сети) и при развитии сети, т. е. при вводе в действие новых узлов коммутации (УК). Коррекция выполняется периодически в процессе функционирования сети или в момент возникновения повреждений или перегрузок.
Рассмотрим эти операции подробнее.
Формирование рельефа. В момент пуска сети формирование
рельефа начинается с некоторого узла УКa, a = 1,2, …, N, где N –
число УК на сети. Говорят, что начинается построение a-рельефа.
В запоминающих устройствах каждого УКi сети отводится объем
памяти N*Mi, где Mi – число исходящих направлений из УКi. Туда
заносится матрица рельефов Ri. При этом i – номер вершины узла
коммутации.
При формировании рельефа из УК-инициализатора во все исходящие из него направления передается цифра 1. Эта единица на
соседних с УК-инициализатором узлах заносится в матрицу Ri по
координатам (n,m1), где n – номер УК-инициализатора; m1 – номер
ветви по которой поступила единица.
Далее процесс построения рельефа производится следующим
образом. Все УК, в которые поступила цифра 1, передают по всем
исходящим направлениям за исключением того направления, по
которому поступила 1, цифру 2. Эта цифра во всех УК, в которые
она поступила, заносится в матрицу Ri по координатам (n,m2), где
m2 – номер ветви, по которой поступила цифра 2. Теперь УК, на
4
которые поступила цифра 2, передают по исходящим направлениям цифру 3 и так далее, при этом должны соблюдаться следующие
правила:
1. Если в УК поступили одинаковые цифры с двух и более направлений, то данный УК инициирует передачу цифры на единицу
больше поступившей по всем без исключения исходящим направлениям.
2. Если в УК поступает цифра с одного направления, то на данном УК происходит инициализация для передачи цифры на единицу больше той, которая поступила по всем направлениям, за исключением того направления, по которому получена данная цифра. Передача цифры по этому направлению возможна лишь при
поступлении в данный УК следующей цифры. Следовательно, цифра, передаваемая по этому направлению, должна быть на единицу
больше цифры, поступающей второй по порядку.
3. Инициализация передачи цифр по всем направлениям на
каждом УК происходит один раз после поступления первой цифры
по порядку.
Пример. Пусть имеется сеть, фрагмент которой изображен на
рис. 1.
Пусть в каждом УК отведена область памяти для формирования матрицы R, фрагменты которых для строки, соответствующей
УКА, приведены на рис. 2 (bij – ветвь от УКi к УКj). Пусть узломинициатором является УКА. В этом случае цифра 1 будет записана
на матрицу RB и RC узлов коммутации УКB и УКC. Далее эти УК
передают по всем исходящим направлениям, за исключением того
направления, по которому поступила цифра 1, цифру 2, которая бу1
1
УКА
1
1
2
2
2
2
3
УК D
3
УК B
2
УК C
3
2
4
3
2
2
3
УК E
3
2
3
3
УК F
3
Рис. 1. Фрагмент сети
5
RB
УКА
RD
УКА
bBA bBC bBD bBE
1
2
4
RC
3
УКА
bDB bDE
2
RE
3
УКА
RF
bFC
УКА
2
bCA bCB bCE
1
2
3
bEB bEC bED
2
2
3
Рис. 2. Фрагменты матриц рельефов
дет занесена в матрицы RB, RC, RD, RE, RF. Теперь УК, на которые
поступила цифра 2, передают по исходящим направлениям цифру
3, соблюдая при этом приведенные выше правила.
Так, согласно правилу 1 в УКЕ цифра 2 поступает с направлений, идущих от УКВ и УКС. В этом случае цифра 3 с УКЕ передается по всем исходящим направлениям, включая УКВ и УКС.
Согласно правилу 2 в УКD цифра 2 поступает только по одному
направлению – от УКВ. Тогда цифра 3 с УКD должна передаваться по всем направлениям, за исключением направления к УКВ. По
этому направлению будет передана цифра 4, так как следующая по
порядку цифра, поступившая в УКD, – цифра 3.
В соответствии с правилом 3 при передаче цифры 3 на УКС от
УКЕ она заносится в матрицу RC по соответствующим координатам, а инициализация передачи следующей по порядку цифры уже
не происходит, так как ранее была осуществлена передача цифры 2.
Так будет сформирован А-рельеф. Аналогично строятся рельефы для всех остальных узлов сети. Считается, что рельеф сформирован, если построены все a-рельефы (a = 1, 2, … N).
Поиск оптимального пути. При установлении соединения от УКi
к УКj поиск оптимального пути состоит в отыскании в УКi и в каждом промежуточном УК ветви, которой соответствует минимальное
число в соответствующей строке матрицы рельефов для УКj.
Пример. Пусть требуется установить соединение от УКD к УКА
(рис. 1). На УКD происходит обращение к строке матрицы рельефов
RD, соответствующей УКА (рис. 2).
6
Соединение устанавливается по ветви, которой соответствует
минимальное число в этой строке. Для рассматриваемого примера – это ветвь bDB. На УКВ процесс поиска оптимального пути повторяется. В данном случае будет выбрана ветвь bВА.
Если в этой ветви нет свободных каналов, то выбирается та
ветвь, которой соответствует следующее по порядку число (в примере – это ветвь bВС) и т. д.
При выборе пути возможно возникновение «петель», когда соединение дважды проходит через один и тот же узел. «Петли» могут
быть двух типов – прямые и косвенные.
Пример. Пусть требуется установить соединение от УКD к УКA.
На УКD выбирается ветвь bDB. Пусть теперь в ветви bBA нет ни одного свободного канала. Тогда вызов согласно матрице RB перенаправляется по ветви bBC. Если в ветви bCA тоже нет свободных каналов, то согласно матрице RC вызов должен быть направлен обратно на УКВ. Это первый тип «петли». При соответствующей комбинации загрузок каналов в узлах, участвующих в передаче, данный
вызов может блуждать по сети, например, по такой петле: bDB, bBC,
bCE, bCB. Вызов дважды попадает в УКВ. Это второй тип «петли».
Появление «петель» первого и второго типов недопустимо. Способ борьбы с ними заключается в том, что в процессе распространения по сети вызов «запоминает» номера УК, через которые он прошел, чтобы не проходить через них дважды.
Коррекция рельефа. Ситуация на сети непрерывно меняется:
одни направления перегружаются, а нагрузка других уменьшается; могут выйти из строя каналы связи; могут быть повреждения в
отдельных направлениях связи и УК. Поэтому необходима периодическая коррекция рельефа сети.
Рассмотрим процесс обмена служебной информацией между
управляющими устройствами (УУ) соседних узлов УКi, УКk, УКm
при коррекции рельефа сети, фрагмент которой приведен на рис. 3,
а соответствующие матрицы рельефов – на рис. 4.
Пусть на УКi поступил сигнал начала передачи служебной информации о рельефах на соседние УК. Тогда его УУ считает из запоминающего устройства (ЗУ), в котором хранится матрица Ri,
элементы первой строки и найдет минимальный из них. Предположим, что минимальным элементом, т. е. элементом с минимальной
высотой первого рельефа, будет r1k. Это означает, что кратчайший
путь из УКi до УК1 проходит через узел УКk, а число транзитных
участков в нем равно r1k. Согласно определению формирования рельефа УУ, прибавив единицу к этому элементу, получим элемент ri1
7
Rk
Ri
Rk
УК k
Ri
Rm
Rm
УК i
УК m
Ri
R1
Rm
Рис. 3. Фрагмент сети
Rk
Ri
Rm
bi1
УК1 ri1
bik
r1k
biMi Rimin
r1Mi
УК1
УКj
УКj rj1
rjk
rjMi
УКj
УКN
УКN rN1
rNk
rNMi
УКN
УК1
bki
bmi
Рис. 4. Матрицы рельефов
= min (r11, …, r1k, … r1Mi) +1, который необходимо передать на соседние узлы. Значение ri1 равно высоте первого рельефа тех ветвей,
которые связывают узлы с УКi.
Однако в рассматриваемой распределенной системе динамического управления элемент ri1 не передается на соседние узлы до тех
пор, пока не будут определены другие элементы, соответствующие
другим рельефам, т. е.
ri2 = min (r21, …, r2k,… r2Mi) +1;
.............
riN = min (rN1, …, rNk,… rNMi) +1.
Эти элементы образуют вектор Rimin = (ri1, …, rij, …, riN).
После того, как вектор Rimin полностью вычислен управляющим
устройством, УКi передает его в УУ всех соседних УК (рис. 4). При
этом он записывается в ЗУ этих УК в качестве столбцов матрицы
рельефов. Точно такие же операции выполняют управляющие
устройства всех остальных УК.
Если в какой-либо ветви, например, bi,k, отсутствуют каналы
или она повреждена, то при вычислении элементов rij (j = 1, …, N)
принимаем rj,k = ∞.
8
Содержание отчета
1. Задание с изображением топологической схемы.
2. Текст программы (с подробными комментариями) для определения оптимальных путей до исходной вершины от вершин, не
являющихся соседними с исходной, методом рельефов. Программа
должна иметь возможность изменения исходных данных.
3. Результаты работы программы для разных вершин – источников.
4. «Деревья» кратчайших путей от рассматриваемых вершин до
исходной вершины.
Варианты заданий
1. Расположение вершин такое же, как и на рис. 1.
2. Соответствие номеров и обозначений вершин следующее:
1 – A; 2 – B; 3 – C; 4 – D; 5 – E, 6 – F.
3. Номер топологической схемы (таблица) выбирается по формуле Nсхемы = 1+ i(mod 4), где i – номер варианта задания.
4. Выбор исходной вершины определяется по формуле
Nвершины = 1+ i(mod 6).
Номер топологической схемы
№ топологической схемы
Ребра, соединяющие вершины
1
2
3
4
AB; AC; BC; BD; BE; CF; DE; EC
AB; AC; BC; BD; BE; CF; DE; EF
AB; AC; BC; BD; BE; CE; CF; EF
AB; AC; BC; BD; CE; CF; DE; EF
9
УЧЕБНО-ИССЛЕДОВАТЕЛЬСКАЯ
ЛАБОРАТОРНАЯ РАБОТА № 2
МЕТОД ОТКЛОНЕНИЙ
Цель работы: ознакомление с методами пакетной коммутации
на сетях при распределении передаваемой информации по каналам
связи для сокращения времени передачи пакета между двумя корреспондирующими узлами коммутации.
Теоретические пояснения
На сети пакетной коммутации применяются различные принципы построения плана распределения информации, т. е. способа
выбора на узлах коммутации (УК) исходящих направлений для
передачи по ним пакетов. Рассмотрим три наиболее характерных.
Первый способ является наиболее простым и предполагает наличие только одного кратчайшего пути передачи пакетов между двумя корреспондирующими УК. При этом матрица маршрутов для
УКi представляет собой вырожденную (единичную) или примитивную матрицу размера N строк на ni столбцов (N – число УК в сети,
ni – число ветвей в узле УКi), например, такого вида:
bi1
0
…
Mi = УКj
1
…
УКN 0
УК1
…
…
…
…
…
bik
1
…
0
...
1
…
…
…
…
…
bini
0
0
0
В такой матрице каждый элемент равен 1 или 0, т. е. mji ∈ (0,1),
в одной строке имеется только одна единица. Поэтому пакеты к
узлу назначения УК1 с УКi будут передаваться только по ветви bik,
если m1k = 1.
Этот способ прост, но не позволяет обеспечить хорошее использование сетевых ресурсов, и велика вероятность возникновения тупиковых состояний даже при локальных перегрузках сети.
Второй способ характеризуется тем, что в случае отказа принятия пакета на соседнем УКk из-за отсутствия свободной памяти,
возникновения ошибки или по каким-либо другим причинам на
УКi, откуда передается пакет на УКk, обеспечивается выбор другой
ветви bir, вместо ветви bik для повторной передачи этого пакета с
УКi. Если и с УКr поступит отказ в принятии пакета, то в третий
10
раз осуществляется передача пакета по ветви bie (e ≠ k; e ≠ r) и т. д.,
пока не будут перебраны все исходящие ветви, доступные для передачи пакетов с УКi к узлу назначения УКj. После этого начинается
второй цикл выбора ветвей. В этом случае элементы mjk, матрицы
маршрутов Mi = || mjk || для УКj принимают целочисленные значения, т. е. mjk ∈ {1,2, … ki}, ki ≤ ni. Они определяют порядок выбора
направлений при передаче пакетов с УКi к УКj.
Данный способ аналогичен методу поиска исходящих направлений в сети коммутации каналов с обходными путями (методу
рельефа), заметно улучшает использование связных ресурсов, существенно уменьшает вероятность возникновения тупикового состояния в сети и время передачи пакетов по сети.
Третий способ (метод отклонений) производит рассеяние каждого из потоков пакетов по направлениям, что позволяет обеспечить минимальную задержку в передаче пакета.
План распределения пакетов задается стохастической матрицей
вида Mi = УКj || mjk ||, где 0 ≤ mjk ≤ 1 и
ni
å mjk = 1.
k=1
При доказательстве оптимальности распределения потоков по
сети пакетной коммутации обычно допускается следующее:
− в модели сети коммутации пакетов, имеющей N узлов коммутации и Ti ветвей, отходящих от каждого узла коммутации, предполагается, что ветвь состоит из одного канала, все каналы сети надежны и УК также надежны;
− пропускная способность канала (ветви) C (пакетов/с) постоянна;
− время обработки пакетов в УК – К (с);
− время распространения сигнала Pk (бита информации) по каналу bk зависит от длины канала lk, т. е. Pk = lk / V, где V – скорость
распространения сигнала по каналам;
− поступающие на УKi пакеты, предназначенные для передачи
на другие УКj, образуют пуассоновский поток пакетов. Его интенсивность обозначена lij пакетов/с;
− пакеты в сети не теряются и не возникают новые, т. е. служебные пакеты не рассматриваются. Объем потока пакетов, поступающего в УКi (и покидающего его) в единицу времени обоTi
значаем l i = å l ij , а общий объем поступающего в сеть потока
N
L=å
Ti
j=1
å lij ;
i=1 j=1
11
− длины всех пакетов независимы и распределены по экспоненциальному закону со средним значением 1/m (бит), где m – интенсивность обслуживания пакета;
− емкость памяти на УК принимается неограниченной.
Отношение li/m характеризует нагрузку ri. Ее называют коэффициентом использования, ri = li / m.
По какой-либо ветви blk может проходить весь пакет или некоlk = Qlk l , или rlk = Qlk r , где Qlk – коэфторая его часть lij, т. е. lij
ij ij
ij
ij ij
ij
фициент рассеяния потока lij, который определяет долю потока,
приходящегося на ветвь blk при передаче потока пакетов от УКi к
УКj, причем 0 ≤ Qlkij ≤ 1. При этом по одной и той же ветви blk могут
проходить различные потоки в частичном или полном объеме. Тогда общий поток, поступающий на ветвь, l lk =
N
å lijlk
i,j=1
При этих допущениях среднее время задержки передачи пакета
по сети
Tñð = (1 / L)
æ l lk / m
ö÷
çç
lk
÷
+
l
T
å çç C - llk / m
lk ÷÷, è
ø÷
l,k=1;l¹k lk
N
(1)
где L – интенсивность суммарного потока пакетов; ll,k – интенсивность отдельного потока на пути УКl – УКk; m – среднее значение
длины передаваемого пакета; C l,k – пропускная способность канала
связи между узлами коммутации УКl – УКk; T l,k – время задержки
передачи (время обработки плюс время распространения) между
узлами коммутации УКl и УКk.
Задача оптимального распределения потока пакетов по сети соlk, при которых будет минимальным
стоит в нахождении величин Qij
среднее время задержки передачи пакета в сети Тср. Для этого может быть использован эффективный итерационный метод – метод
девиации (отклонения) потока.
Пример. Пусть задана ориентированная сеть (рис. 5).
Пусть УК3 находится в космосе на спутнике Земли, а остальные УК – на поверхности Земли. В сеть поступает два потока l14 =
= 2 пакета/с; l32 = 1 пакет/с. Длины пакетов распределены по экспоненте со средним значением, равным 1, т. е. m = 1. Во всех вариантах заданий пропускная способность линий связи Сi,j(i = 1 – 4;
j = 1 – 4) принята равной 3.
12
λ 3,2
УК3
λ 1,3
λ 3,2
λ 2,3
λ 3,4
λ 2,4
λ 1,4
УК1
λ 2,1
УК2
λ 1,4
УК4
λ 4,2
λ 3,2
Рис. 5. Коммуникационная сеть
Во всех вариантах заданий время распространения между наземными узлами коммутации УК1 – УК2; УК2 – УК1; УК2 – УК4;
УК4 – УК 2 плюс время обработки в узлах коммутации принято равным 0.
Во всех вариантах заданий время распространения между узлами коммутации УК1 – УК3; УК3 – УК1; УК2 – УК3; УК3 – УК2;
УК3 – УК4; УК4 – УК3 плюс время обработки в узлах коммутации
принято равным 0,5 c.
Таким образом, матрица требований (Ф) задана в виде
ÓÊ1
ÓÊ2
Ô=
ÓÊ3
ÓÊ4
ÓÊ1 ÓÊ2 ÓÊ3 ÓÊ4
– – – 2
– – – –
– 1 – –
– – – –
.
Матрица емкостей ветвей в виде матрицы пропускной способности Ck,l, (пакеты/с), будет
ÓÊ1
ÓÊ2
Ñk,l =
ÓÊ3
ÓÊ4
ÓÊ1 ÓÊ2 ÓÊ3 ÓÊ4
3
–
–
–
3
3
3
–
–
3
–
3
–
–
–
3
.
13
Время задержки передачи (время обработки плюс время распространения) T представим в виде матрицы
ÓÊ1
ÓÊ2
T=
ÓÊ3
ÓÊ4
ÓÊ1 ÓÊ2 ÓÊ3 ÓÊ4
–
0 0,5 –
0
– 0,5 0
– 0,5 – 0,5
–
– –
0
.
Временем обработки на наземных УК и временем распространения сигналов между наземными УК пренебрегаем.
Метод отклонения потоков позволяет получить минимальное
среднее время задержки пакета в сети и требует достаточно большого объема вычислений. Поэтому для больших сетей, особенно
если требуется перераспределять потоки в изменяющихся условиях, целесообразно применять субоптимальные методы распределения потоков: последовательное или параллельное распределение
потоков некоммутируемой сети.
Рассмотрим один из них, а именно метод последовательного
приближения к оптимальному. Этот метод относится к классу итерационных методов и состоит в последовательном выполнении итераций и шагов итераций.
На нулевой итерации, состоящей из одного шага, производится
распределение потоков по кратчайшим путям, причем критерием
выбора кратчайшего пути является время задержки пакета в этом
пути.
Вначале находятся все пути Пe(j), по которым возможна передача каждого из потоков. Затем для каждого из этих путей Пe (j) с
учетом только первого потока по формуле (1) вычисляется среднее
время задержки ТсрПe(j) в предположении, что поток li,j передается
только по одному пути Пe(1). Из всех возможных путей выбирается
кратчайший, в котором время ТсрПe(1) минимально, и поток li,j направляется по этому пути.
Аналогично выбираются пути для передачи остальных потоков.
После того как все потоки распределены, по формуле (1) подсчитывается среднее время нулевой итерации Тср0. На этом выполнение
нулевой итерации заканчивается.
Замечание. Если на нулевой итерации не найдено ни одного
кратчайшего пути с ТсрПe(j) хотя бы для одного потока, то это означает, что реального плана распределения потоков только по кратчайшим путям без их рассеяния не существует. Поэтому в данном
14
случае происходит условное распределение потока по одному из
«перенасыщенных» путей, для которого
ТсрПe(j) = ∞.
На последующей итерации предполагается рассеяние потоков.
Рассмотрим пример, приведенный выше.
Нулевая итерация
Для этого построим «дерево» путей для имеющихся двух потоков l1,4 (рис. 6, а) и l3,2 (рис. 6, б)
Видно, что для потока l 1,4 имеются два пути П1,3,4 (1,4) и
П1,3,2,4 (1,4); а для потока l 3,2 – два пути П3,2(3,2) и П3,4,2 (3,2).
Найдем кратчайший из них по критерию минимальной задержки. По формуле (1) вычислим время задержки для каждого из путей, предполагая, что по сети передается только один из потоков и
только по одному пути. При этом получим
ТП1,3,4(1,4) = 3; ТП1,3,2,4(1,4) = 4;
ТП3,2 (3,2) = 1; ТП3,4,2(3,2) = 1,5.
Поясним приведенные расчеты Путь П1,3,4 для потока 1 – 4 состоит из двух звеньев 1 – 3 и 3 – 4. При этом общий объем потока L
равен 2 пакета/с. Тогда согласно выражению (1) имеем
Поток 1–4
Ò Ï1,3,4(1 - 4) =
æ
ö÷
,
1
3
1
l /m
l 3,4 / m
= ççç
+ l1,3T1,3 +
+ l 3,4T 3,4÷÷ =
÷
L èç C1,3 - l1,3 / m
C 3,4 - l 3,4 / m
ø÷
ö 1
1æ 2 /1
2 /1
= çç
+ 2 * 0,5 +
+ 2 * 0,5÷÷÷ = (2 + 1 + 2 + 1) = 3.
÷
ç
2è3-2 /1
3-2 /1
ø 2
Аналогично получаем и другие приведенные значения:
T Ï1,3,2,4(1 - 4) =
+l 3,2T 3,2 +
+
1
l1,3 / m
l 3,2 / m
+ l1,3T1,3 +
+
(
L C1,3 - l1,3 / m
C 3,2 - l 3,2 / m
1 2 /1
l 2,4 / m
+ l 2,4T 2,4) = (
+ 2 * 0,5 +
,
2
4
2 3-2 /1
C 2,4 - l / m
2 /1
2 /1
1
+ 2 * 0,5 +
+ 1 * 0) = (2 + 1 + 2 + 1 + 2) = 4.
3-2 /1
3-2 /1
2
15
а)
б)
3
4
4
1
3
2
3
4
2
2
Рис. 6. «Деревья» путей для передачи информации
Поток 3 – 2
Ò Ï3,2(3 - 2) =
ö÷ 1 æ 1
ö
1 æç
l 3,2
3.2
÷÷ = çç
çç
+
+ 1 * 0,5÷÷÷ = 1;
l
T
3
2
,
,
3
2
÷
ç
L èç C 3,2 - l / m
ø÷
ø÷ 1 è 3 -1 / 1
ö÷
1 æç
l 3,4 / m
l 4,2 / m
çç
+ l 3,4T 3,4 +
+ l 4,2T 4,2÷÷ =
÷
L èç C 3,4 - l 3,4 / m
C 4,2 - l 4,2 / m
ø÷
Ò Ï3,4,2(3 - 2) =
ö
1 æç 1 / 1
1/1
+ 1 * 0,5 +
+ 1 * 0÷÷÷ = 1,5
çç
÷ø
1 è 3 -1 / 1
3 -1 / 1
Таким образом, кратчайшим путем для потока l1,4 является
путь П1,3,4, а для потока l 3,2 – путь П3,2. Следовательно,
Q1,31,4 = Q3,41,4 = Q3,23,2 = 1,
а остальные коэффициенты рассеяния равны 0 (рис. 7).
Среднее время задержки при выполнении нулевой итерации c
учетом того, что суммарная интенсивность потока обоих пакетов
L = 3 пакетов/с, будет
Ò ñð0 =
+
1 æç l1,3 / m
l 3,4 / m
çç
+ l1,3T1,3 +
+ l 3,4T 3,4 +
L èç C1,3 - l1,3 / m
C 3,4 - l 3,4 / m
ö÷ 1 æ 2 / 1
2 /1
l 3,2 / m
+ l 3,2T 3,2÷÷ = çç
+ 2 * 0,5 +
+
,
3
2
÷
ç
÷ø 3 è 3 - 2 / 1
3-2 /1
C 3,2 - l / m
+2 * 0,5 +
а)
1
1
3
1
ö
1/1
+ 1 * 0,5÷÷÷ = 2,33
÷ø
3 -1 / 1
б)
4
4
0
0
3
0
2
0
4
3
1
0
2
2
Рис. 7. Распределение потоков при передаче информации
только по кратчайшим путям
16
Первая итерация. Шаг 1
Производится рассеяние потока l1,4 на УК3. Пусть шаг рассеяния D = 0,1. Тогда
Q1,31,4 = 1; Q3,41,4 = 0,9; Q3,21,4 = 0,1.
Остальные коэффициенты рассеяния не изменяются, т. е.
Q2,41,4 = Q3,23,2 = 1 (рис. 8).
С учетом этих коэффициентов получим:
l1,31,4 = 2; l3,41,4 = 1,8; l3,21,4 = 0,2; l2,4 1,4 = 0,2; l3,23,2 = 1.
По формуле (1) среднее время задержки шага 1 первой итерации
Ò ñð1,1 =
+
+
1 æç l1,3 / m
l 3,4 / m
çç
+ l1,3T1,3 +
+ l 3,4T 3,4 +
L çè C1,3 - l1,3 / m
C 3,4 - l 3,4 / m
l 3,2 / m
l 2,4 / m
3,2
+
+
+ l 2,4T 2,4 +
l
T
3
,
2
C 3,2 - l 3,2 / m
C 2,4 - l 2,4 / m
ö÷ 1 æ 2 / 1
1,8 / 1
l 3,2 / m
+ l 3,2T 3,2÷÷ = çç
+ 2 * 0,5 +
+
3
2
,
÷
ç
÷
3
3
2
/
1
3
1,8 / 1
è
/
m
C 3,2 l
ø
+1,8 * 0,5 +
0,2 / 1
0,2 / 1
+ 0,2 * 0,5 +
+ 0,2 * 0 +
3 - 0,2 / 1
3 - 0,2 / 1
ö
1/1
+
+ 1 * 0,5÷÷÷ = 2,21.
3 -1 / 1
ø÷
Итак, Тср1,1 = 2,21. Так как Тср1,1 < Тср0, данное рассеяние принимается.
Шаг 2
Рассеиваем поток l1,4 на транзитном УК3, принимая
Q1,31,4 = 1; Q3,41,4 = 0,8; Q3,21,4 = 0,2; Q2,41,4 = 1,
оставляя остальные коэффициенты рассеяния без изменения (рис. 9).
а)
1
1
б)
0,9
3
4
0,1
2
1
4
3
1
2
Рис. 8. Распределение потоков на 1-м шаге
17
При этом l1,31,4 = 2; l3,41,4 = 1,6; l3,21,4 = 0,4; l2,4 1,4 = 0,4;
l3,23,2 = 1. Тогда Тср1,2 = 2,14. Так как Тср1,2< Тср1,1, данное рассеяние принимается.
Шаг 3
Рассеиваем поток l1,4 на транзитном УК3, принимая
Q1,31,4 = 1; Q3,41,4 = 0,7; Q3,21,4 = 0,3; Q2,41,4 = 1,
оставляя остальные коэффициенты рассеяния без изменения
(рис. 10).
При этом l1,31,4 = 2; l3,41,4 = 1,4; l3,21,4 = 0,6; l2,4 1,4 = 0,6;
3,2
l 3,2 = 1. Тогда Тср1,3 = 2,12. Так как Тср1,3< Тср1,2, данное рассеяние принимается.
Шаг 4
Рассеиваем поток l1,4 на транзитном УК3, принимая
Q1,31,4 = 1; Q3,41,4 = 0,6; Q3,21,4 = 0,4; Q2,41,4 = 1,
оставляя остальные коэффициенты рассеяния без изменения
(рис. 11).
а)
1
0,8
3
1
б)
4
0,2
2
1
3
4
1
2
Рис. 9. Распределение потоков на 2-м шаге
а)
1
3
1
0,7
0,3
б)
4
2
1
3
4
1
2
Рис. 10. Распределение потоков на 3-м шаге
а)
1
1
3
0,6
0,4
б)
4
2
1
4
3
1
Рис. 11. Распределение потоков на 4-м шаге
18
2
При этом l1,31,4 = 2; l3,41,4 = 1,2; l3,21,4 = 0,8; l2,4 1,4 = 0,8;
l3,23,2 = 1. Тогда Тср1,4 = 2,062. Так как Тср1,4< Тср1,3, данное рассеяние принимается.
Шаг 5
Рассеиваем поток l1,4 на транзитном УК3, принимая
Q1,31,4 = 1; Q3,41,4 = 0,5; Q3,21,4 = 0,5; Q2,41,4 = 1,
оставляя остальные результаты коэффициентов рассеяния без изменения (рис. 12).
При этом l1,31,4 = 2; l3,41,4 = 1; l3,21,4 = 1; l2,4 1,4 = 1: l3,23,2 = 1.
Тогда Тср1,5 = 2,16. Так как Тср1,5 > Тср1,4, данное рассеяние не
принимается.
Далее рассеивать поток λ 1,4 на транзитном узле УК3 не целесообразно, и в дальнейшем поток l 1,4 на УК3 рассеиваться не будет,
т. е. после шага 4 «дерево» путей для потока λ 1,4 не меняется (см.
рис. 11).
Шаг 6
Произведем рассеивание потока l 3,2 на два потока (рис. 13)
При этом Q1,31,4 = 1; Q3,41,4 = 0,6; Q3,21,4 = 0,4; Q2,41,4 = 1,
Q3,4 3,2 = 0,1; Q4,2 3,2 = 1; Q3,2 3,2 = 0,9. Тогда Тср1,6 = 2,053. Так как
Тср1,6 < Тср1,4, то данное рассеяние потока l3,2 принимается.
Шаг 7
Произведем дальнейшее рассеивание потока l 3,2 на два потока
(рис. 14).
а)
1
0,5
3
б)
4
0,5
1
1
2
1
3
4
2
Рис. 12. Распределение потоков на 5-м шаге
а)
б)
1
1
3
0,4
0,6
4
2
0,1
1
4
3
0,9
4
1
2
2
Рис. 13. Распределение потоков на 6-м шаге
19
а)
3
1
1
0,6
0,4
б)
4
2
0,2
1
4
0,8
3
4
1
2
2
Рис. 14. Распределение потоков на 7-м шаге
При этом Q1,31,4 = 1; Q3,41,4 = 0,6; Q3,21,4 = 0,4; Q2,41,4 = 1,
Q3,4 3,2 = 0,2; Q4,2 3,2 = 1; Q3,2 3,2 = 0,8. Тогда Тср1,7 = 2,381. Так
как Тср1,7 > Тср1,6, то данное рассеяние потока l3,2 не принимается. Возвращаемся к распределению потоков на шаге 6.
При этом Q1,31,4 = 1; Q3,41,4 = 0,б; Q3,21,4 = 0, 4; Q2,41,4 = 1;
Q3,2 3,2 = 0,9;. Q3,1 3,2 = 0,1; Q1,2 3,2 = 1. Тогда Тср1,6 = 2,053.
Окончательное распределение потоков показано на рис. 15.
λ 3,2 = 1
λ 3,2 =1
УК3
3,4
λ 1,4 =1,2
3,2
λ 3,2 =0,9
1,3
3,4
λ 3,2 =0,1
3,2
λ 1,4 =2
λ 1,4 =0,8
2,4
λ 1,4 =0,8
УК1
λ1,4 =2
УК2
4,2
λ 3,2 =0,1
λ
УК41,4
λ 1,4 =2
Рис. 15. Окончательное субоптимальное распределение потоков
20
Варианты заданий
№
варианта
Интенсивность
потоков
1-го
2-го
От 1-го
1
l1,4 = 2 l3,2 = 1
1–>2
2
l4,1 = 2 l2,3 = 1
1–>3
3
l1,4 = 2 l2,3 = 1
1–>3
4
5
6
7
l4,1 = 2
l1,4 = 2
l4,1 = 2
l1,4 = 2
8
l4,1 = 2 l3,2 = 1
–
9
10
l1,4 = 2 l3,2 = 1
l4,1 = 2 l2,3 = 1
1–>3
–
11
l1,4 = 1 l3,2 = 2
1–>2
12
l4,1 = 1 l2,3 = 2
1–>3
13
l1,4 = 1 l2,3 = 2
1–>3
14
15
16
17
l4,1 = 1
l1,4 = 1
l4,1 = 1
l1,4 = 1
18
l4,1 = 1 l3,2 = 2
–
19
20
l1,4 = 1 l3,2 = 2
l4,1 = 1 l2,3 = 2
1–>3
–
l3,2 = 1
1–>2
l3,2 = 1 1–>2; 1–>3
l2,3 = 1 1–>2; 1–>3
l2,3 = 1
1–>3
l3,2 = 2
1–>2
l3,2 = 2 1–>2; 1–>3
l2,3 = 2 1–>2; 1–>3
l2,3 = 2
1–>3
Линии связи
от узлов
От 2-го
От 3-го
3–>1; 3–>2;
2–>3; 2–>4
3–>4
3–>1; 3–>2;
2–>1; 2–>3
3–>4
2–>1; 2–>3;
3–>2; 3
2–>4
2–>3; 2–>4 3–>1; 3–>2
2–>1; 2–>3 3–>1; 3–>4
2–>1; 2–>3 3–>1; 3–>4
2–>1; 2–>4 3–>2; 3–>4
3–>1; 3–>2;
2–>1; 2–>3
3–>4
2–>1; 2–>4 3–>2; 3–>4
2–>3; 2–>4
3–>1
3–>1; 3–>2;
2–>3; 2–>4
3–>4
3–>1; 3–>2;
2–>1; 2–>3
3–>4
2–>1; 2–>3;
3–>2; 3
2–>4
2–>3; 2–>4 3–>1; 3–>2
2–>1; 2–>3 3–>1; 3–>4
2–>1; 2–>3 3–>1; 3–>4
2–>1; 2–>4 3–>2; 3–>4
3–>1; 3–>2;
2–>1; 2–>3
3–>4
2–>1; 2–>4 3–>2; 3–>4
2–>3; 2–>4
3–>1
От 4-го
–
4–>2
–
4–>2; 4–>3
4–>2
4–>2
4–>3
4–>3
4–>2
4–>2; 4–>3
–
4–>2
–
4–>2; 4–>3
4–>2
4–>2
4–>3
4–>3
4–>2
4–>2; 4–>3
21
Контрольные вопросы
1. В чем заключается суть метода отклонений потока?
2. Что достигается в результате оптимального распределения
потока?
3. Чем субоптимальное распределение потока отличается от оптимального?
4. Чем обусловлено применение субоптимального метода распределения потока?
5. Как задается матрица требований?
6. Как строится матрица пропускных способностей путей передачи информации?
7. Как строится матрица временных задержек путей передачи
информации?
Библиографический список
1. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы,
технологии, протоколы. СПб.: Питер, 2006. 672 с.
2. Лазарев В. Г. Интеллектуальные цифровые сети: Справочник/ Под ред. Н. А. Кузнецова. М.: Финансы и статистика,
1996.224 с.
22
СОДЕРЖАНИЕ
Введение....................................................................................... 3
Учебно-исследовательская лабораторная работа № 1. Метод рельефов... 4
Теоретические пояснения................................................................ 4
Содержание отчета......................................................................... 9
Варианты заданий.......................................................................... 9
Учебно-исследовательская лабораторная работа № 2. Метод отклонений..............................................................................................10
Теоретические пояснения................................................................10
Варианты заданий..........................................................................21
Контрольные вопросы.....................................................................22
Библиографический список ............................................................22
23
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 088 Кб
Теги
0d51c151e4, krylov
1/--страниц
Пожаловаться на содержимое документа