Тема 13.

Разпределена маршрутизация с дистантен вектор


страницата се нуждае от дописване/преглеждане


Както стана ясно, централизираната маршрутизация има своите недостатъци и затова започват да се търсят други начини за осигуряване на динамично маршрутизиране. Появява се децентрализираното '(разпределено) маршрутизиране: устройството само си изчислява маршрутната таблица. Идеята се оказва продуктивна и се появяват множество разработки (протоколи), базирани на нея. Според начина на съставяне на таблицата, протоколите се разделят на няколко класа. Един от най-големите е маршрутизирането с дистантен вектор (distance vector).

Distance vector - що е то?

Distance vector-протоколите определят най-добрия маршрут, като разглеждат два параметъра: метрика (metric) и следващ съсед (next hop)1. Метриката играе ролята на цена: ниската метрика означава добър (бърз, ненатоварен) маршрут. Next hop пък указва откъде минава този маршрут. Ако двете се разглеждат като разстояние и посока, се получава нещо като вектор на отстоянието (distance vector) - оттам и името на метода. Метриката се мери по различен начин в различните протоколи - брой хостове от източника до целта (hop count), бързина на връзката (bandwidth), натовареност (load), надеждност (reliability), или някаква линейна комбинация на изброените.

За принципа на дистантния вектор, доста добра аналогия са указателните табели: единственото, което се научава от тях, е какво разстояние има до целта и откъде се минава за натам - и това е напълно достатъчно, за се вземе решение накъде да се тръгне.

За да може да се достигне целта обаче, е нужно на всяко разклонение по пътя да има набор от табели, които да дават точна информация за отстоянието и посоката на целта. В термините на маршрутизацията, нужно е всеки рутър по избрания маршрут да съдържа вярна и актуална маршрутна таблица. За да постигнат това, рутърите, работещи по протокол с дистантен вектор, изпълняват алгоритъма алгоритъма на Bellman-Ford (в някои случаи, може би този на Dijkstra). Те периодично обменят таблиците си със своите съседи, и извършват релаксация на текущите маршрути2.

Изграждане на таблиците

Хубава илюстрация на работата на DV-протокол (в текущия прозорец)

При включване на нов рутър в мрежата, първата му работа (чрез Echo пакети или по друг начин) е да открие своите съседи и (ако е нужно) да измери метриката до тях. С тази информация се попълва таблицата му. До възли (рутъри), до които той няма директна връзка, се счита, че съществува връзка с метрика $\infty$ за нуждите на алгоритъма. През определен интервал от време маршрутната таблица се разпраща до съседите на рутъра, а от тях се получава тяхната и се извършва релаксация. Така поетапно таблицата се попълва и подобрява, докато се достигне до оптималното състояние - тогава мрежата е конвергирала.

DV5routers.png
Етап на ъпдейти Разстояние от B до A Разстояние от C до A Разстояние от D до A Разстояние от E до A
Начален $\infty$ $\infty$ $\infty$ $\infty$
1 1 $\infty$ $\infty$ $\infty$
2 1 2 $\infty$ $\infty$
3 1 2 3 $\infty$
4 1 2 3 4

На първа стъпка, B открива съседа си A и го вписва на отстояние 1. На втора стъпка, B праща таблицата си на C, добавяйки преди това единица към цените на маршрутите, за да отчете ребрата между себе си и съседите. C открива по-добър маршрут (2) до A от досегашния си (безкрайност) и го записва в таблицата си. Същото се повтаря на трета стъпка между C и D, и на четвърта, между D и E. След стъпка 4, се наблюдава конвергенция на мрежата - всички маршрути са оптимизирани.

По същия начин, при отпадане на някоя от връзките, промяната се отразява първо в двата съседа, които са загубили връзка, след това в техните съседи, и тъй нататък.

Проблеми на Distance vector-протоколите.

Бавно конвергиране

Тъй като ъпдейтите се изпращат през период от време, новата информация се разпространява на периодични "вълни": директно свързаните съседи научават на края на първия интервал за ъпдейти, тези през един възел - на края на втория, и тъй нататък. Получава се така, че по-далечните рутъри научават за промяната след известно време. В мрежи с голям диаметър (най-голямото минимално разстояние между два рутъра) това се превръща в значителен проблем, тъй като в тях е голяма вероятноста да се случват фалове, и в голяма част от времето мрежата няма да е конвергирала.

