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.
Requirements
for Inter Domain Routing
Analysis
of IDR requirements and History
None yet
None yet
|
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 Outline:
psg.com/~avri/irtf/IETF60/irtf-rrg.pdf
psg.com/~avri/irtf/IETF60/rrg-history.pdf
psg.com/~avri/irtf/IETF60/rrg-bgp.pdf
psg.com/~avri/irtf/IETF60/rrg-rrfs.pdf
psg.com/~avri/irtf/IETF60/rrg-mm.pdf
http://psg.com/~avri/irtf/IETF60/rrg-nemo.pdf
Request to change agenda [no responses]
RFC editor comments: -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 History: There were historically 2 subgroups of the RRG:
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:
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)
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?
Updates since -00:
Believes that document is still relevant What next?
Known missing pieces
Avri-- how many people have read this doc? (show of hands-- quite a few)
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
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)
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 Agenda:
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]?
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://www.ndzh.com/IBGP 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 Prehistory-- seamoby WG ietf-seamoby-mm-problem-02.txt IP Paging Problem Statement draft-ietf-seamoby-paging-problem-statement-03.txt IP Paging Protocol Assessment draft-ietf-seamoby-paging-protocol-assessment-01.txt 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 draft-irtf-mm-taxonomy-00.txt 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? =====Discussion: 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 http://www.sfc.wide.ad.jp/~ernst draft-ietf-nemo-basic-support 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 usages transportation, health care, military configurations single mobile IP subnet multiple mobile IP subnet multi-home nested / multi-homed mobility patterns Approaches 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 Conclusion 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 |