Global State Routing

MANET Tutorial



[fblike]

Global State Routing(GSR): Introduction

  • Global State Routing is based upon the fundamental concepts of link state routing.
  • In Link State Routing(LSR), one of the node floods out a single routing table information to its neighbors and those neighbors floods out that table to further nodes. This process continue to take place until the routing table is received by all the nodes throughout the network.
  • But in case of Global State Routing, the routing table of a particular node is broadcast-ed to its immediate neighbors only. Then initial tables of those neighboring nodes are updated. These updated tables are further broadcast one by one and this process continue to take place until all the nodes broadcasts their tables to each node in the network.

 

This image describe the concept of link state routing.

Concept : Link State routing

 

Concept : Global State Routing

  • GSR protocol uses and maintains three tables for every node individually. These tables are:

1. Distance Table : This table contains the distance of a node from all the nodes in network.

 

This image describes the format of routing table used in global state routing.

Global State Routing : Distance Table

 

2. Topology Table : This table contains the information of Link state data along with the sequence number which can be used to determine when the information is updated last.

 

This image describes the topology table used in global state routing.

Global State Routing : Topology Table

 

3. Next Hop Table : Next hop table will contain the information about the immediate neighbor of a particular node.

 

This image describes the next hop table used in GSR routing.

Global State Routing : Next Hop Table

 

  • These tables are updated on every step and ensures that each node receives correct information about all the nodes including their distances.

 

Global State Routing Protocol : Working

  • GSR broadcasts the routing tables to its immediate neighbors rather than flooding it to all the nodes as Link State Routing protocol does.
  • Consider a network of 4 nodes having a distance of “1” on each of its edge. Below mentioned steps will let you know how GSR works and how its routing tables are updated.

 

This image describes a sample network over which GSR routing is to implemented.

Global State Routing : Example Network

 

Steps

  1. For Node “X” : Firstly three tables as mentioned above will be maintained which includes distance table, Topology table and Next hop tables. This same process will be done for rest of the nodes too.

For “X”

Global State Routing : Sample Tables

  1. Secondly, broadcasting of all the tables will be done to all the immediate neighbors of “X” i.e. “Y” and “Z”.
  2. These tables are updated at “X”, “Y” & “T” nodes respectively.
  3. Same will be done for node “Y”. After first updation from “X”, node “Y” will broadcast the tables to its immediate neighbors i.e. “X” & “T” and those tables will be updated accordingly. This will be done for “T” & “Z” also.
  4. Once done, all the nodes “X”, “Y”, “Z” & “T” will be having the updated routing tables containing distances from each, with the help of which an optimal path can be chosen if data needs to be transferred from one node to other.

 

For X: Global State Routing : Sample Tables

For Y:

     Global State Routing : Sample Tables

 For Z: 

Global State Routing : Sample Tables

  1. Now, broadcasting of topology tables of “X” will take place to its neighbour i.e. “Y” & “Z” and updated tables will be like as mentioned below.

For Y:

 Global State Routing : Sample Tables

For Z:

Global State Routing : Sample Tables

  1. Similarly, these tables are further updated with topology tables of “Y”, “Z” & “T” as done in case of “X.

 

Advantages : Global State Routing Protocol

  • Higher accuracy of GSR in generating optimal path as compared to LSR.
  • Broadcasting reduces error rate as compare to flooding used in LSR.

Disadvantages : Global State Routing Protocol

  • Large bandwidth consumption.
  • Higher operational cost.
  • Large Message size resulting in more time consumption.