Информационные сети

Мы уже сталкивались с подобными протоколами - пример, старт-стопный протокол. Там n равно 1. Обычно n=2k-1. У получателя и отправителя есть набор последовательных чисел - номеров для кадров, которые отправитель может отправить, не ожидая подтверждения каждого. Эти кадры образуют окно отправки. Аналогично, у получателя есть буфер для получения и временного хранения получаемых кадров - окно получения.

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

Рис. 3-12 показывает работу такого протокола для n=1 в форме диаграммы.

До сих пор мы предполагали, что время доставки кадра и время доставки подтверждения пренебрежимо малы. В некоторых случаях это предположение очевидно не работает. Оно может приводить к серьезным бесполезным тратам пропускной способности канала. Рассмотрим пример, спутниковый канал на 50-Kbps с общей задержкой 500 mсек. Пусть мы хотим использовать протокол 4 для передачи кадров размера 1000 бит. В момент =0 отправитель отправляет первый кадр. В =20mсек кадр полностью отправлен, в =270mсек он принят и в =520mсек отправитель получил подтверждение. Эти цифры говорят о том, что отправитель был блокирован в течении 500/520, т.е. 96% времени. А это - потеря пропускной способности канала.

Эта проблема есть следствие правила, по которому отправитель ждет подтверждения прежде, чем пошлет следующий кадр. Это требование можно ослабить - разрешить отправителю отправлять до w кадров, не ожидая их подтверждения. Надлежащим выбором значения w отправитель может заполнить все время, необходимое на оправку кадра и получение его подтверждения. В вышеприведенном примере w должно быть по крайней мере 26. Это как раз то количество кадров, какое отправитель успеет отправить за 520 mсек. прежде, чем придет подтверждение на кадр 0. Таким образом, неподтвержденными будут 25 из 26 кадров, окно отправителя будет на 26 кадров.

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

Есть два приема для решения этих вопросов: откат и выборочный повтор. При откате все кадры, поступившие после поврежденного, сбрасываются и не подтверждаются. Отправитель по timeout повторно пошлет все кадры, начиная с не подтвержденного. Этот подход показан на рис.3-15 (а). В этом подходе окно у получателя длины 1.

При выборочном повторе у получателя окно длины как и у отправителя. Отправитель отмечает не подтвержденный кадр и перепосылает его. Получатель не передает на сетевой уровень последовательность пакетов, если в ней есть разрывы. Этот подход показан на рис.3-15 b).

Протокол HDLC: основные вопросы организации

Здесь мы познакомимся с группой протоколов давно известных, но по-прежнему широко используемых. Все они имеют одного предшественника - SDLC - Synchronous Data Link Control - протокол управления синхронным каналом, предложенным фирмой IBM в рамках SNA. ISO модифицировало этот протокол и выпустило под название HDLC - High level Data Link Control. МККТТ модифицировало HDLC для X.25 и выпустило под именем LAP - Link Access Procedure. Позднее он был модифицирован в LAPB.

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

На рис.3-24 показана типовая структура кадра. Поле адреса используется для адресации терминала, если их несколько на линии. Для линий точка-точка это поле используется для различия команды от ответа.

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

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

Поле Checksum - это поле используется CRC кодом.

Флаговые последовательности 01111110 используются для разделения кадров и постоянно передаются по незанятой линии в ожидании кадра. Существуют три вида кадров: Information, Supervisory, Unnumbered. Организация поля control для этих трех видов кадров показана на рис.3-25. Как видно из размера поля Seq в окне отправителя может быть до 7 неподтвержденных кадров. Поле Next используется для посылки подтверждения вместе с передаваемым кадром. Подтверждение может быть в форме номера последнего правильно переданного кадра, а может быть в форме первого не переданного кадра. Какой вариант будет использован - это параметр.

Разряд P/F использует при работе с группой терминалов. Когда компьютер приглашает терминал к передаче он устанавливает этот разряд в P. Все кадры, посылаемые терминалами имеют здесь P. Если это последний кадр, посылаемый терминалом, то здесь стоит F.

Supervisory кадры имеют четыре типа кадров. Тип 0 - уведомление в ожидании следующего кадра (RECEIVE READY). Используется когда нет встречного трафика, чтобы передать уведомление в кадре с данными.

