Számítógépes hálózatok Gyakorló feladatok megoldása 1. feladatsor

Utolsó módosítás: 2007.01.23. 13.00

Számítógépes hálózatok Gyakorló feladatok megoldása 1. feladatsor 1. feladat: Rendelje a következő fogalmakat az Internet négy rétegéhez! 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

E-Mail Csomagtovábbítás (packet forwarding) Ethernet Optikai kábel TCP Internet Protocol Port cím Koaxiális kábel Token ring Wi-Fi IP cím HTTP Útvonal-meghatározás (routing)

/ Felhasználói / / Hálózati / / Adatkapcsolati (Fizikai) / / Adatkapcsolati (Fizikai) / / Szállítási / / Hálózati / / Szállítási / / Adatkapcsolati (Fizikai) / / Adatkapcsolati (Fizikai) / / Adatkapcsolati (Fizikai) / / Hálózati / / Felhasználói / / Hálózati /

2. feladat: Az ISO/OSI modell hét réteget definiál, míg a TCP/IP modell négyet. Gyüjtsön érveket, melyik modell a jobb. Határozzon meg kritériumokat a két modell értékeléséhez és értékelje a modelleket azok alapján. Megoldás: Összetett kérdés, sok szöveg kell ide. 3. feladat: A legtöbb hálózatban az adatkapcsolati réteg úgy kezeli az átviteli hibákat egy linken, hogy a hibás vagy elveszett frame-et újraküldi. Ha annak a valószínüsége, hogy egy frame hibás vagy elveszett, p, mennyi az átviteli kisérletek (küldések) számának várható értéke egy frame sikeres küldéséhez (ha feltesszük hogy a küldő minden sikertelen küldésről értesül)? Megoldás: Geometriai eloszlás: hányadik kísérletre fog bekövetkezni először egy p valószínűségű esemény. Itt most az 1–p valószínűségű esemény bekövetkeztére vagyunk kíváncsiak. Erre a geometriai eloszlás 1 várható értéke: E ( X ) = 1− p 4. feladat: Képzeljük el, hogy egy kiképzett bernáthegyi mentőkutya rum helyett CD-t visz magával 700MB adattal. Tegyük fel, hogy ez a kutya el tud jutni önhöz 18 km/h sebességgel, bárhol is van. Milyen távolságig nagyobb a kutya adatrátája, mint egy 2,5 Mbps DSL vonalnak? Megoldás: v = 18 km/h = 5 m/s a = 700MB = 5600Mb b = 2,5 Mbps

1

Utolsó módosítás: 2007.01.23. 13.00 s: a keresett távolság

s s t= = v 5 a a = ≥b s t 5

5600 ≥ 2,5 s 5 5600 ⋅ 5 s≤ = 11200m = 11,2km 2,5

2. feladatsor Ezek gyakorlati feladatok, ilyenek nem lesznek vizsgán.

3. feladatsor 1. feladat: Írja fel az s (t ) =A ⋅ sin( 2πft + Φ ) függvényt, mint s (t ) = a1 sin(b1t ) + a 2 cos(b2 t ) azáltal, hogy megadja az a1, a2, b1, b2 együtthatókat az A, f és Φ függvényeként. Megoldás:

s (t ) = A ⋅ sin( 2πft + Φ)= A ⋅ [sin( 2πft ) ⋅ cos Φ + sin Φ cos(2πft )] = = cos Φ sin( 2πft ) + A sin Φ cos(2πft ) ⇒

a1 = A cos Φ a 2 = A sin Φ b1 = b2 = 2πf

