Выбор наикратчайшего пути в сети по методу Дейкстры

ОСНОВЫ IP-ТЕЛЕФОНИИ

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

для студентов всех форм обучения специальностей
5В071900 - Радиотехника, электроника и телекоммуникации

Алматы 2013

СОСТАВИТЕЛИ: К. С. Чежимбаева, Ш. А. Мирзакулова. Основы IP-телефонии. Методические указания к расчетно-графическим работам для студентов всех форм обучения специальностей 5В071900 - Радиотехника, электроника и телекоммуникации.- Алматы: АУЭС, 2013. - 17 с.

Изложены расчетно-графические работы по дисциплине «Основы IP-телефонии». В них представлены задачи по сжатию двоичной последовательности методом кодирования длин повторений и выбору наикратчайшего пути в сети IP методом Дейкстры.

Ил. - 14, табл. - 1, библиогр.- 7 назв.

Рецензент: канд. техн. наук, проф. К.Х. Туманбаева

Печатается вне плана издания некоммерческого акционерного

общества «Алматинский институт энергетики и связи» на 2013 г.

© НАО «Алматинский университет энергетики и связи», 2013 г.

Содержание

Расчетно-графическая работа №1

Сжатие методом кодирования длин повторений

1.1.1 Задание работы:

- используя исходные данные изображения, приведенные в приложении А нужно закодировать двоичное (двухцветное) изображение размером 8х8 элементов. При этом пустая клетка обозначает белый цвет, а клетка в которой проставлена буква "Ч" обозначает черный цвет;

- выбор варианта заданий осуществляется по списку журнала преподавателя;

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

1.1.2 Описать процедуру установления связи между пунктами сети IP-телефонии. Варианты описаны в приложении Б.

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

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

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

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

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8х8 элементов, приведенное на рисунке 1.1. После сканирования этого изображения по строкам получим двоичный вектор данных Х [1].

Х=(0111000011110000000100000001000000010000000111100011110111101111) длиной 64 бит (скорость исходного кода составляет 1 бит на элемент изображения).

Рисунок 1.1 - Двуцветное изображение

Выделим в векторе Х участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков - положительных целых чисел, соответствующих исходному вектору данных Х - будут иметь вид r=(1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4). В этой последовательности заметна определенная повторяемость, которые можно закодировать каким-либо статическим кодом (таблица 1.1).

Таблица 1.1 - Кодер

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

В результате получим кодовое слово:

B(r)=(0101110011010110101101011001110100100)

длиной в 34 бита, то есть результирующая скорость кода R составит 37/64, или немногим более 0,5 бита на элемент изображения. При сжатии изображений большего размера и содержащих множество повторяющихся элементов эффективность сжатия может оказаться существенной.

Расчетно-графическая работа №2

Выбор наикратчайшего пути в сети по методу Дейкстры

2.1.1 Выбор варианта:

- исходные данные для топологии сети IP, представленной на рисунке 2.1 приведены в приложении В;

Рисунок 2.1 - Исходная топология сети

- выбор варианта заданий осуществляется по списку журнала преподавателя:

- определить наикратчайшие пути в сети IP между маршрутизаторами методом Дейкстры;

- описать работу сетевых протоколов. Варианты представлены в приложении Г.

2.1.2 Методические указания к выполнению работы. Алгоритм Дейкстры - это алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

При этом в этом алгоритме каждой вершине графа, где установлен маршрутизатор сопоставим метку - минимально известное расстояние от одной вершины до другой. Алгоритм работает пошагово - на каждом шаге он посещает одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершины посещены.

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

Кружками на графе обозначены вершины, линиями - пути между вершинами. В кружках обозначены номера вершин.

Рисунок 2.2 - Граф сети

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

Рисунок 2.3 - Нулевой этап

Нулевой этап фиксируется только с целью указать конечный узел с вершиной "1", метка которого равна нулю.

Минимальную метку имеет вершина 1. Ее соседями являются вершины 2 и 3 (рисунок 2.4).

Рисунок 2.4 - Первый шаг

Первый по очереди сосед вершины 1- вершина 2, так как путь до нее минимален (5). При этом длина пути равна сумме кратчайшего расстояния до вершины 1, то есть 0+5=5. Это значение меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-1 вершины равна 5 (рисунок 2.5).

Рисунок 2.5 - Новая метка первой вершины

Продолжим аналогичные операции с вершиной 3 (рисунок 2.6)

