Subject: [RRG] Geographic aggregation-based routing

From: "William Herrin" <[email-masked]>
Date: Thu, 10 Jul 2008 10:46:32 -0400

On Thu, Jul 10, 2008 at 9:04 AM,  <[email-masked]> wrote:
> But geographical labelling does, and, it does NOT need any distribution
> mechanism.

Heiner,

As I'm pretty sure most everyone else on the list has figured out,
routing based on geographic aggregation results in routing policy
violations in any sufficiently complex internetwork.

Consider the configuration of 8 nodes at:
http://bill.herrin.us/network/geoag.gif

The black lines are network links. The two blue circles represent
geographically proximate areas, that is every node in the same circle
has the same geographic label. The green arrows indicate who pays who
for transit service. Note the absence of an arrow between C and G, and
between B and F: those are unpaid reciprocal peering.

With both BGP and geographical routing, this network is fully
connected. There are announced routing paths leading from each node to
every other node.

With BGP, packets from D to F would travel:

D-C(d pays)-G(e pays)-F(e pays)-E

With geographic routing, they travel:

D-C(d pays)-B(oops!)-F(e pays)-E.

This breaks a critically important part of routing policy! At every
router and on every link, the source, the destination or both must pay
for that packet to be there.

When are you gonna figure this out and move on from geographic
routing? There are a couple  topological aggregation variants which
still hold some possibility but geographic isn't one of them.

Regards,
Bill Herrin

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

--
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: Thu, 10 Jul 2008 11:38:04 EDT

In einer eMail vom 10.07.2008 16:48:15 Westeuropäische Normalzeit schreibt  
[email-masked]:

> But  geographical labelling does, and, it does NOT need any distribution

I should have added already here: I am not in favor of a BGP-like Routing  
Table that contains geographical prefixes !!! I am not favoring collecting  
routes, instead computing/distributing/collecting topological links of different  
zooming levels. And links can be marked. E.g. "Not for transit". Will  say, 
your example doesn't manifest any problem.
I admit, I still have some problems by going for the "ultimate" which of  
course is the more hampered by the incremental deployability issue. But your  
example is not one of them.
 
