Multicast Routing

Unicasting vs Multicasting

Unicasting

One source and one destination
- Unicast routers have a forwarding table
- Make the decision according to the packet’s unicast destination address (U-DA)

Multicasting

One source and a group of destinations
- Source IP address: Unicast
- Destination IP address: Multicast (M-DA)
- Multicast routers have another forwarding table
- Make the decision according to the packet’s multicast destination address (M-DA)

Multicasting

Two approaches to achieve multicast:

Multicast via unicast (application-layer multicast)
- Multiple Unicasting: Source sends N unicast datagrams, one addressed to each of N receivers

Network multicast
- Router actively participate in multicast, making copies of packets as needed and forwarding towards multicast receivers

Applications of Multicasting:

Access to Distributed Databases
- Large databases are distributed, i.e., stored in more than one location
- Multiple requests can be sent to a distributed database
Information Dissemination
- Examples: sending software update to all purchasers; sending news.
Teleconferencing
- same information at the same time.
Distance Learning
Live Internet Protocol TV (IPTV)
- A server has many TV channels (Groups)
- A host subscribes any one of the TV channels (Becomes a group member)

To perform Multicasting, we need the following components:

Multicast Addresses - A multicast destination address defines a group of destinations
Forwarding Table - A router needs to know any members of a group connected to it.
- Internet Group Management Protocol (IGMP)
Routing Protocols - Determine the ‘best’ path to all destinations
- Distance Vector Multicast Routing Protocol (DVMRP)
- Multicast Open Shortest Path First (MOSPF)
- Protocol Independent Multicast (PIM)

Internet Multicast Model

Hosts addresses IP datagram to multicast group
Routers forward multicast datagrams to hosts that have “joined” that multicast group

Any host can “join” a multicast group at network layer
- A host simply issues a membership_report to its attached MRouter (Multicast Router)
- That mrouter, along with other mrouters, will begin delivering multicast datagrams to that host
Joining a multicast group is therefore receiver-driven
- A sender need not be concerned with explicitly adding receivers to its multicast group
- It cannot control who joins the group or who sends to the group either
There is no network layer coordination of the use of multicast addresses
Possible that two different multicast groups choose the same multicast address
From a multicast application viewpoint, this will result in interleaved multicast traffic (some datagrams are useful, while others are redundant)
Although the network layer does not provide for filtering, ordering, or privacy of multicast datagrams, these mechanisms can all be (and are assumed to be) implemented at the application layer

Internet Multicast Model is a two-step process.

Local: host informs local mcast router of desire to join group: IGMP (Internet Group Management Protocol)
- Internet Group Management Protocol (IGMP) are used by hosts and routers to manage the multicast addresses (multicast group membership information)
Wide area: local router interacts with other routers to receive mcast datagram flow (multicast routing)
- multicast protocols (e.g., DVMRP, MOSPF, CBT, PIM)

Multicasting within a LAN is simple

broadcast nature of most LANs
Stations recognize the multicast address accept the packet
IEEE 802 and other LAN protocols provide MAC-level multicasting with multicast addresses = those with the lowest bit of the first byte set to 1

Multicasting is much more difficult in internets that are connected by routers

IP-Level Multicasting

Multicast Router (MRouter)

MRouters must be able to forward multiple copies of a single packet at branch points when required
MRouters must be able to translate between IP multicast address and list of networks containing group members
MRouters must be able to translate between IP multicast address and MAC-level IP multicast address at destination networks
- 48 bits MAC multicast address has the lowest bit of the first byte set to 1

Multicast Address

In multicast, a multicast address is used.

A multicast address defines a group of recipients
A host, which is a member of n groups, has (N+1) addresses
- 1 unicast address
- N multicast addresses

In IPv4, multicast IP addresses is classified as Class D addresses (Class D in Classful Addressing)

224.0.0.0 – 239.255.255.255
$2^{28}$ (~ 268 million) addresses
Served as Group Identifier

Example:

If the destination address is 226.14.18.7, the packet is forwarded to all members in the group
If the destination address is 14.22.45.3 (IP of A), the packet is forwarded to A only

Reserved Multicast Addresses

Local Network Control Block

224.0.0.0/24 - 224.0.0.255/24 (256 addresses)