Рисунок 2.6 - Новая метка третьей вершины

Все соседи вершины 1 проверены. Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена (рисунок 2.7).

Рисунок 2.7 - Новая метка третьей вершины

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

Рисунок 2.8 - Посещение вершины 2

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через вторую вершину. Соседями вершины 2 являются 3 и 4. Первый по очереди сосед вершины 2- вершина 1, но она уже посещена, поэтому с первой вершиной ничего не делаем. Следующий сосед это вершина 3, так как она имеет минимальную метку из вершин (8), отмеченных как непосещенные. Если идти в нее через вершину 2, то длина такого пути будет равна 16 (5+11). Но текущая метка 3 вершины равна 8<16, поэтому метка не меняется.

Рисунок 2.9 - Посещение вершины 2 (метка не меняется)

Еще один сосед вершины 2 это вершина 4. Путь до нее через вершину 2 составит 14. Так как 14< , устанавливаем метку вершины 4 равной 14 (рисунок 2.10).

Рисунок 2.10 - Посещение вершины 4

Все соседи вершины 2 проверены. Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена (рисунок 2.11).

Рисунок 2.11 - Отметка вершины 2 как помеченной

Повторяем аналогично выбрав вершину 3 (рисунок 3.12). В результате обработки она будет вычеркнута.

Рисунок 2.12 - Отметка вершины 3 как помеченной

Повторяем для оставшейся вершины 4 (рисунок 2.13).

Рисунок 2.13 - Отметка вершины 4 как помеченной

Завершение выполнения алгоритма происходит тогда, когда все вершины вычеркнуты. В результате получили кратчайшие пути от вершины 1 до 2 составляет 5, до 3 составляет 8 и 4 составляет 14.

Перечень сокращений

ПК – персональный компьютер

СТОП – сеть телефонная общего пользования

ARP (Address Resolution Protocol) - протокол разрешения адресов

DHCP (Dynamic Host Configuration Protocol) – протокол динамической конфигурации хоста

DNS (Domain Name System) - система доменных имен

FTP (File Transfer Protocol) - протокол обмена файлами

H.323 - стек протоколов для передачи аудио- и видеоинформации по сети

HDLC - высокоуровневый протокол управления каналом

HTTP - протокол передачи гипертекста

ICMP - протоколмежсетевых управляющих сообщений

IGMP - протокол управления группами Internet

IRC - протокол общения пользователей

ISUP (ISDN User Part) – пользователь ISDN

IP (Internet Protocol) - межсетевой протокол

MGCP (Media Gateway Control Protocol) - протокол управления шлюзами

MPLS - многопротокольная коммутация по меткам

SSH – безопасная оболочка

RMON - расширение SNMP

RTCP (RTP Control Protocol) - протокол, использующийся совместно с RTP.

RTP (Real-Time Transport Protocol) - протокол для передачи данных реального времени

RIP (Routing Information Protocol) - протокол маршрутизации

RTSP - потоковый протокол передачи реального времени

RSVP - протокол резервирования ресурсов

OSPF - выбор кратчайшего пути

SCTP - новый транспортный протокол

SIP (Session Initiation Protocol) - протокол инициирования сессий

SNMP - простой протокол управления сетью

SMTP - простой протокол передачи электронной почты

TCP (Transmission Control Protocol) - протокол управления передачей

UDP (User Datagram Protocol) - протокол пользовательских датаграмм

VoIP - голос поверх IP

Список литературы

1. Шульгин В. И. Основы теории передачи информации. Ч. 1. Экономное кодирование. Учебное пособие. - Харьков: Нац. аэрокосм. ун-т "Харьк.авиац.ин-т, 2003. – 102с.

2. Гольдштейн А.Б. IP – телефония.-М.,2001

3. Гольдштейн Б.С., Пинчук А.В., Суховицкий А.Л. IP-телефония. – М., Радио и связь.2001.

4. Росляков А.В. IP – телефония.-М.,2001,2003.

5. Гольдштейн Б.С., Пинчук А.В., Суховицкий А.Л. ІР-Телефония. – М.: Радио и связь, 2001. – 336с.

6. Романчева Н.И. Современные Интернет-технологии: Учебное пособие. - М.: МГТУ ГА, 2007. –104 с.

7. Электронный источник – www.sipnet.ru

Приложение А Исходные данные к заданию РГР№1.1

Продолжение приложения А

Продолжение приложения А

Приложение Б Задание к РГР№1.2

Приложение В Задание к РГР№2.1