WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

К 40-летию Интернета О РаСпРеДеленных КОММУниКациях (введение в распределенные коммуникативные сети) Пол БАРАН 1.

Введение Plt POLITIKA Р ассмотрим такой ви д ком­ муникационной сети, который позволит нескольким тыся­ чам крупных станций поддержи­ • • вать связь после удара противника.

µ OIKONOMIA В качестве критерия живу чести мы выбрали процент станций, как физически не разрушенных в ре­ зультате удара, так и сохранивших связь с наиболее многоч ислен­ ной группой выживших станций.

Этот критерий выбран в качест­ ве консервативного показател я способности выживших станций взаимодействовать в составе пол­ ноценной системы после удара противника. Небольшие группы 2 сентября 2009 года интернету исполни­ станций, изолированные от основ­ лось 40 лет. Эта всемирная сеть обмена ной группы, будут рассматриваться информацией прочно вошла в нашу жизнь.

как выведенные из строя.

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

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

Такое построение делает сеть максималь­ ка») — рис. 1. Централизованная но надежной, защищенной от технических сеть является по определению уяз­ сбоев, а главное — от ударов противника. вимой, поскольку уничтожение Разработкой концептуальных основ «вы­ одного­единственного централь­ живающих» сетей занималась RAND ного узла обрывает связь между Corporation. заказ на исследовательскую оконечными станциями. На прак­ работу в этом направлении получил извест­ тике при создании коммуникацион­ ный экономист Пол Баран. В рамках соот­ ных сетей используется сочетание ветствующей программы Баран написал ряд «звездообразных» и «сетевидных» работ, посвященных различным аспектам элементов. Например, тип Б на конструирования такой сети. Первую из них, по праву считающуюся теоретическим рис. 1 представляет собой иерар­ фундаментом интернета, мы предлагаем хическую структуру, состоящую из вниманию читателей. нескольких «звезд», подключенных в форме большой «звезды» с до­ Baran P. On Distributed Communications.

полнительной линией, образующей I. Introduction to Distributed Communications петлю. Подобные сети часто назы­ Network / The Rand Corporation. Memorandum вают децентрализованными, так как RM­3420­PR. August 1964.

их работа не зависит полностью от какой­либо одной точки.

Перевод с английского ю. Новгородского 14 О распределенных коммуникациях Рис. 1. Централизованные, децентрализованные и распределенные сети 2. Распределенные сети Поскольку в децентрализованных сетях уничтожение даже небольшого количества узлов влечет за собой потерю связи, огромный интерес представля­ ют особенности, проблемы и перспективы создания распределенных сетей.

Термин «уровень резервирования» будет использоваться здесь для харак­ теристики надежности связи (рис. 2). В качестве ориентира с уровнем резер­ вирования 1 будет рассматривать­ ся минимальная сеть — то есть сеть с минимально возможным количест­ вом линий. Если в какой­либо сети с топологией «решетка» используется в два раза больше линий, чем в мини­ мальной, ее уровень резервирования составит 2. На рис. 2 демонстриру­ ется надежность связи для уровней резервирования 1, 1,5, 2, 3, 4, 6 и 8.

В бесконечном массиве станций уро­ вень резервирования будет эквивален­ тен отношению линия/узел. Очевидно, что для уровней резервирования более 3 существуют альтернативные способы создания сети, однако мы обнаружили, что незначительное изменение мето­ да на результат не влияет. Подобный альтернативный метод применен на уровнях 3 и 4 и обозначен R'. Этот же альтернативный метод используется и на уровнях 6 и 81.

Каждый узел и линия массива на рис. 2 обладает пропускной спо­ Рис. 2. Определение уровня резервирования Craig L.J., Reed I.S. Overlap Tesselated Communications Networks // IRE Trans. Comm. Sys.

1962. CS­10. P. 125—129.

1 Пол БаРаН собностью и коммутационной гибкостью, обеспечивающими связь между любой i-станцией и любой j-станцией при возмож­ ности проложить маршрут между i-станцией и j-станцией.

