Примеры алгоритмов.
Алгоритмы управления маршрутизацией
В этом случае к каждому пакету прибавляется счетчик хопов. Отправитель устанавливает этот счетчик и каждый узел сети, который его пересылает, уменьшает этот счетчик на 1. Каждая станция запоминает пересланные пакеты и не посылает их ещё раз. Данный метод оптимизации очень продуктивен в сетях с топологией, отличной от дерева. Связующее дерево (Spanningtree): граф, не содержащий петель. Связующее… Читать ещё >
Примеры алгоритмов. Алгоритмы управления маршрутизацией (реферат, курсовая, диплом, контрольная)
Алгоритм связующего дерева (Адаптивные алгоритмы).
Связующее дерево (Spanningtree): граф, не содержащий петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов.
Reverse path forwarding (Reverse path flooding).
Алгоритм является самым простым и неадаптивным вариантом. Каждый полученный пакет пересылается по всем линиям, за исключением той, через которую он был получен. При этом только отправитель должен знать все связующее дерево. Алгоритм: Каждый маршрутизатор знает путь, который он должен использовать для unicast-пакетов. При получении пакета проверяется, был ли пакет получен по линии, которая обычно используется и пересылается по всем линиям, за исключением той, через которую он был получен. В противном случае пакет отбрасывается.
Reversepathbroadcast.
В отличие от Reversepathforwarding пакеты отправляются только по линиям, по которым другие узлы принимают данные.
ShortestPath Routing.
Данный алгоритм подсчитывает наименьший маршрут от корня дерева до узлов. Смысл заключается в создании пучка узлов Q, для которых уже был определен оптимальный маршрут. Оператор генерирует таблицы маршрутизации, которые загружаются при его инициализации и более не изменяются. Основывается наалгоритме Дейкстры.
Алгоритм:
наименьшее расстояние от A до D;
узел A помечается как рассматриваемый;
присвоить всем соседним узлам значение с дистанцией до рассматриваемого узла B (2, A), G (6, A) и добавить их в список кандидатов;
выбрать из списка кандидатов узел с наименьшей дистанцией B (2, A) ;
пометить этот узел как рассматриваемый и добавить его в дерево;
перейти к пункту 2.
Неадаптивные алгоритмы.
Flow-Based Routing.
Данный алгоритм является одним из неадаптивных алгоритмов. Он учитывает не только дистанцию между маршрутизаторами, но и загрузку сети. Полезен для нахождения маршрута для больших дистанций с большими задержками в доставке пакетов Пример Дан граф для мощности и матрица трафика.
Рисунок 3.1 Граф для мощности Рисунок 3. 2 Матрица трафика.
Подсчет загрузки каждой линии:
взять одно из ребер графа;
найти, где оно встречается в таблице;
сложить все скорости из таблицы для этого ребра.
Line. | лi (packts/sec). |
AB. | 3 (AB) + 7 (ABC) + 7 (BAD) + 4 (BAF) + 3 (BADG) =24. |
AD. | 4 (AD) + 2 (ADE) + 2 (ADG) + 5 (ADEH) + 7 (BAD) + 3 (BADG) = 23. |
AF. | 5 (AF) + 4 (BAF) = 9. |
BC. | 7 (ABC) + 3 (BC) + 4 (BCH) = 14. |
BE. | 3 (BE) = 3. |
CE. | 7 (CED) + 5 (CE) + 3 (CEDF) = 15. |
CH. | 4 (BCH) + 5 (CHG) + 3 (CH) = 12. |
DE. | 2 (ADE) + 5 (ADEH) + 7 (CED) + 3 (CEDF) + 2 (DE) + 9 (DEH) + 3 (EDF) + 9 (FDEH) = 40. |
DF. | 3 (CEDF) + 9 (DF) + 3 (EDF) + 9 (FDEH) = 24. |
EH. | 5 (ADEH) + 9 (DEH) + 1 (EHG) + 2 (EH) + 9 (FDEH) = 26. |
FG. | 1 (FG) = 1. |
GH. | 1 (GH) + 1 (EHG) + 5 (CHG) = 7. |
DG. | 2 (ADG) + 3 (BADG) + 2 (DG) = 7. |
Подсчет задержки для каждого графа по формуле Ti = 1/ (мCi-лi).
Line. | лi (packts/sec). | мCi (packts/sec). | Ti (msec). |
AB. | 38. 46. | ||
AD. | 37. 04. | ||
AF. | 37. 5. | 35. 09. | |
BC. | 90. 91. | ||
BE. | 21. 28. | ||
CE. | 16. 67. | ||
CH. | 26. 32. | ||
DE. | |||
DF. | |||
EH. | 41. 67. | ||
FG. | 10. 1. | ||
GH. | 62. 5. | 18. 02. | |
DG. | 62. 5. | 18. 02. |
Подсчет стоимости каждого ребра по формуле: Wi = лi/?лi.
Line. | лi (packts/sec). | мCi (packts/sec). | Ti (msec). | Wi. |
AB. | 38. 46. | 0. 117. | ||
AD. | 37. 04. | 0. 112. | ||
AF. | 37. 5. | 35. 09. | 0. 044. | |
BC. | 90. 91. | 0. 068. | ||
BE. | 21. 28. | 0. 015. | ||
CE. | 16. 67. | 0. 073. | ||
CH. | 26. 32. | 0. 059. | ||
DE. | 0. 195. | |||
DF. | 0. 117. | |||
EH. | 41. 67. | 0. 127. | ||
FG. | 10. 1. | 0. 005. | ||
GH. | 62. 5. | 18. 02. | 0. 034. | |
DG. | 62. 5. | 18. 02. | 0. 034. |
Подсчет общей задержки Toverall = ?Ti*Wi. Получаем: Toverall=162. 531msec.
Так как полученное значение слишком велико, то его можно уменьшить за счет замены пути с самой большой задержкой DF (Ti, max = 1000msec) на путь D->G->F.
Flooding (алгоритм «затопления»).
Является самым простым алгоритмом маршрутизации для распространения информации по сети. При получении пакета каждый узел пересылает его соседним узлам за исключением того, от которого пришёл пакет.
Рисунок 3.3Алгоритм «затопления».
Данный алгоритм обладает низкой эффективностью из-за повышенной загрузки сети.
Способы оптимизации:
Для улучшения эффективности алгоритма используются следующие способы:
Hopcounter.
В этом случае к каждому пакету прибавляется счетчик хопов. Отправитель устанавливает этот счетчик и каждый узел сети, который его пересылает, уменьшает этот счетчик на 1.
FloodingwithAcknowledge («затопление с подтверждениями»).
Одной из проблем простого алгоритма «затопления» является то, что отправитель не знает о том, достиг ли пакет всех узлов сети. Каждый из узлов сети отправляет подтверждение о получении, если он получил подтверждение от всех узлов, которым он отправлял пакеты.
Рисунок 3.4Алгоритм «затопления» с подтверждениями.
Uniqueresend.
Каждая станция запоминает пересланные пакеты и не посылает их ещё раз. Данный метод оптимизации очень продуктивен в сетях с топологией, отличной от дерева.