•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);
}