ECE544Lec6DR15.ppt

8/18/2019 ECE544Lec6DR15.ppt

1/57

ECE544: Communication Networks-II

Spring 2015

D. Reininger

Lecture 6

Includes teaching materials from L. Peterson, J. Kurose, K. Almeroth

8/18/2019 ECE544Lec6DR15.ppt

2/57

IP Multicast

•Introduction•Internet Group ManagementProtocol (IGMP)

•Routing Protocols

–Intra-domain (DVMRP M!"P# PIM)–Inter-domain (M$GP M"DP) – notco%ered &ere

8/18/2019 ECE544Lec6DR15.ppt

3/57

Multicast: one sener to man! recei"ers • Multicast' act o sending datagram to multiplerecei%ers it& single *transmit+ operation– !ne-to-man, man,-to-man,

• uestion' &o to ac&ie%e multicast

Multicast %ia unicast

• source sends unicast datagramsone addressed toeac& o recei%ers– Redundant traicaround sender

– /eep trac0 o all

t&e IP addresses tosend to

multicast recei"er #re$

not a multicast recei"er

%outers &orwar

unicast atagrams

8/18/2019 ECE544Lec6DR15.ppt

4/57



etor0 multicast

(IP Multicast)

• Routers acti%el,

participate inmulticast ma0ingcopies o pac0ets asneeded and

orarding toardsmulticast recei%ers

Multicast routers (red) duplicate and

forward multicast datagrams

8/18/2019 ECE544Lec6DR15.ppt

5/57



1pplication-la,ermulticast (P2P)

• end s,stems

(*&osts+) in%ol%edin multicast cop,and orard unicastdatagrams amongt&emsel%es

• *&ost+ 3ecomes

P2P 'osts uplicate an

&orwar multicast atagrams

8/18/2019 ECE544Lec6DR15.ppt

6/57

Internet Multicast Ser"ice Moel

multicast group concept'

– 4ac& group &as its on IP multicast address

– 1 &ost can 5oin or lea%e reel,

– Routers orard multicast datagrams (it& destinationaddress o t&e groups multicast address) to &osts t&at&a%e *5oined+ t&at multicast group

12()11*)40)1(+

12()5*)1+)12

12(),4)10()+,

12(),4)10()+0

multicastgroup

22+)1),0)1*

8/18/2019 ECE544Lec6DR15.ppt

7/57

Multicast groups

class D Internet addresses reser%ed ormulticast'

&ost group semantics'o an,one can *5oin+ (recei%e) or lea%e multicastgroup

o an,one (not e%en a mem3er) can send to multicastgroup

o no netor0-la,er identiication o &osts mem3ers

needed: inrastructure to deli%er mcast-addresseddatagrams to all &osts t&at &a%e 5oined t&atmulticast group

8/18/2019 ECE544Lec6DR15.ppt

8/57

Mapping IP Multicast .ressto Et'ernet .ress

• 4t&ernet M17 1ddresses' 89 3its

