Subject: [RRG] Idea for shooting down

From: Brian E Carpenter <[email-masked]>
Date: Tue, 20 Nov 2007 10:59:01 +1300

For a few weeks I've been mulling over what is probably
an unrealistic idea that amounts to adding hierarchy
to locator mapping. It's really quite hard to explain in
pure ASCII and I missed the deadline anyway, but here
it is for comments:

http://www.cs.auckland.ac.nz/~brian/DFZng.pdf

    Brian

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Robin Whittle <[email-masked]>
Date: Tue, 20 Nov 2007 16:08:39 +1100

Hi Brian,

With your proposal:

I get the impression that the result would be the Internet being
much less meshed than it is at present.  This would have negative
impacts including:

1 - Less robustness in the event of link and router failure.

2 - Often longer path lengths (AKA "stretch") as a packet has to
    get out of one of the many Level 1 domains (or the one Level 0
    domain) up to some Level 2 domain in order to get to another
    Level 1 (or the Level 0) before it could be delivered.  This is
    true even if the ISP border routers connecting to the sites with
    the sending and receiving hosts are physically close, but happen
    to be of ISPs which are in separate domains.  (I assume an ISP
    can only be in one domain, but perhaps I am wrong.)

3 - Therefore, further dimensions of "Balkanisation" of the
    Net, where actual packet delivery times and reliability
    levels depend not just on physical (partly geographic)
    topology, link capacities and traffic levels but also on
    which domain each host is in and how far the packet has to
    travel to go up and then down a level to the destination
    domain.

4 - Therefore, a lot of fuss as ISPs try to decide which domain
    to be in.

5 - Also, perhaps, more pressure on "sites" (as I think you
    nicely describe them) to multihome to various ISPs in
    different domains.  However, that only helps with the
    path length if the "site" is smart enough to send outgoing
    packets to the optimal ISP's router.  This wouldn't help
    with optimising which ISP and region an incoming packet
    arrives through when it is sent by a non-multihomed site
    or a multihomed site without the smarts to choose the
    best outgoing router.

Also, I don't understand how your proposal would help with the
central problem we are trying to solve - of a multihomed site's
router requiring a separate route for every prefix advertised by any
site anywhere at all.

The fact that the destination site is in a different domain doesn't
alter the fact that the multihomed site's router needs a separate
route for that slice of address space, because the router still
needs to decide which of the two or more upstream ISP routers to
forward the packet to.

 - Robin

---

From: [email-masked]
Date: Tue, 20 Nov 2007 06:17:10 EST

I have well hi-lighted the advantages of my NIRA model before (no  
scalability problem, no churn,...)  In response to the current discussions,  I should 
add: No changes in the hosts, no requirement that IPv4 addresses have  to be  
worldwide unique forever (i.e.IPv4 address depletion is no issue  with this 
model).
 
By looking at Brian's concept: It is, by all its new details, just another  
form of hierarchy like Nimrod or PNNI, with a node aggregation which is a)  
cumbersome in doing and b) underperforming wrt its result.  In some  older email 
I expressed my suspicion that the term "stretch" has been invented  just to  
discriminate hierarchy. Well, if you  only accept  hierarchical models like 
Nimrod, PNNI, ISLAY, or Brian's new proposal than this  criticism is appropriate.
 
