Subject: Re: [rrg] Terminology, 2nd pass

From: [email-masked]
Date: Sun, 29 Mar 2009 18:39:23 EDT

Maybe this discussion about what is a locator (and what is it not) may  
benefit from reasoning what makes a locator poor, good, excellent,...
 
Heiner

---

From: Dow Street <[email-masked]>
Date: Sun, 29 Mar 2009 19:09:21 -0700

On Mar 29, 2009, at 3:39 PM, [email-masked] wrote:

> Maybe this discussion about what is a locator (and what is it not)  
> may benefit from reasoning what makes a locator poor, good,  
> excellent,...
>
> Heiner

Thinking about this some more...

Given a system that has a notion of geography or topology, we can  
assign names to different points within that geography or topology.   
So, as a starting point, it seems reasonable to define a locator as  
(1) a name for a point (or location) in a geography or topology.

Depending upon the nature of the geography or topology, it may be  
possible to devise a namespace (and set of semantics) for these names  
so that the name (value) itself (2) encodes information about the  
geographic or topological position of the point being named.

I think some people have been defining a "locator" as a name that  
meets condition (1).  Others seem to have been defining a "locator" as  
a name that meets condition (2), and still others seem to be thinking  
it must meet (1) and (2) (i.e. have location semantics and be "in use"  
in that context).

For example, I would argue that a MAC address meets condition (1) -  
i.e. it names a location in a topology - but it does not meet (2),  
because it does not encode in the name (value) itself any topological  
information.  Part of what makes this confusing is that different  
types of geographies or topologies lend themselves to varying degrees  
of location encoding (2) using known mathematical tricks.  For  
example, the Geographic Coordinate System (http://en.wikipedia.org/wiki/Geographic_coordinate_system 
) embeds the complete details about position in the location's name.   
Knowing the name, you know the position.  On the other end of the  
spectrum is a switched ethernet, where knowing the location name (MAC)  
tells you nothing about the relative topological position of the point  
being named by the MAC.  However, the MAC (in my mind) still serves as  
the name of a location.

IP routing usually falls somewhere between these two.  The proximity  
semantics of IP allow some relative positional information to be  
encoded in the name.  For this to be of benefit, though, the routing  
system must be (a) designed to take advantage of the proximity  
semantic (e.g. by passing around prefixes instead of individual  
addresses) and (b) the points in the geography must be named in a  
supporting manner (i.e. locations named with sets of addresses that  
allow for aggregation).  What is important here is that "if location  
information is only partly encoded in the name, a secondary system  
(e.g. routing) is needed to complete the mapping function".  I think  
this leaves us with a spectrum of cases, for example...

Geographic Coordinate System
- the position in the geography is fully encoded in the name of the  
location (coordinates)
- no supplemental "routing system" needed

Internet Routing
- location in the topology is partly encoded in the name of the  
location (IP address)
- routing system does *some* work.

Ethernet Switching
- location in the topology is not encoded in the name of the location  
(MAC address)
- routing (i.e. switching) system does "all" the work.

A key part of the RRG routing problem (if I understand correctly) is  
that it is hard to embed positional information in a location's name  
when the geography or topology of the system (graph) has Internet-like  
properties.  Grids are easy, trees are easy, but Internet-like  
topologies are not.  So what we do currently (again, if I understand  
correctly), is devise the semantics for the IP address namespace to  
make it efficient to embed position information for points on a tree,  
and then use routing as glue between this tree representation and the  
actual topology.  As such, if we are relying on aggregation as our  
scaling tool, the less tree-like the topology, the more routing state  
there will be (even in the *best* case where names are assigned in a  
maximally aggregatable manner.)

R,
Dow

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 29 Mar 2009 23:01:13 -0400

There are two different approaches to this.
We can define the behavior of the system, and the various names the 
routing system manipulates.
Or we can define the properties we want certain names to have, and then 
define a system that maintains those properties.

The properties that many of us have concluded (possibly wrongly, but it 
is one of the things some of us think is interesting) we want is the 
ability to have certain types of identificitaiton for certain objects 
which are location insensitive.  That is, the names do not change when 
the object moves in the graph.  This means that it does not change when 
you use different interfaces to reach it, or whatn different ISPs are 
used for communication.  The intention is that htis naming can stay 
fixed if the device itseslf moves.

That does not prevent the packet forwarding system from using that name 
for forwarding.  If one uses flat routing (classic IS-IS level 1 area, 
or Bridging, or ...) one can still make forwarding decisions based on 
that label.  If the entity that is identified mvoes (in any sense) then 
the routing information may have to change to reflect that.  But the 
label itself does not move.

