Ответы на билеты (2014), страница 8

При буферизации в общей памяти все фреймыхранятся в общем буфере памяти, который используется всеми портами коммутатора.По лекциям.Lookup Address – фаза просмотра адреса.Forwarding Table – анализ заголовка пакета с определением выходной линии.Update Header – модификация заголовка сетевого уровня (TTL, контрольная сумма).Ethernet коммутатор.1. Проверяет заголовок каждого прибывающего кадра.2. Если адрес DA есть в таблице коммутации, то кадр передают на надлежащий выходной порт.3.

Если адрес DA нет в таблице, кадр рассылается по всем портам, кроме того на который пришел.4. Когда придет ответ на разосланный пакет, то по его адресу отправителя мы узнаем , куда надонаправлять пакеты с такими адресами получателей.Интернет маршрутизатор.311. Если Ethernet DA поступившего кадра есть Ethernet адрес маршрутизатора, то принять кадр, иначесбросить его.2. Просмотреть поля IP version и длина дейтаграммы.3. Сократить поле TTL, пересчитать контрольную сумму IP заголовка.4.

Проверить TTL на 0.5. Если IP DA есть в таблице маршрутизации, переслать на надлежащий выходной порт для следующего скачка (hop).6. Найти Ethernet DA для следующего маршрутизатора.7. Построить новый Ethernet кадр и отправить его.Базовые операции коммутатора.1. Поиск адреса: как адрес ищется в таблице маршрутизации?2. Коммутация: как пакет пересылают на надлежащий выходной порт?Поиск адреса: Ethernet.1. Адреса хранятся в хэш-таблице.2.

Ищем в хэш-таблице точное совпадение.Рис. 9: Таблица Ethernet адресов.Поиск адреса: IP.Ищут совпадение по самому длинному префиксу, а не точное совпадение.Рис. 10: Таблица IP адресов в маршрутизаторе.32Троичная Ассоциативная память.Двоичная АП – простейший тип ассоциативной памяти, который использует слова поиска данных,состоявшие полностью из единиц и нулей. В троичной АП добавляется третье значение для сравнения«X» или «не важно», для одного или более битов в сохраненном слове данных, добавляя таким образомбольшей гибкости поиску.

Например, в троичной АП могло бы быть сохранено слово «10XX0», котороевыдаст совдпадение на любое из четырех слов поиска «10000», «10010», «10100», или «10110». Добавление гибкости к поиску приходит за счет увеличения цены двоичной АП, поскольку внутренняя ячейкапамяти должна теперь закодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности»(«важно»/«не важно») к каждой ячейкепамяти.

Голографическая ассоциативная память обеспечивает математическую модель для интегрированного ассоциативного воспоминания бита «не важно», используя комплекснозначное представление.Поиск адреса <совпадение, действие>.Обобщение поиска и коммутации в коммутаторах, маршрутизаторах и т.п.∙ По сути, Ethernet коммутаторы и маршрутизаторы выполняют одинаковые действия.∙ Поиск адреса в коммутаторе и маршрутизаторе происходит по-разному.Организация очередей на входе.Примером такого варианта размещения может служить организация буферов на входных портахнеблокирующей структуры с пространственным разделением, например баньяновидной сети Бэтчера.К его недостаткам можно отнести опасность возникновения блокировки в начале очереди.

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

