имя

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

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

По этим причинам был разработан альтернативный способ сертификации открытых ключей. Он известен под общим названием PKI (Public Key Infra­structure — инфраструктура систем с открытыми ключами). В этом разделе мы
рассмотрим только общие принципы действия PKI, поскольку было внесено мно­жество предложений по ее модификации и некоторые детали могут со временем измениться.

ЦУ

РО 2

УС принято. Открытый ключ: 6384AF863B... Подпись РО 2

а                                                                                                            б Рис. 8.22. Иерархия PKI (а); цепочка сертификатов (б) Итак, наш PKI работает следующим образом. Допустим, Алисе нужен откры­тый ключ Боба, чтобы она могла с ним пообщаться. Она ищет и находит содер­жащий его сертификат, подписанный УС 5. Однако Алиса никогда ничего не слышала про УС 5. Этим «Управлением» может оказаться, на самом деле, деся­тилетняя дочка Боба. Алиса может отправиться в УС 5 и попросить подтвердить легитимность. Управление в ответ может показать сертификат, полученный от

PKI состоит из множества компонентов, среди которых Управления сертифи­кации, сами сертификаты, а также каталоги. Инфраструктура систем с открытыми ключами предоставляет возможность структурной организации этих компонен­тов и определяет стандарты, касающиеся различных документов и протоколов. Одним из простейших видов PKI является иерархия Управлений, представлен­ная на рис. 8.22. На рисунке представлены три уровня, однако реально их может быть как больше, так и меньше. Управление сертификации верхнего уровня (root) мы будем называть Центральным управлением (ЦУ). Центральное управление сертифицирует управления второго уровня — назовем их Региональными отде­лами (РО), — так как они могут обслуживать некоторый географический регион, например, страну или континент. Этот термин не стандартизован. Названия для уровней иерархии вообще не оговариваются стандартом. Региональные отделы, в свою очередь, занимаются легализацией реальных Управлений сертификации (УС), эмитирующих сертификаты стандарта Х.509 для физических и юриди­ческих лиц. При легализации Центральным управлением нового Регионального отдела последнему выдается сертификат, подтверждающий его признание. Он содержит открытый ключ нового РО и подпись ЦУ. Аналогичным образом РО взаимодействуют с Управлениями сертификации: выдают и подписывают серти­фикаты, содержащие открытые ключи УС и признающие легальность деятель­ности.

РО 2 принят. Открытый ключ: 47383АЕ349...

Подпись ЦУ

РО 2 и содержащий открытый ключ УС 5. Теперь, вооружившись открытым ключом УС 5, Алиса может удостовериться в том, что сертификат Боба действи­тельно подписан УС 5, а значит, является легальным.

Если только РО 2 не является двенадцатилетним сыном Боба. Если Алисе вдруг придет в голову такая мысль, она может запросить подтверждение леги­тимности РО 2. Ответом будет служить сертификат, подписанный Центральным управлением и содержащий открытый ключ РО 2. Вот теперь Алиса может не сомневаться, что она получила открытый ключ Боба, а не кого-то другого.

А если Алиса хочет узнать открытый ключ ЦУ? Как это сделать? Загадка. Предполагается, что открытый ключ ЦУ знают все. Например, он может быть «зашит» внутрь ее браузера.

Но наш Боб — добряк, он не хочет доставлять Алисе лишние хлопоты. Он по­нимает, что она захочет проверить легитимность УС 5 и РО 2, поэтому он сам собирает соответствующие сертификаты и отправляет их ей вместе со своим. Те­перь, зная открытый ключ ЦУ, Алиса может проверить по цепочке все интере­сующие ее организации. Ей не придется никого беспокоить для подтверждения. Поскольку все сертификаты подписаны, она может запросто уличить любые по­пытки подлога. Цепочка сертификатов, восходящая к ЦУ, иногда называется до­верительной цепочкой или путем сертификата. Описанный метод широко при­меняется на практике.

Конечно, остается проблема определения владельца ЦУ. Следует иметь не од­но Центральное управление, а несколько, причем связать с каждым из них свою иерархию региональных отделов и управлений сертификации. На самом деле, в современные браузеры действительно «зашиваются» открытые ключи более 100 центральных управлений, иногда называемые доверительными якорями. Как видите, можно избежать проблемы одного всемирного учреждения, занимающе­гося сертификацией.

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

Каталоги

Инфраструктура систем с открытыми ключами должна решать еще один вопрос. Он касается места хранения сертификатов (и цепочек, ведущих к какому-нибудь доверительному якорю). Можно заставить всех пользователей хранить свои сер­тификаты у себя. Это безопасно (так как невозможно подделать подписанные сертификаты незаметно), но не слишком удобно. В качестве каталога для серти­фикатов было предложено использовать DNS. Прежде чем соединиться с Бобом, Алисе, видимо, все равно придется узнать с помощью службы имен доменов (DNS) его IP-адрес. Так почему бы не заставить DNS возвращать вместе с 1Р-ад- ресом всю цепочку сертификатов?

