Scalable inter-domain routing with TOS, policy and topology resolution
Cengiz Alaettinoğlu · 1995
The Internet has grown into a large heterogeneous internetwork consisting of many separately-administered domains and carrying traffic of diverse applications. As a result, interdomain traffic is now subject to various administrative policy constraints and type-of-service (ToS) constraints. Traditional interdomain routing protocols are no longer adequate because the scaling techniques that they employ lose domain-level ToS and policy information, and hence may eliminate valid routes or allow invalid routes. In this dissertation, I present two interdomain routing protocols that satisfy ToS/policy constraints, scale up to large numbers of domains, and adapt dynamically to topology changes. I also present an evaluation model to compare different interdomain routing protocols. My first protocol introduces a new hierarchy. Special routers called viewservers maintain the view of domains in a surrounding precinct. A viewserver can provide routes between source and destination nodes in its precinct. Obtaining a route between nodes that are not in any single view, involves accumulating the views of a sequence of viewservers. To make this process efficient, viewservers are organized hierarchically, and an associated addressing structure is used. My second protocol is based on aggregating domains hierarchically into superdomains. Traditional protocols using this approach lose domain-level ToS and policy information. I solve this problem by having routers store both a strong set of constraints and a weak set of constraints for each visible superdomain. The strong set (weak set) of constraints of a superdomain is constructed such that if it is satisfied (not satisfied) by a packet, then every route (no route) through the superdomain is valid for the packet. This information suffices for a query protocol to discover valid paths or the absence of such paths. To evaluate and compare interdomain routing protocols, I have developed a computational evaluation model in which one can define realistic internetwork topologies, policy/ToS constraints, interdomain routing hierarchies, and performance measures. Performance measures include memory and time requirements, and number of valid routes found (and their lengths). I have used this model to evaluate my protocols for internetworks of current Internet size. The results indicate that both protocols scale well to large internetworks.