(Optional) Homework 4 (Due Jan. 5 14:00 pm)

1. Assume we have a directed network Graph: G = (N,E) where N = set of routers = { u, v, w, x, y, z } and E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }. Normally, we are given the link costs (as given below) and we find the shortest path from a source to all possible destinations using Dijkstra’s algorithm (Week 6, page 25). In the current example, assume that a loss probability is given to us for all links, say p(e) for all edges e in E. For example let p((w,y)) be 0,1 then 10% of the packets using (w,y) would be lost. Assuming independent links, modify Dijkstra’s algorithm to find the best possible path to all possible destinations where the best path gives the least loss probability. Give the pseuodo-code of the algorithm using the same format as in the viewgraphs.

2. Find the optimal paths in the above figure for all source-destination pairs assuming that all the loss probabilities are 0.01 except for the two lossy links (v,w) and (w,y) which have a loss probability of 0.04. Give your result in the form of a table where rows are pairs and columns are paths.