2. feladat: Számolja ki a következő függvény Fourier-sorát: sin(t ), ha t ∈ (2πk ,2πk + π ) f (t ) =  cos(t ), ha t ∈ (2πk + π ,2πk + 2π ) ahol k egész szám. Ábrázolja az eredményt grafikusan úgy, hogy az első öt Fourier-tagot a [0, 2 π ] intervallumban függvényként ábrázolja. Megoldás: Fourier-sorfejtés... Az integrál tartomány szerint szétbontható + addíciós tételek. 3. feladat: Az előadáson bemutatott kódok közül melyek önütemezők? Minden bemutatott kódhoz adjon meg vagy egy bitsorozatot, amelyből nem nyerhető ütemezés, vagy mutassa meg, hogy hogyan nyerhető az ütemezés bármely lehetséges kódolt bitsorozatból. Megoldás: Önütemező: Manchester, Biphase-M, Biphase-S, Differential Machester Delay, Delay Modulation (Miller) Nem önütemező: NRZ-L ( 11111111 ), NRZ-M ( 00000000 ), NRZ-S ( 11111111 ) , RZ ( 00000000 ), Bipolar ( 00000000 ) Magyarázat: A nem önütemezőben van olyan bitsorozat, amiből nem tudjuk megállapítani, hogy hol van egy bit vége, egybefolynak. Az önütemezőknél még meg kéne mutatni, hogy bármely 00, 01, 10, 11 kombinációból meg tudjuk mondani, hogy hol vannak a határok.

2


4. feladat: Milyen probléma merülhet fel a Manchester-kódolással, ha az egyes bitsorozatok átvitele között hosszabb átviteli szünet van (pl. ha a 01 bitsorozatot egy hosszabb szünet után visszük át)? Hogyan lehet ezt a problémát megoldani? Megoldás: Még nincs...

4. feladatsor 1. feladat: Mutassa be, hogyan ábrázolódik a 011001 bitsorozat, ha 1. amplitúdó moduláció 2. frekvencia moduláció 3. fázis moduláció által kerül átvitelre. Válassza ugyanazt a vivőfrekvenciát minden esetben. Adja meg először a (szabadon választott) kódolást, és ábrázolja grafikusan a függvényt, amit ez eredményez. Megoldás: 1. amplitúdó moduláció 0: F (t )= 0 sin( 2πft + 0) 1: F (t )= 1sin( 2πft + 0) 2. frekvencia moduláció 0: F (t )= 1sin( 2π ( f )t + 0) 1: F (t )= 1sin( 2π (2 f )t + 0) 3. fázis moduláció 0: F (t )= 1sin( 2πft + 0) 1: F (t )= 1sin( 2πft + π ) + rajzok, lásd 4. előadás anyaga, 4–6. oldal. 2. feladat: Egy küldő egy üvegszál kábelen egy fényszignált küld PS teljesítménnyel. Tegyük fel, hogy a fogadónál ennek a szignálnak legalább PS/1000 teljesítménnyel kell megérkezni ahhoz, hogy fel tudja ismerni. A kábelben az elnyelődés 6,5% per km. Milyen hosszú lehet a kábel? Megoldás:

Px = (1 − 0,065) x PS PS = 0,935 x PS 1000 1 = 0,935 x 1000 1 log10 = log 10 0,935 x 1000 − 3 = x log10 0,935 x=

−3 ≈ 0,102km = 102m log10 0,935

3. feladat: Adjon felső korlátot az elméletileg elérhető adatrátára Shannon tétele alapján 1. sodort réz érpár Cat-5 kábelre 100MHz-ig,

3


2. koaxiális kábelre 1GHz-ig és 3. üvegszál kábelre az infravörös tartományban, 20dB szignál-zaj-ráció (SNR) esetén. Hasonlítsa össze az eredményeket az 512kbps-8Mbps DSL (twisted pair), 100Mbps Fast Ethernet (twisted pair) és 40Gbps OC-786 (üvegszál) rátáival. Kommentálja az eredményeket. Megoldás: S S = 20 ⇒ = 100 N N S  Shannon : B ≤ h log 2 1 +  N  1) B ≤ 100Mhz ⋅ log 2 (1 + 100) ≈ 666Mbps SNR=20dB ⇒ 10 log10

2)

B ≤ 1GHz ⋅ log 2 (1 + 100) ≈ 6,666Gbps

3)

B ≤ 1013 Hz ⋅ log 2 (1 + 100) ≈ 6666Gbps

(az infravörös tartomány 1013 Hz)

Látható, hogy ezek csak durva elméleti korlátok, a gyakorlatban messze járnak ezektől az értékektől.

