Comments 8
Ориентированный означает, что пройти по такому графу можно только в одном направлении.
Ориентированный значит, что рёбра однонаправленные. В самом графе могут быть и циклы.
Так называемые L2-коммутаторы не являются участниками ip-сетей и в алгоритме кратчайших путей не участвуют. Они являются мостами для организации взаимодействия подключенных маршрутизаторов, позволяя экономить физические порты роутеров и уменьшать количество настроек.
Немного зауженный взгляд на свитчи. Нельзя сказать, что написанное Вами неверно, но я б сказал что свитчи являются для Ethernet примерно тем же, чем роутеры для IP-сетей.
Поиск по ресурсу выдал примерно 20 страниц со статьями, но к сожалению среди них не было ни одной подробной про работу алгоритма в ip-сетях.
Обычно алгоритм выбирают под задачу, а не ищут решения задачи с использованием какого-то алгоритма. Насколько я знаю, алгоритм Беллмана-Форда используется в RIP и BGP. Почему так? У меня только догадки. Может быть Вы могли бы в статье раскрыть свой выбор. Заодно и рассказать про оценку сложности конкретно вашей реализации на плюсах с использованием set вместо очереди с приоритетом для непосещённых узлов, что получается если её сравнить по вычислительной сложности и затратам памяти с тем же Беллманом-Фордом.
После прочтения я так и не понял, что для меня в этой статье, как бы я мог воспользоваться этим. Может разве что кто-то захочет написать свою реализацию протокола динамической маршрутизации. Отчасти статья выглядит как курсовая работа, раздутая до требуемого объёма листингами.
По первым двум замечаниям внёс правки. По свитчам расписал, хотя считаю это лишнее, т.к. тема вообще никак не относится к свитчам. И объединяет ip и ethernet только тот факт, что и тут и там есть src и dst и некий процесс табличного поиска с целью понять через какой порт пульнуть датаграмму (а точнее запрограммировать ASIC'и), на этом сходства кончаются. На L2-свитчах (как и на L3 в режиме L2) Вы не построите сеть в виде циклического графа - там любые параллельные связи это автоматически петля со всеми вытекающими (идём в сторону STP, но опять же статья вообще не про эту область знаний). Поэтому описал наличие и функционал коммутаторов так сжато, как смог. Почему именно Дейкстра? Просто потому, что используется в OSPF и на данном этапе мне было интересно разобраться именно с этим протоколом. В дальнейшем не исключено, что и Беллман-Форд будет рассмотрен. Насколько я помню алгоритм Дейкстры это производная от БФ, либо имеет много общего. Контейнер set использовался скорее из-за его простоты для понимания, хотя согласен, что оптимизация до приоритетной очереди здесь напрашивается.
Так называемые L2-коммутаторы не являются участниками ip-сетей и в алгоритме кратчайших путей не участвуют. Они являются мостами для организации взаимодействия подключенных маршрутизаторов, позволяя экономить физические порты роутеров и уменьшать количество настроек.
Это верно исключительно для тупых хабов НЕуправляемых коммутаторов. Но уже простейший управляемый коммутатор второго уровня очень даже способен повлиять на описываемый алгоритм. Например, включив где-нибудь изоляцию портов...
u32i
мне интересно, зачем нужен постфикс у типа. неужели кто-то пользуется беззнаковыми вещественными типами, да ещё и в сетях? или это какое-то определение endianness?
Адаптация алгоритма Дейкстры для расчёта кратчайших путей в IP-сетях