Ćwiczenia 2 - HackMD

###### tags: `Sieci Komputerowe` # Ćwiczenia 2 ## Zadanie 1 :::info W kablu koncentrycznym używanym w standardowym $10$-Mbitowym Ethernecie (Można założyć, że $10\space Mbit = 10^7\space bit$) sygnał rozchodzi się z prędkością $10^8\space m/s$. Standard ustala, że maksymalna odległość między dwoma komputerami może wynosić co najwyżej $2,5 km$. Oblicz, jaka jest minimalna długość ramki.(Wraz z nagłówkami, w rzeczywistości sygnał rozchodzi się ok. $2$ razy szybciej, ale opóźnienia występują nie tylko w kablu.). ::: Wiemy, że: 1. Czas transmisji pakietu $T_t\geq 2T_p$, gdzie $T_p$ jest czasem propagacji 2. Czas transmisji wyraża się wzorem $T_t=\frac LR$ Gdzie $L$ jest rozmiarem pakietu, a $R$ przepustowością łącza 3. $T_p=\frac sv$ gdzie $s$ to odległość między dwoma komputerami, a $v$ prędkością sygnału Po podstawieniach: $\frac LR \geq \frac{2s}{v}$ / $*R$ $L \geq \frac{2sR}{v}=\frac{2*2500m*10^7\space bit/s}{10^8\space m/s}=\frac{5000*10^7}{10^8}\space bit=\frac{500*10^8\space bit}{10^8}\space bit=500\space bit$ Czyli minimalna długość ramki wraz z nagłówkami wynosi $500$ bitów. ## Zadanie 2 X :::info Rozważmy rundowy protokół Aloha we współdzielonym kanale, tj. w każdej rundzie każdy z n uczestników usiłuje wysłać ramkę z prawdopodobieństwem $p$. Jakie jest prawdopodobieństwo $P(p, n)$, że jednej stacji uda się nadać (tj. że nie wystąpi kolizja)? Pokaż, że $P(p, n)$ jest maksymalizowane dla $p = 1/n$. Ile wynosi $\displaystyle\lim_{n→∞} P(1/n, n)$? ::: ## Zadanie 3 X :::info Wyszukaj w sieci informację na temat zjawiska Ethernet capture i wytłumacz w jaki sposób ono powstaje. (Tym mianem określa się sytuację, w której jedna ze stacji nadaje znacznie częściej, choć wszystkie stacje używają algorytmu CSMA/CD.) ::: ## Zadanie 4 :::info Jaka suma kontrolna $CRC$ zostanie dołączona do wiadomości $1010$ przy założeniu że $CRC$ używa wielomianu $x^2 + x + 1$? A jaka jeśli używa wielomianu $x^7 + 1$? ::: Musimy znaleźć taki wielomian $S(x)$, że $G(x)\space |\space x^r*M(x)+S(x)$ Wiemy, że $S(x)=R(x)$, gdzie $x^r*M(x) : G(x)=Q(x)*G(x)+R(x)$ ### a) :::info $x^2 + x + 1$ ::: $G(x)=x^2+x+1$ $r=st(G)=2$ Skoro $m = 1010$ to $M(x)=x^3+x$ $x^r*M(x) : G(x)=x^2*(x^3+x):(x^2+x+1)=\frac{x^5+x^3}{x^2+x+1}=\frac{x^5+x^4+x^3-x^4}{x^2+x+1}=\frac{x^3(x^2+x+1)}{x^2+x+1} + \frac{-x^4}{x^2+x+1}=\\=x^3+\frac{-(x^4+x^3+x^2)+x^3+x^2}{x^2+x+1}=x^3+\frac{-x^2(x^2+x+1)}{x^2+x+1} + \frac{x^3+x^2}{x^2+x+1}=x^3-x^2 + \frac{x^3+x^2}{x^2+x+1}=\\=x^3-x^2 + \frac{x^3+x^2+x-x}{x^2+x+1}=x^3-x^2 + \frac{x(x^2+x+1)}{x^2+x+1} + \frac{-x}{x^2+x+1}=x^3-x^2 + x + \frac{-x}{x^2+x+1}=\\=x^3-x^2 + x + R(x)$ Gdzie $R(x)=\frac{-x}{x^2+x+1}$, czyli $S(x)=-x=10$ ### b) :::info $x^7 + 1$ ::: $G(x)=x^7+1$ $r=st(G)=7$ Skoro $m = 1010$ to $M(x)=x^3+x$ $x^r*M(x) : G(x)=x^7*(x^3+x):(x^7+1)=\frac{x^{10}+x^8}{x^7+1}=\frac{x^3(x^7+1)+x^8-x^3}{x^8+1}=x^3+\frac{x^8-x^3}{x^7+1}=\\=x^3+\frac{x(x^7+1)-x^3-x}{x^7+1}=x^3+x+\frac{-x^3-x}{x^7+1}=x^3+x+R(x)$ Gdzie $R(x)=\frac{-x^3-x}{x^7+1}$, czyli $S(x)=-x^3-x=0001010$ ## Zadanie 5 :::info Pokaż, że $CRC-1$, czyli $1-bitowa$ suma obliczana na podstawie wielomianu $G (x) = x + 1$, działa identycznie jak bit parzystości. ::: $G(x) = x+1$ $r=st(G)=1$ $M(x) = m$ $x^r*M(x) : G(x)=x*M(x):(x+1)$ Z twierdzenia Bézouta wiemy, że jeśli $(x+1)\space |\space x*M(x)$, to $(-1)*M(-1)=0$ Czyli w arytmetyce $F_2$: $\space S(x) = 0 \leftrightarrow M(1)=0$ $M(1)=\displaystyle\sum_{i=1}^{St(M)} m_i$, gdzie $m_i$ jest $i$-tym bitem liczby binarnej $m$ W arytmetyce $F_2$ suma ta jest równa $1$ jeżeli liczba zapalonych bitów jest nieparzysta, a równa $0$ jeżeli ta suma jest parzysta. Czyli ta 1-bitowa suma działa identycznie jak bit parzystości. $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare$ ## Zadanie 6 X :::info Załóżmy, że wielomian $G(x)$ stopnia n stosowany w $CRC$ zawiera składnik $x^0$. Pokaż, że jeśli wybierzemy dowolny odcinek długości $n$ z wiadomości i dowolnie go zmodyfikujemy (zmienimy dowoln niezerową liczbę bitów w nim), to zostanie to wykryte. Czy taka własność zachodzi, jeśli $G(x)$ nie zawiera składnika równego $x^0$? ::: ## Zadanie 7 X :::info Pokaż, że kodowanie $Hamming(7,4)$ umożliwia skorygowanie jednego przekłamanego bitu. Wskazówka: wystarczy pokazać, że odległość Hamminga między dwoma kodami wynosi co najmniej $3$. ::: ## Zadanie 8 X :::info Pokaż, że suma $CRC$ stosująca wielomian $G (x) = x^3 + x + 1$ wykryje wszystkie podwójne błędy (zmianę wartości dwóch bitów), które są oddalone od siebie o nie więcej niż $6$ bitów (tj. pomiędzy dwoma zmienianymi bitami jest nie więcej niż $5$ innych bitów) ::: ## Zadanie 9 X :::info Załóżmy, że wyliczamy sumę $CRC$ dla $4$-bitowej wiadomości używając wielomianu $G (x) = x^3 + x + 1$; wtedy wiadomość wraz z sumą ma długość $7$ bitów. Załóżmy, że co najwyżej jeden z tych $7$ bitów został przekłamany. Pokaż, jak odbiorca takiego komunikatu może wykryć i skorygować takie przekłamanie. ::: ## Zadanie 10 X :::info Dana jest deterministyczna funkcja skrótu $h$ zwracająca na podstawie tekstu liczbę $m$-bitową. Losujemy $2^{m/2}$ tekstów i obliczamy na nich funkcję $h$. Zakładamy tutaj, że przy takim losowaniu tekstu $x$, $h(x)$ jest losową (wybraną z rozkładem jednostajnym) liczbą $m$-bitową. Pokaż, że prawdopodobieństwo, że wsród wylosowanych tekstów istnieją dwa o takiej samej wartości funkcji $h$ jest $Ω(1)$. :::