Subject: RE: The state of IPv6 multihoming development

From: "Tony Li" <[email-masked]>
Date: Wed, 23 Oct 2002 10:41:54 -0700

|     We have been down this road before. I though we were in 
|   agreement on 
|   two things:
|       1) that multihoming would increase, 
|       2) and that we can't do it like IPv4.

Yes, we agree.  Now we're onto something harder:

	3) we need to fix it now

Tony

---

From: Greg Maxwell <[email-masked]>
Date: Wed, 23 Oct 2002 13:54:40 -0400 (EDT)

> Yes, we agree.  Now we're onto something harder:

I've still yet to see an idea here that provided complete multihoming
(i.e. ones that won't get filtered to uselessness) without either breaking
aggregation and exploding the DFZ or making transport level changes..

In other news.. SCTP is included now in the Linux 2.5.xx development
chain.

---

From: Randy Bush <[email-masked]>
Date: Wed, 23 Oct 2002 11:08:52 -0700

> (i.e. ones that won't get filtered to uselessness)

as i am not aware of anyone filtering v6 announcements at the moment
(well, other than maybe at /48 or something), perhaps this wg should
work on solutions to the routing problems presented and assume that,
if reasonable aggregation is one of those goals and is met, that the
isps will act rationally.

randy

---

From: Greg Maxwell <[email-masked]>
Date: Wed, 23 Oct 2002 14:27:16 -0400 (EDT)

> isps will act rationally.

Lets say that everyone who mutihomes will take their provider based
address and announce it to other providers.. This would work..
But it would also explode the DFZ..

Okay, so people could filter the smaller routes... effectively
de-multihoming the multihomer.. so filtering is not a reasonable solution
to multihoming caused DFZ inflation.

So, here is the point of the problem:

Do we care about inflating the DFZ?

  Keep in mind that DFZ inflation is more costly in v6 due to the larger
  amount of data involved and the expected growth of multihomed networks..
  and that it's price carried by everyone, even people without business
  relationships with the multihomers

If we don't care (which I think would be an example of extremely poor
foresight..) then multihomers should just announce more-specifics of
their other providers address blocks and act just like it is in the v4
world.  Problem solved.

If we do care about preserving aggregation (one of the stated goals of
IPv6), then we can NOT permit *any* multihoming aggregation busting and
multihoming must be provided either by transport layer enhancements (my
favor, see archives) or via tunnel hacks.

I got tired of discussing the matter because of the group's unwillingness
to seriously consider transport layer modifications (wah wah outside of
the scope blah.. I thought my argument for prefix flowthrough and SCTP
was compelling.. No DFZ busting, the only catch was that legacy apps
wouldn't be multihomed: a good reason to upgrade them).. If you simply can
not do anything but break aggregation then fine, stop waffling and
declare it already. The problem isn't just going to go away.

The only thing worse then making a bad decision is wasting a lot of time
making a bad decision.

---

From: "Craig A. Huegen" <[email-masked]>
Date: Wed, 23 Oct 2002 13:29:08 -0500 (Central Daylight Time)

> isps will act rationally.

We had been announcing a /40 for a short period of time.  A month or two
ago, we experienced unreachability to www.kame.net and found that filters
were put in place to filter anything longer than /35 in one of the
Japanese ISP's, such that 2001:420::/40 was no longer accepted.

/cah

---
Craig A. Huegen, Chief Network Architect      C i s c o  S y s t e m s
IT Transport, Network Technology & Design           ||        ||
Cisco Systems, Inc., 400 East Tasman Drive          ||        ||
San Jose, CA  95134, (408) 526-8104                ||||      ||||
email: [email-masked]       CCIE #2100      ..:||||||:..:||||||:..

---

From: Pekka Savola <[email-masked]>
Date: Wed, 23 Oct 2002 21:36:35 +0300 (EEST)

> Japanese ISP's, such that 2001:420::/40 was no longer accepted.

And you think advertising it was rational?

Nope...

I want to announce my 6to4 /48 too but my neighbors won't let me :-(

-- 
Pekka Savola                 "Tell me of difficulties surmounted,
Netcore Oy                   not those you stumble over and fall"
Systems. Networks. Security.  -- Robert Jordan: A Crown of Swords

---

From: "Craig A. Huegen" <[email-masked]>
Date: Wed, 23 Oct 2002 13:56:56 -0500 (Central Daylight Time)

> I want to announce my 6to4 /48 too but my neighbors won't let me :-(

*shrug* I was pointing out to Randy that some providers are indeed
filtering.

Do I think it's rational to advertise that /40?  Given the circumstances,
yes.

/cah

---

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 23 Oct 2002 21:04:19 +0200 (CEST)

> aggregation and exploding the DFZ or making transport level changes..

I think http://www.muada.com/drafts/draft-van-beijnum-multi6-geo-aggr-00.txt
(name may change as I submit the draft) or "Geographical Aggregation to
Support Multihoming in IPv6" fits the bill. Sure, there are many reasons
not to like this, but so far I haven't heard any reasons why it wouldn't
_work_. As it provides relief almost immediately without any pain (that
comes later...), I can't see why this (or rather, an address allocation
mechanism supporting it) shouldn't be implemented, unless someone can
present _very_ convincing arguments why all of this is evil.

Iljitsch

---

From: Greg Maxwell <[email-masked]>
Date: Wed, 23 Oct 2002 15:19:20 -0400 (EDT)

> present _very_ convincing arguments why all of this is evil.

We're still in the game of having a cost set onto the outsiders.. sure,
now we've flattened the nonlinearity of price (hardware to contain a
million routes is more complex then a group of 100k routers with a similar
totally routing ability).

