Sieci komputerowe
wykład dla ZLM4
2007/2008
wykład 9
Agata Półrola
Wydział Matematyki i Informatyki UA

http://www.math.uni.lodz.pl/~polrola
Jeszcze o trasowaniu:
protokoły routingu
Trasowanie
Routery dokonują wyboru trasy na
podstawie informacji zapisanej w tablicy
tras
Pytania:
jakie wartości powinny się znajdować
w tablicach tras?
skąd routery mają w tablicach wszystkie
potrzebne informacje?
Tablice tras
Każdy router rozpoczyna działanie z pewną
początkową tablicą tras, która jest
następnie aktualizowana jeżeli trasy się
zmieniają
W małych sieciach wystarczająca jest
aktualizacja ręczna, w dużych i szybko się
zmieniających potrzebne są metody
automatyczne
Tablice tras  c.d.
Dotychczas rozważany schemat nie
zawierał automatycznej modyfikacji tras
(poza ICMP redirect, przesyłanym między
routerem a hostem, a nie między routerami)
oraz nie zapewniał spójności trasowania
Rozwiązanie
z wczesnego Internetu
Sieć szkieletowa
Routery podzielone na dwie grupy: routery
centralne (core / interior routers) i routery
zewnętrzne (inaczej poboczne, exterior routers)
Routery centralne komunikują się między sobą,
tak aby każdy z nich miał pełną wiedzę o
wszystkich możliwych trasach i aby ta wiedza
była spójna
Routery centralne nie stosują tras domyślnych,
gdyż może to prowadzić do nieefektywności
komunikacji
Rozwiązanie
z wczesnego Internetu  c.d.
We wczesnym Internecie  szkielet (routery
centralne) stanowiła sieć ARPANET
Routery centralne były zarządzane przez INOC
(Internet Network Operation Center), a poboczne
 przez inne (lokalne) organizacje mające dostęp
do sieci
Takie rozwiązanie nie sprawdza się w sieciach
o bardziej złożonej topologii (np. utworzenie dwóch sieci
szkieletowych komunikujących się ze sobą za pośrednictwem
kilku routerów bardzo komplikuje trasowanie)
Najpopularniejsze algorytmy
obliczania i propagacji tras
Algorytm wektor - odległość (vector  distance,
Bellman-Ford routing)
Router pamięta w tablicy wszystkie znane mu routery
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ą
wada algorytmów  wektor  odległość : konieczność
wymiany dużej liczby komunikatów
Algorytmy obliczania
i propagacji tras  c.d.
Link-state routing (tzw. SPF, najpierw
najkrótsza ścieżka)
Algorytmy SPF wymagają od każdego routera pełnej
informacji o topologii sieci
Router testuje stan routerów sąsiednich (stan łącza)
i propaguje stan łącza do wszystkich innych routerów
Co jakiś czas router rozgłasza informacje ze stanem
wszystkich łączy. Router otrzymujący taką informację
modyfikuje stan tras w swojej  mapie sieci i aktualizuje
tablicę tras obliczając najkrótsze ścieżki w uzyskanym grafie
(algorytm Dijkstry)
Protokół GGP
Wczesny Internet używał do wymiany informacji
o routingu protokołu GGP (Gateway  to 
Gateway Protocol)
Protokół  wektor-odległość
Był używany przez routery centralne
Nowy router dodawany do systemu otrzymywał listę
sąsiadów, z którymi wymieniał informacje
Wymieniane informacje zawierały zbiór par (N,D),
gdzie N  sieć docelowa, D  odległość mierzona
w  router hops (liczba routerów w drodze do tej
sieci)
Routing hierarchiczny
wraz ze wzrostem rozmiaru sieci i liczby
routerów obciążenie związane z
przechowywaniem i przesyłaniem informacji
związanych z routingiem staje się bardzo duże
niemożliwe jest, aby każdy router przechowywał informacje
o całej sieci globalnej
potrzebna jest autonomia administracyjna
poszczególnych organizacji mających swoje sieci
rozwiązanie: organizowanie routerów za pomocą
systemów autonomicznych
Systemy autonomiczne
System autonomiczny  grupa sieci
i routerów pod wspólną administracją
Routery wewnątrz systemu autonomicznego
dowolnie zarządzają trasami
Każdy system autonomiczny wybiera router lub
routery przeznaczone do komunikacji z innymi
systemami autonomicznymi. Odpowiadają one za
przekazywanie informacji o osiągalności sieci
wewnątrz  swojego systemu do innych
systemów
Systemy autonomiczne  c.d.
Routery odpowiedzialne za komunikację
z innymi systemami autonomicznymi
nazywane są routerami zewnętrznymi albo
brzegowymi (exterior gateways), routery
działające wewnątrz systemu 
wewnętrznymi (interior gateways)
Komunikacja między routerami
zewnętrznymi
Jednym z protokołów używanych do komunikacji
między routerami zewnętrznymi jest EGP (Exterior
Gateway Protocol)
router może uzgodnić z innym routerem, że będą
 sąsiadami . tzn. będą wymieniać informacje o trasach
