2.9.3 Routing Group (RRG)


Chair: Avri Doria avri@psg.com
Interest Mailing List: irtf-rr@puck.nether.net
Subscription and mailing list management: http://puck.nether.net/mailman/listinfo/irtf-rr
Web Site: http://psg.com/~avri/irtf/rrg-page.html
Research Group Chat Room: rr@irtf.xmpp.org

This research group is chartered to explore routing problems that are important to the development of the Internet but are not yet mature enough for engineering work within the IETF. The group will work closely with the IESG Routing Area Directors to ensure the free flow of information in both directions and avoid duplication of work with the various IETF working groups.

The first steps taken in the RRG consisted of conducting a survey the state of the art in routing research, the needs of the user community (ISPs, router vendors, etc.) and the history of routing requirements. While this work will be ongoing as the state of research and of needs changes, the next step involves taking a number of the problem brought out in the analysis and focusing on these issues.

Going forward the RRG will focus on a small number of specific problems. The problem set will include both short term issues and long term issues and will cover both IPv4, IPv6 and special circumstances brought into play by dual stack. The near term issues are those where the intent is to provide input into the IETF routing community on issues that are of current importance. In the case of these short term issues, the results would be expected within an 18 month period. The long term issues are those where the goal is to develop new technologies for the evolving Internet including investigation of new Internet inter-domain architectures and protocols.

The areas for research topics to be investigated include:

This group will have an open general discussion mailing list where any topic of interest to the routing research community can be discussed. Small limited membership subgroups will be formed to do research into focused issues. These subgroups will be responsible for reporting on their efforts to the general mailing list on a quarterly basis. The RRG, as a whole, will hold open meetings from time to time to solicit input from, and supply information to, the community. In particular, once per year there will be a review of the group's activities held at an IETF meeting.

The output of the group is to consist of Informational and Experimental RFCs as well as Journal Articles on the topics covered by the subgroups.

The current set of sub-groups includes:

Other subgroups will be formed as the topics and plans reach maturity.

Internet Drafts

Requirements for Inter Domain Routing
Analysis of IDR requirements and History


None yet

Other Publications

None yet

Current Meeting Report

IRTF RRG Meeting - 60th IETF San Diego 4-Aug-2004 9:00

Attendance: approx 110 people (estimated by Kevin)

Scribe: Kevin Fall (Intel)

Chair: Avri Doria

Been some time since met at an IETF meeting Avri has been trying to 're-energize' and continue the work in RG

Speakers: Avri, John Loughney, Elwyn Davies, Dmitri Krioukov, Susan Hares, Thierry Ernst


  • RFC Editor Comments and response to routing requirements document


  • Updates to history document


  • New subgroups-

  • BGP stability <a sort of short-term subgroup>,


  • RRG scalability


  • Report on MicroMobility subgroup


  • Research Opportunities in Nemo


  • Discussion: How should RRG (and IRTF more generally) deal with shorter-vs-longer term research

Request to change agenda [no responses]

RFC editor comments:

Routing Requirements

-02 was returned to RG for rework due to some issues

-03 fixes some

- 04.txt will be released sometime following the meeting with further fixes and changes


There were historically 2 subgroups of the RRG:

  1. compatible architecture - Group B

  2. non-necessarily compatible architecture [no past constraints] – Group A

The question was, how similar were (1) and (2) were going to be. It seemed maybe there is an 80% overlap. Eventually decided to combine output of 1> and 2> into one doc resulting in the the routing requirements document-- including the output of both group A and group B without major modification.

This doc has been ping-ponging with the rfc-editor since then

Discussion of specific issues:

  • security- IESG may want something. Avri is not sure how strong this need to be given that RRG is not a WG. Ran Atkinson offered to author a 'real' security section. Should we?

  • use of MUST/SHOULD/MAY Avri- basically de-capitalize. There is an intro that says that the "requirements" in the doc really are "suggestions" anyhow

  • it says Radia Perlman must be able to explain the architecture in an hour. IESG says this is a silly requirement. Ran A. suggests to de-personalize the comment to refer to a 'reasonable practitioner' {this was a group A comment}

Dmitri-- this shouldn't be a requirement. We cannot expect the architecture to be explained in an hour.

Avri-- I wouldn't feel comfortable removing the complexity argument, but I could remove her name.

Show of hands:

option(1)- stay what is in there and explane

option(2) - replace 'Radia' with generic version

