Speaker: Eva Tardos
Affiliation: CS Department, Cornell University
Date: 10/19/2000
Time and Location: 4:15 PM, B17 Upson Hall
Title: How Bad is Selfish Routing?

We consider the problem of routing traffic in a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion. We consider a "selfish" routing in which each network user routes its traffic on the minimum-latency
path available to it, ignoring the latency of all other users. We will compare this "selfish" routing to a social optimum, where the objective is to route traffic such that the sum of all travel times---the total latency---is minimized. In general the "selfish" assignment of traffic
to paths will not minimize the total latency, i.e., the lack of central regulation degrades network performance. In this talk we will quantify the degradation of network performance due to unregulated traffic.