5. feladatsor 1. feladat: Tekintsünk az adatkapcsolati rétegben egy byte alapú protokollt, melyben a frame-ek egy flag-byte-tal kezdődnek és byte beszúrást használ. Legyen p annak a valószínűsége, hogy egy byte hibásan kerül átvitelre. összesen m frame-et küldünk. Legyen n a frame-ek összhossza (azaz a médiumon áthaladó byte-ok száma). 1. Határozza meg a byte hibák várható értékét. 2. Határozza meg a hibásan fogadott frame-határoló flagek számának várható értékét. 3. Határozza meg a helytelenül értelmezett flagek számának a várható értékét a hasznos adatok között, ha egy flag-byte gyakorisága az (eredeti) adatokban 1/256. 4. Határozza meg a helytelenül értelmezett flagek számának a várható értékét a hasznos adatokban, ha az átvitelre kerülő adatok csak flagekből állnak. Emlékeztető: Ha egy esemény q valószínűséggel következik be egy kisérlet során és a független kisérletek száma k, akkor az esemény bekövetkezéseinek a számának a várható értéke kq. Megoldás: 1. 2. 3.

4.

n byte halad át rajta, minden byte-ra p a hiba valószínűsége, ezért np a byte hibák várható értéke. m frame, frame-enként 2 flag byte van, mindegyikre p a hiba valószínűsége, ezért 2mp a várható érték. n–2m a hasznos byte-ok száma, de a flag-byte-ot két byte-on tudjuk kódolni az adatok között, ugyanígy az emiatt használt escape-byte-ot, és ezek gyakorisága (az utóbbira csak feltételezve 1/256), tehát 256 byte-nyi átküldendő adatban átlagosan egy escape-byte, egy pedig flag-byte, ezért átlagosan 256 átküldendő byte-ot 258 byte-on ábrázolunk. Hogy ezek közül pont a flag 1 256 p ⋅ p ( n − 2 m) = ( n − 2 m) . byte-ot értelmezzük rosszul, annak várható értéke: 256 258 258 Itt most minden elküldendő byte-ra két elküldött byte jut, a flag byte-ok gyakorisága 1, ezért a várható érték: 1 p ( n − 2 m) 2 4


2. feladat: Ebben a feladatban meghatározzuk, hogy mekkora lehet legfeljebb egy kód könyv C, melynek Hamming-távolsága d(C) = k. Tekinstünk n hosszú bitsztringeket. 1. Határozza meg egy tetszőleges x œ {0, 1}n bitsztringhez azon u œ {0, 1}n bitsztringek számát, melyekre d ( x, u ) = i, 0≤i≤n 2. Tekintsünk egy tetszőleges x œ {0, 1}n bitsztringet. Mutassa meg, hogy legfeljebb egy legális k −1 kód u œ C létezhet, amelyre d ( x, u ) ≤ 2 3. Határozza meg azon n hosszú bitsztringek számát, amelyeknek egy adott legális u œ C kódtól  k − 1 (nem kell zárt kifejezés). a Hamming-távolsága legfeljebb   2  4. Mutassa meg a Hamming-korlátot minden C ⊆ {0, 1}n kódra, melyre d(C) = k: C⋅

 k −1   2   

n

∑  i  ≤ 2

n

.   5. Mekkora lehet legfeljebb egy kód könyv a Hamming korlát szerint n = 8 és k = 3 esetén? 6. Próbáljon meg egy jó kód könyvet konstruálni, ha n = 8 és k = 3. i=0

