#header-inner {background-position: right !important; width: 100% !important;}

1/7/14

Broadcast routing.

In broadcast routing, the network layer provides a service of delivering a (data) packet sent from a source node to all other nodes in the network.


N-way-unicast.

Perhaps the most straightforward way to accomplish broadcast communication is for the sending node to send a separate copy of the packet to each destination. Flaw of this approach is such that addresses have to be known beforehand.


Uncontrolled packet flooding.

Another straightforward way to broadcasting is packet flooding: source node sends one packet to each of it's neighbours, then each of the neighbours makes copies of it and repeats the process.

It has flaws as well.

If network (node graph) has cycles, then one or more copies of each broadcast packet will cycle indifinitely.

When node is connected to more than two other nodes it will create and forward multiple copies of the broadcast packet, each of which will create multiple copies of itself, and so on. This broadcast storm, resulting from the endless multiplication of broadcast packets, would eventually result in so many broadcast packets that the network would be rendered useless (processing of packets at each node or internet device uses some of its resources).

Controlled packet flooding.

The key to avoiding a broadcast storm is for a node to judiciously chooste when to flood a packet, and when not.

In practice, this can be done in one of several ways.

In sequence-number-controlled flooding, a source node puts its address (or other unique identifier) as well as broadcast sequence number into a broadcast packet. Each node maitains a list of the source address and sequence number of each broadcast packet it has already received, duplicated and forwarded. When a node receives a broadcast packet, it first checks whether the packet is in the list, then either drops or proceeds with duplication and forwarding (broadcasting) to it's neighbors (except the node from which the packet has just been received).

A second approach to controlled flooding is known as reverse path forwarding (RPF), also sometimes referred to as reverse path broadcast (RPB). When a router receives abroadcast packet with a source address, it transmits the packet on all of its outgoing links (except the one which it was received) only if the packet arrived on the link that is on its own shortest unicast path back to the source. Otherwise, the router simply discards the packet. Note that RPF does not use unicast routing to actually deliver a packet to a destination, nor does it require that a router know the complete shortest path from itself to the source. RPF needs only know the next neighbor on its unicast shortest path to the sender - it uses this neighbor's identity only to determine whether or not to flood a received broadcast packet.

Spanning-Tree Broadcast.

While sequence-number-controlled flooding and RPF avoid broadcast storms, they do not completely avoid the transmission of redundant bradcast packets. With spanning tree - a tree that contains each and every node in a graph - we can broadcast without such unneccessary redundancy in packet transmission. Thus, another approach to providing broadcast is for the network nodes to fist construct a spanning tree.


Source: [3].

See also: Broadcast and Multicast routing.

No comments:

Post a Comment