2004 Inter-Domain Routing Workshop Notes
May 2004

Geoff Huston

In May 2004 an Inter-Domain Routing Workshop was held in Amsterdam, just before the RIPE-48 meeting.

Happy Packets

Randy Bush

The question posed here is whats the relationship between the control plane and ther data plane regarding routing instability? Is the quantity of BGP updates good or bad in terms of moving data packets through the network? There are comments about BGP announcement rates equated to some form of bad behaviour of the BGP routing system. In this work there is an attempt to see 'real' measures of "good" and "bad" from the point of view of data flows, rather than just equating of BGP protocol update rates against the 'soundness' of the Intenet.

The work reported here looks at small events, not big universal events across the entire routing system. The questions posed here are concerned with "routing quality" and the metrics of "good routing". The presentation makes the point that 'good routing' is when customers get packets, and the metrics of this are the usual collection of measurement of jitter, drop, reordering and latency. The work described is setting about measuring packet behaviour when a stream of packets is imposed over a routing change. The setup requires a set of packet injectors, a receiver, and an induced routing change close to the reciever that may cause a path change.

The receiver is a dual-homed beacon, and the beacon regularly undertakes all possible transitions in a regular manner.

The injectors are configured to generate a regular timed packet stream using http://planet-lab.org as the platform.

The packet stream is UDP sequenced timestamped packet streams

The initial results indicate that there is an interval of packet drop associated with a change of home AS. There are also intewrvals of intermittent path restoration on a change of origin AS.

The work also looks for evidence of correlation between the duration of the instability in the routing control plane and the duration of instability in the data plane. The duration of BGP updates for each type of transition is measured and correlated against the data plane loss interval. Interestingly there is not a tight correlation here.

The greater the router hop count between sender and reciever the higher the loss rate across a routing transition (in other words, a longer duration of data plane loss). Also, curiously, some sites have a higher loss rate in steady state, and improve their performance during phases of routing change.

The presented results appear to indicate that there is no direct correlation between the number of routing updates and the duration of the data plane instability. Data plane instability directly related to control plane instability

Non-routing Routers

Simon Leinen
Source Routing is not used today in the Internet. The presentation poses the question: why shouldn't hosts pick paths? Benefits in such an approach are proposed in terms of selection of a path characteristic that matchs the application's intended or required behaviour. Also this could include the concept of hosts trying alternate paths to get best match of characteristics to application behaviour, rather than attemnpting to get the routing system to signal in advance the supposed path characteristics.

There are a number of questions about this approach, including that of how hosts could be supplied with a collection of loop-free alternate routes, and the granularity of routes.

Personally I have some reservations about this approach. Part of the convergence of the path selection algorithm in a distance vector routing system to obtain loop free paths is pruing based on minimizing a per link metric. Unless you move to an LSP-styled protocol how could alternate paths be generated that are not prone to loop creation? Its also hard to see the relationship of this with QoS routing. In QoS routing you ask for a path with certain characteristics - in this approach you speficy a path and test it for certain characteristics. As I see it scaling in the routing system depends on abstraction of information, but if you want to get explicit hop-by-hop source routing then its not clear how this could be abstracted.

The approach presented here includes the concept of 'path servers' to help hosts select paths. How such path servers operate is an open issue. The Source Routing proposal of Saltzer, Reed and Clark of c 1980, is cited, as well as NIMROD, UUCP, PIIP, landmark routing, and others, all inspired from peer-to-peer networks. The observation is that much of this is 1980's terminology and research.

The objectives cited here are host selectable paths, path servers and link pricing, with potential outcomes of 'smarter' upper layers, better incentives for matching path characteristics to application requirements and richer network topologies.

Internet Routing Registry System

Larry Blunt

It appears to be a 'loose concept' rather than an authoritative and complete source of reference information of routing policy intent. The IRR system is a loosely coordinated effort over some 50 routing registries. There is some confusion between the IRR, the RABD, and the whois servers. There is a consequence of inconsistent data collected from varous IRR sources. There are difference in formats, languages and policies in the various IRRs.

The presentation included a a survey of RFCs on RPS, plus the CRISP work. RFC 2725 provides the framework for RPSL authority. Once you get outside the RIPE and APNIC regions and outside the recent allocatins into legacy space, then there are real issues here with authority derivation.

It is unclear how the IRR effort can provide a broader set of accurate, up to date and authoritative information. it currently encompasses a collection of disparate efforts or varying quality and currency.

There is some hope that CRISP could be used to improve this situation, but no details on this were provided.

Comments were made regarding the distributed nature of the database, so there there is an explicit 'repository' field. Also distributing the data weakens the authority model of the IRRs. i.e. how can you trust a particular IRR source? Also authentication is associated with the object, not the registry.

Nemecis - IRR Analyzer

George Sigano

This is first effort to quantify the accuracy of the IRR.

The accuracy of the IRRs has not been quantified, and RPSL is a complex description language. Nemecis is an implementation of a framework for policy analysis, that is intended to check the registered policies for accuracy, completeness and comparison with actual BGP data.

RSPL describes routes and communities., plus a structure to group routes and use the group as an alias in the specification language. The complexities of the environment and the expressive ability of the language can lead to internal inconsistencies.

Nemecis attempts to analyse the policy by deriving relationships, examining policies, and identifying inconsistencies. It works on a principle of classifying relationships into customer, peer, upstream relationships and a new concept called "sibling' (which appears to be a partitioned AS set controlled by a single entity), and applies a conventional rule of route propagation between these classes, and then compares this calculated model with the IRR data to see if there is a correlation.

Compact Routing

KC channelling Dimitri Krioukov

There are theoretical limits related to routing on graphs. This an analysis exercise intended to expoose whether there are theoretical limits to routing on graphs motivated by scaleability concerns, topological density, allocation policies, traffic engineering, etc. There have been various fixes proposed, such as routing based on AS sets rather than prefixes.

The presentation proposes that such activities postpones the problem, but do not directly address it.

There is a tradeoff between memory space, adaption cost and 'stretch' of path length.

Inter-Domain Resilience

Christoph Riechert

This presentation looks as a mechanism for inter-domain routing resilience based on an approach of maintaining 2 next hops for each destination. It is noted that there is the possibility of loop formation close to the destination.

This does appewar to have the potential for high speed dynamic failover, but it does require a network to be bi-connected, in that each node must belong to a triangle. Can the scheme be extended to inter-domain? Can you maintain end to end path choices in a distributed manner?

It is claimed that this in possible in a slightly constrained environment, where border routes to a neighbour AS must be directly interconnected. It is possible to construct networks that can maintain two nexthops for all destinations that are essentially loop free. The critical area is the BGP/IGP interaction.

Stablizing the BGP Control Plane

Gotz Lichtwald

This work is motivated by the observation of unconstrained amplication of BGP updates. A fast interdomain failure reaction as an augmentation to BGP using constrained scope of propagation of the repair. Fast Soped Rerouting is a fine grained approach to BGP. In the case of failure set up a fast substitute path and if the original path recovers quickly then press on and emit no BGP updates.

This leads to one of the more fundamental questions in the inter-domain routing space: what is the base cause of BGP updates - physical topology outage or preference/policy oscillation?

Up Down routing marking

This approach is an attempt to identity route policy anomalies by attempting to apply an analysis of route peering and classify each into an up/down/level (provider / customer / peer) relationship. The observation is that all paths in a consistent routing environment have no "valleys" (down - * - up).

It is an interesting approach, but assumes symmetric business relationships and the transitivity of up/down marking. It may not be the case that both parties to an interconnection have a consistent view of that interconnection.

Detecting Multi-Homing

Assertion that you can detect multihoming throug prefix comparison. Look for all prefixes that have a fist hop AS change and label them as multihomed. For this to work the window needs to be a short(ish) size!

BGP Wedgies

Tim Griffin

Source similar to MED oscillation, but no oscillation is involved here. They are the outcome of policy interactions that are hard to debug when they occur.

For example, use of a community that signals to de-pref routes. WHat happens when a multihome when primary fails and restoration dcoes not compoletely restore traffic off the backup? i.e. the configuration has 2 distinct solutions and the state will not completely flop from one soln to the other.

Then this is non-deterministic. How bad could this get? i.e. is there a situation rewquiring multiple simultaneous resets to kick from one state to another? There is a mutual dependency primary / secondary that will wedge. In this case the wedge gets resolved with prefix withdrawal and reannouncement with community

There may be nosolution to a BGP config, or many solutions. How do you get one nominated solution from multiple choice?

complex policies (weights, communities, pref setting) increase the changes of routing anomalies.

A configuration that has multiple solutions, but no single AS has sufficient knowledge to unwedge.