Структура сети и коммутация пакетов.

Логическая и программная структура сети.

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

Таблица 1

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

 

 

Рис.3 Логическая структура сети.

 

Проектирование сетей ЭВМ.

Теория проектирования сетей ЭВМ базируется на аппарате систем массового обслуживания(СМО).

Обозначим n-e требование, поступающее в СМО через

- момент поступления требования

- время между соседними требованиями и .

- среднее время между соседними требованиями

- среднее время обслуживания.

Для обозначения различных типов СМО используется обозначение, которое имеет вид A/B/m. Так обозначается СМО с m обслуживающими приборами, а A и B указывают соответственно на распределение времени между соседними требованиями и распределение времени обслуживания. А и В принимают значение из следующего набора символов:

M – показательное распределение (Markovian), - распределение Эрланга порядка r.

- гиперпоказательное распределение порядка r, D- постоянная величина(Deterministic),

G – произвольное распределение (General).

Наиболее важным параметром СМО G/G/1 является коэффициент использования

,

где - плотность входного потока (средняя скорость поступления требований в систему),

- плотность потока обслуживания.

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

Для многолинейной СМО G/G/m

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

В общем случае - математическое ожидание доли используемой пропускной способности системы. В любой стабильной системе

Случай не допускается. Чем ближе к 1, тем больше очереди и время ожидания.

Среднее время пребывания требования в системе:

- среднее время ожидания в очереди.

Среднее число требований в очереди:

- формула Литтла.

Соответствующий результат для числа требований в очереди:

- средняя длина очереди.

Для системы G/G/m справедливо:

(следует из формулы Литтла).

(1)

Для системы M/M/1 вероятность того, что в системе находится k требований равна

;

Отсюда среднее число требований в системе:

,

а дисперсия равна:

.

Используя формулу Литтла и (1) при m=1 получим две основные характеристики М/M/1 – ее средние характеристики:

 

;

 

(2)

Величины , , растут по мере убывания (1- ). При средние задержки и длины очередей растут неограниченно.

Пусть сеть с коммутацией сообщений имеет М каналов и N узлов. Каналы – бесшумные и абсолютно надежные. Пропускная способность i-го канала равна (бит в секунду). Поток, поступающий в сеть из внешних источников(например, из машины HOST)образует Пуассоновский процесс со средним значением (сообщений в секунду) для тех сообщений, которые возникают в узле j и предназначены для узла k.

Полный внешний поток, поступающий в сеть, равен:

.

Длины всех сообщений по предположению независимы и распределены по экспоненциальному закону со средним значением 1/ (бит) (пока не учитывается возможная пакетная структура сообщений).

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

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

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

Как и для внешнего потока, определим полный поток в сети:

.

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

Пусть - стоимость всей сети (по предположению состоит лишь из стоимости каналов):

.

Выше была определена задержка сообщения как такое время, которое сообщение проводит в сети.

Средняя задержка сообщения в сети - главная характеристика сети.

[задержка сообщения]

Обозначим

[задержка сообщения, которое возникло в j и имеет место назначения k].

Ясно, что

(3)

 

так как доля полного входящего потока имеет в среднем задержку, равную .

Последнее равенство представляет разложение сети по параметрам источник – адресат.

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

1. выбор пропускной способности каналов { };

2. выбор потоков в каналах { };

3. выбор топологии.

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

Определим 4 задачи, которые отличаются только множеством переменных, варьируемых при проектировании. В каждой из этих задач считается, что заданы положения узлов, внешний поток , стоимость каналов , постоянные D и , а так же предполагается, что используемые потоки { } являются реализуемыми (то есть они согласуются с пропускной способностью и ограничениями на внешний поток, а также удовлетворяют закону сохранения).Первая задача – это выбор пропускных способностей (ВПС).

 

 

Задача ВПС.

Дано:	потоки { } и топология сети.
Минимизировать:	.
Варьируются:	{ }.
Ограничение:	.

 

Вторая задача – распределение потоков(РП).

 

