Routing dynamiczny

Routing dynamiczny

Celem protokołu routingu jest stworzenie

i utrzymywanie tablicy routingu.

Routing dynamiczny

Algorytmy routingu podzielić na:

* a. wektora odległości,
* a. stanu łącza,
* a. hybrydowe zrównoważone.

W rozwiązaniach opartych na wektorze odległości

Określana jest odległość oraz kierunek (wektor)

do dowolnego łącza w intersieci.

Podejście oparte na analizie stanu łącza polega

na odtworzeniu dokładnej topologii całej intersieci

.

Warstwa łącza

Warstwa łącza

Warstwa sieci

Warstwa transportu

Warstwa sesji

Warstwa prezentacji

Miejsce w modelu OSI/ISO

Warstwa aplikacji

Zawiera programy
obsługi urządzeń i

odpowiadające im karty

interfejsów sieciowych.

Odpowiada

za fizyczne dołączenie

do kabla sieciowego

Obsługuje ruch pakietów w

sieci

Zapewnia przepływ danych

pomiędzy dwoma

komputerami, obsługując

znajdującą się nad nią

warstwę aplikacji

Obsługuje funkcje związane

z określoną aplikacją

Tablica routingu



Zawiera skojarzenie pomiędzy adresem IP przeznaczenia
(może to być zarówno pełny adres komputera jak i adres sieci)
a adresem IP routera następnego przejścia

bezp. dołączona

130.2.0.0

bezp. dołączona

120.0.0.0

IP nast. przejścia

Sieć docelowa

130.2.2.1

150.2.0.0

130.2.2.1

200.2.5.0

bezp. dołączona

200.2.5.0

bezp. dołączona

130.2.0.0

IP nast. przejścia

Sieć docelowa

200.2.5.2

150.2.0.0

130.2.1.1

120.0.0.0

?

0.0.5.
5

R0

120.1.3.
8

120.1.3.
8

130.2.
0.0

200.2.
5.0

150.2.
0.0

120.0.
0.0

R2

R3

120.1.1.1

130.2.1.
1

130.2.2.
1

200.2.5.
1

200.2.5.
2

150.2.1.
2

R1

Tablica routingu – wnioski



Routing IP jest dokonywany na podstawie

kolejnych przejść



Router nie zna pełnej trasy do żadnego z punktów

przeznaczenia



Routing jest możliwy dzięki przekazywaniu

datagramu do następnego routera. Zakłada się,

że kolejny router jest „bliżej” punktu

przeznaczenia niż komputer wysyłający

informację oraz że wysyłający komputer jest

połączony z jakimś routerem, który odbiera od

niego datagramy.

Podział Protokołów
Routingu

Routing
Statyczny

Routing
Dynamiczny

Wewnętrzny

Zewnętrzny

Z wektorem Stanu
odległości łącza

Z wektorem Stanu
odległości łącza

Zbieżność

Router potrzebuje czasu na znalezienie

alterantywnej ścieżki w wypadku zmiany topologii

sieci (np. awaria)

Czas, po którym routery będą miały jednakowy

“obraz” sieci jest zależny od konfiguracji (np. odstęp

między periodycznie rozsyłanymi pakietami)

Zbieżność

Czas wykrywania awarii:

Łącza szeregowe:

natychmiastowo (przerwa w obwodzie)

Token Ring i FDDI: od razu

Ethernet: dwa lub trzy cykle zegara “keepalive”

Brak EIGRP Hello

lub OSPF Hello

R1

N1

Pierwotna ścieżka

Alternatywna ścieżka

X

Równoważenie obciążenia

• Równe koszty ścieżek

R1

R4

N2

N1

R3

R2

T1

T1

T1

T1

Równoważenie obciążenia

• Zbliżone koszty ścieżek

R1

R4

N2

N1

R3

R2

T1

768K

512K

T1

Routing
statyczny vs. dynamiczny



Przewidywalny – trasa po

której pakiet jest przesyłany

jest dobrze znana i może

być kontrolowana.



Łącza nie są dodatkowo

obciążone wiadomościami

służącymi do routowania.



Łatwe do skonfigurowania w

małych sieciach.



Brak skalowalności



Brak obsługi redundantnych

połączeń



Nieumiejętność

dostosowania się do

dynamicznych zmian w

konfiguracji sieci



Skalowalność



Zdolność dostosowania się do

