1EE228a - Lecture - Spring 2006Routing Games - Presented by Nikhil ShettyLecture notes by: Nikhil Shettyemail: nikhils[AT]eecs.berkeley.eduAbstractWe have, by now, seen the various uses of game theory in different aspects of networking like bandwidth trading, MAC Layeraccess, congestion control, etc. In this lecture, we will see how routing is modeled using game theory.I. INTRODUCTIONIn routing, it is generally assumed that a distributed protocol calculates the routes for all the flows. It is then assumed thatthese routes are followed by the flows. However, this may not necessarily be true for cases where the routing is, say, betweenAutonomous Systems (AS). Also, in situations like ad hoc networks, the intermediate nodes suffer a heavy cost in terms of thepower expended, with battery power being precious. Hence, in such situations, cooperation cannot be assumed and nodes haveto be given incentives to forward packets. This leads one to the question - How bad is Selfish Routing1? This is answered by [1]and this paper will be discussed in this lecture.Also, we will look at how this problem can be dealt with, by designing mechanisms that achieve the desired results and arenot computationally expensive. Further, we will look at applications of this mechanism design in BGP routing and routing in adhoc networks.II. BASIC CONCEPTS AND EXAMPLESWe consider a network of nodes connected together by links, where a set of nodes wish to send data to another set of nodes.The latency on the links is a function of the traffic on the link. Users are assumed to be selfish but not malicious. This meansthat they play within the rules and are strategic but do not have an ulterior motive of bringing down the network. Each strategicuser wants to minimize the latency for her traffic. The cost of a flow is assumed to be the product of latency and traffic. In thissituation, the social optimum is defined as the minimum possible sum of costs of all the flows. When users are strategic and wishto minimize their own latency, the equilibrium distribution will not necessarily be socially optimal. Lets see this with an example.Consider figure 1. In this figure, consider there is an amount of flow of unit 1 from node s to node t. This flow consists of alarge number of tiny flows belonging to independent users, such that each user on her own is unable to change the latency on alink and will hence choose just one path to move from source to destination. In this case, the upper link has latency as a linearfunction of the traffic, while on the lower link it is always 1.The social optimum is to send 0.5 units of flow on the upper link and 0.5 on the lower. The cost of the social optimum is0.75. However, we observe that any user whose flow goes by the lower link suffers a latency of 1 and she is hence envious ofthe flows flowing on the upper link. By switching to the upper link, she can improve the latency that she sees. Therefore, it turnsout that the Nash equilibrium for all the flows is the condition in figure 2 where all the flow goes along the upper link. In thiscase, all the flows see the same latency and hence are no longer envious. It is a Nash Equilibrium because by changing the pathunilaterally, no flow can gain in latency. The cost of the Nash equilibrium to society is 1. Thus, the cost to society has worseneddue to the Nash equilibrium.Fig. 1. Example 12Fig. 2. Example 2Fig. 3. Braess Paradox 1A. Braess ParadoxAnother important concept is the Braess Paradox. It is illustrated in the example in figures 3 and 4. Figure 3 shows an examplewhere the Nash equilibrium results in social optimality. The social cost is 1.5 in this case. However, when an additional zero-costlink is added between the intermediate nodes, it turns out that the Nash equilibrium is one in which all flows travel along thepath shown in figure 4. If any flow tries to unilaterally move away from this path, he will see a higher cost and hence there isno incentive to deviate from this equilibrium. The cost of the Nash flow in this case is 2, which is higher than the previous case.This is counterintuitive because we do not expect that the addition of a zero-cost link would increase the social cost. We expectedthat it would reduce. This is the Braess Paradox and has been observed in a number of traffic cases.III. HOW BAD IS SELFISH ROUTING?In their paper, Tardos and Roughgarden wish to characterize how the social cost of the Nash equilibrium compare to thatat the socially optimal solution. This is characterized by the ratio of the cost of selfish equilibrium to the cost of the optimalsolution. The following sections will explain their model.A. ModelConsider a graph G = (V, E) where V is the set of vertices and E is the set of edges. There are k source-destination pairs{s1, t1}, {s2, t2}, . . . with rate ritraffic between every pair {si, ti}. f is the total description of the flow on each link of thegraph. feis the sum of flows on the edge e. The latency function on the links is le(fe), i.e., the latency is a function of the trafficon the link. The latency faced on a certain path from source to destination is given by lp(f) =Pe∈Ple(fe). where P is the setof all paths, i.e., the union of set of paths for each flow (Pi). AlsoPP∈PifP= ri, i.e., the sum of flows over all paths from asource to the destination is the total rate between the pair of nodes.1The title of the paper by Tardos and RoughgardenFig. 4. Braess Paradox 23Fig. 5. Another ResultB. Nash equilibriumA flow f is said to be at Nash equilibrium if no agent can improve its latency by changing its path. If ∀i ∈ {1, 2, . . . , k}P1P2and δ ∈ [0, fP1], we have lP1(f) ≤ lP2(˜f), where˜fPis obtained by moving δ amount of traffic from path P1to path P2. Lettingδ tend to 0, continuity and monotonicity of edge latency functions tell us that the latency on each of the paths at a Nash equilibriumwill be the same. This is the Wardrop’s Principle or the Wardrop Equilibrium.C. Optimal SolutionFor the optimal solution, we minimize the sum of the latencies seen by all the flows. This is given by the optimization problem.MinPe∈Ece(fe)subject toPP ∈PifP= rife=PP ∈P:e∈PfPfP≥ 0where ce(fe) = le(fe)feThe above problem is the system problem. We can decompose it into local problems for each of the flows to minimize. Thiscan be done as all the constraints and the latency functions are convex and therefore, the local optimum corresponds to the globalone. Thus, when each of the flows
View Full Document
Unlocking...