Начиная с сети, состоящей из массива станций, соединенных, как показано на рис. 3, рассмотрим, что произойдет при разрушении определенного процента узлов и линий. Если после этого все еще можно провести линию, соединяющую i-станцию и j-станцию, то меж­ ду этими станциями есть связь. Рис. 3. Массив станций Разрушение узлов Производительность сети представлена на рис. 4 как функция веро­ ятности разрушения каждого отдельного узла. Когда характерный «шум» слышен в результате обычной поломки, подобные неисправности с разной вероятностью распределяются по всей сети. Но если связь была нарушена в результате удара противника, нужно быть готовым к максимально небла­ гоприятному сценарию.

Чтобы разделить надвое сеть из 32 линий, потребуется применение 288 единиц оружия с вероятностью поражения (Вп) 0,5, или 160 единиц с Вп 0,7, что обеспечит разъединение сети с вероятностью 0,9. При нали­ чии скрытого командного пункта после удара наиболее многочисленная отдельная группа станций должна составлять около 50% от изначального количества не выведенных из строя станций. Ошибки противника в расчетах огневой мощи и эффективности оружия применительно к каждой отдельной линии, а также отсутствие точных данных обо всех линиях в зоне опера­ ции приведут в провалу операции. Малая вероятность успеха при ударах по высокопараллельным структурам в итоге заставит противника разрабатывать альтернативные стратегии. Рассмотрим обобщенный пример наступательной операции. Предположим, что против сети из 1000 станций применяется орудий. Станции расположены таким образом, что поражение двух станций одной единицей оружия маловероятно. Разделим 2000 орудий на 2 равные залповые группы по 1000 единиц. Предположим, что вероятность поражения одного узла одним орудием составляет менее 1,0 — к примеру 0,5. Каждое орудие первой залповой группы способно поразить цель с вероятностью 0,5.

Но в таком случае для каждого орудия второй залповой группы этот пока­ затель составит 0,25, поскольку половина целей уже поражена. Этот пример наступательной операции, таким образом, будет в дальнейшем рассматри­ ваться нами в качестве наименее благоприятного сценария.

Подобные удары с наименее благоприятным сценарием рассматрива­ лись применительно к массиву 18 18, моделирующему сеть из 324 узлов, при изменяемых вероятности поражения и уровне резервирования (рис. 4).

Вероятность поражения изменялась от нуля до единицы по оси абсцисс, в то время как живучесть располагалась по оси ординат. В качестве крите­ рия живучести рассматривался процент станций, не выведенных из строя физически и поддерживающих связь с наиболее многочисленной отдельной группой выживших станций. Кривые на рис. 4 описывают живучесть как функцию интенсивности удара для сетей с различными уровнями резервиро­ вания. Линия, обозначенная как «оптимальная», обозначает верхнюю грани­ 1 О распределенных коммуникациях Рис. 4. Идеальная коммутация в распределенной сети — чувствительность к разрушению узлов при 100% исправных линий цу потери производительности в результате только физических повреждений.

К примеру, если сеть подверглась удару с вероятностью поражения каждого узла 0,5, ожидается, что выживет только 50% узлов — независимо от того, как хорошо работает сеть. Нас же в первую очередь интересует дальнейшее ухудшение работы системы в результате отказа коммуникаций. Графики на рис. 4 позволяют сделать два важнейших вывода. Во­первых, создание сетей с крайне высокой живучестью возможно и при достаточно низком уровне резервирования. Уровень резервирования, составляющий около 3, позволяет сети выдерживать крайне мощные удары с незначительной потерей связи.

Во­вторых, обратим внимание на острые углы излома кривых живучести.

Сеть данного типа способна выдерживать удар возрастающей интенсивности до определенной точки, после которой ее производительность стремительно падает. Поэтому оптимальный уровень резервирования можно определить как функцию ожидаемой интенсивности удара. Дальнейшее увеличение уров­ ня резервирования фактически ничего не даст. Устойчивость сети к крайне интенсивным ударам достигается при достаточно невысоком уровне резер­ вирования — где­то в 3—4 раза выше уровня минимальной сети.

Разрушение линий В предыдущем примере мы рассматривали производительность сети как функцию разрушения узлов (которые являются более уязвимыми мишенями, чем линии). Теперь рассмотрим ту же сеть, но в условиях ненадежной работы линий. Нас особенно интересует то, насколько ненадежными могут быть линии, не вызывая ухудшения работы сети. На рис. 5 представлены резуль­ таты для сети с идеально функционирующими узлами — в случае отказа только линий. Даже в случае крайне ненадежных линий (со временем неис­ правного состояния порядка 50%) производительность системы снижается незначительно — при условии, что все узлы исправны.

