Összefoglalás és gyakorlás
High Speed Networks Laboratory
1 / 28
Hálózatok jellemző paraméterei
High Speed Networks Laboratory
2 / 28
Evolúció alkotta adatbázis • Önszerveződő adatbázis = (struktúra, lekérdezés) • Megtervezett adatbázis → evolúció alkotta adatbázis
Elosztott adatbázisok: A kommunikációs költségek csökkenése. Mindenki a számára ismerős adatokat gondozza. Egy-egy csomópont kiesése esetén a többi adatai továbbra is elérhetőek. • Lehetséges a moduláris tervezés, a rugalmas konfigurálás. • • • •
• Rugalmasabb adatstruktúra kell • Önszerveződő adatbázisok: • A kapcsolódást nem egy központi egység határozza meg • A csomópontok saját maguk döntik el, hova kapcsolódnak 3 / 28
Számunkra jelenleg lényeges paraméterek 1. Hálózat méret: Csomópontok száma • Ezres, milliós, esetleg milliárdos méretek esetén lehet statisztikai adatokkal jól jellemezni egy hálózatot 2. Klaszterezettség: “Csoportosulás” mértéke • A szomszéd node-jaim kapcsolódnak-e egymáshoz? Ha 1 akkor mindig, ha 0 akkor soha! 3. Átmérő: Kis átmérő, rövid utak, “kisvilág” jelleg • Egy rácsban igen nagy átmérők lehetnek, míg pl. a teljes gráf átmérője 1. 4. Hasonlósági paraméter (γ): Mennyire hasonló a
szerepük? (skálafüggetlen szerkezet) •
Ha a szám magas, akkor az egyének nagyon hasonlítanak, ha alacsony akkor (~ 2) akkor erősen eltérő szerepek vannak
5. Fokszámeloszlás: a csúcsok mekkora hányadának k a
fokszáma?
• Egyenletes? Binomiális? Valami más?
4 / 28
Kisvilág-tulajdonság •
5 / 28
Skálafüggetlenség • A fokszámeloszlás hatványfüggvényt követ
Kialakulásához vezet • Növekedés • Preferenciális kapcsolódás https://www.youtube.com/watch?v=SXaOsz_T5uQ •
•
6 / 28
Gyakorló feladat 1. • Hogyan néz ki egy önszerveződően alakuló hálózat? N=100 E=296 Diam=5 C=0.063
N=100 E=294 Diam=4 C=0.095
7 / 28
Hogyan navigálunk kisvilág hálózatban? Kisvilág-hálózat Kleinberg modellje • Jon Kleinberg: Nem csak a topológia érdekes, hanem hogy gyorsan
meg is lehet találni a célt, térkép nélkül • Az optimális modell kereséshez
High Speed Networks Laboratory
• Távolság: d(u,v) lépkedések
száma a szomszédokon • A rácson két pont között az kapcsolat valószínűsége ~ d(u,v)-r • Mohó keresési algoritmus 8 / 28
Egy Google keresés
9 / 28
Search Engine Optimization + Success Factors
10 / 28
Search Engine Optimization + Success Factors
White Hat
Black Hat
11 / 28
Forgalmi modellezés
High Speed Networks Laboratory
12 / 28
Egyensúly vs optimum • Közösségi költség: a forgalommintához tartozó átviteli idők összege • Egyensúlyi költség: közösségi költség a Nash-egyensúlyi állapotban • Közösségi optimum: a lehető legkisebb közösségi költségű állapot
• Két fontos kérdés: 1. 2.
Van-e egyensúlyi állapotra vezető forgalomminta? Ha igen, van-e olyan, aminek a költsége nincs túl messze a közösségi optimumtól? 13 / 28
Egyensúlyi vs optimális átviteli idő • Optimálsi átviteli idő ≠ egyensúlyi átviteli idő • Braess-paradoxon: upgrade nem feltétlenül javít az átviteli időn • Legjobbválasz-leképezések → Nash-egyensúly • Analízis eszköze: forgalomminta potenciális energiája = travel-time
függvények összege
14 / 28
Forgalmi minta megtalálása az egyensúlyban LEGJOBBVÁLASZ-ALGORITMUS 1. Kiidulás: egy tetszőleges forgalmi minta 2. Ha egyensúly KÉSZ 3. Egyébként: létezik legalább egy csomag, aminek a legjobbválasza a
többire egy gyorsabb út • Válasszunk egy tetszőleges ilyet; az váltson át erre 4. GOTO 2.
• 1. Állítás: Az algoritmus véges sok lépésben megáll • Minden lépésben a forgalomminta potenciális energiája csökken
• 2. Állítás: Az egyensúlyi költség (egyéni átviteli idők összege) a
szociális optimum költségének legfeljebb 2x-ese 15 / 28
Gyakorló feladat 2. • 2.a. 300 csomagot küldünk A B, a lehetséges útvonalak az ábrán
láthatóak. Milyen x és y értékek mellett áll be a Nash-egyensúly?
16 / 28
Gyakorló feladat 2. • 2.b. Létrejön egy új kapcsolat A-ból B-be, amin a csomagok számától
függetlenül 5 az átviteli idő. Mi a Nash-egyensúlyi állapot? Hogyan változik a teljes átviteli idő az a) ponthoz képest?
5
17 / 28
Gyakorló feladat 2. • 2.c. Az A B kapcsolat megszakad, de helyette létrejön egy új, C és D
között, amin 0 idő alatt érnek át a csomagok. Mi a Nash-egyensúlyi állapot? Hogyan változik a teljes átviteli idő?
0
18 / 28
Gyakorló feladat 2. • 2.d. Visszaépül az A B kapcsolat, miközben a C és D közötti is
megmarad. Ebben az esetben mi a Nash-egyensúlyi állapot? Hogyan változik a teljes átviteli idő?
0 5
19 / 28
Gyakorló feladat • Mit tanultunk az egyensúlyi és az optimális átviteli idő viszonyáról? • Hogyan változik a potenciális energia legjobbválasz leképezések
során? • Szemléltesd mindkettőt az alábbi példán!
150
300
0
150
20 / 28
Hálózatok növekedése, vírusterjedés
High Speed Networks Laboratory
21 / 28
Lineáris növekedési modell • Legegyszerűbb: • N(t) = az adatbázis mérete t időpontban • r = növekedési ráta •
d𝑁 d𝑡
= 𝑟 𝑁(𝑡)
• A növekedés üteme időben
állandó r t • Exponenciális növekedés • 𝑁 𝑡 = 𝑁0 𝑒𝑟𝑡 • A hálózat felrobban
• Nem mehet a végtelenségig 22 / 28
Módosítás • Vegyük be a túlnépesedést = túl
sokan vannak • Korlátos erőforrások = a szerver csak bizonyos számú számítógépet tud kiszolgálni • A növekedési ráta nem időben • • • •
állandó Kis N-re r még konstans Egyre jobban csökken K = carrying capacity = teherbírás Ha N>K, akkor negatív: többen hagyják el a hálózatot, mint ahányan jönnek
A növekedési ráta változása az adatbázisban levő számítógépek számának függvényében.
23 / 28
A növekedési modell • A növekedési ráta nem időben állandó • Kis N-re r még konstans • Egyre jobban csökken • K = carrying capacity = teherbírás • Ha N>K, akkor negatív: többen hagyják el a hálózatot, mint ahányan
jönnek • Az egységre eső növekedés: • N-ben lineárisan csökken
• Kapjuk: logisztikus növekedési modell: • Kérdés: N(t) = ? • Meg lehet oldani analitikusan
• És grafikusan 24 / 28
A növekedés mértéke • K/2-ig nő, utána csökken • K után negatív • Két fixpont: a 0 és a K • Először gyorsan nő, aztán
egyre lassabban • A teherbírást ha túllépi, csökkeni fog • Többen hagyják el a hálózatot,
mint ahányan jönnek • 0 fixpont, de instabil: kicsit
megváltozik, akkor K-ba konvergál • K fixpont, stabil: perturbáció hatására oda visszatalál 25 / 28
Vírusterjedés: SIR modell • Vírusterjedés vizsgálata • SIR modell • Természetesen tudni kell, hogy ki kivel érintkezik • S(t),I(t),R(t): fertőződésre hajlamosak, fertőzőek, gyógyultak
száma t-kor
• β = S → I contact rate • ν = I → R recovery rate
Lassú, robbanás, lecsengés 26 / 28
Véletlen immunizálás vs hubok védelme • Ha véletlenszeűen immunizáljuk a csomópontokat: • Kiválasztunk 5 csomópontot • Ezeket + a szomszédaikat immunizáljuk • 24 csomópontot érünk el
27 / 28
Véletlen immunizálás vs hubok védelme • Hubokat immunizáljuk • 1 lépésben ≈ 60 csomópontot érünk el • A hatékony megoldás a
hubok védelme • A hubok azonosítása
felvet némi problémát… • Véletlen node egyik
kapcsolata nagy valószínűséggel egy hub
28 / 28
