Számítógépes Hálózatok és Internet Eszközök 2011 11. Hálózati réteg – Multicast
Hálózatok, 2011
1
Lukovszki Tamás
Broadcast és Multicast Broadcast routing Egy csomagot (másolatot) minden más csomópontnak el kell küldeni Megoldások: A hálózat elárasztása (flooding) Jobb: Konstruáljunk egy minimális feszítıfát Multicast routing Az adatokat egy küldıtıl egyidejőleg több fogadóhoz kell eljuttatni Real time Streaming, Web-cache update, IPTV, Multi-player játékok Telefon-, Videokonferencia (all-to-all multicast), …
Hálózatok, 2011
2
Lukovszki Tamás
Multicasting Naív megoldás: Multicast-via-Unicast: A küldı egy külön másolatot küld az adatokról minden fogadónak. Nagyon inefficiens: A küldött csomagok száma sokkal nagyobb, mint ami szükséges lenne (különösen rossz all-to-all multicast esetén). Egy multicast-fa felepítése segítségével: Minden linken csak egyszer továbbítódik egy csomag. A routerek döntik el, hogy egy csomagot több linken is továbbítanak-e. fogadó
fogadó
fogadó
Küldı
fogadó
Küldı
fogadó
Naív megoldás Hálózatok, 2011
fogadó
fogadó
Multicast-fa 3
fogadó
Lukovszki Tamás
IP Multicast Címek Class D IP címek 224.0.0.0 – 239.255.255.255 Egy multicast-csoport (group) minden tagja ugyanazt a címet használja Group ID
1 11 0
Cím allokálása Jól ismert (well-known) multicast címeket az IANA (Internet Assigned Numbers Authority) adja ki Átmeneti (Transient) multicast címek dinamikusan allokálhatók és visszadhatók
Hatralévı rész: Jim Kurose (UMASS) foliái alapján
Hálózatok, 2011
4
Lukovszki Tamás
Multicast Routing: A megoldandó probléma Cél: találjunk egy fát (vagy fákat), amely összeköti azokat a routereket, melyek lokális hálózatában van olyan állomás, amely tagja a multicast csoportnak fa: nem tartalmaz kört (nem minden utat használ a routerek között) forrás alapú (source-based): minden forrástól külön fa a fogadókhoz osztott fa (shared tree): ugyanazt a fát használja a csoport minden tagja
Osztott fa Hálózatok, 2011
Forrás alapú fák 5
Lukovszki Tamás
Módszerek multicast fák felépítésére Módszerek: source-based tree (forrás alapú fa): küldınként egy fa legrövidebb utak fája utak megfordítása (reverse path forwarding) group-shared tree: a csoport ugyanazt a fát használja Steiner fa center-based trees
…elıször áttekintjük az alap módszereket, majd a specifikus protokollokat, hogy hogyan használják ezeket a módszereket
Hálózatok, 2011
6
Lukovszki Tamás
Legrövidebb utak fája (Shortest Path Tree) multicast forwarding tree: a legrövidebb utak a küldıtıl minden fogadóhoz Dijkstra algoritmusa
S: küldı R1 1
2
R4
R2 3
Router, amelyhez nem kapcsolódik csoport tag
5 4
R3 R6
Hálózatok, 2011
router, melyhez kapcsolódik csoport tag
R5 6 R7
i
link, melyet használunk a továbbításhoz, i jelzi, hanyadikként adta hozzá az algoritmus
7
Lukovszki Tamás
Utak megfordítása (Reverse Path Forwarding) Azon alapul, hogy a routerek tudják a legrövidebb utat a küldıhöz Minden router a következı szabály szerint továbbítja a csomagot:
if (multicast datagramot fogadunk a küldı felıl a regrövidebb úton a bejövı linken) then minden kimenı linken továbbítjuk a datagramot (elárasztás) else ignoráljuk a datagramot
Hálózatok, 2011
8
Lukovszki Tamás
Reverse Path Forwarding: példa S: küldı R1
R4
router, melyhez kapcsolódik csoport tag
R2 router, melyhez nem kapcsolódik csoport tag
R5
datagram továbbítódik
R3 R7
R6
datagram nem továbbítódik
• Az eredmény egy küldı-specifikus fordított legrövidebb utak fája – Aszimmetrikus linkek esetén rossz választás lehet
Hálózatok, 2011
9
Lukovszki Tamás
Reverse Path Forwarding: A fa “visszavágása” (pruning) A fa tartalmazhat részfákat, melyekben egyetlen egy multicast csoport tag sincs. Ilyen részfákba nem kell a datagramokat továbbítani “prune” üzeneteket küldenek visszafelé azok a routerek, amelyekhez tartozó részfában nincs csoport tag
S: küldı R1
router, melyhez kapcsolódik csoport tag
R4
R2
router, melyhez nem kapcsolódik csoport tag
P P
R5 R3 R6 Hálózatok, 2011
P R7 10
“prune” üzenet linkek melyek megmaradnak a multicast forgalomhoz Lukovszki Tamás
Shared-Tree: Steiner fa Steiner fa: egy fa, amely minden routert összeköt, amelyhez kapcsolódik multicast csoport tag Minimum Steiner fa: minimális költségő fa, amely minden routert összeköt, amelyhez kapcsolódik multicast csoport tag A minimum Steiner fa kiszámítása NP-teljes probléma kiváló heurisztikák léteznek a gyakorlatban nem használják: számítási bonyolultság a teljes hálózatról szükséges információ monolitikus: újraszámítás, ha egy új router csatlakozik a hálózathoz, vagy egy elhagyja a hálózatot
Hálózatok, 2011
11
Lukovszki Tamás
Centrum alapú fák (Center-based trees) Egy közös fát használ mindenki Egy routert azonosítunk a fa centrumaként Kapcsolódás a fához: A csatlakozni kívánó router küld egy unicast join-üzenetet a centrum-routernek A „join”-üzenetet közbensı routerek továbbítják a centrumrouternek A „join”-üzenet elér egy olyan routert, amely már benne van a fában (legrosszabb esetben a centrum-routert) Az út, amin a by „join”-üzenet továbbítódott, egy új ága lesz a fának, amely az elért routerbıl ágazik le
Hálózatok, 2011
12
Lukovszki Tamás
Centrum alapú fák: egy példa Tegyük fel, hogy R6 lett centrumnak választva:
R1 3 R2
router, amelyhez kapcsolódik csoport tag
R4
router, amelyhez nem kapcsolódik csoport tag
2 R5
1
R3 1
Hálózatok, 2011
R6
az utak sorrendje, amelyeken „join”-üzenetek továbbítódnak
R7
13
Lukovszki Tamás
Internet Multicasting Routing: DVMRP DVMRP: distance vector multicast routing protocol, RFC1075 flood-and-prune (elárasztás és visszavágás): reverse path forwarding (RPF), source-based tree Egymással kommunikáló DVMRP routerek felépítenek egy RPF fát, amelyet a DVMRP saját routing tábláiban tárol Semmit sem teszünk fel a DVMRP routerek között felhasznált unicastról A multicast csoportot inicializáló datagram mindenfelé továbbítódik RPF-elárasztást használva Azok a routerek, melyek nem kívánnak csatlakozni a fához, „prune”-üzenetet küldenek vissza
Hálózatok, 2011
14
Lukovszki Tamás
DVMRP: folytatás… soft state: DVMRP router periodikusan (1 percenként) “elfelejti” a visszavágott (pruned) ágakat: A multicast adatok továbbfolynak a nemvisszavágott ágba A router egy ilyen ágban vagy megint visszaküld egy „prune”-üzenetet vagy tovább fogadja az adatokat Routerek gyorsan tudnak csatlakozni a fához Miután egy szomszédos állomástól IGMP „join”-üzenetet kaptak Általánosan implementált kommerciális routerekben Mbone routing DVMRP-t használ
Hálózatok, 2011
15
Lukovszki Tamás
Alagút (Tunneling) Hogy lehet összekötni a multicast routereket az unicast routerek „tengerében”?
Logikai topológia
Fizikai topológia
A multicast datagramot beágyazzuk egy „normális” (nem-multicastcímzéső) datagram belsejébe A „normális” IP datagram-ot rendes IP unicast-ot használva „egy alagúton” küldjük a fogadó multicast routerhez A fogadó multicast router „kiágyazza” multicast datagramot az unicast datagram belsejébıl Hálózatok, 2011
16
Lukovszki Tamás
PIM: Protocol Independent Multicast Nem függ semmilyen specifikus unicast routing algoritmustól (mindegyikkel mőködik) Két különbözı multicast scenárió : Sőrő:
Ritka:
A csoport tagjai sőrőn helyezkednek el egymáshoz közel
A hálózatok száma, melyek tartalmaznak csoport tagot, összehasonlítva a kapcsolódó hálózatok számával, alacsony
Sávszélesség bıven rendelkezésre áll
Hálózatok, 2011
A csoport tagjai nagy távolságra szétszórtak Sávszélesség nem áll olyan bıségesen rendelkezésre 17
Lukovszki Tamás
A sőrőség / ritkaság következményei: Sőrő: A routereknél feltételezzük a csoport tagságot, addig amíg a router explicit „prune” ızenetet küld A multicast fa konstrukciója adatok által irányított (pl. RPF) Sávszélességet és a nem-csoportrouterek erıforrását pazarolja
Hálózatok, 2011
18
Ritka: Amíg a router nem kapcsolódik explicit, addig nincs csoport tagsság A multicast fa konstukciója fogadó által irányított (pl., centrum alapú fa) Sávszélességet és a nem-csoportrouterek erıforrását konzervatívan használja
Lukovszki Tamás
PIM Sőrő Mód (PIM Dense Mode) flood-and-prune RPF, hasonló a DVMRP-hez, de A felhasznált unicast protokoll routing tábláját használja az RPF-hez Kevésbé bonyolult (kevésbé hatékony) elárasztás lefelé, mint amit DVMRP használ, csökkenti a függést a felhasznált routing algoritmustól tartalmaz olyan protokoll mechanizmusokat, amellyel egy router kideríti, hogy levél csomópont-e a fában
Hálózatok, 2011
19
Lukovszki Tamás
PIM – Ritka Mód (PIM Sparse Mode) Centrum alapú fa felépítése A kapcsolódó router „join” üzenetet küld a rendezvous ponthoz (RP) Közbensı routerek aktualizálják az állapotukat és továbbítják a „join” üzenetet Miután az RP átal kapcsolódott a router, a router átválthat forrás alapú fára Növekszik az átvitel: kevésbé centralizált, rövidebb utak Hálózatok, 2011
R1
R4
join R2
join R5 join
R3
R7 R6
Minden adat multicast rendezvous a rendezvous pont pontból
20
Lukovszki Tamás
PIM – Ritka Mód Küldı(s): Az adatot unicasttal küldi a RPnak, ami lefelé elosztja a fában, amelynek az RP a centruma A RP kibıvítheti a multicast fát a forráshoz A RP küldhet „stop” üzenetet, ha nincs fogadó “senki se hallgat!”
R1
R4
join R2
join R5 join
R3
R7 R6
Minden adat multicast rendezvous a rendezvous pont pontból
Hálózatok, 2011
21
Lukovszki Tamás
Multicast Scope Control – kicsi TTL esetén Táguló győrő keresés (expanding ring search) a csoport egy közeli részhalmazának megtalálásához
1. 2. 3. 4.
s 1
5. 6.
2
Kezdetben TTL=1 Multicast query, Várunk a válaszra Ha nincs válasz, növeljük a TTL-t Ha TTL=max, hiba goto 2.
3
Hálózatok, 2011
22
Lukovszki Tamás
Multicast Scope Control – Nagy TTL esetén Adminisztratív TTL korlát a multicast forgalmat az adminisztratív domain-en belül tartja, pl. biztonsági vagy erıforrás okokból
A domain-en kívüli Internet
Ezken a linkeken beállítunk egy TTL korlátot. Ha a korlát > TTL a csomagban, eldobja a csomagot Konvenciók: 0: azonos állomás, 1: azonos alhálózat, 15: azonos hely 63: azonos régió, 127: világszerte, 191: világszerte, korlátos sávszélességgel, 255: korlátlan
Egy adminisztratív domain
Hálózatok, 2011
23
Lukovszki Tamás
Multicast Scope Control Administratively-Scoped Addresses (RFC 1112 ) 239.0.0.0 — 239.255.255.255 közti címeket használ Támogat átfedı (nem csak egymásba ágyazott) domain-eket is
A domain-en kívüli Internet
Cím korlátot állítunk be ezen linkek interface-ein
Egy adminisztratív domain Hálózatok, 2011
24
Lukovszki Tamás