zmian topologii sieci



Łatwość konfiguracji – nie

popełniamy błędów



Większy stopień zawiłości

działania sieci. Im lepiej

protokół reaguje na zmiany w

sieci tym bardziej

skomplikowany musi być –

trudności w implementacji –

różnice pomiędzy sprzętem od

różnych producentów



Konieczność okresowej

wymiany danych to z punktu

widzenia użytkownika

niepotrzebne obciążenie sieci.

Klasyfikacja protokołów
routingu dynamicznego



Podział ze względu na obszary zastosowań

◦

protokoły wewnętrzne

◦

protokoły zewnętrzne



Podział ze względu na charakter
wymienianych informacji

◦

protokoły z wektorem odległości

◦

protokoły stanu łącza

Protokoły routingu —
wewnętrzne i zewnętrzne



Wewnętrzne

◦

Stosowane wewnątrz jednej domeny administracyjnej

◦

Proste, w małym stopniu obciążają routery

◦

Mało skalowalne

◦

RIP (Routing Information Protocol), IGRP (Interior Gateway Routing

Protocol), OSPF (Open Shortest Path First),



Zewnętrzne

◦

Odpowiadają za wymianę informacji pomiędzy dwiema

niezależnymi administracyjnie sieciami

◦

Dają się skalować, łatwo obsługują duże sieci

◦

Są skomplikowane, ilość dodatkowych informacji przesyłanych

siecią może szybko zablokować pracę małej lub średniej sieci

◦

EGP (exterior gateway protocol), BGP (border gateway protocol)



Można je zamieniać, ale nie jest to mądre, bo zostały

przystosowane do innego trybu pracy

Budowa tablic routingu



Routery otrzymują tablice od swoich

sąsiadów



Zapamiętują najlepszą znaną odległość do

określonego odbiorcy oraz router który

przesłał taką informację



Uaktualniają wpis jeśli odbiorą informację o

lepszej odległości



Obliczają minimalną odległość przyrostowo,

nie potrzebują przechowywać wszystkich

danych od sąsiadów

Routing Information Protocol
(RIP)



Router wysyła informacje co 30s do
wszystkich swoich sąsiadów — pakiety typu
broadcast — o znanych sobie sieciach i
odległości do nich



Miarą odległości jest liczba routerów jaką
należy przejść, żeby dostać się do danej
sieci



Po 180s nie odświeżona droga jest usuwana
z tablicy routingu

www.cs.agh.edu.pl

Pakiet RIP — enkapsulacja

Pakiet RIP

Nagłówek IP

Pole danych

Nagłówek UDP Pole danych

Port 520

To Send/Rcv

Pakiet RIP

musi być wypełnione zerami

metryka

musi być wypełnione zerami

musi być wypełnione zerami

adres IP

identyfikator rodziny adresów

musi być wypełnione zerami

wersja

polecenie

(zapytanie/odpowiedź)

28
31

24

20

16

12

8

4

0

N

Wady RIP — liczenie do
nieskończoności

Sieć 1

R1

R2

R3



Router R2 wysyła informacje o
dostępności sieci 1 co 30 sekund



Po 180 sekundach R1 wpisuje do swojej
tablicy nową drogę do sieci 1

N

H

Sieć 1 2

N

H

Sieć 1 3

N

H

Sieć 1 4

N

H

Sieć 1 5

N

H

Sieć 1 6

N

H

Sieć 1 7

N

H

Sieć 1 8

N

H

Sieć 1 9

N

H

Sieć 1 10

N

H

Sieć 1 11

N

H

Sieć 1 12

N

H

Sieć 1 13

N

H

Sieć 1 14

R0

N

H

Sieć 1 15

N

H

Sieć 1 16

RIP — zmniejszanie prawdopodobieństwa
wystąpienia liczenia do nieskończoności



Uaktualnianie z podzielonym horyzontem

◦

router nie propaguje informacji o dostępności sieci na
interfejs, przez który prowadzi najlepsza trasa



Wstrzymanie

◦

router wstrzymuje się z akceptacją komunikatów o
dostępności sieci, o której awarii otrzymał informację
(zazwyczaj na 60 sek.)



Odświeżanie wymuszone

◦

w wypadku zmiany w tablicy router nie czeka 30s tylko
rozgłasza nową informację natychmiast

RIP — dzielony horyzont



