You are in the engineering library of Princeton University studying for your final exam, which will take place in 1 hour. You suddenly realize you did not attend a key lecture on power control. Your kind TA offers to send you a video of the lecture. Unfortunately, she lives off in the Graduate College, which is somewhere way off-campus (you do not even know where).

Since you want to get the video as quickly as possible, you decide to split it into many pieces before sending it over the Princeton network. Suppose the Princeton network has the pipe capacities given in Figure 13.12. How much capacity should you send over each pipe so that you maximize your total rate?

We will walk through a step-by-step approach for solving this maximum flow problem. A useful operation will be generating a residual graph. Given a flow, for each link along the flow’s path, we draw a backward link with the amount of flow, leaving a forward link with the remaining capacity of the link. An example is shown in Figure 13.3.

(a) Allocate 4 Mbps to the path G–M–B–E. Draw the residual graph.

(b) Allocate 2 Mbps to the path G–W–B–M–F–E on the residual graph from (a). Draw the new residual graph.

(c) Allocate 2 Mbps to the path G–M–F–E on the residual graph from (b). Draw the new residual graph.

(d) There are no paths remaining on the residual graph from (c), so the algorithm terminates. The capacity allocation is given by the net capacity from steps (a), (b), and (c). Draw the graph with the final capacity allocation on each of the links.

This classic algorithm is called the Ford–Fulkerson algorithm.

Graduate Mathey (Whitman) Pirot Butler Figure 13.12 A simplified Princeton campus network, with the six modes abbreviated as C. M. F. E. B, and W