Multihoming:
If I can route towards the destination (while ignoring any prefixes, but  
guided by geo.coordinates) as close as I want by design, than I can afford  (!!) 
to treat sites (as defined by Brian) being nodes in my topology of lowest  
level s, whose adjacent links have such high weights that the site wouldn't be  
used for transit. (with the current BGP design no one can afford to extend the  
routing tables by let's say a factor 100 or 1000). But if that site is the  
destination node, IP forwarding may be done via any  of the site's adjacent  
links (to different ISPs) - i.e. multihoming is just multipath routing.
 
Postal mail versus email:
By looking at not so normal situation one may recognize whether a  concept is 
sane or insane:
If I send a letter, let's say from Germany to Sausolito, but the receiver  
has moved to a different place, it is perfectly ok  that the last postal  office 
would realize the receiver's relocation and would send the letter  back.
It would be insane to disseminate that someone has changed his address to  
all postal offices in the world, just for the effect that an incorrect  
destination address could be detected by the ingress postal office.
I think the existing postal concept is sane, and of course, with the NIRA  
concept the email would also be sent to (at least California) and then returned. 
 I think it would be ok if the email is returned with not deliverable. It 
would  also be great if the first node who returns the email could also return 
the new  address, if known,  respectively any other node on the way back  -  
just as an assist of the DNS.
 
Imho, it could be so simple. Sometimes I compare my situation with Platon's  
cove story. Because I am not so good in BGP I am bad in interpreting the 
shadows  on the wall, hence my model is ignored.
 
Heiner

In einer eMail vom 20.11.2007 06:11:51 Westeuropäische Normalzeit schreibt  
[email-masked]:

With  your proposal:

- Robin

---

From: Brian Carpenter <[email-masked]>
Date: Wed, 21 Nov 2007 11:15:02 +1300

[Resend due to
This is an automatically generated Delivery Status Notification

Delivery to the following recipient failed permanently:

      [email-masked]

Technical details of permanent failure:
PERM_FAILURE: SMTP Error (state 13): 550 deferred because 209.85.198.185 is in  a black list at qil.mail-abuse.com]

Heiner,

On 2007-11-21 00:17, [email-masked] wrote:
...
> shadows  on the wall, hence my model is ignored.

Please point us to a document describing your proposal. The animation on
your site doesn't explain NIRA in a way that I can understand.

    Brian

---

From: Brian Carpenter <[email-masked]>
Date: Wed, 21 Nov 2007 11:16:03 +1300

[Resend due to

      [email-masked]

On 2007-11-20 18:08, Robin Whittle wrote:
> much less meshed than it is at present. 

Not exactly. The individual regions can be as meshed as one
wants, and they are *not* geographical regions - in fact they
are more likely to evolve as conglomerates of ISPs.

> This would have negative

As noted in the draft, there can be multiple links between
layers - as many as desired, in fact.

>     can only be in one domain, but perhaps I am wrong.)

Definitely more stretch. But that may be inevitable as we grow towards
ten billion hosts.
>     travel to go up and then down a level to the destination

I don't see why that is Balkanisation, which implies walled gardens
to me. I would counter this and the previous two arguments with the
assertion that an organised hierarchy of finite meshes is intrinsically
easier to understand and debug than a single unbounded mesh.
> 4 - Therefore, a lot of fuss as ISPs try to decide which domain

I don't see this as being that much different from today's fuss
as ISPs decide who to peer with.

>     or a multihomed site without the smarts to choose the

I don't see this as any different from a site's point of view than
today. The sites will perceive ISPs, not regions. They have all those
issues today.

> needs to decide which of the two or more upstream ISP routers to

As I said, this idea is *orthogonal* to LISP, Ivip, etc. We
definitely  need a robust solution for exit router selection
that doesn't require full routes. I haven't had time to analyse
draft-baker-6man-multiprefix-default-route-00 yet, but we need
something with that degree of simplicity and robustness.

    Brian

---

From: Tony Li <[email-masked]>
Date: Tue, 20 Nov 2007 14:31:53 -0800

On Nov 20, 2007, at 2:15 PM, Brian Carpenter wrote:

>> Imho, it could be so simple. Sometimes I compare my situation with  
>> Platon's  cove story. Because I am not so good in BGP I am bad in  
>> interpreting the shadows  on the wall, hence my model is ignored.
>

To be fair, Heiner did indeed give a conceptual overview to the  
mailing list.  If I understood it correctly, it involved geographic  
routing at the top levels, based on longitude/latitude, with prefix  
routing locally.  What I found unclear was how hop-by-hop forwarding  
worked while packet addressing continued to be strictly address  
based.  I await further enlightenment.

Tony

---

From: [email-masked]
Date: Tue, 20 Nov 2007 18:10:09 EST

In einer eMail vom 20.11.2007 23:32:31 Westeuropäische Normalzeit schreibt  
[email-masked] (mailto:[email-masked]) :
Tony, Brian,
Each node has to see a network topology where this node is surrounded by  
nodes and links, whereby the more remote the looser the links, whereas the nodes  
are all individual routers (even those at highest hierarchical level !!! ). 
The  length of each link between any two nodes is precisely determined due to 
the  routing protocol which builds this hierarchical topology. I expect that 
the  length of some hierarchical link is according to the number of physical 
link  hops in between the two adjacent nodes (not the geographical distance in 
miles  or km, which could be done as well, e.g. in order to build a disk for 
worldwide  car navigation ). What is needed: for each viewed node its 
geographical  coordinates (proper degrees, not the minutes or seconds) and the 
destination's  geographical coordinates, likewise, which would take 3 parameter octets 
in the  IPv4-header.  DNS lookup should provide this info together with the 
IPv4  address. I hope, the ingress host can put the geo-info into the 
IPv4-header, or  at least some proxy who is close to the source user and has cached what 
he has  learned from a passing DNS query.
 
But then the real (strict) next link determination can be done even if the  
destination node is not on the radar screen :-) but just some other node with  
geo-data closest to the destination's geo-data.
So routing, fairly as close as we want by design, can be done without any  
reachability info evaluation.
It could be done such close that the last few hops can be done just like in  
OSPF, where each passed node forwards based on the reachability info of the  
egress node, or, if you want, by using classic BGP, however with a small  
routing table with geographical square degree- wide unique address prefix.
 
Heiner

Tony

---

From: "Fleischman, Eric" <[email-masked]>
Date: Tue, 20 Nov 2007 15:33:05 -0800

I don't mean to imply any push-back against this approach, since I haven't yet adequately read and studied it. However, when we talk about Internet-wide scaling on schemes such as this, I would think that a desirable attribute would be to know the local links well, but to know much less about remote links (e.g., which network interface to forward packets on). This could be accomplished by a variety of technologies (e.g., Hazy Sided Link State; Landmark routing; Fisheye Hierarchical Routing; etc.). However, the affects that I am naively suspecting that would tend towards greater scalability would be to have results that resembled link state (Dykstra) computations for local links (e.g., whatever grouping is decided to be "local"; whether regional, country, continent, or some other definition of proximity) and Bellman-Ford-like results for remote (i.e., non-"local") links.

  _____  

From: [email-masked] [mailto:[email-masked]] 
Sent: Tuesday, November 20, 2007 3:10 PM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [RRG] Idea for shooting down