Zmniejsza prawdopodobieństwo
wystąpienia zjawiska zliczania do
nieskończoności

Sieć 1

R1

R2

R3

N

H

Sieć 1 3

N

H

Sieć 1 3

Najkrótsza trasa do

1

jest dostępna przez

R1

R0

R2 nie wysyła informacji o dostępności
Sieci 1 do R1 bo przez ten router
prowadzi najkrótsza trasa tej sieci

RIP — wstrzymanie



Po otrzymaniu komunikatu od routera, że
poprzednio dostępna sieć jest niedostępna
włącza licznik (hold-down timer)



Jeśli otrzyma komunikat od tego samego
routera, że sieć jest dostępna wyłącza
licznik



Jeśli otrzyma komunikat od innego routera
ogłaszający lepszą trasę wyłącza licznik



Jeśli otrzyma gorsze trasy

ignoruje je



Po upłynięciu licznika kasuje wpis

RIP — odświeżanie
wymuszone



Pakiet RIP wysyłany jest natychmiast po
zaobserwowaniu zmiany

◦

czas zwykle jest opóźniony o kilka sekund, żeby
nie spowodować zalewania sieci



Nie wysyłana jest cała tablica routingu a
tylko informacja o zmianach

RIP i podsieci

10.1.0.0/24

10.2.0.0/24

10.3.0.0/24



Potrafi przekazywać informacje
jedynie o sieciach i
pojedynczych komputerach

◦

W polu hosta są same zera —
sieć

◦

W przeciwnym przypadku — host



Potrafi obsłużyć sytuację, w
której istnieją jednakowo długie
podsieci — na podstawie
adresów swoich interfejsów.

◦

Wszystkie routery zakładają, że
w sieci istnieje jedna długość
maski

Wady RIP — synchronizacja



Co 30 sekund w sieci opartej na protokole RIP
następuje znaczny spadek wydajności
(synchronizacja komunikatów o tablicach
routingu)

◦

mniejsza przepustowość lub większy procent
zagubionych pakietów



Rozwiązania:

◦

inicjowanie routerów w różnych momentach

◦

modyfikacja interwału (15s – 45s; średnio 30s) pomiędzy
wysyłaniem kolejnych informacji o zawartości tablicy
routingu (losowo)

Wady RIP — rozgłaszanie



W przypadku Ethernetu lub FDDI —
naturalna metoda przesyłania informacji
dotyczących routingu



W ISDN lub X.25 „milczenie jest złotem”

◦

Transmisja wymaga zestawienia kanału
transmisyjnego

◦

ISDN „B” — 64 kbps

◦

kanał wirtualny X.25 — 9,6 kbps



przesłanie 2 pakietów RIP zajmuje około 1 sekundy
(!)

Wady RIP — rozgłaszanie



Remedium: tablice routingu rozgłaszane są
tylko wtedy, gdy zachodzi taka konieczność

◦

transmisja z potwierdzeniem

◦

problem:



jak stwierdzić, że połączenie z sąsiednim routerem
działa?



założenie osiągalności



jeśli próba przesłania pakietu zawiedzie to przerwane



„zapominanie” informacji o gorszych drogach



po 30 sekundach się nie pojawią (!!!)



rozwiązanie: przechowywanie listy tras wewnątrz routera



stosowane nie tylko w przypadku łącz typu X.25

Wady RIP



Zbyt prosta metryka

◦

łącze X.25 i FDDI „tyle samo warte”



X.25 drogie i wolne



FDDI tanie i szybkie

Sieć 1

Sieć 2

A

C

B

X.25

(9600 bps)

100000000 bps

100000000 bps

• Dobry do sieci jednorodnych

www.cs.agh.edu.pl

RIP i podsieci

R1

10.1.0.0/24

10.2.0.0/24

20.0.0.0/8



R1 nie może przekazać
informacji o podsieci, bo na
tym interfejsie nie ma
podsieci — inne routery
zinterpretowały by jego
komunikat jako drogę do
hosta 10.1.0.0



R2 może nie znać
poprawnej drogi do hosta
10.1.1.1

10.0.0.0

R2

10.1.1.1

10.0.0.0

R3

10.3.0.0/24

RIP-2



W ramce zawarta jest również maska
podsieci



Propaguje numer domeny routingu



Propaguje adres następnego routera (next-
hop)

www.cs.agh.edu.pl

Pakiet RIP-2