Vast majority chose option(2)

  • Need a reference for the Mike O'Dell comment in 2.1.2 *Need a

  • reference for the Dave Clark comment in 2.2.3 [probably 1991]

  • other content?

  • enlarged security section

  • a section on measurement other non group A/B contribs

Pro: would make doc stronger

Con: wouldchange the character and take time

Re: enlarged sec section

Rand: I said I could edit the security section to say A,B,C are references to security. I didn't really volunteer to develop new content there

Re: measurement:

Avri: my inclination is not to do this

Phil ?[JHU]: its tough to get information now, so building some form of consideration for measurement would be good Avri: I would content there are various places where there should be a capability to manage w/out directly identifying what specifically should be measured

Dmitri: Its also somewhat more generic. There is a 'performance' question, which strongly depends on everything in the net, including topology and other things.

Avri: does that mean you think yes? I am concerned we have security but not manageability sections in documents. I could put the manageability section into the document. I sort of resist this because I am trying to reflect what the RG folks talked about. I could put in a section simialr to the Securlty section that points to section in the Group A and Group B sections that speak about manageability. Shall I do this?

Group: most seem like this is a good idea

Kevin: what will be done with the doc?

Avri-- this group and hopefully groups in the routing area in IETF will use it for guidance in creating new routing architectures. For new sub-projects in RRG, we will use it to see how future proposals compare to the routing requirements

Elwyn Davies - elwynd@nortelnetworks.com -

Updates to The IRTF RRG Routing History Document, editor

This draft contains the other half of what group B did. This is a new version:draft-irtf-routing-history-01.txt has effectively been dormant for approx. 3 yrs

Is it really history?

  • yes: describes at least partially how IDR got to where it was in 2001

  • partial view of what happened since then

  • also: a problem statement and a summary of current work

Updates since -00:

  • added notes on trials and progress of multi6 added notes on

  • DARPA NewArch

Believes that document is still relevant

What next?

  • has the world of IDR <RFC1126> moved on?

  • Do we know anything more now?

  • are new tools available?

  • look at the academic research revisit the problem statement

Known missing pieces

  • summary of ISO work on IDR review impact of RFC2547 now that it is deployed

  • update on views of QoS routing + impact of DiffServ

  • impact of DTN and sensor networks

Avri-- how many people have read this doc? (show of hands-- quite a few)

  • Should this be a history document, or should it be a living doc?

  • should it be renamed?

  • need people to: record their oral history, write sections, be reviewers

Dmitri-- this question should be undertaken at routing area

Rudiger Geib-- inter-domain traffic engineering; what about some sort of delay minimization routing?

Elwyn-- my co. is very interested in minimizing delay; it seems important

Patrice Lyons-- when talking voip, if voice is just another kind of data; I have been working in this area. I could help to write it up.

Elwyn-- I mention it because its a hot topic PL-- something about identity management: naming was an issue

Avri-- show of hands?

Should we continue or

release the snapshot?

{About 1/2-1/2 split.}.

Basically the default condition was to just publish it, so maybe we should do this.

Kevin-- doesn't question 2 depend on question 1?

Avri-- not really.

So, should we change its name?

Show of Hands {about even again}.

Same reaction... keep default.

We need, in any case, reviewers. Would like to have a strong review of this in next 2 weeks, esp. by people where were there, who are already historians of routing.

PL-- there is a notion of an evolving document. Could have periodic updates and make sure its updated.

Avri-- that might be interesting. Make a proposal if you want to. It might be useful.

Dmitri Krioukov - Scalability sub-project - dima@caida.org

RR-FS: routing-research future-scalability subgroup

There is an e-mail list. Only some folks on it... certainly there are others working in this area that aren't on the list.

Outline: progress in rtg theory, apps to realistic topologies, future directions, recent advances

  • Tradeoffs between: adaptation costs / memory space / stretch.

  • Space vs stretch known in Kleinrock 1977 paper lots of recent work in the issue of compact routing not much progress in the dynamic routing case:

  • eg. lower bound of omega(n/s) for size n and stretch s {so note that stretch-1 shortest path routing will be painful}

  • Mention of stretch-3 bound as first point at which significant table size reduction can be achieved. In particular can get to omega(sqrt(n))

Recent 'very static' breakthroughs:

L. Cowen (SODA 1999), 'Compact routing with minimum stretch', s=3, ~O(n^(2/3))

    M. Thorup and U Zwick, 'Compact routing schemes', SPAA 2001,

    s=3,~O(sqrt(n)) on trees:

    s=1, ~O(1)(=(1+o(1))log n)

    all forwarding decisions in O(1)

  • these are name-dependent schemes

