[Irtf-rr] draft-irtf-routing-reqs-00.txt
Dmitri Krioukov
dima at krioukov.net
Thu Aug 14 21:51:27 EDT 2003
Avri,
I'd like to comment on those TBDs you're concerned with.
I don't think we'd be able to come up with any reasonable
numbers for stability/convergence-related TBDs. There are
two reasons for that.
First, there are very few results on the theoretical
lower and upper bounds for adaptation costs (i.e.
number of messages generated per topology change,
their sizes, etc.) for dynamic routing on graphs
with arbitrary topology (i.e. generic graphs). The
progress on this subject in distributed computing has
been *very slow* over the past 20 years, one of the
reasons being, I think, that the problem is quite hard.
(I'm talking not about BGP convergence, but about
fundamental bounds for any kind of routing algorithms.)
Furthermore, the results that do exist are quite pessimistic
(for example, for *any* shortest-path routing
algorithm, there *exist* an n-node graph and such
topology change in it that *not less* than n messages
are required to process this topology change).
And there are no theoretical results at all
for routing (dynamic or static) on networks with
Internet-like topologies (scale-free networks)
(except our latest publication :)
Given this fundamental lack of knowledge, how can
we come up with any realistic numbers for convergence
then?
The second reason is related to p.3.10.1 in the draft.
If we allow for freedom in network modeling, then
convergence might not be an issue at all (recall
the physical routing discussion, etc.).
So that, I'd propose either to leave it as is or
to restructure the whole thing to something like:
--
Given the fact that there are currently no known bounds
for adaptations costs for dynamic routing on scale-free
networks, the precise formulation of the convergence
requirements is a subject of future research.
--
I think that scalability related part (i.e. ~"should scale
indefinitely") is OK.
--
dima.
http://www.krioukov.net/~dima/
> -----Original Message-----
> From: irtf-rr-bounces at puck.nether.net
> [mailto:irtf-rr-bounces at puck.nether.net]On Behalf Of avri
> Sent: Tuesday, August 12, 2003 2:55 AM
> To: irtf-rr at puck.nether.net
> Subject: [Irtf-rr] draft-irtf-routing-reqs-00.txt
>
>
> Hi,
>
> First apologies for talking so long to deliver. I finally got the the
> joint draft done. About a year late.
>
> ---
>
> Title : Requirements for Inter Domain Routing
> Author(s) : A. Doria et al.
> Filename : draft-irtf-routing-reqs-00.txt
> Pages : 70
> Date : 2003-8-11
>
> These requirements for routing architectures are the product of two
> sub-groups with the IRTF Routing Research Group. They represent two
> individual and separate views of the problem and of what is required
> to fix the problem. While speaking of requirements, the document is
> actually a recommendation to anyone who would create a routing
> architecture for the Internet in the coming years.
>
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-irtf-routing-reqs-00.txt
>
> ---
>
> This doc, except for the intro is a faithful (I hope) representation of
> the final draft of each of the two sub-groups contributions. In
> working through them (thanks to xml2rfc and Elwyn for the formatting) I
> found myself wondering how much the requirements had changed over the
> year that these sat. In some respects, I believe they did, though
> not in any major sense. The work that has gone into shoring up the
> current architecture has certainly made it appear more resilient.
> Perhaps not so resilient as to last until the current projected
> delivery date for:
>
> > "THE
> > right choice in the long run" for the Internet inter-domain routing
> > I am happy to report that this work, aka as a LTSFGTC (Long Term
> > Solution For Generations To Come), is in progress and is expected
> > to be published in RFC100000.
> (from the writings of Yakov on the Routing Area list )
>
> But in general I believe that the superset of requirements for long
> term solutions is fairly well expressed by this unified document. and
> yes, many of the issues look like they would still require research for
> a solution.
>
> The original idea had been to create this unified draft, put it through
> a RG review and then have it released as an informational RFC.
> Personally, I would still like to see that happen.
>
> Before that can be published, though, there are two instances of TBD
> left in the document that I think need to be replaced.
>
> - in 2.1.8 (from sub-group a requirements) there are two instances
>
> > We have two separate scopes over which we can set requirements with
> > respect to convergence:
> >
> > 1. Single Change
> > In this requirement a single change of any type (link addition
> > or
> > deletion, router failure or restart, etc.) is introduced into a
> > stabilized system. No additional changes are introduced. The
> > system must restabilize within TBDms. This requirement is a
> > fairly abstract one as it would be impossible to test in a real
> > network.
> >
> > 2. System-wide
> > Defining a single target for maximum convergence time for the
> > real Internet is absurd. As we mentioned earlier, the Internet
> > is large enough and diverse enough so that it is quite likely
> > that new changes are introduced somewhere before the system
> > fully
> > digests old ones.
> >
> > So, the first requirement here is that there must be mechanisms to
> > limit the scope of any one change's visibility and effects. The
> > number of routers that have to perform calculations in response to a
> > change is kept small, as is the settling time.
> >
> > The second requirement is based on the following assumptions
> >
> > - the scope of a change's visibility and impact can be limited.
> > That is, routers within that scope know of the change and
> > recalculate their tables based on the change. Routers outside of
> > the scope don't see it at all.
> >
> > - Within any scope, S, network changes are constantly occurring and
> > the average inter-change interval is Tc seconds.
> >
> > - There are Rs routers within scope S
> >
> > - A subset of the destinations known to the routers in S, Ds, are
> > impacted by a given change.
> >
> > - We can state that for Z% of the changes, within Y% of Tc seconds
> > after a change, C, X% of the Rs routers have their routes to Ds
> > settled to a useful answer (useful meaning that packets can get
> > to
> > Ds, thought perhaps not by the optimal path -- this allows some
> > 'hunting' for the optimal solution)
> >
> > X, Y, Z, ARE TBD
>
>
> - 3.1.7 (from sub-group b requirements) there are 3 X's and 3 TBD
>
> > 3.7 Performance requirements
> >
> > Over the past several years, the performance of the routing system
> > has frequently been discussed. The requirements that derive from
> > those discussions are listed below. Currently the required values
> > for these performance requirements are left for further discussion.
> >
> > R(49) The routing system MUST support domains of at least X systems.
> > A system is taken to mean either an individual router or a
> > domain.
> >
> > R(50) Local convergence SHOULD occur within X units of time.
> >
> > R(51) The routing system MUST be 99.99x?% available.
> >
> > R(52) The routing system MUST be reliable as measured by TBD.
> >
> > R(53) The routing system MUST be locally stable as measured by TBD.
> >
> > R(54) The routing system MUST be globally stable as measured by TBD.
> >
> > R(55) The routing system SHOULD scale to an indefinitely large
> > number
> > of domains.
> >
> > In many cases there has been very little data or statistical
> > evidence
> > for many of the performance claims being made. In recent years
> > several efforts have been initiated to gather data and do the
> > analyses required to make scientific assessments of the performance
> > issues and requirements. In order to complete this section of the
> > requirements analysis, the data and analyses from these studies
> > needs
> > to be gathered and collated into this document. This work has been
> > started but has yet to be completed.
>
> My assumption is that we should either arrive at some numbers for those
> TBD, or at least, a documentable method for understanding the size and
> scope of those numbers. I am hoping this list is willing to take up
> this discussion.
>
> Also a discussion of the continuing appropriateness of the requirements
> would be a good thing to see. Plus anything else I may have messed up
> in moving the drafts together.
>
> As next steps, I will be be ready to do quick edits of this doc so that
> it can be released as an informational document.
>
> I am also working on an update of the History companion document. It
> needs a bit more work since a year of history has accumulated since the
> last edit. I will, however, put out a version in the next week or so
> so that others can correct the notion of history that is documented in
> that draft before sending it on to become an informational RFC.
>
> Other then that, it would be good to see this RG tackle some of the
> issues, even if the immediate result is not Yakov's LTSFGTC. I am
> happy to see the Routing Area tackle immediate issues such as the
> loading of functionality on BGP, but I do believe that there are useful
> problems, both near term and long term that this group, collectively
> and in smaller groups, could work on productively. That is if the
> routing research group does not blink out of existence in the near
> future. I believe that would be a pity.
>
> a.
>
> _______________________________________________
> irtf-rr mailing list
> irtf-rr at puck.nether.net
> http://puck.nether.net/mailman/listinfo/irtf-rr
More information about the irtf-rr
mailing list