IP MULTICAST ROUTING

0
26
IP MULTICAST ROUTING
IP MULTICAST ROUTING

IP MULTICAST ROUTING

What is Multicasting?
IP Multicast Addressing
IGMP
Multicast Forwarding Algorithms
Simple, Source-Based Tree, Shared-Tree
Multicast Routing Protocols
Dense-mode (DVMRP, MOSPF, PIM – DM)
Sparse-mode (PIM – SM, CBT)

 

Multicast Forwarding

Multicast Forwarding

 

Time To Live (TTL)

Scope-limiting parameter for IP Multicast datagrams
Controls the number of hops that an IP Multicast packet is allowed to propagate
TTL = 1: local network multicast
TTL > 1: Multicast router(s) attached to the local network forward IP Multicast datagrams

 

Internet Group Management Protocol (IGMP)

Used by mrouters to learn about Multicast Group Memberships on their directly attached subnets
the existence of at least one member/group
Implemented over IP
Designated Router
Each network has one Querier
All router begin as Queriers
Mrouter with the lowest IP address chosen

 

IGMP Messages

IGMP Messages

 

Multicast Routing

Unicast vs. Multicast routing
Multicast address identifies a particular transmission session
Network routers need to translate multicast addresses into host addresses
Multicast Forwarding Algorithms
Simple
primitive techniques that waste a lot of BW and router resources.
do not scale well for larger groups.
Source-based trees
Shared trees

 

Flooding

When a router receives a multicast packet for a group, it determines if it is the first time it has seen the packet
Then, it forwards it to all interfaces except the incoming interface.
Routers only need to store recently seen packets

 

Spanning tree

Just enough connectivity so that only one path between every pair of routers
A router copies an incoming packet only on the interfaces part of the spanning tree
Packets replicated only when the tree branches
Source/Destination based routing
Dynamically updated
Diasadv: Centralize traffic, sub-optimal tree between source and destination

Spanning Tree

 

Reverse Path Broadcasting (RPB)

Reverse Path Broadcasting

Different spanning tree constructed for each active (source, group) pair
Parent Link: the link the router considers to be the shortest path back to the source
Limitation: Does not consider group memberships when constructing trees

 

Example of Reverse Path Broadcasting

Truncated Reverse Path Broadcasting (TRPB)

Truncated Reverse Path Broadcasting (TRPB)

Use IGMP

Forward only to Leaf networks with members
Lim: Does not consider group memberships

Reverse Path Multicasting (RPM)

Creates a delivery tree that spans only:
Subnetworks with group members, and
Routers and subnetworks along the shortest path to subnetworks with group members
Allows the source-rooted tree to be pruned
The first packet is forwarded using TRPB
Downstream routers send Prunes if they have no members
Periodically refresh pruned tree using TRPB
Lim: Scalability

 

Reverse Path Multicasting

Reverse Path Multicasting

 

Core-Based Trees (CBT)

Constructs a single delivery tree that is shared by all members of a group
a spanning tree per group
Core routers
Join messages towards the core
Non-members unicast the data to the core
Good scalability and conservation of BW
Lim: Concentration of traffic and sub-optimal trees

 

Multi-Core CBT Delivery Tree

Multi-Core CBT Delivery Tree

Dense – Mode Multicast Routing Protocols

DVMRP, MOSPF, PIM-DM
Assumptions
group members are densely distributed throughout the network
BW is plentiful
Rely on periodic flooding of the network with multicast traffic to set up and maintain the spanning tree
Data-driven approach to construct the tree

 

Distance Vector Multicast Routing Protocol (DVMRP)

Distributed protocol that generates IP Multicast delivery tree per source-group
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

Algorithm

Per-source broadcast trees built based on routing exchanges ( using DVRP)
Reverse Path Multicasting
Initially, assume that every host on the network is part of the Multicast group (TRPB)
Per Source-Group Multicast delivery tree
Reverse Path Forwarding check
Poison Reverse
Determine downstream interfaces to forward the packet on
Prune and Graft messages

 

Tunnel Encapsulation

Encapsulated in IP packets

Tunnel Encapsulation

 

Neighbour Discovery