Megoldás: n 1.   , mert n byte-ból ennyiféleképpen tudunk megváltoztatni i byte-ot. i 2. Tegyük fel indirekten, hogy két ilyen tulajdonságú eleme is létezik a kód könyvnek, legyenek ezek u és u'. Ekkor ezek távolságára: d (u , u ' ) ≤ d ( x, u ) + d ( x, u ' ) ≤ k − 1 , de kikötöttük, hogy a kód távolsága k, így az elemeinek távolsága legalább k, tehát ellentmondásra jutottunk.  k −1   

 2  n    k − 1   bitet változtathatunk, tehát a feladat 1. része alapján ez: 3. Legfeljebb  ∑  2  i=0  i  4. A 2. és a 3. feladat megoldása alapján ha a kódtávolság k, akkor minden u kódkönyvbeli  k −1   2   

elemhez tartozik

n

∑  i 

bitsztring, ami pontosan u-hoz van a legközelebb, nevezzük ezt u   környezetének. Ha vesszük az összes kódkönyvbeli elemet a környezetükkel együtt, az összelemszámuk nem lehet nagyobb, mint az összes n hosszú bitsztring száma, azaz 2 n , 5. Behelyettesítve a Hamming-korlát képletébe azt kapjuk, hogy: i=0

5


C⋅

 3−1   2   

8

∑  i  ≤ 2

8

  8 C ⋅ ∑   ≤ 256 i =0  i  i =0 1

  8 8 C ⋅    +    ≤ 256   0 1 9 C ≤ 256 C ≤

256 ≈ 28,4 9

Tehát a kódkönyv legfeljebb 28 elemű. 6. Olyan kódkönyvet kéne generálni, amelyben minden elem legalább három bitben különbözik egymástól. Perfekt kód nem létezik n = 8, k = 3-ra, a Hamming-korlátban nem teljesülhet egyenlőség, hiszen |C| nem lehet egyenlő egy nem egész számmal. Az {11111111, 11111000} például egy jó kódkönyv, nem volt megadva a kódkönyv minimális elemszáma. De például egy bővebb kódkönyv készíthető a (7,4,3)-as Hamming-kóddal, ha azt kibővítjük egy utolsó 0 bittel. Ezt egy mátrixszal tudjuk generálni 4 bites inputokra: 1 0 0 0 1 1 1 0    0 1 0 0 0 1 1 0  0 0 1 0 1 0 1 0    0 0 0 1 1 1 0 0  

(0 0 0 0)(0 0 0 0 (0 0 0 1)(0 0 0 1 (0 0 1 0)(0 0 1 0 (0 0 1 1)(0 0 1 1 (0 1 0 0)(0 1 0 0

0 0 0 0) 1 1 0 0)

1 0 1 0)

0 1 1 0)

0 1 1 0) ...

(1

1 1 1)(1 1 1 1 1 1 1 0 )

Tehát ezzel az eljárással kapunk 16 különböző elemből álló kódot, amelynek a Hamming-távolsága 3. Persze az utolsó bit kihasználásával lehetne még több elemből álló kódot generálni.

6. feladatsor 1. feladat: (CRC) Számolja ki a 0101.1011.1101.0010 inputhoz a 4-bit-CRC kontrollösszeget, ha a generátor polinóm x4 + x2 + 1. Adjon egy olyan inputot, amely 1-gyel kezdődik és ugyanezt a kontrollösszeget erdményezi. Megoldás: 1011011110100100000:10101 (=100110000010110) -10101 11111 -10101 10101

6


-10101 0010010 -10101 11100 -10101 10010 -10101 1110 a 4 bites CRC-kontrollösszeg Ahhoz, hogy a generátorpolinommal való osztás ugyanazt a maradékot adja, az input polinomhoz a generátorpolinom többszörösét kell hozzáadni, azaz például az eltoltját. Így a megoldás: 10101000000000000000 +01011011110100100000 11110011110100100000 2. feladat: Tekintsük a következő paritás-technikát: • Tekintsük az n küldendő adatbitet mint egy k × ℓ bit-mátrix. • Minden oszlophoz számoljon ki egy paritás-bitet (pl. odd parity) és egészítse ki a mátrixot egy új sorral, mely ezeket a paritás-biteket tartalmazza. • Küldje el az adatokat soronként. 1. Adjon egy példát k = 3, ℓ = 4 esetén. 2. Hogy viselkedik ez a módszer egyszerű bit-hibák és löketszerű (burst) bit-hibák esetén? Milyen hosszú lehet egy bitsorozat, melynek minden bitje hibás (burst), hogy a hibát felismerjük? 3. Egészítse ki a mátrixot egy új oszloppal is, amely minden sorhoz paritás-bitet tartalmaz (két dimenziós paritás technika). Hogyan használható ez a módszer 1-bit-hiba javítására? Mi a helyzet több bithibával és burst-hibákkal? Megoldás: 1. 1011 1101 1010 0011 2.

3.

Odd, azaz páratlan paritásnál úgy kell kiegészíteni a biteket, hogy páratlan sok egyes legyen. Egyszerű bithibákat fel tud ismerni, de nem képes javítani őket, mert nem lehet tudni, hogy melyik sorban történt a hiba, hiába látjuk, hogy nem stimmel a paritás. 2ℓ–1 hosszú bursthibánál is képes észlelni a hibát, ha ezek valóban eltérnek az eredetitől, és nem történik más bithiba (ekkor előfordulhat, hogy csak egy bitnyi hibát érzékelünk, de ez még épp elég az észleléshez). A módosított mátrix: 1011 0 1101 0 1010 1 0011 Egy bithiba esetén a következő esetek lehetségesek: A) az eredeti adatfolyamban történt hiba: Ekkor a megfelelő sorhoz és oszlophoz tartozó paritásbitek a várttól eltérő értékéből tudunk következtetni a hiba jelenlétére, illetve helyére is. Emiatt ez a hiba javítható.

