Тема 2. Методы доступа

Метод доступа – это способ определения того, какая из рабочих станций сможет следующей использовать ЛВС. То, как сеть управляет доступом к каналу связи (кабелю), существенно влияет на ее характеристики. Примерами методов доступа являются:

— множественный доступ с прослушиванием несущей и разрешением коллизий (Carrier Sense Multiple Access with Collision Detection – CSMA/CD);

— множественный доступ с передачей полномочия (Token Passing Multiple Access – TPMA) или метод с передачей маркера;

— множественный доступ с разделением во времени (Time Division Multiple Access – TDMA);

— множественный доступ с разделением частоты (Frequency Division Multiple Access – FDMA) или множественный доступ с разделением длины волны (Wavelength Division Multiple Access – WDMA).

CSMA/CD

Алгоритм множественного доступа с прослушиванием несущей и разрешением коллизий приведен на рис. 4.5.

Рис. 4.1 Алгоритм CSMA/CD

Метод множественного доступа с прослушиванием несущей и разрешением коллизий (CSMA/CD) устанавливает следующий порядок: если рабочая станция хочет воспользоваться сетью для передачи данных, она сначала должна проверить состояние канала: начинать передачу станция может, если канал свободен. В процессе передачи станция продолжает прослушивание сети для обнаружения возможных конфликтов. Если возникает конфликт из-за того, что два узла попытаются занять канал, то обнаружившая конфликт интерфейсная плата, выдает в сеть специальный сигнал, и обе станции одновременно прекращают передачу. Принимающая станция отбрасывает частично принятое сообщение, а все рабочие станции, желающие передать сообщение, в течение некоторого, случайно выбранного промежутка времени выжидают, прежде чем начать сообщение.

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

TPMA

Алгоритм множественного доступа с передачей полномочия, или маркера, приведен на рис. 4.6.

Рис. 4.1 Алгоритм TPMA

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

Маркер (token), или полномочие, – уникальная комбинация битов, позволяющая начать передачу данных.

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

Пакет распространяется по ЛВС от адаптера к адаптеру, пока не найдет своего адресата, который установит в нем определенные биты для подтверждения того, что данные достигли адресата, и ретранслирует его вновь в ЛВС. После чего пакет возвращается в узел из которого был отправлен. Здесь после проверки безошибочной передачи пакета, узел освобождает ЛВС, выпуская новый маркер. Таким образом, в ЛВС с передачей маркера невозможны коллизии (конфликты). Метод с передачей маркера в основном используется в кольцевой топологии.

Данный метод характеризуется следующими достоинствами:

— гарантирует определенное время доставки блоков данных в сети;

— дает возможность предоставления различных приоритетов передачи данных.

Вместе с тем он имеет существенные недостатки:

— в сети возможны потеря маркера, а также появление нескольких маркеров, при этом сеть прекращает работу;

— включение новой рабочей станции и отключение связаны с изменением адресов всей системы.

TDMA

Множественный доступ с разделением во времени основан на распределении времени работы канала между системами (рис.4.7).

Доступ TDMA основан на использовании специального устройства, называемого тактовым генератором. Этот генератор делит время канала на повторяющиеся циклы. Каждый из циклов начинается сигналом Разграничителем. Цикл включает n пронумерованных временных интервалов, называемых ячейками. Интервалы предоставляются для загрузки в них блоков данных.

Рис. 4.1 Структура множественного доступа с разделением во времени

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

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

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

FDMA

Доступ FDMA основан на разделении полосы пропускания канала на группу полос частот (Рис. 4.8), образующих логические каналы.

Широкая полоса пропускания канала делится на ряд узких полос, разделенных защитными полосами. Размеры узких полос могут быть различными.

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

Рис. 4.1 Схема выделения логических каналов

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

Метод доступа FDMA относительно прост, но для его реализации необходимы передатчики и приемники, работающие на различных частотах.

Вопросы

1. Что такое топология?

2. Перечислить наиболее используемые типы топологий?

3. Охарактеризовать топологию Общая шина и привести примеры использования данной топологии.

4. Какие сетевые технологии используют топологию Общая шина?

5. Охарактеризовать топологию Кольцо и привести примеры этой топологии.

6. В каких случаях используют топологию Кольцо?

7. Охарактеризовать топологию Звезда и привести примеры использования этой топологии.

8. К какой топологии относится сеть при подсоединении всех компьютеров к общему концентратору?

9. Привести примеры и охарактеризовать древовидную топологию.

10. Что такое ячеистая топология и в каких случаях она используется?

11. Что такое метод доступа и как влияет метод доступа на передачу данных в сети?

12. Какие существуют методы доступа?

13. Охарактеризовать метод доступа с прослушиванием несущей и разрешением коллизий.

14. При каком методе доступа обе станции могут одновременно начать передачу и войти в конфликт?

15. В каких сетевых технологиях используется метод CSMA/CD?

16. Охарактеризовать метод доступа с разделением во времени и перечислить в каких случаях используется данный метод.

17. Что такое маркер?

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