Is this really about the limits of top end scaling?
I always considered it to be about making routing more O(1)ish with
respect to multihomed networks you don't have a bussiness relationship
then O(n*mumble)..

The multinational geospacial distribution is a non-issue imho.. there is
too much clustering.. In places where multihoming load will matter.. thats
where the majority of the networks are....  I think it's reasonable to say
that if a router can handle X routes (i.e. all of the US, all of asia, or
all of europe) that asking it to handle 4X routes is not a big deal.

I don't believe that it is reasonable to ask providers to zone their
networks any smaller then continents.

---

From: Pekka Savola <[email-masked]>
Date: Wed, 23 Oct 2002 22:28:55 +0300 (EEST)

> Do I think it's rational to advertise that /40?  Given the circumstances,

Maybe, but is it rational to expect it to not to be filtered?  No.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 23 Oct 2002 21:29:56 +0200 (CEST)

> to multihoming caused DFZ inflation.

If nothing changes, this is exactly what will happen. This is also quite
common in v4 today: it is very close to impossible to get a small PI
block, so many multihomers take addresses from one ISP and announce them
over both. This provides a reasonable degree of multihoming if the ISP
they take addresses from accepts the announcement from the alternate
ISP. Then, if the multihomer's connection to the primary ISP goes down
and their more specific is filtered, the traffic ends up at the primary
ISP thanks to the aggregate, and the primary ISP sends it to the
secondary ISP who in turn delivers it to the multihomer. This doesn't
protect the multihomer from all failure modes for the primary ISP, but
it sure beats single homing.

> declare it already. The problem isn't just going to go away.

Personally, I feel this is a network issue so it should be dealt with at
the network layer. However, I'll take a good solution at any other layer
over a bad one at the network layer any day of the week.

A more compelling reason to do it at the network layer is that we have
many boxes that can do stuff at the network layer, while all the
transport layer decisions are (should be) made by the end hosts. See
Craig's problem with host solutions.

Also, keeping a single address for the transport layer (essentially
promoting this one to an identifier) and a possibly large set of
alternate addresses that are hidden from it (these would be locators)
keeps the transport protocols simple (= the same as they are now).

But in order to make it all work efficiently, there must be tight
integration between TCP and the multi-address engine, because TCP knows
when sessions start and end, and when there are (potential) reachability
problems.