Тип 1 - негативное уведомление (REJECT) - указывает на ошибку при передаче. Поле Next указывает номер кадра, начиная с которого надо перепослать кадры.

Тип 2 - RECEIVE NOT READY. Подтверждает все кадры, кроме указанного в Next. Используется, чтобы сообщить источнику кадров об необходимости приостановить передачу в силу каких-то проблем у получателя. После устранения этих проблем получатель шлет RECEIVE REDAY, REJECT или другой надлежащий управляющий кадр.

Тип 3 - SELECTIVE REJECT - указывает на необходимость перепослать только кадр, указанный в Next. LAPB и SDLC не используют этого типа кадров.

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

Все протоколы имеют команду DISConnect - для указания о разрыве соединения. SNRM и SABM - для установки счетчиков кадров в ноль, сброса соединения с начальное состояние, установки соподчиненности на линии. Команда FRMR - указывает на повреждение управляющего кадра (например, контрольная сумма верная, а вот значения полей противоречивы).

Сравнительная характеристика протоколов УКД Интернет: SLIP и PPP

Здесь мы рассмотрим протоколы, которые используются для каналов точка-точка в Internet. Соединения точка точка-точка возникают между маршрутизаторами в Internet. Вторая часто встречающаяся ситуация для таких соединений - соединение из дома через модем с сервис провайдером в Internet. Эта ситуация показана на рис.3-26.

Для соединений маршрутизатор-маршрутизатор и хост-маршрутизатор через телефонную линию было предложено два протокола SLIP и PPP.

SLIP - Serial Line IP

SLIP - наиболее старый из этих двух протоколов. Он был создан в 1984 Rick Adams для соединения SUN рабочих станций через модем. Этот протокол был описан в RFC 1055. Этот протокол очень прост: он вставляет специальные флаг-байты в начало и конец IP пакета.

Последние версии этого протокола также осуществляют сжатие TCP и IP заголовков у последовательных пакетов, так как они несут очень много одинаковой информации. Последняя версия этого протокола описана в RFC 1144.

Этот протокол имеет ряд серьезных недостатков - он не занимается контролем и исправлением ошибок, оставляя это протоколам верхних уровней. Во вторых, он работает только с IP пакетами и не может работать ни с какими другими. В современных условиях, когда Internet объединяет самые разнообразные сети - это серьезное припятствие.

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

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

В пятых, нет стандарта на этот протокол и существует много его версий, не все из которых совместимы.

PPP - протокол точка-точка

Чтобы исправить это положение IETF (Internet Engineering Task Force) создало группу, которой было поручено разработать новый протокол. В результате ее усилий появился протокол РРР (Point-to-Point Protocol), определенный в RFC 1661, 1662,1663. РРР обеспечивает обнаружение ошибок, поддерживает разные протоколы, позволяет динамически выделять IP адрес только на период соединения, выполняет аутентификацию абонентов и имеет ряд других преимуществ перед SLIP.

РРР обеспечивает три протокола:

Распознавание кадров, т.е. однозначно определяет начало нового и конец кадра. Здесь же происходит обнаружение ошибок.

Протокол управления линией, т.е. активизация линии, ее проверка, определение основных параметров передачи в диалоге, корректное завершение передачи со сбросом параметров. Этот протокол называет LCP( Link Control Protocol).

Протокол для определения основных параметров между сетевыми уровнями, который обеспечивает независимость от реализации сетевого уровня. Выбранный метод предполагает наличие разных NCP (Network Control Protocol) на каждом поддерживаемом сетевом уровне.

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

После этого следует обмен NCP пакетами для конфигурирования сетевого уровня. В частности здесь происходит временное присваивание РС IP адреса, который действует только на период соединения. Это происходит если обе стороны хотят использовать TCP/IP стек.

Теперь когда РС стала полноправной машине в Internet она может обмениваться IP пакетами с другими машинами. Когда пользователь закончит работу, NCP разрывает соединение с сетевым уровнем и освобождает ранее занятый IP адрес. После этого LCP протокол разрывает соединение на канальном уровне. А затем компьютер говорит модему "Положи трубку".