Assigned to a multicast routing protocol to be used inside a network
- 224.0.0.1 is used to send datagrams to all hosts and routers inside a network
- 224.0.0.2 is used to send datagrams to all routers inside a network
Example
- Internet Group Management Protocol (IGMP)
- Distance Vector Multicast Routing Protocol (DVMRP)

Internetwork Control Block

224.0.1.0/24

Assigned to a routing protocol to be used in the whole Internet
Example
- Precision Time Protocol (PTP)
  - synchronize clocks throughout a computer network

Source-Specific Multicast (SSM) Block

232.0.0.0/8

Used for source-specific multicasting (SSM) routing
- Packets that are delivered to a receiver are those originating from a specific source address requested by the receiver.

Administratively Scoped Block

239.0.0.0/8

Used in a particular area of the Internet.
- Example: A college can grant each professor one of the addresses from 239.x.y.0 to 239.x.y.255. That address can be used to send multicast communications to the students.
- x.y. is related to the autonomous system of the college.

MAC-Level Multicasting

Each host on an Ethernet LAN has a unique MAC address

How do you talk to a group of hosts (the multicast group), where each host has a different MAC address, and at the same time ensure that the other hosts don’t process the information?

When a computer joins a multicast group:
- The computer must be able to distinguish between normal unicasts (which are directed to one computer) and multicasts
- The computer must be able to configure its network card, via its drivers, to watch out for particular MAC addresses (in this case, multicast MAC addresses) apart from its own unicast address

MAC Multicast Addresses

The Ethernet network card only processes a packet which has a destination MAC address that matches any of its multicast MAC addresses

Ethernet uses the low-order bit of the high-order byte to distinguish conventional unicast addresses from multicast addresses.
- Last bit of the First byte
A unicast MAC address would have this “multicast” bit set to 0, whereas a multicast MAC address would have the bit set to 1

Example:

00-A0-C9-AB-0E-8F = 00000000-10100000-… => a normal unicast Ethernet address

01-00-5E-00-00-00 = 00000001-00000000-… => a multicast address (reserved for mapping to IP multicast addresses)

Translate between IP and MAC multicast addresses

To translate between IP and MAC multicast addresses, we set the lowest 23 bits of a Class D IP-multicast address as the lowest 23 bits of the special MAC address 01-00- 5E-00-00-00

Example - IP 239.255.255.255 (11101111.1**1111111.11111111.11111111**) corresponds to MAC address 01:00:5E:7F:FF:FF

Class D address has 28 “free” bits (because the first 4 bits must be 1110, so only 28 out of 32 bits can be changed)
- A mapping based on the lowest 23 bits is not unique
- More than one Class D address may be mapped to the same MAC address
- In those cases, “unwanted” multicast packets should be discarded by the upper layers and will generally do no harm

IGMP: Internet Group Management Protocol

In both unicast and multicast routings, creating a forward table involves two steps:

Needs to know to which destination it is connected.

Propagate the information to other routers

Unicast Routing

The first step is completed during the setup of routers

Routing protocols such as RIP are responsible for propagating these collected information

Multicast Routing

During setup, a router does not know which host in the attached network is a member of a particular group

Besides, a host may join some new groups and leave some others in a short period of time.

Therefore, we need an extra protocol to collect information

Internet Group Management Protocol (IGMP) is a network layer protocol for collecting information about group membership

IGMP messages are encapsulated in an IP datagram

IGMP

Host: sends IGMP report when application joins multicast group
Router: sends IGMP query at regular intervals
- Host belonging to a multicast group must reply to query

IGMP Messages

IGMP has three types of messages: the query, the membership report, and the leave report. There are two types of query messages, general and special.

Query
- General Query
- Special Query
Membership report
Leave report

IGMPv2 Message Format

Type – 8 bits
- Membership Query (= 00010001, sent by router with 2 subtypes)
- General: to query which multicast groups are joined by attached hosts (issued periodically)
- Group-specific: to query if specific multicast group is joined by any attached hosts (usually issued after receiving a leave-group message)
- Membership Report (= 00010110, sent by hosts)
  - to report that it wants to join or is joined to a given multicast group
- Leave Group (= 00010111, sent by host)
  - to report that it leaves the given multicast group