7


B) az egyik oszlop paritásbitben történt hiba: Ez azt jelenti, hogy a sorra vonatkozó paritásbitek mind stimmelnek, ez jelzi, hogy nem az eredeti adatfolyamban történt a hiba, és ilyenkor a paritásbitet kell javítani. C) az egyik sor paritásbitben történt hiba: Hasonló a helyzet, mint a B esetben. Ha azonos sorban vagy oszlopban több bithiba történt, azt nem képes kijavítani ez a módszer, de 2ℓ hosszú burst-hibákat képes észlelni. 3. feladat: Tegyük fel, hogy a csomagok P1, P2,...,P7 simplex-üzemmódban kerülnek átvitelre. A csatorna egy csomagot egy időegység alatt visz át. A hálózati réteg megpróbál minden második időegységben egy csomagot átadni az adatkapcsolati rétegnek. A fizikai rétegben pontosan minden második csomag és pontosan minden harmadik nyugta hibásan kerül átvitelre. Szimulálja a csomagok átvitelét 1. az egyszerű simplex protokoll, 2. az alternáló bit protokoll és 3. egy csúszó ablak protokoll esetén, ahol n = 3 és a küldő- és a fogadó-ablakméret 3. Tegyük fel, hogy a ”timeout” egy időegység a simplex és az alternáló bit protokoll esetén és két időegység a csúszó ablak esetén. Tegyük továbbá fel, hogy a csomag átadása a hálózati és az adatkapcsolati réteg között, valamint az adatkapcsolati és a fizikai réteg között gyakorlatilag időveszteség nélkül történik. Minden csomag (és minden nyugta) a csatornát egy egész időegységre lefoglalja. Adatcsomag és nyugta nem vihető át egyidejűleg. Tegyük fel, hogy konfliktus esetén mindig az adatcsomag győz. Megoldás: Ez több hosszú rajz lenne, lásd gyakorlat. 4. feladat: ”Go-Back-N” és Szelektív Ismétlés esetén legfeljebb hány csomagot küldhet a küldő egyszerre, illetve legfeljebb hány csomag lehet egyidejűleg elküldött, de nem nyugtázott, ha a sorszámok tere 16 elemű (pl. sorszámok 0-tól 15-ig)? Gondoljon a legkedvezőtlenebb pillanatokban elveszett nyugtákra. Mutasson egy példát erre az esetre. Megoldás: A küldő egyszerre 8 csomagot küldhet nyugtázás nélkül. Tegyük fel, hogy 9 csomagot küld. Ekkor előfordulhat, hogy mind a 9 (0, 1, 2, 3, 4, 5, 6, 7, 8) megérkezik a fogadóhoz, és az ezekről visszaküldött nyugták mind elvesznek. Ekkor a fogadó a (9, 10, 11, 12, 13, 14, 15, 0, 1) sorszámúakat fogadja el, a küldő pedig a timeout után újraküldi az első kilencet, ami azt eredményezi, hogy a fogadó kétszer fogadja el a 0-s és az 1-es sorszámú csomagot.

7. feladatsor 1. feladat: A ”slotted ALOHA” protokoll esetén egy slot hossza pontosan egy frame átviteléhez szükséges időnek felel meg. Tegyük fel most, hogy egy frame átviteléhez szükséges idő a slot hosszának r-szerese. Adja meg az S átvitelt a terhelés G függvényében, ahol G a csomagküldési kisérletek várható száma egy csomag átviteléhez szükséges idő alatt (nem egy slot alatt!) Megoldás: Egy (A) csomag sebezhetőségi ideje az az időmennyiség, amennyin át ha elkezdünk elküldeni egy másik (B) csomagot, akkor ütközés történik a kettő között. Ha r slot ideig tart egy frame átvitele, akkor ez az idő slotokban mérve: 2r–1, a két szélső esetre egy ábra r=4 esetre:

