Алгоритмы телекоммуникационных сетей. Часть 2. Протоколы и алгоритмы маршрутизации в INTERNET

Протоколы и алгоритмы маршрутизации в Интернет

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

Семенов Ю.А.

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

2

УДК [004.715+004.738.5.057.4](07)
ББК 12
С30
Алгоритмы телекоммуникационных сетей. Часть 2. Протоколы и алгоритмы маршрутизации в
INTERNET / Семенов Ю.А. - M.: Национальный Открытый Университет “ИНТУИТ”, 2016 (Основы
информационных технологий)
ISBN 978-5-94774-707-2

В курсе рассмотрены транспортные протоколы (IPv4, IPv6, UDP, TCP, DCCP, TFRC и др.),
протоколы работы с именами и адресами (ARP, DNS, DHCP, NAT и т.д.), базовые прикладные
протоколы HTTP, RTP/RTCP, а также алгоритмы и протоколы маршрутизации (RIP, OSPF, BGP,
LDP, PIM и др.). Описаны протоколы с коммутацией по меткам (MPLS и GMPLS).
Курс представляет собой справочник по протоколам и рассчитан на студентов, специализирующихся
в области передачи информации, специалистов, которые интересуются этими проблемами, а также на
широкий круг читателей, которые хотели бы в этом разобраться.

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

3

Введение в Интернет

История возникновения Интернет. Базовые принципы, позволившие Интернет
выиграть в конкурентной борьбе. Нормативные документы RFC. Стек протоколов
TCP/IP. Информационный обмен с и без установления соединения. Особенности IP-
протоколов версий 4 и 6. IP-туннели

В середине 60-годов в самый разгар холодной войны министерство обороны США
планировало создать сеть для управления, которая бы помогла выжить в условиях
ядерной войны. Стандартные телефонные сети считались недостаточно надежными,
так как выход из строя одного из центральных коммутаторов может парализовать
целый регион (телефонная сеть имеет древовидную топологию).

Для решения задачи было привлечено агентство ARPA (Advanced Research Project
Agency). Это агентство было создано в ответ на запуск в СССР в 1957 году
искусственного спутника земли. Агентство не имело своих лабораторий и ученых, и
его бюджет был незначительным (по масштабам Пентагона). ARPA решало проблемы,
выдавая гранты университетам и компаниям, чьи предложения оказывались
перспективными. Ими была исследована возможность построения сетей на основе
переключения пакетов. Затем была построена такая сеть, состоящая из субсетей и
отдельных ЭВМ. Субсети состояли из IMP (Interface Message Processor), построенных
на мини-ЭВМ, соединенных каналами передачи данных.

Уже на этом уровне предусматривалась динамическая маршрутизация пакетов – и
выход из строя отдельного узла или канала приводил к тому, что пакеты начинали
двигаться в обход поврежденного участка. Каждый узел состоял из IMP и ЭВМ,
соединенных коротким кабелем. ЭВМ могла послать IMP сообщение длиной 8063
бита. IMP разделял это сообщение на кадры длиной 1008 бит и пересылал их адресату.
Сеть работала по схеме “запомнить и переслать”, при которой пакет сначала
записывается целиком в буфер и только затем передается далее.

В 1968 году был организован тендер на создание экспериментальной сети. Тендер
выиграла компания BBN. Сеть была построена на базе мини-ЭВМ DDP-316 с памятью
12K 16-битных слов. Машины были соединены с помощью выделенных линий с
пропускной способностью 56 кбит/с. Программное обеспечение было создано в 1969
году силами студентов-выпускников местного университета. Программы базировались
на технологии сокетов 4.2BSD. Именно тогда окончательно сформировалась идеология
TCP/IP.

К 1983 году сеть ARPANET содержала уже более 200 узлов, а стек протоколов TCP/IP
приобрел официальный статус. Тогда же были введены в строй первые DNS (Domain
Name System) серверы.