1 Пол БаРаН Рис. 5. Идеальная коммутация в распределенной сети — чувствительность к разрушению линий при 100% исправных узлов Разрушение узлов и линий Худший случай — это последствия разрушения как узлов, так и ли­ ний. На рис. 6 показаны последствия отказа линий для сети, потерявшей 40% узлов. Оказывается, линии, которые сегодня считаются «ненадеж­ ными», могут использоваться в распределенных сетях почти с таким же Рис. 6. Идеальная коммутация в распределенной сети — чувствительность к разрушению линий при поражении 40% узлов 1 О распределенных коммуникациях успехом, как и полностью надежные. На рис. 7 представлены результа­ ты 100 испытаний, проведенных для оценки плотности распределения вероятности производительности системы при отказах и узлов, и линий.

Вот как выглядит распределение при 20% поврежденных узлов и 35% поврежденных линий.

Рис. 7. Плотность распределения вероятности для наиболее многочисленной группы станций, поддерживающих связь друг с другом (идеальная коммутация, R=3, 100 случаев, при 80% выживших узлов и 65% выживших линий) 3. Диверсификация каналов Существует и другой — более распространенный — способ обеспе­ чения надежности связи, чем предполагающий идеальную коммутацию на каждой станции метод, о котором мы говорили выше. Этот альтер­ нативный принцип «диверсификации каналов» не требует коммутации.

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

Моделирование В матрице из N­го числа отдельных станций каждая i-станция соедине­ на с каждой j-станцией тремя кратчайшими, но полностью независимыми маршрутами (i = 1, 2, 3,…,N;

j = 1, 2, 3,…,N;

i j). Затем сеть подвергается удару. Далее изучается каждый из предварительно назначенных отдельных маршрутов между i-станцией и j-станцией. Если после удара выживает один или более маршрутов, можно сказать, что между i-станцией и j-стан­ цией есть связь. В качестве критерия живучести используется медианное число станций, соединенных с каждой из данных станций, усредненное для всех станций.

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

1 Пол БаРаН Рис. 8. «Диверсификация каналов» vs. «идеальная коммутация» в распределенной сети Сравнение с современными системами Распространенные в наши дни системы коммутации способны обнаружи­ вать лишь малую долю от потенциального количества маршрутов, которые можно проложить в сети с решетчатой топологией. А ведь чем выше процент опробованных потенциальных маршрутов, тем ближе работа сети к принципу идеальной коммутации. Таким образом, идеальная коммутация представляет собой верхнюю границу ожидаемой производительности для сети с решет­ чатой топологией, тогда как принцип диверсификации каналов — нижнюю ее границу. Между этими полюсами располагаются системы, использующие сочетание принципов коммутации и диверсификации каналов. Принцип диверсификации каналов хорошо подходит для коротких маршрутов, позво­ ляя обойтись в этом случае без коммутации, однако требует высокой живу­ чести и надежности каждого из своих парных элементов в сетях высокой протяженности, проходящих через множество узлов. Поскольку при дивер­ сификации на как минимум одном из немногих маршрутов все оборудование должно быть единовременно исправно, этот принцип, как правило, требует высокого запаса надежности и наличия резервного оборудования.

4. Технологии будущего Мы стоим на пороге эпохи, когда гарантировать живучесть какого­либо элемента сети будет практически невозможно. Но нам вполне по силам разработать системы, для разрушения которых противнику придется выво­ дить из строя каждую станцию. А если сделать количество этих станций достаточно большим, то можно говорить о строительстве систем с высо­ чайшей степенью живучести и в термоядерную эру. Создание подобных сетей предполагает большое количество элементов. Нас интересует то, 200 О распределенных коммуникациях насколько можно удешевить эти элементы без ущерба для надежности системы. Существует безусловная зависимость между стоимостью элемен­ та и его надежностью. Для создания системы, рассчитанной на макси­ мальные разрушения в случае как удара противника, так и стандартных технических проблем, необходимо рассмотреть сочетание повреждений в результате удара и обычных технических неисправностей при условии, что противник не знает, какие элементы выведены из строя. Главная задача, которую нам предстоит решить, — создание высоконадежных систем из заданного набора малонадежных элементов с минимальными затратами.

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

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

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

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