One can conversely model different forwarding systems (and their 
associated routing information exchange systems) based on whether they 
use information from the labels or about the labels, or hybrids.  In 
fact, if we believed that the (currently theoretical, but mathematically 
interesting) compact routing work was deployable and able to cope with 
dynamics, we could in principle have an internet scale system that 
worked purely in terms of identifiers.
The point, as far as I am concerned, in defining the term is to be able 
to indicate certain properties of certain labeling that I think are 
useful.  The point is NOT to define the properties of the packet 
forwarding / routing system.  While I find the exercise of defining an 
alternative routing and forwarding system interesting, I do not see that 
as a good place to start the process.  (In part, this is because the 
last time we went down that road we could not find sufficient small 
scale incentives to make deployment work.  So I am tending to look at 
system behavior first, and routing behavior second.)

Yours,
Joel

Dow Street wrote:
> 
> On Mar 29, 2009, at 3:39 PM, [email-masked] 
> <mailto:[email-masked]> wrote:
> 
> Given a system that has a notion of geography or topology, we can assign 
> names to different points within that geography or topology.  So, as a 
> starting point, it seems reasonable to define a locator as (1) a name 
> for a point (or location) in a geography or topology. 
> 
> possible to devise a namespace (and set of semantics) for these names so 
> that the name (value) itself (2) encodes information about the 
> I think some people have been defining a "locator" as a name that meets 
> condition (1).  Others seem to have been defining a "locator" as a name 
> that meets condition (2), and still others seem to be thinking it must 
> meet (1) and (2) (i.e. have location semantics and be "in use" in that 
> context).    
> 
> For example, I would argue that a MAC address meets condition (1) - i.e. 
> it names a location in a topology - but it does not meet (2), because it 
> does not encode in the name (value) itself any topological information. 
>  Part of what makes this confusing is that different types of 
> geographies or topologies lend themselves to varying degrees of location 
> encoding (2) using known mathematical tricks.  For example, the 
> (http://en.wikipedia.org/wiki/Geographic_coordinate_system) embeds the 
> complete details about position in the location's name.  Knowing the 
> name, you know the position.  On the other end of the spectrum is a 
> switched ethernet, where knowing the location name (MAC) tells you 
> nothing about the relative topological position of the point being named 
> by the MAC.  However, the MAC (in my mind) still serves as the name of a 
> location.  
> 
> semantics of IP allow some relative positional information to be encoded 
> in the name.  For this to be of benefit, though, the routing system must 
> be (a) designed to take advantage of the proximity semantic (e.g. by 
> passing around prefixes instead of individual addresses) and (b) the 
> points in the geography must be named in a supporting manner (i.e. 
> locations named with sets of addresses that allow for aggregation). 
>  What is important here is that "if location information is only partly 
> encoded in the name, a secondary system (e.g. routing) is needed to 
> complete the mapping function".  I think this leaves us with a spectrum 
> of cases, for example...  
> 
> - location in the topology is partly encoded in the name of the location 
> (IP address)
> correctly), is devise the semantics for the IP address namespace to make 
> it efficient to embed position information for points on a tree, and 
> then use routing as glue between this tree representation and the actual 
> topology.  As such, if we are relying on aggregation as our scaling 
> tool, the less tree-like the topology, the more routing state there will 
> be (even in the *best* case where names are assigned in a maximally 
> aggregatable manner.)  
> 
> R,
> Dow
> 
>   
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> rrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/rrg

---

From: Scott Brim <[email-masked]>
Date: Mon, 30 Mar 2009 08:26:17 -0400

> for a point (or location) in a geography or topology. 

I like the recent development that a locator can refer to a whole
prefix.  I would like to retain that.  We used to say a locator was a
particular attachment point and we left prefixes kind of hanging out
there.