19. Охарактеризовать метод доступа с передачей полномочия.

20. Охарактеризовать метод множественного доступа с разделением частоты.

21. Какие существуют варианты использования множественного доступа с разделением во времени?

Источник

Методы доступа. Наиболее популярные ситуации

Статья в первую очередь расчитана на начинающих разработчиков, либо для тех, кто только начинает переходить от процедурного стиля программирования к ООП, посему матерых гуру просьба не вгонять в минуса 🙂

Права доступа к свойствам и методам — это на первый взгляд всего лишь три слова: private, protected и public. Но что скрывается за ними? Какие преимущества это дает в разработке? И как их правильно использовать? Здесь, как и во всех других аспектах программирования, без практики не разобраться…

Одна из трех основных концепций ООП — наследование (другие две: инкапсуляция и полиморфизм). Вобщем-то именно для нее и были реализованы права доступов. Основанная идея наследования: Дочерний объект, при наследовании (extend) родителя перенимает себе все родительские методы и свойства, а так же может обзавестись своими собственными. Понимая эту базу, можно перейти в всему что находится ниже…

Private — объявляет метод или свойство доступным только в том классе в котором он присутствует. Тоесть к private методам и свойствам мы не можем обращаться ни из объектов, ни из дочерних классов.

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

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

Сразу хочу заметить, что при наследовании, методы доступа изменяться могут только к более лояльным. тоесть в следующей последовательности, но не обратно: private → protected → public

Так же методы могут быть final тоесть такими, которые невозможно переопределить в классах потомках.

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

Практика

Похожим способом ведут себя и сеттеры (setter\’s), когда нам необходимо иметь возможность установить значение переменной, но не читать ее напрямую, так как она, к примеру, должна быть преобразована прежде чем быть использованной. Пример метода сеттера:

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

if (empty($value)) <
$value = //. тут значение создается по каким-то известным параметрам и повлиять извне на него мы никак не сможем
>

Хорошей практикой является сокрытие всех свойств методом private и, в зависимости от нужд, создавать для них сеттеры или геттеры, но нужно быть внимательным, что если для свойства существует и сеттер и геттер, а дополнительной логики обработки данных нет, то не проще ли их убрать, а свойство сделать публичным? 🙂

Источник

Методы доступа

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

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

— множественный доступ с контролем несущей и с предотвращением коллизий;

— доступ с передачей маркера;

— доступ по приоритету запроса.

Первый метод применяется исключительно в сетях с логической общей шиной. Все компьютеры такой сети имеют непосредственный доступ к общей шине, поэтому она может быть использована для передачи данных между двумя компьютерами. Одновременно все компьютеры сети имеют возможность немедленно (с учетом задержки распространения сигнала по физической среде) получить данные, которые любой из компьютеров начал передавать на общую шину. Говорят, что кабель, к которому подключены все станции, работает в режиме множественного доступа (Multiply Access, MA). Суть метода состоит в следующем:

а) станция, желающая передать данные, должна убедиться, что разделяемая среда свободна. Это достигается прослушиванием основной гармоники сигнала, которая называется несущей частотой (carrier-sense, CS). Признаком занятости среды является отсутствие на ней несущей частоты, которая при манчестерском способе кодирования равна 5 – 10 МГц, в зависимости от последовательности единиц и нулей, передаваемых в данный момент. Если среда свободна, то узел может начать передачу данных. После окончания передачи данных все узлы сети обязаны выдержать технологическую паузу (Inter Packet Gap) в 9,6 мкс. Эта пауза нужна для приведения адаптеров в исходное состояние, а также для предотвращения монопольного захвата среды одной станцией;

б) после окончания технологической паузы узлы имеют право начать передачу данных, так как среда свободна. При передаче данных все станции одновременно наблюдают за возникающими на кабеле сигналами. Если передаваемые и наблюдаемые сигналы отличаются, то фиксируется обнаружение коллизии (collision detection, CD) (столкновения пакетов);

в) если станция обнаружила коллизию, то, для увеличения вероятности скорейшего обнаружения этого столкновения всеми станциями сети, она прерывает передачу своих данных и усиливает ситуацию коллизии посылкой в сеть специальной последовательности из 32 бит,называемой jam-последовательностью;

На рис.2.8. показана схема возникновения и распространения коллизии.

Рисунок 2.8. Схема возникновения и распространения коллизии

Чем больше компьютеров в сети, тем интенсивнее сетевой трафик, и число коллизий возрастает, а это приводит к замедлению сети.

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

Второй метод – самый непопулярный из всех методов доступа. Используя CSMA/CA, каждый компьютер перед передачей данных в сеть сигнализирует о своем намерении, поэтому остальные компьютеры «узнают» о готовящейся передаче и могут избежать коллизий. Однако широковещательное оповещение увеличивает общий трафик сети и уменьшает ее пропускную способность. Поэтому CSMA/CA работает медленнее, чем CSMA/CD.

Метод доступа с передачей маркера заключается в следующем:

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

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