Recent 'less static' breakthroughs (name independence)

M. Arias, et al., Compact routing with name independence, SPAA 2003

    s=5, ~O(sqrt(n))

I. Abraham, et al., Compact name-independent routing with minimum stretch, SPAA 2004

s=3, ~O(sqrt(n))

Applications to realistic topologies

D. Krioukov, et. al., 'Compact routing on Internet-like graphs', Infocom 2004

avg stretch of TZ scheme on power-law graphs is low

(~1.1, ~70% paths are shortest)

does <not> depend on gamma

<decreases> with n

routing table size is WELL below upper bound (52

vs 2187 entries for n=10k) avg stretch fn has a unique critical pt and the Internet is located in its close neighborhood [quite SURPRISING]

Future Directions

proposal to NSF: toward mathematically rigorous next-gen routing protocols on realistic network topologies


  • routing: name-independent routing scheme on realistic graphs,

  • low avg stretch routing on realistic graphs topology:

  • (what <are> realistic graphs)

  • traceroute-based AS-level topology data

  • comparative analysis of Internet

  • topologies obtained from different data sources

  • evolution: graph entropy-based extensions to

  • existing methodologies

Just started

P. Mahadevan (UCSD) - comparative analysis of Internet topologies

Internet topology evolution modeling (with UCLA)

Very very recent results

Inference of biz relationships between AS's

(w/X. Dimitropolous [GaTech]) Why relevant [to routing]?

  • routing, topology,

  • modeling validity

AS Relationship inference

node-degree based approach

produces many paths inconsistent w/standard BGP

import/export policies [invalid paths]

invalid path minimization approach

(from Berkeley/Lakshme at ICIR)- produces

unrealistic AS hierarchies [e.g. small ISP appears

as provider to UUNET]

our approach

uses multi-objective opt of the two objective fns

above (with weighting) casts the problem as a SDP

relaxation of MAX2SAT (NP hard) problem resolves

the issue of the Berkeley work

http://rr-fs.caida.org will be updated soon mailing list subs,

collaboration requests, etc. send to dima@caida.org

Cengiz Alaettinoglu - was stretch 1.1 avg? What was worst case? (a: 2). What is run-time complexity of algorithm?

Dmitri-- understand this is the static case, so the topology is already known. So, the forwarding is const. time. So you created a graph, labeled it, and assigned the tables. So how to discover the topology is not our problem here. (it is discussed in other papers). How many Dijkstra computations, for example? Let's discuss this later, and you will see.

Geoff Huston-- can you return to AS-relationships. Do you believe the relationship holds for all prefixes or data types. Or are these relationships much more multi-variate. That is, they can vary substantially by data type. When you analyze a BGP table, you may expect strict adherence and you find anomalies, which happen to be deliberate. Therefore, when you start thinking about 'inconsistent' import/export policies... if your granularity is so coarse, you are losing information that is relied upon inthe routing table.

Dmitri-- we are aware of this, and are looking at it, but don't have results yet.

GH-- these anomalies represent a special relationship for a prefix, and may not really be anomalies. The LG work was quite some time ago.

Dmitri-- in Lixin Gao paper, there is mention of sibling link [?]. Its hard to formalize.

GH-- can I press you further? The outcome of today's table are subtly different routing than prefix. Its expression of biz policy as well as path connectivity. I believe it may be quite resistant to compression due to the myriad of specialized policies. Thus its hard to achieve optimization.

Dmitri-- thank you for your comment. We are working on that. These are the 1st results in the direction.

Sue Hares - skh@nexthop.com - BGP Stability Subgroup -


http://psg.com/~avri/irtf/BGP-stability... [?]

Why study BGP stability?

problems in IBGP are one of the prime causes in the demonstrated lack of full global BGP convergence in the Internet

Is somebody already doing this work? If so, maybe we do not need this (sub)group?

Operators struggle with IBGP/BGP

D. McPherson et al, 'Persistent Route Oscillation Condition'

The problem w/BGP convergence C. Labovitz, MSR/Merit [...]

4 different foci:

measure what happens reproduce in lab create theoretical modules to match test out new algorithms proposed

Steps of work

create full list of existing studies / work cull existing work to find effects of IBGP on global convergence only if needed create new investigation and data collection methods to define problem test existing proposals for improvements make recommendations