Neighbor Probe messages with TTL = 1
Addressed to “ALL_DVMRP_ROUTERS”
Contains a list of Neighbor DVMRP routers for which a Probe has been received on that interface
Establish “Two-Way adjacency”
Know capabilities of routers (Version no)
Keep-alive function
Sent every 10 secs
Neighbor time-out: 35secs

DVMRP Probe Message Format

DVMRP Probe Message Format
Length depends on # of neighbours
Generation ID
Non-decreasing number used to detect restart of the router
When a change in Gen ID is detected, a copy of the routing table is unicast to the router
Any prune received from the router discarded
If the prune was propagated UP, a Graft sent
Only when “Two-way adjacency” established, the router can send Poison Route reports

 

Source Location

When a multicast datagram is received at the router
Look up the source network in the routing table
RPF check
Forwarding cache entry created
Provide consistent view of shortest path to the source
Propagate routing table to all routers

Route Exchange Reports

Network number, Mask and Metric of interfaces directly connected to it
Each interface has a metric configured
Physical interfaces use a metric of 1
Tunnel interfaces metric varies with distance and BW in the path
Also, relay routes received
Adjusted Metric relayed

Poison Reverse

To determine if any downstream interfaces depend on them for forwarding data
If the interface is the best previous hop back to the source, the downstream router echoes the route on the upstream interface with an adjusted metric of “infinity + original metric”
Upstream router adds the downstream interface to the list of dependent interfaces
To determine Pruning of the Source-Group tree

Designated Forwarder
When two or more Mrouters connected to a multi-access network
Both routers may forward packets on the LAN
Elect one router per source Router with lowest metric back to the source
Equal metrics, router with lowest IP address
Route report interval of 60 secs

Routing Table

Does not consider group memberships
Source Subnet
The subnetwork containing the source host

Routing Table

 

Building Multicast Trees

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

 

Forwarding Cache Entries

Separate entries for each (Source network, Destination group) pair
Created on demand based on Routing table, Group memberships and Prunes

Forwarding Cache Entries

Pruning Multicast Trees

If a router has no dependent downstream interfaces, a Prune sent up to delete that interface from list of dependent interfaces
Leaf networks without any host members
Non-leaf networks, all downstream interfaces send a Prune
Propagates up
Limit the life of a Prune
Periodically resume TRPB
May include Network mask to specify specific source data to be pruned

 

Prune message Packet Format

Prune message Packet Format

 

Grafting

To support dynamic host memberships
To cancel previously pruned interfaces
When a new host joins the group
Or a graft message received from downstream
Separate messages sent for each source network pruned
Acknowledge each Graft with a “Graft ACK” hop by hop

 

Graft / Graft ACK Packet Format

Graft ACK Packet Format

 

Multicast Open Shortest Path First (MOSPF)

Multicast extensions to OSPF v2.
Route packets along least-cost paths
Cost: Link state metric
Metric: Can be configured to distance, load.
Source/Destination routing
Each router maintains the up-to-date image of the topology of the entire network
For use within a single routing domain
Supports hierarchical routing, load balancing and import external route info.

 

MOSPF Algorithm

Hello Protocol
Form adjacency with neighbour
Each MOSPF router maintains an identical Link State Database describing the AS topology using LSAs
Each router floods its local state through the AS
Source-rooted Shortest path tree for each [source network, destination group] pair
External routing data from BGP used
Flooded throughout the AS

 

MOSPF Algorithm

 

Local Group Database

Use IGMP to monitor group memberships
Designated router in a network
List of directly attached group members
DR generates the Group Membership LSA
For each multicast group in the database
Flooded through the area

Local Group Database

Link State Database

Describes a directed graph
Vertices: Routers and Networks
Cost associated with each outgoing interface of the router
Derived from LSA of routers and networks and Group memberships
Source-rooted SPT calculated at each router
Based on LS database (Router, Network LSAs)
Provides the best route to any destination in AS
Pruned SPT – Group membership LSAs

 

Link State Database

 

Forwarding Multicast Datagrams

Each router determines its position in the pruned SPT
Upstream and Downstream interfaces
Create a forwarding cache entry the first time and use it for further routing
Entry changes only when the topology or Group membership changes