в) компьютер, распознавший пакет, который адресован ему, принимает этот пакет, устанавливает в маркере специально выделенный бит подтверждения и отправляет связку из маркера и пакета дальше;

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

На рис.2.9. показан метод доступа с передачей маркера.

Рисунок 2.9. Метод доступа с передачей маркера

Доступ по приоритету запроса(demand priority) – относительно новый метод доступа, разработанный для сети Ethernet со скоростью передачи данных 100 Мбит/с – 100VG – AnyLAN.

Этот метод учитывает своеобразную конфигурацию сетей 100VG-AnyLAN, которые состоят только из коммутаторов и оконечных устройств. Коммутатор управляет доступом к кабелю, последовательно опрашивая каждый узел в сети и выявляя запросы на передачу. Станция, желающая передать пакет, посылает специальный низкочастотный сигнал коммутатору и указывает его приоритет. В сети 100VG – AnyLAN используется два уровня приоритетов – низкий и высокий. Низкий уровень приоритета соответствует обычным данным (файловая служба, служба печати и т.п.), а высокий приоритет соответствует данным, чувствительным к временным задержкам (например, мультимедиа).

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

В сетях с использованием доступа по приоритету запроса связь устанавливается только между компьютером – отправителем, коммутатором и компьютером – получателем. Такой вариант более эффективен, чем CSMA/CD, где передача ведется для всей сети. Кроме того, в таких сетях каждый компьютер может одновременно передавать и принимать данные, поскольку в них применяется восьмипроводной кабель, по каждой паре проводов которого сигналы передаются с частотой 25 МГц. На рис.2.10 показан метод доступа по приоритету запроса.

Рисунок 2.10. Метод доступа по приоритету запроса

Источник

Топология

Среди топологических схем наиболее популярными являются (см. рис. 4.1):

Рис. 4.2. Примеры сетевых топологий

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

Рис. 4.3. Различные сетевые топологические схемы

Современные вычислительные системы используют и другие топологии: решетки (А), кубы (В), гипердеревья (Б), гиперкубы и т.д. (см. рис. 4.4). Но так как некоторые вычислительные системы (кластеры) базируются на сетевых технологиях, я привожу и такие примеры. В некоторых системах топология может настраиваться на решаемую задачу.

Рис. 4.4. Некоторые топологии вычислительных систем

Метод доступа к сети

Метод доступа определяет алгоритм, согласно которому узлы сети получают доступ к среде передачи данных, и осуществляют мультиплексирование/ демультиплексирование данных.

В 1970-х годах Норман Абрахамсон вместе с сотрудниками Гавайского университета предложил оригинальный способ решения проблемы доступа к сети, который был назван позднее ALOHA (Aloha на местном гавайском наречии означает приветствие). Этот алгоритм использовался для доступа к радио-каналу большого числа независимых пользователей. ALOHA разрешает всем пользователям передачу тогда, когда им это оказалось нужно. При этом неизбежны столкновения и искажения передаваемых данных. Алгоритм, благодаря обратной связи, позволяет отправителям узнать, были ли данные в процессе передачи искажены. Если зарегистрировано такое столкновение, все вовлеченные участники выжидают некоторое время и предпринимают повторную попытку. Время выдержки выбирается случайным образом, что делает повторные столкновения менее вероятными.

Большая часть современных сетей базируется на алгоритме доступа CSMA/CD (carrier sensitive multiple access with collision detection), где все узлы имеют равные возможности доступа к сетевой среде, а при одновременной попытке фиксируется столкновение и сеанс передачи повторяется позднее. Этот способ доступа защищен патентами США 406329 и 4099024 (Ксерокс), но IEEE имеет соглашение с этой компание, которое разрешает использовать данные идеи без каких-либо ограничений.. Ряд разновидностей такого протокола рассмотрели Кляйнрок и Тобаги еще в 1975 году. После передачи кадра обычно делается некоторая выдержка. Здесь нет возможности приоритетного доступа и по этой причине такие сети плохо приспособлены для задач управления в реальном масштабе времени. Некоторое видоизменение алгоритма CSMA/CD (как это сделано в сетях CAN или в IBM DSDB) позволяют преодолеть эти ограничения. Доступ по схеме CSMA/CD (из-за столкновений) предполагает ограничение на минимальную длину пакета.

По существу, метод доступа CSMA/CD предполагает широковещательную передачу пакетов (не путать с широковещательной адресацией). Все рабочие станции логического сетевого сегмента воспринимают эти пакеты хотя бы частично, чтобы прочесть адресную часть. При широковещательной адресации пакеты не только считываются целиком в буфер, но и производится прерывание процессора для обработки факта прихода такого пакета. Логика поведения субъектов в сети с доступом CSMA/CD может варьироваться. Здесь существенную роль играет то, синхронизовано ли время доступа у этих субъектов. В случае Ethernet такой синхронизации нет. В общем случае при наличии синхронизации возможны следующие алгоритмы.

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