znacznik trasy

metryka

next hop

maska podsieci

adres IP

identyfikator rodziny adresów

numer domeny routingu

wersja

polecenie

(zapytanie/odpowiedź)

28
31

24

20

16

12

8

4

0

N

RIP-2 — przykład

A

B

C

D

E

F



Na podstawie numeru domeny routingu wiadomo które pakiety odbierać



W protokole RIP w drodze od A do F przez D pakiet dwa razy przesyłany jest

przez ten sam Ethernet



W RIP-2 router D może rozgłosić w domenie X adres E jako „next-hop” w drodze

do F

Wybrany do
komunikacji ze
światem
zewnętrznym

System autonomiczny

„X”

System autonomiczny

„Y”

RIP-2 — bezpieczeństwo



Wada RIP-1

◦

w RIP-1 każdy komputer nadający z portu 520 jest
uznawany za router

◦

konieczna ręczna konfiguracja routingu: lista
autoryzowanych sąsiadów



Mechanizm autentykacji RIP-2

◦

w ramce RIP-2 można umieścić pole zawierające
„hasło” (rodzina adresów ‘FFFF’)

◦

nie powoduje to utraty kompatybilności
z RIP-1

www.cs.agh.edu.pl

RIP-2 — rozgłaszanie



Wada RIP-1

◦

używa broadcastowego adresu MAC do rozsyłania
informacji o dostępności do sieci



RIP-2 używa do tego celu multicastowego
adresu IP klasy D (224.0.0.9)

◦

nie są konieczne mechanizmy rutowania pakietów
klasy D, bo informacje dotyczą tylko lokalnej sieci

RIP-2 — podsumowanie



Oferuje znaczące rozszerzenia względem
RIP-1

◦

routing bazujący na CIDR i podsieciach

◦

autoryzacja pakietów

◦

kompatybilność z RIP-1



Nie eliminuje wszystkich wad RIP-1

◦

np. konieczność liczenia do nieskończoności w
razie awarii sieci

◦

bardzo prosta metryka



Centralne zarządzanie siecią komputerową o

globalnym rozmiarze jest technicznie niemożliwe, a

ponadto niewskazane. Dlatego na najwyższym

poziomie sieć Internet podzielona jest na niezależnie

zarządzane, numerowane obszary, z których każdy

obejmuje wiele sieci IP. Obszary te nazywa się

systemami autonomicznymi (ang. Autonomous

System, w skrócie AS).

BGP

System autonomiczny AS w Internecie to sieć lub grupa sieci pod wspólną

administracyjną kontrolą i posiadająca wspólną strategię trasowania. Systemy

autonomiczne czasem nazywane są segmentami. Operatorzy Internetu i

korporacje posiadają zwykle swoje systemy autonomiczne. Propagacja

informacji o trasach odbywa się na dwa sposoby. Wewnątrz pojedynczego

systemu autonomicznego jego trasy ogłasza protokół typu wewnętrznego, IGP

(ang. Interior Gateway Protocol), na przykład RIP czy OSPF, zaś wymianą

informacji o trasach pomiędzy systemami autonomicznymi zajmuje się

protokół typu zewnętrznego, EGP (ang. Exterior Gateway Protocol).

SYSTEM AUTONOMICZNY
(AS)

Zakres stosowania protokołów
IGP i EGP

Koncepcja działania protokołu
BGP

przykłady BGP między trzema
odrębnymi sieciami



BGP działa w warstwie transportowej modelu OSI/ISO.



Do komunikacji używany jest protokół TCP oraz port 179.



Dzięki TCP protokół rutowania nie musi się martwić o utrzymywanie
połączenia i sprawdzanie poprawności danych



Niektóre z protokołów, takie jak EIGRP, wykorzystują własne protokoły
stworzone specjalnie do komunikacji, w tym przypadku RTP, niektóre
nie robią tego w ogóle, jak RIP czy IGRP, i korzystają z protokołów
bezpołączeniowych jak UDP.



Powyżej warstwy transportowej BGP używa własnych mechanizmów
do zestawiania sesji i wymiany danych.



BGP tworzy trwałe połączenia pomiędzy ruterami komunikującymi się
bezpośrednio.



Używanych jest kilka typów komunikatów do komunikowania się
ruterów: OPEN, UPDATE, KEEPALIVE, NOTIFICATION. Potrzebne są one
do zestawienia sesji, informowania rutera sąsiada o zmianach i
podtrzymywania oraz zamykania sesji.

