Routing protocols and architectures/Multicast routing

Multicast is the capability to transmit the same information to multiple end users without being forced to address the latter singly and without having, hence, the need to duplicate for each of them the information to spread.

Multicast routing is in charge of deciding and propagating information needed to forward multicast packets outside Local Area Networks among multiple interconnected multicast routers (mrouter) over the network:

1. determining the existence of receivers on a particular LAN segment: in case no receivers exist, it does not make sense to forward those packets to the LAN → the networks which have no receivers are cut away from the tree (pruning);
2. propagating the existence and location of receivers over the whole IP network: multicast routing should keep track of locations of the various receivers, creating a 'spanning tree', called distribution tree, so as to minimize costs and deliver packets to everyone;
3. transmitting and forwarding data: transmitters generate packets with a particular multicast destination address, and mrouters forward them along the distribution tree up to receivers.

Multicast routing algorithms use two types of distribution tree:

• source-specific tree (RPB, TRPB, RPM, Link State): there is one tree for every sender → paths are optimal, but updates are more complex;
• shared tree (CBT): there is one tree for every multicast group, valid for all senders → updates are simpler, but paths are not optimal.

Multicast routing algorithms

• selective flooding
• Distance Vector
  • reverse path forwarding (RPF)
  • reverse path broadcasting (RPB)
  • truncated reverse path broadcasting (TRPB)
  • reverse path multicasting (RPM)
• Link State
• core-based tree (CBT)
• hierarchical

Distance-Vector multicast routing

Reverse path forwarding

When a router receives a multicast packet, it sends it on all the other interfaces, provided that the one from which it has arrived is on the shortest path between the router and the source.

Problems

• traffic: it loads the network unacceptably:
  • no routing trees: on a LAN multiple copies of the same packet can transit if two routers attached to the LAN have the same minimum distance from the source;
  • no pruning: the packet is always distributed on all links, without considering the fact that there could be no listeners;
• symmetric network: it considers the cost of the reverse path from the router to the source, which could be different from the cost of the path from the source to the router due to the presence of unidirectional links.

Reverse path broadcasting

A source (root node)-based distribution spanning tree is built, and packets reach all destinations going along branches of this tree:

• parent interface: the interface at the minimum distance toward the source, from which packets are received from upper levels;
• child interfaces: the other interfaces of the router, to which packets are sent toward subtrees (possible received packets are always discarded).

On a LAN a single copy of the same packet transits: among routers having child interfaces on the LAN, the router which has the lowest distance toward the source is elected as the designated router for that link (in case of equal cost, the interface with the lowest IP address is taken).

Problems

• traffic: it loads the network unacceptably:
  • no pruning: the packet is always distributed on all links, without considering the fact that there could be no listeners;
• symmetric network: it considers the cost of the reverse path from the router to the source, which could be different from the cost of the path from the source to the router due to the presence of unidirectional links.

Truncated reverse path broadcasting

Interested hosts send membership reports to subscribe to the multicast group → routers will send multicast packets only to interested hosts, and will delete from the tree the branches on which no membership reports have been received (pruning).

Unfortunately the distribution tree depends, besides on the source, even on the multicast group, resulting in reporting bandwidth and router memory requirements in the order of the total number of groups times the total number of possible sources → to reduce bandwidth and memory requirements, only leaf LANs which have no listeners are deleted from the tree: a leaf LAN is a network not used by any other router to reach the multicast source.

How to determine whether a certain LAN is a leaf LAN? In split horizon with poisoned reverse, the destinations reached through the link on which the announcement has been sent are put with distance equal to infinite: if at least a downstream router propagates the entry related to the concerned source with infinite distance, then that router is using that link as its shortest path to reach the source → that link is not a leaf, and then there could be further downstream leaf LANs with listeners.

Problem

It is not possible to perform pruning of whole subtrees, but only leaf LANs are deleted → useless traffic travels on internal nodes in the tree.

Reverse path multicasting

It is possible to perform pruning of a whole subtree:

1. the first packet sent by the source is propagated according to the TRPB algorithm;
2. if the first packet reaches a router attached only to leaf LANs devoid of listeners for that group, the router sends a non-membership report (NMR) message to its parent router;
3. if the parent router receives NMR messages from all its children, it in turn generates a NMR message toward its parent.

NMR messages have limited validity: when the timeout expires, the TRPB algorithms is adopted again. When in a pruned branch a listener is added to that group, the router sends to its parent node a membership report message to quickly enable the branch of the tree without waiting for the timeout.

Problems

• periodic broadcast storms: they are due to the TRPB algorithm on every timeout expiration;
• scalability: it is critical, because each router should keep a lot of information for every (source, group) pair.

Link-State multicast routing

Thanks to the full map of the network built by a LS-like (unicast) routing protocol, each router is able to compute the distribution tree from every source toward every potential receiver.

'Flood and prune' is no longer needed, but every router is able to autonomously determine whether it is along the distribution tree:

1. in a leaf LAN devoid of listeners, a host communicates to be interested in the group;
2. the attached router sends in flooding a LS packet which announces the existence of a LAN with listeners and its location inside the network;
3. the other nodes in the network store the LS packet and in turn propagate it in flooding to all the network;
4. when the first transmission packet arrives at a router, before being able to forward it it needs to compute the shortest-path tree to know whether it is along the distribution tree and, if so, on which links it should be forward the packet;
5. for the following packets this computation is no longer needed because the information will be found in the cache.

Problems

• routing the first packet in a transmission may require quite a lot of time: each router needs to compute the shortest-path tree for the (source, group) pair;
• memory resources: each source has a distinct tree toward every destination → an entry for every active (source, group) pair is in the routing table;
• CPU resources: running the Dijkstra's algorithm to compute the routing tree is heavy for routers.

Multicast routing with core-based tree algorithm

The multicast distribution tree is unique for the whole multicast group and independent of the source (shared tree). The core router is the main router in the distribution tree.

Tree building

1. a host notifies its edge router (leaf router) which it wants to join the multicast group (as both receiver and transmitter);
2. the edge router sends a Join Request message to the core router;
3. intermediate routers receiving the Join Request message mark the interface from which the message has arrived as one of the interfaces to be used to forward multicast packets for that group;
4. when the core router receives the Join Request message, also it marks that interface for forwarding and signaling stops.
   In case the message reaches a router which is already belonging to the tree, signaling stops before reaching the core router, and a new branch is added to the previous tree.

Data forwarding

1. a group member simply sends the packet in multicast;
2. the packet is forwarded first along the branch from the source to the core router, then on branches from the core router to other group members: every router receiving the packet, including the core router, sends it on all the interfaces belonging to that multicast group defined at the tree-building time (except for the one from which the packet has arrived).

Advantage

• scalability: few state information in routers.

Disadvantages

• usage of 'hard states': the core router is fixed, and no periodic refresh messages about the status of multicast groups is sent → little suitable for highly variable situations;
• the core router is a single point of failure (even though another router can be elected);
• the location of the core router heavily affects algorithm performance: the core router may become a bottleneck because all traffic crosses it;
• paths are not optimized: the distribution tree is not built based on the location of the source, but all group members can be sources.

Hierarchical multicast routing

Hierarchical algorithms are needed for inter-domain routing: the complexity of traditional algorithms (and state information to be kept) do not allow scalability to the whole Internet.

In general, routing policies come into play, and 'hosts' are replaced by 'domains':

• non-hierarchical routing: host X wants to receive groups A, B, C;
• hierarchical routing: domain Y wants to receive groups A, B, C.