В 1991 году конгресс США принял закон о создании сети NREN (National Research and
Education Network – национальная сеть для науки и образования) с каналами,
рассчитанными на скорость передачи в диапазоне гигабит/с. Таким образом, можно
считать, что Интернету более 30 лет, а первому официальному документу Интернет (
RFC ) — более 35.

4

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

Первый документ RFC (Request for Comments) регламентирующий стек протоколов
TCP/IP, увидел свет в апреле 1969 года. За первый год было подготовлено всего 27
RFC. Далее активность в этой сфере начала расти. Создавалось ядро протоколов. К
концу 1982 были созданы помимо IP, базовые почтовые протоколы RFC-82122, ARP и
TCP. В 1983 году оформился протокол DNS (Domain Name Service), который нужен
для преобразования имени сетевого объекта в IP-адрес. С этого момента открылась
возможность создавать сетевые приложения типа telnet (удаленный доступ) и FTP (File
Transfer Protocol). Темп подготовки документов RFC по годам отображен на рис. 1.1.

Рис. 1.1.  Число выпускавшихся документов RFC по годам

Из этого распределения видно, что к 1979 году окончательно сформировался стек
базовых протоколов и начался экстенсивный рост сети Интернет. По мере выявления
недостатков протоколов и новых потребностей после 1989 года началась активная
разработка новых направлений и приложений в Интернет. Это, прежде всего,
мультимедиа, базой для внедрения которой стали протоколы MIME и НТТP, системы
сетевой и информационной безопасности, мобильные услуги, IPv6, MPLS/GMPLS и
различные виды сервисов. Общий вид дерева протоколов показан на рис. 1.2.

5

Рис. 1.2.  Дерево протоколов

На данном рисунке отмечены, разумеется, не все протоколы и алгоритмы, но эта схема
отражает основные направления разработок. Анализируя перечень RFC за 2005 год,
можно сделать вывод, что проблема безопасности вышла на первое место, появились
первые документы по цифровому ТВ, мобильной связи и QoS (качество
обслуживания). “Дерево протоколов” до какой-то степени отражает
последовательность их разработки. Структура книги также следует этой схеме.
Документы, которые обретают статус стандарта, хранятся в специальном каталоге и
имеют расширения имени файла .std.

В сущности, современные сети, и Интернет в частности, базируются на достаточно
ограниченном списке идей:

1. пакетный принцип передачи данных и управления;
2. адаптация длины пакета к условиям передачи (фрагментация/дефрагментация);
3. инкапсуляция пакетов друг в друга;
4. динамическая маршрутизация.

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

Разработчики базовых принципов Интернет и не предполагали, что придет время — и
пользователи сети сами начнут разрабатывать средства для разрушения сети и
нападения на других (видно, такова уж природа человека).

По существу Интернет – это совокупность программ, взаимодействующих друг с
другом по определенным правилам. Правила взаимодействия определяются
протоколами (IP, UDP, TCP, DNS,…).

Привлекательность сети не только в том, что это единая среда общения людей,

6

находящихся в разных странах и на разных континентах. Телефония в принципе
предоставляла на первый взгляд аналогичные услуги. Но для связи по телефону вам
нужно знать номер телефона партнера. Системы связи через Интернет (подписные
листы, ICQ и т.д.) позволяют связаться с нужным человеком, о существовании
которого вы и не подозревали.

Более 10 лет назад мне пришлось решать проблему дозиметрии для ультрафиолетового
излучения солнца (озоновая дыра). С дозиметрией жестких излучений от рентгена до
нейтронов я был хорошо знаком, но с ультрафиолетовым излучением раньше не
работал. Я провел поиск во всех доступных библиотеках и WEB-серверах. Результат
оказался минимальным. Тогда я обратился к помощи подписного листа, тематика
которого показалась мне соответствующей проблеме. В течение недели я получил
отклики из США, Канады и Новой Зеландии (Stephan Straus и Martin Brown), частично
это были библиографические ссылки на журналы, которые были в России недоступны,
но было два сообщения, где содержались нужные мне данные. А ведь я не знал адресов
людей, которые мне помогли.

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

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

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

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

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