router sprawdza co jakiś czas czy jego sąsiedzi działają
sąsiedzi wymieniają komunikaty pozwalające
zaktualizować tablice routingu. Komunikat taki zawiera
listę znanych danemu routerowi sieci i odległości do nich
Inny protokół tego typu  (E)BGP (Exterior Border
Gateway Protocol)
Komunikacja między routerami
wewnętrznymi
Grupę protokołów używanych przez
routery wewnątrz systemu autonomicznego
określa się nazwą IGP (Interior Gateway
Protocols)
Przykładowe protokoły z tej grupy:
RIP
HELLO
OSPF
Komunikacja między routerami
wewnętrznymi  c.d.
RIP  Routing Information Protocol
implementacja algorytmu wektor-odległość
dla sieci lokalnych
odległość mierzona jako  hop count 
liczba routerów między rozważanymi
sieciami
przeznaczony dla niewielkich sieci 
odległość 16 traktowana jest jako
nieskończoność
Komunikacja między routerami
wewnętrznymi  c.d.
HELLO
protokół bazujący na algorytmie  wektor-
odległość
do oceny odległości używa opóz
nień (tj.
czasu potrzebnego na dostarczenie
komunikatu za pośrednictwem sieci), a nie
liczby routerów pośredniczących
Komunikacja między routerami
wewnętrznymi  c.d.
OSPF  Open SPF Protocol
zestandaryzowany protokół implementujący algorytm SPF
wprowadza wiele ulepszeń pozwalających na bardziej
efektywną komunikację
wymiana danych między routerami jest autoryzowana (dane
wymieniają tylko routery uprawnione)
zezwala na abstrakcję szczegółów sieci fizycznych (krawędz
w
pamiętanym grafie połączeń może odpowiadać przejściu przez kilka
sieci pośredniczących; węzeł grafu może być routerem lub siecią)
pozwala na równoważenie obciążeń, jeśli do danej sieci prowadzi
kilka tras o tym samym koszcie
pozwala na trasowanie  type of service (trasami o małych
opóz
nieniach, wysokiej przepustowości itp, jeśli nadawca tego
wymaga)
Protokół IPv6
nowa wersja protokołu IP
Protokół IPv6
Wersja protokołu IP omówiona wcześniej
to wersja 4 (IPv4)
Opracowanie nowej wersji (6, oznaczanej
jako IPv6, IPng) zostało spowodowane
m.in. przez wyczerpywanie się przestrzeni
adresowej
Protokół IPv6  c.d.
Cechy IPv6 analogiczne do IPv4:
protokół bezpołączeniowy
umożliwia nadawcy wybieranie rozmiaru datagramu
nagłówek datagramu zawiera adres IP nadawcy
i odbiorcy
adres odbiorcy służy do wyznaczania trasy
jedno z pól nagłówka ogranicza liczbę routerów,
przez które może przejść datagram
zachowana została większość rozwiązań związanych
z opcjami IPv4, w tym związanych z fragmentacją
i trasowaniem wg nadawcy
Protokół IPv6  c.d.
Nowe cechy IPv6:
dłuższe adresy
(128-bitowe zamiast 32-bitowe)
elastyczny format nagłówka
ulepszone opcje IP
wsparcie dla rezerwowania zasobów
można ustanowić ścieżkę wysokiej jakości przez
sieci bazowe i powiązać datagramy z tą ścieżką;
przydatne dla aplikacji multimedialnych
zapewnienie rozszerzalności protokołu
Adresy IPv6
Adres 128-bitowy (ponad 3.4 " 1038
adresów)
gdyby adresy były przypisywane z prędkością
milion adresów na mikrosekundę, to przypisanie
wszystkich zajęłoby około 20 lat
Nie ma klas, podział na prefiks i sufiks
może przebiegać w dowolnym miejscu
i nie można go wyznaczyć na podstawie
samego adresu
Adresy IPv6  c.d.
Zestaw adresów specjalnego przeznaczenia
bardzo się różni od IPv4:
nie ma rozgłoszenia skierowanego do danej
sieci
każdy adres należy do jednego z trzech
podstawowych typów:
adres jednostkowy
adres rozsyłania grupowego
adres grona
Adresy IPv6  c.d.
Adres jednostkowy 
datagram wysyłany pod ten adres jest przesyłany
najkrótszą trasą do danego komputera
Adres rozsyłania grupowego 
odpowiada zbiorowi komputerów, które mogą się
znajdować w różnych miejscach sieci
przynależność do tego zbioru można zmieniać
w dowolnym momencie
datagram wysyłany pod taki adres jest dostarczany
do wszystkich członków grupy
Adresy IPv6  c.d.
Adres grona -
adres odpowiadający zbiorowi komputerów
mających pewien wspólny prefiks adresu (np.
znajdują się one w jednym miejscu)
datagram dostarczany jest najkrótszą ścieżką do
tego miejsca, a następnie dostarczany jednemu
z członków grupy
grona stosuje się z powodu konieczności
zapewnienia repliki usługi
Adresy IPv6  c.d.
Format adresów umożliwia adresowanie
hierarchiczne, np:
typ provider subscriber subnet node ID
adresu ID ID ID
Istnieje możliwość odwzorowania adresu IPv4 na
adres IPv6 (96 bitów wypełnionych zerami, dalej
 32 bity jak w adresie IPv4)