> meet (1) and (2) (i.e. have location semantics and be "in use" in that

I think it's both because of the point made in the last few messages
that the issue is usability.  Noel pointed out that MACs as administered
are not _usable_ as locators because of their structure.

> does not encode in the name (value) itself any topological information.

Aha ... A MAC names an interface but not an attachment point.  A MAC is
a property of the device, not the network.

> On the other end of the spectrum is a

A MAC is a property of the device, not the network.  Contrast it with an
attachment point name.

> complete the mapping function".  

Sounds good.

> I think this leaves us with a spectrum
> of cases, for example...  
> 

OK, this is useful.  It could be incorporated as an attribute of
"locator" (clearly an identifier, being topology-independent and being
able to change independently of topology changes, does not encode
anything about position).  Something like:

  A locator may encode some amount of topological position information
  in its value.

> be (even in the *best* case where names are assigned in a maximally

All true.  This is what we have arrived at based on experimentation but
also on history (the "Internet" was overwhelmingly hierarchical, with
ARPAnet at the core, until 1987).  What do you suggest?

Scott

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 30 Mar 2009 09:10:26 -0700

> are not _usable_ as locators because of their structure.

If MACs are used to find a location of an end-system, then they are  
locators. When a MAC moves from one location to another, the layer-2  
network readjusts to forward packets *in a new direction*. If that is  
not a locator, then what is. Just because the value of the 48-bit  
address doesn't change doesn't mean it's not a locator.

We do find cases where IP addresses move away from their subnet and  
attach to another cable which is assigned another subnet. In that  
case, the IP address value of the host doesn't change and with a more  
specific route, there is a new location for that IP address.

Both these cases are the same. Both these cases use the address as a  
locator.

 From a network perspective, if a switching node makes a forwarding  
decision based on an address in a packet header, then that address is  
a locator.

>> i.e.

No, a MAC can name a system. MACs are used all the time as serial  
numbers for systems. In these cases, sometimes they are used to reach  
the system and other cases they are not.

In the case a MAC is used as a serial number purely, it is simply an ID.

> A MAC is a property of the device, not the network.  Contrast it  

Disagree.

Dino

---

From: Scott Brim <[email-masked]>
Date: Mon, 30 Mar 2009 12:49:31 -0400

Excerpts from Dino Farinacci on Mon, Mar 30, 2009 09:10:26AM -0700:
>> I think it's both because of the point made in the last few
>> messages that the issue is usability.  Noel pointed out that MACs
>> as  administered are not _usable_ as locators because of their
>> structure.
>
> locators. 
> When a MAC moves from one location to another, the layer-2  network
> readjusts to forward packets *in a new direction*. If that is  not a
> locator, then what is. Just because the value of the 48-bit  address
> doesn't change doesn't mean it's not a locator.

As long as calling something a locator doesn't exclude it from being
an identifier, that's okay ... but what good does it do you?  What
good does that definition of a locator do if it's not exclusive?  The
important thing you just said is not about the thing (locator,
identifier) itself, but about what a forwading function things of it.
What your sentence is really about is the first half: MACs are used to
find a location of an end system (i.e. determine a next hop).  MACs
are also used to identify end systems regardless of where they are in
the topology.  

> attach to another cable which is assigned another subnet. In that case, 
> the IP address value of the host doesn't change and with a more specific 
> route, there is a new location for that IP address.

See other messages about that.  Locators don't always, necessarily,
change when the attachment point changes ... but unlike with
identifiers, a function can't assume that locators will NOT change.
They are better off assuming they will change.  On the other hand one
of the inherent properties of identifiers is that any changing they do
is completely decoupled from any attachment point change.  They don't
have to change ever due to topology changes, and they can change
whenever they want even if there are no topology changes.

See?  That's an essential difference that makes the definitions
worthwhile having.  Otherwise why bother having them.

Scott

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 30 Mar 2009 10:09:57 -0700

But you don't want to have irrelevant definitions.

Dino

On Mar 30, 2009, at 9:49 AM, Scott Brim wrote:

>> case,

---

From: Scott Brim <[email-masked]>
Date: Mon, 30 Mar 2009 13:13:34 -0400

> But you don't want to have irrelevant definitions.

That's what I was saying.  "anything used by forwarding is a locator"
isn't very useful, because forwarding can use anything it wants.  That
skips over useful distinctions, like whether something is a persistent
name for an endpoint regardless of where it is attached..

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 30 Mar 2009 10:25:19 -0700

There are multiple values for "vague".  ;-)

Dino

P.S. I'm out of this thread for now.

---

From: Dow Street <[email-masked]>
Date: Mon, 30 Mar 2009 10:40:31 -0700

I think Scott and I are mostly on the same page.  One lingering  
distinction is whether something like a MAC address should be called a  
"locator", or whether (perhaps independently) a MAC can be considered  
to "name a location" even if we don't call it a "locator".

Intuitively, a MAC seems to me like it names a location on an  
ethernet, even though it is a "flat" name.  I think this is a similar  
property to that of an IP address once you get to the "final subnet"  
on the way to a destination.  There the IP address is essentially a  
flat name as well (i.e., all the topological information in the name  
value has been consumed).  This basically maps to the host part of the  
IP address, but gets a little complex to define in general because the  
length of the mask is variable and locally configured.

Returning to definitions, I am happy to say that these types of names  
indeed name locations, but because they do not encode any topological  
information in the name value, we not define them as "locators".   
Pragmatically, this definition of "locator" should also allow for co- 
existance with the opinion that such flat names do not name location,  
only interface.

In other words, not all names of locations are also locators.  More  
generally, it seems we are converging on a common understanding - that  
is good.

R,
Dow

---

From: William Herrin <[email-masked]>
Date: Mon, 30 Mar 2009 16:47:07 -0400

We can (and IMHO should) define the Identifier independently from the locator.

An [identifier] is a "handle" that our software, at whatever layer of
the stack, uses to associate the components of a particular
communication with the communication as a whole. Any handle which
provides this association function is an [identifier].

We want the [identifier] to have two specific properties:

a. The [identifier] is unique within the scope of the function we use it for.

If it isn't unique, we can't guarantee that the components will be
associated with the communication to which they belong.

b. The [identifier] persists unchanged for the duration of its useful function.

If it fails to persist, communication will be disrupted, terminated or
induced to malfunction.

Here's what we can't say about the generic, abstract [identifier]:

i. Scope. It could be global (dns host name). It could be just within
the client and server portions of a specific application (web session
cookie). It could be anywhere in between as needed to serve its
particular function.

ii. Lifetime. It may be quasi-permanent (http://www.cnn.com/). It may
only last for two packets (the transport ID for a UDP DNS query and
its response). It may be anywhere in between as needed to serve its
particular function.

iii. Protocol layer. It might be layer 7 (web session cookie). It
might be layer 2 (the MAC address incorporated in the IPv6 address
incorporated in the TCP transport ID). It might be anywhere in between
as needed to serve its particular function.

Where we run into problems is:

1. Some "thing" serving as part of the [identifier] also serves
another function in which uniqueness adds undesirable complexity.

2. Some "thing" serving as part of the [identifier] also serves
another function in which persistence adds undesirable complexity.

Routing is an example of both problems. We have the extra complexity
of finding the prefix in which the unique IP address belongs and we
have the extra complexity of computing hundreds of thousands of new
paths to the persistent IP addresses every time the system link state
changes.

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Scott Brim <[email-masked]>
Date: Mon, 30 Mar 2009 17:09:58 -0400

> provides this association function is an [identifier].

I'm having to fill in some blanks but that sounds like 'session
control', which is one use, but doesn't cover e.g. most uses of domain
names.  What do you think of this list of relevant identifier uses?

  - Discovery
  - Initial connection 
  - Authentication
  - Session control
  - Referral

> associated with the communication to which they belong.

Sure :-)

> If it fails to persist, communication will be disrupted, terminated or

If I have a session I'm controlling and I periodically change keys and
identifiers, the identifier has changed (or been replaced), but the
change has been managed.  I'm not sure how to fit that into your
statement.

> cookie). It could be anywhere in between as needed to serve its

