Ćwiczenia 1 - HackMD

###### tags: `Sieci Komputerowe` # Ćwiczenia 1 ## Zadanie 1 :::info Dla każdego z podanych poniżej adresów IP w notacji CIDR określ, czy jest to adres sieci, adres rozgłoszeniowy czy też adres komputera. W każdym przypadku wyznacz odpowiadający mu adres sieci, rozgłoszeniowy i jakiś adres IP innego komputera w tej samej sieci. $\blacktriangleright$ $10.1.2.3/8$ $\blacktriangleright$ $156.17.0.0/16$ $\blacktriangleright$ $99.99.99.99/27$ $\blacktriangleright$ $156.17.64.4/30$ $\blacktriangleright$ $123.123.123.123/32$ ::: ### 10.1.2.3/8 10.1.2.3/8 - **adres komputera** 10.0.0.1/8 - **inny adres komputera** 10.0.0.0/8 - **adres sieci** 10.255.255.255/8 - **adres rozgłoszeniowy** ### 156.17.0.0/16 156.17.0.0/16 - **adres sieci** 156.17.0.1/16 - **adres komputera** 156.17.255.255/16 - **adres rozgłoszeniowy** ### 99.99.99.99/27 99.99.99.99/27 - **adres komputera** maska:255.255.255.224 99.99.99.99 $AND$ 255.255.255.224 $=$ 99.99.99.96 99.99.99.96/27 - **adres sieci** 99.99.99.97/27 - **adres innego komputera** 99.99.99.127/27 - **adres rozgłoszeniowy** ### 156.17.64.4/30 maska: 255.255.255.252 156.17.64.4 $AND$ 255.255.255.252 $=$ 156.17.64.4/30 - **adres sieci** 156.17.64.5/30 - **adres komputera** 156.17.64.7/30 - **adres rozgłoszeniowy** ### 123.123.123.123/32 123.123.123.123/32 - **adres sieci** 123.123.123.123/32 - **adres komputera** 123.123.123.123/32 - **adres rozgłoszeniowy** ## Zadanie 2 :::info Podziel sieć $10.10.0.0/16$ na $5$ rozłącznych podsieci, tak aby każdy z adresów IP z sieci $10.10.0.0/16$ był w jednej z tych 5 podsieci. Jak zmieniła się liczba adresów IP możliwych do użycia przy adresowaniu komputerów? Jaki jest minimalny rozmiar podsieci, który możesz uzyskać w ten sposób? ::: Dokonujemy podziału tej sieci na tak, aby powstała sieć o najmniejszym możliwym rozmiarze. 1. * $10.10.0.0/17$ * $10.10.128.0/17$ 2. * $10.10.0.0/17$ * $10.10.128.0/18$ * $10.10.192.0/18$ 3. * $10.10.0.0/17$ * $10.10.128.0/18$ * $10.10.192.0/19$ * $10.10.224.0/19$ 4. * $10.10.0.0/17$ * $10.10.128.0/18$ * $10.10.192.0/19$ * $10.10.224.0/20$ * $10.10.240.0/20$ :::info Jak zmieniła się liczba adresów IP możliwych do użycia przy adresowaniu komputerów? ::: Było: $2^{32-16}-2=2^{16}-2$ Jest: $2^{32-17}-2+2^{32-18}-2+2^{32-19}-2+2^{32-20}-2+2^{32-20}-2=\\=2^{15}+2^{14}+2^{13}+2*2^{12}-10=2^{16}-10$ **Po podziale dostępnych jest 8 adresów IP mniej.** :::info Jaki jest minimalny rozmiar sieci, który możesz uzyskać w ten sposób? ::: Najmniejsza możliwa sieć: $10.10.240.0/20$ Minimalny rozmiar podsieci to $2^{32-20}-2=2^{12}-2=4096-2=4094$ ## Zadanie 3 :::info Tablica routingu zawiera następujące wpisy (podsieć $\rightarrow$ dokąd wysłać): $\blacktriangleright$ $0.0.0.0/0$ $\rightarrow$ do routera $A$ $\blacktriangleright$ $10.0.0.0/23$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.2.0/24$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.3.0/24$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.1.0/24$ $\rightarrow$ do routera $C$ $\blacktriangleright$ $10.0.0.128/25$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.1.8/29$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.1.16/29$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.0.1.24/29$ $\rightarrow$ do routera $B$ Napisz równoważną tablicę routingu zawierającą jak najmniej wpisów. ::: | ID | Router docelowy | Pierwszy adres sieci | Ostatni adres sieci | | --- | --------------- | -------------------- | ------------------- | | 1 | A | $0.0.0.0/0$ | $255.255.255.255/0$ | | 2 | B | $10.0.0.0/23$ | $10.0.1.255/23$ | | 3 | B | $10.0.2.0/24$ | $10.0.2.255/24$ | | 4 | B | $10.0.3.0/24$ | $10.0.3.255/24$ | | 5 | C | $10.0.1.0/24$ | $10.0.1.255/24$ | | 6 | B | $10.0.0.128/25$ | $10.0.0.255/25$ | | 7 | B | $10.0.1.8/29$ | $10.0.1.15/29$ | | 8 | B | $10.0.1.16/29$ | $10.0.1.23/29$ | | 9 | B | $10.0.1.24/29$ | $10.0.1.31/29$ | Sieć pod id równym $6$ zawiera się w sieci $2$ i nie zawiera się w żadnym wpisie z routerem docelowym innym niż B, więc można ten wpis usunąć. Zauważmy, że wpis w tablicy $3$ i $4$ można scalić do jednego: $10.0.2.0/23$ (mają również ten sam router docelowy). Taki nowo powstały adres można scalić z siecią $2$ co daje adres $10.0.0.0/22$. Scalić możemy również sieci $7$ i $8$. Adres powstałej sieci to $10.0.1.8/28$ Nowo powstała tablica routingu: | ID | Router docelowy | Pierwszy adres sieci | Ostatni adres sieci | | --- | --------------- | -------------------- | ------------------- | | 1 | A | $0.0.0.0/0$ | $255.255.255.255/0$ | | 2 | B | $10.0.0.0/22$ | $10.0.3.255/22$ | | 5 | C | $10.0.1.0/24$ | $10.0.1.255/24$ | | 7 | B | $10.0.1.8/28$ | $10.0.1.23/28$ | | 9 | B | $10.0.1.24/29$ | $10.0.1.31/29$ | Sieci $7$ i $8$ zawierają się w sieci $5$, która ma inny router docelowy oraz obie te sieci mają inną maskę. Nowo powstała tablica jest minimalną tablicą routingu. ## Zadanie 4 :::info Wykonaj powyższe zadanie dla tablicy $\blacktriangleright$ $0.0.0.0/0$ $\rightarrow$ do routera $A$ $\blacktriangleright$ $10.0.0.0/8$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.3.0.0/24$ $\rightarrow$ do routera $C$ $\blacktriangleright$ $10.3.0.32/27$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.3.0.64/27$ $\rightarrow$ do routera $B$ $\blacktriangleright$ $10.3.0.96/27$ $\rightarrow$ do routera $B$ ::: | ID | Router docelowy | Pierwszy adres sieci | Ostatni adres sieci | |:---:| --------------- | -------------------- | ------------------- | | 1 | A | $0.0.0.0/0$ | $255.255.255.255/0$ | | 2 | B | $10.0.0.0/8$ | $10.255.255.255/8$ | | 3 | C | $10.3.0.0/24$ | $10.3.0.255/24$ | | 4 | B | $10.3.0.32/27$ | $10.3.0.63/27$ | | 5 | B | $10.3.0.64/27$ | $10.3.0.95/27$ | | 6 | B | $10.3.0.96/27$ | $10.3.0.127/27$ | Zauważmy, że sieci $4,5,6$ mają ten sam router docelowy $B$ oraz adresy tych sieci znajdują się "obok siebie" i wszyskie są zawarte wśród adresów sieci $3$ z routerem docelowym $C$, który jest zawarty w jeszcze większej sieci z routerem docelowym $B$, dlatego możemy podzielić sieć z routerem docelowym $C$ na dwie oraz usunąć sieci $4,5,6$ z tablicy routingu otrzymując minimalnej długości tablicę: | ID | Router docelowy | Pierwszy adres sieci | Ostatni adres sieci | | --- | --------------- |:--------------------:| ------------------- | | 1 | A | $0.0.0.0/0$ | $255.255.255.255/0$ | | 2 | B | $10.0.0.0/8$ | $10.255.255.255/8$ | | 3 | C | $10.3.0.0/27$ | $10.3.0.31/27$ | | 4 | C | $10.3.0.128/25$ | $10.3.0.255/25$ | ## Zadanie 5 :::info Jak uporządkować wpisy w tablicy routingu, żeby zasada najlepszego dopasowania odpowiadała wyborowi „pierwszy pasujący” (tj. przeglądaniu tablicy od początku do końca aż do momentu napotkania dowolnej pasującej reguły)? Odpowiedź uzasadnij formalnie ::: Wpisy w tablicy routingu należy uporządkować malejąco po rozmiarze maski. Dowód: Załóżmy, że tablica routingu jest posortowana malejąco po rozmiarze maski. Weźmy adres komputera $X_1.X_2.X_3.X_4$ i weźmy pierwszy adres sieci od góry, do którego się dopasuje i nazwijmy go $A_1.A_2.A_3.A_4/M_1$ Weźmy kolejny adres sieci, położony później w tablicy routingu, do którego również pasuje adres $X_1.X_2.X_3.X_4$ i nazwijmy go $B_1.B_2.B_3.B_4/M_2$. Wiemy z założenia, że $M_2 \leq M_1$ czyli adres $A_1.A_2.A_3.A_4/M_1$ ma mniej równo dopasowanych bitów początkowych do adresu $B_1.B_2.B_3.B_4$ niż adres $A_1.A_2.A_3.A_4/M_1$ co oznacza, że nie jest lepszym dopasowaniem do adresu $X_1.X_2.X_3.X_4$ $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare$ ## Zadanie 6 :::info W podanej niżej sieci tablice routingu budowane są za pomocą algorytmu wektora odległości. Pokaż (krok po kroku), jak będzie się to odbywać. W ilu krokach zostanie osiągnięty stan stabilny ![](https://i.imgur.com/ULzjg1A.png) ::: * Na początku mamy | | A | B | C | D | E | F | | --- | --- | --- | --- | --- | --- | --- | | **A** | 0 | 1 | | | | | | **B** | 1 | 0 | 1 | | | | | **C** | | 1 | 0 | | 1 | 1 | | **D** | | | | 0 | 1 | | | **E** | | | 1 | 1 | 0 | 1 | | **F** | | | 1 | | 1 | 0 | | **S** | 1 | 1 | | | | | * krok 1 | | A | B | C | D | E | F | | --- |:--------:|:--------:|:--------:|:--------:|:--------:|:--------:| | **A** | 0 | 1 | 2(via B) | | | | | **B** | 1 | 0 | 1 | | 2(via C) | 2(via C) | | **C** | 2(via B) | 1 | 0 | 2(via E) | 1 | 1 | | **D** | | | 2(via E) | 0 | 1 | 2(via E) | | **E** | | 2(via C) | 1 | 1 | 0 | 1 | | **F** | | 2(via C) | 1 | 2(via E) | 1 | 0 | | **S** | 1 | 1 | 2(via B) | | | | * krok 2 | | A | B | C | D | E | F | | --- |:--------:|:--------:|:--------:|:--------:|:--------:|:---------:| | **A** | 0 | 1 | 2(via B) | | 3(via C) | 3(via C) | | **B** | 1 | 0 | 1 | 3(via E) | 2(via C) | 2(via C) | | **C** | 2(via B) | 1 | 0 | 2(via E) | 1 | 1 | | **D** | | 3(via C) | 2(via E) | 0 | 1 | 2(via E) | | **E** | 3(via B) | 2(via C) | 1 | 1 | 0 | 1 | | **F** | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | 0 | | **S** | 1 | 1 | 2(via B) | | 3(via C) | 3 (via C) | * krok 3 (dostaliśmy stan stabilny) | | A | B | C | D | E | F | | --- |:--------:|:--------:|:--------:|:--------:|:--------:|:---------:| | **A** | 0 | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | | **B** | 1 | 0 | 1 | 3(via E) | 2(via C) | 2(via C) | | **C** | 2(via B) | 1 | 0 | 2(via E) | 1 | 1 | | **D** | 4(via B) | 3(via C) | 2(via E) | 0 | 1 | 2(via E) | | **E** | 3(via B) | 2(via C) | 1 | 1 | 0 | 1 | | **F** | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | 0 | | **S** | 1 | 1 | 2(via B) | 4(via E) | 3(via C) | 3 (via C) | **W 3 krokach** ## Zadanie 7 :::info Załóżmy, że w powyższej sieci tablice routingu zostały już zbudowane. Co będzie się działo, jeśli zostanie dodane połączenie między routerami $A$ i $D$? ::: * Na początku mamy | | A | B | C | D | E | F | | --- |:--------:|:--------:|:--------:|:--------:|:--------:|:---------:| | **A** | 0 | 1 | 2(via B) | 4(via E) | 3(via C) | 3(via C) | | **B** | 1 | 0 | 1 | 3( E) | 2(via C) | 2(via C) | | **C** | 2(via B) | 1 | 0 | 2(via E) | 1 | 1 | | **D** | 4(via B) | 3(via C) | 2(via E) | 0 | 1 | 2(via E) | | **E** | 3(via B) | 2(via C) | 1 | 1 | 0 | 1 | | **F** | 3(via B) | 2(via C) | 1 | 2(via E) | 1 | 0 | | **S** | 1 | 1 | 2(via B) | 4(via E) | 3(via C) | 3 (via C) | Droga pomiędzy $A$ i $D$ zostanie zaktualizowana na długość $1$, a następnie wszystkie routery uzależnione od tych dwóch routerów zostaną powiadomione o możliwej krótszej drodze. Następnie te routery analizują i sprawdzają czy mają możliwość krótszej drogi do tych routerów, jak tak to to robią i wysyłają sygnały dalej i tak dalej. * po wykonaniu kroków: | | A | B | C | D | E | F | | --- |:----:|:-----:|:----:|:----:|:-----:|:------:| | **A** | 0 | 1 | 2(B) | 1 | 2(D) | 3( C) | | **B** | 1 | 0 | 1 | 2(A) | 2( C) | 2( C) | | **C** | 2(B) | 1 | 0 | 2(E) | 1 | 1 | | **D** | 1 | 2(A) | 2(E) | 0 | 1 | 2(E) | | **E** | 2(D) | 2( C) | 1 | 1 | 0 | 1 | | **F** | 3(B) | 2( C) | 1 | 2(E) | 1 | 0 | | **S** | 1 | 1 | 2(B) | 2(A) | 3( C) | 3 ( C) | ## Zadanie 8 :::info W przedstawionej poniżej sieci uszkodzeniu ulega połączenie między routerami $D$ i $E$. Załóżmy, że w sieci działa algorytm wektora odległości wykorzystujący technikę zatruwania ścieżki zwrotnej (poison reverse). Pokaż — opisując krok po kroku jakie komunikaty są przesyłane między routerami — że może powstać cykl w routingu. ![](https://i.imgur.com/vEoF3co.png) ::: * Stan przed awarią: | | A | B | C | D | E | | --- | ---- | ---- |:----:|:----:|:----:| | **A** | 0 | 1 | 1 | 2(via B) | 3(via D) | | **B** | 1 | 0 | 2(via A) | 1 | 2(via D) | | **C** | 1 | 2(via A) | 0 | 1 | 2(via D) | | **D** | 2(via B) | 1 | 1 | 0 | 1 | | **E** | 3(via B) | 2(via D) | 2(via D) | 1 | 0 | Przeanalizujmy trasę z routerów $A,B,C,D$ do routera $E$ * Trasa do E: | | A | B | C | D | | --- | ---- | ---- |:----:|:---:| | **E** | 3(via B) | 2(via D) | 2(via D) | 1 | * Możliwy scenariusz, który prowadzi do cyklu: * Usuwamy połączenie z routera $D$ do routera $E$: | | A | B | C | D | | --- | ---- | ---- |:----:|:--------:| | **E** | 3(via B) | 2(via D) | 2(via D) | $\infty$ | * $D$ znajduje lepszą drogę do $E$ przez $C$: | | A | B | C | D | | --- | ---- | ---- |:----:|:----:| | **E** | 3(via B) | 2(via D) | 2(via D) | 3(via C) | * $C$ zna drogę przez $D$, która trwa 3, więc aktualizuje się do $4$ | | A | B | C | D | | --- | ---- | ---- |:----:|:----:| | **E** | 3(via B) | 2(via D) | 4(via D) | 3(via C) | I tak każdy router po kolei będzie aktualizował swoje ścieżki, co prowadzi do cyklu. ## Zadanie 9 X :::info Pokaż, że przy wykorzystaniu algorytmu stanu łączy też może powstać cykl w routingu. W tym celu skonstruuj topologię sieci z dwoma wyróżnionymi, bezpośrednio połączonymi routerami $A$ i $B$. Załóż, że wszystkie routery znają topologię całej tej sieci. W pewnym momencie łącze między $A$ i $B$ ulega awarii, o czym $A$ i $B$ od razu się dowiadują. Zalewają one sieć odpowiednią aktualizacją. Pokaż, że w okresie propagowania tej aktualizacji (kiedy dotarła ona już do części routerów a do części nie) może powstać cykl w routingu. ::: ## Zadanie 10 X :::info Załóżmy, że sieć składa się z łączy jednokierunkowych (tj. topologia sieci jest grafem skierowanym) i nie zawiera cykli. Rozważmy niekontrolowany algorytm „zalewający” sieć jakimś komunikatem: komu- nikat zostaje wysłany początkowo przez pewien router; każdy router, który dostanie dany komunikat przesyła go dalej wszystkimi wychodzącymi z niego krawędziami. Pokaż, że istnieją takie sieci z n routerami, w których przesyłanie informacji zakończy się po czasie $2^{Ω(n)}$. Zakładamy, że przez jedno łącze można przesłać tylko jeden komunikat naraz, a przesłanie go trwa jednostkę czasu. :::