Основные вехи в развитии методов пакетной коммутации

Д. Л. Медведев

Введение

В начале 60-х годов прошлого столетия технология коммутации каналов, несмотря на присущие ей недостатки, зарекомендовала себя достаточно хорошо. Большинство специалистов данную технологию рассматривало как единственную, и говорить о ее замене не приходилось. К тому же еще 80 лет назад - в 1880-х годах, механизм выделения необходимой пропускной способности на все время сеанса связи (а именно на этом принципе построена коммутация ка­налов) был более предпочтительным по сравнению с динамическим выделением необходимых ресурсов (телеграфные службы). Но в то время, когда положение коммутации каналов казалось очень прочным, появляются новые технологии, требующие других механизмов передачи данных и решающие совершенно иные задачи.

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

Основные принципы

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

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

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

рис.1

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

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

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

Рассмотрев некоторые общие вопросы, касающиеся метода коммутации пакетов, перейдем к непосредственному описанию того, кем и когда впервые была предложена пакетная коммутация.

Дейтаграммный режим

Леонард Клейнрок

Одним из пионеров в области пакетной коммутации является Леонард Клейнрок. Клейнрок родился в 1934 г . в Нью-Йорке. После окончания в 1957 г. городского колледжа он стал инженером-электриком. Свое образование Л. Клейнрок продолжил в Массачусетском технологическом институте, где в 1959 г. получил степень магистра, а в 1963 г. защитил докторскую диссертацию. После получения докторской степени он стал профессором в области компьютерных наук в Калифорнийском университете в Лос-Анджелесе (США). В этом учебном заведении им был образован Сетевой измерительный центр ( Network Measurements Center ), сотрудниками которого, как правило, становились студенты, окончившие университет. Данный центр станет первым узлом глобальной сети Интернет.

По воспоминанию самого Л. Клейнрока, работы над теорией пакетной коммутации были начаты им в 1959 г. В июле 1961 г. он опубликовал свою первую работу, посвященную цифровым сетям связи - "Информационные потоки в больших сетях связи". Новые идеи пакетной коммутации были изложены Л. Клейнроком в тезисах к докторской диссертации. Спустя год идеи были им доработаны и опубликованы в книге "Сети связи" ("Communication nets").

Практическая реализация принципов пакетной коммутации состоялась в 1965 г . В феврале этого года директор Бюро по методам обработки информации ( IPTO - Information Processing Techniques Office ) Айвен Сьюзерланд подписал с молодым специалистом Лоуренсом Робертсом контракт на создание местной компьютерной сети. В июле этого же года к Л. Робертсу присоединился молодой психолог Томас Мэрилл. В октябре 1965 г. совместная работа двух молодых ученых увенчалась успехом - им удалось связать низкоскоростной коммутируемой телефонной линией на скорости 1200 бит/с два компьютера - ТХ-2 из Lincoln Lab Массачусетского технологического института и AN / FSQ -32 из System Development Corporation, находившийся в Санта Монике (штат Калифорния, США). Данная компьютерная сеть стала первой сетью с пакетной коммутацией. И хотя в данной сети время доставки сообщения было слишком большим, а надежность системы оставляла желать лучшего, это был шаг вперед на пути к новым технологиям.

Поль Бэрэн

В октябре 1966 г. Л. Робертс и Г. Мэрилл опубликовали книгу "В направлении к кооперативным сетям с компьютерами, разделенными во времени" ("Toward a Cooperative Network of Time - Shared Computers"), в которой подробно описывалась совместная деятельность обоих ученых. В ходе данного эксперимента стало очевидно, что телефонная сеть с коммутацией каналов абсолютно непригодна для построения компьютерной сети. Данное обстоятельство лишний раз подтвердило убежденность Л. Клейнрока в том, что сети будущего будут строиться с использованием коммутации пакетов.