In einer eMail vom 20.11.2007 23:32:31 Westeuropäische Normalzeit schreibt [email-masked]:
Tony, Brian,
Each node has to see a network topology where this node is surrounded by nodes and links, whereby the more remote the looser the links, whereas the nodes are all individual routers (even those at highest hierarchical level !!! ). The length of each link between any two nodes is precisely determined due to the routing protocol which builds this hierarchical topology. I expect that the length of some hierarchical link is according to the number of physical link hops in between the two adjacent nodes (not the geographical distance in miles or km, which could be done as well, e.g. in order to build a disk for worldwide car navigation ). What is needed: for each viewed node its geographical coordinates (proper degrees, not the minutes or seconds) and the destination's geographical coordinates, likewise, which would take 3 parameter octets in the IPv4-header.  DNS lookup should provide this info together with the IPv4 address. I hope, the ingress host can put the geo-info into the IPv4-header, or at least some proxy who is close to the source user and has cached what he has learned from a passing DNS query.
 
But then the real (strict) next link determination can be done even if the destination node is not on the radar screen :-) but just some other node with geo-data closest to the destination's geo-data.
So routing, fairly as close as we want by design, can be done without any reachability info evaluation.
It could be done such close that the last few hops can be done just like in OSPF, where each passed node forwards based on the reachability info of the egress node, or, if you want, by using classic BGP, however with a small routing table with geographical square degree- wide unique address prefix.
 
Heiner

Tony

---

From: Tony Li <[email-masked]>
Date: Tue, 20 Nov 2007 15:41:57 -0800

On Nov 20, 2007, at 3:10 PM, [email-masked] wrote:

> Each node has to see a network topology where this node is  
> surrounded by nodes and links, whereby the more remote the looser  
> the links, whereas the nodes are all individual routers (even those  
> at highest hierarchical level !!! ). The length of each link  
> between any two nodes is precisely determined due to the routing  
> protocol which builds this hierarchical topology. I expect that the  
> length of some hierarchical link is according to the number of  
> physical link hops in between the two adjacent nodes (not the  
> geographical distance in miles or km, which could be done as well,  
> e.g. in order to build a disk for worldwide car navigation ). What  
> is needed: for each viewed node its geographical coordinates  
> (proper degrees, not the minutes or seconds) and the destination's  
> geographical coordinates, likewise, which would take 3 parameter  
> octets in the IPv4-header.  DNS lookup should provide this info  
> together with the IPv4 address. I hope, the ingress host can put  
> the geo-info into the IPv4-header, or at least some proxy who is  
> close to the source user and has cached what he has learned from a  
> passing DNS query.

So would it be fair to characterize this as a locator/ID split, where  
both locator and ID are present in the packet header, and locators  
are geographically assigned?  Routing within the location is doing by  
normal hierarchical routing.

As always with geographic abstractions, how do you deal with the case  
of two sites within the same geographic granularity that have no  
interconnectivity except outside of their locale?

Tony

---

From: Robin Whittle <[email-masked]>
Date: Wed, 21 Nov 2007 16:53:04 +1100

Hi Brian,

I had forgotten that your proposal is intended to be orthogonal to
ITR-ETR schemes such as LISP, eFIT-APT, Ivip or TRRP.  I understand
that "orthogonal" in this context means something like "operate
independently of (using different "dimensions"), to achieve similar
and/or other objectives".

Assuming there is an ITR-ETR scheme which successfully limits the
number of prefixes in the current single DFZ (to some acceptable
number, the same, somewhat higher or lower than the current ~240k),
what benefits would your proposal provide?

> are more likely to evolve as conglomerates of ISPs.

I got the impression from the text and diagrams that no ISP in a
Level 1 domain could link to any other ISP in any other Level 1
domain - that the packets would have to flow via a Level 2 domain,
in the simplest instance.

> layers - as many as desired, in fact.

There could be, but since there are now multiple domains, with
restrictions on what each ISP in each domain can link to (as best I
understand it) then this would surely reduce the opportunities for
meshing compared to the current situation where there is only one
"domain" and any ISP can link to any other ISP.

> Definitely more stretch. But that may be inevitable as we grow towards

ITR-ETR schemes with well placed ITRs and ETRs don't necessarily
involve longer path lengths.  In many or most cases, once the system
is widely adopted, I think there would be no extra distance or
number of routers for most packets.

Your system, as I understand it, involves restrictions on which ISP
can connect with other ISPs, so the total system is going to be more
hierarchical, branched and compartmentalised than would be the case
with a single domain, as exists today.

> easier to understand and debug than a single unbounded mesh.

I didn't mean "walled gardens" - just more like your Step 4 diagram,
in which, as I understand it, an ISP in the bottom right Level 1
domain can't connect - or finds it more complex and therefore
expensive to connect - to an ISP in the bottom middle Level 1 domain.

I doubt that conceptually and practically more complex arrangements
lead to greater ease of understanding and debugging.  The ITR-ETR
schemes all introduce a roughly similar new set of architectural
arrangements in terms of address space, ITRs, ETRs etc. which will
make the total Internet harder to understand and debug.  These
schemes are only being contemplated because we perceive a
prohibitive scaling limit in the DFZ if we don't implement such a
scheme and the number of end-user networks (and ISPs too) continues
to grow as we expect.  These schemes are being contemplated just to
keep the Internet running with its current hosts and most of the
current BGP routers untouched - not because the result will be
simpler or easier to debug.