Maximum Response Time – 8 bits, in units of 0.1 seconds
Checksum – 16 bits, computed over the entire IGMP message
Group address – 32 bits
- Value = 0 in general request messages
- Valid group address in report messages

Scenario: Joining a Group in IGMP

Scenario: When an application on a host wants to receive data from a multicast group, it sends request to IGMP on the host
Action: Host checks whether it is already in that multicast group - if yes, do nothing; if no, issue membership_report message
Format:
Message type = 0x16 = 00010110
Maximum response time = 0 (not used in membership_reports)
Group address field = multicast IP address of the group to join
Source IP address = Host’s IP address
Destination IP address = Group D address
Source MAC address = Host’s MAC address
Destination MAC address = MAC multicast address (01:00:5E:XX:XX:XX)
All mrouters on the LAN must listen to all multicast addresses to collect all membership_reports

Scenario: Leaving a Group in IGMP

Scenario: When a host finds that none of its processes wants to receive data from a specific multicast group
Action: Host should issue leave_group message to mrouter
Format:
- Message type = 0x17 = 00010111
- Maximum response time = 0 (not used in leave_group)
- Group address field = multicast IP address of the group
- Source IP address = Host’s IP address
- Destination IP address = All-routers IP address = 224.0.0.2
- Source MAC address = Host’s MAC address
- Destination MAC address = MAC multicast address (01:00:5E:00:00:02)
When a leave_group message is received, the mrouter cannot tell if the group is no longer needed because other hosts may still be in it
How does a router detect there is no longer any host on an attached interface that are joined to a given multicast group?
- Answer: Group-specific membership query, followed by no response within Max Response Time (default=10, meaning 1 sec)
- Mrouter then infers that no host joined to a given multicast group and stops forwarding data to that group

But leave_group is optional and cannot be trusted because

a host may be shut down suddenly and hence will not have chance to send any leave_group messages
To make sure all the group are active, we can use a periodic query for all groups by mrouters

Monitoring Groups in IGMP

Mrouters periodically (by default, every 125 sec) issue general_membership_query
- Maintain a current list of all active groups
- Sent to all-hosts
- Group address field is set to 0.0.0.0
- Hosts who want to stay in any multicast group must read the messages and respond with report for each group it has joined

IGMP Operation

Mrouters do not care

Which hosts have joined a given group?
How many hosts on the same LAN have joined the same group?

Mrouters only care

whether one or more of its attached hosts belong to a given multicast group
in those cases, the mrouters will continue forwarding multicast traffic to that group

Ideally, the mrouter wants to hear from only one of the attached hosts for each multicast group

Maximum Response Time

IGMP provides an explicit mechanism for reducing the number of membership_reports when multiple attached hosts belong to the same multicast group

