Алгарытм дыфузнага абнаўлення DUAL

Перад тым як пачаць чытанне гэтага артыкула, раім азнаёміцца ​​з матэрыялам пра разлік шляху па алгарытме Bellman - ford.

Алгарытм дыфузнага абнаўлення (Diffusing Update Algorithm -DUAL) - адзін з двух абмяркоўваюцца тут алгарытмаў, першапачаткова прызначаных для рэалізацыі ў размеркаванай сеткі. Ён унікальны тым, што таксама выдаляе інфармацыю аб дасяжнасці і тапалогіі, якая змяшчаецца ў канчатковым аўтамаце алгарытму. Іншыя абмяркоўваюцца тут алгарытмы пакідаюць выдаленне інфармацыі на меркаванне рэалізацыі пратаколу, а не разглядаюць гэты аспект работы алгарытму ўнутры самога алгарытму.

Да 1993 году Bellman-Ford і Dijkstra былі рэалізаваны як размеркаваныя алгарытмы ў некалькіх пратаколах маршрутызацыі. Вопыт, атрыманы ў выніку гэтых ранніх рэалізацый і разгортванняў, прывёў да "другой хвалі" даследаванняў і разважанняў аб праблеме маршрутызацыі ў сетках з камутацыяй пакетаў, што прывяло да з'яўлення вектара шляхі і DUAL.

Паколькі DUAL распрацаваны як размеркаваны алгарытм, лепш за ўсё апісаць яго працу ў сеткі. Для гэтай мэты выкарыстоўваюцца малюнкі 8 і 9. Каб растлумачыць DUAL, у гэтым прыкладзе будзе прасочвацца паток A, які вывучае тры пункта прызначэння, а затым апрацоўваюцца змены ў стане даступнасці для гэтых жа пунктаў прызначэння. У першым прыкладзе будзе разгледжана выпадак, калі ёсць альтэрнатыўны шлях, але няма downstream neighbor, другі разгледзіць выпадак, калі ёсць альтэрнатыўны шлях і downstream neighbor.

На малюнку 8 вывучэнне D з пункту гледжання A:

1. A пазнае два шляхі да D:

1. A не даведаецца шлях праз B, таму што B выкарыстоўвае A ў якасці свайго пераемніка:
2. A параўноўвае даступныя шляхі і выбірае самы кароткі шлях без завес:
3. A правярае пакінутыя шляху, каб вызначыць, ці з'яўляюцца якія-небудзь з іх downstream neighbors:

A ведае гэта, таму што C аб'яўляе маршрут да D са сваёй лакальнай метрыкай, роўнай 3.

A захоўвае лакальную метрыку C у сваёй табліцы тапалогіі.

Такім чынам, A ведае лакальную кошт у C і лакальную кошт у A.

1. 3 (кошт у C) = 3 (кошт у A), таму гэты маршрут можа быць пятлёй, такім чынам, C ня задавальняе ўмове выканальнасць. C ня мае атрыбут downstream neighbors.

Downstream neighbors ў DUAL называюцца магчымымі пераемнікамі. Выкажам здагадку, што канал [A, H] не працуе. DUAL лепш памаўчаць на перыядычныя абнаўлення, таму A не можа проста чакаць іншага абнаўлення з дакладнай інфармацыяй. Хутчэй A павінен актыўна прытрымлівацца альтэрнатыўнаму шляху. Такім чынам, гэта дыфузны працэс выяўлення альтэрнатыўнага шляху. Калі канал [A, H] не працуе, улічваючы толькі D:

1. A правярае сваю лакальную табліцу на прадмет магчымых пераемнікаў (Downstream neighbors).
2. Магчымых пераемнікаў няма, таму A павінен знайсці альтэрнатыўны шлях без завес да D (калі ён існуе).
3. A адпраўляе запыт кожнаму суседу, каб вызначыць, ці ёсць які-небудзь альтэрнатыўны шлях без завес да D.
4. У C:
5. У B:
6. A атрымлівае гэтыя адказы:

На малюнку 9 пункт прызначэння (D) быў перамешчаны з H на E. Гэта будзе выкарыстоўвацца ў другім прыкладзе.

У гэтым прыкладзе ёсць магчымы пераемнік (downstream neighbor).

Вывучэнне D з пункту гледжання A:

1. A пазнае два шляхі да D:
2. A не даведаецца ніякага шляху праз B:
3. A параўноўвае даступныя шляхі і выбірае самы кароткі шлях без завес:
4. A правярае пакінутыя шляху, каб вызначыць, ці з'яўляюцца якія-небудзь з іх downstream neighbors:

Калі канал [A, C] не працуе, проста разглядаючы A:

1. A праверыць сваю табліцу лакальнай тапалогіі на прадмет магчымага пераемніка.
2. Магчымы пераемнік існуе праз H.
3. A перамыкае сваю лакальную табліцу на H як лепшы шлях.
4. A адпраўляе абнаўленне сваім суседзям, адзначаючы, што яго кошт дасягнення D змянілася з 3 да 4.

Як вы можаце бачыць, апрацоўка, калі існуе магчымы пераемнік, нашмат хутчэй і прасцей, чым без яго. У сетках, дзе быў разгорнуты пратакол маршрутызацыі з выкарыстаннем DUAL (у прыватнасці, EIGRP), адной з асноўных мэт праектавання будзе абмежаванне аб'ёму любых запытаў, генераваных ў выпадку адсутнасці магчымага пераемніка. Вобласць запыту з'яўляецца асноўным вызначальным фактарам таго, як хутка завяршаецца двайны алгарытм і, такім чынам, як хутка сыходзіцца сетку.

На малюнку 10 паказаны базавы скончаны аўтамат DUAL.

Рэчы, якія ўваходзяць у route gets worse (пагаршэнне маршруту), могуць прадстаўляць сабой:

• Адмова падлучанага канала або суседа
• Атрыманне абнаўлення для маршруту з больш высокай метрыкай
• Атрыманне запыту ад бягучага пераемніка
• Атрыманне новага маршруту ад суседа
• Выяўлены новы сусед, а таксама маршруты, па якіх ён можа дабрацца
• Атрыманне ўсіх запытаў, адпраўленых суседзям, калі маршрут пагаршаецца