Алгоритмы телекоммуникационных сетей. Часть 1. Алгоритмы и протоколы каналов и сетей передачи данных

Алгоритмы и протоколы каналов и сетей передачи
данных

2-е издание, исправленное

Семенов Ю.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 004.738.2(07)
ББК 12
С30
Алгоритмы телекоммуникационных сетей. Часть 1. Алгоритмы и протоколы каналов и сетей
передачи данных / Семенов Ю.А. - M.: Национальный Открытый Университет “ИНТУИТ”, 2016
(Основы информационных технологий)
ISBN 978-5-94774-706-5

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Семенов Ю.А., 2007-2016

3

Предисловие

Этот курс является переработкой книги “Протоколы Интернет. Энциклопедия”. Часть
материала была удалена как устаревшая или малосущественная. Одновременно было
существенно расширено содержимое некоторых разделов, добавлены описания новых
алгоритмов и протоколов, появившихся после 2001 года и не вошедших по разным
причинам в предыдущую книгу. В этот перечень вошли протоколы MPLS и MPLS-TE,
RSVP-TE, GMPLS, P2P, TFRC, DCCP, LDP, ICQ, SIP, FEC, IEEE 802.16, 802.17,
Bluetooth, Wi-Fi, MPEG-21, IPSec и др. В период с 2000 по 2006 годы темп появления
новых регламентирующих документов RFC не спадал и составлял ~270-350 в год. Эти
документы в основном касались мультимедиа, качества обслуживания, мобильных
сетей, сетевой безопасности и диагностики, а также новых сетевых сервисов.

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

Человечество все в большей степени становится зависимым от сетей и ЭВМ, в
заметной мере от этих технологий начинает зависеть даже жизнь человека.
Генетические коды, истории болезней, страховые полисы и пр. хранятся в машинах и
передаются по сети. По этой причине безопасность и надежность машин и сетей
начинает выходить на первое место.

За год создается более 10000 разновидностей только сетевых червей. Число различных
разновидностей атак, предпринимаемых хакерами, перевалило за 2500 и продолжает
расти. В среднем каждая машина подвергается атакам 20-40 раз в сутки. Появились
принципиально новые виды сетевых атак типа spyware и bot. Сейчас стало опасно
посещать незнакомые web-сайты, даже если вы ничего оттуда не копируете.

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

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

Новым в телекоммуникациях является также широкое внедрение технологии peer-to-
peer (P2P) для целей файлового обмена и телевидения. Эта технология является
альтернативой схемы “клиент-сервер”.

В связи с широким внедрением IP-телефонии и предстоящим развитием IP-
телевидения все больше внимания уделяется средствам обеспечения гарантированного
качества обслуживания.

Ожидается широкое внедрение сетевых технологий в человеческое жилище —
локальные сети высокого быстродействия в московских домах становятся обыденной
реальностью. Локальные сети появляются в автомобилях и других транспортных

4

средствах.

5

Введение в новейшие телекоммуникационные технологии

Введение в новейшие телекоммуникационные технологии. Каналы данных как
продолжение органов чувств человека. Алгоритмы модуляции и кодирования при
передаче данных, теорема Шеннона, природа шумов, шум дискретизации.

Базовые алгоритмы телекоммуникаций

Почему мы поступаем так, а не иначе? Почему именно так сложились обстоятельства?
Что в развитии событий было случайным, а что — закономерным? Над этими
вопросами мы бьемся достаточно часто.

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

1.1. Предыстория

Создатель снабдил людей неплохими системами коммуникаций. Это прежде всего
органы зрения, слуха и голосовой аппарат. Наиболее важные из них продублированы -
мы имеем два уха и два глаза, что создает предпосылки стереовосприятия и
пространственной локации источника звука или оптического объекта. Определенную
информацию об окружающей среде мы получаем от органов вкуса, обоняния и
осязания. Эти информационные каналы весьма важны для сохранения жизни, но с
точки зрения потоков данных они достаточно узкополосны. Самым широкополосным
нашим каналом является визуальный. В оптической области люди могут воспринимать
волны с длиной волны от 400 до 700 нм, и это в принципе может обеспечить потоки
данных масштаба ~60 Тбит/c. Проблема в том, что человек способен воспринимать
<<10 Мбит/с, обрабатывая данные лишь частично (речь идет о восприятии
движущегося изображения). В акустическом диапазоне наши уши чувствительны для
частот от 20 Гц до 20 КГц. Наш акустический канал принципиально асимметричен.
Передачу данных мы осуществляем голосом (полоса 600 Гц – 6 КГц), а восприятие -
слухом, который имеет более чем в два раза большую полосу пропускания. Уместен
вопрос: зачем Природа или Создатель сформировали столь асимметричный канал? Не
признать рациональность такого решения нельзя - хотя бы с точки зрения
безопасности. Ведь в реальной жизни через уши мы получаем данные о шорохе
листвы, по которой к нам подползает змея, или о подлетающем комаре. Частотные
диапазоны таких шумов находятся вне области воспроизведения нашим голосом. Это
же касается раскатов грома или звука выстрела. Отсюда следует, что мудр тот, кто
больше слушает, чем говорит, - так он способствует накоплению информации в своей
памяти.

