Számítógépes Hálózatok Lukovszki Tamás Gyak. helye: Adatbázis labor http://people.inf.elte.hu/lukovszki/Courses/07NWI/ (tavalyi) http://people.inf.elte.hu/lukovszki/Courses/0708NWI/ http://people.inf.elte.hu/lukovszki/Courses/07NWI/ETC/ belépés: halozatok / @dipl.elte Laki Sándor http://lakis.web.elte.hu/szh.html
1. gyakorlat (2007-09-18) Csoportosítsuk a fogalmakat Felhasználói réteg: pl: Email, http Szállítói réteg feladata: pl: TCP, port cím Hálózati réteg: pl: Csomagtovábbítás, Internet Protocol, IP cím Adatkapcsolati réteg: pl: Ethernet, token-ring, wi-fi Fizikai réteg: pl: optikai kábel, koax kábel
2. Melyik modell jobb: ISO/OSI, vagy TCP/IP? ISO/OSI: pro: - az alsó rétegek feladatait is pontosan definiálja. - szinkronizáció kontra: - hibajavítással nem foglalkozik TCP/IP: - adatok burkolása (fejlécként hozzáadja)?
3. Valszám Ha a valószínűsége, hogy egy frame hibás: p, mennyi az átviteli kísérletek számának várható értéke egy frame sikeres küldéséhez? Ha 1/2 a valószínűsége, akkor várhatóan 2x kell küldeni
Ha 2/3 a valószínűsége, hogy elveszik az adat, akkor várhatóan 3x kell küldeni. ... P[sikertelen] := p X: küldési kísérletek száma, amíg sikeresen átvisszük P [X=1] = 1-p P [X=2] = (1-p)p 2 P [X=3] = (1-p)p ... n-1 P[X=n] = (1-p)p E[X]= Szumn=1 végtelenig ... (janinak le van írva) .. = 1/(1-p)
4. Bernáthegyi sávszélessége 700 MB-os CD, 18 km/h-val Milyen távolságig nagyobb a kuya adatrátája, mint egy 2,5 Mbps DSL? CD-n levő adat: 700 MB = 5600 Mbit 2,5 Mbps-kel letölteni 700 MB-ot: 5600 Mbit/2,5Mbps = 2240 sec Meddig jut el ennyi idő alatt a kutya? 18 km/h / 3,6 = 5 m/s 5 m/s * 2240 sec = 11200 m
3. gyakorlat (2007-10-02) Feladatsor: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy03.pdf
1. Bitsorozat ábrázolása Kódolandó: 011001 választunk egy kódolást (1-est, 0-t hogyan kódoljuk?) 0: alacsony feszültség, 1: magas feszültség Így néz ki: (grafikon): alacsony, magas, magas, alacsony, alacsony, magas Ebből még nem lehet érzékelni, hogy hol következik a következő bit (2 azonos bit esetén pl.) Amplitúdó módosítással: 0: frekvencia 1, 1: frekvencia 2 Így néz ki: 1 sin, 2 sin, 2 sin, 1 sin, 1 sin, 2 sin Fázis eltolással (Phase Shift Key): 0: 0-val toljuk el
1: pi/2-vel toljuk el Így néz ki: sin, cos, cos, sin, sin, cos (éles vágások köztük) Difference Phase Shift Key sin, cos, -sin, -sin, -sin, -cos Quadrature Phase Shift Key: ilyen bitet akarunk: ennyivel toljuk el a sin-t: 00: pi / 4 01: 3pi / 4 10: 5pi / 4 11: 7pi / 4 011001 felosztva ilyenekre: 01 | 10 | 01 ==> sin görbék, amik a megfelelő távra vannak eltolva.
2. Kábelhossz, elnyelődés Elnyelődés: alfa = Ps / Pr alfa = 1 / (1 - 0,065) = 1,07 0,29 dB Ennyivel kell, hogy megérkezzen: x Ps / 1000 = (1/alfa) * Ps log10 1/1000 = x * log10 1/alfa -3 = -x * log10 alfa = x * 0,029 102,3 = x - ??? számológéppel más jön ki.. Vagyis 102,3 km lehet max a kábel, ahhoz hogy 1/1000 jelszinttel érkezzen meg a jel.
3. Felső korlát az adatrátára, Shannon tétel segítségével H * log2 (1 + S/N) H: sávszélesség S: jel erősség N: zaj erősség a) 1. sodort rez erpar Cat-5 kabelre 100MHz-ig, S/N = 20 dB = 100 100 * log2 (1+100) 100 * log2 101 = 100 * 6,7 = 670000000 b/s b) itt nem figyeltünk.. c) infravörösben: 109 / 21 nem tudom mi..
4. gyakorlat (2007-10-09) Előadás: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/nwI04s4.pdf Gyak. feladatok: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy04.pdf
1. byte-hiba valószínűsége p: byte hiba valószínűsége m db frame n: frame-ek össz hossza => átlagosan n/m hosszúak 1) byte-hibák várható értéke: p * n 2) hibás frame-határoló flagek száma: p * m 3) ESC karakter kell: flag és ESC elé, hogy sima adatként vigyük át --> 256+2 byte-tal visszük át őket n-m hasznos adatbyte eredeti adatbyte-ok száma várhatóan: (n-m) * 256/258 flag gyakoriság: 1/256 --> eredeti adatban a flagbyte-ok száma: (n-m) * 256/258 * 1/256 hibásan értelmezett: p * (n-m) * 1/258 4) Csak flagbyte-okat viszek át (flag, flag, flag) --> mindegyik karakter 2 byte-nyi (ESC, flag, ESC, flag...) Berakjuk őket keretekbe (normál flag-gel kezdünk, aztán jönnek ezek az ESC-elt flag-ek): (n-m) / 2 --> E = p * (n-m) / 2
2. Hamming távolság Minimális távolság 2 kód között Ha Hamming táv: d, akkor d-1 hiba felismerésére alkalmas Ha d hibát akarunk észrevenni: ... Ha d hibát akarunk javítani: ?2-d? hosszúság kell paritás bittel az 1 bites hibát észrevesszük a hibát. Gond akkor van, ha 2 bit hibásodik meg, és a paritás bit így nem jelez, vagy pont a paritás bit hibásodik meg (távolság) delta = 2/9. 9 9 biten 2 kódszó van (512) (paritás bit rátája): R = 8/9 1) n alatt az i 2) legfeljebb 1 olyan kódszó van, ami nincs messzebb (k-1) / 2 - től T.fel: létezik u,v eleme C: d(x,u) <= (k-1)/2 és d(x,v) <= (k-1) / 2
ekkor d(u,v) <= d(u,x) + d(x,v) <= k-1, ami ellentmondás 3) ...
5. gyakorlat (2007-10-16) Gyak anyaga: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy05.pdf
CRC számolás n = 0101.1011.1101.0010 inputhoz 4 2 x + x + 1 polinom ==> hatványokat nézzük, hogy van-e tag a 4.-en, 3.-on, négyzeten, elsőn, és konstans: (van, nincs, van, nincs, van) ==> 10101. Ezzel fogjuk osztani a polinomot kiegészítve pár nullával: 1) 4-bit CRC-kontroll összeg kiszámolása: legnagyobb kitevő 4 ==> 4 db 0-val kell kiegészíteni az eredeti inputot. Polinom osztás, csak a maradékra vagyunk kíváncsiak: 0101.1011.1101.0010.0000 : 10101 -101 01 000 1111 1 -1010 1 0101 01 -101 01 000 0001 0010 -1 0101 0 0111 00 -101 01 010 010 .. mint ahogy a megoldásban is csináltuk.
Paritás technika Bitmátrix (k*l -es): 10110|0 00101|1 00010|0 11101|1 10011
Csomagátvitel szimulálás Szimplex protokollal.. inkább megyünk Andihoz
6. gyakorlat (2007-10-24) http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy06.pdf http://lakis.web.elte.hu/szh.html Aloha: leginkább szateliteknél használják manapság. Ha csomagot küldök, akkor nem szabad, hogy más adó is használja a közvetítő közeget amíg utazik az adat. Sebezhetőség: 2t (csomag hosszának 2*ese) Slotted aloha: időszeletekre osztjuk. Csomagot csak időszelet határban lehet indítani. Sebezhetőség: t
Átvitel számolás a terhelés függvényében Mivel Poisson eloszlás szerint jönnek a csomagok: S(G) = G*P 0 t: csomagidő s: slotidő t = r*s Ha r = 3: 1 csomag elküldése 3 slotnyi időbe telik. A másik legalább 3 slottal előtte kell, hogy elkezdje a küldést. Ha akár eggyel is később küld, kollózió lesz (5 sloton keresztül) ==> sebezhetőségi idő: (2r - 1). Csomagidőt ebből úgy kapok, hogy osztom r-rel: t = (2r-1) / r ((1-2r)/r) * G P0 = P( 0 csomag* (2r-1)/r időegység alatt ) = e -2G
((1-2r)/r)*G
-G
(sima aloha) G*e <= S(G) = G*e <= G*e (Slotted aloha) vagyis a sima alohánál jobb, de a slotted alohánál rosszabb. CSMA: Carrier Sense Multiple Access: figyeljük a vivő médiumot, hogy szabad-e mielőtt küldünk Non-persistent CSMA: ha a csatorna szabad, akkor kezdjük meg az átvitelt. Ha foglalt, akkor várunk véletlen ideig, majd újra küldjük. CD: Collision Detection: Ha kollízió történik, akkor leállunk a küldéssel, utána véletlen ideig várunk, és mindkettőt újra küldjük. p-persistent CSMA: nem biztos, hogy azonnal küld, még ha szabad a csatorna akkor sem. Ha szabad a csatorna, akkor p eséllyel elkezdjük az adatátvitelt (ha kollízió van, akkor megszakítjuk), (1-p) valószínűséggel várunk a következő slotra. Ha foglalt a csatorna, akkor addig várunk, amíg szabad nem lesz (figyeljük, hogy mikor lesz szabad). http://qwak.web.elte.hu/targyak/szamhalo/6.gyak.JPG
7. gyakorlat (2007-11-06/07) Gyak: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy07.pdf EA: http://people.inf.elte.hu/lukovszki/Courses/0708NWI/nwI07.pdf
Adaptív fa protokoll 8 állomás: 0-tól 7-ig az állomások azonosítói a levelekben. 2,3,4,6 egyszerre akar küldeni (a fa gyökérben ábrázolva). Legfelső szintjét nézem a fának, melyik részében van az adott állomás. Kollíziónál balra lépek lefele, megint nézzük, hogy melyik állomások vannak a részfában a 2,3,4,6 közül: 2,3 ==> megint kollízió. Megint balra lépek egyet lefele, ebben nincs egyik küldő állomás sem ==> üres slot következik. Ekkor nincs ütközés, úgyhogy visszalépek, és vizsgálom a másik oldalt. Ebben az oldalban a 2,3 ütközik, balra lelépünk egyet, itt már csak a 2-es van ==> visszalépés, jobbra vizsgáljuk: csak a 3-as van, és a részfa végére értünk ==> visszalépünk a gyökérbe, és nézzük a jobb oldalát. Itt a 4,6 ütközik, úgyhogy lépünk balra le ==> ebben a részfában már csak a 4-es van, tehát lépünk vissza és jobbra, itt pedig csak a 6-os küldő szerepel, úgyhogy ő küld utoljára. A sorrend tehát: (2,3,4,6) ==> (2,3) ==> () ==> (2,3) ==> (2) ==> (3) ==> (4,6) ==> (4) ==> (6)
Valszám X: ütközések száma P[x=1] = ? P[x=2] = ? P[x=3] = ? Először a két állomás egyszerre akar küldeni egy médiumon, tehát biztosan ütköznek ==> P[x=1] = 1 Lejjebbi szinttől nézem csak a fa egy részfáját: P[x=2] = 1 * 1/2 = 1/2 Legalsó szinten nézzük a fát: P[x=3] = 1/2 * 1/4 = 1/8 Általánosan is felírhatjuk: P[x=i] = P[x=i-1] * P[i. lépésben is ütközés] = p[x=i-1] * 1/2 i-1 n SZUM(n) i(i-1)/2 P[x=i] = PRODn=1 (1/2 ) = 1/2 = 1/2 A slot idő a maximális propagációs idő kétszerese. (slottime = 2*t prop) Így fog rendesen működni a kollízió detektálás.
Propagációs késés számolás Adatráta: r = 100 Mbps kábelhossz: d = 200m Késés: tproc = 0,7ms 8 Sebesség (rézkábel esetén): c = 1,8 * 10 m/s
i-1
8
Kell: tprop1 = d/c = 200/1,8 * 10 = 1,1 * 10 tmaxprop = tprop1 + tproc = 1,8 µs
-6
s = 1,1 µs
Megvizsgálhatjuk, hogy ilyen feltételek mellett működőképes lesz-e az ethernet kábel. Tudjuk, hogy tgen > 2 * tmaxprop kell, hogy működjön a kollízió felismerés. t gen = P size / r Ethernet esetén a legkisebb csomag mérete: 64 byte ==> 6 -6 t gen = P size / r = 64 byte / 100 Mbps = 512 bit / 100 * 10 bps = 5,12 * 10 s = 5,12 µs 2) tmaxprop = tprop1 + 2 tproc = 2,02 µs
9. gyakorlat (2007-11-21) http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy09.pdf
Dijkstra u
dist
A
inf
B
pre
dist
pre
dist
pre
dist
pre
dist
pre
inf
6
E
6
E
6
E
6kész
E
inf
inf
12
E
12
E
12
E
10
A
C
inf
6
D
6
D
5
F
5kész
F
5kész
F
D
0
0kész
-
0kész
-
0kész
-
0kész
-
0kész
-
E
inf
1kész
D
1kész
D
1kész
D
1kész
D
1kész
D
F
inf
2
D
2
D
2kész
D
2kész
D
2kész
D
-
dist
pre
D a start csúcs. 0-val eljutunk bele. A többi még nem elérhető ==> végtelen távolság (inf). D már kész, 0-val. D-ből elérjük: C, E, F-et, (6, 1, 2 költséggel) Legkisebb költségű össz út az E sor (1) ==> már biztos, hogy ez a legrövidebb, úgyhogy odaírjuk, hogy kész. E-ből elérjük: A, B, F-et (6, 12, 8 költséggel). Mivel az F-et már elértük olcsóbban is (D-ből 2-vel), ezért nem írjuk át 8-ra. Legkisebb költségű össz út az F sor (2) ==> F-ből elérjük: C, E-t (5, 9 költséggel), de E már kész, azt nem kell újra vizsgálni. C sorba beírjuk az 5-öt, F-ből. Legkisebb költségű össz út a C sor (5) ==> ... 2) Ha kitöröljük az E-A élt, akkor A-t nem érem már el 6-tal E-n keresztül, hanem körbe kell mennünk D-E-B-A úton 16-tal.
Distance vector routing protokoll 1) Változik-e B távolság vektora, miután B megkapja E táv.vektorát? A "B" táblázatban alapból ismert a többi állomástól való távolság. Ha E elküldi neki az ő által ismert távolságokat, akkor megnézzük, hogy mi van, ha B-ből E-n keresztül érnénk el az állomásokat, vagyis ha B-ből elérhető E 11-gyel, akkor a 11-hez hozzáadjuk az E-ből elérhető állomások távolságait, és ha valamelyik közülük kisebb lenne, mint a B-ben található távolság, akkor inkább E-n keresztül kéne irányítanunk a forgalmat. Mivel azonban a példában nincs ilyen eset, ezért nem változik B távolság vektora. 2) Ha A és B közt megszűnik a kapcsolat, akkor B táblájában az A sorba bekerül egy végtelen költség. ==> Miután megkapja E-től a távolság vektort, és meg tudja nézni, hogy E-n keresztül elérhető-e az A állomás. Megnézzük E táblázatot, ott szerepel A sor, 5 költséggel, tehát B-ből is elérhető az A, viszont előtte E-be kell menni 11-gyel, aztán 5-tel A-ba, vagyis B táblázatának az A sorába 16, E kerül.
IP csomag útja Nem lesz vizsgán..
10. gyakorlat (2007-11-28) http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy10.pdf
Path Vektor protokoll C
út
költség
A
CBA
7
B
CB
3
D
CBED
11
E
CBE
9
D
n
költség
A
DEA
7
B
DEB
8
C
DEBC
11
E
DE
2
1) Megnézzük, hogy C-ből és D-ből melyik legolcsóbb költségű úttal érjük el a csomópontokat. 2) Hozzáadva egy F csomópontot és 2 élt, felírjuk az új csomópont táblázatát is: F út költség
A
CBA
8
B
CB
4
C
C
1
D
D
1
E
DE
3
majd aktualizáljuk a többi distance vectort is, pl a D távolság vektorának a C sora javul F-en keresztül 2-re 11 helyett: D út költség C
DFC
2
Utolsó gyak (2007-12-12) http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy11.pdf 2) Három DUPACK esetén a TCP Tahoe: újraküld + slowstart fázis: lecsökkentjük teljesen a küldési ablakot, majd exponenciálisan növeljük a treshold szintig, onnan kezdve már egyenletesen növeljük. Hibánál teljesen lecsökkentjük megint a küldési ablakot. TCP Reno: ezzel szemben nem teljesen csökkentjük le, hanem csak a treshold értékig. Ez a módszer jóval hatékonyabb, mert nem mindig 0-ról kezdjük növelni. 2/4) ha folyamatosan alacsony számú ablakot küldünk, akkor a partner is ehhez fogja tartani magát.. Elkezd működni a slowstart szerint, kiküldünk egy ablakot. Ha jön a válasz a fogadótól, akkor növelhetjük az ablak számát 2-re. Ha azt is visszajelzi a fogadó, akkor megint növeljük az ablakok számát 4-re.. 3) n db kapcsolat ugyanazt a vonalat használja kell: fairness index.. sok szumma =( http://people.inf.elte.hu/lukovszki/Courses/0708NWI/gy12.pdf 1) x1, x2 tengelyen átlós a maximális kapacitás x1: AIMD stratégiát használ (additív növekedés, multiplikativ csökkentés) AI: x := x + 1 MD: x := x/2 x2: AIAD: AI: x := x + 1 AD: x := x - 1 Kezdetben a fairness egyenesről indulunk. mindkettő látja, hogy van szabad kapacitás, AI szerint kezdenek el működni, x1 és x2 mentén is 1-1-et lépünk felfele. Elérjük a maximum vonalat, elkezdünk csökkenteni: x1 irányban MD szerint, azaz megfelezzük az x1 tengely mentén, és 1-et levonunk belőle x2 tengely mentén.
megint jöhet a növelés: 45°-ban felfele (+1 x1, +1 x2), majd a felezés függőlegesen és balra 1. ... Ezt ismételgetve a 45° os fairness egyenes től jobbra-lefele fogunk konvergálni, Vagyis nem fair a működés, x2-nek kedvez inkább. 1/2) Nem kaphatunk fair eredményt, mert ha különböző stratégiát használnak, akkor mindig valahova máshova fog konvergálni. 2/1) d = 43 2/2) kódolt üzenet: 47
