flooding (static)

This is another type of static algorithm.

the main concept of flooding is to sent every incoming packet on a line to every other outgoing line except the line it arrived on.

flooding generates a large no.of duplicate packets, sometimes infinite unless we may take certain measures.

the measures are as follows:-

  • one measure is use of hop count in the header of each packet and decrement this count at each hop when count reaches to zero discard the packet.
  • How to take this hop count is another problem. Generally it is set to the length of path from source to destination and in worst cases the full diameter of the subnet.

  • another way is avoid sending a packet more than once through a router this is possible by using sequence no.
  • i.e, a source router (which generates packets) can put a sequence no. to each packet and each router will maintain a list of sequence nos. and if sees a packet with same sequence no in the list that packet is discarded (not flooded).

another way of flooding is of use selective flooding.

i.e, with this the router wouldn’t send every incoming packet on every line instead the router will send packets in a particular direction only.

i.e, east bound packets are sent on east side routers and similarly on  west side by west side routers.

even flooding is cumbersome, it has some uses

i.e,

  1. used in military applications.
  2. used in distributive data base applications in which to update all data bases concurrently.
  3. used in broadcast Routing.

flooding is used rather than any other algorithm since flooding chooses shorter path between two nodes where other algorithms may not.

1 Star2 Stars

Circuit Switched Networks

A Circuit Switched N/w consists of a set of switches connected by physical links.

A connection b/w ‘2’ stations is dedicated path made of one (or) more links. Each connection uses only one dedicated channel on each link.

i.e, each link is divided into n channels either by using TDM (or) FDM.

This circuit consists of 4 switches I, II, III and IV and Multiplexers with n=’3′ channels and one link.

In some circuits Multiplexing can be implicitly included in the switch fabric it self. In this circuit the end systems are connected to a switch for simplicity consider ‘2’ end systems A and M, connected to the switches I and III.

when A needs to communicate with M . A needs to request to a connection to M, which must be accepted by all switches and by M it self- which is called setup phase.

a channel circuit is reserved on each link and the combination of circuits forms a dedicated path. After establishing path data transfer can take place. The next phase is tear down.

i.e, after all data have been transferred. Generally circuit-switching takes place at the physical layer.

Before Communication (starting), the stations must make reservation for the resources like channels, switch buffers switch i/o ports switch processing time and are dedicated during the entire duration of data transfer until the tear down phase.

Data transferred is not packatized that is data is send as a continuous flow b/w source and destination.

there is end-to-end addressing in setup phase.

The 3 phases involved are:-

Circuit switched N/w’s requires ‘3’  setup phases

  1. Connection-setup.
  2. Data transfer.
  3. Tear down.

Setup Phase:-

A dedicated circuit is established before the ‘2’ communicating parties talk to each other.

i.e, creating  a dedicated channels b/w switches. To communicate A with M . initially a requesting process as follows

A to I, I to IV and IV to III, III to M and an acknowledgement in the reverse order after the reception of ‘ack’ a connection is established.

Data Transfer Phase:-

In this phase data transfer occurs b/w the ‘2’ devices.

Tear down phase:-

To disconnect , a signal is sent to each switch to release the resources by any one of station.

Efficiency of Circuit Switched Network:-

These are less efficient in terms of allocated resources. Since all the resources are allocated during the entire duration of the connection  and these resources are un available to other connections.

Delay in this type of N/w’s is due to establishment of connection , data transfer and disconnecting the circuit.

Switching at the physical layer in the traditional telephone N/w uses the circuit switching approach.

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 the 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 forwards 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 the packet to M and discards to N.

This is reverse path forwarding.

 

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert