materiały

Report
Technologie sieciowe 2 (TS2)
Wykład 3: Trasowanie
a efektywność wykorzystania
zasobów sieci
dr inż. Andrzej Szwabe
Instytut Automatyki i Inżynierii Informatycznej,
Wydział Elektryczny Politechniki Poznańskiej
e-mail: [email protected]
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
1
Plan wykładu
• Podstawy rutingu (trasowania)
–
–
–
–
–
Ruting a przekazywanie pakietów IP (IP forwarding)
Classless Interdomain Routing (CIDR)
Systemy autonomiczne w rutingu
Routery wewnętrzne i zewnętrzne oraz ich najważniejsze protokoły
Identyfikatory ruterów, numerowane i nienumerowane połączenia
• Dystrybucja informacji o trasach w sieci
– Ruting wg wektorów odległości (distance vectors)
– Ruting wg stanu połączeń (link state routing)
– Wektory ścieżek i polityki
• Algorytmy wyznaczania ścieżek:
– Open Shortest Path First (OSPF),
– Constrained Shortest Path First (CSPF),
– Equal Cost Multipath (ECMP)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
2
Podstawy rutingu (trasowania)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
3
Ruting a przekazywanie pakietów IP
(IP forwarding)
• Routery dokonują wyboru trasy na podstawie informacji zapisanej w
tablicy tras.
• Router działa na podstawie aktualizowanej zawartości tablicy tras – w
ogólności trasy się zmieniają w czasie -> poza hostami końcowymi
konieczne jest trasowanie dynamiczne.
• Trasowanie (ruting) dynamiczne jest złożeniem funkcji:
– Pozyskiwania od innych ruterów rozproszonych danych o dostępnych
trasach przekazywania pakietów („wejście danych sterujących”)
– Lokalnego wyznaczania przez rutery dostępnych tras przekazywania
pakietów („przetwarzanie danych sterujących -> podejmowanie decyzji”)
na podstawie danych o rutingu (RIB)
– Lokalnego przekazywania pakietów pomiędzy posieciami („wykonanie
pracy”) na podstawie danych o przekazywaniu pakietów (FIB)
– Udostępniania innym ruterom danych o dostępnych trasach
przekazywania pakietów („wyjście danych sterujących”)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
4
Dane o rutingu (RIB) a dane o
przekazywaniu pakietów (FIB)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
5
Bezklasowe trasowanie
międzydomenowe (CIDR)
• Classless Interdomain Routing
– Środek zaradczy wobec rosnącej liczby wpisów w tablicach trasowania
dla rutingu bazującego na klasach adresów IP
– Agregacja tras umożliwia dalszą redukcję liczby wpisów w tablicach
trasowania dzięki reprezentowaniu wielu podsieci przez pojedynczy wpis.
• W przykładzie podsieci 176.19.168.16/28 176.19.168.32/28 mogą być dla
potrzeb trasowania reprezentowane jako pojedyncza podsieć
176.19.168.32/27.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
6
Systemy autonomiczne w rutingu
• System autonomiczny – wyodrębniona grupa integralnie
zarządzanych sieci i routerów.
• Routery wewnątrz systemu autonomicznego zarządzają trasami w
sposób niewidoczny dla hostów spoza systemu autonomicznego
– Rutery działające wewnątrz systemu to tzw. bramki wewnętrzne (interior
gateways).
• W obrębie systemu autonomicznego funkcjonują rutery przeznaczone
do komunikacji z innymi systemami autonomicznymi
– Routery odpowiedzialne za komunikację z innymi systemami
autonomicznymi to tzw. bramki zewnętrzne albo brzegowe (exterior
gateways) - odpowiadają one za przekazywanie do innych systemów
informacji o osiągalności sieci wewnątrz „swojego” systemu.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
7
Systemy autonomiczne w rutingu
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
8
Routery wewnętrzne i zewnętrzne
oraz ich najważniejsze protokoły
•
Do protokołów używanych do komunikacji między routerami zewnętrznymi
należą BGP (Border Gateway Protocol) i EGP (Exterior Gateway Protocol)
– Ruter zewnętrzny komunikuje się z sąsiednim routerem zewnętrznym, „ustalając”
wzajemne sąsiedztwo i wymieniając informacje o ścieżkach łączących sieci.
– Ruter cyklicznie weryfikuje działanie sąsiednich ruterów.
– Sąsiednie rutery wymieniają komunikaty umożliwiające aktualizację tablice rutingu
- komunikat zawiera listę znanych danemu routerowi sieci (łączących rutery
wewnętrzne) i odległości do nich.
•
Do protokołów używanych do komunikacji między routerami wewnętrznymi
należą RIP i OSPF
– Najpowszechniej stosowanym porotokołem rutingu wg wektorów odległości
(distance vectors routing protocol) jest RIP (Routing Information Protocol)
– Najpowszechniej stosowanym porotokołem rutingu wg stanu połączeń (link state
routing protocol) jest OSPF (Open SPF Protocol, nie mylić protokołu z algorytmem
Open Shortest Path First!)
– W sieciach typu wireless multihop stsosuje się podobny do OSPF protokół OLSR
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
9
Identyfikatory ruterów i połączeń
•
Przykład prostej sieci z połączeniem wielodostępowym (multi-access link),
numerowanym połączeniem dwudostępowym (numbered point-to-point
link) i połączeniem nienumerowanym.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
10
Dystrybucja informacji o trasach
w sieci
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
11
Ruting według wektorów odległości
(distance vector routing)
•
Algorytm trasowania według wektorów odległości
–
–
–
–
–
Router przechowuje w tablicy wszystkie znane mu routery.
Router przy starcie tworzy tablicę sieci bezpośrednio dostępnych.
Każdy wpis w tablicy zawiera informację o odległości do danej sieci.
Co jakiś czas router wysyła tablicę tras do wszystkich bezpośrednio dostępnych routerów,
a one aktualizują swoje tablice tras zgodnie z uzyskaną informacją.
Podstawowa zasada działania trasowania z użyciem protokołu RIP
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
12
Ruting według wektorów odległości
•
Ograniczona szybkość propagacji danych o trasach
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
13
Ruting według wektorów odległości
•
Ograniczona szybkość propagacji danych o trasach
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
14
Problem „liczenia w nieskończoność”
•
Nawet w przypadku niewielkiej sieci trasowanie według wektorów
odległości może teoretycznie prowadzić do wystąpienia zjawiska „liczenia
w nieskończoność”.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
15
Prosty środek zaradczy wobec
„liczenia w nieskończoność”
•
Zastosowanie w sieci z trasowaniem według wektorów odległości progu
dopuszczalnej odległości wpisu jest prostym środkiem zaradczym wobec
problemu „liczenia w nieskończoność”.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
16
Ruting według stanów połączeń
(link state routing)
•
•
Podstawowa zasada: trasy wyznaczane przez węzły niezależnie od siebie (w
sposób rozproszony) na podstawie współdzielonych danych o połączeniach, a nie
trasach.
Podstawowe funkcje trasowania według stanów połączeń:
–
–
„Odkrywanie” (discovery) sąsiednich (w sensie warstwy drugiej) ruterów
Rozgłaszanie informacji o połączeniach (Link State Advertisement, LSA) na zasadzie
„powodzi” (link state flooding)
•
•
–
–
Selektywne odświeżanie lokalnych baz danych o stanie połączeń
Wykrywanie przerwanych połączeń
•
•
•
•
„Starzenie się” wpisów w lokalnej bazie rutera
Cykliczne ponawianie („odświeżanie”) LSA
Sprzętowe, na poziomie warstwy fizycznej
Na poziomie warstwy łącza danych
Na poziomie warstwy sieciowej (niepowodzenie komunikacji z użyciem protokołu Hello)
Algorytmy wyznaczania ścieżek w sieciach z trasowaniem według stanów połączeń:
–
–
–
Open Shortest Path First (OSPF) – algorytm Dijsktry wyznaczania najkrótszej trasy
Constrained Shortest Path First (CSPF) – dodatkowe parametry połączeń jako podstawę
wykluczenia ich w procesie wyznaczania najkrótszej trasy
Equal Cost Multipath (ECMP) – umożliwia równoległe stosowanie wielu alternatywnych
tras o równym koszcie (długości liczonej w węzłach pośredniczących)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
17
Ruting według stanów połączeń
• Podstawowe funkcje
trasowania według
stanów połączeń:
– „Odkrywanie”
(discovery)
sąsiednich (w sensie
warstwy drugiej)
ruterów
– Rozgłaszanie
informacji o
połączeniach i
odświeżanie
lokalnych baz danych
o stanie połączeń
– Informowanie węzłów
sąsiednich o
przerwaniu
połączenia
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
18
Obszary w sieci z trasowaniem
według stanów połączeń
•
Problem złożoności obliczeniowej algorytmów wyznaczania tras według stanów
połączeń
–
–
•
Duża liczba wpisów w bazach danych o połączeniach może ograniczać szybkość działania
algorytmu.
Złożoność obliczeniową algorytmu można przybliżyć funkcją liczby połączeń n jako większą
od n*log(n), ale mniejszą od n^2.
Technika sprzyjająca skalowalności algorytmów wyznaczania tras według stanów
połączeń – obszary sieci (areas) połączone ruterami ABR- jako jedynymi znającymi
połączenia wewnątrz obszarów (niekiedy będącymi bramami zewnętrznymi).
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
19
Trasowanie według wektorów
ścieżek (path vector routing)
•
•
•
Trasowanie według wektorów ścieżek zakłada przekazywanie w komunikatach o trasach danych o
całych ścieżkach, co m.in. umożliwia łatwą identyfikację pętli i zapobiega problemowi liczenia do
nieskończoności.
Wadą jest znacznie większy niż w przypadku rutingu według wektorów odległości rozmiar
komunikatach o trasach.
Zaletą jest umożliwienie dokonywania przez ruter wyboru trasy nie tylko w oparciu o dane o
dystansie lub koszcie trasy, ale z uwzględnieniem również innych atrybutów ruterów i połączeń
tworzących ścieżki
–
–
–
Możliwe jest podejmowanie decyzji o wyborze tras zgodnie z lokalnymi regułami, tzw. politykami (policies).
Możliwe jest uwzględnienie informacji o tym, że np. pewne połączenia są bardziej zawodne, mniej bezpieczne
lub droższe.
Stosowanie zbyt uproszczonych polityk, niedopasowanych do polityk stosowanych w innych ruterach może
doprowadzić do powstawania pętli.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
20
Trasowanie według wektorów
ścieżek (path vector routing)
•
Jedna z podstawowych zasad trasowania według wektorów ścieżek: redukcja ilości
danych rutingowych dystrybuowanych w sieci dzięki mechanizmowi „streszczania
tras” (route summarization) – trasy są rozgłaszane jako sekwencje ścieżek.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
21
Trasowanie według wektorów
ścieżek (path vector routing)
•
Druga podstawowa zasad trasowania według wektorów ścieżek: agregacja tras
dzięki funkcji grupowania ścieżek w grupy (path sets).
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
22
Współdziałanie protokołów o różnych
metodach trasowania
• Niezależność technologiczna systemów autonomicznych
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
23
Współdziałanie protokołów
o różnych metodach trasowania
•
Rola ruterów ASBR (Autonomous System Border Router) – ruterów realizujących
zarówno funkcje protokołów IGP jak i EGP.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
24
Porównanie najważniejszych metod
trasowania
•
...
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
25
Algorytmy wyznaczania ścieżek:
OSPF, CSPF, ECMP
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
26
Algorytm wyznaczania ścieżek Open
Shortest Path First
•
•
•
s - wierzchołek źródłowy, w(i,j) - waga krawędzi (i,j) w grafie
d - tablica odległości od źródła dla wszystkich wierzchołków grafu
Algorytm Dijkstry - znajdowanie najkrótszej ścieżki z pojedynczego źródła
w grafie o nieujemnych wagach krawędzi:
Dijkstra(G,w,s):
dla każdego wierzchołka v w V[G] wykonaj
d[v] := nieskończoność
poprzednik[v] := niezdefiniowane
d[s] := 0
Q := V
dopóki Q niepuste wykonaj
u := Zdejmij_Min(Q)
dla każdego wierzchołka v – sąsiada u wykonaj
jeżeli d[v] > d[u] + w(u, v) to
d[v] := d[u] + w(u, v)
poprzednik[v] := u
•
Złożoność algorytmu Dijkstry:
, N – liczba węzłów, l – liczba połączeń
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
27
Algorytm Dijkstry (1)
•
•
Algorytm ma na celu odnalezienie najkrótszej drogi (w sensie sumy
kosztów trasy) z a do każdego z pozostałych węzłów.
Wartości kosztu połączeń niekoniecznie są symetryczne.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
28
Algorytm Dijkstry (2)
•
•
Czerwone strzałki wskazują drogę do węzłów osiągalnych z jedynego węzła o już
ustalonej finalnie odległości (startowego, zaznaczonego na niebiesko).
Odległość do d jest najmniejszą możliwą ponieważ każda inna trasa przez węzły
zaznaczone na czerwono („w trakcie sprawdzania”) będzie większa -> wezeł d
uznaje się za „ostatecznie sprawdzony” i zaznacza kolorem pomarańczowym.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
29
Algorytm Dijkstry (3)
•
•
•
Czerwone strzałki wskazują drogę do węzłów osiągalnych z węzłów o już ustalonej finalnie odległości
(pomarańczowych).
Spośród węzłów o tymczasowo określonej odległości (b=4, e=33, g=23) tym o najmniejszej odległości jest
węzeł b (b=4) – każda inna ścieżka do węzła b niż ta odpowiadająca odległości 4 musi prowadzić przez jeden z
pozostałych węzłów o tymczasowo określonej odległości, a więc jest dłuższa niż 4.
Węzeł b zostanie zaznaczony na pomarańczowo jako węzeł o już ustalonej finalnie odległości (odległość od a
do b zostaje uznana za równą 4)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
30
Algorytm Dijkstry (4)
•
•
•
Odległości wynoszą aktualnie: c=6, e=16, g=23.
Uwaga: tymczasowa „estymata” odległości od węzła a do węzła e uległa
zmianie.
Węzeł c ma najmniejszą odległość od węzła a, a więc wartość 6 uznaje się
za ostatecznie wyznaczoną odległość od węzła a do węzła c.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
31
Algorytm Dijkstry (5)
•
•
•
Odległości wynoszą aktualnie: e=16, f=80, g=23, j=18.
Węzeł e ma najmniejszą odległość od węzła a i nie jest wskazywany przez żadną
inną czerwoną strzałkę.
Wartość 16 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła e.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
32
Algorytm Dijkstry (6)
•
•
•
Odległości wynoszą aktualnie: f=80, g=23, h=49, j=18.
Węzeł j ma najmniejszą odległość od węzła a - każda inna ścieżka do węzła j niż ta
odpowiadająca odległości 18 musi prowadzić przez jeden z pozostałych węzłów o
tymczasowo określonej odległości, a więc jest dłuższa niż 18.
Wartość 18 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła j.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
33
Algorytm Dijkstry (7)
•
•
•
•
Odległości wynoszą aktualnie: f=26, g=23, h=49.
Uwaga: tymczasowa „estymata” odległości od węzła a do węzła f uległa zmianie.
Węzeł g ma najmniejszą odległość od węzła a - każda inna ścieżka do węzła g niż ta
odpowiadająca odległości 23 musi prowadzić przez jeden z pozostałych węzłów o tymczasowo
określonej odległości, a więc jest dłuższa niż 23.
Wartość 23 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła g.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
34
Algorytm Dijkstry (8)
•
•
•
Odległości wynoszą aktualnie: f=26, h=49.
Węzeł f ma najmniejszą odległość od węzła a - każda inna ścieżka do węzła f niż ta
odpowiadająca odległości 26 musi prowadzić przez jeden z pozostałych węzłów o
tymczasowo określonej odległości, a więc jest dłuższa niż 26.
Wartość 26 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła f.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
35
Algorytm Dijkstry (9)
•
•
•
Odległości wynoszą aktualnie: h=33, i=37.
Węzeł h ma najmniejszą odległość od węzła a - każda inna ścieżka do węzła g niż ta
odpowiadająca odległości 33 musi prowadzić przez jeden z pozostałych węzłów o tymczasowo
określonej odległości, a więc jest dłuższa niż 33.
Wartość 33 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła h.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
36
Algorytm Dijkstry (10)
•
•
•
Odległość węzła i od węzła a równa jest 37.
Węzeł i nie jest wskazywany przez żadną alternatywną czerwoną strzałkę.
Wartość 37 uznaje się za ostatecznie wyznaczoną odległość od węzła a do węzła i.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
37
Algorytm Dijkstry (11)
•
Algorytm zakończył działanie – pomarańczowe strzałki wskazują trasy o
najmniejszych odległościach od węzła a, a wartości odległości podane są jako
liczby opisujące węzły.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
38
Algorytmy wyznaczania ścieżek
CSPF i ECMP
• Constrained Shortest Path First (CSPF) – dodatkowe parametry
połączeń jako podstawę wykluczenia ich w procesie wyznaczania
najkrótszej trasy
• Equal Cost Multipath (ECMP) – umożliwia równoległe stosowanie
wielu alternatywnych tras o równym koszcie (długości liczonej w
węzłach pośredniczących)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
39
Wybrane pozycje literaturowe
•
•
•
•
•
•
•
The Internet And Its Protocols, A Comparative Approach,
Adrain Farrel, Morgan Kaufmann, Elsevier, San Francisco, 2004
Sieci komputerowe i intersieci, D. E. Comer, WNT, Warszawa 2001
Computer Networks, A. Tanenbaum, Prentice-Hall, 1996
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
A. Szwabe, DANUMS: The First Delay-Aware Utility Maximization System for Wireless
Networks, In Procs. of 2009 NEM Summit, September 2009, Saint-Malo, France, ss.
59-64
A. Szwabe, P. Misiorek, Integration of multi-path Optimized Link State Protocol with
Max-Weight Scheduling, In Proc. of 2009 International Conference on Information and
Multimedia Technology (ICIMT 2009), Jeju Island, South Korea, December 2009, ss.
458-462.
Zalecane samodzielne wyszukiwanie informacji w specyfikacjach (np. RFC) i
publikacjach naukowych dostępnych w Internecie (potencjalny temat konsultacji)
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
40
Dziękuję za uwagę.
Proszę o pytania.
Andrzej Szwabe, Instytut Automatyki i Inżynierii Informatycznej, Wydział Elektryczny Politechniki Poznańskiej
Technologie sieciowe 2 (TS2) – Wykład 3: Trasowanie a efektywność wykorzystania zasobów sieci
41

similar documents