С целью пояснения этого утверждения рассмотрим случай, когда одна из станций (1) передает пакет самой удаленной ЭВМ (2) в данном сетевом сегменте. Время распространения сигнала до этой машины пусть равно Т. Предположим также, что машина (2) попытается начать передачу как раз в момент прихода пакета от станции (1). В этом случае станция (1) узнает о столкновение лишь спустя время 2Т после начала передачи (время распространения сигнала от (1) до (2) плюс время распространения сигнала столкновения от (2) к (1)). Следует учитывать, что регистрация столкновения это аналоговый процесс и передающая станция должна “прослушивать” сигнал в кабеле в процессе передачи, сравнивая результат чтения с тем, что она передает. Важно, чтобы схема кодирования сигнала допускала детектирование столкновение. Например, сумма двух сигналов с уровнем 0 этого сделать не позволит. Можно подумать, что передача короткого пакета с искажением из-за столкновения не такая уж большая беда, проблему может решить контроль доставки и повторная передача.

Сопоставление эффективности использования канала для различных протоколов произвольного доступа произведено на рис. 4.5.

Рис. 4.5. Сравнение эффективности канала для различных протоколов произвольного доступа и разных значений p

Протокол доступа CSMA может предполагать, что когда канал оказывается свободным, а рабочая станция готова начать передачу, реальная пересылка кадра в рамках заданного временного домена происходит с определенной вероятностью p. С вероятностью 1-р передача будет отложена до следующего временного домена. В следующем домене, если канал свободен с вероятностью р осуществится передача или будет отложена до следующего домена и так далее. Процесс продолжается до тех пор, пока кадр не будет передан. На рисунке эта вероятность р отмечена цифрами после аббревиатуры CSMA-. В случае Ethernet эта вероятность равна единице (CSMA-1) [46, Танненбаум, стр 302], то есть рабочая станция безусловно начнет передачу, если она к этому готова, а канал свободен. Из рисунка видно, что чем меньше эта вероятность, тем выше эффективность (среднее время доступа к сетевой среде также увеличивается). Очевидно, что все разновидности протокола доступа CSMA эффективнее протокола ALOHA в обеих его разновидностях. Связано это с тем, что ни одна станция не начинает передачу, если обнаружит, что сетевая среда занята. Существует еще одна разновидность протокола CSMA (nonpersistent), в которой сетевой субъект при готовности анализирует состояние сетевой среды и, если канал занят, возобновляет попытку спустя псевдослучайный интервал времени, то есть ведет себя так, будто произошло столкновение. Такой алгоритм повышает эффективность использования канала при существенном возрастании усредненной задержки доступа.

Рассмотрим, как можно избежать проблем столкновений пакетов. Пусть к сетевому сегменту подключено N рабочих станций. После передачи любого пакета выделяется N временных интервалов. Каждой подключенной к сетевому сегменту машине ставится в соответствие один из этих интервалов длительностью L. Если машина имеет данные и готова начать передачу, она записывает в это интервал бит, равный 1. По завершении этих N интервалов, рабочие станции по очереди, определяемой номером приписанного интервала, передают свои пакеты (см. рис. 4.6, N=8).

Рис. 4.6. Схема реализации протокола доступа к сети bit-map

В примере на рисунке 4.6 сначала право передачи получают станции 0, 2 и 6, а в следующем цикле 2 и 5 (пересылаемые пакеты окрашены в серый цвет). Если рабочая станция захочет что-то передать, когда ее интервал (домен) уже прошел, ей придется ждать следующего цикла. По существу данный алгоритм является протоколом резервирования. Машина сообщает о своих намерениях до того, как начинает что-либо передавать. Чем больше ЭВМ подключено к сетевому сегменту, тем больше временных интервалов L должно быть зарезервировано и тем ниже эффективность сети. Понятно, что эффективность растет с ростом L.

Для малого числа станций вероятность получить доступ к каналу относительно высока, но уже при k=3-5 вероятность приближается к асимптотическому значению 1/e.

Алгоритм адаптивного обхода

Существует еще один относительно эффективный алгоритм доступа к каналу, называемый адаптивным протоколом перебора. Рассмотрим случай, когда в сетевом сегменте имеется 8 активных станций. На базе этих станций строится дерево (см. рис. 4.7).

Рис. 4.7. Алгоритм адаптивного обхода

Первая ниша доступа следует за очередной успешной передачей и соответствует узлу дерева 0 (на рис. 4.7 не показан). В этом узле всем станциям предоставлена возможность доступа. Если одна из них его получила, очень хорошо. Если же произошло столкновение, то в нише узла 1 до конкурса допускаются станции, связанные с узлом 2 (А, Б, В и Г). Если одна из них получила доступ, в нише, следующей за переданным кадром, будут соревноваться станции, связанные с узлом 3 (Д, Е, Ж и З). Если же на предшествующем этапе произошло столкновение, следующая попытка предоставляется станциям, связанным узлом 4 (А и Б) и т.д.. Если столкновение произошло в нише узла 0, то сначала исследуется все дерево, чтобы выявить все готовые к передаче станции. Каждая бит-ниша ассоциируется с определенным узлом дерева. Если происходит столкновение, поиск продолжается рекурсивно для правой и левой ветвей узла. Если бит-ниша пассивна (нет заявок на передачу), или если имеется только одна станция-претендент, поиск будет прерван, так как все станции-претенденты найдены. Существует достаточно большое число вариаций данного алгоритма доступа к сети.