Регенеративно-импульсные ретрансляционные линии Изобретенный еще Сэмюэлем Б. Морзе регенеративный повторитель недавно пережил второе — транзисторное — рождение. Созданное Морзе электрическое реле позволяет усиливать слабые бинарные телеграфные сиг­ налы до заданного уровня. В ходе экспериментов, проводимых различными организациями (главным образом Bell Telephone Laboratories), было уста­ новлено, что цифровые данные со скоростью около 1,5 млн бит/с можно передавать по обыкновенным телефонным линиям с ретрансляционным интервалом порядка 6000 футов для медной пары диаметра 22 с целлюлозной изоляцией. В настоящее время в мультиплексной ИКМ­системе T­1 произ­ водства Bell System используется более 20 каскадно подключенных усили­ телей без каких­либо проблем с синхронизацией. И ничто не мешает нам использовать линии с меньшей потерей сигнала и с увеличенным ретранс­ ляционным интервалом или более эффективные способы ресинхронизации для увеличения протяженности линий до более чем 200 миль. Именно такие масштабы потребуются для создания национальной распределенной сети.

Пол БаРаН Питание для миниатюрных транзисторных усилителей­ретрансляторов подается по тому же медному проводу.

«Микрозатратные» микроволны Даже при том, что стоимость микроволновой связи падает, экономи­ ческий потенциал этой технологии еще далеко не исчерпан. В аналоговой сети от длинной череды каскадно подключенных повторителей требуются высокая надежность и низкий уровень искажений. Использование цифровой модуляции наряду с идеальной коммутацией позволит свести эту статью рас­ ходов к минимуму. Будущее за маломощными, производимыми большими партиями микроволновыми приемниками/передатчиками, устанавливаемыми на недорогие, невысокие опоры на оттяжках. Ретрансляционный интервал будет составлять порядка 20 миль. Но можно сэкономить и еще больше — за счет сведения к минимуму резервного оборудования и уменьшения запаса на затухание сигнала. А возможность поиска альтернативных маршрутов позволит серьезно говорить об использовании частот, обычно подверженных затуханию в дожде, что снизит загруженность диапазона.

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

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

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

Линии с варьируемой скоростью обработки данных В традиционной сети с коммутацией каналов каждой из парных линий должны соответствовать свои полосы пропускания. Чтобы цифровая линия приносила максимальную пользу, скорость передачи данных после устране­ ния ошибок должна варьироваться в зависимости от уровня помех. Задача, таким образом, заключается в создании сети, сформированной из линий с варьируемой скоростью передачи данных, что позволит максимально эффективно распоряжаться ресурсами.

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

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

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

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

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

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

Пол БаРаН Важнее всего то, что стандарти­ зированные блоки вывода данных позволят одновременно множеству пользователей с разными требова­ ниями к пропускной способности экономно использовать широкопо­ лосную сеть, состоящую из линий с различной скоростью передачи данных. Стандартизированные блоки вывода данных упростят и создание высокоскоростных коммутационных устройств. Любой пользователь, под­ Рис. 10. Блок вывода данных ключенный к сети, будет иметь воз­ можность передавать данные с лю­ бой скоростью, вплоть до максимальной. Трафик пользователя сохраняется до тех пор, пока первая станция не получает блок сообщения целиком. Этот блок «проштамповывается» заголовком, обратным адресом и дополнительной служебной информацией. После этого блок передается в сеть.

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

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

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

Однако, с точки зрения пользователя, вызывающего «виртуальное соеди­ нение» с оконечной станцией и за долю секунды передающего сообщения через все Соединенные Штаты, эта система скорее представляет собой некое устройство, обеспечивающее соединение с адресатами по всем США. Есть два требования, которые необходимо выполнить для построения подобной системы «квазиреального времени». Во­первых, хранение входящих данных на каждом узле должно быть сведено к минимуму во избежание задержек.

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

Однако цифровые компьютерные технологии продвинулись настолько, что сегодня с подобными задачами можно справиться, располагая довольно скромным арсеналом цифрового оборудования. Следующим шагом станет сеть с автоматизированной цифровой коммутацией и с применением при­ нципа самообучения на каждом узле, что позволит эффективно распределять трафик в условиях меняющейся сетевой среды без центрального, то есть потенциально уязвимого пункта управления. Один из подобных методов маршрутизации — отличающийся своей простотой так называемый эвристи­ ческий метод «горячей картошки» — мы рассмотрим более подробно.

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

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

