Broadcast Routing(dynamic)

In some applications hosts need to send messages to many (or) all other hosts like weather reports, stock market updates (or) live radio programs.

 i.e, sending a packet to all destinations simultaneously is called Broadcasting.

 Different methods of Broadcasting:-

  • first method is to send a packet to all destinations. This is a method wasteful of Band width and source needs to know the complete list of all destinations.

so this is least desirable one.

  • flooding is another way to broadcast a packet, the problem with flooding is that it generates too many packets and also consumes too much of Band width.
  • Third way is to use multi destination routing

In this technique each packet contains a list of destinations (or) a bit map for those destinations.

when a packet arrives at a router,  the router checks all the output lines it requires. The router generates a new copy of the packet for each output line after sufficient number of hops each packet will carry only one destination.

i.e, multi destination routing is like separately addressed packets (to B,C,D,E & D) must follow the same route one of them pays full fare and rest are free.

  • The fourth type of method is to use sink tree (or) spanning tree.

A spanning tree is a subset of subnet that includes all the routers but contains no loops.

if each router knows which of it’s lines belong to spinning tree then it broadcasts packet to all the lines except the one it arrived on.

This is efficient method in terms of Band width usage but problem is to maintain the knowledge of all the nodes of spanning tree at a routes.

  • Last method is to use Reverse path forwarding to approximate behavior of spanning tree.

Consider a subnet and it’s sink tree for router I as root node and how reverse path algorithm works in figure (C) 

on the first hop I sends packets to F, H, J & N. on the second hop eight packets are generated among them 5 are given to preferred paths indicated as circles (A,D,G,O,M)

of the 6 packets generated in third hop only 3 are given to preferred paths (C,E & K) the others are duplicates.

in the fourth hop to B and L after this broadcasting terminates.

advantages of reverse path forwarding:-

  • it is easy to implement.
  • it does not require routers to known about spanning trees.
  • it does not require any special mechanism to stop the process (as like flooding).

The principle is : if a packet arrives on a line if it is preferred one to reach source it gets forwarded.

if it arrives on a line that is not preferred one that packet is discarded as a duplicate.

ex:-

when a packet arrives at ‘L’ the preferred paths are N and P so it forward the packets to both N and P and if a packet arrives at ‘K’ , there the preferred path is M and N is not preferred so it forwards packet to M and discards to N.

This is reverse path forwarding.

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)

Loading...

image_print
Advertisements

Author: Lakshmi Prasanna Ponnala

Completed M.Tech in Digital Electronics and Communication Systems and currently working as a faculty.