Do you have a pointer to your transport layer ideas, BTW?

> The only thing worse then making a bad decision is wasting a lot of time

The ship has sailed on making a good decision fast, so let's focus on
making a good decision period.

Iljitsch

---

From: Greg Maxwell <[email-masked]>
Date: Wed, 23 Oct 2002 15:46:36 -0400 (EDT)

> it sure beats single homing.

Well perhaps this specific filtered, cross announce approach could be
combined with my transport layer ideas as a transitional method.

> over a bad one at the network layer any day of the week.

I'm not so sure it's a network layer issue..
The network moves packets to a network location.. when their is a failure
and multihoming comes into play, you are effectivly moving onto a NEW
network location..

> Craig's problem with host solutions.

[snip]

> Do you have a pointer to your transport layer ideas, BTW?

I made some long posts to this list a while back, search based on my email
address.  Ascii graphs and such..

I started working on a draft, but it seemed like the consensus was that
"transport layer solutions are outside of the scope of this working
group".. The irony is that everyone with anything to do with transport
protocols said IPv6 and multihoming arn't our bussiness.

> making a good decision period.

My concern is that we should make a decision that doesn't tie us in.. If
we decided on an DFZ exploding solution, there will be no going back..

I really don't believe that weak DFZ exploding solutions like I said
might work above (like, announce specifics and filter, and if you want
better then upgrade to transport layer multihoming) are sufficent because
of the current practice of flooding the DFZ with IPv4 (i.e. the filtering
won't happen/people will cry and get it removed when it first annoys
them.. which will work early in IPv6's production deployment becuase it
won't yet be many networks)..

Am I off? Can we really get away with saying 'well, the technoligy allows
you to flood the DFZ like in v4, but policy says you should play nice and
not do so' and actually have that happen?  or must we make a strong stand:
aggregate and solve your multihoming via this non-DFZ exploding method or
cope with being singly homed!

---

From: "Craig A. Huegen" <[email-masked]>
Date: Wed, 23 Oct 2002 14:52:46 -0500 (Central Daylight Time)

> Maybe, but is it rational to expect it to not to be filtered?  No.

Given today's possible multihoming solution set for large enterprises with
tens of thousands of segments, and

given the requirement for multi-homing as per the draft + my comments, and

given the rather small routing table currently used for research,

yes; it is rational for me to expect it not to be filtered.  This is
partially in line with the discussion a bit earlier about providers not
filtering all that much today because it isn't too great of a concern.

/cah

---

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 23 Oct 2002 22:42:23 +0200 (CEST)

> respect to multihomed networks you don't have a bussiness relationship

O(1)?  :-)

Well, maybe there is such a beast. When I studied software engineering I
was told there were no sorting algorithms that could do better than
O(n*log(n)). However, some digging produced radix sort, which was used
in the good old days of the Hollerith machines and scales O(n). So just
because people think it can't be done doesn't mean it can't be done.

> too much clustering.. In places where multihoming load will matter..

Why is that a bad thing?

> thats

Agree. That's why flat routing within a continent isn't worth the
hassle, while flat routing within a country/state/province or a metro
area (+ aggregating away everything on the outside) would be.

> networks any smaller then continents.

Is it reasonable to ask people to not multihome? Is it reasonable to ask
providers to buy bigger routers because the routing table explodes? If
we give people the tools, they can decide on how to use them. That's why
we need geographically aggregatable PI address space.

On the other hand, we could just throw the towel in the ring, accept a
large DFZ and start optimizing for that. 1 KB per prefix is way to much.
If we can get this down to 10 bytes on average (in theory it could be
one bit per path: reachable or unreachable) and double our memory and
slightly more than double our CPU power every two years, we're at 2^4 *
1024 / 10 * 114k = ~200M routes in 2010's equivalent of a 7200. Not too
shabby.

---

From: "Tony Hain" <[email-masked]>
Date: Wed, 23 Oct 2002 13:59:31 -0700

Iljitsch van Beijnum wrote:
> ... If we give people the tools, they can 
> decide on how to use them. That's why we need geographically 
> aggregatable PI address space.
> 

More correctly, that is why we need an aggregatable PI address space.
The fact that people generally put up abstraction barriers that align
with geography is orthogonal and an artifact of human nature. Since they
will tend to want to do that anyway, we can leverage that with geo-PI
allocations, as long as they fit the fundemental requirement of being
aggregatable. 

Tony

---

From: Greg Maxwell <[email-masked]>
Date: Wed, 23 Oct 2002 18:44:52 -0400 (EDT)

> allocations, as long as they fit the fundemental requirement of being

Contentential boundries are the only ones that make sence.. Any tighter
and there is too much movement and interconnection.

Contentential bounderies also make sence because they could be aligned
with the addressing authorties.

But.. They don't buy us much.. At best they would reduce the routing
table by a factor of 4 or so, probably less..

Heres the thing.. If a simple linear reduction like that will suffice,
then lets just flood the DFZ and let hardware improvments take care of it.
If we do not believe it will suffice, then we must have a solution that
does not increase the routing tables for networks who do not have a
direct relationship with the multihomed network.

Lets work on answering these questions: Is it approiate for network
operators to have to carry the burden created by other peoples
multihoming? and Can we expect routers handle the future growth of the
IPv6 internet without aggregation?

I thought that was already answered by the heavily aggregation centric
approach of IPv6. Perhaps not.. If we decide yes, they can, then simple..
lets just declare that the IPv4 way is the way to go.. If not, then we
should not waste time talking about aggregation break schemes.

My thought on scaling: I don't think that it's unreasonable to say that
simple enhanced versions of todays routing hardware/software could handle
a million routes.. But what happens when we want links that move many 10s
or hundreds of gigabits a second... and we're forced into using optical
packet-level switching..

In the stuff I offered up using pure transport-level multihoming, the
number of routes a network had would be a pure linear relationship to the
sum of (customers+peers+transit providers).  A unpeered lower tier
networks routing table would be close to 1:1 with the number of customers
they have.  I can easily see this making or breaking the possiblity of
'optical routing' until there are major advances in photonic computing
devices.

---

From: "Tony Hain" <[email-masked]>
Date: Wed, 23 Oct 2002 16:18:37 -0700

Greg Maxwell wrote:
> ...
> Contentential boundries are the only ones that make sence.. 
> Any tighter and there is too much movement and interconnection.
> 
> Contentential bounderies also make sence because they could 
> be aligned with the addressing authorties.
> 
> But.. They don't buy us much.. At best they would reduce the 
> routing table by a factor of 4 or so, probably less..
> 
> Heres the thing.. If a simple linear reduction like that will 
> suffice, then lets just flood the DFZ and let hardware 
> improvments take care of it. If we do not believe it will 
> suffice, then we must have a solution that does not increase 
> the routing tables for networks who do not have a direct 
> relationship with the multihomed network.
> 
> Lets work on answering these questions: Is it approiate for 
> network operators to have to carry the burden created by 
> other peoples multihoming? and Can we expect routers handle 
> the future growth of the IPv6 internet without aggregation?
> 
> I thought that was already answered by the heavily 
> aggregation centric approach of IPv6. Perhaps not.. If we 
> decide yes, they can, then simple.. lets just declare that 
> the IPv4 way is the way to go.. If not, then we should not 
> waste time talking about aggregation break schemes.

The current provider-aggregate approach is very focused on the needs of
the service provider at the expense of the needs of the enterprise.
While this does create a very scalable system, it also creates one that
doesn't solve the real problems (more correctly it only solves a subset
of them). I will agree that to a large degree the only thing that makes
sense today is contential aggregation, but I don't think that gets us
very far. It is a great first step, so we should take it, but we need a
plan that goes further. Those are the kinds of issues I was talking
about in my USE draft.