– 3roadcast' all 1s '''''

– multicast' multicast lag (t&e loest 3it

o t&e :st octet); :•

8/18/2019 ECE544Lec6DR15.ppt

9/57

IP"+ Multicast .resses#%/C 2,5$

• lo-order lag indicates permanent @transient groupA t&ree ot&er lagsreser%ed

• scope ield' : - node local–2 - lin0-local

–= - site-local–9 - organiBation-local–$ - communit,-local–4 - glo3al

–(all ot&er %alues reser%ed)

4 112 bits8

group IDscopeflags11111111

4

8/18/2019 ECE544Lec6DR15.ppt

10/57

oining a mcast group: two-step process

• local: &ost inorms local mcast router odesire to 5oin group' IGMP (Internet Group

Management Protocol)

• wide area: local router interacts it& ot&errouters to recei%e mcast datagram lo

– man, protocols (e.g. DVMRP M!"P# PIM)

IMP

IMP

IMP

wie-areamulticast

routing

8/18/2019 ECE544Lec6DR15.ppt

11/57

IMP: Internet roup Management Protocol

• host: sends IGMP report &en application5oins mcast group

– IPC1DDCM4M$4R"IP soc0et option

– &ost need not eEplicitl, *un5oin+ group&en lea%ing

• router: sends IGMP Fuer, at regularinter%als

– &ost 3elonging to a mcast group mustrepl, to Fuer,

uer! report

8/18/2019 ECE544Lec6DR15.ppt

12/57

3ow IMP orks

• on eac& lin0 one router is elected t&e *Fuerier+

• Fuerier periodicall, sends a Mem3ers&ip uer, messageto t&e all-s,stems group (228.

8/18/2019 ECE544Lec6DR15.ppt

13/57

3ow IMP orks #cont)$

• &en a &osts timer or group G eEpires it sends aMem3ers&ip Report to group G it& L ; :

• ot&er mem3ers o G &ear t&e report and stop t&eir timers

• routers &ear all reports and time out non-respondinggroups

Q

G G G G

8/18/2019 ECE544Lec6DR15.ppt

14/57

Source Speci&ic Multicast

• "ource "peciic Multicast' arecei%ing &ost speciies

(source mcast group) to 5oin– recei%e multicast pac0ets addressedto t&e group and onl, i t&e, arerom t&e speciic sender (one-to-

man,)• 1n, source multicast (1"M)'man,-to-man,

8/18/2019 ECE544Lec6DR15.ppt

15/57

IMPIGMP version 1

• router: ostMem3ers&ip uer,msg 3roadcast onL1 to all &osts

• host: ostMem3ers&ip Reportmsg to indicate

group mem3ers&ip– randomiBed dela,3eore responding

– implicit lea%e %iano repl, to uer,

• R#7 :::2

IGMP v2: additions

include• group-speciic uer,

• Lea%e Group msg– last &ost repl,ing to

uer, can send eEplicitLea%e Group msg

– router perorms group-speciic Fuer, to see ian, &osts let in group

– R#7 22?6

IGMP v3:– Hoin@Lea%e speciic " inG

– R#7 ??>6

8/18/2019 ECE544Lec6DR15.ppt

16/57

Multicast %outing: Prolem Statement

• Goal: ind a tree (or trees)connecting routers &a%ing local mcastgroup mem3ers– tree: not all pat&s 3eteen routers used

– source-based: dierent tree rom eac& sender torc%rs

– shared-tree: same tree used 3, all group mem3ers

Source-ase trees S'are tree

8/18/2019 ECE544Lec6DR15.ppt

17/57

.pproac'es &or uiling mcast trees

1pproac&es'

• source-3ased tree' one tree per source– s&ortest pat& trees

– re%erse pat& orarding

• group-s&ared tree' group uses one tree– minimal spanning ("teiner)

– center-3ased trees

6we &irst look at asic approac'es7 t'en speci&icprotocols aopting t'ese approac'es

8/18/2019 ECE544Lec6DR15.ppt

18/57

S'ortest Pat' 8ree

• mcast orarding tree' tree o s&ortestpat& routes rom source to all recei%ers– Di50stras algorit&m

%1

%2

%,

%4

%5

%+ %

21

+

, 4

5

i

router wit' attac'egroup memer

router wit' no attac'egroup memer

link use &or &orwaring7i inicates orer linkae ! algorit'm

9EENS: source

8/18/2019 ECE544Lec6DR15.ppt

19/57

%e"erse Pat' /orwaring

if (mcast datagram recei%ed on incoming lin0 ons&ortest pat& 3ac0 to source)

then lood datagram onto all outgoing lin0s else ignore datagram

rel! on router;s knowlege o& unicasts'ortest pat' &rom it to sener

eac' router 'as simple &orwaring e'a"ior:

8/18/2019 ECE544Lec6DR15.ppt

20/57

source

8/18/2019 ECE544Lec6DR15.ppt

21/57

source

8/18/2019 ECE544Lec6DR15.ppt

22/57

%e"erse Pat' /orwaring: e=ample

> result is a source-speci&ic re"erse SP8

? ma! e a a c'oice wit' as!mmetric links

%1

%2

%,

%4

%5

%+ %



atagram will e&orware

9EENS: source

atagram will not e&orware

8/18/2019 ECE544Lec6DR15.ppt

23/57

%e"erse Pat' /orwaring: pruning• orarding tree contains su3trees it& nomcast group mem3ers

– no need to orard datagrams donsu3tree

– *prune+ msgs sent upstream 3, routerit& no donstream group mem3ers

%1

%2

%,

%4

%5

%+ %



prune message

9EENS: source

links wit' multicast&orwaring

P

P

P

8/18/2019 ECE544Lec6DR15.ppt

24/57

S'are-8ree: Steiner 8ree

• "teiner ree' minimum cost tree connectingall routers it& attac&ed group mem3ers

• pro3lem is P-complete

• eEcellent &euristics eEists• not used in practice'

– computational compleEit,

– inormation a3out entire netor0 needed

– monolit&ic' rerun &ene%er a router needs to5oin@lea%e

8/18/2019 ECE544Lec6DR15.ppt

25/57

Center-ase trees

• single deli%er, tree s&ared 3, all• one router identiied as “center” otree

• to 5oin'– edge router sends unicast join-msg addressed to center router

– join-msg *processed+ 3, intermediate

routers and orarded toards center– join-msg eit&er &its eEisting tree 3ranc&or t&is center or arri%es at center

– pat& ta0en 3, join-msg 3ecomes ne 3ranc&

o tree or t&is router

8/18/2019 ECE544Lec6DR15.ppt

26/57

Center-ase trees: an e=ample

Suppose %+ c'osen as center:

%1

%2

%,

%4

%5

%+ %



pat' orer in w'ic' @oin

messages generate

9EEN

21

,

1

8/18/2019 ECE544Lec6DR15.ppt

27/57

Current Intra-omain

Multicast %outing ProtocolsDVMRP Distance-Vector Multicast RoutingProtocol

lood-and-prune

unidirectional per-source trees3uilds on routing ta3le

M!"P# Multicast 4Etensions to !pen "&ortest-

Pat& #irst Protocol

3roadcast mem3ers&ipunidirectional per-source trees

uses !"P# routing ta3le

8/18/2019 ECE544Lec6DR15.ppt

28/57

Current Intra-omain Multicast%outing Protocols #cont)$

PIM-DM Protocol-Independent Multicast Dense-Mode

3roadcast-and-pruneunidirectional per-source trees

uses unicast routing table (Protocol Independent)PIM-"M Protocol-Independent Multicast "parse-Mode

uses meeting places (*rendeB%ous points+)

unidirectional per-group or s&ared treesuses unicast routing table (Protocol Independent)

7$ 7ore-$ased rees

uses meeting places (*cores+)3idirectional s&ared treesuses unicast routing ta3le

8/18/2019 ECE544Lec6DR15.ppt

29/57

8'e /irst Intra-omain%outing Protocol: AM%P

l

8/18/2019 ECE544Lec6DR15.ppt

30/57

istance-Aector Multicast%outing Protocol #AM%P$

DVMRP consists o to ma5or components'

(:)a con%entional distance-%ector routing protocol (li0e RIP) &ic& 3uilds in eac& router a routing ta3le li0et&is'

(2) a protocol or determining &o to orard multicast pac0ets 3ased on t&e routing ta3le and routing messages

Subnet(Destination)

shortest dist(cost)

via interface(NextHop)

a 1 i1

b 5 i1

c 3 i2… … …

8/18/2019 ECE544Lec6DR15.ppt

31/57

E=ample 8opolog!

g g

s

g

8/18/2019 ECE544Lec6DR15.ppt

32/57

P'ase 1: 8runcate

8/18/2019 ECE544Lec6DR15.ppt

33/57

P'ase 2: Pruning

g g

s

prune (s,g)

prune (s,g)

g

8/18/2019 ECE544Lec6DR15.ppt

34/57

Stea! State

g g

s

g

g

8/18/2019 ECE544Lec6DR15.ppt

35/57

graft (s,g)

graft (s,g)

ra&ting on New %ecei"ers

g g

s

g

g

report (g)

8/18/2019 ECE544Lec6DR15.ppt

36/57

Stea! State a&ter ra&ting

g g

s

g

g

8/18/2019 ECE544Lec6DR15.ppt

37/57

Multicast %outing: MBSP/

8/18/2019 ECE544Lec6DR15.ppt

38/57

Multicast BSP/ #MBSP/$

• an eEtension to !"P# (!pen "&ortest-Pat&#irst)a lin0-state intra-domain routing protocol

speciied in R#7s :=98 J :=9=

• multicast-capa3le routers indicate t&atcapa3ilit, it& a lag in t&eir lin0-statemessages

• routers include in t&eir lin0-state messagesa list o all groups t&at &a%e mem3ers on t&erouters directl,-attac&ed lin0s (as learnedt&roug& IGMP)

8/18/2019 ECE544Lec6DR15.ppt

39/57

S1

R1

R2

X

Y

Link state: each router floods link-state advertisementMulticast: add membership information to “link state”

Each router then has a complete map of the topology, includingwhich links have members of which multicast groups

Z

8/18/2019 ECE544Lec6DR15.ppt

40/57

S1

R1

R2

X

Y

Z has network map, including membership at X and YZ computes shortest path tree from S1 to X and YZ builds multicast entry with one outgoing interfaceW, Q, R, each build multicast entries

Z

W

Q

R

8/18/2019 ECE544Lec6DR15.ppt

41/57

R1

R2

X

Y

Z

W

Q

R

S1

Link-state advertisement with new topology (may be due to link failure)may require recomputation of tree and forwarding entry.Link WZ failed in the diagram below.

8/18/2019 ECE544Lec6DR15.ppt

42/57

R1

R2

X

Y

Z

W

Q

R

S1

T

R3

Link state advertisement (T) withnew membership (R3) may requireincremental computation and addition of interface to outgoing interfacelist (Z) (Similarly, disappearance of a membership may cause deletionan interface from an outgoing interface list). LinkWZ is back to normal.

8/18/2019 ECE544Lec6DR15.ppt

43/57

Multicast %outing: PIM

Protocol Inepenent

8/18/2019 ECE544Lec6DR15.ppt

44/57

Protocol InepenentMulticast #PIM$

> Protocol InepenentD? does not perform its own routing information exchange

? uses unicast routing tale mae ! an! o& t'e e=isting unicastrouting protocols

> PIM-M #ense Moe$ - similar to AM%P7 ut:? wit'out t'e routing in&ormation e=c'ange part

? i&&ers in some minor etails

> PIM-SM #Sparse Moe$7 or @ust PIM - instea o&

irectl! uiling per-source7 s'ortest-pat' trees:? initially builds a single (unidirectional) tree per group ,

shared by all senders to that group

? once ata is &lowing7 t'e s'are tree can e con"erte to a per-source7 s'ortest-pat' tree i& neee

8/18/2019 ECE544Lec6DR15.ppt

45/57

PIM Protocol B"er"iew

• $asic protocol steps

– routers it& local mem3ers send Join messages

toards a Rendezvous Point (RP) to 5oin s&aredtree

– routers it& local sources encapsulate data toRP

– routers it& local mem3ers ma, initiate data-dri%en sitc! to source"speci#ic$ s!ortest"pat!tree

8/18/2019 ECE544Lec6DR15.ppt

46/57

RP

R1

R2 R3

R4

Join message

toward RP

Shared tree after

R1,R2,R3 join

P'ase 1:

8/18/2019 ECE544Lec6DR15.ppt

47/57

P'ase 2: Sources Sen to %P

RP

R1

R2 R3

R4

S1

unicast encapsulated

data packet to RPRP decapsulates,

forwards down

Shared treeS2

PIM

Register

P' , St E l ti

8/18/2019 ECE544Lec6DR15.ppt

48/57

P'ase ,: Stop Encapsulation

RP

R1

R2 R3

R4

S1

Join G for S1Join G for S2

S2

(S1,G)

(S1,G)

(*.G)

(S2,G)

8/18/2019 ECE544Lec6DR15.ppt

49/57

P'ase 4: Switc' to S'ortest Pat' 8ree

R1

R2 R3

R4

Join messages

toward S2

shared tree

S1

S2

RP

P' 5 P # 2 &&$ ' 8

8/18/2019 ECE544Lec6DR15.ppt

50/57

P'ase 5: Prune #S2 o&&$ S'are 8ree

R1

R2 R3

R4

S1

S2 distribution tree

Shared tree

Prune S2 off Shared tree

where iif of S2 and

RP entries differS2

RP

8/18/2019 ECE544Lec6DR15.ppt

51/57

56

8oa!;s 3omework• Peterson J Da%ie 7&ap 8

8.86

8.=2

8.=9

Due on #rida, ?@6A Reminder' Midterm 3%13

8/18/2019 ECE544Lec6DR15.ppt

52/57

5

%e"iew Items &or Mi-8erm #1$• op-don design

– &o to e%aluate &ig&-le%el reFuirementsand map to a netor0 topolog, J ma5orcomponents

– draing a netor0 diagram it&sitc&es routers etc.

– draing t&e protocol stac0s at eac&netor0 element

– 4%aluating 3asic traic los atdierent lin0s@nodes in t&e netor0

– 1nal,sis o ireless co%eragereFuirements in terms o p&,sicalco%erage and traic load

8/18/2019 ECE544Lec6DR15.ppt

53/57

5!

%e"iew Items &or Mi-8erm #2$• "&ared Media Protocols

– $asic Principles– 1L!1 "lotted 1L!1 7"M1– &roug&put eFuations or simple cases– Details o 4t&ernet@9

8/18/2019 ECE544Lec6DR15.ppt

54/57

5"

%e"iew Items &or Mi-8erm #,$• "itc&ing

– "itc&ing %s s&ared media– 4t&ernet 3ridging and sitc&ing– "el learning 4t&ernet sitc&–"panning tree algorit&m J protocol– 1M sitc&ing principles

– Virtual circuits and related signalingprotocols

– 1M 11Ls– 1M perormance calculations

8/18/2019 ECE544Lec6DR15.ppt

55/57

6#

%e"iew Items &or Mi-8erm #4$• IP Routing $asics

– IP%8 principles and protocol structure– D7P 1RP etc– Routing algorit&ms' DV and Di50stra

– Routing algorit&m numerical pro3lems– RIP and !"P# protocols– Loop remo%al in RI#– !"P# L"P looding algorit&m– 7alculating routing o%er&eads

8/18/2019 ECE544Lec6DR15.ppt

56/57

6$

%e"iew Items &or Mi-8erm #5$• IP Routing 1d%anced

– 7IDR addressing– umerical eEamples it& 7IDR routing ta3le– $GP routing principles

– $GP protocol speciicsA orarding ta3lesreac&a3ilit, ad%ertisements longest preiEmatc&

– IP%6 main eatures and dierences it&IP%8

8/18/2019 ECE544Lec6DR15.ppt

57/57

6%

%e"iew Items &or Mi-8erm #+$• IP Multicast

– IP multicast principles– IGMP 3asics– "ource trees and re%erse pat& routing

– "&ared trees– ree setup and 5oin@lea%e e%ents– RendeB%ous Point (RP) and related met&ods– M!"P# DVMRP and PIM@"M protocols aseEamples

Documents

ECE544Lec6DR15.ppt