Рекомендовано для студентов специальности 220100, 220200, 220400 и других смежных специальностей
Составитель Крылов Ю. Д.[1]
Теоретические пояснения. 1
Содержание отчета. 5
Варианты заданий. 5
Контрольные вопросы.. 6
Цель работы – ознакомление с методами определения кратчайших путей коммутационными между узлами в вычислительных сетях.
Теоретические пояснения
Распределение каналов и потоков информации на линии связи производится с учетом длины пути. Для оценки длины пути используются различные критерии: число транзитных участков между взаимодействующими узлами коммутации (УК); протяженность пути; качество тракта передачи; надежность передачи и т. д.
Кратчайшим путем передачи информации называется путь, для которого критерий длины пути имеет наименьшее значение по сравнению с его значением для других возможных путей.
В теории потоков все методы выбора кратчайших путей основаны на утверждении о том, что если кратчайший путь mij от произвольного УКi к УКj проходит через промежуточные УК1,…, УКk (Рис. 1), то кратчайшие пути μi1,…, μkj являются частями кратчайшего пути μij от УКi к УКj.
Рис. 1
Если длина пути μi1 равна li1, то lij = li1 + l1j. Так как μij является кратчайшим, то , где N – число узлов сети. Для нахождения кратчайшего пути от узла i к узлу j необходимо просмотреть все возможные пути и выбрать тот, у которого длина наименьшая.
Имеется ряд методов определения длины кратчайшего пути. Их можно разделить на две группы: методы нумерации узлов и матричные методы.
Матричный метод определения кратчайших путей позволяет найти длины кратчайших путей между всеми узлами сети одновременно и основывается на применении операций над матрицами расстояний.
Структуру сети связи с указанием длин ветвей можно описать в виде матрицы расстояний (длин) непосредственных связей L1 = ||l1ij||, где элемент l1ij определяет длину дуги βij.
Пример. Пусть сеть связи имеет вид представленный на Рис. 2.
Рис. 2
Цифры на дугах соответствуют длинам дуг. Тогда матрица расстояний будет иметь вид