> as ISPs decide who to peer with.

Can an ISP be in two domains at the same time?  Can an ISP be in two
or more Level 1 domains?  Two or more domains of different levels?
In the Level 0 (existing DFZ) and in some other domain(s)?

If the answer to any of these questions is negative, then I think
your system imposes more restrictions on how ISPs can connect to
other ISPs, which I think would lead to more fuss.  Likewise if the
answers are all "yes - but only with extra costs or complexity".

> today. The sites will perceive ISPs, not regions. They have all those

My first sentence refers to my perception that each site will want
to connect to several ISPs in several different domains, in order to
maximise diversity for multihoming robustness.  The second and third
sentences refers to my understanding that the overall path lengths
are going to be longer with your scheme, since ISPs in general are
less meshed - although theoretically a multihomed site could be
smart enough to know which of the upstream ISPs was closest to the
destination of each outgoing packet, and so could to some extent
reduce the general path-lengthening effect by forwarding the packet
to the optimal outgoing link.

 - Robin

---

From: [email-masked]
Date: Wed, 21 Nov 2007 04:42:01 EST

In einer eMail vom 21.11.2007 00:43:31 Westeuropäische Normalzeit schreibt  
[email-masked]:

So would it be fair to characterize this as a locator/ID split, where  both 
locator and ID are present in the packet header, and locators are  
geographically assigned?  

You may or may not see it as a different type of locator/ID  split. It is 
first of all a scalable way for routing.
Wrt. ID: In the years 2013/2014 we might be glad to continue with IPv4  
because it would provide enough addresses which are unique within one  geo-patch. 

Routing within the location is doing by normal hierarchical  routing.

Let's say by traditional reachability-info-based determination of the  egress 
node.

As always with geographic abstractions, how do you deal with the case of  two 
sites within the same geographic granularity that have no  interconnectivity 
except outside of their locale?

Partitioning is always a troublemaker :-). One way to deal with is to  cheat: 
If I remember correctly, then not all islands of the Hawaii island group  are 
in the same time zone, but for practical reason they have all
Honolulu time.
But of course, this problem should be dealt with by the protocol: We may do  
something which allows us to detect e.g. that Alaska (which is truly the case) 
 has a partitioned road system, e.g. by recognizing that all its 
representative  nodes in the hierarchically next upper level (country map) are more than 
those  that the current Anchorage node can discern on its state map.Yes, it may 
involve  a crankback detour. 
This problem would also show up in case of  partitioning due to some  link 
failures. I am much in favor that any viewed topology is the result of a  
routing protocol and not of any configurational data.
Configurational, IANA-based info should only guide the way how the  hierarchy 
evolves, i.e. which lower geo-patches should be combined to the next  upper 
geo-patch.
Political borders must not have any influence ! However  IANA may optimize 
the  geo-patches,e.g. as to get larger geo-patches  on the oceans than on soil.
 
But there may be further ideas how to deal with partitioned geo-patches  
(have a number for each part ?!)
Note: Because the hierarchical network view is the result of a routing  
protocol the partion may also hit any larger geo-patch at any upper level  
(partitioning of a "country" needs to be handled, likewise.) 
 
Heiner

---

From: [email-masked]
Date: Wed, 21 Nov 2007 11:59:25 EST

In einer eMail vom 21.11.2007 00:34:43 Westeuropäische Normalzeit schreibt  
[email-masked]:

However, the affects  that I am naively suspecting that would tend towards 
greater scalability would  be to have results that resembled link state 
(Dykstra) computations for local  links (e.g., whatever grouping is decided to be 
"local"; whether regional,  country, continent, or some other definition of 
proximity) and  Bellman-Ford-like results for remote (i.e., non-"local")  links.

Certainly, I completely share your opinion. Dijkstra works also in a  network 
wich contains both strict and loose (hierarchical) links.
 
Heiner

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 21 Nov 2007 23:52:26 +0100

On 21 nov 2007, at 0:33, Fleischman, Eric wrote:

> results that resembled link state (Dykstra) computations for local  
> links (e.g., whatever grouping is decided to be "local"; whether  
> regional, country, continent, or some other definition of proximity)  
> and Bellman-Ford-like results for remote (i.e., non-"local") links.

Note that Dijkstra and Bellman-Ford are two algorithms that provide  
the exact same solution to the exact same problem (finding the  
shortest path between network nodes), they only differ in their  
implementation constraints: Dijkstra pretty much needs to have all  
information for the entire network available in one place before the  
algorithm can be run, Bellman-Ford is able to reach the same result by  
distributing the work over multiple network nodes, the tradeoff being  
that you need iterate the computation and distribution of results as  
many times as there are nodes in the worst case.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 22 Nov 2007 13:13:24 +0100

> http://www.cs.auckland.ac.nz/~brian/DFZng.pdf

I don't understand how this works... Would ISPs at each level  
aggregate the address prefixes used at the level below, or would  
addressing be completely separate from the hierarchy so some kind of  
mapping/encapsulation would need to happen?

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 23 Nov 2007 09:59:59 +1300

On 2007-11-23 01:13, Iljitsch van Beijnum wrote:
> I don't understand how this works... Would ISPs at each level aggregate 
> the address prefixes used at the level below, or would addressing be 
> completely separate from the hierarchy so some kind of 

