Стислий конспект лекцій з дисципліни "Телекомунікаційні та інформаційні мережі" (тім) (програма бакалаврського мінімуму) Лектор доц. В.І. Тіхонов
| Вид материала | Конспект |
- Конспект лекцій Суми Видавництво Сумду 2010, 2423.29kb.
- Конспект лекцій з дисципліни "Інформаційні системи та технології у фінансових установах", 1112.81kb.
- Назва модуля: Інформаційні системи в менеджменті Код модуля, 40.82kb.
- Робоча навчальна програма з дисципліни «Політичні комунікації» Укладач: к філол н.,, 310.09kb.
- Конспект лекцій з дисципліни „Радіоекологія для студентів спеціальності 040106 „Екологія,, 1393.76kb.
- Виконавці, 499.61kb.
- Конспект лекцій по дисципліні Інформаційні моделі "великих" систем, 1986.92kb.
- Дисципліна «Финанси» Довідник з дисципліни Для спеціальностей 0104, 0105, 0106, 0100, 539.85kb.
- Робоча навчальна програма дисциплiни " планування та проектування інформаційних систем", 115.77kb.
- Конспект лекцій Удвох частинах Частина 1 Суми, 2323.63kb.
Недостаточная надёжность протокола может выражаться как в потере отдельных пакетов, так и в их дублировании. UDP используется при передаче ссылка скрыта, ссылка скрыта, а также некоторых других типов данных. Если приложению требуется большая надёжность, то используется протокол ссылка скрыта или ссылка скрыта.
Использование: UDP используется в следующих протоколах: ссылка скрыта ссылка скрыта ссылка скрыта
^ 4.11. Режим виртуального вызова, виртуального канала, виртуального
соединения. Их достоинства и недостатки.
Исторически основным способом установления связи в сетях была коммутация телефонных каналов (т.е. установление сквозного соединения между двумя или более точками сети на время сеанса связи и обмен информацией в реальном времени; как правило, это соединение является логическим, а не физическим). С появлением Интернет возник новый способ связи – передача пакетных сообщений. Простейший вариант связи для сетей IP заложен уже на сетевом уровне стека протоколов TCP/IP (вариант сетевого протокола IPv4).
Общая схема построения блоков пересылки информации по сетям IP такова: информационное сообщение или его часть (блок данных для обмена, запрос либо ответ) с помощью драйвера транспортного уровня дополняется слева подзаголовком транспортного уровня образуя сегмент; далее на сетевом уровне этот сегмент дополняется слева с помощью драйвера сетевого уровня подзаголовком сетевого уровня, образуя датаграмму либо пакет (в зависимости от того, вставляется ли подзаголовок транспортного уровня и какой); далее на канальном уровне датаграмма (либо пакет) с помощью драйвера канального уровня (т.е. драйвера сетевого контроллера) дополняется слева подзаголовком канального уровня, образуя кадр (или фрейм).
Отдельные фреймы при передаче по каналам связи отделяются друг от друга т.н. преамбулой (фиксированная зарезервированная последовательность битов – синхро-блок – или же в некоторых протоколах совокупность недопустимых для других частей кадра комбинации битов и недопустимых модуляций, например, символов J и K манчестерского кода). Заголовок канального уровня содержит адреса отправителя и получателя (в двухточечных протоколах это поле может отсутствовать). Далее в некоторых протоколах может использоваться поле длины кадра. Протоколы с кадрами фиксированной длины обходятся без этого поля. Далее в заголовке идут поля протокола LLC (Logical Link Control- управление логическим соединением). Этот протокол определяет верхний подуровень канального уровня в стандартах IEEE 802; нижний подуровень – это MAC (Media Access Control - управление доступом к среде). Далее в кадре следует тело – инкапсулированные в датаграмму или в пакет содержательные данные, которые в свою очередь тоже могут иметь сложную структуру. Заканчивается кадр контрольной суммой (для коротких кадров – это бит четности, а для длинных – CRC – Cyclic Redundancy Check – Проверка избыточным циклическим кодом). Обрамляется кадр маркером конца кадра, который, как и преамбула, в некоторых протоколах может содержать не только зарезервированные комбинации битов, но и запрещенные модуляции.
Формат заголовка пакета IP предусматривает следующие поля: 4 бита версии протокола (например, IPv4 в двоичном коде, 4 бита IHL (Internet Header Length) – длина заголовка в 32-битных словах; соответственно эта длина может принимать значения от 20 до 60 байт; 8 бит типа обслуживания, 2 байта – полная длина всего паета, 2 байтовый идентификатор датаграммы (т.е. всего пакета); битовые флаги DF (don’t fragment) и MF(more fragment- еще будут фрагменты далее) и 13-битовое смещение фрагмента, которое задает смещение в 3-х байтных блоках поля данных этого пакета относительно начала исходного пакета; один байт TTL (Time to live – оставшееся время жизни или количество узлов, которые может еще пройти пакет, чтобы не попасть в замкнутый цикл; обычно этот параметр устанавливают равным 32 или 256, и при каждом проходе очередного узла он уменьшается на единицу; как только он станет равным нулю, пакет уничтожается. Далее в заголовке имеется один байт идентификатора протокола транспортного уровня; контрольная сумма заголовка (2 байта); 4 байтовые IP адреса отправителя и получателя; дополнительные поля и выравнивание (4 байта).
В процессе передачи может понадобиться фрагментация пакета на меньшие части (т.к. не все транзитные каналы и узлы могут обрабатывать и пропускать пакеты одинаковой длины). С этой целью в заголовке каждого пакета или его фрагмента предусмотрен двухбайтовый идентификатор пакета. Все фрагменты одного пакета должны иметь одинаковый идентификатор пакета. Это позволяет восстанавливать исходный пакет по его удачно доставленным фрагментам и производить обмен простыми короткими сообщениями, что особенно эффективно, когда размер сообщения не превышает размера одного пакета. Для многих приложений такой обмен с негарантированной доставкой данных вполне приемлем. Этот вид связи (фактически без установления какого-либо специального соединения или канала) называют датаграммным.
Установление связи в сетях коммутации пакетов является прерогативой транспортного уровня. В данном случае, простейший датаграммный протокол является вырожденным (т.е. нет никакого специального транспортного протокола). В то же время, стек TCP/IP предлагает специальный датаграммный протокол, называемый UDP (User Datagram Protocol). Этот протокол добавляет к 20 байтовому заголовку пакета IP еще один 8 байтовый заголовок UDP. При этом общая длина пакета (2 байтный код в заголовке) учитывает не только сами данные пакета, но и эти оба заголовка, т.е. непосредственно для данных отводится 216 –1 - 20 – 8 = 65508 байт). Сам протокол IP способен гарантированно передать в одном пакете (без фрагментации) 576 байт. Канальный уровень каждого маршрутизатора в сети Интернет имеет свой собственный MTU (Maximum Transmission Unit – максимальный размер пакета, пропускаемого без фрагментации). Поэтому драйвер транспортного уровня источника сообщения должен знать этот параметр для каждого устанавливаемого соединения. Заголовок UDP содержит: порт отправителя и получателя (по 2 байта); длина датаграммы (2 байта); контрольная сумма (2 байта) по заголовку и псевдо-заголовку UDP.
Альтернативным видом сервиса транспортного уровня является установление логического соединение с гарантированной доставкой всего сообщения. Этот сервис связан с понятием виртуального канала или виртуального соединения (некоторые авторы разделяют эти понятия на два). Главное назначение его – передача информации без искажений и потерь. Для этого в стеке протоколов TCP/IP для сетей X.25 имеется специальный протокол транспортного уровня TCP (стандартизован RFC 793)*.
Протокол TCP действует между прикладными процессами и протоколом IP. Он добавляет к данным свой заголовок, образуя сегмент обмена. Байтовые потоки, поступающие на транспортный уровень от прикладных процессов, образуют очереди. Эти очереди с точками входа называют портами прикладных процессов. Порт вместе с номером сети и номером узла определяет прикладной процесс в сети. Этот набор параметров имеет название «розетка» (socket). Распределением портов для прикладных процессов занимается организация IANA (Internet Assigned Numbers Authority). Например, порты 25 и 110 закреплены за службой электронной почты (протоколы SMTP и POP3 – Post Office Protocol v.3 – протокол аутентификации с передачей пароля открытым текстом); порт 23 закреплен за службой удаленного доступа telnet. Протокол TCP осуществляет поддержку двух очередей данных для каждого порта: очереди от сети и очереди от прикладных процессов. Обслуживание запросов от прикладных процессов называют мультиплексированием данных, а обратную процедуру распределения поступивших от сети данных между прикладными процессами – демультиплексированием данных. Порт для протокола TCP играет роль адреса. Процессы установления соединения, как правило, асимметричны: один из участников постоянно находится в состоянии готовности приема запроса (сервер). Другой включается и отправляет запрос в произвольное время (клиент). Для того чтобы участники соединения могли обмениваться сообщениями, разбитыми на отдельные пакеты, нужно эти пакеты последовательно нумеровать; это позволит осуществить сборку пакетов в единое сообщение на приемном конце. Но каждый из участников соединения осуществляет свою собственную независимую нумерацию пакетов; при этом важно, чтобы оба участника в процессе установления виртуального соединения заранее договорились и сообщили друг другу, какие начальные номера пакетов у каждого из них в данном виртуальном соединении. Клиент сперва должен сообщить свой начальный номер, затем получить ответ от сервера с подтверждением этого номера и сообщением о начальном номере нумерации у сервера; наконец, клиент должен снова отправить подтверждение серверу, что он правильно понял его стартовый номер пакетной нумерации. Эти номер кодируются 32 битами в полях заголовка TCP сегмента.
TCP заголовок содержит от 20 до 60 байт: порты отправителя и получателя по 2 байта каждому; собственный номер (4 байта); подтверждаемый номер (4 байта); смещение в 32-разрядных словах (4 бита); определяет общую длину заголовка от 20 байт до 15 х 32\8 =60 байт. Шесть контрольных бит, в частности 5-й бит =1 означает SYN – запрос на установление логического соединения. шестой бит =1 означает FIN – запрос на закрытие соединения. Размер окна (поле длиной 16 бит): получатель указывает в этом поле количество байт или пакетов, которые он способен принять (до 216 ); если в этом поле появляется ноль, то передача прекращается. Отправитель в этом поле указывает количество байт или пакетов, которые он может передать без подтверждения. Это связано с размерами буферов памяти у каждой из сторон. Наличие этого поля позволяет реализовать процедуру «скользящего окна». По мере получения подтверждений окно перемещается далее. Контрольная сумма (16 бит) для заголовка, включая и т.н. псевдо-заголовок (IP адреса источника и приемника, идентификатор транспортного протокола, длина IP пакета (т.е. эти данные дублируют часть заголовка самого пакета для повышения надежности).
Процесс установления соединения в упрощенном виде определяется как «тройное рукопожатие» (three-way handshake):
- клиент (прикладной процесс - инициатор вязи) передает запрос на сервер и сообщает начальный номер своего первого пакета данных;
- сервер, получив запрос, отправляет подтверждение (в т.ч. о номере клиента), а также сообщает начальный номер своего первого пакета данных;
- клиент передает подтверждение номера сервера.
Соединение между конкретными портами прикладных процессов двух IP компьютеров считается установленным. Отметим, что виртуальный канал, вообще говоря, определяет однонаправленную схему приема-передачи содержательной информации от источника к приемнику.
Как уже отмечалось выше, существует еще один практически важный тип сервиса транспортного уровня – передача данных реального времени. Несмотря на определенное сходство с виртуальными каналами, это совершенно отдельный вид сервиса и далеко не все транспортные протоколы его предоставляют. Его называют иногда виртуальным соединением. Приложения реального времени не требуют обязательной доставки всех пакетов и допускают потерю и искажение некоторой их части. Для них критичной является нарушение порядка прибытия пакетов и постоянство скорости передачи. Поэтому запрос повторов и отправка потерянных пакетов здесь просто недопустима. Такой сервис не может быть полноценно обеспечен средствами одного только транспортного уровня и накладывает определенные требования на сетевой и канальный уровни стека протоколов, а именно – предоставление средств резервирования пропускной способности.
Существует еще одно близкое понятие – виртуальный путь или тракт (virtual path). Так, например, в ячейках ATM (после установления виртуального соединения) в адресной части заголовка вместо адреса получателя записывается двухуровневый идентификатор – VPI (Virtual Path Identifier- 8 или 12 бит) и VCI (Virtual Channel Identifier – 16 бит). В то же время, на этапе установления виртуального соединения по сигнальному протоколу Q.2931 (сообщения этого протокола передаются по резервированному виртуальному каналу 5); при этом используются 20 байтовые адреса AESA (ATM End System Address). Маршрутизаторы ATM при этом называются уже коммутаторами, а таблицы маршрутизации тоже содержат адреса AESA.
Дальнейшим развитием идеи иерархической структуризации виртуальных каналов и построения сложных виртуальных соединений стала технология MPLS (Multi Protocol Label Switching – многопротокольная коммутация меток). Виртуальное соединение здесь может иметь более двух уровней и именуется LSP (Label Switch Path – путь коммутации меток). Каждый уровень такой иерархии определяет некий класс маршрутизационной эквивалентности (Forwarding Equivalence Class – FEC) Как правило, коммутация меток реализуется не во всей сети, а в отдельной группе подсетей (доменах коммутации меток), чаще всего магистральных. Снабжение пакета меткой очередного уровня иерархии является формой инкапсуляции пакета, а сам процесс прохождения пакета через домен может считаться туннелированием. В каждом домене маршрутизация осуществляется пол метке верхнего уровня иерархии. При выходе из этого домена метка снимается. Входной маршрутизатор очередного домена может снова набросить новую метку (ввести пакет в новый туннель) или же продвигать его по указанному идентификатору тоннеля. На выходе последнего маршрутизатора снимается последняя метка пакета. Эта технология сегодня является наиболее перспективной для построения магистральной инфраструктуры Интернет.
^ 5. Модельное представление сетей как объектов анализа и синтеза
5.1. Топология сети: табличные и графовые формы
Графовые модели сети и их характеристики
Ориентированные и неориентированные графы
^ Отношения смежности и инцидентности элементов графа
Дискретные графовые модели (заданные алгебраически в виде таблиц,
списков и т.п.)
Все задачи, возникающие при построении и эксплуатации инфокоммуникационных сетей можно разделить на два класса: задачи синтеза и задачи анализа. «Синтез» в переводе с греческого означает «соединение, составление». Задача синтеза сети возникает как при построении новой сети, так и при реконструкции и развитии существующих сетей. Эта задача носит технико-экономический характер, так как чаще всего отыскивается решение, оптимальное по ряду экономических показателей, например, по минимуму капиталовложений. При синтезе сети обычно считается заданным расположение пунктов сети. Конфигурация (топология) же линий связи может меняться при оптимизации экономических показателей. Это позволяет использовать затраты на линии связи в качестве целевого критерия оптимального синтеза сети. На конфигурацию линий могут быть наложены ограничения в виде исключения отдельных географических трасс при организации связи между пунктами, например, если они пересекают водные или горные преграды. К частным задачам синтеза можно отнести задачи выбора оптимальной топологии сети, выбор оптимального количества и места расположения узлов коммутации и т. д.
^ Задачи анализа актуальны для существующей, то есть уже синтезированной сети.
К ним относятся задачи нахождения оптимальных путей передачи информационных сообщений, определения совокупности путей заданной транзитности, оценки пропускной способности сети, вероятности установления соединения между пунктами и т. д. В классе задач анализа рассматриваются также вопросы расчета характеристик и параметров как сети в целом, так и отдельных ее элементов. К таким характеристикам относят качество обслуживания на сети, параметры надежности и живучести. Для того чтобы решить конкретную задачу синтеза или анализа телекоммуникационной сети, ее необходимо формализовать, т. е. записать в виде схемы: что дано, что необходимо определить и при каких ограничениях. Формализацию можно выполнить в словесной форме (такая форма называется вербальной моделью задачи) либо в виде математической модели, описывающей задачу в терминах той или иной теории (например, теории графов, теории оптимальных решений и т. п.)
Осуществление формализации требует не только понимания стоящей проблемы, но и выбора соответствующей модели самого объекта (сети связи). Модельное (упрощенное) представление объекта синтеза или анализа позволяет выявить и отразить наиболее существенные, с точки зрения стоящей проблемы, элементы объекта и связи между ними, не отвлекаясь на детали. Для модельного представления сетей связи наиболее часто используются графовые модели. На основе модели объекта и ее параметров (количества пунктов и линий сети, расстояний между пунктами, пропускной способности узлов и линий сети, стоимостных параметров и т. п.) можно построить математическую модель, отражающую зависимость между искомыми параметрами и независимыми переменными задачи в виде математических функций. В задачах синтеза и анализа сетей связи чаще всего используются математические модели оптимизации, где цель решения задачи записывается в виде так называемой целевой функции, для которой необходимо отыскать экстремум (минимум или максимум). На входящие в нее параметры могут накладываться ограничения, указывающие, в каких пределах могут изменяться значения искомых параметров.
О п р е д е л е н и е. Задачи, в которых отыскивается экстремум (минимум либо максимум) некоторой целевой функции, отражающей критерий оптимальности решения задачи, называются экстремальными.
Характерной особенностью экстремальных задач синтеза и анализа телекоммуникационных сетей является их большая размерность. Формулировка этих задач в терминах графовых и сетевых моделей позволила получить ряд эффективных, с точки зрения преодоления вычислительной сложности, методов и алгоритмов их решения, ориентированных на применение ЭВМ. Ряд таких алгоритмов рассмотрено ниже.
Под алгоритмом понимается процедура, обеспечивающая получение оптимального решения задачи, выполнение которой можно поручить ЭВМ. Различают алгоритмы точные и приближенные, так называемые эвристические.
Точные алгоритмы всегда гарантируют нахождение оптимального решения (глобального оптимума целевой функции). Например, алгоритм полного перебора всех возможных решений с выбором наилучшего среди них, является точным алгоритмом.
Однако точные алгоритмы, как правило, довольно трудоемки с вычислительной точки зрения. Поэтому на практике часто используют более простые алгоритмы, обеспечивающие быстрое получение решения с приемлемой для практики точностью. Такие алгоритмы строятся с использованием рациональных, с точки зрения логики человека, правил выполнения вычислений. Эти правила называются эвристиками и, как показывает практика, позволяют получить решение, близкое к оптимальному. Например, задача определения замкнутого контура наименьшей длины, обеспечивающего обход всех пунктов сети, может быть решена путем полного перебора всех возможных контуров с выбором среди них контура наименьшей длины, т. е. точным алгоритмом. Известно, что для сети, содержащей n пунктов, количество возможных контуров составляет порядка n!, получение которых для сети, размером n>30, представляет значительные трудности. Однако использование эвристики: "на каждом шаге движемся только к ближайшему пункту" обеспечивает получение приемлемого решения за время, необходимое для построения всего лишь одного контура.
Эвристические алгоритмы используются также в тех случаях, когда построить точный алгоритм не удается ввиду сложности математической модели задачи (ее нелинейности, дискретности и т. п.).
^ Модельное представление сети как объекта синтеза и анализа
Инфо-коммуникационная сеть как объект синтеза и анализа представляет собой совокупность пунктов сети и соединяющих их линий. В качестве математической модели такого объекта используют граф.
О п р е д е л е н и е. Графом называется некоторая совокупность точек и связывающих их стрелок.
Точки графа называются вершинами, а стрелки – дугами. Граф математически обозначается как G(N,V), где N - конечное множество вершин мощностью n, а V – конечное множество дуг мощностью m.
Вершины можно обозначить строчными буквами (i, j, k, l, s) либо цифрами (1, 2, 3, 4, 5), а дуги соответственно парами: {(i, j), (j, k), (k, l) ... } либо {(1,2), (2,3), (3,4), ... }, где первый индекс определяет начало, а второй – конец дуги (см.рис.5.1).
Рисунок 1. Графовая модель сети
Граф, в котором задается направление дуг, называется ориентированным, в противном случае – неориентированным. Неориентированные дуги называются ребрами. Между двумя вершинами, соединенными дугой (ребром), существует отношение смежности (для ориентированного графа вершины i и j смежны, лишь если дуга начинается в i и направлена в j). Между вершиной и соединенными с ней дугами (ребрами) существует отношение инцидентности.
Граф, каждой дуге (ребру) которого поставлены в соответствие некоторые числовые характеристики, называемые весами, представляет собой взвешенный граф. При необходимости веса могут быть приписаны также вершинам графа. Взвешенный граф принято называть сетью (в данном случае имеется в виду сетевая модель, а не сама сеть как объект). В качестве весовых характеристик сети могут выступать расстояния, пропускная способность, стоимость и т. д. Помимо геометрического изображения в виде точек и линий, граф может быть представлен в дискретной форме. Именно эта форма используется при вводе графовой модели в ЭВМ.
Одним из наиболее распространенных дискретных представлений графа является матрица смежностей. Это матрица А=[aij], размером (nn) элементов, которые могут принимать значения:
аij = 1, если в графе G существует дуга (ребро) между вершинами i и j;
аij = 0, - в противном случае.
Матрица смежностей графа, приведенного на рис. 5.2, имеет вид:
| A= | 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 |