As I view this names vs. addresses issue:
Autonomous System numbers are pure identifiers without providing any topology information.
Does it make sense to integrate topological information like the well-known Country Code?
My recommendation: please do not! Kingdoms not only may bleed but also vanish, empires and countries like the soviet union or yugoslavia dissolve so that instead of one country code all of a sudden multiple country codes are needed.etc.
The task I think is to design a routing concept which fits precisely, right right, and which will fit precisely at any time in the future, no matter whether the internet's size grows slowly and steadily or explodes all of a sudden by factor 1000. It should not need any amendments from time to time at all.
Pure integer numbers do not contain immediate topology information. However they enable most powerful ordering schemes as to match this task.
Heiner Hummel
In einer eMail vom 11.10.2005 04:36:28 (MEZ) - Mitteleurop. Sommerze schreibt joel@stevecrocker.com:
I am not sure that this conclusion follows from the work I have seen.
(Caveat: I do not have the level of exposure to the research that you folks
have, nor do I have the level of expertise at seeing the implications of
the research.)
However, the work I saw had a number of interesting properties that might
or might not lead one to either
a) need location dependent names to make them work, or worse
b) need to take a different approach.
For example, most of the approaches seemed to rely on having a set of
labels for the sender to apply to the packet at origination, where those
labels had certain topological properties. For example, they needed to
identify nodes with a certain visibility within a certain range of the
sender and / or the receiver.
Crafting those labels without having either global routing knowledge
(destroying the scaling properties) or having other topological assistance,
such as topologically sensitive names, is not obviously feasible.
I am not saying it is infeasible.
I am certainly not saying that the approaches should not be explored. They
certainly look like interesting starts.
But discarding topologically sensitive names as a tool seems a mistake.
As another example, the techniques all recognize that they have difficulty
with changes in topology. Depending upon what form the topologically
sensitive names take, they may provide some assistance.
For example, in the vein of the old PIP proposal, maybe the name is the
list of near by globally known nodes, along with an identifier known to
those nodes.
Yours,
Joel
PS: I certainly have no objection to a scheme that has packet header
re-writing. And I would like to include a non-topologically sensitive name
in the over all mechanism, as that is needed to address many
problems. (Particularly if one is re-writing labels one needs something
else to attach the security to.)
At 09:17 PM 10/10/2005, Dmitri Krioukov wrote:
>exactly! and we know that in the compact routing framework
>(which is the most fundamental level of abstraction of routing
>problems), name dependence does not buy you much!
>
>indeed, the most surprising finding is that for *generic*
>(applicable to all graphs) routing schemes, name-independent
>routing can be made as efficient as name-dependent one -- at
>least in terms of routing table size vs. stretch trade-off:
>in the both cases, you can construct stretch-3 routing schemes
>with O(n^{1/2}) routing tables. in other words, you cannot
>make routing to perform 'better' by exploiting topology-
>sensitive addresses!
>
>of course, you cannot get name-independence from name-dependence
>'for free' either. the price is roughly: 1) more algorithmic
>complexity; 2) packet headers must be rewritable. it's
>straightforward to see why the both points are unavoidable.
>(recall the best known results
>name-dependent http://www.cs.tau.ac.il/~zwick/papers/route-SPAA.ps.gz
>name-independent http://dept-info.labri.fr/~gavoille/article/AGMNT04.pdf.gz )
>--
>dima.
>http://www.caida.org/~dima/
>
>
> > -----Original Message-----
> > From: Kevin Fall [mailto:kfall@EECS.Berkeley.EDU]
> > Sent: Saturday, October 08, 2005 8:49 AM
> > To: Joel M. Halpern
> > Cc: Dmitri Krioukov; rr-fs@caida.org; rrg@psg.com
> > Subject: Re: [rr-fs] names vs. addresses
> >
> >
> > >
> > > From: "Joel M. Halpern" <joel@stevecrocker.com>
> > > To: "Dmitri Krioukov" <dima@caida.org>, <rr-fs@caida.org>
> > > cc: rrg@psg.com
> > > Subject: Re: [rr-fs] names vs. addresses
> > > Date: Fri, 07 Oct 2005 23:45:30 EDT
> > >
> > > ...
> > >
> > > While that is interesting, most folks looking at that
> > problem tend instead
> > > to look at as a matter of layering. That is, on one level the
> > > communication is in terms of topologically insensitive
> > names (identities),
> > > and at another layer communication is in terms of
> > toplogically sensitive
> > > names (addresses).
> > > Admittedly, this is based on the historically grounded
> > assumption that
> > > routing on the basis of topologically sensitive names is more
> > > effective. But that does still seem to be a reasonable assumption.
> > > some of this is explored in the output of the Name Space
> > Resrach Group.
> > >
> > > Yours,
> > > Joel
> >
> > I think this assumption that is probably the most important one
> > to be questioned/investigated at this point in time.
> >
> > There is certainly some evidence to suggest that routing
> > based on topologically insensitive names is possible and
> > reasonably efficient. That concept has not permeated IETF
> > very much.
> >
> > The evidence, in my mind, is related to results in the
> > DHT/overlay community and also the compact routing work. The
> > overlay 'evidence'
> > however has always troubled me some, because it generally constructs
> > arbitrary graphs in a 'convenient' way whereas the compact routing
> > work does not. Also, these communities define the term
> > 'stretch' in different ways-- overlay/DHT people tend to define
> > it in terms of delay and CR people define it in terms of
> > hop count ratios. The work is cut out for us..
> >
> > as the coffee takes effect...
> > - K
> >
> > >
> > > At 08:43 PM 10/7/2005, Dmitri Krioukov wrote:
> > > >several people, including vint cerf at the last sigcomm,
> > > >talk about differentiating between node names (or IDs)
> > > >and node addresses having some topological sense. i'd
> > > >like to emphasize that, at least formally, this distinction
> > > >is very well understood, formalized, and researched. it
> > > >is directly related to what's called name-independent
> > > >routing (working with node "names") vs. name-dependent
> > > >routing (working with node "addresses").
> > > >
> > > >indeed, by definition (http://arxiv.org/abs/cs.NI/0508021),
> > > >name-dependent routing embeds some topological information
> > > >in node labels which thus cannot be arbitrary, while routing
> > > >that can work on the graphs with arbitrary node labels is
> > > >called name-independent. thus, networking terms like "node
> > > >name" or "node ID" essentially refers to the name-independent
> > > >case, while the term "node address" usually implies a
> > > >topologically informative node label, i.e., the name-dependent
> > > >case.
> > > >
> > > >even finer classification is considered in
> > http://arxiv.org/abs/cs.DC/990300
> > 9
> > > >which differentiates the name-dependent case into the two
> > > >subcases: node label set is 1...n (case \beta) or completely
> > > >arbitrary (case \gamma).
> > > >--
> > > >dima.
> > > >http://www.caida.org/~dima/
> > > >
> > > >
> > > >_______________________________________________
> > > >rr-fs mailing list
> > > >rr-fs@caida.org
> > > >http://rommie.caida.org/mailman/listinfo/rr-fs
> > >
> > > _______________________________________________
> > > rr-fs mailing list
> > > rr-fs@caida.org
> > > http://rommie.caida.org/mailman/listinfo/rr-fs
> >
--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com
|