МАРШРУТИЗАЦИИ СЕТИ TYMNET

Алгоритм маршрутизации сети TYMNET, первоначально реализо­ванный в 1971 г., основан на методе кратчайшего пути и является адаптивным, как и алгоритмы TYMNET. Однако способы реализации идеи адаптивного выбора кратчайшего пути значительно различаются в этих двух сетях.

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

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

Алгоритм TYMNET хорошо показал себя в работе в течение не­скольких лет. Несколько его идей применены в сети Codex, имеющей сходную структуру. Алгоритм Codex, однако, является распределен­ным и более сложным. Слабое место алгоритма TYMNET - его уязвимость к ошибкам и выходам из строя супервизора. Для повышения на­дежности в сети TYMNET используются узлы, дублирующие работу су­первизора. В распределенном варианте, используемом сети Codex, длины всех линий передаются в широковещательном режиме всем узлам (как в сети ARPANET), и каждый узел сам должен отвечать за маршрутизацию цепей, возникающих или заканчивающихся в этом узле.