> 
> My thought on scaling: I don't think that it's unreasonable 
> to say that simple enhanced versions of todays routing 
> hardware/software could handle a million routes.. But what 
> happens when we want links that move many 10s or hundreds of 
> gigabits a second... and we're forced into using optical 
> packet-level switching..
> 
> In the stuff I offered up using pure transport-level 
> multihoming, the number of routes a network had would be a 
> pure linear relationship to the sum of 
> (customers+peers+transit providers).  A unpeered lower tier 
> networks routing table would be close to 1:1 with the number 
> of customers they have.  I can easily see this making or 
> breaking the possiblity of 'optical routing' until there are 
> major advances in photonic computing devices.

Changing the model to make the transport deal with the multi-homing is a
very long term problem. It is not that it is a particularly difficult
task, but that human nature plays here so it just takes a substantial
amount of time. When SCTP is well published, taught in every University
course as the proper way to create connections, and those who have been
taught to do so are finally in charge of software development projects,
then we might start to see a shift. Basically you have to promote/retire
out the entrenched development community that is under pressure to
deliver and will always fall back on what they were taught and know
works.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 24 Oct 2002 12:05:30 +0200 (CEST)

> and there is too much movement and interconnection.

That's too bad for the movee. If someone wants to move from Nova Scotia
to Costa Rica, they'll just have to renumber. I can live with that.

> table by a factor of 4 or so, probably less..

50% for the US because that's where most of the crap is today. But in
the long run it will be better as other regions start to do
more multihoming.

> then lets just flood the DFZ and let hardware improvments take care of it.

Three or so rounds of a factor 10 improvement should be able to take
care of it for a good long time. We hear "exponential growth" but of
course the growth will only be exponential for so long: in the end, it
will be an S curve. So a good solution would be to go for continental
aggregation in a couple of years, country/state/province aggregation in
five years and metropolitan aggregation in ten years or so. But then we
have to start assigning addresses based on metro *now* if we want to
avoid renumbering later.

> direct relationship with the multihomed network.

The only way you need to see all routes is if you are a "tier 1" ISP and
don't pay anyone for transit. If having all these routes in your tables
is too expensive you can simply pay someone for transit and use a
default. It's not like we're forcing innocent bystanders to upgrade
their routers, only those who do routing as their core business.

> multihoming?

Yes. The alternative is becoming telcos and spend a cent a minute to
charge someone for a service that costs only a tenth of a cent to
provide in the first place. All ISPs share the costs of multihoming, but
they also all have multihomed customers so who cares.

> and Can we expect routers handle the future growth of the

Maybe it will turn out that they can, but counting on it is too
dangerous.

> or hundreds of gigabits a second... and we're forced into using optical

Switching isn't the problem as routing table lookups scale at O(log(n)).
However, processing the updates scales at O(n*log(n)), assuming longer
prefixes are as stable as short ones, which they aren't.

So routing table lookups should use about 17% more processing for a
factor 8 increase (~1M routes) while processing routing updates requires
9.4 times more CPU power. On the other hand, routing table lookups have
timing constraints (at least if you want to forward at line rate) while
routing updates can be delayed.

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 25 Oct 2002 00:57:37 +0859 ()

Iljitsch;

> because people think it can't be done doesn't mean it can't be done.

Radix sort uses address arithmetic complexity of which is silently
assumed to be O(1).

However, speed of real memory is O(log(size of the memory)). 

That's one of the reason why reduction of DFZ is important for
the high speed Internet with quick routing table look up.

							Masataka Ohta

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 24 Oct 2002 20:31:17 +0200 (CEST)

> the high speed Internet with quick routing table look up.

The IRTF doesn't agree:

http://www.ietf.org/internet-drafts/draft-irtf-routing-reqs-groupa-00.txt

4.1 Forwarding Table Optimization

        We believe that it is not necessary for the architecture to
        minimize the size of the forwarding tables (FIBS).  Current
        memory sizes, speeds, and prices, along with processor and ASIC
        capabilities allow forwarding tables to be very large, O(E6),
        and fast (100M lookups/second) tables to be built with little
        difficulty.

---

