bgp_map

BGP или «протокол на трёх салфетках»

БЮРО ПЕРЕВОДОВ

Четверг 19 января 1989 года в техасском городе Остин выдался ненастным. Дождь лил, как из брандспойта. В такую погоду приятно посидеть в кафе, выпить чего-нибудь горяченького!

cafe-catering

Тот самый кафетерий

Во второму часу дня в кафетерий исследовательского центра Техасского университета хлынули посетители. Кофе, бутерброды, гул оживлённых голосов… Вот за столиком сидят двое мужчин и что-то горячо обсуждают. Один из них, кудрявый, говорит с сильным славянским акцентом, другой, чернобровый, что-то показывает руками. Они так увлечены, что совсем забыли про еду. Зачем же этот, с акцентом, тянется за салфеткой? Хм, что за каляки-маляки?

bgp1

Салфеточный манускрипт

Собеседниками были Яков Рехтер (Yakov Rekhter) и Кирк Лохид (Kirk Lougheed).

img0065

Яков Рехтер

66926252n07_r

Кирк Лохид

Здесь, в Остине, с 18 по 20 января 1989 года проходила встреча рабочей группы IETF (Internet Engineering Task Force) ― международного сообщества проектировщиков, учёных, сетевых операторов и провайдеров, и оба они приехали на эту встречу, чтобы обсудить проблемы маршрутизации. Рехтер на тот момент уже 5 лет работал в IBM; акцент выдавал в нём бывшего гражданина СССР: в начале семидесятых он окончил Ленинградский Государственный Университет (успел даже поиграть на фортепиано в студенческой рок-группе), потом отучился в Нью-Йоркском университете и защитил докторскую. Лохид работал в Cisco ― он был одним из пяти учёных из Стэнфордского университета, которые основали эту компанию в 1984 году. Сейчас, в кафетерии, Рехтер и Лохид сочиняли совершенно новый протокол ― Border Gateway Protocol, протокол граничного шлюза, или просто BGP. Да-да, прямо на салфетках, потому что бумаги под рукой не было: ведь они просто вышли перекусить в перерыве между заседаниями рабочей группы и никаких протоколов придумывать, вроде бы, не планировали… Тогда как же это вышло?

402812

Возможно, ничего подобного не случилось бы, если бы за 20 лет до этого, в далёком 1969 году, Министерство обороны США в лице агентства по передовым исследованиям ARPA (Advanced Research Projects Agency) не запустило проект ARPANET. Холодная война с СССР и гонка вооружений не настраивали на мирный лад, поэтому военные готовились к худшему и решили построить компьютерную сеть, чтобы использовать её для связи в условиях боевых действий, если таковые будут, то есть, в прямом смысле на случай атомной войны. В те времена они и представить не могли, что их проект даст начало бесконечному множеству сетей и сеточек, которые опутывают сегодня весь земной шар, как элементы огромного кружевного полотна – Интернета. В 1969-ом, однако, всё было скромно: сеть состояла всего из четырёх узлов, которые находились в Калифорнийском университете в Лос-Анджелесе, Стэнфордском исследовательском центре, Университете Юты и Университете штата Калифорния в Санта-Барбаре.

1969_4-node_map

Схема ARPANET, 1969 год

Для маршрутизации использовались мини-компьютеры под названием IMP (Interface Message Processor), (или просто «импы»), которые выпускала компания BBN. («Мини» — это, конечно, громко сказано: на самом деле они были размером с добрый холодильник и выше человеческого роста, но по тем временам это было немного!) IMPы были сделаны на основе компьютера Honeywell DDP 516. IMP подключался к своему компьютеру-хосту и передавал данные от него к другим IMPам и обратно. Каждый IMP был связан как минимум с двумя другими IMPами. При отказе одного из них или линии связи сообщения автоматически шли по альтернативному маршруту. Общались IMPы по собственному протоколу, который так и назывался: IMP-IMP.

vs-bbn-imp

Interface Message Processor (IMP)

