Nash equilibrium and the price of anarchy in priority based network routing

摘要

We consider distributed network routing for networks that support differentiated services, where services are prioritized by a proportional weighting system. We use the classical Generalized Processor Sharing (GPS) scheme for scheduling traffic on network links. In such a scheme, each type of traffic is guaranteed a minimum capacity rate based on its priority. To model the performance of this scheme and to account for autonomous routing we consider scheduling games on networks. We consider both networks with a set of parallel links (which also applies to processor scheduling) and more general scenarios where the network is a multi-graph. In each of these settings we consider two different routing schemes: Atomic and Non-Atomic. Atomic routing requires all traffic of one type to follow a single path. Non-Atomic routing splits traffic into a flow over multiple paths. For each type of game, we prove either the existence of Nash Equilibrium or give a counterexample. We consider the inefficiency of equilibrium (termed as the price of anarchy) and provide price of anarchy upper bounds under reasonable assumptions. In general, this inefficiency in queuing systems is unbounded. We also provide complexity results on computing optimal solutions and the existence of equilibrium in these games.