Datagram IPv6
Datagram IPv6 zaczyna się od nagłówka
podstawowego, po którym następuje zero lub
więcej nagłówków dodatkowych, po których
następują dane
nagłówek nagłówek nagłówek dane
dodatkowy dodatkowy
podstawo- . . .
1 n
wy
opcjonalnie
Nagłówki dodatkowe mogą być różnych rozmiarów
Datagram IPv6:
nagłówek podstawowy
wersja
priorytet etykieta potoku
nast. nagłówek liczba etapów
długość zawartości
adres IP nadawcy
adres IP odbiorcy
Nagłówek podstawowy  c.d.
wersja  wersja protokołu IP (tu 6)
priorytet  określenie priorytetu datagramu
długość zawartości  określa (w oktetach) rozmiar
przenoszonych danych (bez nagłówków). Datagram
może zawierać do 64 kilobajtów danych
liczba etapów  odpowiada polu czas życia
w datagramie IPv4.
Różnica  w IPv4 czas życia był traktowany jako
kombinacja czasu i liczby etapów; tu jest to dokładnie liczba
etapów (routerów przez które przechodzi datagram)
Rozmiar nagłówka podstawowego  40 oktetów
Datagram IPv6:
nagłówki dodatkowe
Dodatkowe nagłówki pełnią rolę podobną
do opcji IPv4  nadawca może
zdecydować, jakie dołączyć, a jakich nie
Każdy z nagłówków  podstawowy
i dodatkowe  zawiera pole następny
nagłówek, pozwalające określić rodzaj
kolejnego nagłówka lub typ danych
przenoszonych w datagramie, jeśli
następny nagłówek nie istnieje
IPv6: fragmentacja datagramów
Datagramy IPv6 są fragmentowane
z analogicznych powodów jak datagramy
IPv4
Połączenie fragmentów odbywa się
u ostatecznego odbiorcy
Datagramy będące fragmentami mają
dodatkowy nagłówek fragmentacji