Огромен динамический диапазон воспринимаемых нами звуков - более 1:20000. К
счастью, имеющийся у нас аппарат преобразования звука в нервный (электрический)

6

сигнал является нелинейным. В противном случае при близком грозовом разряде или
выстреле мы могли бы погибнуть от шока - из-за слишком большого импульса
возбуждения. Устройство преобразования звука у человека имеет логарифмическую
характеристику и спасает нашу нервную систему от перегрузок. Это позволяет нам и
воспринимать шорох листвы, и выживать, когда сосед слушает тяжелый рок при 300
Вт звуковой мощности или пытается завести свой мотоцикл на балконе. Частотный
диапазон восприятия у нас настроен так, чтобы воспринимать жизненно важные
звуковые сигналы. Наш голосовой аппарат способен воспроизводить самые
разнообразные звуки, что позволило человечеству сформировать языковую систему
коммуникации. Человеческий голос состоит из гласных и согласных звуков. Гласные
звуки генерируются, когда голосовой тракт открыт, и определяются резонансом,
основная частота которого зависит от размера и формы голосовой системы, от
положения языка и челюстей говорящего. Эти звуки для интервалов порядка 30 мс
являются почти периодическими. Согласные звуки формируются, когда голосовой
тракт частично перекрыт, эти звуки менее регулярные по сравнению с гласными.
Некоторые современные системы генерации и передачи голоса используют модели
голосовой системы с ограниченным числом параметров (например, размер и форма
различных полостей), а не простое стробирование формы голосового сигнала. Вполне
возможно, что успешное использование звуков для сигнальных целей в свою очередь
стимулировало развитие гибкости голосового аппарата

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

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

Наконец был создан символьный язык для описания не только объектов реального
мира, но и абстрактных понятий. Достаточно вспомнить скрижали, которые Бог
передал Моисею. Об этом говорится в Ветхом завете, и было это задолго до Рождества
Христова. Но сами эти камни с письменами предполагали, что народ или хотя бы
священнослужители были способны прочесть то, что на них написано. Письменность
предполагает соглашение между пишущим и будущими читателями относительно
значения графических символов.

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

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

7

Устные знания ненадежны, легко искажаются. Впрочем, это было свойственно и
первым письменным источникам - ведь первые книги переписывались вручную. В
качестве носителя использовались специально обработанные шкуры животных -
пергамент или прототип бумаги - папирусы (древнейшие египетские папирусы
относятся к XXV веку до нашей эры) и, наконец, во втором веке нашей эры - бумага
(Китай). В начале XI века в Китае начали печатать книги с использованием подвижных
литер, выполненных из глины или дерева. В XIV веке в Корее стали применяться для
печати подвижные металлические литеры (чем не прототип пишущей машинки?).
Практически с самого начала в рукописях и “полиграфии” использовалось несколько
цветов.

Сначала записанная информация имела вид свитков. Позднее они стали объединяться,
и такие блоки листов стали называться кодексами. Известные древнейшие библиотеки
относятся ко 2-3-му тысячелетиям до нашей эры, и создавались они героическими
усилиями переписчиков. Переписчик часто заботливо “исправлял” непонятные ему
места, внося неизбежные субъективные искажения. Иногда такие искажения вводились
сознательно в угоду политическим, идеологическим или религиозным воззрениям.

Книгопечатание в Европе появилось сравнительно недавно - в середине XV века в
Германии благодаря усилиям Гуттенберга (литеры из глины). Каменные скрижали
были долговечны, но неудобны для переноса и изготовления. Люди, правда, научились
писать на глиняных пластинках, которые потом обжигались на солнце, но и это не
решало проблемы. Надписям на камне мы обязаны своим знаниям о самых древних
периодах человеческой цивилизации. Бумага и пергаменты хорошо горят (и гниют),
что послужило причиной потери многих ценных манускриптов. Пожары же
преследовали человечество с самого начала, с момента освоения технологии обогрева и
приготовления пищи на очаге. До нашего времени дожили лишь небольшие фрагменты
некоторых древних библиотек (вспомним хотя бы судьбы Александрийской
библиотеки или библиотеки Ивана Грозного). Бумажные книги существуют уже более
800 лет. И только в конце XX века благодаря развитию вычислительной техники у них
появился конкурент - CD-диски (с объемом данных 600-750 Мбайт, и это не предел).
На данной странице около 3,5 килобайт информации. Один CD-диск может содержать
тексты нескольких книг. Объемная плотность информации в CD превосходит книжную
в десятки раз. В принципе технология CD может обеспечить длительность хранения на
уровне многих сотен, а может быть, и тысяч лет.

