Sieci komputerowe

7

INTERSIECI - ROUTING

7.Intersieci – routing76

SieciKom 2014 – 7. Intersieci -

routing

2

•

7.1Przełącznik pakietów w sieci WAN76

•

7.2Routing76

•

7.2.1Zasada zapisz i przekaż76

•

7.2.2Adresacja77

•

7.2.3Następny skok77

•

7.2.4Grafowy model routingu79

•

7.2.5Rozproszone mechanizmy routingu80

•

7.2.6Routing na bazie informacji o stanie łączy80

•

7.2.7Routing z wykorzystaniem wektorów odległości

•

7.2.8Interpretacja odległości w grafie i najkrótszej
trasy

7. Przełącznik pakietów w sieci WAN

• Podstawą działania sieci jest

transmisja  zasady routingu.

• Pierwotnie budowano sieci

z komputerów indywidualnych
i przełączników pakietów (transmisja
bitowa), a obecnie z sieci lokalnych i
(rzadko) indywidualnych
komputerów + transmisja pakietowa

SieciKom 2014 – 7. Intersieci -

routing

3

Rys. 7.1   Tradycyjny przełącznik

SieciKom 2014 – 7. Intersieci -

routing

4

• Współcześnie korzysta się

z przełączników warstwy 2 (obsługa
komputerów w sieciach lokalnych)
oraz routerów (obsługa pakietów
w sieciach rozległych)

SieciKom 2014 – 7. Intersieci -

routing

5

Rys. 7.2   Połączenie sieci LAN z siecią WAN za
pośrednictwem routera

SieciKom 2014 – 7. Intersieci -

routing

6

7.2 Routing

Rys. 7.3   Przykład sieci WAN zbudowanej z przełączników pakietów

SieciKom 2014 – 7. Intersieci -

routing

7

• Przykładowa sieć (Rys. 7.3) oparta

o cztery przełączniki pakietów i
osiem komputerów

– Dobór połączeń zależy od natężenia

ruchu

– Niektóre łącza mogą być

zwielokrotnione – zapasowe

SieciKom 2014 – 7. Intersieci -

routing

8

7.2.1 Zasada zapisz i przekaż

•

Sieci WAN wymagają równoczesnego
przekazywania jak największej liczby pakietów –
uzyskuje się to poprzez zastosowanie zasady
zapisz i przekaż (store and forward), co
wymaga:

– buforowania w przełączniku
– operacji zapisu w momencie odebrania pakietu
– operacji przekazania rozpoczynającej się

w momencie zapisu pakietu w buforze 

• procesor przełącznika analizuje pakiet,
• ustala sieć docelową
• wysyła interfejsem prowadzącym do miejsca docelowego

SieciKom 2014 – 7. Intersieci -

routing

9

• Mechanizm zapisz i przekaż wymaga

utrzymania wszystkich łączy w stanie
gotowości, co powoduje

– zwiększa to wydajność sieci
– nie wymaga wstrzymywania strumieni

wejściowych przychodzących do
przełącznika, gdyż on zapisze je w
buforze i będą one oczekiwały na
gotowość urządzenia odbiorczego 
Rys. 7.3

SieciKom 2014 – 7. Intersieci -

routing

10

7.2.2 Adresacja

13.5.2014

• Każdemu komputerowi w sieci WAN

przypisany jest adres

• Nadawca ramki musi ten adres

uwzględnić w treści ramki

• Stosuje się adresowanie

hierarchiczne:

{ośrodek/sieć/podsieć, komputer

w sieci}

co odpowiada

{przełącznik, komputer}

SieciKom 2014 – 7. Intersieci -

routing

11

Rys. 7.4   Przykład hierarchii adresów

SieciKom 2014 – 7. Intersieci -

routing

12

7.2.3 Następny skok

• Po otrzymaniu pakietu przełącznik wyznacza interfejs

wyjściowy, do którego będzie przekazany pakiet

• Jeżeli adresowany będzie komputer we „własnej” sieci

LAN podłączonej do przełącznika, to pakiet powędruje
bezpośrednio do niego