В 1966 г. Л. Робертс стал руководителем группы по разработке компьютерной сети ARPANET, ставшей предшественницей Интернета. В основу создания этой разветвленной цифровой сети связи, охватывающей большую территорию, Л. Робертс положил идеи Л. Клейнрока. В октябре 1968 г. Л. Робертс заключил контракт с возглавляемым Л. Клейнроком центром на проведение измерений в сети ARPANET. В сентябре 1969 г. сотрудники центра подключили к интерфейсному процессору сообщений один из своих компьютеров, ставший первым хостом сети Интернет.

Л. Клейнрок рядом с первым коммутатором IMP, который в сентябре 1969 г. был установлен в Сетевом измерительном центре университета Лос-Анджелеса

Паралелльно с Л. Клейнроком аналогичный метод коммутации пакетов предложил Поль Бэрэн. П. Бэрэн родился в 1926 г . в Польше. В 1928 г . его родители переехали в США - сначала в Бостон, а затем в Филадельфию. После окончания школы Поль поступил в Дрексельский уни­верситет на факультет электротехни­ки. После окончания данного учебно­го заведения он устроился на работу в качестве техника в Eckert - Mauchly Computer Corporation . Вскоре он переехал вместе с семьей в Лос-Анджелес, где начал работать в Hughes Aircraft Company. Одновременно молодой человек начал посещать в Калифорнийском университете в Лос-Анджелесе ночные учебные курсы для повышения квалификации специалистов, которые успешно закончил в 1959 г.

В том же 1959 г. он ушел из Hughes Aircraft Company и перешел на работу в RAND (Research and Development) Corporation. В начале 70-х годов П. Бэрен покинул RAND Corporation и начал заниматься частной практикой. Он основал компанию Metricom и был соучредителем Com 21. com . За активную научную деятельность и огромный вклад в развитие глобальной информационной инфраструктуры П. Бэрэн награжден многими почетными наградами, включая медаль им. Александра Грэхэма Белла и награду от Международного общества Маркони - MIF ( Marconi International Fellow ­ ship ).

Свои первые исследования по пакетной коммутации П. Бэрэн опубликовал, уже будучи сотрудником RAND Corporation в августе 1964 г. в 11-томном отчете "On Distributed Communications". В разработках П. Бэрэна и Л. Клейнрока было очень много общего. Отчасти это объясняется тем, что основной целью их было создание сети связи, способной выдержать ядерный удар. Первоначально П. Бэрэн назвал данный вид коммутации режимом "горячей картошки" ( hot potato operation ). Позже он будет переименован в дейтаграммный режим.

рис. 2 Передача пакетов в дейтаграммном режиме

рис. 3. Передача пакетов при формировании виртуального канала

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

Принимая во внимание, что основным достоинством данного метода является простота механизма передачи пакетов, он был выбран в качестве основы при построении целого ряда корпоративных сетей в университетских и научно-исследовательских кругах, а также сети ARPANET. В качестве коммутаторов в сети ARPANET использовались специальные процессоры IMP ( Interface Message Processor - интерфейсный процессор сообщений) (рис. 3). Каждый такой процессор, принимая от удаленных рабочих станций и терминалов данные, разбивал их на 128-байтные блоки. Из каждого такого блока путем добавления заголовка, содержащего адреса отправителя и получателя, формировался пакет. Затем процессор IMP на основе динамически обновляемой таблицы маршрутизации пересылал данные пакеты по наиболее быстрому маршруту.

Бурное развитие сети ARPANET недвусмысленно продемонстрировало, что технология коммутации пакетов может использоваться в качестве основы при построении многочисленных сетей передачи данных. Практическая реализация данной технологии на примере сети ARPANET развеяла серьезные опасения большинства специалистов, будто бы данная технология станет невозможной из-за большого числа петель и огромных очередей, которые будут образовываться на большинстве сетевых узлов. Первая публичная демонстрация новой технологии состоялась на проводимой в Вашингтоне (США) в октябре 1972 г . Первой международной кнференции по компьютерным коммуникациям - ICCC ( International Con ­ ference on Computer Communications ).

