---
# System prepended metadata

title: Ćwiczenia 1
tags: [Sieci Komputerowe]

---

###### 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.
:::
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>