Учебно-методическии комплекс дисциплины «Компьютерные сети» для специальности 6М011100 — «Информатика» (стр. 54 )

Но даже при N=32 (например, для 32-разрядного IP-адреса) скорость просмотра таблицы методом двоичного поиска недостаточно высока для маршрутизации в современных магистралях. Например, если на каждом шаге работы алгоритма требуется одно обращение к памяти, то при памяти со временем доступа 40 не уровня одного миллиона операций в секунду достичь не удастся. Для увеличения скорости поиска применяются несколько приемов. Один из таких приемов заключается в использовании ассоциативной памяти (Content Addressable Memory, САМ). В маршрутизаторах Cisco 8500 каждый порт оснащен САМ-памятью объемом 64 Кбайт. Другой метод увеличения скорости поиска состоит в том, что недавно полученные записи таблицы продвижения данных хранятся в кэше. В данном методе важен размер кэша. В последние годы были предложены еще более быстрые структуры данных, позволяющие находить записи в таблице за log(JV) шагов, а также новые методы сжатия таблиц продвижения данных. Аппаратный метод оптимизации поиска в таблице, использующий тот факт, что в адресе, как правило, ищутся 24 или меньше значимых разрядов.

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

Коммутационный блок

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

Рис. 11.8 Три метода коммутации

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

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

Маршрутизаторы, коммутирующие пакеты через память, во многом напоминают мультипроцессоры с коллективным доступом к памяти. К таким маршрутизаторам относятся коммутаторы серии Catalyst 8500 компании Cisco и маршрутизаторы Bay Network Accelar 1200.

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

Учитывая, что пропускная способность современной шины может превышать ги-габит в секунду, метод коммутации через шину часто оказывается достаточным для маршрутизаторов, работающих в корпоративных сетях. Основанный на использовании шины метод коммутации принят в ряде современных маршрутизаторов, включая Cisco 1900, коммутирующих пакеты по шине Packet Exchange Bus с пропускной способностью 1 Гбит/с. Система CoreBuilder компании 3Com соединяет порты, располагающиеся в различных коммутирующих модулях при помощи шины PacketChannel с пропускной способностью 2 Гбит/с.

□ Коммутация с использованием соединительной сети. Один из способов преодолеть ограничения пропускной способности одной общей шины заключается в использовании более сложной соединительной сети, подобной сети, связывающей процессоры в мультипроцессорных системах. Матричный коммутатор представляет собой соединительную сеть, состоящую из 2Л/Гшин, соединяющих N входных портов с JV выходными портами, как показано на рис. 4.35. Прибывающий на входной порт пакет перемещается по горизонтальной шине до пересечения с вертикальной шиной, ведущей к нужному выходному порту. Если ведущая к выходному порту вертикальная шина свободна, пакет переносится в выходной порт. Если в данный момент вертикальная шина уже используется для передачи пакета в тот же самый выходной порт из другого входного порта, тогда пакет блокируется и ставится в очередь входного порта.

В качестве соединительных сетей между входными и выходными портами также предлагалось использовать коммутационные блоки Delta и Omega. В коммутаторах семейства Cisco 12000 применяется соединительная сеть, обеспечивающая пропускную способность до 60 Гбит/с. одна из современных тенденций в устройстве соединительной сети заключается в том, что IP-дейтаграмма переменной длины фрагментируется на ячейки фиксированной длины, которые затем маркируются и коммутируются через соединительную сеть. На выходном порту из этих ячеек восстанавливается исходная дейтаграмма. Ячейки фиксированной длины и внутренняя маркировка существенно упрощают и ускоряют коммутацию пакета через соединительную сеть.

Выходные порты

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

Рис. 11.9 Обработка данных в выходном порту

Очереди

Глядя на конфигурацию, изображенную на рис. 11.8, и учитывая функциональность входного и выходного портов, очевидно, что очереди пакетов могут образовываться как на входных, так и на выходных портах. Необходимо рассмотреть эти очереди несколько подробнее, поскольку при увеличении их размеров буферное пространство маршрутизатора, в конце концов, исчерпывается, и в результате маршрутизатор начинает терять пакеты. Ранее уже вскользь упоминалось, что пакеты «теряются в сети» или «отбрасываются маршрутизатором». Это происходит именно в этих очередях. Точное место, в котором теряется пакет (очередь входного порта или очередь выходного порта), зависит от интенсивности трафика, относительной пропускной способности коммутационного блока и скорости передачи данных в линии связи, что будет показано далее.

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

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

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