• Jeżeli nie, to przełącznik musi przekazać go do

wskazanego przełącznika za pośrednictwem jednego
z dostępnych łączy wyjściowych;

• W tym celu przełącznik analizuje adres docelowy

pakietu i wydziela z niego identyfikator przełącznika,
czyli jeżeli identyfikatory przełączników są zgodne, to
pakiet jest przeznaczony do komputera w dołączonej
sieci LAN

SieciKom 2014 – 7. Intersieci -

routing

13

SieciKom 2014 – 7. Intersieci -

routing

14

Zalety

1. Przełącznik nie musi przechowywać informacji

o dostępności wszystkich komputerów,

2. Przełącznik nie wyznacza całej trasy wędrówki pakietu,
3. Przełącznik jedynie odczytuje identyfikator przełącznika

i odszukuje łącza do tego przełącznika  przełącznik
określa jedynie następny skok (next hop) – analog do
zestawiania połączeń komunikacyjnych z przesiadkami

4. Dla przyspieszenia wyszukiwania następnego skoku

przełączniki dysponują uprzednio przygotowanymi
tablicami przekazywania (forwarding table), które
można interpretować jako tabele indeksowane
przełącznikami (Rys. 7.5)

SieciKom 2014 – 7. Intersieci -

routing

15

Rys. 7.5   Sieć i tabela przekazywania pakietów
przełącznika 2 - przekazanie z komputera {1,2} do
komputera {3,5}

SieciKom 2014 – 7. Intersieci -

routing

16

5. Przełącznik przetwarza jedynie część adresu 

krótszy czas przetwarzania + posługuje się
indeksowanymi tabelami, których nie musi
przeszukiwać + tabela przekazywania nie zawiera
numerów (adresów) konkretnych komputerów

6. Gdy pakiet dotrze do końcowego przełącznika, to

druga część adresu wskaże konkretny/docelowy
komputer (w końcowej sieci LAN)

7. Przełącznik nie potrzebuje znać adresu

początkowego/źródłowego przekazywanego
pakietu.

SieciKom 2014 – 7. Intersieci -

routing

17

7.2.4 Grafowy model routingu

• Poprawna praca sieci WAN wymaga dla każdego

przełącznika aktualnych tablic przełączania
pakietów, które mogą ulegać zmianie
w konsekwencji awarii łączy

• Tablice powinny zawierać 1)poprawne dane

o następnym skoku i 2)zestawiać najkrótsze trasy
do węzła docelowego

• Wykryte awarie łączy powinny uruchamiać

automatyczny wybór zastępczego łącza/trasy 
w węźle powinno być oprogramowanie
odpowiedzialne za automatyczną rekonfigurację
sieci ≡ oprogramowanie routingu

SieciKom 2014 – 7. Intersieci -

routing

18

• Grafowy opis sieci uwzględnia

jedynie przełączniki (komputery nie
są reprezentowane w grafie)

SieciKom 2014 – 7. Intersieci -

routing

19

Rys. 7.6   Sieć i jej graf

SieciKom 2014 – 7. Intersieci -

routing

20

• Notacja (k,j) opisuje połączenie węzła k z węzłem j

SieciKom 2014 – 7. Intersieci -

routing

21

• W powyższych tabelach występują powtórzenia

łączy/skoków, co jest konsekwencją struktury
sieci, np. węzeł 1  eliminacja duplikatów,
których w dużych sieciach może być wiele

• Trasy domyślne (powtarzające się) –

pojedynczy wpis zastępujący powtarzające się
skoki

• Trasy domyślne mają najniższy priorytet, czyli

jeżeli algorytm nie znajdzie połączenia
bezpośredniego, to wybierze połączenie
domyślne

SieciKom 2014 – 7. Intersieci -

routing

22

SieciKom 2014 – 7. Intersieci -

routing

23

Wypełnianie tablic przekazywania odbywa się wg;

– Routingu statycznego – program wyznacza trasy

