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

Метод биполярного кодирования с альтернативной инверсией

Одной из модификаций метода NRZ является метод биполярного кодирования с альтернативной инверсией (Bipolar Alternate Mark Inversion, AMI). В этом методе (рис. 2.16, б) используются три уровня потенциала — отрицательный, нулевой и положительный. Для кодирования логического нуля используется нулевой потен­циал, а логическая единица кодируется либо положительным потенциалом, либо отрицательным, при этом потенциал каждой новой единицы противоположен потенциалу предыдущей.

Код AMI частично ликвидирует проблемы постоянной составляющей и отсут­ствия самосинхронизации, присущие коду NRZ. Это происходит при передаче длинных последовательностей единиц. В этих случаях сигнал на линии представляет собой последовательность разнополярных импульсов с тем же спектром, что и у кода NRZ, передающего чередующиеся нули и единицы, то есть без постоянной составляющей и с основной гармоникой N/2 Гц (где N — битовая скорость переда­чи данных). Длинные же последовательности нулей также опасны для кода AMI, как и для кода NRZ — сигнал вырождается в постоянный потенциал нулевой амплитуды. Поэтому код AMI требует дальнейшего улучшения, хотя задача упрощается — осталось справиться только с последовательностями нулей.

В целом, для различных комбинаций бит на линии использование кода AMI приводит к более узкому спектру сигнала, чем для кода NRZ, а значит, и к более высокой пропускной способности линии. Например, при передаче чередующихся единиц и нулей основная гармоника fo имеет частоту N/4 Гц. Код AMI предоставляет также некоторые возможности по распознаванию ошибочных сигналов. Так, нарушение строгого чередования полярности сигналов говорит о ложном импульсе или исчезновении с линии корректного импульса. Сигнал с некорректной полярностью называется запрещенным сигналом (signal violation).

В коде AMI используются не два, а три уровня сигнала на линии. Дополнительный уровень требует увеличение мощности передатчика примерно на 3 дБ для обеспечения той же достоверности приема бит на линии, что является общим недостатком кодов с несколькими состояниями сигнала по сравнению с кодами, которые различают только два состояния.

Потенциальный код с инверсией при единице

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

(Non Return to Zero with ones Inverted, NRZI). Этот код удобен в тех случаях, когда использование третьего уровня сигнала весьма нежелательно, например в оптичес­ких кабелях, где устойчиво распознаются два состояния сигнала — свет и темнота. Для улучшения потенциальных кодов, подобных AMI и NRZI, используются два метода. Первый метод основан на добавлении в исходный код избыточных бит, содержащих логические единицы. Очевидно, что в этом случае длинные последовательности нулей прерываются и код становится самосинхронизирующимся для любых передаваемых данных. Исчезает также постоянная составляющая, а значит, еще более сужается спектр сигнала. Но этот метод снижает полезную пропускную способность линии, так как избыточные единицы пользовательской информации не несут. Другой метод основан на предварительном «перемешивании» исходной информации таким образом, чтобы вероятность появления единиц и нулей на ли­нии становилась близкой. Устройства, или блоки, выполняющие такую операцию, называются скрэмблерами (scramble — свалка, беспорядочная сборка). При скремблировании используется известный алгоритм, поэтому приемник, получив двоич­ные данные, передает их на дескрэмблер, который восстанавливает исходную последовательность бит. Избыточные биты при этом по линии не передаются. Оба метода относятся к логическому, а не физическому кодированию, так как форму сигналов на линии они не определяют. Более детально они изучаются в следующем разделе.

Биполярный импульсный код

Кроме потенциальных кодов в сетях используются и импульсные коды, когда дан­ные представлены полным импульсом или же его частью — фронтом. Наиболее простым случаем такого подхода является биполярный импульсный код, в котором единица представлена импульсом одной полярности, а ноль — другой (рис. 2.16, в). Каждый импульс длится половину такта. Такой код обладает отличными самосинхронизирующими свойствами, но постоянная составляющая может присутство­вать, например, при передаче длинной последовательности единиц или нулей. Кроме того, спектр у него шире, чем у потенциальных кодов. Так, при передаче всех нулей или единиц частота основной гармоники кода будет равна N Гц, что в два раза выше основной гармоники кода NRZ и в четыре раза выше основной гармоники кода AMI при передаче чередующихся единиц и нулей. Из-за слишком широкого спектра биполярный импульсный код используется редко.

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

В локальных сетях до недавнего времени самым распространенным методом коди­рования был так называемый манчестерский код (рис. 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.

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

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