Section 6.9 Shortest Paths and Distance Vector Protocols The Shortest Paths Problem looks at a routers in a network and wants to find the most efficient path to a destination. We use the cost of a delay (Cvw) on link (v,w) to determine the minimum delay from a source node s to a destination node t. However, in this problem we cannot simply use Dijkstra's Algotithm because we don't have global knowledge of the network. It is actually better to use local knowledge. To solve we use the Bellman Ford Algorithm, which can be thought of as a pull based algorithm. In each iteration t, each node v has to contact each neighbor w, and “pull” the new value M[w] from it. IF a node w has not changed its value, then there is no need for v to get the value again, however, v has no way of knowing that so it computes the pull anyway. To improve upon this wastefulness we can use a pushed base algorithm instead. Specifically, each node w whose distance value M[w] changes in an iteration informs all its neighbors of the new value in the next iteration; this allows them to update their values accordingly. If M[w] has not changed, then the neighbors of w already ahve the current value, and there is no need to “push” it to them again. However, one of the major problems is that we are not guaranteed that the value of a cost of an edge will remain constant during the execution of the program. Node costs may change or in some cases links between nodes could which would effectively increases the cost to infinity. Therefore designers of network routing shcmes have tended to move from distance vector protocols to path vector protcols.

6.10 - Negative Cyles in a Graph We now consider a more general case of the Bellman-Ford Algorithm where a graph that may contain negative cycles. The two questions we thus consider are: How do we decide if a gaph contain a negative cycle? and How do we actually find a negative cycle in a graph that contains one? For this algorithm, we first extend the definiton of OPT(i,v) so that if node v can reach node t and is contained in a negative cycle, then the limit of OPT(i,v) = infinity. If there are no negative cycles in G, then OPT(i,v) = OPT(n-1,v) for all nodes v and all i≥n. So if we know that OPT(i,v) = OPT(n-1,v) for all nodes v, then know there are no negative cycles in the graph. To find a negative cycle, we consider a node v such taht OPT(n,v) does not equal OPT(n-1,v), for this node, a path P from v to t of cost OPT(n,v) must use exactly n edges. We find the minimum cost path P from v to t by tracing back through the subproblems. If G has n nodes and OPT(n,v) does not equal OPT(n-1,v), then a path P from v to t of cost OPT(n,v) contains a cycle C that has a negative cost in it. This algorithm to find the negative cycle run on O(mn) time.

Chapter 7 - Network Flow Chapter 7 looks at network flows and finding the maximum flow in a graph

Section 7.1 - The maximum Flow Problem and the Ford-Fulkerson Algorithm To find the maximum flow in a network flow we first need to consider several ingredients: capacities on the edges, source nodes in a graph, sink nodes, and the traffic itself. Associated withe each edge e is a capacity, which is a nonnegative number that we denot as Cv. There is a single source node s (element of V), and also a single sink node t (element of V). Along with that we know that there are two conditions that are maintained: capacity conditions, and conservation conditions. The capacity condition claims that for each edge e (element of E), we have 0≤f(e)≤Ce, and the conservation condition claims that for each node v other than s and t, we have that the flow in equals the flow out. Whe design the algorithm to find the max flow, we start with zero flow for all edges. Now we try to increase the value of the flow (f) by “pushing” flow along a path from s to t up to the limits imposed by the edges capacities. However there is a more general way to push flow: we can push foward on edges with leftove capacity, and we can push backward on edges that are already carrying flow to divert it in a different direction. Knowing this, we know define the residual graph. Therefore Max_Flow is: initially f(e) = 0 for all e in G while there is an s-t path in the residual graph Gf

 Let P be a simple s-t path in Gf
 f' = augment(f,P)
 Update f to be f'
 Update the residual graph Gf to be Gf'

Endwhile Return f The algorithm above runs at O(mC) time where m is the number of edges and C is the sum of capacities in teh while loop.

7.2 - Maximum Flows and Minimum Cuts in a Network Formally, we say that an s-t cut is a partition (A,B) of the vertex set V, so that s is a element A and t is an element of B. The capacity of a cut (A.B) is simply the sum of the capacities of all edges out of A: c(A,B). Thus if f is any s-t flow, and (A,B) is any s-t cut, then v(f) = fout(A) - fin(A). Furthermore, we know that if f is any s-t flow, and (A,B) is any s-t cut, then v(f) ≤ c(A,B). In summary, we know that the maximum flow can be found by taking the minimum cut of capacity, because flow can never exceed capacity. Given a flow f of maximum value, we can compute an s-t cute of minimum capacity in O(m) time.

7.3 - Choosing Good Augmenting Paths We know from the previous section, that choosing the correct augmenting path is essentail for this algorithm. If we choose paths poorly, we find to be extremely unproductive at solving the max flow problem. Recall that augmentation increases the value of the max flow by the bottleneck capacity of the selected path; so if we choose paths iwth large bottleneck capacity, we will be making a lot of progress. To avoid a slowdown we will maintain a so-called sclaing parameter delta, and we will look for paths that have bottleneck capacity of at least delta. Scaling Max-Flow:

Initially f(e) = 0 for all e in G
Initially set delta to be the largest power of 2 that is no larger than the max capacity out of s
while delta≥1:
  while there is an s-t path in the graph Gf(delta):
    Let P be a simple s-t path in Gf(delta)
    f'=augment(f,P)
    Update f to be f' and update Gf(delta)
  Endwhile
Endwhile
Return f

The Scaling Max-Flow Algorithm in a graph with m edges and integer capacities finds a maximum flow in at most 2m(1+log2C) augmentation, and it can be implemented to run in at most most O(m-squaredlog2C) time.