BGP W SIECI TCP/IP



Rozwiązanie OpenSource pozwalających na stosowanie protokołów
dynamicznego routingu w Linuxie. Jest to oprogramowanie bazujące na kodzie
projektu Zebra (http://www.zebra.org/).



Co jest ciekawe i wygodne dla ludzi znających interfejs Cisco to to, że autor
Zebry, a obecnie także główny deweloper Quaggi, starali się go naśladować.
Osoba, która używała interfejsu Cisco nie będzie miała kłopotu z
konfigurowaniem Quaggi.



Quagga działa jako zespół demonów komunikujących się wzajemnie ze sobą.
Zebra odpowiada za komunikację z systemową tablicą routingu i komunikację
z pozostałymi daemonami bgpd, ripd, ripngd, ospfd, ospf6d. Te obsługują
poszczególne protokoły i komunikują się jedynie z zebrą lub innymi routerami.



Do poszczególnych demonów można się dostać poprzez telnet na port 2601 w
przypadku zebry i 2605 w przypadku bgpd. Warto skorzystać z udogodnienia,
jakim jest vtysh, pozwalający na komunikację z wszystkimi działającymi
demonami podczas jednego połączenia.

QUAGGA

Schemat architektury
Quaggi

Przykładowa konfiguracja

Quagga stanowi
w pełni
funkcjonalny
odpowiednik
routera, który
może być
wykorzystywany
na styku
pomiędzy
operatorami
wykorzystującymi
BGP



Protokół IGMP służy do wymiany informacji o
stanie członkostwa między routerami IP
obsługującymi multiemisję i członkami grup
multiemisji. Z poszczególnych hostów
wysyłane są powiadomienia o
przynależności do grupy multiemisji, a
routery multiemisji okresowo sondują stan
członkostwa.

IGMP

Typy komunikatów IGMP.

Komunikaty IGMP są hermetyzowane i wysyłane

w datagramach IP

Wysyłanie komunikatów IGMP

OSPF jest protokołem otwartym, co oznacza,

że jego specyfikacja jest ogólnie dostępna.

Protokół OSPF jest protokołem

routingującym klasy link-state,

wykorzystującym algorytm SPF

Protokół OSPF

Format
pakietu
protokołu
OSPF



W odróżnieniu od protokołu RIP protokół OSPF może działać
w układzie hierarchicznym. Największą jednostką w hierarchii
jest system autonomiczny AS (Autonomous System), który
jest zbiorem sieci pod wspólną administracją, a które mają
wspólną strategię routingu. OSPF jest protokołem routingu
wewnętrznego systemów AS (wewnętrzna brama), może
jednak przyjmować i wysyłać trasy do innych systemów AS.



System AS można podzielić na pewną liczbę obszarów
(areas), które są grupami sąsiednich sieci i przyłączonych
hostów. Poszczególne obszary sprzęgają routery graniczne
obszaru (area border routers). Router graniczny utrzymuje
oddzielną dla każdego obszaru bazę danych o topologii
(topological database).

OSPF



W zależności od rodzaju ruchu protokół PIM pracuje w dwu
trybach, dense (skupionym) i sparse (rzadkim).



Tryb dense używa algorytmu RPF (Reverse Path Flooding), który
jest podobny do protokołu DVMRP. Istnieją jednak różnice, na
przykład protokół PIM pracujący w trybie dense, w odróżnieniu
od protokołu DVMRP, nie wymaga specjalnego protokołu
unicast, może pracować z dowolnym protokołem tego typu
używanym w sieci.



Tryb sparse jest przeznaczony dla intersieci ze stosunkowo
niewielką liczbą sieci LAN, ale wieloma strumieniami danych.
Definiuje punkty spotkań, które później są używane jako punkty
rejestracji w celu zapewnienia właściwego routingu pakietów.

Protokół PIM



MME (Mesh Made Easy) to protokół routingu
MikroTik używany na poziomie routingu IP w
sieciach bezprzewodowych



MME nie jest w stanie obliczyć tablicy
routingu, zamiast tego sprawdza ile
pakietów zostało utracone przy przesyłaniu
daną drogą i na tej podstawie wybiera
najlepszą drogę dla pakietu.

MME bezprzewodowy protokół
routingu

Dziękuję