На протяжении нескольких веков это время равнялось примерно одному году –
времени публикации данных в одном из журналов и доставки этих журналов
адресатам. Теперь эта задержка для рецензируемых электронных журналов не
превышает 1-2 месяцев и одной недели — для нереферируемых, а для тематических
серверов задержка не превышает нескольких часов.

Сегодня Интернет использует многие десятки протоколов. Если сюда добавить
протоколы физического уровня, то их число превысит сотню. На уровне локальных
сетей наиболее распространены различные разновидности Ethernet, а также Token Ring

7

и некоторые другие. Особенно велико разнообразие протоколов межсетевого обмена.
Здесь, помимо PPP, используются ISDN, Frame Relay, ATM, SDH, Fibre Channel и пр..
На транспортном уровне в Интернет работают протоколы UDP (без установления
соединения) и TCP (с установлением соединения). Это два принципиально разных
подхода к передаче данных. В обоих случаях и передатчик, и приемник имеют
индивидуальные IP-адреса и порты. Но в случае TCP они ассоциируются в
соединители (socket) — две пары IP-адрес-порт, и прием/передача в рамках одной
сессии происходит по схеме точка-точка. Для UDP же допускается возможность
передачи одновременно нескольким приемникам (мультикастинг) и прием данных от
нескольких передатчиков в рамках одной и той же сессии. Протокол TCP используется
для поточной передачи данных, при которой доставка гарантируется на протокольном
уровне. Это обеспечивается обязательным подтверждением получения каждого пакета
TCP. Напротив, протокол UDP не требует подтверждения получения. В этом случае,
как правило, исключается также и фрагментация пакетов, так как пакеты при схеме без
установления соединения никак не связаны между собой. По этим причинам UDP в
основном служит для передачи мультимедийных данных, где важнее своевременность,
а не надежность доставки. Протокол TCP применяется там, где важна надежная,
безошибочная доставка информации (файловый обмен, передача почтовых сообщений
и WEB-технология).

Схема без установления соединения привлекательна также тем, что позволяет при
передаче данных от исходного источника к большому числу приемников
минимизировать общий трафик. Если бы для этой цели использовался протокол TCP,
то при N приемниках надо было бы сформировать N виртуальных каналов и
транспортировать N идентичных пакетов (рис. 1.3). В случае UDP от передатчика до
точки разветвления передается только один пакет, что уменьшает загрузку данного
участка в N раз (рис. 1.4). Причем аналогичная экономия может быть реализована и по
пути к очередной точке разветвления (смотри описание протокола мультикастинг-
маршрутизации PIM).

Рис. 1.3. 

8

Рис. 1.4. 

В примере на рисунке 1.4 на участке 1 снижение трафика по сравнению с
традиционным методом передачи данных происходит в 8 раз, на участке 2 — в 4, а на
сегментах 3 — в два раза. Следует также учитывать, что в случае мультикастинга
удается сократить загрузку за счет использования мультикаст-адресации на уровне
Ethernet.

Все множество протоколов Интернет можно поделить на две группы. К первой
относятся те, что имеют собственный стандарт на формат пакетов (IP, UDP, TCP, ARP,
RARP, RTP, RIP, OSPF, BGP, IGRP, ICMP, SNMP, DNS, PIM, IGMP, BOOTP, AAL и
др.). Вторую группу образуют протоколы, которые формализуют обмен на уровне
сообщений. Они не имеют своих форматов пакетов, а стандартизуют лишь форму
сообщений и алгоритм обмена. Вторая группа использует для передачи своих
сообщений протоколы первой группы. К этой группе относятся SMTP, NTP, POP,
IMAP, FTP, HTTP, RSVP, Telnet/SSH, Finger, NNTP, Whois, SET, SSL и т.д. По
существу, вторая группа располагается на прикладном уровне. Первая группа более
консервативна и достаточно хорошо структурирована, вторая – динамична и постоянно
расширяется. Ко второй группе примыкают некоторые стандартизованные утилиты
типа ping, traceroute, а также поисковые системы. В перспективе на подходе протоколы
для интерфейсов баз данных и мультимедиа. Особняком стоят алгоритмы обеспечения
безопасности.