The second case. There would not only be a separate instantiation of
BGP4 in each region, but also a separate instantiation of (e.g.)
LISP-ALT. The idea is to recurse the whole model (EGP and locator-locator
mapping). ((Er, LISP EIDs are a special case of locator as far as
I'm concerned.))

I realise it's badly explained, but it seems quite hard to explain
clearly. Since I won't be in Vancouver, I will try to come up with
a better description and more diagrams at some point.

    Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 23 Nov 2007 10:22:14 +1300

> what benefits would your proposal provide?

None. But historically, routing swamps have a habit of emerging
spontaneously. This is an idea of how to take the sting out of that.

> in the simplest instance.

Correct. But remember it is a virtual topology; it doesn't need
to add more than one hop to the real topology, if such a connection
is needed. I do assume that ISPs which happen to exchange a lot
of traffic will end up in the same region - very likely the regions
would emerge in existing economic blocs, with the primary driver being
economic, rather than geographic or topological, nearness.

> "domain" and any ISP can link to any other ISP.

Yes. But that may simply be the price of scalability.

> number of routers for most packets.

Well, you don't know that a priori. If we use something like GRE
you actually have no control at the ITR-ETR level over how many
actual routing hops are involved in the GRE tunnel.

> simpler or easier to debug.

Which is worrying in itself.

I would maintain that a hierarchy is conceptually and practically
simpler than an ever-growing mesh. There's a systems engineering
tradeoff here.

> In the Level 0 (existing DFZ) and in some other domain(s)?

I think an ISP would have to operate two ASes to be in two domains
at the same time. I need to think a bit more about shortcut routes
in such a case (i.e. violating the separation of regions). It seems
likely that if a packet shows up in the "wrong" place, there's no
reason it can't be routed further through the system (but some
thought is needed about spoofing and loop-prevention).

> maximise diversity for multihoming robustness.  

If I'm right that regions would emerge in economic blocs, this would
really only arise for the truly international companies that connect
their company networks to the Internet in many different geographic
regions today; the IBMs of this world. These are all sophisticated
BGP4 users already - the worst case, I think, is that they would have to
operate multiple ASes (as suggested above for cross-connected ISPs).

> The second and third

Which the internationals already do.

     Brian

---

From: Peter Sherbin <[email-masked]>
Date: Thu, 22 Nov 2007 17:59:20 -0800 (PST)

A level s assumes 10^7 to 10^8 prefixes. If a household or a person is looked at as
a non-transit site then should we expect about 3*10^9 prefixes at the s level?

Is there an empirical evidence that the ratio is always about 1:10 for Ps+x ->
Ps+x+1?

How much effort is required for pro bono formation of the initial Level 2, Region1?
What is the minimum number and the tier of ISPs that need to be involved?

Thanks,

Peter

> http://www.cs.auckland.ac.nz/~brian/DFZng.pdf

      ____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 23 Nov 2007 16:38:16 +1300

> a non-transit site then should we expect about 3*10^9 prefixes at the s level?

No, I don't see SOHO networks appearing at this level; it will be local ISPs
that we see as WAN prefixes. (OK, there is a geek minority that may want their
SOHO network multihomed, but surely not enough to matter.)

So I'm thinking of a network with at least 10^10 hosts, but three orders of
magnitude fewer WAN prefixes at level s.

> Is there an empirical evidence that the ratio is always about 1:10 for Ps+x ->

No. It's a design choice, if you like.

> What is the minimum number and the tier of ISPs that need to be involved?

I think it could crystallize around quite a small number of ISPs. The number who
could sit together in the bar at some *NOG meeting, for example. If the model
works at all, it has to work that way. Big bangs don't work.

     Brian

---

From: Robin Whittle <[email-masked]>
Date: Fri, 23 Nov 2007 15:32:11 +1100

Hi Brian,

A short version of this message is:

  I think your scheme is not needed - a single BGP system and a
  single ITR-ETR system should do the trick.

You wrote:

> There would not only be a separate instantiation of
> LISP-ALT.

This is very ambitious.

I don't see how an ITR-ETR scheme could be made to work in separate
sections of the Net like this.  If there is one address space for
the whole Internet, there needs to be one ITR-ETR scheme, as far as
I know.

> spontaneously. This is an idea of how to take the sting out of that.

By creating a global multilevel system (AKA a potential swamp, not
just in horizontal dimensions but also vertically) of smaller
individually routing nascent swamps, each of which is kept small
enough that their swampfulness remains within acceptable bounds!

> is needed. 

I don't understand how no more than one hop is added, since it could
take multiple hops to get out of an ISP in a Level 1 domain, up to
an ISP in a higher level domain, and then down to another ISP in
another Level 1 domain.

> I do assume that ISPs which happen to exchange a lot

OK - this lack of meshiness and increased compartmentalisation seems
like a bad idea to me.

> Yes. But that may simply be the price of scalability.

I don't think we need a scheme such as this.  An ITR-ETR scheme can
handle huge numbers of prefixes, whilst keeping the current, single,
BGP system working much as it does today.

> Well, you don't know that a priori. 

In general, for the current ITR-ETR proposals, I think we do know this.

If an ITR is on the path the packet would ordinarily travel on
(without the ITR-ETR scheme) and so is the ETR, then it is
reasonable to assume the tunnel will follow the same path - so there
are no extra hops, stretch etc.

This will be the typical case for most traffic in the currently
discussed schemes - with the reasonable assumption that the ETR is
on whatever would otherwise be the path.

If the ITRs are full database, all traffic will follow the same path
at it would have without the ITR-ETR scheme.

With only a caching ITR on the path, a few initial packets would
have to travel to a full database ITR.  With Ivip or eFIT-APT, that
is likely to be a local ITR or Default Mapper, which is probably on
the path anyway.  Otherwise, the first packets may have a longer
path to take.  LISP-EMACS involves probably much longer paths for
initial packets, since it is a global system - although it is
intended that one copy of the initial packet winds up at the ETR,
which is where an ITR would send it anyway if it had the mapping
information.

Ivip or any other scheme which supports non-upgraded networks with
"anycast ITRs in the core" may involve sub-optimal path lengths when
all the packets must go to the nearest full database ITR outside the
originating network, which is possibly somewhat (or maybe a long
way) off the shortest path.

But your multilevel system seems to involve frequent deviations to
routers in a higher level just to get the packet down to the same
level, in another domain, even if the destination is physically
close to the source.

> If we use something like GRE

Ivip does its own tunneling in a very straightforward way - IP in IP
- without involving any other protocols.  The inner packet is the
original traffic packet.  The outer destination address is that of
the ETR.  The outer source address is that of the sending host.

>> with a single domain, as exists today.

You responded to questions about ISP connectivity later.

> Which is worrying in itself.

Here is a list of possible architectures, ordered best to worst in
terms of ease of debugging:

1 - Current BGP system.

2 - Current BGP system plus a Ivip or some similarly effective
    ITR-ETR scheme.

...

? - Current BGP system without an ITR-ETR scheme, some time in the
    future, when the number of prefixes and routers is so great that
    the whole system doesn't work very well - which means it
    can't easily be debugged.
...

? - A system such as yours which involves multiple BGP systems,
    in a layered hierarchy.

? - As above, but with a separate ITR-ETR scheme in each domain
    (which I think is impossible) - which is what you are
    suggesting.

...

? - Any system which involves host changes.

What I meant to say is:

These ITR-ETR schemes are not being contemplated with the express
purpose of being easier to debug than the current system, but
because the current system can't continue, and we need something
more complex - which will no-doubt be harder to debug than the
current system.

I am convinced that any architecture such as yours which creates
multiple BGP systems and/or multiple ITR-ETR systems will be far
harder to debug than a simpler approach.

> simpler than an ever-growing mesh. There's a systems engineering

It is definitely not conceptually simpler.

I think the ITR-ETR approach enables the BGP system to retain its
current, practical, scale - without any conceptual changes to the
BGP system itself.  The ITR-ETR system is definitely a bunch of
extra concepts and functional elements.  However, the currently
discussed proposals are all for one BGP system with one ITR-ETR
system as the optimal outcome.  (Multiple Ivip systems could operate
in parallel - even on a commercial basis - but this is not what I am
pursuing.)

The trick is to make the ITR-ETR system much more scalable than BGP
is.  This is a challenge, but seems practical.

For instance, Ivip enables each ISP to select where it wants to put
full database ITRs (ITRDs) and Query Servers (QSDs) and where to put
the caching ITRs (ITRCs) and ITFHs (ITR Function in Host).  This
enables them to optimise the arrangement so as not to push all the
mapping data to too many devices, by relying more on local query and
response traffic.

Fanning out a stream of mapping data, fast, to ITRDs and QSCs all
over the world is a challenge, but it is much simpler, faster and
more efficient than trying to get global distribution of a
comparable quantity of information via BGP's slow, awkward,
uncoordinated, one peer to the next approach - which may take ages
to converge on the optimal outcome.

I am proposing we add exactly one (admittedly complex) conceptual
thing to the Internet - and only one instance of that thing.

You seem to be suggesting we need a new multilevel BGP system to
overtake the current one, with a large number of instances of this
new system.  You also wrote that each such instance requires its own
instance of another new concept - an ITR-ETR scheme.

> thought is needed about spoofing and loop-prevention).