Right.  It could be a transport port number and only have meaning
within the transport session.

> as needed to serve its particular function.

Sure

> another function in which persistence adds undesirable complexity.

I guess that last one is a re-statement of the classic
locator/identifier separation problem (using addresses for
identification).  Can you give an example of the first one?

> paths to the persistent IP addresses every time the system link
> state changes.

I'll understand it better when you reply.

Scott

---

From: William Herrin <[email-masked]>
Date: Mon, 30 Mar 2009 18:04:58 -0400

On Mon, Mar 30, 2009 at 5:09 PM, Scott Brim <[email-masked]> wrote:
> names.

Hi Scott,

I'm trying to use "communication" here in a broad, non-technical
sense. Reading my newspaper is a "communication." Its identified by
the title "Washington Post" and located near the checkout counter at
my grocery store. My communication with the Washington Post persists
over the many years that I've read it. The individual editions and
stories are components of that communication which are associated
together under the identifier, "Washington Post."

"Communication" isn't exactly the right word. The general idea is that
there is some Something involved in moving information and the
components of that Something are uniquely and persistently associated
with the Something via the Identifier.

It's like you have a database with many pairs of tables. In the
objects table for each pair you have a unique primary key. In the
components table you have a foreign key back to the primary key of
objects table. That primary key is the identifier for the object and
its components. Each pair of tables corresponds to a different kind of
identifier with a different scope and lifetime.

> change has been managed.  I'm not sure how to fit that into your

Show me an example of an identifier change that doesn't have ambiguous
corner cases.

Shim6 is an interesting guide here. Consider this ambiguous corner case:

I am 1.2.3.4
Request TCP connection A to 6.7.8.9
6.7.8.9 changes identity to 9.8.7.6
Request TCP connection B to 6.7.8.9

Should connection B be established to 6.7.8.9 or to 9.8.7.6? Guess
wrong for that particular application and you get a malfunction.

> Can you give an example?

Sure.

Example #1: We tag the packet with a AS# and an IP address. The AS#
persistently identifies the network in which the the IP address
resides. All IP addresses at that AS are assigned the same AS#; it
isn't unique. Each AS announces it's AS# to the world.

At each router, we perform a hash table lookup to find the next hop
for the destination AS#.

Example #2: We tag the packet with only an IP address. Each AS
announces the address prefixes it serves to the world.

At each router we perform either a TCAM lookup or a radix-tree lookup
to associate the IP address to the prefix to which it belongs and then
to the next hop via which that prefix is found.

Which was more complex and more expensive? The hash table lookup? Or
the radix tree/TCAM lookup?

Regards,
Bill Herrin