Но чем больше протоколов используется, чем сложнее становится технология, тем она
становится уязвимее.

1.1. Протокол IP

В Интернет используется много различных типов пакетов, но один из основных — IP-
пакет (RFC-791), именно он вкладывается в кадр Ethernet и именно в него
вкладываются пакеты UDP, TCP и ICMP. IP-протокол предлагает ненадежную
транспортную среду: ненадежную в том смысле, что не существует гарантии
благополучной доставки IP-дейтаграммы. Алгоритм доставки в рамках данного
протокола предельно прост: при ошибке дейтаграмма выбрасывается, а отправителю
посылается соответствующее ICMP-сообщение (или не посылается ничего).

9

Обеспечение же надежности возлагается на более высокий уровень (UDP или TCP).
Формат IP-пакетов показан на рисунке 1.5.

Поле версия характеризует версию IP-протокола (например, 4 для v4 или 6 – для v6).
Формат пакета определяется программой и, вообще говоря, может быть разным для
разных значений поля версия. Только размер и положение этого поля незыблемы.
Поэтому в случае изменений длины IP-адреса или других вариаций заголовка слишком
тяжелых последствий не произойдет. Понятно также, что значение поля версия во
избежание непредсказуемых последствий должно контролироваться программой. Поле
версия определяет то, что следует далее делать с заголовком дейтаграммы и полем
данных. Ниже на рис. 1.5а для сравнения приведен формат заголовка дейтаграммы
IPv6 (RFC-2460). Заголовок для IPv6 имеет размер в два раза больше, чем для IPv4.

Общим полем для заголовков является только версия. Поле длина заголовка Hlen (v4)
нужно из-за возможности присутствия полей опций. Hlen — длина заголовка,
измеряемая в 32-разрядных словах, обычно заголовок содержит 20 октетов (Hlen=5, без
опций и заполнителя). В версии 6 заголовок имеет фиксированную длину, и
необходимость в поле длины заголовка отпадает. Функция тип сервиса (ToS IPv4)
реализуется в IPv6 в несравненно большем объеме с помощью полей класс трафика и

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

потока или следующий заголовок (IPv6).

Поля идентификатор, флаги (3 бита) и указатель фрагмента (fragment offset; IPv4)
управляют процессом фрагментации и последующей “сборки” дейтаграммы.

Идентификатор представляет собой уникальный код дейтаграммы, позволяющий
идентифицировать принадлежность фрагментов и исключить ошибки при “сборке”
дейтаграмм. Бит 0 поля флаги является резервным, бит 1 служит для управления
фрагментацией пакетов (0 — фрагментация разрешена; 1 — запрещена), бит 2
определяет, является ли данный фрагмент последним (0 — последний фрагмент; 1 —
следует ожидать продолжения). Поле полная длина (IPv4) функционально
эквивалентно полю размер поля данных (IPv6). Поле полная длина определяет полную
длину IP-дейтаграммы (до 65535 октетов), включая заголовок и данные. В случае
Ethernet длина дейтаграммы не может быть больше 1500 байт.

В IPv6 фрагментация может производиться только отправителем и можно считать, что
флаг DF (не фрагментировать) по умолчанию подразумевается равным 1 (хотя поля
флаги здесь по понятным причинам нет).

Протокол IPv6 требует, чтобы каждый канал в Интернет имел MTU = 576 октетов или
более. Для каждого канала, который не способен обеспечить длину пакетов в 576
октетов, должна быть обеспечена фрагментация/дефрагментация на уровне ниже IPv6.

10