From: "Robert J. Rockell" <[email-masked]>
Date: Thu, 24 Oct 2002 15:27:42 -0400 (EDT)

Please allow me to possibly mis-use other portions of this draft.  If you
(all) will allow me to counterpoint based on the same draft:

[...]
       1. The computational power and memory sizes required to execute
           the routing protocol software and to contain the tables must
           be less than the growth in hardware capabilities described
           by Moore's Law, which has hardware capabilities doubling
           every 18 months or so.  Other observations indicate that
           memory sizes double every 2 years or so.

3. The speeds of high-speed RAMS (SRAMs, used for caches and
           the like) are growing, though slowly.  Because of their use
           in caches and other very specific applications, these RAMs
           tend to be small, a few megabits, and the size of these RAMs
           is not increasing very rapidly.

           On the other hand, the speed of "large" memories (DRAMs) is
           increasing even slower than that for the high speed RAMS.
           This is because the development of these RAMs is driven by
           the PC market, where size is very important, and low speed
           can be made up for by better caches.

Not necessarily affecting "geo for now", but not proven either way.
Definitely a hint against CIDR-izing IPv6.

3.5:
[...]
        Some have proposed that a geographic addressing scheme be used,
        requiring exchange points to be situated within each geographic
        'region'.  There are many reasons why we believe this to be a
        bad approach, but those arguments are irrelevant.  The main
        issue is that the routing architecture should not presume a
        specific network structure.

I didn't write it. Send flames to IRTF :)

Another useful quote that is not necessarily germane to this thread, but
indeed a consideration is:

   3.17    Simplicity

        The architecture MUST be simple enough so that Radia Perlman
        can explain all the important concepts in less than an hour.

        The requirement is that the routing architecture be kept as
        simple as possible.  This requires careful evaluation of
        possible features and functions with a merciless weeding out of
        those that "might be nice".

Possibly germane to some proposals:

    3.20     Stand-alone

        The routing architecture and protocols MUST NOT rely on other
        components of the Internet (such as DNS) for their correct
        operation.  Routing is the fundamental process by which data [...]

so 8+8 is probably out too...

So we are back to square one, based on this document...  ?

Thanks
Rob Rockell
SprintLink
(+1) 703-689-6322
-----------------------------------------------------------------------

On Thu, 24 Oct 2002, Iljitsch van Beijnum wrote:

->On Fri, 25 Oct 2002, Masataka Ohta wrote:
->
->> That's one of the reason why reduction of DFZ is important for
->> the high speed Internet with quick routing table look up.
->
->The IRTF doesn't agree:
->
->http://www.ietf.org/internet-drafts/draft-irtf-routing-reqs-groupa-00.txt
->
->4.1 Forwarding Table Optimization
->
->        We believe that it is not necessary for the architecture to
->        minimize the size of the forwarding tables (FIBS).  Current
->        memory sizes, speeds, and prices, along with processor and ASIC
->        capabilities allow forwarding tables to be very large, O(E6),
->        and fast (100M lookups/second) tables to be built with little
->        difficulty.
->
->

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 25 Oct 2002 08:45:05 +0859 ()

Rob Rockell;

> so 8+8 is probably out too...

Could you elaborate?

Maybe, GSE uses DNS internally in the network.

But, GSE is a poor example of 8+8 and hopeless.

8+8 with end to end multihoming resolves DNS purely inside end systems,
of course.

							Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 25 Oct 2002 09:15:13 +0859 ()

Iljitsch;

>         and fast (100M lookups/second) tables to be built with little

1M entry with 100M lookup per second may be possible someday, if the
1M entry memory and core logic of routers be put into a single chip.

However, the statement is politically distorted.

The reality is that, if we don't solve multihoming issue, 1M is small.

Moverover, 100M lookups/second is slow for terabit networking.

If we use multiple chips, we must accept that inter-chip communication
has large overhead, which means it is slow and costs a lot.

High performance routing is still possible with parallelism, which
means a lot of wiring and, thus, a lot more cost.

							Masataka Ohta