Characterizing Internet routing dynamics for enhanced network management

Managing large Autonomous Systems (ASes) that constitute the Internet is a herculean task given the scale and complexity of the Internet. Despite enormous efforts, the Internet still falls short of today's expectations in providing stringent quality-of-service guarantees for delay/loss sensitive applications. One of the several reasons for this shortcoming in network management is the lack of thorough and comprehensive understanding of the dynamic behavior of routing protocols that control the Internet.; We begin by analyzing the dynamic behavior of the Interior Gateway Protocols (IGP) during network resource failures. We develop a model to characterize this behavior and show that although these protocols are reliable at larger time scales, the inconsistency in the states of nodes at smaller time scales results in anomalous conditions like routing loops and link overloads. We explain this dynamic IGP behavior based on the protocol design and operational network conditions. We also propose techniques (like Loopless Interface Specific Forwarding) to avoid anomalous network conditions during convergence.; Traditional Service Level Agreements, defined by average delay or packet loss, often camouflage the instantaneous performance (i.e., the service availability) perceived by end-users. Using extensive simulations and analysis, we show that the traditional approach to characterize networks (using graph-theoretic properties like node degree or network diameter) fails to capture its service availability. We define a new set of metrics and propose a simple, yet powerful way to extract the goodness of a network, and show that this concept has several applications in network management including capacity planning, design, and upgrade.; We also investigate the unintentional interactions between multiple overlay protocols, as well as between overlay and IP-layer protocols. We show that allowing overlay networks to make independent routing decisions at the application level could lead to race conditions (due to synchronization) that can manifest as oscillations (in route selection and network load) and cascading reactions. We identify the causes for synchronization and derive an analytic formulation for the synchronization probability of coexisting overlays. We extensively analyze the implications of our study on the future design of overlay protocols and propose several strategies to reduce the impact of race conditions.