Параллельно и независимо от разработок Л. Клейнрока и П. Бэрэна аналогичные исследования проводились и в Старом свете. Английским специалистом Национальной физической лаборатории NPL (National Physical Laboratory) Дональдом Дейвисом также были начаты исследования в области пакетной коммутации. Д. Дейвис родился 7 июня 1924 г. в английском городе Треорчи. После окончания школы он поступил в Имперский колледж в Лондоне. В 1943 г. Д. Дейвис получил степень бакалавра в области физики, а в 1947 г. - и в области математики. С 1943 по 1947 гг. молодой человек участвовал в проводимых в Бирмингемском университете исследованиях в области атомной физики. Там он посещал лекции Джона Вомерслея, тогдашнего руководителя математического отдела Национальной физической лаборатории. Основу данных лекций составляли редкие в то время материалы по цифровым компьютерам. Потенциальные возможности и перспективы новой технологии глубоко взволновали Д. Дейвиса, и в сентябре 1947 г. он стал работать в небольшой группе, руководимой Аланом Тьюрингом. Под его руководством в данной группе была создана одна из первых в мире программ для цифровых компьютеров. Совместно с Тедом Нейманом и Джимом Вилкик-сом Д. Дейвис принимал участие в проектировании и разработке первого в Англии цифрового компьютера, а позже - и его более совершенной версии.

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

В 1963 г. Д. Дейвис стал руководителем государственного проекта по созданию и внедрению в промышленности Великобритании современной компьютерной техники. В 1966 г. он возглавил атомный отдел в Национальной физической лаборатории. Вскоре данный отдел стал также проводить исследования в области компьютерной техники. Главным направлением разработок руководимой Д. Дейвисом лаборатории стала реализация выдвинутого им в 1965 г. метода коммутации пакетов. После А. Тьюринга Д. Дейвис был первым крупным ученым, который сформировал концептуальные положения компьютерного программирования. В 1979 г. Д. Дейвис оставил административный пост и полностью посвятил себя работе над техническими проектами. Скончался Д. Дейвис в Австралии 28 мая 2000 г.

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

Д. Дейвис

В августе 1965 г. Д. Дейвис организовал в США расширенный технический семинар. После плодотворных обсуждений, основной темой которых было дальнейшее развитие новых сетевых технологии, ученый решил объединить технологию коммутации сообщений с использованием компьютеров в режиме разделения времени. По мнению Дейвиса если длинные информационные сообщения будут делиться на блоки, тогда с приходом на коммутатор длинных сообщений и сообщений небольшой длины, обслуживание первых не окажет сильного влияния на увеличение задержки при обслуживании вторых. Первоначально для обозначения данных блоков Д. Дейвис предложил использовать термин "короткие сообщения", но, проконсультировавшись с лингвистами из Национальной физической лаборатории, в конце концов заменил его на более звучное и к тому же легче переводимое на иностранные языки слово "пакет". 10 ноября 1965 г. данные идеи были впервые опубликованы в небольшом корпоративном отчете, познакомившем специалистов Национальной физической лаборатории с новой технологией.

В марте 1966 г. Д. Дейвис организовал в Национальной физической лаборатории научно-технический семинар, на который было приглашено более 100 ведущих специалистов в области телекоммуникаций. Д. Дейвис поделился с обширной аудиторией своими идеями по технологии коммутации пакетов и ее реализацией в компьютерных сетях. Выступление ученого было опубликовано в июне 1966 г. под названием "Предложения по построению цифровой сети связи" ("Proposal for a digital communication network"). Это была первая в мире публикация, где было использовано слово "пакет". По окончании семинара к Д. Дейвису подошел сотрудник Министерства обороны США А. Ле-веллин и рассказал, что большинство из поднятых на семинаре вопросов касательно метода коммутации пакетов затронул еще в 1964 г. в своей работе сотрудник RAND Corporation П. Бэрэн. Это было удивительно - ученые, находясь на разных континентах, одновременно и совершенно независимо друг от друга пришли к похожим выводам. Мало того, и Д. Дейвис, и П. Бэрэн выбрали одинаковую для пакетов длину -128 байт!