Принцип почтальона Коммутация в любой системе промежуточного хранения напоминает работу почтальона, сортирующего почту. Каждый узел — по сути такой почтальон. «Письма»­сообщения приходят одновременно со всех сторон.

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

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

«Горячая картошка» как метод эвристической маршрутизации Для работы в «реальном времени» нам нужна максимально быстрая реак­ ция на изменения в состоянии сети, поэтому мы будет стремиться извлекать информацию о состоянии сети из каждого блока сообщения.

Любой стандартный блок сообщения содержит адрес «куда», адрес «откуда», номер передачи, а также биты, отвечающие за обнаружение ошибок и другие служебные данные. Блок сообщения аналогичен письму, Пол БаРаН а адрес «откуда» — соответствующему разделу письма. Номер передачи — своего рода метка на каждом блоке сообщения, которой при первичной передаче сообщения в сеть присваивается значение 0. При каждой передаче сообщения значение номера передачи увеличивается. Номер передачи ука­ зывает на время, которое сообщение находится в сети, или на протяжен­ ность маршрута сообщения. Таким образом, эти метки аналогичны дате гашения на обычном письме.

Таблица номеров передачи Хотя в принципе даты гашения можно использовать и в цифровой связи, гораздо удобнее воспользоваться более простой цифровой альтернативой — меткой­тегом, прикрепляемой к каждому сообщению, значение которой увеличивается при каждой передаче сообщения. На рис. 11 показана табли­ ца номеров передачи, хранящаяся в памяти каждого узла. Каждая крупная станции сети, способная генерировать трафик, представлена строкой. Для каждой линии, подключенной к узлу, отведена колонка. Как уже говорилось, при уровне резервирования порядка 4 можно создавать очень «крепкие» сети, а дальнейший запас резервирования мало что дает, поэтому на деле вполне достаточно где­то восьми колонок.

Рис. 11. Таблица номеров передачи Каждый коммутационный узел снабжен таблицей для записи номеров передачи текущих сообщений. Числа в таблице — самые низкие недавние значения номеров передач из станции A, B, C и т. д., для всех восьми линий, проходящих через данный узел. Например, у сообще­ ний из станции Е номер передачи равнялся 7 по линии 1. Таблица слева позволяет рассчитать приоритетные маршруты к указанным станциям. Таким образом, если трафик направляется к станции Е по линии 1, приоритетным выбором будет кратчайший из измеренных маршрутов.

Если линия 1 занята или уничтожена, самый высокий номер передачи сообщения определяется для линии 2 и уже этот маршрут становится приоритетным.

Идеальное обучение При условии, что сеть состоит из идеально надежных, безотказных линий, таблицу можно заполнить следующим образом. Сначала присвоим ячейкам таблицы высокие значения. Изучим номер передачи каждого сообщения, приходящего из каждой станции по каждой из линий. Если реальный номер 20 О распределенных коммуникациях передачи меньше, чем уже заданное в таблице значение, снизим значение ячейки до номера передачи полученного сообщения. Если номер передачи больше заданного в таблице, не делаем ничего. Через некоторое время эта процедура приведет к тому, что таблица будет показывать длину маршрута до каждой станции по каждой из линий, подключенных к соседним стан­ циям. Теперь таблицу можно использовать для создания новых маршрутов.

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

