Sieci komputerowe

wykład dla ZLM4
2007/2008

wykład 9

Agata Półrola

Wydział Matematyki i Informatyki UŁ

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óź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ędź 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óź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 •10

38

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:

Istnieje możliwość odwzorowania adresu IPv4 na
adres IPv6 (96 bitów wypełnionych zerami, dalej
– 32 bity jak w adresie IPv4)

node ID

subnet

ID

subscriber

ID

provider

ID

typ

adresu

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łówki dodatkowe mogą być różnych rozmiarów

dane

nagłówek

dodatkowy

n

. . .

nagłówek

dodatkowy

1

nagłówek

podstawo-

wy

opcjonalnie

Datagram IPv6:
nagłówek podstawowy

adres IP odbiorcy

adres IP nadawcy

liczba etapów

nast. nagłówek

długość zawartości

etykieta potoku

priorytet

wersja

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