Robust Traffic Engineering: Game Theoretic Perspective
Abstract
On-line routing algorithms deal with requests as they arrive without assuming any knowledge of the underlying process that generates the streams of requests. By contrast, off-line traffic engineering algorithms assume complete statistical knowledge of the request generating process. This dichotomy, however, oversimplifies many practical situations when some incomplete information on the expected demands is available, and proper utilization of the available information may improve the network performance. This paper proposes a game theoretic framework for robust traffic engineering intended to guard against the worst case scenario with respect to possible uncertainties in the external demands and link loads. The proposed framework can be interpreted as a game of the routing algorithm attempting to optimize the network performance and the adversarial environment attempting to obstruct these efforts by selecting the worst case scenario with respect to the uncertainties. Two different classes of schemes are considered: first, suitable for MPLS implementation, centralized schemes, and, second, suitable for OSPF-OMP implementation, decentralized schemes.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2002
- Accession Number
- ADA511802
Entities
People
- Vladimir Marbukh
Organizations
- National Institute of Standards and Technology