К сентябрю 1982 года родной IMPовский протокол эволюционировал в протокол GGP (Gateway-to-Gateway Protocol — протокол межшлюзового взаимодействия). Его тоже придумали сотрудники BBN ― Роберт Хинден (Robert Hinden) и Алан Шелтцер (Alan Sheltzer) ― и тоже для ARPA (которое к тому времени превратилось в DARPA (Defense Advanced Research Projects Agency — агентство передовых _оборонных_ исследований). GGP предназначался для первых экспериментальных интернет-шлюзов.

Как, в общих чертах, работал GGP:

  • он прокладывал кратчайший путь от узла к узлу;
  • в таблице маршрутизации была информация об адресе ближайшего соседнего шлюза и о том, подключен ли он к сети;
  • каждый шлюз рассылал соседям обновления маршрутной информации, если менялось его состояние или состояние соседнего шлюза, а также если ему сообщали об изменении состояния какого-нибудь другого шлюза: такое вот «сарафанное радио». Шлюзы слали сообщения до победного конца – пока соседи не подтвердят получение. Едва что-то менялось, на сеть вновь обрушивался шквал сообщений.

harry_potter_catching_letter

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

Однако перемены уже назрели: в том же 1982 году Эрик Розен (Eric C. Rosen) из BBN предложил заменить GGP на новый протокол EGP (Exterior Gateway Protocol – протокол внешнего шлюза). Розен смотрел в будущее: по мере развития сети к ней будут присоединяться новые и новые шлюзы. Они тут же включатся в процесс взаимодействия через протокол GGP. Но ведь эти шлюзы наверняка будут от разных производителей, они будут использовать разное ПО, и для них, таких разных, GGP может не подойти. И вообще, в будущем сеть будет состоять не из отдельных шлюзов, а из автономных систем (АС), а те, в свою очередь, из однородных шлюзов. Те алгоритмы маршрутизации, которыми они будут пользоваться внутри АС, ― их личное дело, а передавать трафик между АС поможет новый протокол EGP.

Над EGP трудились с 1982 по 1984 год. Этот протокол был предназначен, в основном, для того, чтобы передавать информацию о взаимной достижимости между магистральной сетью и АС.

Как работает EGP:

  • шлюзы организуют для себя набор соседей – других шлюзов, с которыми они хотят коллективно пользоваться информацией о достижимости сетей; периодически они опрашивают соседей, чтобы убедиться в их работоспособности;au-copy
  • шлюзы рассказывают соседям, сколько у них в АС внутренних и внешних шлюзов, где находятся их сети, какое до них расстояние, перечисляет сети по IP-адресам;
  • шлюзы передают список сетей, для которых он будет самым удобным входном шлюзом относительно общей сети: «Через Воронеж в Москву удобно ехать тем, кто едет из Сочи».

В общем, EGP даёт маршрутную информацию, но сам никаких умных решений о маршрутизации не принимает. И это не единственный его «минус».

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

143615885

Если что-то случилось в сети, и шлюз рассылает обновление маршрутной информации, но соседи её почему-то не получили, то может случиться так, что пакет отправлен, а «лететь» ему некуда, и он начнёт «крутиться» внутри последовательности маршрутизаторов.

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

Ситуацию усугубило и то, что в 1984 году появилась NFSNET (National Science Foundation Network) — компьютерная сеть Национального фонда науки США, потому что ARPANET нельзя было использовать в коммерческих целях (а очень хотелось). Естественно, сеть стремительно растёт (к ней вовсю присоединяются и иностранные сети), нагрузка на неё тоже растёт, и EGP становится всё более неудобен…

Проблемой занялись члены рабочей группы IETF. Они бились над новой версией протокола (EGP3) с 1987 года ― писали рабочие предложения, встречались, обсуждали их. Решено было ничего принципиально нового не придумывать: ведь EGP работал, надо было только как следует его «допилить».

Увы, как они ни старались, результат им категорически не нравился: «тюнинг» по сравнению с предыдущей версией получался незначительным, принцип работы оставался тем же…

research-center

Исследовательский центр Техасского университета

Очередную встречу устроили 18-20 января 1989 года в Остине, в исследовательском центре Техасского университета.

Четыре часа напряжённой работы в первый день и почти восемь во второй с коротким перерывом ― чуть больше часа. В этот перерыв Яков Рехтер и Кирк Лохид отправились в кафетерий. Сидя за столиком, они рассуждали о том, чего бы им, по-хорошему, хотелось от протокола такого рода и как этого добиться. Усиленный мозговой штурм, под рукой лишь салфетки… На них-то они и набросали идею совершенно нового протокола – BGP (Border Gateway Protocol, протокол граничного шлюза). Он должен был отвечать следующим условиям: устанавливать TCP-соединение (в частности, потому, что протокол TCP использовался почти во всех коммерческих маршрутизаторах и хостах); рассылать только обновления, а не всю таблицу маршрутизации целиком; для каждого маршрута записывать полный путь. Минуточку! Вроде бы, в IETF договорились не изобретать новых протоколов, а совершенствовать старый?.. «Нам нужно было продавать маршрутизаторы, так что у нас был веский экономический мотив», — говорит Кирк Лохид.

printing-money

К июню того же года Рехтер и Лохид подготовили описание своего протокола и вынесли его на суд коллег. Сначала постановили, что BGP станет временным решением: из него возьмут лучшее для усовершенствования EGP, но… как говорится, нет ничего более постоянного, чем временное.

У BGP были неоспоримые преимущества:

  • для него не важна топология сетей;
  • маршрутизатор не делает расчёт маршрута до каждой сети, он выбирает один из нескольких предложенных;
  • можно выбрать самый удобный маршрут по разным параметрам (где быстрее, короче, дешевле, безопаснее);
  • предусмотрена гибкая система фильтрации маршрутов, о каких-то маршрутах можно не получать информацию, о каких-то – самим умолчать (например, я знаю, что есть удобная дорожка через мой огород, но никому не скажу, нечего всем через него шастать);
  • cоседи рассылают друг другу не только адреса сетей и информацию о расстоянии, но и о самих маршрутах – атрибуты, которые описывают разные характеристики маршрутов (всё как в жизни: соседи, вестимо, знают, на какой дороге нормальный асфальт, на какой орудуют разбойники, а на какой бесплатный проезд) ― это помогает шлюзам принимать решения о том, куда следует направлять потоки данных;
  • BGP пересылает таблицу маршрутизации целиком только один раз ― инициируя соединение между шлюзами, а потом посылает только обновления.

Для внешней маршрутизации такой протокол оказался гораздо удобнее, чем EGP. Временное решение, наспех записанное на салфетках, успешно работает больше 25 лет!

Сами судьбоносные салфетки (по слухам, изрядно заляпанные кетчупом), не сохранились, однако Рехтер и Лохид предусмотрительно скопировали то, что было на них написано, и эти копии висят на стене в Cisco.

1433225144290-1

Копия «трёх салфеток»

Судьба протокола BGP сложилась благополучно, а что же случилось с его создателями? Яков Рехтер после IBM работал в Cisco, а потом перешёл в Juniper Networks, где провёл 15 лет. В январе 2015 года он вышел на пенсию. «Бога маршрутизации» провожали не только офф-лайн, но и всем Твиттером.

16-12-2016-11-26-42

Кирк Лохид посвятил карьеру родной компании Cisco. Кроме работы он увлекается фотографией. Его пейзажи отлично продаются на стоках!

kirk-lougheed