Наш голосовой канал прежде всего предназначен для общения с себе подобными.
Часть предыдущей фразы до запятой содержит 19 букв (в кодовом представлении - 19
байт). Обычно она произносится примерно за одну секунду, что создает поток данных
в 152 бит/с. Хорошо тренированный оператор за полторы-две секунды может
напечатать эту часть фразы.

Отсюда видно, что наши собственные возможности передачи данных, сопряженные с
движениями пальцев рук или языка, весьма ограничены и не превышают (100-150) бит/
с.

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

8

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

Нашу нервную систему вполне можно рассматривать как локальную сеть, внешние же
коммуникации человека могут служить аналогом Интернета. По внутренним нервным
магистралям распространяются сигналы от различных рецепторов, сообщая данные о
состоянии окружающей среды и самого организма; аналогично, но в противоположном
направлении передаются управляющие сигналы. Обратные связи являются основой
жизни и способом адаптации к окружающей среде. Я не являюсь тонким знатоком
физиологии человека, но тем не менее позволю себе предположить, что в нашей
нервной системе используются как “проводные” соединения, так и адресная система
доставки сообщений. Мне трудно представить, например, чтобы тактильные и
температурные датчики транспортировали в мозг сигналы по разным каналам - такое
решение представляется неэффективным, хотя вполне может оказаться, что я
ошибаюсь. Для построения систем, непосредственно контактирующих с органами
чувств человека, крайне важно точно знать параметры внутренних каналов передачи
сигналов. Такие данные помогут корректно спроектировать интерфейсы,
оптимизировать и заметно удешевить технические решения.

Наш визуальный канал принято справедливо считать быстродействующим.
Быстродействие тем не менее здесь не столь велико, как это можно предположить. Во-
первых, его ограничивает инерциальность датчиков в глазу, которая характеризуется
постоянной времени ~0,04 с (вспомним частоту кадров в кино). Второй
ограничивающий фактор - скорость обработки и распознавания образов в головном
мозге. Оценить эту составляющую быстродействия сложнее. Попытаемся все же это
сделать. За сколько секунд вы можете прочесть эту страницу? Это у вас занимает 1-1,5
минуты? Тренированные люди способны читать до 1000 слов в минуту. Будем считать
среднюю длину слова равной 8 букв, тогда получим скорость восприятия 135 байт/c.

Таким образом, максимальная скорость обработки текстовых данных составит <150
байт/с. Всего в 10 раз быстрее, чем при восприятии на слух!

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

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

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

9

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

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

Если попытаться проанализировать полезность или эффективность получаемой
информации (ее изучает ветвь семиотики, называемая прагматикой), то результат
будет во многих случаях довольно печальным. При разговоре мы часто повторяем одни
и те же фразы, мысли и факты, произносим огромное число слов-паразитов. Я уже не
говорю о пустой болтовне по телефону, уведомляющей собеседника о количестве
выпитого накануне или о покрое юбки жены соседа. Люди по какой-то причине не
могут без этого. Нам приходится слушать речи высоких политиков или читать статьи
или книги, смысл которых ничтожен, а содержащаяся в них информация может быть
охарактеризована несколькими битами, уведомляющими слушателя или читателя об
амбициях автора. Многоточие в конце романа классика во много раз информативнее.
Трудно представить, чтобы ЭВМ Центра управления полетами, прежде чем передать
управляющую информацию бортовой машине, перешлет ей сначала анекдот,
найденный только что в Интернете. Впрочем, это относится скорее к области
информатики, чем телекоммуникаций. Хотя, от умения компактно передавать наиболее
существенные данные зависит эффективная работа информационных систем будущего.

Здесь мы прикасаемся к проблеме издержек, которые связаны с заголовками пакетов
данных, пересылаемых по сетям. Так, при удаленном доступе (протоколы Telnet, SSh и
пр.) на один переданный байт, характеризующий нажатую клавишу терминала,
приходится более 50 байт заголовков и другой вспомогательной информации.

Эффективность удаленного ввода с консоли, как видите, меньше КПД паровоза. Но
современные телекоммуникационные технологии пока не могут предложить ничего
лучшего.

Способность передачи определенных данных посредством мимики и поз роднит

10