Цифровое моделирование Данный принцип маршрутизации был смоделирован методом Монте­ Карло для массива станций 7 7. Для моделирования наименее благопри­ ятной ситуации, когда ни одна из станций не располагает информацией о других, все таблицы были изначально совершенно пустыми. В течение половины от смоделированного реального времени сеть определила нахож­ дение всех подключенных станций и приступила к нормальному распреде­ лению трафика. При переменной загрузке сети соотношение средней длины маршрута и минимально возможной абсолютной длины было весьма благо­ приятным. Предварительные результаты свидетельствуют о том, что загрузка сети до 50% пропускной способности линий не приводит к неоправданному увеличению длины маршрута. При возникновении в сети отдельных загру­ женных участков трафик временно направляется в обход подобных мест, что позволяет разгрузить сеть и избежать потенциальных «пробок». Таким образом, с точки зрения отдельного узла сеть представляет собой систему с варьируемой скоростью передачи данных, способную ограничивать коли­ чество обслуживаемых локальных пользователей. При легкой загрузке любая вводная линия сети способна принимать интенсивный трафик, возможно, до 1,5 млн бит/с. Но при плотном трафике на каждой станции и сильной загрузке сети допустимая вводная скорость передачи данных может падать и до 0,5 млн бит/с для любой станции. Абсолютно минимальная гаранти­ рованная пропускная способность станции при передаче данных в систему является функцией нахождения станции в сети, уровня резервирования и средней длины маршрута трафика. При моделировании подобного ограни­ чения ввода признаков нестабильности в работе загруженной сети отмечено не было. Было обнаружено, что большинство преимуществ технологии про­ межуточного хранения сохраняется и в системе с относительно небольшим объемом памяти. Такая сеть «гарантирует» быстрое распределение всего принятого от пользователя трафика.

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

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

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

Приспособляемость к среде Этот простой механизм обучения и забывания, применяемый независи­ мо на каждом из узлов, придает сети в целом черты легко адаптирующейся системы, способной без вмешательства человека реагировать на серьезные изменения окружающей среды. К примеру, рассмотрим адаптацию сети к мес­ тонахождению станции. Некоторая станция, Able, обычно ведет передачу из определенного места в сети (рис. 12а). При изменении мес­ тонахождения для обозначения своего нового места станции нужно всего лишь передать несколько секунд ложного тра­ фика — сеть незамедлительно определит новое местонахож­ дение станции Able и направит туда адресованный ей трафик.

Точно так же сеть «переучит­ ся» и в случае изменения или разрушения линии. Любой узел как бы близорук, все его Рис. 12. Адаптация к изменению местонахождения «зрение» ограничено линиями, пользователя соединяющими его с немного­ численными соседями, и информацией о состоянии этих линий. Никакого центрального управления здесь нет, на каждом узле применяется простой метод маршрутизации — но система при этом способна адаптироваться.

20 О распределенных коммуникациях Наименее затратный путь Нам необходимо обеспечить наименее затратный маршрут обмена данными между пользователями. Когда мы говорим о масштабных сетях, охватывающих континенты, мы сталкиваемся с проблемой создания сетей, состоящих из линий с различной скоростью передачи данных. Как направить данные таким обра­ зом, чтобы использовались наименее дорогостоящие линии? И здесь снова на помощь приходит простейший принцип адаптации. Вместо того чтобы увели­ чивать номер передачи на заданную величину при каждой передаче сообщения, привяжем эту величину к соотношению «стоимость линии/биты» передающей линии. Таким образом, главным критерием выбора маршрута будет не крат­ чайший свободный маршрут, а наименее затратный маршрут между пользова­ телями. Этот метод можно развить, разместив информацию от приоритетности и лимите затрат в самом блоке сообщения, что предоставит ряду пользователей пространство для маневра в периоды высокой загруженности сети.

5. Настоящее и будущее Несмотря на то что сейчас еще рано в полном объеме говорить о проблемах и затратах, связанных с цифровыми сетями, есть все основания полагать, что они будут строиться иначе, чем привычные нам аналоговые телефонные сети.

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

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

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

Совместимая с такими линиями новая коммутируемая сеть представляется нам адекватным решением с учетом растущей потребности в цифровой связи.

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

Позиция авторов представленных в номере статей не всегда совпадает с позицией издателей журнала.

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

Редакция оставляет за собой право не вступать в переписку с авторами и читателями.

Издатель: аНО «Редакция журнала „Экономическая политика“».

Журнал зарегистрирован в Федеральной службе по надзору за соблюдением законодательства в сфере массовых коммуникаций и охране культурного наследия. Свидетельство Пи № ФС77­25546.

Адрес редакции: 119571, Москва, просп. Вернадского, д. 82.

Тел.: (495) 933­80­52, 933­80­20. E­mail: ec_policy@anx.ru.

Индекс журнала в каталоге агентства «Роспечать» — 81184.

Над номером работали: е. антонова (научное редактирование), О. Федосова (литературное редактирование и корректура).

Отпечатано с готового оригинал­макета в типографии гОУ аНХ. 119571, Москва, просп. Вернадского, д. 82.

Тираж 1300 экз. (1­й завод 900 экз.). Цена свободная.




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.