We extend the original selfish routing setting by introducing users who are oblivious to congestion. Selfish routing captures only the behavior of selfish users, who choose the cheapest route based on the current traffic congestion without caring about the effects of their routing on their fellow users. However, it is more likely that a certain number of network users will be oblivious to congestion. For example, data from low-level QoS services will be routed on predefined routes with no adaptability to network congestion, while data from high-level QoS services will be routed on the fastest paths available. Networks with selfish users may lead to a stable state or Nash equilibrium, where no selfish users can decrease his or her travel time by changing his or her route unilaterally. Traffic equilibria refer to Nash equilibria in networks only with selfish users, and oblivious equilibria refer to Nash equilibria in networks with both oblivious users and selfish users. We study the performance degradation of networks at oblivious equilibrium with respect to the optimal performance. Our model has a fraction a of oblivious users, who choose predefined shortest paths on the network, and the remaining are selfish users. Considering networks with linear latency functions, first we study parallel links networks with two nodes, and then general topologies. We provide two tight upper bounds of the price of anarchy, which is the ratio of the worst total cost experienced by both oblivious users and selfish users, over the optimal total cost when all users are centrally coordinated. Our bounds depend on network parameters such as a, the total demand, the latency functions, the total cost of a traffic equilibrium flow, and the total cost of an optimal flow. The dependency of our bounds on network parameters seems to be inevitable considering the fact that the price of anarchy can be arbitrary large depending on network parameters as oblivious users may choose an arbitrarily expensive path. / Master of Science (MSc)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/14027 |
| Date | 05 1900 |
| Creators | Kim, Taeyon |
| Contributors | Karakostas, George, Computing and Software |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0017 seconds