LS Algorithms

In LS algorithms, every router has to follow these steps:

  1. Identify the routers that are physically connected to them and get their IP addresses When a router starts working, it first sends a "HELLO" packet over network. Each router that receives this packet replies with a message that contains its IP address.
  2. Measure the delay time (or any other important parameters of the network, such as average traffic) for neighbor routers In order to do that, routers send echo packets over the network. Every router that receives these packets replies with an echo reply packet. By dividing round trip time by 2, routers can count the delay time. (Round trip time is a measure of the current delay on a network, found by timing a packet bounced off some remote host.) Note that this time includes both transmission and processing times -- the time it takes the packets to reach the destination and the time it takes the receiver to process it and reply.
  3. Broadcast its information over the network for other routers and receive the other routers' information In this step, all routers share their knowledge and broadcast their information to each other. In this way, every router can know the structure and status of the network.
  4. Using an appropriate algorithm, identify the best route between two nodes of the network In this step, routers choose the best route to every node. They do this using an algorithm, such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on information that has been collected from other routers, builds a graph of the network. This graph shows the location of routers in the network and their links to each other. Every link is labeled with a number called the weight or cost. This number is a function of delay time, average traffic, and sometimes simply the number of hops between nodes. For example, if there are two links between a node and a destination, the router chooses the link with the lowest weight.

The Dijkstra algorithm goes through these steps:

  1. The router builds a graph of the network and identifies source and destination nodes, as V1 and V2 for example. Then it builds a matrix, called the "adjacency matrix." In this matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."
  2. The router builds a status record set for every node on the network. The record contains three fields: Predecessor field - The first field shows the previous node. Length field - The second field shows the sum of the weights from the source to that node. Label field - The last field shows the status of node. Each node can have one status mode: "permanent" or "tentative."
  3. The router initializes the parameters of the status record set (for all nodes) and sets their length to "infinity" and their label to "tentative."
  4. The router sets a T-node. For example, if V1 is to be the source T-node, the router changes V1's label to "permanent." When a label changes to "permanent," it never changes again. A T-node is an agent and nothing more.
  5. The router updates the status record set for all tentative nodes that are directly linked to the source T-node.
  6. The router looks at all of the tentative nodes and chooses the one whose weight to V1 is lowest. That node is then the destination T-node.
  7. If this node is not V2 (the intended destination), the router goes back to step 5.
  8. If this node is V2, the router extracts its previous node from the status record set and does this until it arrives at V1. This list of nodes shows the best route from V1 to V2.

We will use this algorithm as an example on the next page.