РРР кадры имеют формат очень близкий к HDLC кадрам. Основное различие в том, что РРР байт ориентированный, а HDLC - бит ориентированный. Для РРР не возможен кадр в 30,25 байт, а у HDLC такое может быть. РРР кадр показан на рис.3-27.

Все РРР кадры начинаются со стандартного 01111110 байта. Поле Адрес также по умолчанию равно 11111111. Поле Control по умолчанию равно 00000011, что означает - Unnumbered кадр, т.е. не предполагается нумерации передаваемых кадров и подтверждений в их получении. В случае ненадежной среды передачи данных есть вариант надежной передачи, описанный в RFC 1663/

Так как поля Address и Control - константы, то LCP протокол опускает их, экономы два байта на передаче. В поле Protocol указывается какой тип пакетов будет в поле Payload. Там допускаются LCP, NCP, IP, IPX, Apple Talk и другие. Поле Payload имеет переменную длину, по умолчанию она равна 1600 байт.

На диаграмме 3-28 показаны основные фазы установления соединения и его разрыв.

УКД в широковещательных сетях. Методы управления доступом к среде передачи; протоколы с состязанием

УКД в широковещательных сетях (прежде всего - ЛВС) принято разбивать на два подуровня: LLC-Logical Link Control и MAC-Media Access Control. Первый подуровень решает традиционные для УКД проблемы, а второй - специфическую проблему широковещательных сетей: проблему доступа многих станций к единственной, общей среде передачи.

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

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

Станции. Модель состоит из Nнезависимых станций (компьютеров, телефонов, факс-машин и т.п.). На каждой работает пользователь или программа, которые генерируют кадры для передачи. Вероятность, появления кадра в интервале [t1, t2] равна v(t2-t1), где v константа. Предполагается, что если кадр сгенерирован, то новый не появится, пока не будет передан первый.

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

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

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

Дискретное время. Время разбивается на дискретные интервалы - слоты. Кадр начинает передаваться только в начале слота. Слот может соответствовать нескольким кадрам, если это слот ожидания, он может содержать коллизию, либо успешную передачу.

Обнаружение несущей. Станция всегда определяет занят ли канал прежде, чем использовать его. Если он занят, то ни одна станция не начинает передачу.

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

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

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

ALOHA

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

Мы здесь рассмотрим два варианта системы: чистая ALOHA и слотированная, т.е. разбитая на слоты. Основное различие - в первом случае никакой синхронизации пользователей не требуется, во втором она нужна.

Чистая ALOHA

Идея чистой ALOHA проста - любой пользователь пытается передать сообщение. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, то он видит возникновение конфликта при передаче. Эта обратная связь в среде LAN происходит практически мгновенно, в системах спутниковой связи задержка составляет около 270 mсек.

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

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

Эффективность системы ALOHA из за большого количества коллизий очень низка и составляет примерно 18%. Результат не очень вдохновляющий.

Слотированная ALOHA

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

Протоколы множественного доступа с обнаружением несущей

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

Протоколы, которые реализую именно эту идею - определить есть ли передача и действовать соответствующе, называются протоколами с обнаружением несущей CSMA (Carrier Sense Multiply Access).

Настойчивые и не настойчивые CSMA

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

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

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

CSMA с обнаружением коллизий

Настойчивые и ненастойчивые CSMA протоколы несомненно есть улучшение ALOHA, т.к. они начинают передачу только проверив состояние канала. Другим улучшением, которое можно сделать, - станции должны уметь определять коллизии как можно раньше, а не по окончании отправки кадра. Это экономит время и пропускную способность канала. Такой протокол, известный как CSMA/CD - Carrier Sense Multiply Access with Collision Detection , широко используется в локальных сетях.

На рис. 4-5 показана модель, которая используется во многих протоколах. В момент t0 станция заканчивает передачу очередного фрейма. Все станции, у которых есть кадр для передачи начинают передачу. Естественно происходят коллизии, который быстро обнаруживаются, сравнивая отправленный сигнал с тем который есть на линии. Обнаружив коллизию, станция сразу прекращает передачу на случайный интервал времени, после чего все начинается сначала. Таким образом в работе протокола CSMA/CD можно выделить три периода: состязаний, передачи и ожидания, когда нет кадров для передачи.