8


1 2 3 4 5 6 7 8 9 10 Az alsó sor jelzi az A csomag küldését, az 1–7. időpillanatban nem küldhetünk el B csomagot, ha a 4. időpillanatban küldtük el az A csomagot, tehát a csomag sebezhetőség ideje 7, általánosabban r–1+r = 2r–1, slotokban mérve, ez alatt az idő alatt csak egy csomag küldhető. De a feladat nem a slotok idejét tekinti egységnek, hanem a csomag átviteléhez szükséges időt, ezért ezt még el kell osztani r-rel: 2r - 1 csomagátviteli időn keresztül nem küldhető másik csomag. r Annak a valószínűsége, hogy ennyi idő alatt csak egy csomag átvitelére érkezik kísérlet: 2 r −1 2 r − 1 −G ⋅ r  2r - 1  P1 = P ⋅e idő alatt pontosan 1 db kísérlet  = G ⋅ r  r  −G⋅ 1 csomag S (G ) = ⋅ P1 = G ⋅ e 2r - 1 idő r

2 r −1 r

2. feladat: Tekintsünk egy csatornát véletlen közeghozzáférési protokollal. A csatorna egyik végén van A állomás, a másik végén B és C. A propagációs késés a csatorna két vége között t0. (Tegyük fel, hogy B és C között a késés 0.) Az egyes állomások a következő időpontokban akarnak adatot átvinni: tA = 0, tB = t0/2, tC = 3t0/2. A frame-ek generálási ideje Tgen = 4t0. Ábrázolja a következő hozzáférési protokollok viselkedését: 1. ALOHA 2. nonpersistent CSMA 3. nonpersistent CSMA/CD 4. 0,5-persistent CSMA/CD Tegyük fel, hogy a véletlen várakozási időt CSMA és CSMA/CD esetén {0, 1t0, 2t0,...,(k − 1)t0} közül egyenletes eloszlás szerint választjuk, ahol k értéke ”binary exponential backoff” szerint kerül meghatározásra. Megoldás: 1) Aloha: mindegyik ütközni fog, mert nem tud ráhallgatni a csatornára. És az A 5 időegységre foglalja le a csatornát és ebbe a az időbe B és C is beleesik, ezért kollízió történik. Nincs kollíziófelismerés, tehát mindeki átnyomja összeromboltan a saját csomagját. 2) nonpersistent CSMA: Belehallgat; ha üres a csatorna, küld, ha nem üres, akkor véletlen ideig vár, de itt is lesz kollízió, mert a B nem látja, hogy foglalt a csatorna ( t0 prop késés és t0/2 után küld B), C észleli majd, hogy foglalt a csatorna, ő nem küld, vár véletlen ideig. Nincs kollíziófelismerés végig átnyomja mindenki a saját rombolt csomagját. 3) nonpersistent CSMA/CD: Ugyanaz, mint 2), de amikor A és B csomagja ütközik kollíziófelismerés lesz, és C el tudja küldeni a csomagját, A, B véletlen ideig vár, és látja majd, hogy C dumál, tehát megint vár véletlen ideig. 4) 0,5 persistent CSMA/CD: (ez itt nem tökéletes – T.T.) A) A és B is vár véletlenig és úgy küldenek hogy nincs kollízió, de a várakozási idejük alatt C el tudja küldeni az ő csomagját. Majd A és B is elküldi, a véletlen várakozásnak hála mindenki épen elküldi.

9


B) A vár és B nem vár és kollízió lesz ezt felismerik, C Látja a foglalt csatornát, ezért vár, majd elküldi a csomagját közben A és B is vár. Majd ők is elküldik a csomagjukat kollízió nélkül. C) A sem, B sem vár, és kollízió lesz, de felismerik innentől kb. ugyanaz mint a 3)-as. D) A és B is vár, majd küld, nem lesz kollízió, de C nem veszi észre még, hogy foglalt a csatorna, és elkezd küldeni kollízió, ezt felismerik, abbahagyják az átvitelt, véletlenig várnak, majd hibamentesen átküldik.