Solving the problem

lots of passion in this WIRED workshop inspired mixture of research/discussion/testing

convergence testing methodology?

link failure detect -> IGP convergence -> BGP convergence -> other effects | V other effects

BGP has other issues:

igp fail-over tcp effects full mesh IBGP mesh topos may cause BGP to never converge parallel BGP calculations

BGP policy may be costly to run

inflexible boundaries to BGP (iBGP or EBGP) lacks of policy verification prior to load lacks ability to synchronize bgp policy

IGP convergence times OSPF Performance BGP Convergence

debated, not well understood how to benchmark?

BGP AS convergence

key factor is IBGP convergence minor factor- E-BGP transmission

How to Join

visit page and/or send e-mail start w/reading list,

bi-weekly conf calls face-to-face mtgs

will start as open group

Dmitri-- this seems good. The web page is there now? when I tried to summarize areas in this area, I failed to find anything striking about this. It would be very good indeed to know summaries, what simulation environments are available, etc. It hasn't been explicitly demonstrated.

SH--Simulations sometimes don't tell the truth. Ref to Randy Bush-- the 'real' internet is not captured by simulators.

If I get enough interest, I will continue to promote this.

John Loughney - john.loughney@nokia.com -

IRTF RRG Micromobility routing Subgroup

- send him e-mail if you are interested in this


seamoby WG ietf-seamoby-mm-problem-02.txt IP Paging Problem



IP Paging Protocol Assessment


These two things didn't obtain too much interest in the WG, so was moved to RG

There was a bunch of work in the 90s

IETF 52--

Subnet Mobility Problem Statement Micromobility Taxonomy


Micromobility survey/topologies - Carl Williams Mobility

Routing Issues - Dana Blair

IETF 54--

RRG workshop micro-mobility reqts - Alper Yegin Experience of the BRAIN and MIND

- Robert Hancock IP Paging/Routing issues

Overview of the IST Moby Dick Project

** basically went dormant due to lack of interest **

Future -

Are people interested in this topic? Proposal would be survey of existing micromobility protocols (Cellular IP, EMA, HAWAII) Relation to RRG, Ad Hoc Network Systems Research Subgroup, IP Mobility, Optimizations?

Call: who feels this is interesting?


Carl Williams - I have worked with John One of the issues was that it was a closed design team that was selected. Maybe if it was more open it would be better. There have been many more drafts discussed. could we post them?

Avri -- The main list is an open list for anyone to discuss whatever they want to related to Routing you could start a discussion there, that would be fantastic We can also create another list if there is strong interest.

Relating to subgroups: its up to the subgroup chair(s) as to what to do regarding membership. There is an RRG online page that explains the process for opening a new subgroup.

Dmitri -- there are 2 pages there: one is IRTF

Avri -- There is the formal charter (approved by IAB, etc) then there is the active page, incl. subgroups with their own pages

Charter: http://www.irtf.org/charters/routing.html

RRG page: http://psg.com/~avri/irtf/rrg-page.html

Kevin Fall -- In DTNRG there is some relationship between overlay routing and the underlying (perhaps ad-hoc style) routing. That would probably be interest to us.

Route Optimization and NEMO: Is there something applicable to this group?

Thierry Ernst - ernst@sfc.wide.ad.jp



Review of nemo work

Route Optimization in NEMO: The WG is only chartered to produce an analysis of the solution space for Route Optimization in NEMO. The WG will decide what to do next based on the results of the analysis.

mobility problem

types of nets

access, sensors, pans


transportation, health care, military


single mobile IP subnet multiple mobile IP subnet

multi-home nested / multi-homed

mobility patterns


two-tier addressing

mobile IPv6-like, HMIPv6, correspondent router separation ID/locator (e.g. LIN6) multicast overlay network: e.g. ORC routing-based: using conventional or ad-hoc rtg protocols renumbering: changing addr/prefix combined: routing for local mobility [within AS] + 2-tier for global mobility (between AS)

A specific approach may be more suitable for the type of route optimization e.g. ad-hoc routing protocols in nested NEMO solely made of individual mobile IP-subnet elected.

Solution will probably be some combo of above


NEMO wg workload is advancing much more to study in RO network mobility is an opportunity to re-launch the mobility research activity (RRG or elsewhere).

Time Expired - meeting concluded


U-Turn Alternates for IP/LDP Local Protection
Tunnel based FRR
Fast Reroute Using Alternative Shortest Path