Следующим по популярности после csma/cd является маркерный доступ (Token Ring, Arcnet и FDDI), который более гибок и обеспечивает приоритетную иерархию обслуживания. Массовому его внедрению препятствует сложность и дороговизна. Хотя региональные сети имеют самую разнообразную топологию, практически всегда они строятся на связях точка-точка.

В таблице 4.1 представлены сводные данные по основным видам локальных сетей, используемых в настоящее время (список не является полным).

Таблица 4.1. Параметры различных локальных сетей

Рис. 4.8. Пояснение работы алгоритма доступа WDMA

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

Для осуществления пересылки файла станция А посылает В управляющее сообщение типа “загляните в домен данных 3, там кадр для вас”. Когда В получает управляющее сообщение, она настраивает свой приемник на выходной канал А, чтобы принять кадр данных от А. Станция В может использовать ту же схему для посылки подтверждения получения кадра, если это необходимо. Заметим, что может возникнуть проблема, если с В имеют одновременно соединения А и С и обе станции предлагают В заглянуть в информационный домен 3. Станция В воспримет одно из этих сообщений, второе будет потеряно. При постоянной скорости передачи используется модификация данного протокола. Когда станция А запрашивает соединение, она одновременно посылает сообщение типа “не возражаете, если я буду посылать данные в каждом домене 3?”. Если В способна принять данные (домен 3 не занят), устанавливается соединение с фиксированной полосой. Если это не так, А может попытаться использовать другой свободный временной домен. Для типа обмена 3 (дейтограммы) используется другая вариация протокола. Вместо посылки запроса соединения в найденный свободный домен управляющего канала, станция записывает сообщение “DATA FOR YOU in SLOT 3” (для вас есть данные в домене 3). Если В свободна во время следующего информационного домена 3, обмен будет успешным, в противном случае кадр теряется. Существует большое число различных вариантов протокола WDMA, например, с общим управляющим каналом для всех рабочих станций.

Таким образом, FDM-доступ в N раз хуже, чем вариант, когда мы все кадры помещаем каким-то образом в некоторую общую очередь. Точно такая же аргументация может быть применена для метода TDM. По этой причине предпочтительнее динамические методы организации доступа к каналу (сетевой среде).

Приведенное выше соображение безусловно поверхностно, так как не учитывает того факта, что мало доставить данные, надо их загрузить в ЭВМ (а вагоны машиной приниматься не могут). Но при построении сетей передачи данных и столь архаичный вариант не следует совершенно снимать со счетов.

Данная схема доступа исключает столкновения, характерные для CSMA. Именно это преимущество делает сеть применимой для задач реального времени.

Существует целое семейство методов доступа, исключающих столкновение: это мультиплексирование по времени (TDM) и по частоте (FDM). Здесь каждому клиенту выделяется определенный временной домен или частотный диапазон. Когда наступает его временной интервал и клиент имеет кадр (или бит), предназначенный для отправки, он делает это. При этом каждый клиент ждет в среднем n/2 временных интервалов (предполагается, что работает n клиентов). При FDM передача не требует ожидания. Но в обоих случаях временные интервалы или частотные диапазоны используются клиентом по мере необходимости и могут заметное время быть не заняты (простаивать). Такие протоколы доступа часто используются в мобильной связи.

Фирма Дженерал Электрик разработала сеть gm (map-шина), совместимую со стандартом IEEE 802.4. Целью разработки было обеспечение совместимости с производственным оборудованием различных компаний. Сеть рассчитана на работу со скоростями 1, 5 и 50 Мбит/с.

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

Ниже приведены максимальные размеры пакетов (MTU) для ряда сетей

Операции, ориентированные на установление связи (например, протокол TCP), предполагают трехстороннее соглашение между двумя пользователями и провайдером услуг. В процессе обмена они хранят необходимую информацию друг о друге, с тем, чтобы не перегружать вспомогательными данными пересылаемые пакеты. В этом режиме обмена обычно требуется подтверждение получения пакета, а при обнаружении сбоя предусматривается механизм повторной передачи поврежденного пакета. «Бессвязная» сеть более надежна, так как она может отправлять отдельные пакеты по разным маршрутам, обходя поврежденные участки. Такая сеть не зависит от протоколов, используемых в субсетях. Большинство протоколов Интернет используют именно эту схему обмена. Концептуально TCP/IP-сети предлагают три типа сервиса в порядке нарастания уровня иерархии:

Рис. 4.9. Вариант схемы ресурсной локальной сети

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

Для сопоставления быстродействия различных видов сетей Сталлингс (Stallings, W.: Data and Computer Communications, New York: Mac-Millan Publishing Company, 1985) в 1985 году разработал критерий. Критерий предполагает вычисление битовой длины BL (максимальное число бит в сегменте), которая равна произведению максимальной длины сегмента (L) на полосу пропускания (W), деленное на скорость распространения сигнала в сегменте (S):