8. feladatsor 1. feladat: Tekintsünk nyolc állomást, melyek adaptív fa protokollal visznek át csomagokat. Az állomások azonosítói {0, ..., 7}. Szimulálja a protokoll működését, ha az állomások 2, 3, 4, 6 egyidőben akarnak csomagot átvinni. (Adja meg a verseny slot-okat ettől az időpillanattól addig, amig a protokoll feloldja a kollíziót.) Megoldás: e 0

1

00

01

000

001

0

1

010

10

11

011

100

101

110

111

3

4

5

6

7

2

Egyszerre akar küldeni: 2, 3, 4, 6 adaptive_tree_walk node_test(e) node_test(0) node_test(00) node_test(1) 23 46

23

46

23

2

3

4

6

Ez itt kell??? 2. feladat: Mennyi a valószínűsége egy Ethernet hálózatban, hogy két állomás, amely kezdetben egyidőben akar csomagot küldeni, csak a harmadik kollízió után tudja átvinni a csomagot (feltéve, hogy további állomás nem akar eközben csomagot átvinni)? Mennyi a valószínűsége, hogy csak az i-edik kollízió után? Mennyi ez a valószínűség egy 10Mbps Ethernet hálózatban, ha kezdetben az állomások nem egzakt ugyanabban az időben kezdik az átviteltelt, de kollíziót detektálnak? (Segítség: mennyi a ”slot time”, a minimális csomagméret és mennyi a ”maximum propagation delay”?)

Megoldás: CSMA/CD és binary exponential backoff Kezdetben ütköznek, ezt észlelik, sorsolnak egy slot time-ot 2 lehetséges érték közül {0, 1}. Annak a valószínűsége, hogy ugyanazt sorsolják:

10

Utolsó módosítás: 2007.01.23. 13.00 1 2 Ezután már négy szám közül fognak sorsolni. Hogy másodszor is ütköznek, annak az esélye: 1 1 P2 = ⋅ P1 = 4 8 Hiszen először ütköztek => P1 , másodszorra ugyanazt húzták: 1/4, a kettő független. Hasonlóan: 1 1 P3 = ⋅ P2 = 8 64 P1 =

Az nem volt kikötve, hogy a 3. után már sikerülni fog az átvitel, tehát a keresett valószínűség P3. Általánosíthatunk i-re is: 1 1 1 1 1 1 Pi = i ⋅ Pi −1 = i ⋅ i −1 ⋅ ... ⋅ 1 = i = i (i +1) 2 2 2 2 ∑k 2 2 2 k =1 Legyen tA az az időpont, amikor A akar küldeni, tB az az időpont, amikor B akar küldeni adatot, illetve I( tA ) := ( tA – d, tA + d ). Ütközés akkor van, ha tB œ I( tA ). Ekkor A kisorsolja i-t, B kisorsolja j-t. Mikor lehet ezután ütközés újra? Akkor, ha tB + j*slottime œ I( tA + i*slottime ). Ez a „slot time” ≥ „maximum propagation delay” feltétel miatt csak akkor lehetséges, ha i = j, tehát ugyanaz a helyzet, mint az előbb. 3. feladat: Mennyi a ”maximum propagation delaly” Fast Ethernet (100Mbps) estén, amelyben 1. a kábelek maximális összhossza 200m és egy ”Class I” repeatert tartalmaz, amely (max.) 0,7µs késést okoz, 2. a kábelek összhossza 205m és két ”Class II” repeatert tartalmaz, amely egyenként (max.) 0,46µs késést okoz? Megoldás: 200 m + 0,7 ⋅ 10 −6 s ≈ 1,81 ⋅ 10 −6 s = 1,81µs 8 1,8 ⋅ 10 m/s 205 m 2) + 2 ⋅ 0,45 ⋅ 10 −6 s ≈ 2,04 ⋅ 10 −6 s = 2,04 µs 8 1,8 ⋅ 10 m/s

1)

9. feladatsor

1. feladat: Tekintsük a G = (V, E) gráfot az 1. ábrán. 1. Számítson ki Dijkstra algoritmusával egy legrövidebb utak fáját D csomópontból minden más csomóponthoz (minden él szimmetrikus, a szimmetrikus élek súlya mindkét irányban azonos).

