CS204 Fall 2013

• Each of the non-zero entries in the topology matrix C is reduced from a capacity of 10 to a capacity of 6.
• Columns 2 and 3 from the traffic demand matrix are filled with zeros, so nodes 1 and 4 are the two active destinations.
• Start from the following shortest path routing policy (i.e., take the one-hop path whenever possible, and in case of a tie choose the clockwise two-hop path). Yes, I know it doesn't work very well, but your answers below will improve it.
  

1. Find the flows on links e through l when you add only the traffic for destination 1 (i.e., column 1 from the traffic demand matrix) to the system.
1. Under the fluid-flow model, do all of the links have enough capacity to carry the required load?
2. Find the average delay in this network using Kleinrock's formula for networks of M/M/1 queues.
   
3. Repeat parts (a) and (b) is you change the shortest-path routing policy to break ties in a counterclockwise direction.
   
2. Now find the flows on  links e through l when you add the traffic for both destinations 1 and 4 (i.e., columns 1 and 4 from the traffic demand matrix) to the system, assuming the original shortest-path+clockwise routing policy.
   
1. Under the fluid-flow model, do all of the links have enough capacity to carry the required load? Does your answer change if you try breaking ties in a counterclockwise direction? What does this tell you about the feasibility of sink tree routing?
2. Temporarily assume that all non-zero link capacities have been increased from 6 to 7, so the system "barely works" under the fluid flow model. Find the marginal delay on each link in this case. Use your result to find the minimum marginal delay path for every flow. In each case, state whether the minimum marginal delay path is the same or different than the original shortest-path+clockwise routing policy.
3. Show that if we reroute 10% of the traffic from the old (shortest path) to new (minimum marginal delay) paths (which only matter if they are different!), then the system "still works" under the fluid flow model if we reduce the non-zero link capacities from 7 to 6.5. Find the marginal delay on each link and the minimum marginal delay path for every flow. How is this new situation qualitatively different from the one in part (b)? What fraction of the traffic can or should we reroute from the policy of part (b) to these new paths?
   
4. Use the results of part (c) to find a routing policy that "works" (in terms of both the fluid flow model and Kleinrock's network delay formula) when we reduce the link capacities to 6 and it requires only one node to split its traffic to a single destination across two different paths.

What to turn in.