Рассмотрим подробнее алгоритм состязаний. Сколько времени станции, начавшей передачу, нужно, чтобы определить коллизию. Обозначим t время распространения сигнала до самой удаленной станции на линии. Для коаксиала в 1 км t = 5 ms. Тогда минимальное время для определения коллизии будет 2t. Поэтому, станция не может быть уверена, что она захватила канал до тех пор, пока в течении 2t секунд не будет коллизий. Поэтому, весь период состязаний разбивается на слоты по 2t секунд по одному биту на слот. Захватив канал, станция может далее передавать кадр с любой скоростью.

УКД в широковещательных сетях. Бесконфликтные протоколы предоставления канала. Протоколы беспроводной связи.

Хотя в протоколе CSMA/CD коллизии могут возникать только в период состязаний, тем не менее при больших t и коротких кадрах они съедают часть пропускной способности канала. Здесь мы рассмотрим как можно избежать этих коллизий.

Мы будем предполагать, что у нас есть N станций с адресами от 0 до N-1. Все адреса уникальны. Основным является вопрос: как определить кто будет владеть каналом, когда закончиться текущая передача?

Bit-Map протокол

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

Теперь рассмотрим производительность этого метода. Будем для удобства измерять время во временных слотах периода состязаний. Будем так же предполагать, что передача одного кадра будет занимать ровно d слотов. Для станции с небольшим номером, например, 0 или 1 время ожидания на передачу в среднем будет 1.5N, потому что она, пропустив начала состязаний, будет ждать 0.5N в первом периоде состязаний и N единиц времени во втором. Другая участь у станций со старшими номерами. Эти станции будут ожидать в среднем N/2 слотов до начала передачи. Таким образом, в среднем любая станция должна будет ждать N слотов до передачи.

При небольшой нагрузке нетрудно рассчитать эффективность метода - d/(d+N), где N - накладные расходы на передачу кадра. При плотной загрузке, когда практически каждая станция каждый раз что-то посылает, накладные расходы будут 1 бит на кадр, т.е. d/(d+1).

Адресный счетчик

В этом методе каждая станция, желающая передать выставляет свой адрес бит за битом, начиная со старшего разряда. Эти разряды подвергаются логическому сложению. Если станция выставила на очередном шаге 0, а результат логического сложения - 1, то она должна ждать и в текущих состязаниях участия не принимает. Этот метод проиллюстрирован на рис. 4-7. Эффективность этого метода d/(d + lnN)/

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

Протоколы беспроводной связи

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

Обычная конфигурация таких сетей - в здании размещается сеть стационарных приемопередающих станций, соединенных кабелем. Если настроить приемопередатчики станций и компьютеров на расстояние 3-4 метра, то каждая комната в здании образует ячейку. В каждой ячейке действует только один канал, пропускную способность которого разделяют все машины этой ячейки. Обычна она равна 1-2 Мбита/сек.

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

Естественно было бы попытаться использовать протокол CSMA для радио канала. Однако, в нашем случае возникают проблемы. Рассмотрим рис. 4-11. Станции А и В могут взаимодействовать, станция С может взаимодействовать с B и D, но не с А. Рассмотрим, что будет происходить когда А будет передавать В (рис. 4-11 а). Поскольку С вне действия А, то она не слышит передачи А и может начать свою, что приведет к коллизии. Эта проблема станции, не способной увидеть конкурента называется проблемой спрятанной станции.

Рассмотрим теперь что будет если В начнет передачу, например, А. С услышит эту передачу и ложно заключит что она не может передавать станции D, хотя она свободна. Эта ситуация называется проблемой мнимой станции.

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

MACA

Первые протоколы, разработанные для беспроводных сетей относились к протоколам класса МАСА (Multiple Access Collision Avoidance). Идея заключалась в том, чтобы отправитель принудил получателя послать короткое сообщение перед началом передачи. Все станции, находящиеся в зоне действия получателя, услышат этот сигнал и не начнут передачи. Этот протокол иллюстрирует рис. 4-12.

Рассмотрим как А передает сообщение В. А начинает с передачи специального сообщения RTS (Request To Send). Это короткое сообщение (30 байт) несет информацию (например, длину) о настоящем сообщении. В в ответ шлет CLS (Clear To Send) сообщение. В этом сообщении повторяются данные о сообщении, которое последует. По получении CTS А начинает передачу.