(zapisuje odpowiednie dane w tablicach) w momencie
uruchamiania przełącznika i nie ulegają one dalszym
zmianom  rozwiązanie proste i tanie, ale
nieelastyczne

– Routing dynamiczny – program w momencie

uruchamiania tworzy wstępną tablicę przekazywania
i następnie modyfikuje ją odpowiednio do zaistniałych
zmian w strukturze  duże nakłady obliczeniowe, ale
możliwość dostosowania się do awarii i wykorzystania
łączy/tras zapasowych.

SieciKom 2014 – 7. Intersieci -

routing

24

7.2.5 Rozproszone mechanizmy routingu

• Nie ma “centralnego” oprogramowania do

wyznaczania tras  przetwarzanie rozproszone

• Każdy przełącznik oblicza lokalnie własne tablice

przekazywania

• Wszystkie przełączniki biorą w wyznaczaniu

najkrótszych tras

• Istnieją zasadnicze dwie klasy algorytmów routing:

– Routing na bazie informacji o stanie łączy (Link-State

Routing - LSR) – tzw algorytmy Dijkstry

– Routing z wykorzystaniem wektorów odległości

(Distance-Vector Routing - DVR)

SieciKom 2014 – 7. Intersieci -

routing

25

7.2.6 Routing na bazie informacji o stanie
łączy

• Routing działa w oparciu o algorytm Dijskry poszukiwania

najkrótszej drogi

• Idea algorytmu sprowadza się do:

– Każdy przełącznik okresowo wysyła informację o stanie „swoich”

łączy z „sąsiadami?” – np. łącze 5-9 jest poprawne

– Informacja ta dociera do wszystkich przełączników, które

w oparciu o własne oprogramowanie budują graf sieci + tworzą
tablice przełączania (wg algorytmu 18.2) z sobą jako węzłem
źródłowym

– W przypadku awarii łącza oba podłączone do jego końców

przełączniki wykryją awarię i roześlą komunikaty o jego
niedostępności  wszystkie przełączniki odbiorą te komunikaty
i zmienią grafy sieci oraz uaktualnią swoje tablice przełączania.
Usunięcie awarii zostanie wykryte i nastąpi kolejna
„modyfikacja” sieci

SieciKom 2014 – 7. Intersieci -

routing

26

SieciKom 2014 – 7. Intersieci -

routing

27

7.2.7 Routing z wykorzystaniem wektorów
odległości

• Każdemu łaczu przypisana jest

pewna waga,

• Odległość do celu wyznacza się jako

sumę wag na trasie pomiędzy
przełącznikami

• Każdy przełącznik przechowuje listę

wszystkich potencjalnych sieci
docelowych + informację
o odległości + identyfikatory
najbliższych węzłów

SieciKom 2014 – 7. Intersieci -

routing

28

• Okresowo przełączniki wymieniają komunikaty

o stanie łączy i na podstawie otrzymanych
komunikatów każdy przełącznik rozsyła swoim
sąsiadom całą listę sieci docelowych znanych mu +
informację o koszcie dostarczenia pakietów;

Znam trasę do celu x, odległość ode mnie wynosi y

• Po odebraniu komunikatu przełączniki analizują

swoje tablice i je modyfikują (zmieniają wiersze)
wprowadzając trasy krótsze na miejsce istniejących

• W przypadku awarii łącza wyszukuje się trasę

zastępczą (poprzez inny węzeł) i do kosztu tej trasy
dodaje się koszt dojścia do niej.

SieciKom 2014 – 7. Intersieci -

routing

29

7.2.8 Interpretacja odległości w grafie
i najkrótszej trasy

• Wagi (nieujemne) przypisane łączom

mogą odpowiadać

– odległościom geograficznym pomiędzy

węzłami,

– „przepustowości/pojemności łącza”,
– liczbie przełączników pomiędzy węzłami

itp.

• Trasa opisana jest sumą wag

SieciKom 2014 – 7. Intersieci -

routing

30

Rys. 7.7   Przykład najkrótszej trasy pomiędzy
węzłem 4 i 5

SieciKom 2014 – 7. Intersieci -

routing

31