Forwarding Multicast Datagrams

Splitting of the AS

Number of areas connected by the Backbone
Each area has its own Link state database
Topology of one area invisible to the other
Backbone
Responsible for distributing data between areas
Routing
Intra-area, Inter-area, Inter-AS

 

Area Configuration

LS Database for an area contains
All the paths within the area
Area border router(ABR) advertise into the area
costs to all external destinations (Inter-area SPT)
Location of AS boundary routers
AS-External-LSAs from ASBRs flooded (Inter-AS SPT)
Backbone Database
ABRs summarize the topology of the area
Heard by all other ABRs
ASBRs externally derived information
SPT: SP between all ABRs and ASBRs

 

Inter-Area Routing

Subset of ABRs – “Wildcard Inter-area Multicast Forwarders / Receivers”
Forward Group membership and Topology info into the backbone
Receive all multicast traffic generated in the area regardless of the group
Backbone forwards the data to appropriate ABRs

Inter-Area Routing

 

SPT Calculation

Using wild-card receivers and Summary Link LSAs
CASE I: Source n/w and calculating router in the same area
Only branches without members and Non-wild card Rx are pruned

SPT Calculation

 

CASE II: Source n/w and calculating router in different areas
Estimate the source n/w to ABR distance using Summary Link LSA info

SPT Calculation Case2

 

Inter-AS Routing

Some ASBRs – “Inter-AS Multicast Forwarders” or “Wild-card Multicast Receivers”
Each ASBR executes an Inter-AS routing protocol like DVMRP
Case I & II: Same as Inter-area Routing
Difference: ASBRs should not be pruned too

 

Case I: Source subnetwork and calculating router are in the same AS

Source subnetwork and calculating router are in the same AS

Case III: Source n/w and calculating router in different AS

Use AS-External Links describing source subnetwork

Source network and calculating router in different AS

 

Protocol Independent Multicast (PIM)

Under development by IDMR
To develop a scalable protocol independent of any particular unicast protocol
ANY unicast protocol to provide routing table
A router can switch between DM and SM depending on the group

 

PIM Dense Mode

Deployed in resource-rich environments
RPM Algorithm
Similar to DVMRP
Algorithm
A datagram is forwarded if the arriving interface is the shortest path back to the source
Datagram forwarded on all outgoing interfaces initially
Create forwarding cache entry
Prune and graft messages used to prune the tree

Leaf Network Detection
Absence of PIM Hello messages
No host membership reports
Pruning on a Multi-access LAN
A prune is sent upstream when the outgoing interface list is empty
Upstream router schedules the interface for deletion (Delay 3 sec)
Any other routers on the LAN that depend on the upstream router send a PIM-Join
Deletion request for interface cancelled
Randomly delay Join message to reduce traffic
Prunes are flushed periodically

Graft and Graft ACKs
Designated Router in Multi-access LANs
Highest IP address router as seen in “Hello”
Assert Messages
When duplicate packets arrive on a multi-access LAN
Send Assert with metric for that source
Choose router with lower metric
Equal metrics, higher IP address prevails
Modify upstream and downstream neighbours

 

Sparse – Mode

PIM-SM, CBT
Assumptions
group members are sparsely distributed throughout the network
BW not widely available
Receiver-initiated construction of the spanning tree
Limit multicast traffic and hence improve scalability
Define a Rendezvous Point (RP) and build the multicast tree around it

Algorithm
Sender sends data to the RP
Receivers JOIN the RP tree
Difference from DM
Receiver-initiated vs Data Driven
SM routers maintain state info ( Primary RP)
Advantages
Conserve network resources
Decreased amount of info in routers
Disadvantages
Concentration of traffic around RP
Sub-optimal trees increase Latency

 

PIM Sparse Mode

PIM Sparse Mode

Independent of particular unicast routing protocol
Algorithm
Senders send data to the RP
Receivers JOIN the tree
Unwanted branches pruned
Receivers can switch trees