After receiving a membership_query, each interested host will wait a random amount of time between 0 and the Maximum Response Time before sending a response.
If the host hears a membership_report from some other attached host for that multicast group, it will not send its own report because the attached mrouter already knows some hosts in this LAN belong to that group
- the report can be see by other hosts
- the mrouter wants to hear from only one of the attached hosts for each multicast group
This saves duplicate reports and minimizes network traffic (hence enhances network performance

Example:

A query message was received at time 0; the random delay time (in tenths of seconds) for each group is shown next to the group address.

Each group only 1 report

Multicast Routing: Problem Statement

Goal: to find a tree of links that connects all of the routers that have attached hosts belonging to the multicast group.

Multicast packets will then be routed along this tree from the sender to all of the hosts belonging to the multicast tree.
Link up all involved routers together so they can share the information among them

Approaches for finding multicast tree:

Group-shared tree: group uses one tree
- minimal cost tree (Steiner)
- center-based trees
Source-based tree: one routing tree per source
- Shortest path trees
- reverse path forwarding

Group-shared tree vs Source-based tree

Group-shared tree:
- Higher delay, traffic concentration
- Per-group state at routers
- Efficient for sparse-area multicast
Source-based tree:
- Shortest-path trees – low delay, better load distribution
- More states at routers (per-source state)
- Efficient for dense-area multicast

Entries for Routing Table in Multicast Routing

In unicast routing, the routing table only contains destination address, next hop ip, interface.

But for multicast, we might send multiple copies out. the entries are different for group-shared tree and source-based tree.

Group-shared tree:
- Routing table entries do not list a source IP address, which is indicated with a ‘*’ (star) in the source IP address column. (Dont care)
- The corresponding entry is called a (*, G) entry.
Source-based tree:
- A routing table entry contains a source address as well as a group address.
- This is often called a (Source, Group) or (S, G) entry.

If there are matches for both (S, G) and (*, G) entries, the (S, G) entries take preference.

Multicast Routing Using a Group-Shared Tree

Group-shared tree: group uses one tree

minimal cost tree (Steiner)
center-based trees

Group Shared Tree: Steiner Tree

An optimal multicast routing tree is one having the smallest sum of the tree link costs.
The problem of finding a minimum cost tree is known as the Steiner Tree problem.

Steiner Tree Problem

Input Description: A graph G=(V,E). A subset of vertices T in V.

The Vertices are the routers and the Edges are the links.

Problem: Find the smallest tree connecting all the vertices of T.

(Given a weighted graph in which a subset of vertices are identified as terminals, find a minimum-weight connected subgraph that includes all the terminals)
The Steiner tree problem is distinguished from the minimum spanning tree problem in that we are permitted to construct or select intermediate connection points to reduce the cost of the tree.

An Approximation Algorithm for Steiner Tree

Start with any vertex in the multicast group.
Choose another vertex in the multicast group, which is closest to the first vertex and add the shortest path between the two to the tree (which is now empty).
Choose that vertex of the multicast group which is closest to the tree (distance between a vertex and a tree is the minimum distance between the vertex and a node in the tree).
Augment the tree by the shortest path between the vertex and the tree.
Repeat this procedure till all vertices of the multicast group are in the tree.

Dijkstra algorithm vs Steiner Tree

Dijkstra algorithm find the minimum cost to the source

Steiner Tree find the minimum distance to the tree

Example:

The red routers are in the same group
Start with F

Group Shared Tree: Center-based Tree

Single delivery tree shared by all

One router identified as “center” of tree

To join:

edge router sends unicast join-msg addressed to center router
join-msg “processed” by intermediate routers and forwarded towards center
join-msg either hits existing tree branch for this center, or arrives at center
path taken by join-msg becomes new branch of tree for this router

Build up the tree one by one , from sending the join message

Example

Firstly: R3,R5,R7 send a join-msg to form a tree

Then R6 send a join-msg to R3 to form a tree

R8 send a join-msg to R6 to form a tree

Eventually the tree will form.

Note the data will always first reach the center using unicast, then the center send to all members through multicast.

Multicast Routing Using a Source-Based Tree

Source-based tree: one routing tree per source

Shortest path trees
reverse path forwarding

Source-Based Tree: Reverse Path Forwarding (RPF)

Rely on router’s knowledge of unicast shortest path from it to sender
Each router has simple forwarding behavior:

if (multicast datagram received on incoming link on shortest path back to center):
		then flood datagram onto all outgoing links 
else: 
		ignore datagram

Example:

Suppose A contain the source
B E F are the member that have joined the group (So the group contains A B E F)
Packet first forward from the source to attached routers (A) and send to all output interfaces (B and C)
B and C recieved the packet, they check the routing table whether the Next hop of the reverse path to source is the sender (e.g. Dest to source (A) the next hop is sender (A) ). If yes, flood the packet to all outgoing links / all other interfaces.
For duplicate packet recieved, drop the duplicated packets
F and E recieved the packet forwarded by C, they check the routing table whether the Next hop of the reverse path to source is the sender (e.g. Dest to source (A) the next hop is sender © ). If yes, flood the packet to all outgoing links / all other interfaces.
D recieved the packet forwarded by B, it check the routing table whether the Next hop of the reverse path to source is the sender (e.g. Dest to source (A) the next hop is sender (B) ). If yes, flood the packet to all outgoing links / all other interfaces.
Then D forward to all other interface, the tree is formed.

Pruning RPF Algorithm

A multicast router that receives multicast packets and has no attached hosts joined to that group will send a prune message to its upstream router.
- Reduce overhead
If a router receives prune messages from each of its downstream routers, then it can forward a prune message upstream.

G has no attached group number => prune the message to upstream router (D)

D has no attached group number => prune the message to upstream router (B)

B has attached group number => do nothing

The problem of Pruning

Pruning requires that a router know which routers downstream are dependent on it for receiving their multicast packets. This requires additional information beyond that required for RPF alone.
If a router sends a prune message upstream, then what should happen if a router later needs to join that multicast group?

Possible Solution

One possibility is to add a graft message that allows a router to “unprune” a branch.

Another option is to allow pruned branches to time-out and be added again to the multicast RPF tree; a router can then re-prune the added branch if the multicast traffic is still not wanted.

Multicast Routing Protocols

We have different multicasting protocols (Can be divided into 2 categories):

Large number router involved => use a source-based tree (DVMRP)

Scalability: MOSPF (OSPF) > DVMRP (RIP)

Few number router involved => use a group-shared tree (CBT)

MOSPF – Mutlicast Open Shortest Path First
DVMRP – Distance Vector Multicast Routing Protocol
PIM – Protocol Independent Multicast
- PIM- DM: PIM Dense Mode
- PIM- SM: PIM Sparse Mode
CBT – Core-Based Tree

Multicast Open Shortest Path First (MOSPF)

Multicast Open Shortest Path First (MOSPF) is the extension of OSPF
MOSPF routers maintain current image of the network topology via OSPF.
Through the unicast OSPF, each router has a link-state database (LSDB)
Basic MOSPF runs in OSPF domain
MOSPF uses IGMP to discover members on directly attached subnets.
Each router indicates groups for which there are directly-connected members.
Link state advertisements argmented with multicast group addresses to which local members have joined
- The subnet router floods Group-Membership Link State Advertisements (LSAs) throughout the OSPF domain.

MOSPF Operation

The Local Group Database records attached groups and the subnets on which the group members reside.

The DR then originates a Group Membership LSA for each attached group.
- Only the DR will broadcast the Group Membership LSA for each attached group.
The LSA specifies the group address and the originating router ID and lists all the router’s attached networks on which members of the group reside.
The LSA is then flooded throughout the originating router’s area.
The Group Membership (type 6) LSA is similar to a Network (type 2) LSA
Multicast: Add membership information to “link states”
Each router computes multicast tree for each active source (S,G), build forwarding entry with outgoing interface list
The forwarding table entry for a particular (S, G) pair indicates what upstream neighbor a matching packet should be received from and what downstream neighbors the packet must be forwarded to.
The local group database also is used to make entries into the forwarding table for locally attached networks containing group members.

MOSPF Group Membership LSA Format

Link State ID carries the address of the multicast group being advertised.
Advertising Router is always the router ID of the MOSPF designated router on the multiaccess network, because only the DR can originate type 6 LSAs.
Vertex Type specifies whether the destination is a router (type = 1) or a transit network (type = 2). Vertex ID is the originating router’s router ID.

Example of Multicast Open Shortest Path First (MOSPF)

Suppose a router R received a multicast packet from a source S
- S can be other router not directly connected to R
- The G_ are the involved group of each router

Each Router will have a link state database (LSDB)

First Use the Dijkstra algorithm to create a shortest-path tree with S as the root and all destinations in the internet as the leaves.

Then The router R creates a shortest-path subtree with itself as the root of the subtree

All the interfaces, that do not reach a network with active members corresponding to a particular source-group combination, become inactive.

Since m1 interface does not include G1, we only need m2 interface.

|(S, G1) | Incoming interface: m3 | Outgoing interface list: m2

The routing table will be built.

Each router determines its position in the pruned SPT
- Upstream (IN) and Downstream interfaces (OUT)
Create a forwarding cache entry the first time and use it for further routing
- Entry changes only when the topology or Group membership changes
  - Run the tree again to determine

Distance Vector Multicast Routing Protocol (DVMRP)

DVMRP is an extension of the Routing Information Protocol (RIP)
Distributed protocol that generates IP Multicast delivery tree per source-group
Build the Shortest path from Source to hosts
- based on Number of hops metric
Derived from Routing Information Protocol
- RIP forwards the unicast packets based on the next-hop towards a destination
- DVMRP constructs delivery trees based on shortest previous- hop back to the source
Supports hierarchical routing
Per-source broadcast trees built based on routing exchanges ( using distance vector)
When a router receives a multicast packet, it creates its forwarding table with the following steps:
- Create the Least-cost tree from the source to the router
  - Reverse path forwarding (RPF) algorithm to form a tree
- Create a broadcast tree whose root is the router itself and leaves are all the networks in the internet
  - Reverse path broadcasting (RPB) algorithm to create a broadcast tree
- Create a multicast tree by cutting some branches of the tree that end in networks with no member in the group
  - Reverse path multicasting (RPM) algorithm to create a multicast tree

Reverse path broadcasting (RPB)

In this step, a broadcast tree (one-to-all) from a router is created.
RPB creates a shorest path broadcast tree from the source to each destination.
It guardantees that each destination receives one and only one copy of the packet.

A Quick comparison of RPF and RPB:

Example:

The shortest path is determined from the last step (RPF)
R3 forwards the incoming packet to all the other interfaces
R4 forwards the packet to R1, R5 and the attached network
R5 drops the packet from R4 (RPF)
R4 drops the packet from R5

Look at N, it recieved two copies from the source.

To avoid a network receiving more than one copy of packet from a source, we can assign a parent router (designated router) for each network.
- Only the designated router will forward the packet to the network
When a router that is not the parent of the attached network receives a multicast packet, it simply drops the packet

Reverse Path Multicasting (RPM)

In this step, all the interfaces, that do not reach a network with active members corresponding to a particular source-group combination, become inactive
- Reverse Path Forwarding check
- Poison Reverse
  - Determine downstream interfaces to forward the packet on
- Using Prune and Graft message
Bottom-up from the leaves to the root using the information collected by the routers (IGMP)

Determine upstream interface : RPF
Forward on downstream interfaces
- Initially, all downstream interfaces determined by Poison Reverse are part of tree
- If downstream interface is a Leaf network
  - Consult IGMP Local database
- Non-Leaf Networks
  - Delete interface if a Prune is received

Generally, RPF is a general term including RPB and RPM.

DVMRP Operation

Init:

Then after new member join:

Finally:

Protocol-Independent Multicast (PIM)

Design Rationale:

Broadcast and prune keeps state off-tree and is suitable when members are densely distributed
Explicit join/center-based approach keeps state on-tree and is suitable when members are sparsely distributed
PIM attempts to combine the best of both worlds

PIM provides both dense-mode (DM) and sparse-mode (SM) protocols

PIM-DM: similar to DVMRP but does not build its own routing table
PIM-SM: similar to CBT but provides switching to SPT and bootstrap mechanism for electing the tree center dynamically

PIM Message

PIMv2 protocol messages are encapsulated in IP datagrams with protocol number 103.
PIM messages can be sent as unicast or multicast packets. When sent as multicast packets, PIM uses the multicast IP address 224.0.0.13, which is reserved as the ALL-PIM-Routers group.

Types of PIM Messages:

Message types Hello, Join/Prune, Bootstrap, Assert, and Graft are sent as multicast packets to address 224.0.0.13 with the TTL field in the IP header set to 1.
Note that the same message type is used for Join and Prune messages.
- Join is used for center-based trees
- Prune is used for Reverse Path Forwarding
All other message types are sent as unicast messages.

Designated Router and Designated Forwarder in PIM

For a given network, the role of the designated router (DR) is to send Join/Prune and Register messages on behalf of the hosts that are on the network.
Each PIM router periodically sends Hello messages on all PIM enabled interfaces to detect neighboring routers.
Hello messages are also used to select a Designated Router (DR) on a network with multiple routers.
When multiple routers send Hello messages, the sender with the largest IP address assumes the role of the DR.
The designated forwarder is the router that forwards multicast packet on network with hosts that are multicast group members.
The forwarder is generally identical to the DR, but not necessarily.

PIM-Dense Mode

Similar to DVMRP

Flood-and-prune RPF, similar to DVMRP but

underlying unicast protocol provides RPF information for incoming datagram
less complicated (less efficient) downstream flood than DVMRP and reduces reliance on underlying routing algorithm
- DVMRP tries to detect if downstream has group members, but PIM-DM does not
has protocol mechanism for router to detect it is a leaf-node router

PIM-Sparse Mode

Similar to the Center-based Tree

similar to CBT but it uses a Rendezvous Point (RP) instead of Center

A Rendezvous Point (RP) is chosen as tree center per group to enable members and senders to “meet”
Members send their explicit joins toward the RP
Senders send their packets to the RP
Packets flow only where there is join state
(*,G) [any-source,group] state is kept in routers between receivers and the RP
The center-based tree or rendezvous-point tree (RPT). constructed in PIM-SM is unidirectional, that is, multicast packets are forwarded only downstream in the RPT and sources send multicast packet to the RP.
The RPs can either be statically configured or it can be dynamically determined via an advertisement mechanism, which is part of PIM-SM.
In PIM a router can have both an (S, G) and an (*, G) entry for the same multicast group.
When a packet arrives with source address S for group G the router first tries to find a match in the routing table for an entry (S, G).
If no match is found, the router looks for an (*, G) entry.
If no matching entry is found, the router tries to forward the packet to the RP for that group. If no RP is known, the datagram is discarded.
When a match is found, the router performs an RP check.

PIM-SM Operation

Building the RPT

Suppose R5 is the RP

H2 is joining

DR for host H2, router R3, sends a Join(*, G) message to R2, its RPF neighbor for the RP.
Assuming that R2 does not have a multicast entry for (, G), when R2 receives the Join message, it sets up a (, G) routing table entry, and sends a Join(*, G) message to R5.
When the RP receives the Join message, it adds the outgoing interface that connects to R2 to the routing table entry for (*, G).
As with Prune messages, Join messages are sent periodically, about once per minute.
The routing entries created with a Join message have a limited lifetime.

Then H3 is joining

When host H3 joins the multicast group G, router R4 sends a Join(*, G) message to R2.
Since R2 already has an entry for (, G), the R2 does not forward the Join message to the RP, and simply adds interface I2 to the outgoing interface list for the (, G) routing table entry.

Data Transmission

The source host S1 sends a multicast packet to its DR, R1.

R1 encapsulated the datagram in a Register message, and sends the message as a unicast message to the RP.

The RP extracts the multicast packet from the register message, and forwards the message in the RPT.
The RP sends a Join(S1,G) to the DR of the source.
When R1 receives the Join message it sets up an (S1, G) routing table entry, and begins forwarding native multicast packets, that is, regular IP datagrams with the destination address set to G, to the RP.

Switching to Shortest Path Tree

PIM-SM distribution trees always start out as an RPT, but when the data rate from a source exceeds a certain threshold, the distribution tree is switched over to a source-based tree.
In the context of PIM-SM, the source- based tree is called shortest path tree (SPT).
The switching from an RPT tree to a source-based tree is initiated by the DRs connected to multicast group members by sending a Join message on the RPF interface to the source.

When the SPT is established, a router may receive two copies of the multicast packet, one from the RPT and one from the SPT.
To stop the duplicate transmissions, the router sends a Prune message to the RP, as soon as it receives a packet from the SPT.
The Prune message removes the router from the RPT.

So PIM sparse mode has the chance to switch from group-shared tree to the source-based tree.

Other Issues with IP Multicast

Inter-domain part of IP multicast is not standardized
- Existing approach requires setting up tunnels between AS’s
Multicast address allocation
- Allocate per domain? Are there enough addresses?
Congestion control, co-existence with other traffic
Reliability
- How to deal with packet losses in a scalable way?

Multicast Backbone (MBONE)

It tackles the problem that many routers on the Internet are not mrouters.
To join MBONE, an ISP set up a mrouter that connected to the nearest MBONE link
The idea is to form a multicast network through the existing unicast network
- Link up multicast routers (mrouter) in different domain by some unicast connection
Mrouters are interconnected by unicast routers, and they transfer multicast data via the unicast routers by encapsulating multicast packets inside normal unicast packets (i.e. tunneling)
- The multicast traffic packet will be encapsulated in a unicast packet in those tunnel

Deployment - Tunneling

multicast datagram encapsulated inside “normal” (non-multicast-addressed) datagram
normal IP datagram sent thru “tunnel” via regular IP unicast to receiving mcast router
receiving multicast router unencapsulates to get multicast datagram