11


Minden iteráció után jelölje a "kész" csomópontokat, és adja meg minden u ∈ V csomóponthoz d[u] és pred[u] értékét egy táblázatban. Rajzolja fel a kiszámított legrövidebb utak fáját. 2. Számítsa ki a legrövidebb utak fáját újra D kezdőcsomópontból, ha az (E, A) élt töröljük. Mely csomópontokhoz változik meg az él törlése után a legrövidebb út? Megoldás: u A B C D E F

d[u] ∞ ∞ ∞ 0 ∞ ∞

pred[u] -

u A B C D E F

d[u] ∞ ∞ 6 0 1 2

pred[u] D D D

u A B C D E F

d[u] 6 12 6 0 1 2

pred[u] E E D D D

u A B C D E F

d[u] 6 12 5 0 1 2

pred[u] E E F D D

u A B C D E F

d[u] 6 12 5 0 1 2

pred[u] E E F D D

u A B C D E F

d[u] 6 10 5 0 1 2

pred[u] E A F D D

A feszítőfa:

B

C

4

3

A

F 2 5

E

1

D

Az (E, A) él törlésével keletkezett gráffal ugyanezt végigcsinálva arra jutunk majd, hogy azon az ágon változnak az értékek, ami a fában az (E, A) élen túl van, tehát az A és a B csúcsra. 2. feladat: Számítson ki a Bellman–Ford-algoritmussal egy legrövidebb utak fáját D csomópontból minden más csomóponthoz az 1. ábrán látható G gráfban. Minden iteráció után adja meg minden u ∈ V csomóponthoz d[u] és pred[u] értékét egy táblázatban. Megoldás: Rögzített élsorrend: legyen például az élek súlyának növekvő sorrendjében : 1, 2, 3, 4, 5, 6, 7, 9, 11

12


u A B C D E F

d[u] ∞ ∞ ∞ 0 ∞ ∞

pred[u] -

u A B C D E F

d[u] 6 10 5 0 1 2

pred[u] E A F D D

u A B C D E F

d[u] 6 14 12 5 0 1 2

u A B C D E F

pred[u] E E F D D

d[u] 6 10 5 0 1 2

pred[u] E A F D D

Az élek sorrendjében vizsgáljuk, hogy d[u] + d(u, v) < d[v]. Akkor állunk meg, ha már n–1-szer megismételjük, vagy ha egymás után kétszer ugyanaz az állapot keletkezett. A feszítőfa ugyanaz, mint az előző feladat esetén, hiszen ugyanarra a gráfra kerestük meg. 3. feladat: Tegyük fel, hogy a egy "Distance Vector" routing protokollban a B és E routerek távolságvektora a következő: B A C D E F

cost 4 9 12 11 12

E A B C D F

next hop A C E E C

13

cost 5 11 6 1 3

next hop A B D D D


1. Hogyan változik B távolságvektora, miután B megkapja E távolságvektorát? 2. Ha a kapcsolat A és B között megszűnik, és B újra a fenti távolságvektort kapja E-től, hogyan aktualizálja B a távolságvektorát? Megoldás: 1. Nem változik B távolságvektora, minden cél felé az E-től kapott távolságérték + a B-E távolság nagyobb, mint B aktuális távolsága az adott cél felé. 2. Megváltoztatja az A-ra vonatkozó távolságát úgy, hogy az E-től kapott A-ra vonatkozó távolságértékhez (5) hozzáadja a saját távolságát E-től (11), illetve beállítja, hogy E-nek küldje tovább a csomagot A felé: B A C D E F

cost 16 9 12 11 12

next hop E C E E C

10. feladatsor Nincs meg, de a 2., 3. feladat úgyse lesz.

14


11. feladatsor

15


16


12. feladatsor

17


18


19


Készítette: Orosz György Tihon Tibor Vizi Dávid Zabb László Mindenki saját felelősségére használja, néhol még javításra, és kiegészítésre szorul a dokumentum, azonban a feladat megoldásaihoz felhasználtuk a próbavizsga megoldásait is!

20

Számítógépes hálózatok Gyakorló feladatok megoldása 1. feladatsor

Recommend Documents