You have complex rules about different levels of BGP system and
then, because this creates obvious inefficiencies and unwanted
complexities, you are tempted to create further arrangements (more
complexity still) to resolve these difficulties.

I just think your scheme is not needed - a single BGP system and a
single ITR-ETR system should do the trick.

  - Robin

  http://shootdowns-R-us.net
  This week, the Big Bang Theory: http://astroneu.com

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 24 Nov 2007 08:32:57 +1300

Just two remarks:

>   single ITR-ETR system should do the trick.

We differ ;-). I don't think we can add anything to our arguments,
so I'd like to know what other people think - one level
vs several levels.

<snip>

> the ETR.  The outer source address is that of the sending host.

My argument applies to any form of encapsulation - the inner packet may
perceive one hop from A to B, but the outer header may experience any number
of actual hops.

      Brian

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 24 Nov 2007 22:47:50 +0100

> so I'd like to know what other people think - one level

Since you ask: what I would like to see is a combination of something  
from the LISP family combined with a hierarchical mechanism like CRIO  
that allows packets for which there is no mapping yet to be delivered  
through increased stretch.

The number of levels in the hiearchy would presumably be greater than  
one, but this is something that the operators should figure out.

I'm not sure I've digested all the elements of your IFSD (idea for  
shooting down) approach, but in general, I'm suspicious of an approach  
where there is emphasis on having different levels of an hierarchy  
that isn't a natural extension of the addressing hierarchy because  
this requires extra effort to find out where in the hierarchy a  
certain prefix is present at any given time. An approach where the  
routing hierarchy is aligned with the address bits seems a more  
natural choice to me. But I'm open to hearing more arguments.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sat, 24 Nov 2007 22:47:50 +0100

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 26 Nov 2007 09:24:22 +1300

