•The idea is t o build a graph of the subnet

–with each graph node representing a router and

–each graph edge representing a communication line.

• To choose a route between a given pair of routers the algorithm just finds the shortest path between them.

•How to measure path length

–Hops , Physical distance , Bandwidth, traffic cost , measured delay mean queue length and

–Other factors or combinations of these factors.

•Use Dijkstra’s algorithm to compute the shortest path.

– Each node is labeled with its distance from the source node along the best known path.

– Initially, no paths are known , so all nodes are temporarily labeled with infinity.

– As the algorithm proceeds and paths are found , the labels may change, reflecting better paths. A label may be either temporary or permanent.

– When it is discovered that a label represents the shortest possible path from the source to that node, it is made permanent and never changed thereafter.

**Algorithm :**

#define MAX NODES 1024 /* maximum number of nodes */ #define INFINITY 1000000000 /* a number larger than every maximum path */ int n, dist[MAX NODES][MAX NODES]; /* dist[i][j] is the distance from i to j */ void shortest path(int s, int t, int path[]) { struct state { /* the path being worked on */ int predecessor; /* previous node */ int length; /* length from source to this node */ enum {permanent, tentative} label; /* label state */ } state[MAX NODES]; int i, k, min; struct state *p; for (p = &state[0]; p < &state[n]; p++) { /* initialize state */ p->predecessor = −1; p->length = INFINITY; p->label = tentative; } state[t].length = 0; state[t].label = permanent; k = t; /* k is the initial working node */ do { /* Is there a better path from k? */ for (i = 0; i < n; i++) /* this graph has n nodes */ if (dist[k][i] != 0 && state[i].label == tentative) { if (state[k].length + dist[k][i] < state[i].length) { state[i].predecessor = k; state[i].length = state[k].length + dist[k][i]; } } /* Find the tentatively labeled node with the smallest label. */ k = 0; min = INFINITY; for (i = 0; i < n; i++) if (state[i].label == tentative && state[i].length < min) { min = state[i].length; k = i; } state[k].label = permanent; } while (k != s); /* Copy the path into the output array. */ i = 0; k = s; do {path[i++] = k; k = state[k].predecessor; } while (k >= 0); }