DOC PREVIEW
CMU CS 15892 - How Bad is Selfish Routing?

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

How Bad is Selfish Routing?Tim Roughgarden∗´Eva Tardos†December 22, 2000AbstractWe consider the problem of routing traffic to optimize the performance of a congested net-work. We are given a network, a rate of traffic between each pair of nodes, and a latency functionfor each edge specifying the time needed to traverse the edge given its congestion; the objectiveis to route traffic such that the sum of all travel times—the total latency—is minimized.In many settings, including the Internet and other large-scale communication networks,it may be expensive or impossible to regulate network traffic so as to implement an optimalassignment of routes. In the absence of regulation by some central authority, we assume thateach network user routes its traffic on the minimum-latency path available to it, given thenetwork congestion caused by the other users. In general such a “selfishly motivated” assignmentof traffic to paths will not minimize the total latency; hence, this lack of regulation carries thecost of decreased network performance.In this paper we quantify the degradation in network performance due to unregulated traffic.We prove that if the latency of each edge is a linear function of its congestion, then the totallatency of the routes chosen by selfish network users is at most43times the minimum possibletotal latency (subject to the condition that all traffic must be routed). We also consider themore general setting in which edge latency functions are assumed only to be continuous andnondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulatedselfish network users may be arbitrarily larger than the minimum possible total latency; however,we prove that it is no more than the total latency incurred by optimally routing twice as muchtraffic.1 IntroductionA fundamental problem arising in the management of large-scale traffic and communication net-works is that of routing traffic in order to optimize network performance. One problem of thistype is the following: given the rate of traffic between each pair of nodes in a network, find anassignment of traffic to paths so that the sum of all travel times (the total latency) is minimized.A difficult aspect of this problem is that the amount of time needed to traverse a single link of anetwork is typically load-dependent, that is, the common latency suffered by all traffic on the linkincreases as the link becomes more congested.In practice, it is often difficult or even impossible to impose optimal or near-optimal routingstrategies on the traffic in a network, and thus network users are free to act according to their own∗Department of Computer Science, Cornell University, Ithaca NY 14853. Research done while visiting the Com-puter Science Division, UC Berkeley, Berkeley, CA 94720. Supported by ONR grant N00014-98-1-0589. Email:[email protected].†Department of Computer Science, Cornell University, Ithaca NY 14853. Research done in part while a visitingMiller Professor at the Computer Science Division, UC Berkeley, Berkeley, CA 94720. Pa rtially supported by aGuggenheim Fellowship, NSF grant CCR-9700163 and ONR grant N00014-98-1-0589. Email: [email protected], without regard to overall network performance. For example, existing Internet protocolsplace little restriction on how network traffic is routed, allowing network users to make decisions ina selfish or even malicious manner [5]. The central question of this paper is how much does networkperformance suffer from this lack of regulation?As a first step toward formalizing this question mathematically, we assume that, in the absence ofnetwork regulation, users act in a purely selfish (but not malicious) manner. Under this assumption,we can view network users as independent agents participating in a non-cooperative game and expectthe routes chosen by users to form a Nash equilibrium in the sense of classical game theory [28].In other words, we assume that each agent uses the minimum-latency path from its source to itsdestination, given the link congestion caused by the rest of the network users. It is well-known thatNash equilibria do not in general optimize social welfare; perhaps the most famous example is thatof “The Prisoner’s Dilemma” [12, 28]. We are then interested in comparing the total latency of aNash equilibrium with that of the optimal assignment of traffic to paths.This line of research was recently initiated by Koutsoupias and Papadimitriou [22], who bothconsidered network routing as a non-cooperative game (although in a different model than ours,and only for two-node networks) and proposed the worst-case ratio of the social welfare (suitablydefined) achieved by a Nash equilibrium and by a socially optimal set of strategies as a measure ofthe performance degradation caused by a lack of regulation. As articulated in [22], this questionstudies the cost of the lack of coordination inherent in a non-cooperative game, as opposed to thecost of a lack of unbounded computing power (studied via approximation algorithms) or the cost ofalackofcomplete information (studied via on-line algorithms).For most of the paper we assume that each agent controls a negligible fraction of the overalltraffic. For example, each agent could represent a car and the network a highway system, or agentsmight represent individual packets in a high-bandwidth communication network; an equilibriumthen represents a steady-state in the system (perhaps best achieved in a road network by dailycommuters during rush hour and in a communication network by persistent or long-running ap-plications). Under this assumption, a feasible assignment of traffic to paths in the network canbe modeled as network flow, with the amount of flow between a pair of nodes in the networkequal to the rate of traffic between the two nodes. A Nash equilibrium in the aforementionednon-cooperative game then corresponds to a flow where all flow paths between a given source anddestination have the same latency (if a flow does not have this property, some agent can improve itstravel time by switching from a longer flow path to a shorter one). Beckman et al. [3] showed thatif the latency of each network link is a continuous nondecreasing function of the flow on the link,then a flow corresponding to a Nash equilibrium always exists and moreover all such flows havethe same total latency. Thus, we can study the cost of routing selfishly via the following


View Full Document

CMU CS 15892 - How Bad is Selfish Routing?

Documents in this Course
Lecture

Lecture

35 pages

Load more
Download How Bad is Selfish Routing?
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view How Bad is Selfish Routing? and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view How Bad is Selfish Routing? 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?