Кому-то это кажется выходом из положения, однако некоторые считают, что лучше иметь специализированные серверы с каталогами для хранения серти­фикатов Х.509. Такие каталоги могли бы с помощью имен Х.500 обеспечивать возможность поиска. Например, теоретически можно представить себе услугу сер­вера каталогов, позволяющую получать ответы на запросы типа «Дайте мне пол­ный список всех людей по имени Алиса, работающих в отделе продаж в любом месте США или Канады». Хранить такую информацию можно, например, при помощи LDAP.

Аннулирование

Реальный мир полон разного рода сертификатов, среди которых, например, пас­порта, водительские удостоверения. Иногда эти сертификаты необходимо анну­лировать (например, водительское удостоверение надо аннулировать за езду в нетрезвом состоянии). Та же проблема возникает и в мире цифровых технологий: лицо, предоставившее сертификат, может отозвать его за нарушение противопо­ложной стороной каких-либо условий. Это необходимо делать и тогда, когда за­крытый ключ, в сущности, перестал быть защищенным или, что еще хуже, ключ УС потерял кредит доверия. Таким образом, инфраструктура систем с открыты­ми ключами должна как-то обеспечивать процедуру аннулирования.

Первым шагом в этом направлении является принуждение всех УС к перио­дическому выпуску списка аннулированных сертификатов (CRL — Certificate Revocation List). В нем перечисляются порядковые номера всех аннулированных сертификатов. Поскольку в сертификатах содержится дата окончания срока год­ности, в CRL следует включать номера только тех из них, срок годности которых еще не истек. По истечении срока годности сертификаты перестают быть дейст­вительными автоматически, поэтому нужно различать случаи аннулирования «по старости» и по другим причинам. В любом случае их использование необхо­димо запрещать.

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

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

Где хранить списки аннулированных сертификатов? Было бы здорово хра­нить их там же, где и сами сертификаты. Одна из стратегий подразумевает, что

УС периодически выпускает «черные» списки и заставляет вносить обновления в каталоги (удаляя отозванные сертификаты). Если для хранения сертификатов каталоги не используются, можно кэшировать их в разных удобных местах в се­ти. Поскольку «черный» список сам по себе является подписанным документом, любые попытки подлога тотчас будут замечены.

Если сертификаты имеют большие сроки годности, списки аннулированных сертификатов также будут довольно длинными. Например, количество отозван­ных кредитных карточек со сроком годности 5 лет будет гораздо больше списка отозванных трехмесячных карточек. Стандартным способом борьбы с длинными списками является довольно редкий выпуск самих списков и частый — обновле­ний к ним. Кроме всего прочего, это помогает снизить необходимую для распро­странения списков пропускную способность.

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

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

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

Однако неисправности оборудования или программного обеспечения могут привести к очень серьезным проблемам при использовании данного алгоритма (а также других алгоритмов). Например, если маршрутизатор заявит о существо­вании линии, которой у него в действительности нет, или наоборот, забудет о су­ществовании имеющейся у него линии, граф подсети окажется неверным. Если маршрутизатор не сможет переслать пакеты или повредит их при пересылке, так­же возникнет проблема. Наконец, если у маршрутизатора закончится свободная память или он ошибется в расчетах маршрутов, также возможны различные не­приятности. При увеличении размера подсети до нескольких десятков или сотен тысяч маршрутизаторов вероятность выхода из строя одного из них перестает быть пренебрежимо малой. Все, что можно здесь сделать, — это попытаться огра­ничить вред, наносимый практически неизбежным выходом из строя оборудова­ния. Эти проблемы и методы их разрешения подробно обсуждаются в (Perlman, 1988).

Маршрутизация с учетом состояния линий широко применяется в современ­ных сетях, поэтому следует сказать несколько слов о некоторых примерах прото­колов, использующих данный алгоритм. Одним из таких протоколов является протокол OSPF, все чаще применяемый в Интернете, о котором будет рассказа­но в разделе «Протокол внутреннего шлюза OSPF».

Другим важным протоколом с учетом состояния линий является IS-IS (Intermediate System to Intermediate System — связь между промежуточными сис­темами) — протокол, разработанный для сети DECnet и принятый впоследствии Международной организацией по стандартизации ISO для использования вме­сте с протоколом сетевого уровня CLNP, не требующим соединений. С тех пор он был модифицирован для поддержки также и других протоколов, в частности IP. Протокол IS-IS используется в некоторых магистралях сети Интернет (включая старую магистраль NSFNET) и в некоторых цифровых сотовых системах, напри­мер, в CDPD. В сети Novell NetWare применяется разновидность протокола IS­IS (NLSP) для маршрутизации IPX-пакетов.

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

