Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Vulnerability of Selfish Routing to Attacks: Game-theoretic Models and Initial Results

Published

Author(s)

Daniel I. Genin, Vladimir Marbukh, Anastase Nakassis

Abstract

This paper reports on work in progress on assessing and mitigating selfish routing vulnerability to strategic attacks. We explain mechanisms leading to this vulnerability, propose the corresponding game-theoretic model, solve this model for some particular case, and discuss implications of the vulnerability phenomenon. Our approach extends the well established research agenda on selfish routing by incorporating attacker(s) as separate agent(s) in the corresponding game. While each user makes its routing decision in attempt to minimize its transportation cost, the attacker(s) manipulate the link costs for the purpose of increasing the aggregate transportation cost to all or some users, e.g., by damaging the physical infrastructure or inserting malicious traffic as in Denial of Service (DoS) attack. Our initial results demonstrate that even weak attacker is capable of inflicting a serious damage measured by increase in the price of anarchy as compared to the case without attacker. Presence of attacker(s) can make Braess s paradox more pronounced. These initial results demonstrate importance of further research on the effect of the adversarial actions on selfish routing and a possibility of mitigating of this effect.
Proceedings Title
World Congress on Engineering 2010
Conference Dates
June 30-July 2, 2010
Conference Location
London, GB

Keywords

Selfish routing, attacks, game-theoretic model, price of anarchy.

Citation

Genin, D. , Marbukh, V. and Nakassis, A. (2010), Vulnerability of Selfish Routing to Attacks: Game-theoretic Models and Initial Results, World Congress on Engineering 2010, London, GB, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=905644 (Accessed December 3, 2023)
Created June 29, 2010, Updated October 12, 2021