Таким образом, либо выходные буферы должны функционировать с достаточно высокой скоростью, либо на каждомвыходном порте требуются несколько буферов. Оба решения ограничивают производительность и масштабируемость устройства: в первом случае — из-за необходимости существенно повысить внутреннеебыстродействие коммутатора, а во втором – буферов.Пакетный коммутатор: заключение.Пакетный коммутатор выполняет две базовые операции:∙ Поиск соответствия в таблице коммутации.∙ Передачу на надлежащий выходной порт.33Самый простой и самый медленный коммутатор использует буферизацию на выходе с минимальнойзадержкой пакета.Высокоскоростные коммутаторы используют буферизацию на входе с виртуальными очередями навыходах для увеличения пропускной способности.12Коммутация пакетов: приоритеты, веса и гарантированная скорость потокаРассмотрим пакетный коммутатор с буферизацией на выходе, как гарантию того, что пакеты из буфера будут обслужены с определенной скоростью.Пакетные коммутаторы работают по принципу FIFO, однако поступающие пакеты могут быть разнойдлины, а значит, при равномерной работе, окажется, что кто-то получит бОльшую долю пропускнойспособности.Если пакеты имеют равный размер, то время задержки каждого пакета не более, чем размер буфера/пропускную способность канала.Задание строгих приоритетов нарушает справедливость: на каждом цикле работы сети есть пакеты свысоким приоритетом, то они обслуживаются в первую очередь.

При этом пакеты с низким приоритетомоказываются «задавлены», в то время как с высоким даже не знают о них. Это плохо.Взвешенная справедливая очередь (англ. Weighted fair queuing, WFQ) — механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использованияодного канала передачи данных несколькими конкурирующими потоками. В данном случае под потокомпонимается очередь пакетов данных.Это обобщение алгоритма честных планировщиков (англ.

Fair Queuing) (FQ). Оба планировщикаимеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью R используется для N потоков, то скорость обработки каждого из них будет R/N при использовании честногопланировщика.Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется N активных потоков, с приоритетами 1 , ..., , то i-ый поток будет иметь скорость: .∑︀=1∙ FIFO очередь – нет приоритетов, не гарантирована скорость.∙ Строгие приоритеты: высокоприоритетный трафик «не видит» низкоприоритетного трафика в сети.Полезно, когда высокоприоритетного трафика ограниченное количество.∙ Waited Fair Queuing (WFQ) позволяет каждому потоку обеспечить гарантированный сервис, планируя их в порядке bit-by-bit finishing time.13Коммутация пакетов: гарантирование задержкиОсновные допущения:∙ Пакеты не теряются.∙ FIFO обслуживание.Поскольку мы не можем управлять процессом поступления, его можно ограничить.

Пусть число бит,которые могут поступить за период ограничены + .Где, например, = , = 1 – размер канала,тогда мы не столкнемся с проблемой переполнения буфера (для конкретного случая).34Одной из причин перегрузок является неравномерный трафик. Если бы этого не было, перегрузокможно было бы избежать.

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

Вместе с пакетами в ведро поступают маркеры, а пакеты выходят только при наличииопределенного числа маркеров. Тогда можно накапливать маркеры и кратковременно ускорять передачупакетов в сеть. Особенность – при переполнении буфера маршрутизатору временно будет запрещенопередавать пакеты в сеть. + = , тогда = − , где – длительность временного увеличения трафика на входе, –скорость поступления маркеров Б/с, – максимальная скорость входного трафика Б/с, – емкость корзины35в байтах.Несмотря на то, что технически это возможно, лишь некоторые сети могут управлять е2е задержкой.Причины:1. Слишком сложно и хлопотно.2.

В большинстве сетей комбинация прогнозирования и приоритетов дает вполне приемлемые результаты.∑︀e2e задержка, = ( + + ()).∙ Если мы знаем длину очереди и дисциплину ее обслуживания, то мы можем ограничить величинузадержки в ней.∙ Выбрав длину очереди, и, используя WFQ, мы можем определить скорость обслуживания.∙ Поэтому самое главное не допустить сброса пакетов. Для этого можно использовать текущий буфер.∙ Таким образом, мы можем ограничить величину е2е задержки.14Управление потоком при пакетной коммутацииВ компьютерных сетях неизбежны потери пакетов данных, в частности, из-за переполнения буфернойпамяти хотя бы одного из узлов, расположенных на пути от источника к приёмнику, включая последний.Такие потери, связанные с переполнениями, в дальнейшем именуются перегрузками узлов сети.Существует множество способов предотвращения и устранения перегрузок; эти способы, в большинстве своем, основаны на управлении потоками данных. Особое место занимает обслуживание пакетов сучетом их приоритетов.Способ 1.

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

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