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

Помощь студентам в дистанционном обучении
Ответы на тесты, практикумы, кейсы

Главная

Магазин / СИНЕРГИЯ / Тест/Синергия / «Инфокоммуникационные системы и сети » Ответы Тест Синергия

«Инфокоммуникационные системы и сети » Ответы Тест Синергия

К программным средствам типа «даунлоадеры» относятся.
ReGet, FlashGet, WinMX, GetRight, eDonkey
Kerio Firewall Personal, Agnitum Outpost, Windows Firewall
Mirabilis ICQ, SIM, RQ, Jabber, MSN, Yahoo, xchat, licq)
nternet Explorer, Opera, Mozilla Firefox, Netscape Navigator

Неверно, что состязательный тип доступа используется таким методом доступа, как
CSMA/CD
CSMA/CA
доступ с передачей маркера
доступ по приоритету запроса

Базовая эталонная модель взаимодействия открытых систем Open System Interconnection reference model (OSI) включает.
4 уровня
5 уровней
6 уровней
7 уровней

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

. метод маршрутизации характеризуется тем, что предусматривает составление постоянных таблиц маршрутов, указывающих наиболее эффективные пути предполагаемого трафика сети
Фиксированная (статическая) маршрутизация

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

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

Источник

Топология

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

Источник