Задача РП

Дано:	Пропускные способности { } и топология сети.
Минимизировать:	.
Варьируются:	{ }.

 

Третья задача – задача выбора пропускных способностей и распределения потоков(ВПС и РП).

Задача ВПС и РП.

Дано:	топология сети.
Минимизировать:	.
Варьируются:	{ }и { }.
Ограничение:	.

 

 

Четвертая задача – задача выбора топологии, пропускных способностей и распределения потоков (ВТ, ПС и РП)

Задача ВТ, ПС и РП.

Минимизировать:	.
Варьируются:	топология, { }и { }.
Ограничение:	.

 

Эти 4 задачи в настоящее время решены с различной степенью полноты.

 

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

 

(4)

 

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

[время, затраченное на ожидание и процесс передачи по i-му каналу],

то есть - среднее время, проведенное сообщением в системе, где под системой понимается i-ый канал:

 

(5)

Отсюда из (3) получаем:

 

(6)

Изменим порядок суммирования, тогда как обычно при изменении порядка суммирования условие на i становится условием на j,k. В результате имеем:

 

 

Используя соотношение (4), получаем:

 

(7)

Теперь средняя задержка сообщения разложена на компоненты, относящиеся к отдельным каналам, то есть разложена по .

 

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

выбирается его новая длина .

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

Пользуясь этим предположением, получим, что i-ый канал теперь можно рассматривать как систему М/М/1 с пуассоновским потоком интенсивности на входе и показательным временем обслуживания со средним 1/ секунд. Решение сразу же получаем из (2).

.

 

 

И поэтому, согласно (5), имеем[1]:

(8)

Анализ (4) показывает, что при увеличении нагрузки на сеть никакое слагаемое в выражении (4) не будет доминировать, пока поток в одном из каналов (например, в ) не достигнет пропускной способности этого канала по соответствующему узкому месту сети.

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

 

Это пороговое поведение задержки показано(упрощено) на рис.9

 

 

 

определяется как задержка в отсутствии нагрузки (незагруженная сеть).

Из (4) при и получим:

.

- нагрузка насыщения, при которой .

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

.

Рассмотрим полный поток в сети . Отметим, что вклад потока j-k в полный поток равен , так как сообщений пройдут участков при движении по сети.

 

Следовательно:

Если - длина сообщения, то оно занимает канал на время плюс время передачи по каналу(скорость света). Таким образом и - это среднее время обслуживания сообщения каналом.

в (2) - это здесь, так как и то, и другое – это среднее время обслуживания.

 

.

Из последних двух равенств получаем известный общий результат:

.

Отсюда .

Это дает метод вычисления задержки в отсутствии нагрузки для упрощенной пороговой модели.

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

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

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

Любая совокупность ребер, при устранении которой из сети прерывается весь поток от источника s к адресату t, называется сечением s-t.

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

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

 

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

1. Дайте определение коэффициента использования?

2. Чему равно среднее время пребывания для системы M/M/1? Какая величина называется стоимостью сети?

3. Дайте определение средней задержки в сети. Приведите итоговую формулу.

4. Сформулируйте задачи ВПС, РП, ВПС и РП.

5. Чему равна средняя задержка в канале?

6. Чему равна средняя длина пути в сети?

7. Чему равно среднее время ожидания в очереди для системы M/M/1?

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

 

Лекция 4.

 

Выбор топологии сети.

 

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

5-10% от оптимума (в конце концов, редко можно угадать с большей точностью, так что с технической точки зрения это вполне удовлетворительно).Решение задачи представляет собой итеративную форму решения ВПС и РП. Оно использует тот факт, что каналы могут быть устранены (то есть будут внесены топологические изменения) по мере выполнения алгоритмов ВПС и РП. Так как является вогнутой по потокам { } функцией, то этот алгоритм называется вогнутым методом устранения ребер (ВМУР).

 

ПОДОПТИМАЛЬНЫЙ АЛГОРИТМ ВМУР.

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

2. Для каждого канала провести степенную или линейную аппроксимацию.

