Algorytm wyboru trasy w BGP – RFC4271

Pamię­ta­cie może ze szkoły zda­nie, które pra­wie każdy nauczy­ciel wygła­szał:

< wsta­w_co­kol­wie­k> musisz znać, nawet jak Cię obu­dzą w środku nocy?

To dzi­siaj wpis na bar­dzo ważny temat: Algo­rytm wyboru trasy w BGP.

RFC 4271 – Algorytm wyboru trasy w BGP

Opis algo­rytmu powstał na pod­sta­wie RFC4271. Jest nie­za­leżny od imple­men­ta­cji algo­rytmu BGP przez pro­du­cen­tów sprzętu sie­cio­wego i opro­gra­mo­wa­nia.

Wybór trasy w protokole BGP

Algorytm wyboru trasy w BGP wybiera pożądaną ścieżkę do określonego prefiksu. Wybór dokonywany jest z minimum dwóch ścieżek. Jeśli jest jedna ścieżka, wtedy staje się najlepsza (best).

Next hop

Algo­rytm spraw­dza, czy w tablicy routingu są infor­ma­cję o next hop dla danego pre­fiksu. Czy ma wie­dzę, przez jakie „drzwi ma wypchnąć” ruch do tego pre­fiksu. Jeśli nie ma infor­ma­cji o next hop, wtedy taki pre­fiks jest porzu­cany i nie bie­rze udziału w dal­szej czę­ści algo­rytmu.

Local Pre­fe­rence

Jeśli router ma w tablicy routingu next hop, wtedy porów­ny­wany jest atry­but Local Pre­fe­rence. Dla przy­po­mnie­nia, Local pre­fe­rence to war­tość licz­bowa z zakresu od 0 do 4294967295. Jest prze­ka­zy­wana wewnątrz AS pomię­dzy route­rami.

Pre­fiks z wyż­szym Local pre­fe­rence „wygrywa”.

 A co jeśli Local Pre­fe­rence jest równy?

AS-PATH

Wtedy porów­ny­wane są AS-PATH. Krót­szy AS-PATH wygrywa. AS-PATH to atry­but skła­da­jący się z nume­rów AS (sys­te­mów auto­no­micz­nych), przez które trzeba „przejść”, aby dostać się do danego pre­fiksu. Jeśli trasa zawiera w AS-PATH numer AS, któ­rego czę­ścią jest router, wtedy trasa jest porzu­cana. Jest to mecha­nizm zabez­pie­cza­jący przed powsta­niem pętli w routingu BGP.

A gdy AS-PATH są sobie równe?

Ori­gin

Porów­ny­wany jest atry­but Ori­gin, czyli pocho­dze­nie pre­fiksu. Ori­gin może mieć trzy stany: IGP, EGP i incom­plete.

Algo­rytm BGP pre­fe­ruje IGP bar­dziej niż EGP. Najm­niej pre­fe­ro­waną trasą jest ta, która ma usta­wiony stan na incom­plete.

A co jeśli w tym kroku nie udało się wybrać ścieżki?

MED

Porów­ny­wane są war­to­ści MED. Trasa z niż­szą war­to­ścią MED jest pre­fe­ro­wana. War­tość MED jest porów­ny­wana, wtedy gdy router nauczył się tras z tego samego, sąsied­niego AS. To zacho­wa­nie można zmie­nić. Można skon­fi­gu­ro­wać router, aby porów­ny­wał MED dla tras pocho­dzą­cych z róż­nych sys­te­mów auto­no­micz­nych. W więk­szo­ści przy­pad­ków jest to ostatni krok w algo­rytmie wyboru trasy.

Jeśli MED są równe to co wtedy?

eBGP vs. iBGP

Kiedy atry­but MED jest równy, wybie­rana jest trasa, którą router „nauczył się” z eBGP. Ma tu zasto­so­wa­nie zasada „hot potato routing” – czyli wysła­nie ruchu do naj­bliż­szego wyj­ścia z sieci. Pre­fe­ru­jąc eBGP nad iBGP zmniej­sza się obcią­że­nie połą­czeń wewnątrz sieci. Prze­ci­wień­stwem do hot potato routing jest cold potato routing, gdzie pre­fe­rujemy połą­cze­nia wewnętrzne.

Metryka IGP do next hop

Jeśli router nauczył się tras z iBGP, to pre­fe­ro­wana jest ścieżka z niż­szą metryką IGP do next hop (do drzwi, przez które ma wypchnąć ruch) ; -)

A jeśli obu tras router nauczył się z eBGP?

Wiek trasy (Age of route) – zacho­wa­nie zależne od imple­men­ta­cji

Wtedy porów­ny­wany jest wiek trasy. Star­sza trasa wygrywa. Jest to podyk­to­wane więk­szą sta­bil­no­ścią sieci.

 Możemy mieć w swo­jej sieci cztery trasy do tego samego pre­fiksu. Trzy trasy nam zni­kają. Zostaje tylko jedna. Po jakimś cza­sie trasy zaczy­nają być aktywne. Bez spraw­dze­nia wieku trasy, router mógłby zacząć prze­łą­czać się na now­sze trasy. Skut­ko­wa­łoby to dużą niesta­bil­no­ścią dzia­ła­nia całej sieci.

Router ID

Pre­fe­ro­wane są trasy, któ­rych router nauczyć się od sąsiada z niż­szym router ID.

RT1 router-ID: 10.10.10.1

RT2 router-ID: 192.168.10.1

Trasy z RT1 są wybie­rane.

IP address

Jeśli para­metr router ID jest taki sam, to porów­ny­wane są adresy IP route­rów. Wybie­rane są trasy pocho­dzące z routera o niż­szym adre­sie IP.

Pod­su­mo­wa­nie

Cały algo­rytm wyboru trasy w BGP można stre­ścić do paru punk­tów:

1. Wery­fi­ka­cja czy router ma next-hop
2. Wyż­sza war­tość Local pre­fe­rence
3. Krót­szy AS-PATH
4. Niż­sza war­tość MED
5. Wiek trasy – star­sza trasa jest pre­fe­ro­wana (uza­leż­nione od imple­men­ta­cji)

Musisz pamię­tać, że to jest opis ogólny. Każdy z pro­du­cen­tów ma swoją imple­men­ta­cję. Niek­tóre ele­menty algo­rytmu i ich zacho­wa­nie mogą się róż­nić. Za każ­dym razem, gdy debug­gu­jesz dzia­ła­nie BGP sprawdź, pro­szę doku­men­ta­cję pro­du­centa.

Linki do doku­men­ta­cji pro­du­cen­tów (07.03.2019):

Cisco Systems

Juni­per Networks

Nokia

Poni­żej algorytm wyboru trasy w BGP w formie tabeli.