Теперь рассмотрим как другие станции реагируют на RTS и CTS сообщения. Станции близко расположенные к A слышат RTS и знают что надо хранить молчание достаточное время, чтобы передать сообщение. Станции близкие к В слышат CTS и тоже не будут инициировать передачу для В. Эти ситуации показаны на рис. 4-12.

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

Основные задачи сетевого уровня модели ВОС. Виды сервиса

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

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

Сервис, предоставляемый транспортному уровню

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

Сервис сетевого уровня разрабатывался в следующих целях:

· сервис должен быть независимым от технологии передачи, используемой в подсети;

· транспортный уровень должен быть независим от числа, типа и топологии подсети;

· адрес подсети доступный на транспортном уровне должен иметь унифицированную форму по всей сети.

В остальных вопросах разработчик сетевого уровня свободен в разработке сервиса сетевого уровня. Однако эта свобода выливается в жестокие баталии. Основной их причиной является вопрос: должен ли сетевой уровень быть ориентированным на соединения или нет?

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

Отсюда следует что сервис на сетевом уровне должен быть не ориентирован на соединения, с примитивами типа SEND_PACKET, RECEIVE_PACKET. Никакой проверки упорядочения пакетов, управления потоком не должно здесь быть. Это все делают хосты.. Каждый пакет должен нести полный адрес доставки, поскольку они отправляются абсолютно независимо.

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

· прежде чем передача начнется, передающая сторона должна установить соединение с равнозначной сущностью на принимающей стороне. При этом ей должен быть сообщен специальный идентификатор, который используется в течении всей передачи;

· когда соединение установлено, два процесса начинают переговоры о параметрах, качестве и стоимости предоставляемого сервиса;

· передача происходит в двух направлениях, а пакеты посылаются в определенном порядке;

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

Другие возможности такие как гарантированная доставка, явное подтверждение доставки, приоритетные пакеты являются не обязательными. Как мы уже отмечали в главе 1, сервис не ориентированный на соединение подобен обычной почте, а ориентированный на соединение - телефонной системе.

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

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

Так каким же должен быть сетевой уровень надежным, ориентированным на соединения или не надежным без соединений? Два ответа на этот вопрос предоставляют Internet и ATM. В Internet сетевой уровень без соединений и предполагается не надежным. В АТМ - с соединениями и надежный.

Внутренняя организация сетевого уровня

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

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

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

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

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

Заметим, что каждый процесс должен указать ожидаемое время освобождения виртуального канала. В противном случае возникнут проблемы с принятием решения при освобождении виртуального канала: может быть одна из машин на маршруте зависла?

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

У каждой дейтаграммы должен быть полный адрес доставки. В больших сетях этот адрес может быть достаточно большим ( десятки байт). Когда пакет поступает маршрутизатор по таблице и адресу определяет по какой линии надо отправить эту дейтаграмму и посылает ее туда.

Сравнение подсетей с виртуальными каналами и дейтаграммами

Результаты сравнения подсетей этих двух видов собраны на рис. 5-2.

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

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

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

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

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

Следует подчеркнуть что качество сервиса (с соединением или без) и внутренняя организация подсети - виртуальные каналы или дейтаграммы - вопросы независимые. Теоретически возможны все четыре комбинации. Возможны сервис с соединением на дейтаграммных подсетях когда надо обеспечить очень надежный сервис. Сервис бес соединения над виртуальными каналами - TCP/IP над АТМ. Примеры всех четырех случаев представлены на рис. 5-3.

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

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

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

Стабильность также весьма важный фактор. Существуют алгоритмы маршрутизации, которые никогда не сходятся к какому-либо равновесному состоянию как бы долго они не работали. Справедливость значит, что все пакеты будут обслуживаться равномерно, ни какому направлению не будет отдаваться предпочтение, для всех абонентов будет всегда выбираться оптимальный маршрут. Надо отметить, что справедливость и оптимальность часто могут вступать в противоречие друг с другом. На рис. 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 маршрутизатор вычислит на основании этой информации.

Адресация в IP-сетях: классы адресов, маски

