Diagnosing inter-domain routing problems in the Internet is hard. BGP, the defacto inter-domain glue, is designed for routing, not diagnosis. It is extremely chatty - the most minor connectivity change produces hundreds of BGP messages and a major peering loss can generate millions - and making sense of the deluge of data remains challenging. We have developed statistical techniques to extract the large-scale structure of BGP events and visualization techniques to display that structure in operationally meaningful ways. These tools can be used to detect routing anomalies in real-time. We show case studies of routing instabilities at a Tier-1 ISP and a large institutional network, automatically diagnosed by our tools. We present drawbacks in using BGP events alone to understand inter-domain routing, and discuss how to solve them through the integration of additional data sources.

A scalable object location service can enable users to search for various objects in an environment where many small, networked devices are attached to objects. We investigate two hierarchical, self-configuring or unattended approaches for an efficient object location service. Each approach has its advantages and disadvantages based on the anticipated load. The first approach, SCOUT-AGG, is based on aggregation of object names. The second approach, SCOUT-MAP, is based on indirection, where information about an object is stored at the locator sensor for the object. The relative efficiency of SCOUT-AGG and SCOUT-MAP can be characterized by the query to mobility, update rate of the system. SCOUT-AGG performs better for low query to update rate but its performance deteriorates in general relative to SCOUT-MAP as the queries to update rate increases. The rate of performance deterioration depends on query specificity (i.e., queries for a specific object or for any object of a particular type). SCOUT-MAP generally exhibits better load balancing than SCOUT-AGG for various scenarios. We support the above results through simple analytical modeling and simulation.

Multicast routing enables efficient data distribution to multiple recipients. However, existing work has concentrated on extending single-domain techniques to wide-area networks, rather than providing mechanisms to realize inter-domain multicast on a global scale in the Internet. We describe an architecture for inter-domain multicast routing that consists of two complementary protocols. The Multicast Address-Set Claim (MASC) protocol forms the basis for a hierarchical address allocation architecture. It dynamically allocates to domains multicast address ranges from which groups initiated in the domain get their multicast addresses. The Border-Gateway Multicast Protocol (BGMP), run by the border routers of a domain, constructs inter-domain bidirectional shared trees, while allowing any existing multicast routing protocol to be used within individual domains. The resulting shared tree for a group is rooted at the domain whose address range covers the group's address; this domain is typically the group initiator's domain. We demonstrate the feasibility and performance of these complementary protocols through simulation. This architecture, together with existing protocols operating within each domain, is intended as a framework in which to solve the problems facing the current multicast addressing and routing infrastructure.

We present a scalable VC routing protocol based on the viewserver hierarchy. Each viewserver maintains a partial view of the network. By querying these viewservers, a source obtains a merged view that contains a path to the destination. The source then sends a setup request packet over this path to reserve resources. We use simulation to compare our protocol to a simple approach that maintains a full view of the network. In addition to the savings in storage, our protocol performs as well or better in terms of the VC carried load and blocking probability over a wide range of real-time workload.

We present an interdomain routing protocol based on a new hierarchy, referred to as the viewserver hierarchy. The protocol satisfies policy and type of service (ToS) constraints, adapts to dynamic topology changes including failures that partition domains, and scales well to a large number of domains without losing detail (unlike the usual scaling technique of aggregating domains into superdomains). Domain-level views are maintained by special nodes called viewservers. Each viewserver maintains a view of a surrounding precinct. Viewservers are organized hierarchically. To obtain domain-level source routes, the views of one or more viewservers are merged (up to a maximum of twice the levels in the hierarchy). We also present a model for evaluating interdomain routing protocols, and apply this model to compare our viewserver hierarchy against the simple approach where each node maintains a domain-level view of the entire internetwork. Our results indicate that the viewserver hierarchy finds many short valid paths and reduces the amount of memory requirement by two orders of magnitude.>

The authors present a new viewserver hierarchy and associated protocols that (1) satisfies policy and type-of-service (ToS) constraints, (2) adapts to dynamic topology changes including failures that partition domains, and (3) scales well to a large number of domains without losing detail. Domain-level views are maintained by special nodes called viewservers. Each viewserver maintains a domain-level view of a surrounding precinct. Viewservers are organized hierarchically. To obtain domain-level source routes, the views of one or more viewservers are merged (up to a maximum of twice the levels in the hierarchy). Their evaluation results indicate that the viewserver hierarchy finds many short valid paths and reduces the amount of memory requirement by two orders of magnitude.>

An interdomain routing protocol based on superdomains that always finds a valid path if one exists is presented. Both strong and weak constraints are maintained for each visible superdomain. If the strong constraints of superdomains on a path are satisfied, then the path is valid. If the weak constraints of a superdomain are satisfied but the strong constraints are not, the source uses a query protocol to obtain a more detailed "internal" view of the superdomain, and searches again for a valid path. The protocol handles topology changes, including node/link failures that partition superdomains.>

There are two approaches to adaptive routing protocols for wide-area store-and-forward networks: distance-vector and link-state. Distance-vector algorithms use O(N x e) storage at each node, whereas link-state algorithms use O(N2), where N is the number of nodes in the network and e is the average degree of a node. The ARPANET started with a distance-vector algorithm (Distributed Bellman-Ford), but because of long-lived loops, changed to a link-state algorithm (SPF). We show, using a recently developed network simulator, MaRS, that a newly proposed distance-vector algorithm (ExBF) performs as well as SPF. This suggests that distance-vector algorithms are appropriate for very large wide-area networks.