Вклад Д. Дейвиса в создание систем с пакетной коммутацией был отмечен в 1974 г. Британским компьютерным обществом премией Джона Плэйра. В 1975 г. ученый стал Почетным членом этого общества, а в 1983 г. - его вице-президентом. В 1987 г. Д. Дэйвис был избран членом Королевского общества.

Несмотря на то, что работы американских и английского ученых во многом совпадали, все же они имели и существенные различия. Разработки Д. Дейвиса велись под непосредственным контролем Британского почтового ведомства - ВРО (British Post Office), являющегося национальным монополистом в отрасли связи. Это сильно отразилось на характере проводимых исследований. Основная задача Д. Дейвиса заключалась в создании сетей с гарантированной доставкой информации. Позже метод коммутации пакетов, предложенный Д. Дейвисом получит название метода виртуального канала.

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

История коммутационных технологий еще не закончена. В середине 80-х годов прошлого века в Европе и США широкое распространение получили новые методы коммутации - асинхронное временное разделение - ATD (Asynchronous Time Division) и быстрая коммутация пакетов - FPS (Fast Packet Switching). Позже данные методы войдут в основу технологии ATM (Asynchronous Transfer Mode - асинхронный режим передачи), внедрение которой придется на 90-е годы XX столетия. В это время также начнется создание новой технологии, сочетающей достоинства ATM коммутации и IP маршрутизации - MPLS (Multiprotocol Label Switching - Многопротокольная коммутация по меткам).

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

Автор выражает признательность М.А. Быховскому за ценные замечания, учтенные при написании данной статьи.

Литература

1. Убайдуллаев P.P. Волоконно-оптические сети. - М.: ЭКО-ТРЕНДЗ, 1998.
2. Kleinrock L. The Birth of the Internet
3. http://www.lk.cs.ucla.edu/LK/Inet/birth.html
4. Kleinrock L. Len Kleinrock on the Origins of the Internet: "This is login'", in IEEE Internet Computing Online , 1997, March-April. - Vol. 1. - № 2.
5. http://www.lk.cs.ucla.edu/personal_history.html
6. http://livinginternet.com/i/ii_kleinrock.htm
7. http://www.thocp.net/biographies/davies_donald.htm
8. Davies D. Historical Note on the Early Development of Packet Switching.
9. http://www.cs.utexas.edu/users/kata/HISTORY/DAVIES/DaviesOl.pdf
10. http://www.ibiblio.org/pioneers/baran.html
11. http://livinginternet. с om/i/ii_rand.htm
12. Гольдштейн B. C., Пинчук А. В., Cyxoвицкий А.Л. IP -телефония. - M .: Радио и связь, 2001.
13. Нейман В.И. К дискуссии о коммутации// Электросвязь. - 2004. - № 1.
14. Гольдштейн Б., Голышко А., Шнепс-Шнеппе М., Яновский Г. Коммутационное Евангелие// Вестник связи. - 2001. - № 12.
15. Шварцман В.О. Выбор технологии передачи и коммутации в мультисервисных сетях на основе оптических кабелей// Электросвязь. - 2003. - № 8.
16. Baran P. On Distributed Communication.
17. http://www.rand.org/publications/RM/baran.list.html
18. Roberts L. The First Theory of Packet Networks.
19. http://www.сs.ucla.edu/~lk/first_packet_network_theory. html

Статья опубликована в журнале "Электросвязь"
Перепечатывается с разрешения редакции.

Статья помещена в музей 12.12.2006 года