Internet представляет собой объединение подсетей, которые называются автономными системами. В Internet не какой-либо регулярной, специально предусмотренной структуры подсетей. Он образован из соединения большого числа подсетей, среди которых можно выделить несколько основных backbone. На рис. 5-44 показана схема соединения таких backbone. IP протокол - это то что соединяет все эти автономные системы вместе.

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

IP адресация

Каждая машина в Internet имеет уникальный IP адрес. Он состоит из адреса сети и адреса машины в этой сети. На рис. 5-47 показаны форматы IP адресов. Классы A позволяет адресовать до 126 сетей по 16 миллионов машин, B - 16382 сетей по 64К машин, C - 2 миллиона сетей по 256 машин, D - групповая передача. Адреса выделяет только NIC - Network Information Center. Несколько адресов, показанных рис. 5-48, имеют специальное назначение. Адрес из одних 0 используется при загрузке машины.

Подсети

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

Решением этих проблем является разделение сети на части, которые не видны из вне, но адресуемы изнутри. Эти части называются посети. Мы уже отмечали в главе 1, что термин подсеть в Интернет имеет особый смысл. Итак, подсеть - это часть сети, не видимая извне. Изменение адреса подсети или введение новой подсети не требует обращения в NIC или изменений какой-либо глобальной базы данных. На рис. 5-49 показано разбиение сети класса В на подсети.

Для того чтобы понять как используется адрес подсети надо проследить как маршрутизатор использует IP адрес. Есть две таблицы (сеть, 0) IP адрес и (0,машина) IP адрес. Добавляется таблица (сеть, подсеть,0) и (сеть, подсеть, машина). С помощью операции И выделяется адрес подсети с помощью маски, показанной на рис. 5-49.

Групповая адресация в Internet

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

В IP сетях групповая адресация поддерживается с помощью адресов класса D. 28 разрядов есть для адресации группы, т.е. можно адресовать 250 миллионов групп. При передаче сообщения группе делается все возможное чтобы каждый член группы получил сообщение, но это не гарантируется.

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

224.0.0.1 - все система в данной ЛВС;

224.0.0.2 - все маршрутизаторы в данной ЛВС;

224.0.0.5 - все OSPF маршрутизаторы в данной ЛВС;

224.0.0.6 - все выделенные OSPR маршрутизаторы в данной ЛВС.

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

Групповая адресация реализуется специальным групповым маршрутизатором, который может размещаться отдельно от обычного маршрутизатора. Раз в минуту каждый групповой маршрутизатор рассылает через канальный уровень запрос всем хостам ЛВС указать каким группам принадлежат их процессы. Эти запросы и ответы на них регулируются IGMP протоколом (Internet Group Management Protocol), который очень похож на ICMP. Он описан в RFC 1112.

Отображение IP-адресов на физические (локальные) адреса. Отображение доменных имен на IP-адреса

Address Resolution Protocol

Хотя каждая машина в Internet имеет уникальный IP адрес, но при передаче пакета через сеть от этого мало пользы, так как канальный уровень не понимает IP адресов. Как правило машина подключена к ЛВС через сетевую карту, которая понимает только ЛВС адреса канального уровня, например, Ethernet адрес. Этот адрес имеет 48 разрядов. Сетевая карта знает только такие адреса и ничего об 32 разрядных IP.

Как отобразить 32 разрядный IP адрес на адреса канального уровня, например, Ethernet адрес? Для объяснения воспользуемся рис. 5-51.

Когда машина 1 посылает сообщение машине 2, то через DNS определяется IP адрес места назначения. Далее для отображения IP адреса на Ethernet адрес посылается в подсеть запрос у кого такой IP адрес. Машина с указанным адресом шлет ответ. Протокол, который реализует рассылку запросов и сбор ответов - ARP протокол. Практически каждая машина в Internet имеет этот протокол.

Теперь рассмотрим случай когда обращение идет в другую сеть. Здесь два решения - есть определенный маршрутизатор, который принимает все сообщения, адресованные определенной сети или группе адресов - proxy ARP. Этот маршрутизатор знает как найти адресуемую машину. Другое решение - выделенный маршрутизатор, который управляет маршрутизацией удаленного трафика. Машина определяет, что обращение идет в удаленную сеть и шлет сообщение на этот маршрутизатор.