Milestones

2005-2006

The objective of this project is to move towards modelling a variety of more realistic settings for selfish routing: 

• Malicious users:  The users can be differentiated according to their perception of path costs (their disutility function). Typically, a network user would care for his/her own data flow, and try to optimize its delivery speed. But a malicious user would like to disrupt the other users’ goals, or the overall network performance.  One example is a denial-of-service attack, where malicious users would use their own demands in order to overwhelm a server.  The possibilities of malicious behavior are many, and each one of them gives rise to a different model.  We have initiated the study of malicious users and their effect on the network.

• Path pricing:  The introduction of economic disincentives in the form of taxation on the network paths is a powerful tool for the network designer that wants to lure the selfish towards a flow pattern that achieves certain properties (e.g., flow that minimizes the total delay on the network). The users may have the same or different sensitivity on the pricing; e.g., in Quality-of-Service (QoS) networks, a user may be more concerned about the price of a path than its quality (speed) than another user who can afford a more expensive path of better quality. 

• Elastic demands:  A typical assumption for the selfish routing networks studied so far by the theoretical computer science community is that the users’ demands are predetermined constants.  But this is not the case in real life:  an Internet user who downloads music from a server will request much less data from this server if the “connection" is “slow". Therefore the introduction of elastic demands, i.e., demands that depend on the network congestion, greatly enhances the applicability of the proposed research.
  

• Dynamic networks:  The network elements (e.g., edge capacities) may not be constant during the operation, but they may vary with time. For example, certain edges of the network may be available only for certain periods during the day, or certain percentage of their capacity is dedicated to certain kinds of data traffic during certain periods of time. 
  

After the modelling stage, the resulting model can be studied from many different perspectives:

• Equilibria existence:  Although for some of these settings, for example when the network is dynamic, the existence of equilibria has been proven, for others, and especially for combinations of them, the existence of equilibria is not known.  For example, while we have already shown that there are equilibria which achieve the minimum possible total latency through path pricing when the demands are fixed, we do not know whether such equilibria exist for elastic demands.  Although the existence of equilibria is not of great practical importance, it is the necessary first step in the computation of such equilibria.  Hence this is the starting point for our research.
  

• Coordination ratio:  A central question that drives the current research in selfish routing is the comparison between the total (social) cost of a network at equilibrium and the minimum cost that can be achieved when there is a central coordinating authority. This coordination ratio, i.e., the ratio between the cost of the worst equilibrium over the optimum cost achieved by coordination, is an indicator of how much susceptible the network is to sub-par performance when the users are unregulated. The study of this performance measure is in itself a formidable research goal, and we have already made progress in the cases of capacitated networks and networks with malicious users, leading naturally to the following stage.
  

• Network design:  This stage emphasizes the algorithmic (constructive) aspects of selfish routing.  We propose the study of computational methods that will help network designers to determine the performance of a network at equilibrium, and build networks with good characteristics.  For example, one can ask how big a price should a unit of data flow pay through the edges of the network in order to optimize the coordination ratio. If this pricing can be computed, it may point to unrealistically high prices, and this would mean that the designer would have to change other characteristics of the network, e.g., the priority given to classes of users. Vulnerability to malicious users and denial-of-service attacks should also be detectable and preventable.  All these issues give rise to many algorithmic and computational problems, which this project attempts to address.