1 Routing1.1 Shortest Path & Algorithms1.2 Oscillations1.3 Link State vs. Distance Vector1.4 Trees2 Coloring3 ReferencesEE228a - Lecture 7 - Spring 2006Graph TheoryJean Walrand, scribed by Michael Krishnan ([email protected])AbstractThis lecture offers an introduction to graph theory. We start with routingviewed as finding shortest paths in a graph. We then move on to coloring as itapplies to wireless networks.1 Routing1.1 Shortest Path & AlgorithmsThe problem of routing can be seen as finding shortest paths through a graph.Here we present several algorithms all of which are governed by the principleof optimality. We then briefly address trees, for which routing is easy.Figure 1: An undirected graph with shortest paths to node D1The principle of optimality states that if ABCD is the shortest path fromA to D, then BCD is the shortest path from B to D.We can use this to find the shortest path from any node to any other nodeusing the dynamic programming equation V(A) = minXL(A, X) + V(X). Tofind the shortest path from A to D, we start with V(D) = 0. We then iterateto each node that neighbors D, and subsequently to each of their neighbors,eventually ending at A.We can use a very similar dynamic programming appraoch to solve a prob-lem of optimal control.Suppose we want to minimizeE[ΣNn=0c(xn, un)] (1)where c(xn, un) is the cost of taking action unwhile at state xn, overun= g(n, x0, ..., xn) (2)subject toP [xn+1= y|xn= x, ...x0, un= u] = Pn(x, y, u). (3)(This constraint makes this process a modified Markov process, where x’s andy’s are states and u’s are actions taken.)To solve this problem we defineVn(x) = mingE[ΣNn=0c(xn, un)]. (4)Our principle of optimality gives usVn(x) = minuc(x, u) + ΣyPn(x, y, u)Vn+1(y). (5)Because of the Markovianity, all we need to do is find the best action to take atthe nthstep, and then the rest of the actions from the (n + 1)thon are dictatedby Vn+1(x).We will start out running our algorithm withVN+1:= 0. (6)and solve backward.Let the minimizer at the nthstep beun= g(n, x). (7)The solution is thenun= g(n, xn), n = 0, ..., N. (8)We can also extend this to another variation of the problem. Instead ofN+1 steps, let us have infinity. We then want to minimizeE[Σ∞n=0βnc(xn, un)] (9)(where 0 < β < 1 is decay factor so that far off terms die out) overun= g(n, x0, ..., xn) (10)2subject toP [xn+1= y|xn= x, ...x0, un= u] = Pn(x, y, u). (11)Now letV (x) = mingE[Σ∞n=0βnc(xn, un)] (12)ThenV (x) = minuc(x, u) + βΣyPn(x, y, u)V (y). (13)Let the minimizer beu = g(x). (14)The solution is thenun= g(xn), n = 0, ..., N. (15)The minimization is accomplished by definingVn(x) = minuc(x, u) + βΣyPn(x, y, u)Vn−1(y) (16)with V0= 0. With the proper assumptions, Vn→ V .There are three primary algorithms used for finding paths to route packetsin a network:They are:• Link State (used in OSPF)• Distance Vector (used in RIP)• Path Vector (used in BGP)Link StateIn link state, each node broadcasts information about all of its links (includingthe neighbor and the edge weight). Using this information, each node has afull picture of the graph and can run Dijkstra’s algorithm to find the shortestpaths to each other node.Dijkstra’s algorithm finds the shortest paths from one node to all of theothers. It does this by looking at all paths in order of increasing length. A treeis built starting at the source node, and edges are added one at a time (addingthe edge that creates the shortest path from the source to any non-tree nodeusing only tree edges and the new edge.The result of the algorithm is tree that includes the shortest paths to everynode starting at a given source node. Note that this is different from a minimumspanning tree.An example can be found in the powerpoint slides for this lecture, and acomplete description of the algorithm in 1.The proof of correctness is fairly simple, based on the following lemmaLemma 1 At one stage, algorithms labels n odes in a set P. It then adds nodesto P. Labels in P are the shortest path involving nodes in P. Then when P =V, the theorem holdsProof:3Suppose we have a shorter path using node in TLet p, q in P be two nodes in path, with t in T in betweenBut ifv(p) + d(p, t) + d(t, q) < v(p) + d(p, q), (17)then we would have picked t before q (Contradiction)Distance VectorThe problem with the link state method of finding shortest paths is that thenodes each have to do a lot of computation to run Dijkstra’s algorithm. Thedistance vector algorithm is simpler, as it takes better advantage of the principleof optimality. Each node does not need to know the complete routes.The algorithm used is called the Bellman-Ford algorithm. In this algorithm,each node periodically sends a vector of its (estimated) distances to each of itsneighbors. Upon receiving this information from its neighboring nodes, a nodeupdates its es timates . In a s ystem with N nodes, it takes N iterations for thedistance vectors to stabilize to the correct values.Figure 2: A simple graph that results in counting to infinity. The numbers are thedistances to CThe big problem with this algorithm is that without a complete picutre ofthe graph, when a link is removed, nodes cannot make the proper adjustment.For example, consider the graph in figure 2. If the link from B to C goes out,B thinks it can still get to C via A’s route (not knowing that it is s upposed togo through B). It then updates its distance to 3. Seeing this, A updates itsdistance to 4, and this cycle repeats indefinitely.In a similar example, we can see that in figure 3 if the link between 1 and3 goes out, node 2 will take M iterations to figure out the proper route to 3.The problem is that when the graph changes, we basically have to restart thealgorithm but with arbitrary initial conditions, which may cause the algorithmto take more steps.On the bright side, the algorithm is guaranteed to eventually converge to theshortest paths some time after the graph stops changing, so no synchroizationis required.Path VectorIn the path vector method, nodes do not just give their distances, but thecomplete path, so that other nodes can make more informed decisions.4Figure 3: Bad news travels slowly...1.2 OscillationsAnother issue in Routing is in how to determine the weight associated witheach edge. They s hould in some way reflect the time it takes to send a packetover a given link. This is a function of both link speed and congestion. Butif one link is completely uncongested, the routing protocol will
View Full Document
Unlocking...