Fast Route Convergence, Competition Strategies And Traffic Modeling For Autonomous Systems

The Internet is composed of tens of thousands of self-intereseted domains called Autonomous Systems (ASes). An AS is a collection of routers and links administered by an economic entity, such as Internet Service Provider, company and universities. Border Gateway Protocol is the only inter-domain routing protocol actually used to exchange network reachability information between neighboring ASes. As the Internet has kept growing in terms of both the scales and the amount of applications, many problems emerge on AS level. Appropriate solutions for these problems must be proposed to ensure the healthy and continued development of the Internet.This dissertation covers a series of research on problems of AS level, includes:1. Problem of fast BGP convergence. Empirical measurements have shown that there can be considerable delay in BGP convergence after routing changes. Current solutions either add extra link state information into routing messages, which introduces unacceptable storage cost, or demolish the routing tree and then rebuild it, which decreases the end-to-end connectivity performance. We propose a new heuristic method to speed up BGP convergence by slightly modifying BGP rules of when to send withdrawals and when to send announcements. Moreover, it uses moderate probe cost to replace the aggressive dissemination of withdrawals and can achieve fast BGP convergence with a little memory and communication overhed.2. Problem of traffic competitions between ASes. In today's commercial Internet, an ASes acts as either a Provier or a Customer. How to attract more traffic from one's customers to get more market share and financial gains is a very practical problem for each provider. We explore possible strategies to enhance competition strength of AS against other rivals by forging AS path in routes advertised to neighbors. Our strategies capitalize on the famous Gao-Rexford constraints and have great practical value without violating Internet routing safety.3. Problem of AS traffic characterizing and modeling. Inter-domain traffic engineering is vitally important for high efficiency utilization of network resource and enhancement of end-to-end performance of hosts in different ASes. To effectively control AS traffic, we must understand certain principles of AS traffic generation and change. We use Netflow tools to measure the traffic of a core router in CHINANET backbone for a period of 50 days and propose a model to depict AS level Internet based on the measured data. Our goal is to infer the visual size and daily behavior of each AS through the intensity and fluctuation of the observed traffic. Based on the assumption that each AS consists of independent hosts with the same traffic emission behavior and follows a mixed activation mechanism, our model fits the measured data quite well and is simple enough to be used in traffic engineering and traffic anomalies detection.