Subject: [RRG] incrementally deployable

From: [email-masked]
Date: Tue, 6 Nov 2007 11:46:36 EST

Some weeks ago Robin asked whether my hierarchical routing model would be  
incrementally deployable
and I responded by saying "No", without having given any thoughts to this  
aspect. But in the meantime I did
and my answer to his question is "Yes, for sure".
 
Hierarchy means logarithmical reduction of the complexity.
E.g. instead of 50 x 50 x 50 x 50 (which is 6,250,000) you need only 50 +  50 
+ 50 +50 = 200.
 
Whenever I said instead of 200-300K FIB entries, 2-3K entries will be  
sufficient, I even might have been too cautious. The above figures mean: a  BGP-FIB 
with up to 6,250,000 entries can be replaced by 200 entries.
However, 200 is such a neglectable number, that it should be  affordable IN 
ADDITION to the current BGP-FIB figure as well. Consequently for  the next hop 
determination towards a far remote destination a router may  have two 
alternatives, and as I said before, for the last few hops towards  a destination in 
the neighboring network part, the existing method could be  applied (even for a 
longer while).
 
Also: this little new forwarding information  can generously be placed into a 
bigger-sized table such that the next hop  towards any genuine hierarchical 
node can be done by ONE SINGLE  matrix element look up ! (no search for a 
fitting match).
 
Also: Eliminating the scalability problem is not all. Indeed, this little  
but well aquired new routing information can do much more than BGP or  LISP:  
Note that Multihoming is only focused on multiple alternatives  with respect to 
the last hop. The right focus however would be multiple  alternative paths 
whose last hops involve alternative ISPs. 
 
Heiner

---

From: Robin Whittle <[email-masked]>
Date: Wed, 07 Nov 2007 11:25:21 +1100

Hello Heiner,

You have written a number of messages indicating that there is some
radically different, superior and (I guess) simpler approach to the
routing scalability problems than those currently being contemplated
with LISP-CONS/NERD, eFIT-APT, Ivip, TRRP or various moderate
enhancements to BGP.

However, I don't think you haven't written about what you are
proposing as an alternative.

Your site:

  http://www.hummel-research.de

has a Flash presentation which mentions "Multipath Direction Field
MPDF", but Google finds no other mention of this.

Where is your proposal clearly documented?

Incremental deployment means (perhaps amongst other things) that
there are immediate overall benefits for the early adopters of a new
technology.  Any scheme which requires complete upgrades of all BGP
routers, all hosts etc. is not at all incrementally adoptable.
Likewise, a scheme in which the address space managed by the new
system is unreachable from non-upgraded networks is not
incrementally deployable, because virtually all of the people who
might initially adopt this new space would find the loss of
connectivity a far greater problem than whatever benefits the new
system provided.

   - Robin

--
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: [email-masked]
Date: Wed, 7 Nov 2007 04:15:04 EST

As already mentioned, I did describe my solution when "we" submitted the  
NIRA-project proposal for being funded by the EU,but it was rated to be POOR and  
therefore rejected.I still think that the NIRA objectives are  outstanding,at 
least far ahead of what this community is dreaming of. With  the scalability 
problem eliminated,  much better TE objectives as well as  new services could 
be envisioned for decades to come.
(Note, you never consider p2mp/mp2mp inside LISP etc. !)
 
Remains the question whether the  NIRA-objectives are feasible? I indirectly 
provided proofs by  submitting well computed graphs. In view of the outcome, I 
was well  advised not to disclose the used algorithm. 
I am pretty sure that the evaluator subscribes to RAM/RRG-  mailinglists. I 
am also waiting to see any other ideas being taken to these  mailinglists which 
come from the 150 adopted projects. My hope is, that there  will be another 
research project opportunity somewhere in the future.
So I do not mind that LISP etc. is continued in the meantime.But I  sometimes 
observe the hereby hit obstacles and think none of all this sweat is  needed.
 
Heiner

In einer eMail vom 07.11.2007 01:29:24 Westeuropäische Normalzeit schreibt  
[email-masked]:

Hello  Heiner,

Your  site:

- Robin

---

From: Tony Li <[email-masked]>
Date: Wed, 7 Nov 2007 01:36:03 -0800

Care to share your project proposal?

Tony

On Nov 7, 2007, at 1:15 AM, [email-masked] wrote:

> As already mentioned, I did describe my solution when "we"  
> submitted the NIRA-project proposal for being funded by the EU,but  
> it was rated to be POOR and therefore rejected.I still think that  
> the NIRA objectives are outstanding,at least far ahead of what this  
> community is dreaming of. With the scalability problem eliminated,   
> much better TE objectives as well as new services could be  
> envisioned for decades to come.
> Remains the question whether the NIRA-objectives are feasible? I  
> indirectly provided proofs by submitting well computed graphs. In  
> view of the outcome, I was well advised not to disclose the used  
> algorithm.
> I am pretty sure that the evaluator subscribes to RAM/RRG-  
> mailinglists. I am also waiting to see any other ideas being taken  
> to these mailinglists which come from the 150 adopted projects. My  
> hope is, that there will be another research project opportunity  
> somewhere in the future.
> So I do not mind that LISP etc. is continued in the meantime.But I  
> sometimes observe the hereby hit obstacles and think none of all  
> this sweat is needed.
>
> Heiner
>
>
> In einer eMail vom 07.11.2007 01:29:24 Westeuropäische Normalzeit  
> schreibt [email-masked]:
> Hello Heiner,
>

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Wed, 7 Nov 2007 12:06:43 +0100

On Wed, Nov 07, 2007 at 04:15:04AM -0500,
 [email-masked] <[email-masked]> wrote 
 a message of 178 lines which said:

> As already mentioned, I did describe my solution when "we" submitted
> the NIRA-project proposal for being funded by the EU,

URL where I can download a text file / HTML page / PDF document /
whatever? Otherwise, I would not be the only one to think it is purely
handwaving...

---

From: [email-masked]
Date: Wed, 7 Nov 2007 08:15:38 EST

In einer eMail vom 07.11.2007 12:08:26 Westeuropäische Normalzeit schreibt  
[email-masked]:

I can assure you that this concept (which needs algorithmical  computation of 
topologies) is based on what you can see on my website's  sample network 
diagram, where all links are converted to arrows. The result may  be called 
Multipath Direction Field, or may be called All Links Spanning Tree  (ANST). All 
blue arrows form an ALL Nodes Spanning Tree (ANST) which is simply  the Dijkstra 
shortest path tree and which is part of the ALST resp. MPDF.
 
The ALST resp. MPDF is just a starter. It  will impact ipfrr  as well as the 
more important current RRG-topic, plus more.
 
As to find out whether this is just hot air or not, choose any sequence of  
arrows you like and try not to wind up at the red node. Only if you can  
accomplish this or if you can detect any single loop of arrows, I will  apologize...
 
Heiner
 