Для Ethernet BL = [500(м)*10 10 6 (бит/c)]/2 10 8 (м/c) = 25 бит.

Коэффициент использования сети равен b = 1/(1+ a ), где

. Для Ethernet при длине пакета 1500 байта a = 0,0021, что дает для эффективности использования сети 0,997. Таким образом, максимальная пропускная способность ethernet составляет 9,97 Мбит/c или 1,25 Мбайт/с. Разумеется, в этом подходе не учитываются издержки, связанные с заголовками пакетов, которые дополнительно снижают эффективность сети. Из данного рассмотрения может показаться, что чем больше пакет, тем лучше. С точки зрения пропускной способности так оно и есть. Но с увеличением длины пакета увеличивается время отклика сети. Таким образом, выбор MTU определяется реальными требованиями пользователей.

Принципы построения сетевых программных интерфейсов

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

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

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

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

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

В третьем варианте сетевого программного интерфейса используются служебные запросы. Этот тип сетевого доступа удобен для коммуникационных протоколов высокого уровня, таких как команды ввода/вывода CSP-стиля (Communicating Sequential Processes) или процедуры обмена языка Ада. В этом методе накладываются определенные ограничения на реализацию нижележащих коммуникационных уровней.

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

Одной из важнейших и достаточно трудно реализуемых функций сетевого оборудования (например, на скорости более 10Мбит/c) является обслуживание очередей и подавление перегрузок.

Оптимальность управления сетью в условиях перегрузок определяет эффективность использования сети. Пока субсеть загружена незначительно, число принимаемых и обрабатываемых пакетов равно числу пришедших. Однако, когда в субсеть поступает слишком много пакетов может возникнуть перегрузка и рабочие характеристики деградируют. Идеальная с точки зрения потребителя нагрузочная характеристика сети характеризуется прямой линией, то есть числа посланных и доставленных пакетов равны или почти равны (линейный участок кривой А на рис. 4.12). При достижении максимума пропускной способности число пакетов, доставляемых в единицу времени, становится постоянным, в то время как число посланных продолжает расти. К сожалению в реальной жизни такого не происходит. Желательной нагрузочной харакетистикой (кривая Б) является такая, которая при малых и максимальных нагрузках ведет себя как идеальная, а при переходных скоростях имеет плавный характер и доставляет несколько меньший процент пакетов, чем в идеале. Реальная нагрузочная характеристика (например, для Ethernet с возможностью столкновений) много хуже даже желательного варианта (линия В). При потоках, превышающих некоторый порог, число доставляемых пакетов начинает падать при росте числа посланных пакетов, а при дальнейшем росте нагрузки число доставляемых пакетов может стать нулевым.Такая ситуация называется коллапсом сети.

Перегрузка, в сущности, связана с несогласованностью характеристик каких-то частей системы, например, полосы пропускания каналов.

Очереди FIFO

Очереди FIFO (First-In-First-Out) используются обычно в скоростных интерфейсах (быстродействие > 2048кбит/c). Здесь первый пришедший пакет первым и покидает очередь. Порядок следования пакетов при этом алгоритме не изменяется. Приоритетное обслуживание в этом варианте также не может быть осуществлено. Когда очередь заполнена, все последующие пакеты будут отбрасываться до тех пор, пока из очереди не будет изъят хотя бы один пакет.

Приоритетное обслуживание очередей (PQ)

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

Обычное обслуживание очередей (СQ)

Взвешенные справедливые очереди (WFQ)