Цикли (Routing loops)

Routing loops и решенията за тях
В горната конфигурация, може да се случи така, че връзката A-B да се разпадне. Тогава B ще отбележи в таблицата си, че A е недостъпен - метриката на връзката ще бъде безкрайност. В това положение може да се получи routing loop: C има в таблицата си маршрут през B до A, чиято цена е по-добра от безкрайност. При ъпдейт, B ще получи този маршрут, увеличен с единица, но няма да знае, че той всъщност минава през него, и ще го запише в таблицата си. Тогава, пакет от D за A ще мине през C, оттам през B, оттам отново през C, отново през B, и така нататък, докато TTL-полето на пакета се занули.

Count to infinity

В горната ситуация, метриката от C до A е 2, а от B до A - 3. При следващ ъпдейт, C ще получи от B маршрут с цена 4. Понеже най-добрият маршрут на C минава през B, то C ще извърши релаксация, и тъй като новият маршрут е единствен, C ще го запише с метрика 4.3. На следваща стъпка, това се повтаря в обратна посока - B получава от C маршрут с цена 5, и по същите съображения го впише с таблицата си. Това продължава потенциално до безкрайност.

Решения на проблемите

Безкрайност

Безкрайността е стойност на метриката, при която дадена мрежа (рутър) се счита за недостъпна. Тази стойност зависи от конкретния distance vector протокол. За RIP, например, тя e 16, докато за EIGRP e 224. Безкрайността предотвратява count-to-infinity (и може да се ползва при инициализацията). Същевременно, обаче, безкрайността ограничава мрежата по диаметър (най-голямото минимално разстояние между два рутъра), което означава, че distance vector протоколите могат да се ползват в малки до средни мрежи.

Split horizon

Това правило диктува, че ъпдейт за даден маршрут не се изпраща по същия интерфейс (към същия рутър), по който е получен. В нашия пример, ако C спазва split horizon, няма да изпрати фаталния ъпдейт до B с метрика 3. Правилото се използва, за да предотврати маршрутните цикли, но, само по себе си, не е достатъчно за тази цел. Примерът:
triangle.png
Тук, маршрутът C-D отпада. При ъпдейт, C известява A и B за отпадналия маршрут. Може да се получи така, обаче, че A да получи ъпдейта от C, но B да изпрати своя ъпдейт, с вече невярната информация, към A, преди да получи ъпдейта си от C. Така отново ще се завърти порочен кръг и A и B ще влязат в count-to-infinity. Затова обикновено split horizon се използва заедно с други механизми.

Таймъри

Различните distance vector протоколи имат различни таймъри, които използват, за да регулират ъпдейтите.
Ако за определен период от време по даден маршрут не бъде получен ъпдейт, то маршрутът се счита за неработещ (невалиден).
За да успеят останалите рутъри да научат за отпадането на маршрута, е възможно той да се постави в holddown. Това е един вид замразяване: в ъпдейтите, които рутърът изпраща се отбелязва, че маршрутът е невалиден, но метриката му остава същата в таблицата. Ъпдейти за този маршрут се получават, но поради факта, че е бил най-добър, той се променя само ако пристигне ъпдейт със същата или по-добра метрика - ще рече, че или връзката се е възстановила, или се е появила някоя нова и по-добра. В такъв случай holddown се премахва.
Маршрут, който е бил в holddown достатъчно дълго, се премахва от таблицата.

Route poisoning (Извън лекциите)

При този механизъм, метриката на неработещ маршрут се променя на безкрайност, след което той се съобщава като невалиден на съседите. Помага рутърите по-бързо да научат за отпадналия маршрут.4

Triggered updates (Извън лекциите)

Triggered update е специален ъпдейт, който се изпраща моментално при отпадане на маршрут (или мрежа, свързана към рутър), без да чака да изтече периодът. Това ускорява конвергенцията. В много случаи holddown и route poisoning-механизмите работят коректно и ефективно само с triggered update.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License