Version 12 (modified by nsomani, 6 years ago) (diff)


I am working on prototyping of "Intra-partition Graph" of the control plane in GSTAR routing protocol.

What is Intra-partition Graph ?

Intra-partition graph consists of an up-to-date connection state information of the currently reachable nodes.


This graph is formed by exchanging the following messages:

Probe Messages:-

These messages enables each node to know about its current one hop neighbors with their short term and long term link qualities.

Each node periodically broadcasts a "link probe message":

Each neighbor on receiving this message,replies with a "link probe acknowledgement message":

This process enables the nodes to get the link quality by calculating the time elapsed between sending a link probe and receiving back an ACK. This elapsed time is called "Short term estimated transmission time (SETT)". Simple average of last 10 SETTs gives the "Long term estimated transmission time (LETT)".

Topology Messages:-

Each node periodically broadcasts a "link state advertisement (LSA) message" containing GUID, SETT and LETT of all its one hop neighbors.

Each node on receiving the LSA re-broadcasts it on all of its own interfaces. Thus, these messages flood the entire current network partition.

Computation of Intra-partition Graph

The above messaging process, enables each node to have a complete up-to-date information of all the other nodes of the current network partition.

Each node then uses "Djikstra's Algorithm" to calculate fastest paths (i.e. paths with least SETT) for reaching all other nodes in the current network partition.

Implementation and Validation

I am using "Click Modular Router" which is a software router for implementation.

The Validation is performed on "ORBIT Testbed" both for wired and wireless links.

Attachments (4)

Download all attachments as: .zip