Sccs 420 Ch 22-2 (multicast Routing)

Contents

LECTURE 8

• I. Multicast Routing Protocols

Internet Routing Protocols

— Source-based Tree — Group-based Tree — RPF, RPB, and RPM

Chapter 22 Network Layer: Delivery, Forwarding and Routing (Forouzan, Data Communications and Networking, 4th Edition)

2

1

I. MULTICAST ROUTING PROTOCOLS

Figure 22.33 Unicasting

In this section, we discuss multicasting and multicast routing protocols.

Topics discussed in this section:

In unicasting, the router forwards the received packet through only one of its interfaces.

Unicast, Multicast, and Broadcast Applications Multicast Routing Routing Protocols

• One source and one destination, in one-to-one relationship • Both source and destination IP addresses are unicast address 3

4

Broadcasting

Figure 22.34 Multicasting In multicasting, the router may forward the received packet through several of its interfaces.

• One source and all the other hosts are destinations, in one-to-all relationship • Does not explicitly supported in the Internet —Can generate a large amount of traffic

• One source and a group of destinations, in one-to-many relationship • Source IP addresses is unicast address, but destination is a group address — Group address identifies members of the group

5

6

Multicast Applications

Figure 22.35 Multicasting versus multiple unicasting • All multicast packets has the same destination address • In multiple unicasting, source sends five packets, each with a different unicast destination address • email to a group of people Emulation of multicasting through multiple unicasting is not efficient and may create long delays, particularly with a large group. 7

• Distributed databases —Request is made to a group of database servers, and only those that has the information will respond

• Information dissemination —Software update can be sent to all of its purchasers

• Dissemination of news —A single message can be sent to those interested in a particular topics

• Teleconferencing —Every attendees need to receive the same information

• Distance learning 8

Multicast Routing Concept

Figure 22.36 Shortest path tree in unicast routing

• Routing is based on shortest path tree —Root of the tree = source

• In unicast routing, the shortest path to each destination can be obtained from its routing table —The whole routing table is a shortest path tree —Only one tree (or table) is needed • Each multicast group needs its own shortest path tree

—Each router has its own shortest path tree • Some multicast routing protocols use the same tree for all routers

9

Multicast Routing

In unicast routing, each router in the domain has a table that defines a shortest path tree to possible destinations. 10

Figure 22.37 Source-based tree approach

• A multicast packet may have destinations in more than one network • Forwarding a single packet to members of a group requires a shortest path tree —If we have n groups, we may need n shortest path trees In multicast routing, each involved router needs to construct a shortest path tree for each group.

• There are two approaches to reduce complexity —Source-Based Tree —Group-Shared Tree

• In the source-based tree approach, each router needs to have one shortest path tree for each group 11

•Define the next hop for each network with group members

12

Figure 22.38 Group-shared tree approach Figure 22.39 Taxonomy of common multicast protocols

Other routers forward multicast packet to the core router

Link State Multicast Routing

In the group-shared tree approach, only the core router, which has a shortest path tree for each group, is involved in multicasting.

Distance Vector Multicast Routing

Generalization Generalization of DVMRP, of CBT, used used in dense in sparse portion of the portion of the network network

13

14

Multicast Open Shortest Path First (MOSPF)

Distance Vector Multicast Routing Protocol (DVMRP)

• Based on Link State Routing, in which each node need to advertise the state of its link

•

—MOSPF also advertises group member on the link in a new packet called group-membership LSA

•

• Associate unicast address of a host with group address

• Shortest path tree is only constructed when a router receives packet with a multicast destination address —Using Dijkstra’s algorithm —Save on time and space

•

Create multicast routing table by using information from unicast distance vector table DVMRP uses source-based tree approach, but does not actually create a new tree for each group DVMRP is based on four forwarding strategies 1. Flooding: Packet is sent out from every interface except the one from which it was received •

15

May create a loop if the previous copy cannot be identified

2. Reverse path forwarding (RPF): Packet is only forwarded if it has traveled the shortest path from source to the router

16

Figure 22.40 Reverse path forwarding (RPF)

1. R1 extracts the source address from the packet

Figure 22.41 Problem with RPF

2. R1 uses this source address to look up its unicast routing table, to obtain the next hop router and interface 3. If this multicast packet come form the hop defined in the table, the packet is forwarded •

Thick line indicates shortest path tree

RPF eliminates the loop in the flooding process.

17

DVMRP Forwarding Strategies

• RPF does not guarantee that each network receives only one copy, because forwarding is only based on source address • Topology resembles a graph, and not a tree • Net3 has two parents (R2 and R4) and thus receives two copies, one from each parent 18

Figure 22.42 RPF Versus RPB

3. Reverse path broadcasting (RPB): — Define one parent router for each network — A network can receive a multicast packet from a particular source only through a designated parent router — For each source, router send packet only out of those interfaces for which it is the designated parent

4. Reverse path multicasting (RPM): — Flooding, RPF, and RPB are all broadcast packets — RPM introduces two new procedures — If no one want to receive multicast packet, router sends a prune message to its upstream router, excluding its interface from RPM — A graft message is used to reactivate multicast reception

19

RPB creates a shortest path broadcast tree from the source to each destination. It guarantees that each destination receives one and only one copy of the packet. 20

Core-Based Tree (CBT)

Figure 22.43 RPF, RPB, and RPM

•

Group-shared protocol that uses a core as the root of the tree — Only core router has n shortest path trees

•

AS is divided into regions, with one core for each region — Every router knows unicast address of the core router — Router sends unicast join message (similar to grafting message) to core router if it want to join a group •

RPM adds pruning and grafting to RPB to create a multicast shortest path tree that supports dynamic membership changes.

Intermediate router extracts source address and incoming interface from the packet

— Router sends unicast leave message to upstream router if it want to leave 21

22

DVMRP, MOSPF, and CBT

Figure 22.44 Group-shared tree with rendezvous router

•

Tree formation — DVMRP and MOSPF form a tree from the root downward — CBT forms a tree from the leaf upward — DVMRP tree is fully made from broadcast and then pruned — CBT tree is gradually made from joining messages

•

Rendezvous router = core router

23

24

Protocol Independent Multicast (PIM)

Figure 22.45 Sending a multicast packet to the rendezvous router •

•

•

Core router is solely responsible for distributing multicast packets Source sends the multicast packet (encapsulated in a unicast packet) to the core router The core router decapsulates the packet and forwards it to all interested 25 interfaces

PIM-SM (Sparse Mode) •

•

PIM-DM (Dense mode) — In dense network, each router is likely to involve in multicast operation •

Acceptable to use broadcast (RPF with pruning & grafting)

— Similar to DVMRP, but also accommodate link state protocol as well PIM-DM is used in a dense multicast environment, such as a LAN. PIM-DM uses RPF and pruning and grafting strategies to handle multicasting. However, it is independent of the underlying unicast protocol.

26

Figure 22.46 Logical tunneling

PIM-SM (Sparse mode) — In sparse network, each router is unlikely to involve in multicast operation •

CBT is more appropriate

— Similar to CBT, but simpler because it does not require acknowledgement from a join message PIM-SM is used in a sparse multicast environment such as a WAN. PIM-SM is similar to CBT but uses a simpler procedure.

• • • 27

Only a small fraction of Internet routers can multicast Only routers in shaded circle are capable of multicasting Tunneling is needed to provide logical connection 28 between two multicast routers

Figure 22.47 MBONE

• •

Multicast backbone (MBONE) is created out of these isolated multicast routers by tunneling Only DVMRP supports MBONE

29