3. Выполнить алгоритм ВПС И РП. Если при какой-либо итерации нарушается ограничение связности(например, двусвязности – больше и равное двум число путей между узлами), то прекратить оптимизацию и перейти к шагу 4.

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

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

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

7. Повторить шаги 1-6 для ряда начальных топологий.

 

Опыт показывает, что к хорошим результатам приводят от 20-30 повторений в шаге 6 и несколько (5-7) исходных топологий (их которых одна полносвязная, а другие – сильносвязные сети) в шаге 7.

Эти методы представляют современное состояние проектирования подсети связи сетей ЭВМ.

 

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

1.Приведите подоптимпльный алгоритм ВПС И РП.

2. Сформулируйте задачу ВПС и РП в двойственной форме с решением.

3. Приведите алгоритм ВМУР.

4. В чем заключается метод отыскания потока?

5. Приведите алгоритм отыскания потоков, идущих по кратчайшим путям.

6. Приведите оптимальный алгоритм ОП для выбора маршрутов.

7. В чем заключается подоптимальный метод ОП?

8. Приведите алгоритм ОП для фиксированной процедуры выбора маршрута.

Лекция № 6

Адресация, маршрутизация пакетов и управление потоками данных.

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

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

Иерархическое кодирование – способ построения имен (адресов) путем присоединения к локальным именам имен систем, которым принадлежит объект. Имя (адрес) имеет следующий вид: A, B, …, Q, R, где А – имя системы, В – имя подсистемы системы А, R – имя объекта в подсистеме Q, входящей в ранее указанную подсистему. По такому способу строится почтовая адресация: имя страны, имя города, улицы, дома и т.д.

Распределение адресов – состоит в присвоении постоянных имен (адресов) лишь отдельным процессам, которым выдают разрешение на доступ к системе, выделяя для доступа временные адреса. Пусть, например, системе А выделены адреса с 0001 до 0999, а системе В – с 1000 до 1999. Для доступа к этим системам выделяются постоянные адреса, например, 0001 для системы А и 1000 для системы В. Когда в системе А инициируется процесс Х, ему присваивается общесетевой адрес, например, 0125. Процесс из системы А обратится к процессу с локальным именем Y в системе В по адресу 1000. Система В с помощью процесса 1000 выделяет процессу Y временный адрес, например, 1021 (общесетевой). По окончании взаимодействия эти адреса становятся свободными.

Отображение адресов – присвоение любому объекту общесетевого адреса. Адреса преобразуются (отображаются) любой системой в локальные имена. Например, обращаясь по сетевому адресу 1256, преобразуется в локальное имя Y адресуемого объекта.

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

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

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

В существующих сетях используются разнообразные способы адресации. В настоящее время отсутствуют подробные стандарты на способы адресации абонентов СПД и процессов и их портов, связанных с СПД транспортно-сеансовыми службами систем.

 

Маршрутизация пакетов.

Используются следующие основные способы маршрутизации:

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

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

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

 

Управление потоками.

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

Управление потоком в сети – ограничение входного потока в сеть с целью недопущения перегрузки.

Протокол Х.25/3.

Уровень 3 Рекомендации Х.25 МККТТ (Х.25/3) определяет виртуально-датаграмную сеть: «формат пакета и процедуры управления для обмена пакетами, содержащими информацию управления и данные пользователя». Он описывает требования, предъявляемые к двум элементам программной структуры сети: управление передачей и управление сетью. Х.25 однозначно определяет сетевой уровень.

В вычислительной сети одновременно создается много логических каналов. Х.25 описывает создание как временных (на один сеанс), так и постоянных логических каналов. Чаще всего постоянные соединения используются для связи хост-машин, а временные – для взаимодействия терминалов с большим числом хост-машин. Временное соединение в протоколе Х.25 называется виртуальным вызовом, а постоянное – виртуальной цепью. Любому виртуальному вызову либо виртуальной цепи присваивается номер группы логических каналов (от 0 до 15) или номер логического канала (от 0 до 255). Виртуальный вызов связан с проведением одного сеанса связи. Поэтому указанные номера приписываются любому сеансу связи и изменяются циклически. Виртуальная цепь существует постоянно. Поэтому номер этой цепи относится ко всем проводимым через нее сеансам связи.

