Simulation of Link State Routing Algorithm Using PHP

Link State is one of the main routing protocols. Purpose of any routing protocols is to dynamically communicate information about all network paths used to reach a destination and to select from those paths, the best path to reach a destination network. Link state algorithm selects routing paths with lowest costs that are calculated using a distance metric iteratively checking them from each node. 

 

A link-state routing protocol is one of the two main classes of routing protocols used in packet switching networks for computer communications (the other is the distance-vector routing protocol). Examples of link-state routing protocols include OSPF and IS-IS.

The link-state protocol is performed by every switching node in the network (i.e. nodes that are prepared to forward packets; in the Internet, these are called routers). The basic concept of link-state routing is that every node constructs a map of the connectivity to the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. The collection of best paths will then form the node's routing table.

This contrasts with distance-vector routing protocols, which work by having each node share its routing table with its neighbors. In a link-state protocol the only information passed between nodes is connectivity related.

Link state algorithms are sometimes characterized informally as each router 'telling the world about its neighbors'. 

Pseudo-code of Link State Algorithm is presented below:

1. Initialization
2. N’ = u
3. For all nodes v
4.     If v is a neighbor of u
5.         Then D(v) = c(u, v)
6.     Else
7.         D(v) = µ
8. Loop
9. Find w not in N’ such that D(w) is minimum
10. Add w to N’
11. Update D(v) for each neighbor v of w and not in N’
12.     D(v) = min( D(v), D(w)+c(w,r) )
13. /*
14. Least path cost to w plus cost from w to v */
15.  Until N’=N

Link State algorithm is implemented using PHP with Html and Javascript interface. Below I am presenting the implementation.

Download Script: http://dl.dropbox.com/u/47625598/linkstate/index.php