Стратегия справедливых (взвешенных) очередей WFQ (Weighted Fair Queuing) используется по умолчанию для интерфейсов низкого быстродействия. WFQ делит трафик на несколько потоков, используя в качестве параметров (для IP-протокола): IP-адреса и порты получателя и отправителя, а также поле IP-заголовка ToS. Значение ToS служит для квалификации (части выделяемой полосы) потока. Для каждого из потоков формируется своя очередь. Максимально возможное число очередей равно 256. Очереди обслуживаются в соответствии с карусельным принципом (round-robin). Более высокий приоритет имеют потоки с меньшей полосой, например, telnet. По умолчанию каждая из очередей имеет емкость 64 пакета (но допускается значение и

Усреднение длины очереди ( ) производится согласно следующей формулы:

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

Рис. 4.14. Зависимость от времени и Q (Wq=0.002; pc=0.2; T1=25; T2=60; размер буфера = 800; время эксперимента 30 сек; перегрузка l/m =1.4)

На рис. 4.14 ромбиками отмечена зависимость текущего значения длины очереди от времени. Отсюда видно, что усредненное значение длины очереди на начальном участке зависимости уступает текущей длине более чем в два раза. В расчетах входной поток l и выходной m задавались в битах в секунду. В области от 0 до Т1 рост длины очереди определяется произведением ( l-m )t. После достижения уровня Т1 скорость роста длины очереди замедляется, так как часть пакетов отбрасывается, зависимость становится квадратичной. Прекращение роста и начало спада Q происходит в момент, когда достигает уровня Т2.

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

Расчеты проводились с привлечением пакета программ моделирования NS-2 [2]. Значения Т1 и Т2 задавалось в пакетах. Отношение l/m определяет уровень перегрузки канала.

На рис. 4.15. показана зависимость усредненного значения длины очереди от времени и параметра P_C. P_C здесь варьировалось в интервале от 0,01 до 0,7.

Представленные на рисунке результаты показывают, что минимальные осцилляции происходят в области P_C 0,6 осцилляции длины очереди не затухают даже спустя 30 сек после начала перегрузки канала. Производная dA/dpc=10, где А – максимальная амплитуда осцилляций очереди, остается постоянной в интервале 0,1

Рис. 4.15. Расчеты эволюции как функции P_C выполнены при следующих значениях параметров: l/m = 1,4, qw = 0.002, T1=25, T2=40

Если в области малых P_C осцилляции происходят вокруг равновесного значения

Т2, то при P_C > 0,4 этот уровень падает до 30, что связано с тем, что заметная доля пакетов отбрасывается еще до достижения уровня Т2.

Рис. 4.16. Зависимость амплитуды осцилляции от P_C

Если при малых значениях P_C равновесное значение длины очереди равно Т2=40, то при больших значениях P_C равновесное значение после затухания осцилляций приближается к 30.

На рис. 4.17 показана зависимость от времени и уровня перегрузки l/m в диапазоне от 1.1 до 2.0. Остальные параметры имели следующие значения: P_C =0.5 и qw =0.002, T1=25, T2=40 (размер буфера В=180 пакетам). С ростом уровня перегрузки амплитуда осцилляций линейно падает, одновременно также линейно сокращается период осцилляций.

Рис. 4.17. Зависимость от времени и уровня перегрузки канала l/m

Из рисунка видно, что наименьший уровень осцилляций длины очереди имеет место для l/m в диапазоне 1,2-1,5. К сожалению, на практике этот параметр обычно не выбирается

Рис. 4.18. Зависимость амплитуды осцилляции длины очереди от l/m

Рис. 4.19. Зависимость периода осцилляции длины очереди от l/m

На рис. 4.20 показана зависимость осцилляций длины очереди от фактора усреднения qW. Из рисунка видно, что приемлемые значения лежат в области >0,003. При меньших значениях qW осцилляции не затухают даже через 10 сек после начала перегрузки. Равновесное значение

Рис. 4.20. Зависимость от фактора усреднения qW

Ниже на рис. 4.21. представлена зависимость от порога Т2. Фактор перегрузки постоянен l/m =1.4; Т1=25=const; T2=(T1/10)*index; index=[1:40]; Pc=0.1; B=900.

Рис. 4.21. Зависимость от разницы порогов Т2-Т1

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

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

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

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

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

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

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

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

Одной из причин перегрузки часто являются импульсные загрузки сегмента сети или сетевого устройства. По этой причине любые меры (напр., pipelining), которые могут выровнять поток пакетов, безусловно улучшат ситуацию (например, traffic shaping в сетях ATM). В TCP же с его окнами импульсные загрузки предопределены.

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

Алгоритм leaky bucket («дырявое ведро»)

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

Алгоритм Token Bucket («маркерное ведро»)

Алгоритм token bucket предполагает наличие в буферном устройстве (или программе) некоторого количества маркеров. При поступлении на вход буфера пакетов маркеры используются для их транспортировки на выход. Дальнейшая передача данных на выход зависит от генерации новых маркеров. Поступающие извне пакеты тем временем накапливаются в буфере. Таким образом, полной гарантии отсутствия потерь мы не имеем и здесь. Но алгоритм token bucket позволяет передавать на выход «плотные» группы пакетов ограниченной численности (по числу маркеров), снижая в некоторых случаях вероятность потери. Если буферное устройство «смонтировано» внутри ЭВМ-отправителя, потерь можно избежать вовсе, блокируя передачу при заполнении буфера. Как в одном так и в другом алгоритме мерой передаваемой информации может быть не пакет, а n-байт (где n некоторое оговоренное заранее число).

В системах, где управление трафиком осуществляется с использованием обратной связи, можно достичь большей эффективности. Одним из механизмов преодоления перегрузок является управление разрешением (admission control). Суть метода заключается в том, что при регистрации перегрузки не формируется более никаких виртуальных соединений до тех пор, пока ситуация не улучшится. Альтернативным вариантом может служить решение, где формирование нового соединения разрешается, но при этом осуществляется маршрутизация так, чтобы обойти узлы, в которых выявлена перегрузка (смотри рис. 4.22 ).

Рис. 4.22. Выбор маршрута нового виртуального канала при наличии перегрузки

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

Еще более универсальным решение, пригодным для работы с установлением соединения и без, является посылка пакетов блокировки (choke packets). Маршрутизатор обычно контролирует загруженность всех своих внешних каналов l, которая может принимать значения от 0 до 1. Когда l достигает некоторого порогового значения, отправителю посылается пакет блокировки. При вычислении l следует использовать какую-либо методику усреднения, чтобы избежать слишком частых блокировок.

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

ЭВМ может понижать трафик, корректируя свои параметры, например, ширину окна или темп передачи на выходе устройства типа «дырявое ведро». Обычно первый блокирующий пакет уменьшает поток вдвое, следующий на 0,25 от первичного и т.д. Увеличение потока также производится аналогичными шагами. Существует большое число вариантов алгоритма управления потоком с использованием пакетов блокировки. Параметром, который контролируется и определяет условие отправки пакета блокировки, может служить длина очереди или заполненность буфера.

Ситуация перегрузки не всегда управляется однозначно. Например, при поступлении на вход пакетов от трех источников возможна ситуация, когда приемник посылает блокирующие пакеты всем отправителям, а откликнется сокращением потока только один. В результате этот узел, который «играет по правилам» (как это часто бывает и в жизни) оказывается в проигрыше. В 1987 году Нагле был предложен алгоритм fair queueing (честная очередь). В этом алгоритме маршрутизатор организует независимые очереди для пакетов, поступающих от разных источников. Когда выходной канал маршрутизатора оказывается свободным, он просматривает очереди циклически и отравляет очередной пакет. В результате при n очередях по завершении такого цикла просмотров-посылок оказываются посланы по одному пакету из каждой очереди. Такой алгоритм используется в некоторых ATM-переключателях. Следует заметить, что этот алгоритм дает некоторые преимущества тем узлам, которые посылают более длинные пакеты. Демерс (Demers) и др. в 1990 году предложил некоторое усовершенствование алгоритма. В данном варианте организуется циклический просмотр очередей не по-пакетно, а по-байтно. Система последовательно сканирует очереди и определяет положение концов пакетов. Первыми отправляются более короткие пакеты. Для иллюстрации предлагается рассмотреть рис. 4.23. (см. также [39])

Рис. 4.23. Маршрутизатор с 4-мя входными каналами, в каждом из которых ждет очереди передачи по одному пакету. В правой части рисунка представлен порядок посылки этих пакетов.

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

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

В протоколе TCP используется алгоритм управления трафиком, называемый «скользящее окно». Здесь размер окна, которое определяет число сегментов, посылаемых без получения подтверждения, варьируется в зависимости от наличия потерь пакетов. При большой вероятности потери система переходит в режим, когда очередной пакет не посылается до тех пор, пока не будет подтверждено получение предшествующего. При серьезных перегрузках, когда потери становятся значительными, нарушается механизм вычисления значений RTT и таймаутов, что может приводить к трудно предсказуемым последствиям. Следует обратить внимание, что в протоколе UDP какого-либо механизма управления трафиком не предусмотрено. По этой причине для некоторых мультимедийных задач, следует предусматривать другие, например, ICMP-способы подавления перегрузки. В приложениях типа NFS, где используется UDP, для подавления перегрузки используется упомянутый выше ICMP-механизм. К сожаления в ряде мультимедийных приложений потеря пакетов не контролируется (например IP-телефония). Там шлюз 100-10Мбит/с может восприниматься как канал с вероятностью потери пакета 90%.

Проблемы адресации

Когда обсуждались варианты Интернет (разработчики, правда, еще не знали, что это будет Интернет), Ethernet, хотя и не долго, уже существовал. Почему Интернет нельзя было целиком выполнить на основе Ethernet?

Действительно, коммутатор локальной сети существенно дешевле маршрутизатора, Ethernet способен обеспечить уже сегодня пропускную способность 400 Гбит/c и т.д. Список кажущихся выгод можно было бы продолжить.

Проблемы становятся очевидны, если мы задумаемся над задачей маршрутизации (переадресации) пакетов. Каждому адресу в переключателе Ethernet соответствует одна запись в таблице переадресации. Таблица же IP-маршрутизации оперирует блоками адресов, используя префиксы и номера автономных систем. Именно это ограничивает объемы маршрутных таблиц в маршрутизаторах и минимизирует время переадресации. IP-адреса распределяются блоками не менее 256 (С-класс). Именно это позволяет легко с помощью масок разделить локальные и удаленные сетевые объекты. Почему нельзя использовать ту же технику для Ethernet?

Проблема в том, что адреса Ethernet присваиваются изготовителем оборудования, именно это гарантирует их уникальность и в редкой локальной сети можно найти адреса, отличающиеся на 1 в двоичном представлении. Разумеется, Ethernet-адреса можно изменить вручную, но при этом станет трудно, практически невозможно, обеспечить их уникальность. Либо нужно вводить порядок выдачи Ethernet-адресов блоками, как это делается для IP, либо разработать какой-то другой механизм обеспечения уникальности адресов.

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

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

Именно это обстоятельство сделало актуальной проблему big data – объем информации, при котором время выборки начинает быстро стремиться к бесконечности. Это связано с тем, что в маршрутизаторах и базах данных используется выборка через посредство хэшей (адресация по содержимому).

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

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

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

Источник