Reliable Internet Routing
Abstract
Network routing algorithms responsible for selecting paths to destinations have a profound impact on network reliability experienced by the network users. Unfortunately, performance of state-of-the-art routing algorithms often falls short of users' expectations. (i) The flexibility with which operators of independently administered networks can choose their routing policies allows them to make selections that are "conflicting" and may lead to route oscillations. Oscillating routes have a negative impact on performance experienced by the user, and also cause overloading of the routers with control messages. (ii) Interdomain routing in the Internet is based on trust. As a result, false route announcements can be made by a malicious network operator. Such false announcements can be made even without knowledge of the network operator e.g., due to accidentally misconfigurations or router hijacking. False route announcements may lead to denial of service, or worse yet, traffic can be intercepted without detection of both the sender and recipient. (iii) Even if network routes are stable and secure, unexpected equipment failures may cause performance degradation. It is difficult to pre-configure current routing protocols with all possible failures in mind, and not enough flexibility is offered to balance load in the network evenly. This thesis addresses these three challenging problems. (i) We provide a new theoretical model of interdomain routing and derive the necessary and sufficient conditions that determine which policy combinations lead to route oscillations. Moreover, we also provide a practical polynomial-time algorithm that allows network operators to verify the existence of such conflicts. (ii) To secure routing against malicious attacks, we offer a new secure routing protocol that, unlike earlier attempts is incrementally deployable.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2011
- Accession Number
- ADA571266
Entities
People
- Martin Suchara
Organizations
- Princeton University