Designated Router
Multiple routers on a LAN: Highest IP address
Responsibilities
IGMP Queries
JOIN/Prune messages towards RP
Maintain status of active RP
Route Entry
Source address, Group Address
Incoming interface (towards RP)
Outgoing interfaces (towards receivers)
WC-bit: Any source would match (*, G)
RPT-bit: Join sent up the shared RP tree

Receivers: when a new host report received
Look up primary RP for that group
Unicast JOIN message to the RP
Payload: Address G, Join = RP, WC_bit, RPT_bit, PRUNE = NULL
Create forwarding route entry for (*, G) pair
Delete cache entry when no more members
Intermediate routers transmit JOIN to RP
Create forwarding route
entry for (*, G)

DesignatedRouter

 

Hosts sending to Group
Its DR looks up the active RP for that group
Unicast data, encapsulated in a PIM-SM-Register to the RP
Active RP sends a PIM-Join to the source DR
Intermediate routers maintain state info (*, G)
When source gets a Join, it sends further packets without encapsulation
RP resends all data on the shared tree

Hosts sending to Group

If data rate warrants an SPT, an (S, G) state created
RP sends periodic Join/Prune to the source
Intermediate routers maintain (S, G) state info
Sources stop encapsulating data when they receive Register-Stop messages
RP has no downstream members for that group or source
RP already receives native data from (S, G) tree
Switching from RP-Shared tree to SPT
Depending on the data rate of a particular source, a switchover may be initiated
Only by RP or routers with members
Activate (S,G) route entry

JOIN/PRUNE message from the Rx towards the source
Payload: Address G, Join = S, Prune = NULL
Prune towards the RP for that (S, G)
Steady state of distribution tree
Each router periodically sends JOIN/PRUNE for each active route entry
To the neighbour indicated in the route entry
Helps capture changes in topology/state/membership

Steady state of distribution tree

RP Information
Bootstrap messages are used to distribute RP information within the domain
Domains’ Bootstrap Router (BSR) elected from set of candidates
A set of RP candidates periodically advertise to the BSR the groups associated with them
C-RP-Advertisements: Address of C-RP, Group address and mask
C-RP-Advs distributed in BS messages
The Advs are used by DRs
use a Hash function to map a group address to one C-RP whose ad includes the group

 

Inter-operation with DM Protocols

All PIM-SM generated packets distributed into the DVMRP domain by PMBRs
PMBRs send JOIN/PRUNE to each RP
All PIM-SM routers support (*,*,RP)
Aggregate all groups associated with an RP
Delivery of external packets
PMBRs encapsulate data in Registers and unicast to corresponding RP
PMBR route entry created
Register-Stop sent to PMBR

Data Forwarding

Longest match route entry used
(S, G)
(*, G)
(*,*,RP)
Else discarded
Match Incoming interface
Dominant Router
Elected using Assert messages (Same as DM)

 

Core Based Trees (CBT)

Construct a single tree shared by a Group
Similar to PIM-SM
Protocol independent
Bootstrap Core Discovery
Differences
Receiver cannot switch from RP-tree to SPT
CBT state bi-directional
data flow in either direction along the branch
data from a source directly connected to an existing tree branch need not be encapsulated
Core router equivalent to RP

Protocol
Host sends IGMP report to Join a group
JOIN-Request sent towards the core router
JOIN_Request is explicitly acked using JOIN-Ack by core or on-tree router
Intermediate routers set up Transient state
<Group, Incoming interface, Outgoing interface>
Transient state converted to Active state by JOIN-Ack
Bi-directional state
On-tree routers lookup forwarding cache to forward data

Data from non-members
Encapsulated as IP-over-IP and unicast to Core
Echo-Request
Each on-tree router is responsible for maintaining its Upstream link
Sent to the Upstream router
Carries a list of groups for which the upstream router is the parent
Echo-Reply
From the parent with the list of groups attached to the child interface

Flush-Tree
If link to a Parent fails, Flush-tree transmitted on all its child interfaces
Causes tearing down of all downstream branches of that group
Each downstream router responsible for re-attaching itself to the tree
Hello Protocol
Elect Designated router and Border routers
Quit Notification
Prune message sent upstream if no child interface list
Bootstrap and C-Core-Adv

 

Related Post

LEAVE A REPLY

Please enter your comment!
Please enter your name here