Számítógépes Hálózatok 5. gyakorlat
Feladat 0 •
Tízezer repülőjegy-foglaló állomás egyetlen "slotted ALOHA"-csatorna használatáért verseng. Egy átlagos állomás 24 kérést ad ki óránként. Egy slot hossza 250 μs. –
Megközelítőleg mekkora a teljes feldolgozandó terhelés G? Hogyan határozható meg?
–
Adja meg S(G) átvitelt is!
Gombos Gergő
Számítógépes hálózatok
2
Feladat 0 •
Tízezer repülőjegy-foglaló állomás egyetlen "slotted ALOHA"-csatorna használatáért verseng. Egy átlagos állomás 24 kérést ad ki óránként. Egy slot hossza 250 μs. –
Megközelítőleg mekkora a teljes feldolgozandó terhelés G? Hogyan határozható meg? • • •
–
//1 μs = 1000000 s
Adja meg S(G) átvitelt is! •
Gombos Gergő
10000 * 24 kérés/óra = 200/3 kérés/sec 1000000/250 = 4000 slot/sec G = (200/3) / 4000 = 1/60 kérés/slot
S(G) = G * e-G =~ 0,01639
Számítógépes hálózatok
3
Bináris visszaszámlálás protokoll • Forgalmazni kívánó állomás elkezdi a bináris címét bitenként elküldeni a legnagyobb helyi értékű bittel kezdve. • Feladja a küldést ha van nála nagyobb sorszámú • Mok és Ward módosítás – Minden sikeres átvitel után ciklikusan permutáljuk az állomások címét.
Gombos Gergő
Szám.háló 2012 ősz
4
Gyakorló feladat 1. Szimuláljuk a bináris visszaszámlálás protokollt 8 állomás esetén, ahol az állomás azonosítók rendre a {C, H, D, A, G, B, E, F} halmaz elemei, ez a sorrend a prioritási sorrend is. Ez esetben a virtuális azonosítókat 3 biten ábrázolhatjuk. Tegyük fel, hogy A, C, D és E állomások akarnak egy-egy csomagot átvinni. (Nézze meg mi módosulna a Mok- és Ward-féle változat esetén.)
Gombos Gergő
Szám.háló 2012 ősz
5
Gyakorló feladat 1. C – 111, H – 110, D – 101, A – 100, G – 011, B – 010, E – 001, F – 000
idő 1
2
A
1
0
C
1
1
D
1
0
E
0
Gombos Gergő
3
4
5
6
1
0
0
1
0
1
7
8
9
1
adat
10
11
0
adat
Adat 0
adat 0
Szám.háló 2012 ősz
6
Gyakorló feladat 1. (Mok – és Ward) 0. idő: C – 111, H – 110, D – 101, A – 100, G – 011, B – 010, E – 001, F – 000 3. idő: H – 111, D – 110, A – 101, G – 100, B – 011, E – 010, F – 001, C – 000 6. kör: H – 111, A – 110, G – 101, B – 100, E – 011, F – 010, C – 001 , D – 000 8. kör: H – 111, G – 110, B – 101, E – 100, F – 011, C – 010 , D – 001 , A – 000
idő 1
2
A
1
0
C
1
1
D
1
0
E
0
Gombos Gergő
3
4
5
1
0
1
1
6
7
8
1
adat
9
10
1
adat
11
Adat adat
0
0 Szám.háló 2012 ősz
7
Adaptív fa bejárás • 1943 –Dorfmana katonák szifiliszes fertőzöttségét vizsgálta • Működés – – – –
0-adik időrésben mindenki küldhet. Ha ütközés történik, akkor megkezdődik a fa mélységi bejárása. A rések a fa egyes csomópontjaihoz vannak rendelve. Ütközéskor rekurzívan az adott csomópont bal illetve jobb gyerekcsomópontjánál folytatódik a keresés. – Ha egy bitrés kihasználatlan marad, vagy pontosan egy állomás küld, akkor a szóban forgó csomópont keresése befejeződik.
Gombos Gergő
Szám.háló 2012 ősz
8
Gyakorló feladat 2. •
Adaptív fabejáró protokoll alkalmazásával tizenhat állomás verseng egy csatorna használatáért. Ha az összes olyan állomás, amelynek prímszáma van, egyszerre kerül adásra kész állapotba, akkor mennyi bit-résre van szükség a versengés feloldására?
Gombos Gergő
Szám.háló 2012 ősz
9
Gyakorló feladat 2.
2,3, 2,3, 5,7, 5,7 11,1 3 Gombos Gergő
2,3
2,3
2
3
5,7
Szám.háló 2012 ősz
5
7
11,1 11 3
13
10
Gyakorló feladat 3 • Számítsa ki a kontrollösszeget a következő üzenethez! – Üzenet: 1101.1101.0010.1000.0101.1000 – Generátor polinóm: x4+x+1
Gombos Gergő
Számítógépes hálózatok
11
Gyakorló feladat 3 • Számítsa ki a kontrollösszeget a következő üzenethez! – Üzenet: 1101.1101.0010.1000.0101.1000 – Generátor polinóm: x4+x+1
• Megoldás: 1111
Gombos Gergő
Számítógépes hálózatok
12
Gyakorló feladat 4. Történt-e hiba az átvitel során, ha a vevő a következő üzenetet kapja: 0000 1011 0001 1101 1111 1100 0011 0101 110001 A generátor polinom x6+x4+x+1.
Gombos Gergő
Számítógépes hálózatok
13
Gyakorló feladat 4. Történt-e hiba az átvitel során, ha a vevő a következő üzenetet kapja: 0000 1011 0001 1101 1111 1100 0011 0101 110001 A generátor polinom x6+x4+x+1. R(x)
≈ 100111 ≠ 000000
Gombos Gergő
Számítógépes hálózatok
14
Gyakorló feladat 5. 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 egy időben akarnak csomagot átvinni. (Adja meg a verseny slot-okat ettől az időpillanattól addig, amíg a protokoll feloldja az ütközést.)
Gombos Gergő
Számítógépes hálózatok
15
Gyakorló feladat 5. 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, amíg a protokoll feloldja a kollíziót.)
2,3, 4,6
2,3
Gombos Gergő
2,3
2
3
4,6
4
Számítógépes hálózatok
6
16
Minimális keretméret • A maximális késleltetés és a CSMA/CD algoritmus közötti összefüggés miatt a keret elküldése minimum 2τ időre van szükség, ahol τ a két legtávolabbi állomás közötti késleltetést jelöli. • Jelölje a H sávszélességet, v a jel terjedési sebességet, 𝑙max a maximális távolságot két állomás között, a τ a maximális propagációs késést és a 𝐷min pedig a minimális keretméretet. Ekkor a következő összefüggés írható fel. • 𝐷min=2τ𝐻 • τ=𝑙max/𝑣
Gombos Gergő
Számítógépes hálózatok
17
Példa • A 802.3 szabványban a maximális távolság két állomás között: 2500 méter. Ez esetben 4 ismétlő van és a vonal 10Mb/s-os sávszélességet feltételezünk. • A legrosszabb esetre 50 μs-ot rögzítettek az RTT értékének. • Azaz minimum 500 bit átvitele kell, ezt kerekítették fel 512bitre (64bájtra).
Gombos Gergő
Számítógépes hálózatok
18
Gyakorló feladat 6. •
Tekintsük egy 1 Gbps CSMA/CD protokoll tervezését maximum 300 méter hosszú rézkábelen való használatra (repeater nincs), melyben az elektromágneses hullámok terjedési sebessége 1.8*108 m/s (0,6*fénysebesség). Mekkora a minimális keret méret? Hogyan határozza ezt meg?
• •
𝐷min=2τ𝐻 τ=𝑙max/𝑣
Gombos Gergő
Számítógépes hálózatok
19
Gyakorló feladat 6. • Tekintsük egy 1 Gbps CSMA/CD protokoll tervezését maximum 300 méter hosszú rézkábelen való használatra (repeater nincs), melyben az elektromágneses hullámok terjedési sebessége 1.8*108 m/s. Mekkora a minimális keret méret? Hogyan határozza ezt meg? – – – – – –
d = l / v = 300 m / 1,8 * 10^8 m/s Tgen >= 2d Tgen = x/c = x/10^9 Mbps x / 10^9 >= 2 * 5/3 *10^-6 Tmingen >= 1/3 * 10^4 s min keretméret = 1/3 * 10^4 bit
Gombos Gergő
Számítógépes hálózatok
20
Gyakorló feladat 7. • 2 állomás 10 Mbps-es hálózat köt össze közvetlen. tudjuk hogy a minimális keretméret 500 byte • - Mekkora lehet a maximális távolság két eszköz között? • Koax kábelen sebesség = 0,6 * 3*10^8 • 𝐷min=2τ𝐻 • τ=𝑙max/𝑣
Gombos Gergő
Számítógépes hálózatok
21
Gyakorló feladat 7. • •
2 állomás 10 Mbps-es hálózat köt össze közvetlen. tudjuk hogy a minimális keretméret 500 byte - Mekkora lehet a maximális távolság két eszköz között? –
x/c = Tgen >= 2d
– – –
500 byte / 10 Mbps >= 2d 4*10^3 bit / 10^7 bit/s >= 2d 2*10^-4 >= d //propagációs késés
– – – –
2*10^-4 >= d = l/r 2*10^-4 s >= 3*10^8 * 0,6 m/s 6*10^4*60% >= l 36km>=l
Gombos Gergő
Számítógépes hálózatok
22
Gyakorló feladat 8. • Mennyi a max prop delay fast ethernet (100Mbps) esetén – kábelek max hossza 200m és 1 Class I repeater tartalmaz amely 0,7 μs késést okoz – kábelek max hossza 205m és 2 Class II repeater tartalmaz amely 0,43μs késést okoz
• Adjuk meg a minimális keretméretet!
• 𝐷min=2τ𝐻 • τ=𝑙max/𝑣
Gombos Gergő
Számítógépes hálózatok
23
Gyakorló feladat 8. •
Mennyi a max prop delay fast ethernet (100Mbps) esetén – –
kábelek max hossza 200m és 1 Class I repeater tartalmaz amely 0,7 μs késést okoz kábelek max hossza 205m és 2 Class II repeater tartalmaz amely 0,46μs késést okoz
•
Adjuk meg a minimális keretméretet!
• • • • • • • • • •
v = 0,6*3*10^8 m/s = 1,8 * 10^8 m/s d = l/v 1- dp = 200m / v = (2/1,8) * 10^-6 s 2- dp = 205m / v = (2,05 / 1,8) * 10^-6 s késleltetés: 1- ds = (2/1,8 + 0,7) * 10^-6 s 2- ds = (2,05/1,8 + 0,92) * 10^-6 s x / 100Mbps >= 2ds 1 - x >= 2* (2/1,8+0,7)*10^2 bit 2 - x >= 2* (2,05/1,8+0,92)*10^2 bit
Gombos Gergő
Számítógépes hálózatok
24
Gyakorló feladat 9. •
Tekintsünk 16 allomást, melyek adaptív fabejárás protokollal visznek át csomagokat. Az állomások azonosítói 0,...,15. Szimulálja a protokoll működését, ha az állomások 0,3,9,11,14 egy időben akarnak csomagot átvinni! (Adja meg a verseny slotokat ettől az időpillanattól addig, amíg a protokoll feloldja a kollúziót.)
Gombos Gergő
Szám.háló
25
Gyakorló feladat 9. •
Tekintsünk 16 allomást, melyek adaptív fabejárás protokollal visznek át csomagokat. Az állomások azonosítói 0,...,15. Szimulálja a protokoll működését, ha az állomások 0,3,9,11,14 egy időben akarnak csomagot átvinni! (Adja meg a verseny slotokat ettől az időpillanattól addig, amíg a protokoll feloldja a kollúziót.)
0,3,9,11, 14
0,3
0,3
0
3
9,11,14
9,11
9
11
14
Gombos Gergő
Szám.háló
26
Gyakorló feladat 10. Egy megosztott kábel használati jogáért 2n állomás egy csoportja verseng adaptív fabejárás protokoll használata mellett. Egy adott pillanatban kettő közülük adásra kész lesz. Minimálisan illetve maximálisan hány időrés szükséges a fa bejárásához?
Gombos Gergő
Szám.háló 2012 ősz
27
Gyakorló feladat 10. • Minimális: 3 lépés • Maximális: (log2 2n)*2 + 1
Gombos Gergő
Szám.háló 2012 ősz
28
Feladat 11 Tekintsünk az adatkapcsolati rétegben egy bájt alapú protokollt, amely bájt beszúrást használ. Legyen p annak a valószínűsége, hogy egy bájt hibásan kerül átvitelre. Összesen m keretet küldünk. Legyen n a keretek összhossza (azaz a médiumon áthaladó bájtok száma). a. Határozza meg a bájt hibák várható értékét. b. Határozza meg a hibásan fogadott keret-határoló FLAG-ek számának várható értékét. c. Tegyük fel, hogy egy FLAG bájt gyakorisága az (eredeti) adatokban 1/256. Határozza meg a hibás FLAG bájtok számának a várható értékét a hasznos adatok között. Emlékeztető: Ha egy esemény q valószínűséggel következik be egy kísérlet során és a független kísérletek száma k, akkor az esemény bekövetkezéseinek a számának a várható értéke kq.
Gombos Gergő
Szám.háló
29
Feladat 11 Tekintsünk az adatkapcsolati rétegben egy bájt alapú protokollt, amely bájt beszúrást használ. Legyen p annak a valószínűsége, hogy egy bájt hibásan kerül átvitelre. Összesen m keretet küldünk. Legyen n a keretek összhossza (azaz a médiumon áthaladó bájtok száma).
• Határozza meg a bájt hibák várható értékét. 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 • Határozza meg a hibásan fogadott keret-határoló FLAG-ek számának várható értékét. 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
Gombos Gergő
Szám.háló
30
Feladat 11 •
Tegyük fel, hogy egy FLAG bájt gyakorisága az (eredeti) adatokban 1/256. Határozza meg a hibás FLAG bájtok számának a várható értékét a hasznos adatok között.
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, ezek gyakorisága 1/256, tehát 256 byte-nyi átküldendő adatban átlagosan egy flag-byte,ezért átlagosan 256 átküldendő byte-ot 257 byte-on ábrázolunk. Hogy ezek közül pont a flag byte-ot értelmezzük rosszul, annak várható értéke:
1 p p( n 2m) ( n 2m) 257 257
Gombos Gergő
Szám.háló
31
Vége
