May 29, 2024
Internet Network Flow

Routing game over time in the Internet network with delay on Routers

In a routing game on the Internet, players intend to send a fixed amount of flow from source to the destination through the network consist of millions of public and private sub networks. A player strategy is the chosen path from source to destination. The time that it takes to a flow particle (a packet) to arrive to destination depends on chosen path by the player and the routing chosen by other players. In an equilibrium flow, no player can unilaterally chooses a different path (i.e. changes its strategy) to reduce the time taken to arrive to sink. There exist vast literature around static selfish routing game, while routing games over time is fresh and active area of research. Internet network is one of fascinating area of routing games researches. Although many results on routing games over time have been achieved over the last years, the previous researches did not consider an important feature of the Internet network. In all previous researches, Nash equilibrium and price of anarchy was studied in the networks with only delay on edges, however in real world router’s latency is a key parameter of Internet which its efficacy on equilibrium is unavoidable . In the Internet network, packets are transmitted through the router. Like other network facilities, a router has a limited amounts of resources (e.g. physical memory, CPU, internal links and etc). Thus the routers have limited capacity to route flow particles (packets) through the network to the destination, therefore if, at some point in time more flow particles (packets) enter into router than its capacity, they form a queue in the router.

In this paper we present a new model for routing game over time in the Internet network based on ”Dynamic queuing” model considering flow dependent routing-delay on routers. The Dynamic queuing model first used by Yagar and Bhaskar represented a Stekelberg strategy to make the total price of anarchy of equilibrium flow no worse than 2e/(e − 1) times the optimal, based on this setting. In our article I show that the new model (network with flow dependent delay on edges and nodes) is reducible to simple model (network with only flow dependent delay on edges), then we represent an polynomial-time algorithm to reduce the original network in this model to the ”node-expanded network”.

The Article can be found here

Leave a Reply

Your email address will not be published. Required fields are marked *