Стек протоколов TCP/IP.

(Transmit Control Protocol/ Internet Protocol)

TCP/IP – это промышленный стандарт стека протоколов, разработанный для глобальных сетей. Стандарты TCP/IP опубликованы в серии документов, названных Reguest For Comment (RFC). Документы RFC описывают внутреннюю структуру сети Internet. Стек был разработан для ARPANET до появления модели взаимодействия открытых систем ISO/OSI. Он также имеет многоуровневую структуру, но соответствие между TCP/IP и OSI достаточно условно. Протоколы TCP/IP делятся на 4 уровня

 

	www Gopher WAIS	SNMP	FTP	telnet	SMTP	TFTP	I

Прикладной

уровень

	www Gopher WAIS	TCP	UDP	II

Транспорт-ный

уровень

 

 

IP

ICMP

RIP

OSPF

ARP

III

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

 

	Не регламентируется в стеке TCP/IP, Но поддерживает все популярные стандарты Enternet, Token Ring, FDDI, X.25, PPP, SLIP? FrameRelay, ATM	IV

Уровень доступа к сети

 

Уровни Рис. 22 Уровни модели OSI и стека протоколов TCP/IP

 

Формат IP-заголовка.

 

	4 бита	4 бита	1 байт	16 бит
	Версия	Длина заголовка	Тип обслуживания	Длина дейтаграммы
	16 бит Идентификатор сообщения	1б	1бит DF	1бит MF	13 бит Смещение фрагмента
	8 бит Время жизни	8 бит Протокол	16 бит CRC Заголовок
	32 р IP-адрес отправителя
	32 р IP-адрес получателя
	Опции (произвольно)	Заполнитель
Рис.23. Формат заголовка пакета протокола IP.

 

- версия - номер версии IP (IP v4, IP v6) – 4 бита.

- длина заголовка – в 32-х разрядных словах (5 или 6 слов).

- тип обслуживания – это поле имеет следующую структуру:

 

3 бита	1 бит	1 бит	1бит	2 бита
приоритет	задержка	пропускная способность	надежность	не используется

 

Приоритет- от 0 до 7 (0-обычный, 7 – управление).

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

- длина дейтаграммы – полная длина включая заголовок (max-65535 байт).

- идентификатор – идентификатор сообщения. Исключает сборку фрагментов разных сообщений.

- DF – не фрагментировать (Don’t Fragment). (1-фрагментация запрещена).

- MF- More Fragments- есть еще фрагменты. (1-есть еще фрагмент, 0- фрагмент последний).

- Смещение фрагмента- смещение в битах фрагмента относительно начала сообщения.

- Время жизни- время в секундах отводимое на доставку пакета. Если время доставки пакета> пакет delete, Каждый узел уменьшает время жизни на 1с и учитывается время ожидания в шлюзах. Если время жизни становится меньше нуля, то пакет уничтожается и высылается квитанция обратной связи.

- Протокол – код транспортного протокола (для TCP код = 6).

- CRC- контрольная последовательность. (Вычисляется со временем жизни т.е. изменяется)

- Опции – могут отсутствовать; секретность, запись маршрута (в дополнительных полях), маршрутизация отправителям, запись временных меток и т.п.

- Заполнитель – требуется для дополнения заголовка до целого числа 32 разрядных слов.

Протокол ТСР.

Главная функция ТСР- доставка сообщения без потерь. Для этого предварительно устанавливается соединение между приложением-отправителем и приложением-получателем. Именно ТСР производит повторную передачу искаженного или утерянного пакета.

ТСР получает поток байтов от приложения и собирает в сегменты, добавляя заголовки в начало сегментов. В заголовке – CRC и порядковый номер сегмента.