_www.hummel-research.de_ (http://www.hummel-research.de)

---

From: <[email-masked]>
Date: Wed, 7 Nov 2007 16:03:18 -0000

Heiner

I for one would be very interested to learn about your ideas. 

I followed your challenge about following the sequence of arrows (the first part of which was to find the right page to look at on your web site!!) - and indeed I ended up at the red node. So your approach is devising a Directed Acyclic Graph? I worked a bit on the TORA routing protocol, which formed DAGs so would be interested to hear how similar /different it is. why are your arrows multi-coloured? How does it work when the topology changes? Where's there's a choice of next hops, how do you decide which to use? Earlier you said that the alternative routes would use different ISPs, how is this reflected in the DAG?

You earlier implied that your approach is hierarchical, where does the hierarchy come into it? [your red node picture doesn't seem to have a hierarchy]

You mention Rekhter's law: addressing may follow topology or topology may follow addressing but choose one. Which one would you choose? Why? Nb at least some of the rrg proposals are trying at a high level to do this - splitting locator & ID to allow more freedom on how the locators are assigned so that they can follow the topology more closely [better aggregatable] and hence improve scalability of routing tables. Do you agree?

Sorry for all the questions, would be very interested in the answers!

Ps I expect you know -  when the EU judges research proposals 'Scientific & technical excellence' is worth 1/3rd of the marks, so it's quite possible for proposals to score well in this category and still fail. Which can be frustrating. Do you have plans to submit a proposal with similar technical scope?

Thanks

Best wishes

Philip Eardley 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: 07 November 2007 13:16
To: [email-masked]
Cc: [email-masked]
Subject: Re: [RRG] incrementally deployable

In einer eMail vom 07.11.2007 12:08:26 Westeuropäische Normalzeit schreibt [email-masked]:

I can assure you that this concept (which needs algorithmical computation of topologies) is based on what you can see on my website's sample network diagram, where all links are converted to arrows. The result may be called Multipath Direction Field, or may be called All Links Spanning Tree (ANST). All blue arrows form an ALL Nodes Spanning Tree (ANST) which is simply the Dijkstra shortest path tree and which is part of the ALST resp. MPDF.

The ALST resp. MPDF is just a starter. It  will impact ipfrr as well as the more important current RRG-topic, plus more.

As to find out whether this is just hot air or not, choose any sequence of arrows you like and try not to wind up at the red node. Only if you can accomplish this or if you can detect any single loop of arrows, I will apologize...

Heiner

www.hummel-research.de

---

From: [email-masked]
Date: Wed, 7 Nov 2007 12:02:19 EST

Philip,
Please excuse my ignorance about DAG and TORA, so I can't say anything  about.
I use the following colors: blue = Dijkstra best hop, red = equally best,  
yellow= remote node has the same distance to the red destination node. Because  
in this example all link weights are equal 1, therefore there is no green 
arrow,  with green = get closer to dest. but not as close as by a blue or red  
arrow.
 
My picture doesn't show any hierarchy. It only shows the effects  of this 
elementary algorithm which however is needed to  compute  topologies of upper 
hierarchical levels.
 
My favorite is "topology follows addressing", but I guess this remark  
doesn't help you much without knowing the entire solution - which indeed does  not 
just improve scalability but abolishes this problem. Not only  for now, but 
forever. 
 
Thanks for your interest, anyway. 
Heiner

 
In einer eMail vom 07.11.2007 17:03:43 Westeuropäische Normalzeit schreibt  
[email-masked]:

Heiner 
I for one would be  very interested to learn about your ideas.  
I followed your  challenge about following the sequence of arrows (the first 
part of which was  to find the right page to look at on your web site!!) – and 
indeed I ended up  at the red node. So your approach is devising a Directed 
Acyclic Graph? I  worked a bit on the TORA routing protocol, which formed DAGs 
so would be  interested to hear how similar /different it is. why are your 
arrows  multi-coloured? How does it work when the topology changes? Where’s there’
s a  choice of next hops, how do you decide which to use? Earlier you said 
that the  alternative routes would use different ISPs, how is this reflected in 
the  DAG? 
You earlier implied  that your approach is hierarchical, where does the 
hierarchy come into it?  [your red node picture doesn’t seem to have a hierarchy] 
You mention Rekhter’s  law: addressing may follow topology or topology may 
follow addressing but  choose one. Which one would you choose? Why? Nb at least 
some of the rrg  proposals are trying at a high level to do this – splitting 
locator & ID  to allow more freedom on how the locators are assigned so that 
they can follow  the topology more closely [better aggregatable] and hence 
improve scalability  of routing tables. Do you agree? 
Sorry for all the  questions, would be very interested in the answers! 
Ps I expect you know  -  when the EU judges research proposals ‘Scientific & 
technical  excellence’ is worth 1/3rd of the marks, so it’s quite possible 
for  proposals to score well in this category and still fail. Which can be  
frustrating. Do you have plans to submit a proposal with similar technical  scope? 
Thanks 
Best  wishes 
Philip Eardley   
 
-----Original  Message-----
From:  [email-masked] [mailto:[email-masked]] On Behalf Of  
[email-masked]
Sent: 07 November 2007 13:16
To: [email-masked]
Cc: [email-masked]
Subject: Re: [RRG] incrementally  deployable 

 

 

Heiner

_www.hummel-research.de_ (http://www.hummel-research.de/)

---

From: Tony Li <[email-masked]>
Date: Wed, 7 Nov 2007 09:18:05 -0800

On Nov 7, 2007, at 5:15 AM, [email-masked] wrote:

> I can assure you that this concept (which needs algorithmical  
> computation of topologies) is based on what you can see on my  
> website's sample network diagram, where all links are converted to  
> arrows. The result may be called Multipath Direction Field, or may  
> be called All Links Spanning Tree (ANST). All blue arrows form an  
> ALL Nodes Spanning Tree (ANST) which is simply the Dijkstra  
> The ALST resp. MPDF is just a starter. It  will impact ipfrr as  
> well as the more important current RRG-topic, plus more.
>
> As to find out whether this is just hot air or not, choose any  
> sequence of arrows you like and try not to wind up at the red node.  
> Only if you can accomplish this or if you can detect any single  
> loop of arrows, I will apologize...
>

Thanks, but one example hardly shows that you have a new and  
beneficial approach.  In fact, all it proves is that you have... an  
example.

Until and unless you present the conceptual underpinnings, you're not  
contributing.

Tony

---

From: David Williamson <[email-masked]>
Date: Wed, 7 Nov 2007 10:34:03 -0800

> connectivity a far greater problem than whatever benefits the new

I wanted to chime in on this point.  Incremental deployment is vital to
the success of any new routing methodology.  It doesn't matter how much
of an improvement any of the available proposals produce if it cannot
offer incremental deployment, as operators will simply not use it.

For non-incrementally deployable methods, there are only two choices
for a service provider like my organization.  We can either build
another instance of our entire service that uses the new method while
the old one continues to use traditional routing until our last
customer moves to the new scheme, or we can depend on a third-party for
some sort of proxy service between the two routing regimes.  The former
is clearly financially impractical, and the latter would require a
third-party capable of essentially zero downtime.  Neither option is
particularly palatable.

I haven't read deep enough into all of the proposals to figure out
which ones are incrementally deployable.  While I slowly work on that,
I hope that everyone involved keeps the practical requirements in
mind.

Thanks!

-David

-- 
David Williamson
Operations Architecture
Tellme, a Microsoft subsidiary 
<[email-masked]> <[email-masked]>

---

From: JFCM <[email-masked]>
Date: Thu, 08 Nov 2007 05:42:47 +0100

>I hope that everyone involved keeps the practical requirements in

multi-incremental deployability is actually the need. It is not 
believable at this stage that any solution can be agreed, documented, 
tested, validated and deployed before users start being concerned 
enough to test various other solutions by their own.
jfc

---

From: <[email-masked]>
Date: Wed, 7 Nov 2007 16:03:18 -0000

Heiner

Thanks

Best wishes

Philip Eardley 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: 07 November 2007 13:16
To: [email-masked]
Cc: [email-masked]
Subject: Re: [RRG] incrementally deployable

Heiner

www.hummel-research.de

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Thu, 8 Nov 2007 12:02:44 +0100

On Wed, Nov 07, 2007 at 08:15:38AM -0500,
 [email-masked] <[email-masked]> wrote 
 a message of 101 lines which said:

> arrows.

A nice animation is not what I would call a serious proposal,
specially when all I see is a warning that I have to download some
plugin...

---

From: Christian Vogt <[email-masked]>
Date: Fri, 09 Nov 2007 15:38:45 +0200

David -

> which ones are incrementally deployable. 

Amongst those solution proposals that use IP address mappings [Shim6,
Six/One, LISP, eFIT, Ivip], incremental deployability is equivalent to
the use of globally routable IP addresses on both sides of the mapping.

If IP addresses are globally routable, packets can reach their
destination with and without a mapping.  Hosts can then communicate even
if the mapping is not supported on either one's side.  All it takes is a
mechanism that discovers lack of mapping support on the remote side and, 
in such a case, disable the mapping on the local side.

Six/One and Shim6 are incrementally deployable because they use
provider-dependent IP addresses, which are aggregatable and hence can be 
represented in the global routing table in a scalable manner.  Ivip, 
too, is incrementally deployable because it uses provider-dependent IP 
addresses in combination with globally routable anycast IP addresses.

For techniques that use non-routable IP addresses on the host side of
the mapping, such as LISP, reachability of hosts depends on a mapping
being accomplished on both sides of a packet flow.  This precludes
incremental deployment because for one edge network to deploy the
technique without loss of global reachability, all other edge networks
must deploy the technique also.

- Christian

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Fri, 9 Nov 2007 08:57:08 -0800

> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of Christian Vogt
<snip>
> For techniques that use non-routable IP addresses on the host 
> side of the mapping, such as LISP, reachability of hosts 
> depends on a mapping being accomplished on both sides of a 
> packet flow.  This precludes incremental deployment because 
> for one edge network to deploy the technique without loss of 
> global reachability, all other edge networks must deploy the 
> technique also.
> 

So are you claiming incremental deployment is not possible with
LISP?

What if a 3rd party provides a proxy between the two systems,
then incremental deployment is possible. Then networks who
are not LISP capable can reach EIDs that are not in the global
Routing table.

Alternatively, what if an xTR performs NAT between PA space
and EID space?

There are some other possibilities here, but I think you are
being too harsh in your analysis.

-Darrel

---

From: David Williamson <[email-masked]>
Date: Fri, 9 Nov 2007 09:05:39 -0800

> are not LISP capable can reach EIDs that are not in the global

That's certainly a form of incremental deployment, and I alluded to it
in my original message.  The real question is if that's sufficient for
a wide majority of business models.  I'll take my own org as an
example: we run an extremely reliable service, but we have dependencies
on reaching customers and partners for content of various types.  Much
of that runs across direct private connections, so there's really no
impact from LISP.  Some of it, however, is over the Internet.

Would a 3rd party proxy be sufficiently robust and reliable to permit
me to make my site LISP capable and still have the level of
connectivity my business requires to those customers?  That's a very
hard quesiton to answer.  I'm not saying it's out of the question, but
it's a very troublesome additional piece of complexity for a service
provider to contemplate.  I honestly don't know the answer right now.
The concept is palatable, but it would depend on the business features
of a 3rd party product.

> Alternatively, what if an xTR performs NAT between PA space

Where would PI fit in this?  Renumbering into PA space isn't a viable
option at the moment.  I don't think I quite see the entire implications
here, yet.

Thanks!

-David

---

From: "Stephen Sprunk" <[email-masked]>
Date: Sat, 10 Nov 2007 10:29:02 -0600

Thus spake "David Williamson" <[email-masked]>
>> are not LISP capable can reach EIDs that are not in the global

Technically, if there were anycast ITRs, then all EIDs would be in the DFZ, 
albeit in aggregated form.  For instance, say we decided v6 EIDs would be in 
4000::/3; every anycast ITR would advertise that prefix, providing 
reachability from sites without their own ITR.  Or, if each set of ITRs only 
handled part of the EID range (say, each RIR maintained a separate 
database), then they'd provide an anycast advertisement for their part.

> That's certainly a form of incremental deployment, and I alluded to
> it in my original message.  The real question is if that's sufficient for
> example: we run an extremely reliable service, but we have
> dependencies on reaching customers and partners for content of
> various types.  Much of that runs across direct private connections,
> so there's really no impact from LISP.  Some of it, however, is over
> the Internet.
>

And that, in turn, depends on who is providing those public ITRs. 
Logically, the RIRs are the best folks to be keeping copies of the 
EID-to-RLOC mappings since they already maintain all sorts of databases 
about RLOCs and would probably be the folks handing out EIDs as well.  The 
RIRs, then, are the logical providers of ITRs-of-last-resort.  They might 
provide the public ITRs themselves, or contract with a large number of 
default-free ISPs -- or CDNs -- to provide ITRs.  That's up to them to 
figure out.

> option at the moment.  I don't think I quite see the entire implications

PI is still new in v6; ARIN has only handed out ~100 blocks as of last 
month, all out of an easily-identified prefix (2620:0000::/23).  It'd be 
easy enough to redefine that as an EID block, or to deprecate assignments 
from that block and give them a different block (out of a top-level IANA 
block) designated for EIDs.

S

Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

---

From: Christian Vogt <[email-masked]>
Date: Mon, 12 Nov 2007 17:00:10 +0200

Darrel:

> What if a 3rd party provides a proxy between the two systems, then 
> incremental deployment is possible. Then networks who are not LISP 
> capable can reach EIDs that are not in the global Routing table.

This proxy would defeat the purpose of any multi-homing solution in
terms of reducing an edge network's dependency on a provider, since the
edge network would then depend on the provider operating the proxy.  The
edge network would probably also have to pay for the proxying service.

Two more issues with this proxy approach depend on the type of
addressing space proxies would advertise in BGP:

(a) If proxies advertised EID space, the number of global routing table
     entries could not be reduced.

(b) If proxies advertised LOC space, hosts in upgraded networks would
     continue to be reached via LOC addresses, and this reduces the
     benefit of the EID/LOC split.

Ivip avoids the dependency on a single proxy by grouping multiple
providers to do the proxying for redundancy.  An edge network's EID
space is then advertised by multiple providers.  To reduce the number of
routing table entries, Ivip also groups edge networks, and it uses one
EID block per edge network group.

The Ivip model creates new dependencies, though:

- Providers in a group are bound to other providers in the group.  They
   must coordinate their BGP advertisements because a customer edge
   network of one provider is also a customer of the other providers in
   the group.

- Edge networks in a group are bound to other edge networks in the group
   because they cannot leave the group without renumbering.

- Edge networks are bound to their provider group because they cannot
   move to a provider in a different group without renumbering.

> Alternatively, what if an xTR performs NAT between PA space and EID 
> space?

This is classic NAT'ing.  It's no longer LISP because the IP address
mapping won't be reversed.  Furthermore, NAT'ing reduces the benefit of
the EID/LOC split because hosts continue to be reached via LOCs.

- Christian