On 2007-11-25 10:47, Iljitsch van Beijnum wrote:
> where there is emphasis on having different levels of an hierarchy that 
> isn't a natural extension of the addressing hierarchy because this 
> requires extra effort to find out where in the hierarchy a certain 
> prefix is present at any given time. An approach where the routing 
> hierarchy is aligned with the address bits seems a more natural choice 
> to me. But I'm open to hearing more arguments.

I really wish it could be like that, but I think all the history,
including pre-CIDR days and the modern PI heresy, shows that we simply
aren't going to achieve congruence between topology and address
structure. So yes, I guess I'm arguing that *if* we want a defined
hierarchy, it has to be orthogonal to address structure (which is why
I suggest borrowing some AFI bits to represent the hierarchy in the
maps).

    Brian

---

From: Tony Li <[email-masked]>
Date: Tue, 27 Nov 2007 19:50:30 -0800

> I suggest borrowing some AFI bits to represent the hierarchy in the

Well, I think it's pretty clear that congruence isn't entirely  
possible.  If nothing else, addressing naturally forms a hierarchy,  
whereas topology is an arbitrary graph.  Perhaps I'm putting more  
into 'congruence' than you really meant.

Yes, clearly we need hierarchy so that we have abstraction. Yes, we  
would clearly like to have things defined, as the alternative is  
worse.  ;-)  However, it's not at all clear to me that borrowing bits  
from the AFI really changes anything conceptually.  It's basically  
just more bits that could have been part of the address prior.

[rant about variable length addressing elided...]

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 28 Nov 2007 17:12:18 +1300

On 2007-11-28 16:50, Tony Li wrote:
> whereas topology is an arbitrary graph.  Perhaps I'm putting more into 
> 'congruence' than you really meant.
> 
> would clearly like to have things defined, as the alternative is worse.  
> ;-)  However, it's not at all clear to me that borrowing bits from the 
> AFI really changes anything conceptually.  It's basically just more bits 
> that could have been part of the address prior.

It means you can change a prefix's place in the hierarchy without changing
the bits in the prefix - given the allergy of most user sites to
renumbering, that seems to be a plus point.
> [rant about variable length addressing elided...]

[rant about how we could have added address extensions in 1994
elided...]

     Brian

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 28 Nov 2007 08:10:51 -0500 (EST)

> From: Brian E Carpenter <[email-masked]>

    > It means you can change a prefix's place in the hierarchy ...
    > given the allergy of most user sites to renumbering

[Rant about how it's unreaonable to expect to be able to change *where* you
are in the topology without changing your location-name elided... :-]

	Noel

---

From: Tony Li <[email-masked]>
Date: Wed, 28 Nov 2007 08:10:47 -0800

> are in the topology without changing your location-name elided... :-]

And we *are* talking about changing a locator, not an identifier,  
right????

Tony

---

From: "Tom Petch" <[email-masked]>
Date: Wed, 28 Nov 2007 15:18:32 +0100

----- Original Message -----
From: "Brian E Carpenter" <[email-masked]>
To: "Iljitsch van Beijnum" <[email-masked]>
Cc: "RRG" <[email-masked]>
Sent: Thursday, November 22, 2007 9:59 PM
Subject: Re: [RRG] Idea for shooting down

> clearly.

For once, I think the .pdf explains it clearly (or perhaps I do not
understand:-)

I think that every scheme proposed, and every scheme that will be proposed, is
based on a heirarchy in some abstract sense and that the feature of this one is
to use AFI to 'expand' the IP address range, and to allow multiple levels.

I wonder about router capacity, that is that the Internet only works because
routers are incredibly fast at 'parsing' IPv4 addresses and I think that that is
the inherent nature of an IP address, rather than because ASICs have been
optimised for that task.  So what I wonder about is the speed of routers at the
transition from s+x flat routing to the next level down, s+x-1; an alternative
could be to put the equivalent of the AFI bits into the middle of an IPv6
address (howls of protest) with an IPv4 address in the lower order bits, so
preserving the single bit-structure to parse.

My other thought is the political one, that ISPs have had a fairly free rein to
place points of presence where they will, unconstrained by the sorts of
considerations of Internet technology that drive these discussions, and that
some day they may (will?) have to change and accept that eg because they are in
a particular location, then they must aggregate in a certain way and use a
certain transit to access the rest of the world.

Tom Petch

> Since I won't be in Vancouver, I will try to come up with

---

From: Tony Li <[email-masked]>
Date: Wed, 28 Nov 2007 10:58:23 -0800

> preserving the single bit-structure to parse.

I can vouch that routers are incredibly fast at doing longest-match  
lookups because folks have put in incredible amounts of work into the  
ASICs.  Yes, of course, it could be much, much worse, but doing  
longest-match can in no way be construed as 'simple' to implement in  
hardware.

