Курс лекций по "Клиент- серверные информационные технологии"

Манчестерский код

В локальных сетях до недавнего  времени самым распространенным методом кодирования был так называемый манчестерский код (рис. 2.16, г). Он применяется в технологиях Ethernet и Token Ring.

В манчестерском коде для кодирования  единиц и нулей используется перепад потенциала, то есть фронт импульса. При манчестерском кодировании каждый такт делится на две части. Информация кодируется перепадами потенциала, происходящими в середине каждого такта. Единица кодируется перепадом от низкого уровня сигнала к высокому, а ноль — обратным перепадом. В начале каждого такта может происходить служебный перепад сигнала, если нужно представить несколько единиц или нулей подряд. Так как сигнал изменяется по крайней мере один раз за такт передачи одного бита данных, т.о. манчестерский код обладает хорошими самосинхронизирующими свойствами. Полоса пропускания манчестерского кода уже, чем у биполярного импульсного. У него также нет постоянной составляющей, а основная гармоника в худшем случае (при передаче последовательности единиц или нулей) имеет частоту N Гц, а в лучшем (при передаче чередующихся единиц и нулей) она равна N/2 Гц, как и у кодов AMI или NRZ. В среднем ширина полосы манчестерского кода в полтора раза уже, чем у биполярного импульсного кода, а основная гармоника колеблется вблизи значения 3N/4. Манчестерский код имеет еще одно преимущество перед биполярным импульсным кодом. В последнем для передачи данных используются три уровня сигнала, а в манчестерском — два.

Потенциальный код 2В1Q

На рис. 2.16, д показан потенциальный код с четырьмя уровнями сигнала для кодирования данных. Это код 2В1Q, название которого отражает его суть — каждые два бита (2В) передаются за один такт сигналом, имеющим четыре состояния (1Q). Паре бит 00 соответствует потенциал -2,5 В, паре бит 01 соответствует потенциал -0,833 В, паре 11 — потенциал +0,833 В, а паре 10 — потенциал +2,5 В. При этом способе кодирования требуются дополнительные меры по борьбе с длинными последовательностями одинаковых пар бит, так как при этом сигнал превращается в постоянную составляющую. При случайном чередовании бит спектр сигнала в два раза уже, чем у кода NRZ, так как при той же битовой скорости длительность такта увеличивается в два раза. Таким образом, с помощью кода 2В1Q можно по одной и той же линии передавать данные в два раза быстрее, чем с помощью кода AMI или NRZI. Однако для его реализации мощность передатчика должна быть выше, чтобы четыре уровня четко различались приемником на фоне помех.

15. Сравнительная характеристика методов коммутации: каналов, сообщений, пакетов

 

Коммутация каналов

На рис.2-34 a и b показаны схемы работы при коммутации каналов и при  коммутации пакетов.

Коммутацию каналов изобрел  в ХIХ в. Алмонд Строугер (Almond Strowger). История этого изобретения достаточно интересна. Строугер был владельцем похоронного бюро в небольшом городке. В этом же городе было еще одно похоронное бюро, жена владельца которого работала на телефонной станции. Поэтому когда родственники умершего звонили и просили соединить с похоронным бюро ловкая жена тут же соединяла их со своим мужем. Поэтому Строугер оказался перед выбором: либо изобрести автоматический коммутатор, либо закрыть дело. Он предпочел первый вариант. Так был изобретен телефонный коммутатор. За истекшие 100 лет мало что изменилось.

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

Если соединение установлено, то задержка при передачи составит 5 msec. на 1000 км. Если соединение установлено, то нет  опасности что во время разговора Вы услышите сигнал занято.

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

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

Основные различия этих методов:

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

16. Принципы маршрутизации. Алгоритмы маршрутизации

 

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

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

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

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

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

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

Принцип оптимальности

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

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

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

 

Маршрутизация по наикратчайшему пути

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

Проиллюстрируем концепцию наикратчайшего пути на рис. 5-6. Расстояние можно измерять в скачках, а можно в километрах. Тогда маршрут АВС длиннее  маршрута АВЕ. Возможны и другие меры. Например, дуги графа могут быть размечены величиной средней задержки для пакетов. В графе с такой разметкой наикратчайший путь - наибыстрейший путь, которые не обязательно имеет минимальное число скачков или километров.

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

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

На рис. 5-6 показан процесс построения маршрута. Самым интересным является момент 5-6 (е). Здесь в окрестности  вершины Н оказывается вершина F, у которой пробная метка показывает, что путь через F короче. Поэтому метка у вершины Н меняется так, как если бы маршрут шел через вершину Н.

Маршрутизация по вектору расстояния

Все современные сети используют динамическую маршрутизацию, а не статическую. Один из наиболее популярных алгоритмов - маршрутизация по вектору расстояния. Этот алгоритм построен на идеях алгоритмов Беллмана-Форда и Форда-Фолкерсона. Он изначально использовался в сети ARPA и используется по сей день под названием RIP алгоритма. Он используется в сети Novell, AppleTalk, Cisco маршрутизаторах.

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

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

Рассмотрим пример на рис. 5-10. На рис. 5-10 (а) показана подсеть. На рис. 5-10(в) показаны вектора, которые J маршрутизатор получил от своих соседий и его замеры задержек до соседей. Там же показана итоговая таблица маршрутизации, которую J маршрутизатор вычислит на основании этой информации.