If you look at the graph on _www.hummel-research.de_ 
(http://www.hummel-research.de)  you can see  many, many routes to the red destination node which 
caters for multipath,  traffic balancing, QoS/Policy-routing... Why not also 
inter-domain-wise ?! 
By knowing the topology you can do better policy-TE than without.  Sure, 
after you have learnt shortest path, first. And the elimination of the  
scalability problem is just a side-effect !
 
IMO I do propagate a different school of thought. It will also enable  
different solutions with respect to rigidity versus compromises. In the past I  have 
seen that the PNNI-architecture was given about 5 years of efforts,  although 
(as I know now) it defeated itself: the hierarchical nodes became  bigger and 
bigger, hence required a node-internal topology :-(. But if you  look at 
GOOGLE MAP examples: that looks marvelous and does inspire to do  topology 
aggregation or, if you want, to compose topologies of mixed zooming  levels. 
 
IMO, research is about trying.
 
Heiner

 

Heiner,

Regards,
Bill Herrin

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Jul 2008 08:19:59 +1200

> violations in any sufficiently complex internetwork.

Oh, it'll work just fine if you deploy a municipally-funded,
neutral and zero-fee IXP in every population centre. Admittedly,
that changes the entire economic structure of the network...

    Brian

---

From: [email-masked]
Date: Thu, 10 Jul 2008 17:47:20 EDT

Brian

Thank you. But this is not what I have in mind. Because it would be  too much 
to acquire the topological view of the net of all ISPs'  OSPF-networks, this 
view must be reduced, such that each current router is  surrounded by strict 
links in the near neighborhood and by loose and looser  links the more remote 
they are. Geographical information will hereby be helpful,  but the nodes and 
links of the resultingly  viewed topology could be  bestowed with whichever 
attributes wrt  QoS/SLA.
 
Brian, correct me if I am wrong: DiffServ'axiom: I (the current router) do  
not see the network outside. I try to do my contribution for differentiated  
forwarding service based on my router-local experiences.Right?
Whereas, with topology aggregation, the router can see the entire  
ISPs-network and base on it the own contributions. It will see many paths to the  
destination. It will  precisely see that network part which would forward  packets 
via it. There is much more and much better TE possible. The router could  do 
better things than wasting the time with unnecessary UPDATE churn.
 
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Fri, 11 Jul 2008 00:19:18 -0400

On Thu, Jul 10, 2008 at 11:38 AM,  <[email-masked]> wrote:
> Will say, your example doesn't manifest any problem.

Based on: http://bill.herrin.us/network/geoag.gif

The path I claim your algorithm picks for packets from D to E is
wrong. It subjects an unaffiliated third-party to an unbounded and
unrecoverable expense. The only valid path from D to E is D-C-G-F-E.
If your algorithm might pick some other path, your algorithm is
broken. Period.

This is your "put up or shut up" moment. If you think your algorithm
picks D-C-G-F-E to get from D to E -AND- picks H-G-C-B-A to get from H
to A (the only valid paths for those two communications), show us how
nodes C and G over in "right area" make those polar-opposite path
selections based on the aggregated knowledge that destinations A and E
both reside in "left area."

Or shut up about geographical routing. Give it up for bad and put your
mind to task on the next possibility. Please.

-Bill Herrin

---

From: "William Herrin" <[email-masked]>
Date: Fri, 11 Jul 2008 00:19:27 -0400

On Thu, Jul 10, 2008 at 4:19 PM, Brian E Carpenter
<[email-masked]> wrote:
> Oh, [geographic routing will] work just fine if you deploy a municipally-funded,

Brian,

As it turns out, even that wouldn't be good enough. Take a look at the
example I gave. You'd also need to single-source all the links between
the IXPs so that regardless of which links the packet travels between
them, you pay the same entity.

Regards,
Bill

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Jul 2008 17:58:14 +1200

> them, you pay the same entity.

That makes sense, unless they are all funded pro bono. Basically, it
would only work in a non-competitive economy. (What does that remind
me of? Oh yes, the telephone system pre-liberalisation.)

   Brian

---

From: [email-masked]
Date: Fri, 11 Jul 2008 02:32:34 EDT

In einer eMail vom 11.07.2008 06:19:20 Westeuropäische Normalzeit schreibt  
[email-masked]:

Sorry Bill, but your proof is broken.You may consider your black lines as  
one or eventually two directed arrows (2 if opposite) and compute a path being a 
 sequence of arrows all bound to the same endpoint.
 
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Fri, 11 Jul 2008 14:48:08 -0400

On Fri, Jul 11, 2008 at 2:32 AM,  <[email-masked]> wrote:
> one or eventually two directed arrows (2 if opposite) and compute a path
> being a sequence of arrows all bound to the same endpoint.

No Heiner, you can't. The black lines describe only interconnection.
The green arrows describe permission. Regardless of the actual
interconnection, you may only choose a path for which you have
permission. Honoring permission is core to the problem definition, one
of the criteria any serious proposal MUST meet.

Think of it like this: If you want to go from London to Mexico City,
you can fly to Canada and then drive southwest, but ONLY if you have a
passport, both US and Canadian visas valid for the specific timeframe
of your travel and an international driver's license. If you lack the
visas or the license, or if you're on the TSA watch list, you'll have
to fly around the US to Mexico. Although the US is geographically in
between the two and other folks making similar trips are permitted to
enter and use US roads, you are not.

I have invited you to describe your algorithm's actual path selection
choices in a concrete routing scenario. All you have to do is type two
sets of five letters and then explain how you picked them. Instead,
you waved your hands about and said "no, no, that's not right."

I invite you one final time: demonstrate your algorithm's behavior in
the described scenario. Show that it picks paths consistent with the
given permission without disaggregating the geographic knowledge. Put
up or shut up.

-Bill Herrin

---

From: [email-masked]
Date: Fri, 11 Jul 2008 19:05:49 EDT

Besides, It would be easier if you had indicated in which direction  packets 
may be sent for any black line. 
 
My understanding of what you want is this: forwarding from C to B is  not 
allowed. Hence the packet from D to E must go like  this: D--->C-->G-->F-->E    
and NOT  D-->C-->B-->F-->E.    
My saying is: That can be respected. But this is almost normal  Dijkstra.Only 
the following enhancements are required: Build a graph, which  consists of 
these nodes A,..H and of directed arrows. Between any two nodes  according to 
the black lines there are two  inversely directed  arrows.Except  between B and 
C. Here there is only one arrow which is from  B to C, but not from C to B.
Node C runs Dijkstra with itself being the root, however modified such that  
selecting a predecessor node for any node presumes that  there is an arrow  
from that predecessor node to that "any"-node. So , while running Dijkstra, C  
won't even see that B is a neighbor/candidate.Hence the resulting shortest path 
 tree will not include "from C to B" but only "from C to G".
 
But this is normal Dijkstra enhanced with constrains.
 
You might want to make the checking even more difficult: It is not allowed  
to forward from C to B unless B is the termination point. Even that can be 
taken  into account (btw, I won't call this ROUTING BEYOND DIJKSTRA; it is just  
constraint-based routing).
 
Compare inter- with intra- domain. You can't say that distance  
vector-technology enables  better TE than Dijkstra.
 
Heiner

 
In einer eMail vom 11.07.2008 20:50:57 Westeuropäische Normalzeit schreibt  
[email-masked]:

-Bill  Herrin

---

From: "William Herrin" <[email-masked]>
Date: Fri, 11 Jul 2008 20:56:29 -0400

On Fri, Jul 11, 2008 at 7:05 PM,  <[email-masked]> wrote:
> allowed. Hence the packet from D to E must go like
> this: D--->C-->G-->F-->E    and NOT D-->C-->B-->F-->E.
> the black lines there are two  inversely directed arrows.Except  between B
> and C. Here there is only one arrow which is from B to C, but not from C to
> B.
> from that predecessor node to that "any"-node. So , while running Dijkstra,
> C won't even see that B is a neighbor/candidate.Hence the resulting shortest
> path tree will not include "from C to B" but only "from C to G".

Okay. I added what I think you just described in red at
http://bill.herrin.us/network/geoag-h1.gif. Is that correct?

This means that the forwarding information base at node G looks like:

destination {left area}: send to F
destination C: send to C
destination H: send to H
destination D: send to C

And the FIB at node C looks like:

destination {left area}: send to G
destination G: send to G
destination D: send to D
destination H: send to G

Is that correct?

So, D--->C-->G-->F-->E happens for packets from D to E because when
the packet is at C, C understands that all of {left area} is available
via G and when the packet is at G, G understands that all of {left
area} is available via F. Thus geographic aggregation cut the FIB
almost in half since C and G only have to keep track of {left area}
instead of keeping track of A, B. F and E.

Still correct?

-Bill

---

From: [email-masked]
Date: Sat, 12 Jul 2008 03:13:10 EDT

In einer eMail vom 12.07.2008 02:57:44 Westeuropäische Normalzeit schreibt  
[email-masked]:

Yes.

Is  that correct?

Yes.

So,  D--->C-->G-->F-->E happens for packets from D to E because  when
the packet is at C, C understands that all of {left area} is  available
via G and when the packet is at G, G understands that all of  {left
area} is available via F. 
Still correct.

Thus  geographic aggregation cut the FIB
almost in half since C and G only have  to keep track of {left area}
instead of keeping track of A, B. F and  E.

Still correct?
Yes, if you want, but I prefer to say No: I do not pursue to have a FIB of  
the current classic design. My goal is to fill a table from which by means  of 
a single indexed/offset element lookup the next hop can be retrieved.
 
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Sat, 12 Jul 2008 12:15:09 -0400

>> destination {left area}: send to G

Okay, good. Now, based on the graph you just agreed to and the two FIB
tables you just agreed to, route a packet from node H to node A. The
path I compute is H->G->F->B->A. Do you get that path as well?

-Bill

---

From: [email-masked]
Date: Sat, 12 Jul 2008 12:31:26 EDT

In einer eMail vom 12.07.2008 18:16:25 Westeuropäische Normalzeit schreibt  
[email-masked]:

Sure. Each router computes a Dijkstra shortest path tree to all the others.  
Hereby, whenever a predecessor is determined (which either is the computing  
router or which at least is closer to the computing router) for some node, the  
condition must be met, that there is an arrow from that predecessor  to  that 
"some node".
So no matter who originates the packet or who receives the packet, it will  
forward it in compliance with such policy restrictions.
 
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Sat, 12 Jul 2008 15:02:34 -0400

On Sat, Jul 12, 2008 at 12:31 PM,  <[email-masked]> wrote:
>>> http://bill.herrin.us/network/geoag-h1.gif.
>>
> Sure.

There is your error. You violated the permission constraint: F is not
a permitted node in the transit path between H and A. There is no
trail of green arrows from H to F. There is also no trail of green
arrows from A to F. Hence F is not permitted for a packet whose
addresses are H and A.

There is one permitted path from H to A:  H->G->C->B->A. Each node in
that chain has a trail of green arrows leading to it from either H or
A. This designates permission.

Would you like to redraw your red arrows? Can you think of a
configuration of red arrows where you get *both* H->G->C->B->A *and*
D->C->G->F->E ?

-Bill

---

From: [email-masked]
Date: Sat, 12 Jul 2008 15:33:00 EDT

In einer eMail vom 12.07.2008 21:02:46 Westeuropäische Normalzeit schreibt  
[email-masked]:

There is your error. You violated  the permission constraint: F is not
a permitted node in the transit path  between H and A.
You added, as I asked for, the red arrows which indicate in which direction  
forwarding is allowed.
>From G to F forwarding is allowed. Also from F to B. So why can't packets  
from H to A go along
H-->G-->F-->B-->A ? 
I do not see any error.
 
Heiner

There is  no

-Bill

---

From: [email-masked]
Date: Sat, 12 Jul 2008 15:40:26 EDT

In einer eMail vom 12.07.2008 21:04:28 Westeuropäische Normalzeit schreibt  
[email-masked]:

Well, it requires a red arrow not only from B to C but also from C to  B.
But then all black lines are replaced by pairs of oppositely directed  arrows.
So we have no restricted situation anymore. 
 
Heiner, shruging my shoulders

---

From: [email-masked]
Date: Sun, 13 Jul 2008 10:38:19 EDT

The emails of this thread have been about the shortest path  computation in a 
network where any subset of links are allowed to be used only  in one 
particular direction.
I wonder whether the described solution (replacing links by either two or  
only one arrow,assigning any predecessor only if there is a fitting arrow from  
there) is or is not common place?
 
It has always been useful for QoS/SLA/available bandwidth  sensitive/etc  
routing inside any OSPF network.
 
Can either OSPF-experts or edu-folks comment on my question?

Myself, I know about this trick since the early days of PNNI where there  
were uni-directional uplinks (i.e.without inversely  directed down-links).
 
Heiner

---

From: Robert Bonomi <[email-masked]>
Date: Sun, 13 Jul 2008 11:49:17 -0500 (CDT)

> From [email-masked]  Sun Jul 13 09:45:46 2008
> From: [email-masked]
> Date: Sun, 13 Jul 2008 10:38:19 EDT
> Subject: Re: [RRG] Geographic aggregation-based routing
> To: [email-masked]
> CC: [email-masked]
>
>
>

Back in my college days (long! ago :), in civil engineering it was universal
to represent *all* traffic segments as _one-way_ linkages for 'most desirable' 
path determination.

For, among other reasons, the fact that desirability of using certain segments 
was sensitive to instantaneous load levels on that segment; also load levels/
delays in one direction are -not- necessarily indicative of behavior and/or
desirability of the reverse path.

In the real world there _are_  non-trivial numbers of 'corner' cases -- one-
way paths, assymetric paths, etc. -- that one must be prepared to deal with.

The use of unidirectional graphing elements makes it much easier to deal with
those 'corner' cases.

Unidirectional elements -- in a multiple-source, multiple-destination, 
network -- also allow for better handling of assymetric load levels among 
particular station 'pairs' -- i.e., A->B is much higher/lower than B->A,
by whatever metric is employed.

And, of course, when networks have multiple points of inter-connection, the
'preference' of which inter-connect point ot use may well be different, 
depending on "where, on which network" one is starting from.

Many years ago, in metro Chicago,  I had a wonderful real-world example
of this.  Two systems, less than 3 miles apart, on networks without any
direct peering, or regional inter-connect.  'Preferred' path from A to
B was via MAE-EAST, but the preferred path from B to A was via MAE-WEST.
'traceroute' clearly identified where the preference changed -- one could
clearly see the discontinuity in RTT when packets reached the node where
the 'return' preference changed.

---

From: "William Herrin" <[email-masked]>
Date: Sun, 13 Jul 2008 16:53:26 -0400

> Heiner, shruging my shoulders

Precisely. There is no configuration of red arrows you can draw that
correctly respects the permission constraint described by the green
arrows. Nor can we simply do away with the green arrows; they describe
the technical portion of the Internet's core economic model.

Hence we have found a contradiction: a valid network configuration for
which your algorithm can't meet the constraints. If this was math,
we'd say it was disproven. Since it's engineering, we say something
along the lines of: disqualified for technical error.

It turns out that -all- geographic aggregation strategies suffer from
a variant of this problem. That's why none of the rest of us are
interested in talking about geographic aggregation.

Your insights into other approaches, however, continue to be welcome.

> [the described approach] has always been useful for QoS/SLA/available bandwidth
> sensitive/etc  routing inside any OSPF network.

I used OSPF for my interior routing back in my ISP days. I have the
following two answers to that question:

1. OSPF is intradomain. Because all links are owned by the same
organization, permission is not a hard constraint the way it is in
interdomain routing.

2. I never got more than a trivial amount of aggregation with OSPF.
I'm not sure if the fault was OSPF or my configuration, but it didn't
offer up aggregation easily.

Regards,
Bill Herrin

---

From: [email-masked]
Date: Sun, 13 Jul 2008 18:31:18 EDT

I still do not understand what you try to teach me.
At first, this has nothing to do with geographical data. It would be the  
same task inside some OSPF-network.
 
The way I described how to use Dijkstra enables a Dijkstra shortest path  
tree which respects constraints like uni-directional forwarding. E.g. from node  
N1 to N2 but not from N2 to N1. And even conditioned: .. but not from N2 to N1 
 unless N1 is the destination node.

I didn't ask for adding red arrows but for expressing the task differently,  
by telling me which black line may be passed in which direction(s). If every  
node not only sees the topology of black lines but also the attributes per  
line (allowed forwarding direction(s)  ), then I don't see why my  
Dijkstra-based computation should produce incorrect paths.
 
Heiner
 
In einer eMail vom 13.07.2008 22:53:42 Westeuropäische Normalzeit schreibt  
[email-masked]:

Regards,
Bill Herrin

---

From: [email-masked]
Date: Mon, 14 Jul 2008 10:58:58 EDT

In einer eMail vom 13.07.2008 18:50:57 Westeuropäische Normalzeit schreibt  
[email-masked]:

Thanks for your response.
Certainly, the computation of a different path from B to A than from A to B  
may not only be enforced by some link which is only usable in one  direction, 
but as well by the  per link and per direction assigned  weight values.
In summary, there are many good reasons for replacing a link by either  one 
or two directed arrows.
 
Heiner

---

From: "William Herrin" <[email-masked]>
Date: Mon, 14 Jul 2008 11:17:26 -0400

On Sun, Jul 13, 2008 at 6:31 PM,  <[email-masked]> wrote:
> tree which respects constraints like uni-directional forwarding. E.g. from
> node N1 to N2 but not from N2 to N1. And even conditioned: .. but not from
> N2 to N1 unless N1 is the destination node.

Precisely. It fails to respect one of the required system constraints:
that of transit permission.

> I still do not understand what you try to teach me.

Your algorithm does not correctly enforce the permission constraint.
Thus it is unusable in an interdomain setting where the permission
constraint is a requirement.

-Bill Herrin

---

From: [email-masked]
Date: Mon, 14 Jul 2008 11:29:53 EDT

In einer eMail vom 14.07.2008 17:17:46 Westeuropäische Normalzeit schreibt  
[email-masked]:

Of course it would reflect this requirement: It reflects the  
direction-specific attribute per link.
Hence yields the appropriate path.
I am aware that current BGP works based on distance vector, but current BGP  
is not the clean-slate solution either.

Heiner

---

From: "William Herrin" <[email-masked]>
Date: Mon, 14 Jul 2008 12:18:49 -0400

> direction-specific attribute per link.

Your algorithm failed to pick the permitted paths when we computed the
example over the weekend. Would you like to change something in the
computation so that your algorithm picks permitted paths for both H to
A and D to E?

Remember: permission is described by the green arrows in the diagram.
A packet is permitted to transit a node IF AND ONLY IF there is a
trail of green arrows to that node from either the packet's source
node or the packet's destination node.

Your error may be that you don't comprehend Internet routing's
permission model. It's not a BGP thing, it's an economic thing. Quite
simply, each green arrow indicates the payment of money or some other
consideration in exchange for "Internet service." The arrow starts
with the node making payment and points to the node which is paid.

Until you understand the economic model you must engineer for, you
will continue to fail.

Regards,
Bill Herrin

---

From: [email-masked]
Date: Wed, 16 Jul 2008 03:38:30 EDT

Bill,
I think we should summon up this thread by one more email from either side.  
I'll hereby start so that you have the final word:-)
 
There are many possible and well working business models. They may not  be  
identical if based on the green arrows compared with if based on the  red 
arrows. Postal service providers know how to make business with each other,  and so 
do telephone service providers, although they  neither use BGP nor  OSPF.
And sometimes business models change: Least Cost Routing (with multiple  
distance zones and time zones) is more or less replaced by flat rate billing  
(which is so unfair but liked by every customer - and probably also by the  
service providers because it simplifies proper billing).
Will say: This business model issue is not a killer argument at all and we  
shouldn't bother about while searching for a (clean-slate) solution.
 
Heiner

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 16 Jul 2008 17:24:51 +0200

> interested in talking about geographic aggregation.

You're oversimplifying.

If you split the world into regions and then have interconnections  
between different networks in some regions but not in all of them, you  
can't solve routing if you first send packets to the target region and  
then try to hand them over to the target network.

(Note that you can easily reverse this problem: today we route to the  
target network and then to the target region. This works with  
incomplete regional interconnection between networks, but it fails if  
different parts of a single network become partitioned. Hence we spend  
a lot of money and effort to make sure that doesn't happen.)

The solution is rather than to impose 100% geographical aggregation,  
just apply the aggregation when the more specific and the aggregate  
align. If they don't, keep the more specific. This way, we get to  
benefit from the regionality that is clearly present in the network,  
especially outside huge countries like the US and (presumably) China,  
while at the same time not imposing any new requirements on protocols  
or business models.

However, we DO need to start giving out addresses in a geographically  
aggregatable way, rather than in pseudo-random fashion, the way things  
happen today. There is no guarantee this will help, but at least there  
is the possibility of future geographic aggregation, while if this  
doesn't materialize we're no worse of than today. The way things are  
now we KNOW there is no way to aggregate PI prefixes.

---

From: "William Herrin" <[email-masked]>
Date: Wed, 16 Jul 2008 11:41:44 -0400

On Wed, Jul 16, 2008 at 11:24 AM, Iljitsch van Beijnum
<[email-masked]> wrote:
> The solution is rather than to impose 100% geographical aggregation, just
> apply the aggregation when the more specific and the aggregate align. If
> they don't, keep the more specific. This way, we get to benefit from the
> regionality that is clearly present in the network, especially outside huge
> countries like the US and (presumably) China, while at the same time not
> imposing any new requirements on protocols or business models.
>
> happen today. There is no guarantee this will help, but at least there is
> the possibility of future geographic aggregation, while if this doesn't
> materialize we're no worse of than today. The way things are now we KNOW
> there is no way to aggregate PI prefixes.

Iljitsch ,

You more or less re-propose provider-aggregatable addressing with
geographic registries, an approach which has been in place for better
than a decade now and has already achieved the close to the maximum
aggregation it can.

I personally think there's still a little room for improvement in the
FIB calculation. It might be possible to reduce the FIB by selecting
the most-common exit in the RIB for each /8 and then only installing
the more specifics in the FIB for the prefixes that use a different
exit. But the closer you get to the core, the less improvement that
offers, something you should be able to confirm or refute with RIB
snapshots from various operators if you care to try it.

Regards,
Bill Herrin

---

From: "William Herrin" <[email-masked]>
Date: Wed, 16 Jul 2008 11:42:12 -0400

> I'll hereby start so that you have the final word:-)

Fair enough.

> There are many possible and well working business models. [...] And
> sometimes business models change [...] This business model issue is
> not a killer argument at all and we shouldn't bother about while
> searching for a (clean-slate) solution.

Beyond the basic question for a routing protocol (does it actually
route packets from the source to the destination?) the issue of most
critical importance is the manner in which it supports the economics
which drive the Internet.

The "desired" economic model for the Internet, the one that operators
have been pushing and enhancing since the dawn of the commercial
Internet, can be summarized as follows:

1. Maximize the ability to directly bill customers for resource consumption.
2. Maximize the resources available to sell.
3. Minimize the count and cost of overhead resources that aren't
attributable to specific customers.

We're here on RRG today because BGP falls short of this model in one
important respect: The routing table itself is very expensive to
maintain and operate yet those who consume it can't be directly billed
for their use.

For any of our solutions to proceed to implementation, we have to come
closer to the desired economic model. We have to come enough closer
than BGP does to merit the cost of change.

Any solutions which stray further from the desired economic model than
BGP does are simply non-starters. This includes Geoaggregation.

Regards,
Bill Herrin

---

From: [email-masked]
Date: Wed, 16 Jul 2008 14:47:05 EDT

In einer eMail vom 16.07.2008 17:25:07 Westeuropäische Normalzeit schreibt  
[email-masked]:

(Note that you can easily reverse this problem: today we route to  the  
target network and then to the target region. This works  with  
incomplete regional interconnection between networks, but it  fails if  
different parts of a single network become partitioned.  Hence we spend  
a lot of money and effort to make sure that doesn't  happen.)
I must admit: Partitioning is an important and also  interesting problem for 
which I have no worked out solution yet. But I am  glad about this, because it 
guarantees to have some fun during a project I  am still hoping for. It will 
certainly be inspired by the marvelous Google map  zooms.

However, we DO  need to start giving out addresses in a geographically  
aggregatable  way, rather than in pseudo-random fashion, the way things  
happen  today. 
You are absolutely right ! At least an additional such part of  the address.
 
Heiner

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 17 Jul 2008 12:16:21 +0200

> than a decade now and has already achieved the close to the maximum

You mean that PA has already gone as far as it can go and geoPI == PA?

Not so. The big difference is that with geoPI you get to switch ISPs  
without changing your address. (Including connecting to more than one  
ISP at the same time.) This is exactly the thing that PA won't give you.

> snapshots from various operators if you care to try it.

That's because today, there is little rhyme or reason to the  
distribution of prefixes within each of those /8s. However, if you  
know that everything in 145.0.0.0/8 is in the Netherlands, there is  
really no reason to keep all those more specifics in your routers in  
Seattle, as interconnection with Dutch networks typically happens in  
Amsterdam with backups in England and Germany, or at the very least in  
the US north east, where all the transatlantic cables land.

Since there is no cost (except for updating some registry machinery)  
for doing geoPI rather than straight PI for IPv6, there's really no  
reason NOT to do it.

---

From: "William Herrin" <[email-masked]>
Date: Thu, 17 Jul 2008 10:41:47 -0400

On Thu, Jul 17, 2008 at 6:16 AM, Iljitsch van Beijnum
<[email-masked]> wrote:
> That's because today, there is little rhyme or reason to the distribution of
> prefixes within each of those /8s. However, if you know that everything in
> 145.0.0.0/8 is in the Netherlands, there is really no reason to keep all
> those more specifics in your routers in Seattle, as interconnection with
> Dutch networks typically happens in Amsterdam with backups in England and
> Germany, or at the very least in the US north east, where all the
> transatlantic cables land.

Iljitsch,

Sounds like a straightforward research project. Go get RIB snapshots
from core routers at various tier-1's. Compute the maximum aggregation
you could get in the RIB to FIB computation with the prefixes as they
are now. Then match whois records to the prefixes and reallocate them
by a manageable geography, "country" let's say. Simulate the
incremental nature of address assignment with a requirement that the
prefixes within a country be randomly distributed within that
country's block, taking no hints from general topography. Then remap
the reallocated prefixes back to the originals in those RIB snapshots
and see what aggregation you achieve in the FIB to RIB computation.

I look forward to reading your results.

*Note* that while you can potentially drop the routes in the FIB, you
can't drop them in the RIB. Your downstream customer could reasonably
have an alternate set of routes where some of your more specifics are
optimal and some aren't. Even if two adjacent routes in your router
are identical in every respect, his may not be. If you drop the routes
from the RIB, it impairs his ability to make good routing decisions.

Since the FIB costs *a lot* more than the RIB, reducing just the FIB
is still an interesting endeavor.

Regards,
Bill Herrin

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 17 Jul 2008 16:59:29 +0200

On 17 jul 2008, at 16:41, William Herrin wrote:

> Sounds like a straightforward research project.

I don't see how evaluating the savings in the current situation is  
very interesting. We know our routers can handle the current situation.

> from the RIB, it impairs his ability to make good routing decisions.

Sure. But you can handle this with a route server rather than have  
EVERY router have all prefixes.

And when geographic aggregation gets off the ground, multihomed end- 
users will probably stop being interested in geoPI more specifics, but  
rather, get geo aggregates from their ISPs.

You do need to propagate all your geoPI customer prefixes to other  
networks in all locations to avoid problems, though. For the largest  
networks in the world even that number may be significant...

Iljitsch