---
# System prepended metadata

title: SIECI Ćwiczenia 1-3
tags: [Sieci]

---

# SIECI Ćwiczenia 1-3
###### tags: `Sieci`

## Ćwiczenia 1

### 1.
![](https://i.imgur.com/CypbYWg.png)
* `10.1.2.3/8`
Maska: `11111111.00000000.0000000.00000000`
Adres sieci: `10.0.0.0`
Adres rozgłoszeniowy: `10.255.255.255`
Przykładowy adres: `10.1.1.1`


* `156.17.0.0/16`
Maska: `11111111.11111111.00000000.00000000`
Adres sieci: `156.17.0.0`
Adres rozgłoszeniowy: `156.17.255.255`
Przykładowy adres: `156.17.2.137`


* `99.99.99.99/27`
Maska: `11111111.11111111.11111111.11100000`
Adres sieci: 
`99 = 01100011`
`01100011 & 11100000 = 01100000 = 96(dec)`
`99.99.99.96`
Adres rozgłoszeniowy:
`01100000 | ~11100000 = 01100000 | 00011111 = 01111111 = 127(dec)`
`99.99.99.127`
Przykładowy adres: `99.99.99.100`


* `156.17.64.4/30`
Maska: `11111111.11111111.11111111.11111100`
Adres sieci: 
`4(dec) & 11111100 = 00000100 & 11111100 = 00000100 = 4(dec)`
`156.17.64.4`
Adres rozgłoszeniowy:
`00000100 | ~11111100 = 00000100 | 00000011 = 00000111 = 7(dec)`
`156.17.64.7`
Przykładowy adres: `156.17.64.5`

* `123.123.123.123/32`
Maska: `11111111.11111111.11111111.11111111`
Nie jest to adres sieci tylko adres pojedyńczego hosta.


### 2.
![](https://i.imgur.com/OUcmloX.png)

Do stworznenia 5 podsieci będziemy potrzebować 3 bitów ($\log_25$). Rozmiar maski to 16 bitów, więc pierwsze 16 bitów adresu IP musi pozostać niezmieniona. Pierwszy adres będzie miał następne 3 bity 000. Jego końcówka więc wygląda tak: `00000000.00000000`. Docelowy adres będzie musił wiziąć pod uwagę, że dodatkowe 3 niezmienne bity będą musiały pozostać niezmienione, więc maska powiększy się o 3. Docelowo będzie wyglądać tak:
* `00001010.00001010.00000000.00000000/19 = 10.10.0.0/19`
* Drugi adres będzie w miał następne 3 bity w postaci 001 więc docelowy adres będzie wyglądał tak:
`00001010.00001010.00100000.00000000/19 = 10.10.32.0/19`
* Trzeci: `00001010.00001010.01000000.00000000/19 = 10.10.64.0/19`
* Czwarty: `00001010.00001010.01100000.00000000/19 = 10.10.96.0/19`
* Ostatni adres będzie nieco większy ponieważ 3 bity mogą przechować 8 możliwości, a my wykorzystujemy tylko 5. Maska w ostatnim adresie nie będzie większa o 3 tylko o 1. Docelowy adres:
`00001010.00001010.10000000.00000000/17 = 10.10.128.0/17`
    * `00001010.00001010.10000000.00000000/19 = 10.10.128.0/19`
    * `00001010.00001010.10100000.00000000/19 = 10.10.160.0/19`
    * `00001010.00001010.11000000.00000000/19 = 10.10.192.0/19`
    * `00001010.00001010.11100000.00000000/19 = 10.10.224.0/19`

Liczba adresów IP zmniejsza się dzieląc sieć na 5 podsieci, ponieważ są one zajmowane również przez adresy rozgłoszeniowe i adresi sieci. W poprzedniej sieci były 2 zajęte adresy, teraz mamy 10.

Aby usyskać minimalną podsieć należy za każdym razem dzieląc sieć, zwiększać maskę o jeden, wtedy otrzymamy najmniejszą możliwą podsieć. Otrzymujemy więc:
* 1: `00001010.00001010.10000000.00000000/17 = 10.10.128.0/17`
* 2: `00001010.00001010.01000000.00000000/18 = 10.10.64.0/18`
* 3: `00001010.00001010.00100000.00000000/19 = 10.10.32.0/19`
* 4: `00001010.00001010.00010000.00000000/20 = 10.10.16.0/20`
* 5: `00001010.00001010.00000000.00000000/20 = 10.10.0.0/20`
Najmniejsza podsieć, to ta z największą maską czyli 4 lub 5. Jej rozmiar to $2^{32-20}-2 = 2^{12} - 2 = 4094$.

### 3.
![](https://i.imgur.com/jpCiwH8.png)

Zakres routingów:
* 1: A `default`
* 2: B `10.0.0.0  ` - `10.0.1.255`
* 3: B `10.0.2.0  ` - `10.0.2.255` 
* 4: B `10.0.3.0  ` - `10.0.3.255`
* 5: C `10.0.1.0  ` - `10.0.1.255`
* 6: B `10.0.0.128` - `10.0.0.255`
* 7: B `10.0.1.8  ` - `10.0.1.15`
* 8: B `10.0.1.16 ` - `10.0.1.23`
* 9: B `10.0.1.24 ` - `10.0.1.31`

![](https://i.imgur.com/qlYsalT.png)

Wpisy od 2 do 4 możemy skleić w jeden - `10.0.1.0 - 10.0.3.255 = 10.0.0.0/22`
7- `10.0.1.8 - 10.0.1.15 = 10.0.8/29`
Od 8 do 9 `10.0.1.16 - 10.0.1.31 = 10.0.1.16/28`

Zmniejszona tablica routingu będzie więc wyglądać:
| Podsieć        | Cel | Początek    | Koniec            |
|:-------------- | --- | ----------- | ----------------- |
| `default     ` | A   | `0.0.0.0`   | `255.255.255.255` |
| `10.0.0.0/22 ` | B   | `10.0.0.0`  | `10.0.3.255`      |
| `10.0.1.0/24 ` | C   | `10.0.1.0`  | `10.0.1.255`      |
| `10.0.1.8/29 ` | B   | `10.0.1.8`  | `10.0.1.15`       |
| `10.0.1.16/28` | B   | `10.0.1.16` | `10.0.1.31`       |




### 4.
![](https://i.imgur.com/Yg6uhMc.png)


Zakres routingów:
* 1: A `default`
* 2: B `10.0.0.0  ` - `10.255.255.255`
* 3: C `10.3.0.0  ` - `10.3.0.255` 
* 4: B `10.3.0.32` - `10.3.0.63`
* 5: B `10.3.0.64` - `10.3.0.95`
* 6: B `10.3.0.96` - `10.3.0.127`


![](https://i.imgur.com/kRosrAW.png)
Patrząc na rysunek, możemy zauważyć, że "przebijając" górną siecią B przez C w C zostaną nam zakresy: `10.3.0.0 - 10.3.0.31 = 10.3.0.0/27` i `10.3.0.128 - 10.3.0.255 = 10.3.0.128/25`. Dlatego możemy zredukować wszystkie określenia B od jednego, szerokiego `10.0.0.0 - 10.255.255.255 = 10.0.0.0/8`, i dodać dwie podsieci C "nad" B.
![](https://i.imgur.com/DDazWQX.png)


| Podsieć          | Cel |
|:---------------- |:--- |
| `    default   ` | A   |
| `  10.0.0.0/8  ` | B   |
| `  10.3.0.0/27 ` | C   |
| ` 10.3.0.128/25` | C   |


### 5.
![](https://i.imgur.com/vRaZQfV.png)

Wpisy w tablicy będziemy uporządkowywać od najdłuższych pasujących prefiksów do najkrtószych. Jeżeli długość prefiksu jest taka sama, to nie sortujemy.

**Dowód:**
Załóżmy, że wpisy w tablicy roubingu są uporządkowane od najdłużyszch pasujących prefiksów do najkrótszych. Udowodnimy, że wybór pierwszego pasującego wpisu prowadzi do najlepszego dopasowania:

Weźmy dowolny adres IP, oznaczmy go jako $x$. Niech $y$ będzie pierwszym wpisem w tablicy routingu, do którego nie pasuje $x$. Przez $n$ oznaczmy długość prefiksu $y$, a skoro $x$ pasuje do $y$, to pierwsze $n$ bitów $x$ oraz $y$ są takie same. Teraz weźmy dowolny wpis $z$ będący w tablicy routingu za $y$. Oznacza to, że $z$ ma mniejszy prefiks od $y$, a więc długość $m$ prefiksu $z$ spełnia nierówność $m \leq n$. Oznacza to, że dopasowane zostanie nie więcej bitów $x$ niż $n$, czyli $y$ nie jest gorszym dopasowaniem niż $z$, więc wybór "pierwszy pasujący" odpowiada zasadzie najlepszego dopasowania. $\Box$

### 6.
![](https://i.imgur.com/XpEVbPR.png)

Stan stabilny to taki w którym kolejne wysyłania wektorów nie powodują aktualizacji.
Algorytm ten polega na okresowym powiadamianiu sąsiadów o całej swojej tablicy przekazywania, czyli w każdym korku tablica routingu będzie aktualizowana o nowe wpisy. Początkowo każdy zna tylko własnych sąsiadów.
W tabelce liczbą będziemy oznaczać "odległość", a puste komórki będą w tym kroku jeszcze nieosiągalne.

* Stan początkowy
    | Z:   | A   | B   | C   | D   | E   | F   |
    |:---- | --- |:--- |:--- | --- |:--- |:--- |
    | do A | -   | 1   |     |     |     |     |
    | do B | 1   | -   | 1   |     |     |     |
    | do C |     | 1   | -   |     | 1   | 1   |
    | do D |     |     |     | -   | 1   |     |
    | do E |     |     | 1   | 1   | -   | 1   |
    | do F |     |     | 1   |     | 1   | -   |
    | do S | 1   | 1   |     |     |     |     |

* Krok 1
    | Z:   | A        | B        | C        | D        | E        | F        |
    |:---- | -------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A | -        | 1        | 2(via B) |          |          |          |
    | do B | 1        | -        | 1        |          | 2(via C) | 2(via C) |
    | do C | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D |          |          | 2(via E) | -        | 1        | 2(via E) |
    | do E |          | 2(via C) | 1        | 1        | -        | 1        |
    | do F |          | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S | 1        | 1        | 2(via B) |          |          |          |

* Krok 2
    | Z:   | A        | B        | C        | D        | E        | F        |
    |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A | -        | 1        | 2(via B) |          | 3(via C) | 3(via C) |
    | do B | 1        | -        | 1        |          | 2(via C) | 2(via C) |
    | do C | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D |          | 3(via C) | 2(via E) | -        | 1        | 2(via E) |
    | do E | 3(via B) | 2(via C) | 1        | 1        | -        | 1        |
    | do F | 3(via B) | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S | 1        | 1        | 2(via B) |          | 3(via C) | 3(via C) |

* Krok 3
    | Z:   | A        | B        | C        | D        | E        | F        |
    |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A | -        | 1        | 2(via B) | 4(via E) | 3(via C) | 3(via C) |
    | do B | 1        | -        | 1        | 3(via E) | 2(via C) | 2(via C) |
    | do C | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D | 4(via B) | 3(via C) | 2(via E) | -        | 1        | 2(via E) |
    | do E | 3(via B) | 2(via C) | 1        | 1        | -        | 1        |
    | do F | 3(via B) | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S | 1        | 1        | 2(via B) | 4(via E) | 3(via C) | 3(via C) |


Jak widać w 3. kroku osiągniemy stan stabilny - wszystkie routery w sieci będą znały drogę do pozostałych, a wyznaczone ścieżki są najkrótsze.

### 7.
![](https://i.imgur.com/mPXb4UB.png)

* Stan początkowy - tablica z zadania 6.
    | Z:    | A        | B        | C        | D        | E        | F        |
    |:----- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A  | -        | 1        | 2(via B) | 4(via E) | 3(via C) | 3(via C) |
    | do B  | 1        | -        | 1        | 3(via E) | 2(via C) | 2(via C) |
    | do C  | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D  | 4(via B) | 3(via C) | 2(via E) | -        | 1        | 2(via E) |
    | do E  | 3(via B) | 2(via C) | 1        | 1        | -        | 1        |
    | do F  | 3(via B) | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S  | 1        | 1        | 2(via B) | 4(via E) | 3(via C) | 3(via C) |

* Krok 1
    | Z:   | A        | B        | C        | D        | E        | F        |
    |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A | -        | 1        | 2(via B) | 1        | 3(via C) | 3(via C) |
    | do B | 1        | -        | 1        | 3(via E) | 2(via C) | 2(via C) |
    | do C | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D | 1        | 3(via C) | 2(via E) | -        | 1        | 2(via E) |
    | do E | 3(via B) | 2(via C) | 1        | 1        | -        | 1        |
    | do F | 3(via B) | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S | 1        | 1        | 2(via B) | 4(via E) | 3(via C) | 3(via C) |
    Tutaj A i D dowiadują się o połączeniu między sobą.

* Krok 2
    | Z:   | A        | B        | C        | D        | E        | F        |
    |:---- |:-------- |:-------- |:-------- |:-------- | -------- |:-------- |
    | do A | -        | 1        | 2(via B) | 1        | 2(via D) | 3(via C) |
    | do B | 1        | -        | 1        | 2(via A) | 2(via C) | 2(via C) |
    | do C | 2(via B) | 1        | -        | 2(via E) | 1        | 1        |
    | do D | 1        | 2(via A) | 2(via E) | -        | 1        | 2(via E) |
    | do E | 2(via D) | 2(via C) | 1        | 1        | -        | 1        |
    | do F | 3(via B) | 2(via C) | 1        | 2(via E) | 1        | -        |
    | do S | 1        | 1        | 2(via B) | 2(via A) | 3(via C) | 3(via C) |
    Stan stabilny, wyszystkie ścieżki są najkrótsze.

### 8.
![](https://i.imgur.com/fCuJOum.png)

Na początku zróbmy tablice routingu dla działającego połączenia


* Krok 1:
    | X    | A   | B   | C   | D   | E   |
    | ---- | --- | --- |:--- |:--- |:--- |
    | do A | -   | 1   | 1   |     |     |
    | do B | 1   | -   |     | 1   |     |
    | do C | 1   |     | -   | 1   |     |
    | do D |     | 1   | 1   | -   | 1   |
    | do E |     |     |     | 1   | -   |

* Krok 2:
    | X    | A        | B        | C        | D        | E        |
    | ---- | -------- | -------- |:-------- |:-------- |:-------- |
    | do A | -        | 1        | 1        | 2(via B) |          |
    | do B | 1        | -        | 2(via D) | 1        | 2(via D) |
    | do C | 1        | 2(via A) | -        | 1        | 2(via D) |
    | do D | 2(via B) | 1        | 1        | -        | 1        |
    | do E |          | 2(via D) | 2(via D) | 1        | -        |

* Krok 3:
    | X    | A        | B        | C        | D        | E        |
    | ---- |:-------- | -------- |:-------- |:-------- |:-------- |
    | do A | -        | 1        | 1        | 2(via B) | 3(via D) |
    | do B | 1        | -        | 2(via D) | 1        | 2(via D) |
    | do C | 1        | 2(via D) | -        | 1        | 2(via D) |
    | do D | 2(via B) | 1        | 1        | -        | 1        |
    | do E | 3(via B) | 2(via D) | 2(via D) | 1        | -        |

Teraz gdy mamy gotową tabele możemy przerwać połączenie między D i E

* Stan początkowy:
    | X    | A        | B        | C        | D        | E        |
    | ---- |:-------- | -------- |:-------- |:-------- |:-------- |
    | do A | -        | 1        | 1        | 2(via B) | 3(via D) |
    | do B | 1        | -        | 2(via D) | 1        | 2(via D) |
    | do C | 1        | 2(via D) | -        | 1        | 2(via D) |
    | do D | 2(via B) | 1        | 1        | -        | 1        |
    | do E | 3(via B) | 2(via D) | 2(via D) | 1        | -        |

* Krok 1: E zostaję odpięte od D
    | X    | A        | B        | C        | D        |
    |:---- |:-------- | -------- |:-------- |:-------- |
    | do A | -        | 1        | 1        | 2(via B) |
    | do B | 1        | -        | 2(via D) | 1        |
    | do C | 1        | 2(via D) | -        | 1        |
    | do D | 2(via B) | 1        | 1        | -        |
    | do E | 3(via B) | 2(via D) | 2(via D) | ==DIS==  |

* Krok 2: D informuje C i B, ale na razie komunikat dociera do C, że nie łączy się z E. C wysyła komunikat do A, że nie łączy się z E.
    | X    | A        | B        | C        | D        |
    |:---- |:-------- | -------- |:-------- |:-------- |
    | do A | -        | 1        | 1        | 2(via B) |
    | do B | 1        | -        | 2(via D) | 1        |
    | do C | 1        | 2(via D) | -        | 1        |
    | do D | 2(via B) | 1        | 1        | -        |
    | do E | 3(via B) | 2(via D) | ==DIS==  | DIS      |

* Krok 3: A informuje C, że droga do E porzebiega przez B, a później do B dobiega informacja, że D nie ma połączenia do E. B wysyła komunikat do A, że nie ma połączenia.
    | X    | A        | B        | C            | D        |
    |:---- |:-------- |:-------- |:------------ |:-------- |
    | do A | -        | 1        | 1            | 2(via B) |
    | do B | 1        | -        | 2(via D)     | 1        |
    | do C | 1        | 2(via D) | -            | 1        |
    | do D | 2(via B) | 1        | 1            | -        |
    | do E | 3(via B) | ==DIS==  | ==4(via A)== | DIS      |

* Krok 4: A otrzymuje komunikat że B i C nie ma połączenia do E. C informuje D, że zna drogę do E przez A.
    | X    | A        | B        | C        | D            |
    |:---- |:-------- |:-------- |:-------- |:------------ |
    | do A | -        | 1        | 1        | 2(via B)     |
    | do B | 1        | -        | 2(via D) | 1            |
    | do C | 1        | 2(via D) | -        | 1            |
    | do D | 2(via B) | 1        | 1        | -            |
    | do E | ==DIS==  | DIS      | 4(via A) | ==5(via C)== |

* Krok 5: D informuje B, że zna drogę do E przez C. A wysyła informacje do C, że nie ma połączenia do E.
    | X    | A        | B            | C        | D        |
    |:---- |:-------- |:------------ |:-------- |:-------- |
    | do A | -        | 1            | 1        | 2(via B) |
    | do B | 1        | -            | 2(via D) | 1        |
    | do C | 1        | 2(via D)     | -        | 1        |
    | do D | 2(via B) | 1            | 1        | -        |
    | do E | DIS      | ==6(via D)== | 4(via A) | 5(via C) |

* Krok 6: B informuje A, że zna droge do E przez D. Otrzymuje tak poison reverse.
    | X    | A            | B        | C        | D        |
    |:---- |:------------ |:-------- |:-------- |:-------- |
    | do A | -            | 1        | 1        | 2(via B) |
    | do B | 1            | -        | 2(via D) | 1        |
    | do C | 1            | 2(via D) | -        | 1        |
    | do D | 2(via B)     | 1        | 1        | -        |
    | do E | ==7(via B)== | 6(via D) | 4(via A) | 5(via C) |

### 9.
![](https://i.imgur.com/ITglfs0.png)


```graphviz
graph finite_state_machine {
    rankdir=LR;
    node [shape = circle];
    A -- B;
    B -- C;
    C -- A;
    C -- D;
} 
```

* Stan początkowy:
    | X    | A        | B        | C   | D        |
    | ---- |:-------- |:-------- |:--- |:-------- |
    | do A | -        | 1        | 1   | 2(via C) |
    | do B | 1        | -        | 1   | 2(via C) |
    | do C | 1        | 1        | -   | 1        |
    | do D | 2(via C) | 2(via C) | 1   | -        |


* Krok 1: Uszkodzenie połączenia między C i D.
    | X    | A        | B        | C       | D        |
    | ---- |:-------- |:-------- |:------- |:-------- |
    | do A | -        | 1        | 1       | 2(via C) |
    | do B | 1        | -        | 1       | 2(via C) |
    | do C | 1        | 1        | -       | ==DIS==  |
    | do D | 2(via C) | 2(via C) | ==DIS== | -        |

* Krok 2: C wysyła informację do A i B, ale narazie indormacja dochodzi tylko do A, a B wysyła informacje do A, że zna droge do D przez C.
    | X    | A       | B        | C   | D       |
    | ---- |:------- |:-------- |:--- |:------- |
    | do A | -       | 1        | 1   | ==DIS== |
    | do B | 1       | -        | 1   | ==DIS== |
    | do C | 1       | 1        | -   | DIS     |
    | do D | ==DIS== | 2(via C) | DIS | -       |
* Krok 3: Do B dochodzi informacja, że połączenie między C i D zostało przerwane, a A wysyła informacje do C, że zna drogę do D przez B.
    | X    | A            | B       | C   | D   |
    | ---- |:------------ |:------- |:--- |:--- |
    | do A | -            | 1       | 1   | DIS |
    | do B | 1            | -       | 1   | DIS |
    | do C | 1            | 1       | -   | DIS |
    | do D | ==3(via B)== | ==DIS== | DIS | -   |
* Krok 4: B wysyła informacje do A, że połączenie między C i D zostało przerwane, a C wysyła informacje do B, że zna drogę do D przez A.
    | X    | A       | B   | C            | D   |
    | ---- |:------- |:--- |:------------ |:--- |
    | do A | -       | 1   | 1            | DIS |
    | do B | 1       | -   | 1            | DIS |
    | do C | 1       | 1   | -            | DIS |
    | do D | ==DIS== | DIS | ==4(via A)== | -   |
* Krok 5: C wysyła informacje do B, że połączenie między C i D zostało przerwane, a B wysyła informacje do A, że zna drogę do D przez C.
    | X    | A   | B            | C       | D   |
    | ---- |:--- |:------------ |:------- |:--- |
    | do A | -   | 1            | 1       | DIS |
    | do B | 1   | -            | 1       | DIS |
    | do C | 1   | 1            | -       | DIS |
    | do D | DIS | ==5(via C)== | ==DIS== | -   |
Dalsze kroki zapętlają się i dostajemy cykl.

### 10.
![](https://i.imgur.com/52RcSpp.png)

```graphviz
digraph finite_state_machine {
    rankdir=LR;
    node [shape = circle];
    a1 -> x0;
    a1 -> y0;
    x0 -> a2;
    y0 -> a2;
    a2 -> x1;
    a2 -> y1;
    "..."    [ style = dashed    ];
    x1 -> "..." [ style=dashed ];
    y1 -> "..."  [ style=dashed ];
} 
```

Router $a0$ przesyła komunikat do routertów  $x0$ i $y0$ (1 jednoskta czasu). Router $x0$ i $y0$ przesyłają do $a1$, kóry otrzyma 2 komunikaty. Router $a1$ ma do przekazania dwa komunikaty, każdy do dwóch następnych routerów (zajmuje mu to 2 jednoski czsu). Router $a2$ ma do przekazania 4 komunikaty (4 jednoski czasu) itd...

Poprawione 10 (chyba)

Weźmy graf (sieć, wierzchołek-router) taki że wierzchołek $A_0$ ma dwie krawędzie, do $X_0,Y_0$. $X_0,Y_0$ mają po jednej krawędzi do wierzchołka $A_1$. $A_1$ ma dwie krawędzie, do $X_1,Y_1$. $X_1,Y_1$ mają po jednej krawędzi do wierzchołka $A_2$. $A_2$ ma dwie krawędzie, do $X_2,Y_2$. I tak dalej do $A_{\lfloor{n/3}\rfloor}$



Router $A_0$ przesyła komunikat do routerów  $X_0$ i $Y_0$ w jednej jednostce czasu. Routery $X_0$ i $Y_0$ przesyłają komunikat do $A_1$ w jednej jednostce, do którego dojdą dwa komunikaty. Router $A_1$ ma teraz do przekazania dwa komunikaty, każdy do dwóch następnych routerów. Zajmie mu to dwie jednoski czsu. Po przejściu przez $X_1, Y_1$ router $A_2$ będzie miał do przekazania cztery komunikaty routerom $X_2, Y_2$ czyli zajmie mu to cztery jednostki czasu, itd. do $A_{\lfloor{n/3}\rfloor}$. 
W sumie będziemy mieć $2*\sum_{i=0}^{\lfloor{n/3}\rfloor} 2^i=2^{1+\lfloor{n/3}\rfloor}-1$ jednostek czasu, a $1+\lfloor{n/3}\rfloor\in \Omega(n)$




## Ćwiczenia 2

### 1.
![](https://i.imgur.com/9kguNdW.png)


droga ($s$) = $2,5$km = $2500$m
prędkość ($V$) = $10^8 \frac{m}{s}$
bandwidth ($b$) = $10$Mb = $10^7$bitów
opóźnienie ($d$) = $\frac{s}{V}$ = $2,5*10^{-5}$s

Długość ramki = $b*d*2$ = $10^7*2,5*10^{-5}*2$ = $500$bitów


### 2.
![](https://i.imgur.com/7tIeabH.png)

Protokół ALOHA wysyła bez uprzedniego sprawdzania czy ktoś nadaje i sprawdzania czy będzie kolizja (np. stacje naziemne transmitujące do satelity + stacje się nawzajem nie widzą). Czas dzielimy na rundy(sloty). Założenie jest takie, że mamy dużo wysyłających nadajacych rzadko + pakiety mają takie same długości. Wysyłamy pakiet/slot czasowy z prawdopodobieństwem p.

1. Załóżmy, że uda się nam wysłać ramkę.
2. Załóżmy, że innym n-1 uczestnikom nie uda sie wysłać ramki.
3. Takich przypadków, że jednemu udało się wysłać, a reszenie nie jest $n$.

Skoro każdy wysyła z prawdopodobieństwiem $p$, to szansa, że jeden wyśle a pozostałe nie wyślą jest równa:
* $P(p,n)=n*p*(1-p)^{n-1}$

Teraz liczymy pochodną po $p$ i otrzymujemy:

$P'(p)=n(1-p)^{n-1}-(n-1)*n*(1-p)^{n-2}*p$
$P'(p)=-\frac{n*(1-p)^n(n*p-1)}{(p-1)^2}$
Miejsca zerowe: $p=\frac{1}{n}$

Jeśli miejsce zerowe jest w $\frac{1}{n}$ to jest tam ekstemum.

Teraz liczymy drugą pochodną:

$P''(p)=\frac{n^2*(1-p)^{n-1}*(n*p-1)}{(p-1)^2}+\frac{2*n*(1-p)^n*(n*p-1)}{(p-1)^3}-\frac{n^2*(1-p)^n}{(p-1)^2}$
$P''(p)=-\frac{(n-1)*n*(1-p)^n*(n*p-2)}{(p-1)^3}$
Miejsca zerowe: $p=\frac{2}{n}$

* Podstawiając $1/n$ do drugiej pochodnej otrzymujemy coś ujemnego -> maksimum.

* $lim_{n \to \infty}[P(\frac{1}{n}, n) = (1-\frac{1}{n})^{n-1} = (1-\frac{1}{n})^n * (1-\frac{1}{n})^{-1} ]= \frac{1}{e} * 1 = \frac{1}{e}$

### 3.
![](https://i.imgur.com/RkAGkcq.png)

A i B muszą sobie wysłać nawzajem jakieś pakiety w tym samym czasie. Próbują zrobić to w tym samym czasie następuje kolizja. Oba nadajniki czekają więc losową ilość czasu między na przedziale [0, 2]. Zakładamy, że A losuje szybsze wysłanie więc wysyła pakiet pierwszy, a B notuje kolizje. Teraz gdy A ma dalej pakiety do wysłania i B próbuje coś do niego wysłać więc znowu oba notują kolizje. Z racji tego że to druga nieudana próba dla B, B losuje na przedziale [0,4], a A losuje na przedziale [0,2], więc szansa na to że wygra znowu A jest większa. Następnym razem B znowu przegrywa i teraz losuje na [0,8]. Dzieje się tak, aż B przegra wszystkie próby (16 przegranych kolizji z rzędu) i wtedy B wycofuje się na dłuższy czas lub na przykład odrzuca pakiet. Prawdopodobieństwo takej sytuacje juest dość duże, bo po 4-5 przegranych próbach szansa na przejęcie kanau przez B jest bardzo niska. Wtedy mówimy że A przejeło kanał.



### 4.
![](https://i.imgur.com/h8w69sA.png)

* wiadomość $m=1010 \iff M(x)=x^3+x$

:::    info
$B(x) = x^r * M(x) + S(x)$ - gdzie s wybieramy tak, żeby B(x) był podzielny przez G(x)
:::

1. 
$G(x) = x^2 + x + 1 \iff g=111_2$ deg=2
Dzielimy $x^r*M(x)=x^5+x^3 = 101000_2$ przez G(x)
$x^3+x^2+x$ reszta $S(x)=x$
Suma kontrolna powinna mieć $deg(G)=2$ bity, czyli $s = 10$

2.
$G(x)=x^7+1 \iff g=10000001_2$, deg=7
Dzielimy $x^r*M(x)=x^{10}x^8 = 10100000000_2$ przez G(x)
$x^{3}+x$ reszta $S(x)=x^3+x$
Suma kontrolna powinna mieć $deg(G)=7$ bity, czyli $s = 0001010$

### 5.
![](https://i.imgur.com/9BctmWU.png)

TEZA: Jeżeli liczba zapalonych bitów w słowie maszynowym jest parzysta dzielenie przez $x+1$ da resztę 0, a w przeciwnym przypadku 1.

Musimy pokazać, że $x+1$ dzieli bez reszty wszystkie wielomiany o parzystej liczbie składników.

Każdy wielomian w postaci $x^n-x^k \equiv x^n+x^k$, więc w szczególności $x-1 \equiv x+1$.
Dla $m = 0 \to s=0$ i $m = 1 \to s=1$ więc oczywiste.

**Założenie indukcyjne:**
Załóżmy, że $m=k$, gdzie $k$ całkowite:
$x^k-1=(x-1)*P(x)$, gdzie P to wielomian.

Weźmy teraz $m=k+1$:
$x^{k+1}-1=(x-1)*Q(x)$, gdzie $Q$ to wielomian.

$x^{k+1}-1= (x-1)*x^k+x^k-1$
$x^{k+1}-1= (x-1)*x^k+(x-1)*P(x)$(z zał indukcyjnego)
$x^{k+1}-1= (x-1)*(x^k+P(x))$
$x^{k+1}-1= (x-1)*(x^k-x-1)$
$x^{k+1}-1= (x-1)*(x^k*(x-1)+x^k-x-1)$
$x^{k+1}-1= (x-1)*(x^{k+1}-x^k+x^k-x-1)$
$x^{k+1}-1= (x-1)*Q(x)$

### 7.
Z wykładu wiemy, że wystarczy pokazać, że odległość jest większa bądź równa 3.
Czyli chcemy pokazać że nie występuje odległość 1 i 2.

Macierz generująca $G$ kodu (7,4) i jego macierz kontroli parzystości $H$, a $x$, $y$ to kody z $G$. Wtedy $x-y$ należy do $H$ ponieważ $H$ jest kodem liniowym.

Teraz sprawdzamy czy możliwe jest:
1.$dist(x,y)=1$ wtedy wszystkie kolumny w $H$ są niezerowe, ale jeśli $x-y$ jest kodem (7,4), to $G(x-y)=0$, co jest sprzecznością.
2.$dist(x,y)=2$, wtedy $G(x-y)=0$ a tak jest tylko w wypadku kuedy 2 kolumny są liniowo zależne, a w kodzie Hamminga nie ma liniowej zależności.

### 8.