That said, if we want to make forwarding plane changes (and all of  
the proposals that I've seen involve some changes somewhere ;-),  
making those changes in the ASICs is not unreasonable.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 29 Nov 2007 09:44:18 +1300

On 2007-11-29 05:10, Tony Li wrote:
> And we *are* talking about changing a locator, not an identifier, right????

Well, in my proposal [Note to self: invent acronym] the idea is to change
the map entry. Using AFI bits to do so is only a trick.

    Brian

---

From: [email-masked]
Date: Wed, 28 Nov 2007 17:51:33 EST

In einer eMail vom 28.11.2007 20:00:04 Westeuropäische Normalzeit schreibt  
[email-masked]:

Tony

A single matrix lookup for any destination which is still in a different  
geo-patch can also be done by ASIC.
Can anybody tell the difference in time compared with prefix lookup by  ASICs 
?
 
Heiner

---

From: Tony Li <[email-masked]>
Date: Wed, 28 Nov 2007 14:57:55 -0800

On Nov 28, 2007, at 2:51 PM, [email-masked] wrote:

> A single matrix lookup for any destination which is still in a  
> different geo-patch can also be done by ASIC.

True, that should be a straightforward array lookup.

> Can anybody tell the difference in time compared with prefix lookup  
> by ASICs ?

Yes, the longest-match would be much, much slower.  ;-)

In any non-trivial forwarding table, the longest-match will require  
multiple memory reads.  Exactly how many is very much a function of  
the specific lookup algorithm.  In a naive v4 implementation, you  
could reasonably take around 24 memory reads.  However, the array  
lookup should be just a single read.

Tony

---

From: [email-masked]
Date: Thu, 29 Nov 2007 03:59:58 EST

In einer eMail vom 28.11.2007 23:59:17 Westeuropäische Normalzeit schreibt  
[email-masked]:

On Nov 28, 2007, at 2:51 PM, [email-masked] 
(mailto:[email-masked])  wrote:

In any non-trivial forwarding table, the longest-match will require  multiple 
memory reads.  Exactly how many is very much a function of the  specific 
lookup algorithm.  In a naive v4 implementation, you could  reasonably take around 
24 memory reads.  However, the array lookup should  be just a single read.

Tony

=

You see, this concept is not only scalable but enables faster  forwarding as 
well
 
Another point: Mobile IP-phones. They can provide the geo-location down to  
the second (rather just down to the degree). If they move to a different 1x1  
geo-patch they have to notify their base stations about the new long/lat 
degrees  and advertise the changed reachability only within the affected 1x1 square  
degree geo-patches, within the previous (for withdraw) and within the new  
one. No world-wide routing churn.
 
I am sure, if each of you started to trust your own eyes, you would  discover 
many more improvements than me. You know the hurdles and the ackwards  of the 
current BGP better than me.
 
Heiner

Heiner

---

From: Scott Brim <[email-masked]>
Date: Wed, 5 Dec 2007 18:40:40 -0800

> mapping). ((Er, LISP EIDs are a special case of locator as far as

Brian, I believe the goal is to reduce the number of map entries that
an ETR might want to cache.  However, the lookup key for a cache entry
is the ultimate prefix.  Reducing the number of ETRs doesn't help.  If
I understand your scheme, reducing the number of entries depends on
prefixes being more aggregatable as you bring in your higher levels of
ETRs.  There will certainly be some aggregation if "regional" IRs
continue to allocate address blocks, but there will always be
outliers, for example when a USA oil company relocates to Kazakhstan.
So your scheme helps if address allocation is constrained to follow
topology ... but if that's true then the problem I think you solve
doesn't arise.

So based on what you say above, I no longer think I understand what
problem you solve.

Excerpts from Iljitsch van Beijnum on Sat, Nov 24, 2007 10:47:50PM +0100:
> Since you ask: what I would like to see is a combination of something from 
> the LISP family combined with a hierarchical mechanism like CRIO that 
> allows packets for which there is no mapping yet to be delivered through 
> increased stretch.

Take a look at the LISP interworking draft.
http://www.1-4-5.net/~dmm/draft-lewis-lisp-interworking-00.txt

Does that do what you want?

CRIO had "destination-side" default routers (my terminology), serving
particular destination prefixes on behalf of all sources.  The other
model is to be more "source-side", serving all destinations on behalf
of a particular set of sources.  An intermediary like you want can be
either, depending on deployment optimizations.  The LISP interworking
draft calls them proxy tunnel routers.

swb

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 07 Dec 2007 10:45:03 +1300

Scott,

> topology ... but if that's true then the problem I think you solve

Firstly, it certainly doesn't make the map smaller; in fact the
entries get slightly bigger and there will be a small proportion
of additional entries at the higher levels of the hierarchy.

However, it doesn't assume a rigid correspondence between
the topology of the regions and the addressing structure;
by recursing the LISP (or equivalent) model at each level,
you avoid that.

> So based on what you say above, I no longer think I understand what

It seems pretty clear to me that just as pollution/entropy has arisen
naturally in the current DFZ, the same thing will happen in the
cleaned-up DFZ that LISP will initially create. And as we grow
the network to billions of nodes and many thousands of RLOCs, that
problem may need solving. Recursing the model seems to be the
only way to do so.

I like the PTR model you mention below, but what happens when
you need PTRs to clean up mess among the RLOCs? You recurse.

     Brian