Многие новшества, разработанные для протокола IS-IS, были приняты несколь­ко лет спустя при разработке протокола OSPF. К ним относятся метод саморегу­ляции лавинного потока обновлений информации о состоянии линий, концеп­ция выделенного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути и умножения метрик. Соответственно, между про­токолами IS-IS и OSPF нет почти никакой разницы. Наиболее существенное различие между ними заключается в том, что способ кодирования в протоколе IS-IS, в отличие от OSPF, облегчает одновременную поддержку нескольких се­тевых протоколов. Это свойство особенно важно в больших многопротокольных средах.

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

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

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

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

В-третьих, может произойти искажение порядкового номера — например, вмес­то номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае паке­ты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие.

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

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

Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рис. 5.11, а, показана на рис. 5.12. Каждый ряд здесь соответству­ет недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и F соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.

Как видно из рис. 5.12, пакет состояния линий от маршрутизатора А пришел напрямую, поэтому он должен быть отправлен маршрутизаторам С и F, а под­тверждение о его получении следует направить маршрутизатору А, что и пока­зывают флаговые биты. Аналогично, пакет от F следует переслать маршрутиза­торам А и С, a F отослать подтверждение.

Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отли­чается. Он был получен дважды, по линиям ЕАВ и EFB, Следовательно, его нуж­но отослать только С, но подтверждения выслать и А, и jF, как указывают биты.

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

Хорошо известно, что при борьбе с перегрузкой гораздо проще вовремя обнару­жить затор, чем дать ему развиться до критических размеров, а потом думать, что делать в сложившейся ситуации. Это соображение приводит к идее отвержения некоторых пакетов еще до того, как все буферное пространство будет заполнено скопившимися необработанными данными. Популярный алгоритм, реализующий данную идею, называется случайным ранним обнаружением (RED — Random Ear­ly Detection, Floyd и Jacobson, 1993). Некоторые транспортные протоколы (вклю­чая TCP) на потерю своих пакетов отвечают снижением трафика от источника, чего мы, в сущности, и добиваемся. Обоснование такой логики состоит в том, что TCP предназначен для проводных сетей, которые по сути своей являются очень надежными, и потеря пакетов в них чаще всего сигнализирует о переполнении буфера, а не об ошибках передачи. Этот факт и используется для уменьшения пе­регрузок.

Если заставить маршрутизаторы сознательно терять пакеты еще до того как ситуация станет безнадежной (именно такой момент зашифрован в слове «ран­нее» из названия подхода), то останется время на то, чтобы предпринять какие- то действия. Для определения условий, при которых следует начинать терять па­кеты, маршрутизаторы постоянно высчитывают скользящее среднее длин своих очередей. Когда средняя длина очереди на какой-либо линии превышает порого­вое значение, эта линия объявляется перегруженной и выполняются действия по предотвращению затора.

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

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

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

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

Стратегия подтверждений также влияет на перегрузку. Если каждый пакет немедленно подтверждается получателем, то пакеты с подтверждениями образу­ют дополнительный трафик. Однако если подтверждения добираются обратно «верхом» на попутном потоке кадров, то количество трафика в сети снижается, зато увеличивается среднее время получения подтверждений, что может, в свою очередь, вызвать увеличение повторно переданных пакетов вследствие истече­ния времени ожидания подтверждений. Более жесткая схема управления пото­ком (например, с небольшим размером окна) уменьшает скорость передачи дан­ных и помогает бороться с перегрузкой.

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

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

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

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

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

Еще одно различие двух алгоритмов заключается в том, что при переполне­нии маркерного ведра алгоритм игнорирует маркеры, но никогда не отвергает пакеты. Алгоритм дырявого ведра, напротив, при переполнении выбрасывает са­ми пакеты.

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

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

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

Суть алгоритма маркерного ведра состоит в том, что он допускает передачу Данных пачками, но ограничивает длительность пачки. Для примера рассмотрим рис. 5.29, в, на котором изображено маркерное ведро емкостью 250 Кбайт. Мар­керы появляются с частотой, соответствующей выходной скорости 2 Мбайт/с. Предположим, что маркерное ведро заполнено, когда прибывает пакет данных , размером 1 Мбайт. Ведро может быть освобождено с максимальной скоростью 25 Мбайт/с примерно за 11 мс. Затем оно должно уменьшить скорость передачи ' До 2 Мбайт/с, пока не будет передан весь входной пакет данных.

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

Один из способов получения более гладкого трафика состоит в помещении дырявого ведра после маркерного ведра. Скорость дырявого ведра должна быть выше минимальной скорости маркерного ведра р, но ниже максимальной скоро­сти сети. На рис. 5.29, е показан выходной поток маркерного ведра емкостью 500 Кбайт, за которым установлено дырявое ведро со скоростью протекания, равной 10 Мбайт/с.

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