Subject: [RRG] Topology that follows addressing

From: [email-masked]
Date: Fri, 9 Nov 2007 06:53:55 EST

Let me address just that  particular NIRA-objective which this mailinglist’s 
discussion is all about, its  design and yes, also soon, the hereby needed 
algorithmic technology as to  compute consistently viewed hierarchical 
topologies. For that computation only a  minor enhancement of the Dijkstra is required, 
but not the entire All  Links Spanning Tree (ALST). But step by  step. Prior 
contributing this small though important puzzle as to show the HOW,  I think it’
s appropriate to show at first WHAT shall be accomplished as well as  WHY 
this protocol development will get us out of the BGP-trap or better said  
aggregation-trap (an imaginary world-wide OSPF would have the same  problems). 
WHAT:The goal is that each router  aquires a hierarchical network view, where 
the current router is surrounded by a  network of strict links, which is 
surrounded by a network of looser  … and looser links. For proper understand  WHY 
so, let me give the following example: 
Imagine to be at some street  junction in Munich, Germany, and you want to 
get to  Sausolito. 
You have available road maps, for  Munich, Bavaria, Germany, Europe and a 
world map which e.g. contains only 4  US-cities: New York, Chicago, L.A., Miami.  
But none of your maps shows Sausolito !!!  Here, BGP would give up!  
But let’s assume, you also know the  geographical coordinates of Sausolito as 
well as of all nodes of all your nodes  on your maps.( 1 degree precision is 
enough, no minute or second precision is  required.). Let’s also assume you 
can by some procedure combine all your maps to  a single map whereby your closer 
zoomed available map information  replaces the respective part in the less  
zoomed map. You may find out that L.A. is closest to your destination and use  
the L.A. node as the destination node for determining the best next hop – here 
 to the next street in Munich towards the Munich airport. Later, you may 
arrive  in NY, and your current country map would also show San Francisco, but 
still not  Sausolito.So you would make the best next hop being bound to S.F. 
Whenever you  arrive in California, you may also see Sausolito on your current 
state map and  determine the best next hop bound to Sausolito.  However, as soon 
as you have reached a  router which has the same geographical coordinates like 
your destination, this  kind of information cannot help you any further. Yes 
from now on you need  guidance based on aggregated prefix information as to 
determine the proper  destination node on your map as we are used to. So prefix 
propagation can be  limited to a 1-degree-square. 
Note,  how powerful the„<=“ operator was,  when L.A. was selected,  compared 
to  „==“.  
Mathematical analogy:  If you want to find out whether the real  number x is 
between 0 and 1 you don’t have to compare x with all real numbers in  this 
interval. 
Now the big thing is to build the  proper hierarchical network, i.e. the 
combined topology of the various maps of  different zoom. Each loose link must 
have the right length (weight)  ! 
There must be a clear understanding  which   1-degree-squares would be 
contained  within which more upper map. This is subject to „well-known“ 
standardization  information.  
Although the borders should be  determined by clean longitude/latitude values 
and not by political areas like  counties, states, countries, continents, let 
me, for better understanding, use  such political terms by the following. 
Example: A state map shall be built  based on all county maps thereof. Each 
county node router computes the (same  identical) county’s  contribution  for 
this state map, i.e that set of loose links by which it shall be represented  
in the next upper topology. Hereby it is sufficient that each node of the 
county  knows all those county nodes that shall show up in the state map.  This 
information needs to be exchanged  across the borders of neighboring counties of 
the same state. Not of different  states; that would be required in the next 
recursion cycle. The process is  similar to forming a PNNI hierarchy. 
Like there we would  have to deal with uplinks (for combining  maps of 
different zoom) and hierarchical horizontal links, but there are some  important 
differences. An uplink is not the aggregation of a group of  border-to-border 
physical links.Instead its upper end is some representative  node of the 
neighboring county. 
Instead of the inmature Logical  Group Node Representation with spokes and 
nucleus etc, we would  have well-computed representative  topologies, in the 
precisely same manner as when we have road maps for cities,  counties, states, 
countries, continents. 
If  DNS-lookup not only provided the  destination IPv4-address but also the  
longitude/latitude information, and if we  computed for each visible node the 
best next hop, which includes each visible  hierarchically upper node, then we 
could place the best next hop info into a  matrix with 360 x 360 elements, 
and could retrieve it by means of a single  access (at least in case of 
hierarchically upper dest.  nodes) 
Yesterday I received the Internet  Journal with contributions about the IPv4 
address  depletion. 
Maybe IPv4 addresses have only to be  unique 1-degree-square-wide rather than 
world-wide ?!   
It may of course be up to the  ID-utilization (besides the LOC-utilization), 
but eventually this solution may  also avoid this depletion dilemma.  
LISP-CONS: Look, there is no  political quarrel about the proper allocation 
of longitudes/latitudes. They are  already properly positioned and do not need 
any dissemination process. By taking  geographical coordinates also as address 
info, then it is appropriate to  speak of building some (hierarchical) 
topology that follows addressing  :-)  
Routing churn: You will see, a loose  link like Chicago---L.A. would only go 
down in case of a power black out  throughout the western part of the USA. 
Hence the looser the link, the less the  churn. 
Rome was not built in one day.   Nor this concept. It may take some time for 
being developed. 
But it has immense beneficial  objectives, which really can be accomplished.  
Heiner

---

From: [email-masked]
Date: Fri, 9 Nov 2007 15:54:40 EST

Philip, thanks for your email.
See my comments inside whether your understand does or does not comply with  
what I was writing.
Heiner
 
In einer eMail vom 09.11.2007 16:56:27 Westeuropäische Normalzeit schreibt  
[email-masked]:

Heiner 
Thanks. re your first  para - personally I find it very useful to understand 
what a protocol is  trying to do at a high level and why - before reading all 
the  detail. 
Let me see if I  understand your approach: 
- A node’s address is  simply its geographic location [based on 
latitude/longitude].  
No. The geographical location is only an attribute. Within the same  
geographical area there are, in general, multiple routers which show up  at some more 
upper map. You might object, well, a single particularly  elected router shall 
represent let's say a fifth of all router's from  California. What if that 
one goes down?
Well, all other routers which are closer to this one than to any other  
representative router from California, would continue to "stick to it". 
Sometimes ugly situations like such one are helpful to demonstrate the  
bottom line:
If I am sending from Munich, Germany, a postal letter to someone in  
Sausolito, who however has moved to a different location, it is perfectly fine -  in 
my view - that this letter is first of all sent to some postal office in  
Sausolito rather. For me, it is acceptable that such a letter has to be sent  back 
all the long way because I believe, it makes no sense, that if someone  
relocates, all postal offices in the world should be informed. Also, in that  case 
we wouldn't have got the lovely Elvis song RETURN TO SENDER :-)

- The topology is  hierarchical & follows the addressing.  
The topology is  hierarchical and the way the hierarchy is "formed up" is 
according to  geograph. attributes. 
Geographic-based  routing is an interesting idea and there has been some 
study of it in the ad  hoc community I believe. Couple of questions: 
- Would any policy  control be possible?
 For sure, because as soon as some concept is established people  are smart 
enough to enhance it :-) 
Also: Imagine, that your OSPF routers would also have these geo-attributes!  
You may try to get closest to the destination inside your OSPF network,  e.g.

eg to route through a  particular higher level network that you have a 
commercial deal with. How  about TE & multihoming? 
How about multiple routes with even different   hierarchical  links towards 
the egress?!
 
All these things would seem to me to  make it more problematic to enforce ‘
topology must follow geography’. in the  context of a global network, would it 
mean there was only one  network?

- how would failures  be dealt with? Can you discover & swap to and 
alternative path? (this  would then mean that topology didn’t follow  geography)
Maybe it is better to put this law aside again, there is no extra value in  
following this or that. The proposed concept was not developed based on this  
law.

- could you handle  mobile nodes and networks? 
We can cross that bridge when we have arrived there.
 
Heiner

---

From: <[email-masked]>
Date: Fri, 9 Nov 2007 15:55:04 -0000

Heiner

Thanks. re your first para - personally I find it very useful to
understand what a protocol is trying to do at a high level and why -
before reading all the detail.

- A node's address is simply its geographic location [based on
latitude/longitude]. 

- Would any policy control be possible? eg to route through a particular
higher level network that you have a commercial deal with. How about TE
& multihoming? All these things would seem to me to make it more
problematic to enforce 'topology must follow geography'. in the context
of a global network, would it mean there was only one network?

- how would failures be dealt with? Can you discover & swap to and
alternative path? (this would then mean that topology didn't follow
geography)

sorry if I've completely misunderstood it

best wishes,

Phil Eardley 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: 09 November 2007 11:54
To: [email-masked]
Subject: [RRG] Topology that follows addressing

Let meaddress just that particular NIRA-objective which this
mailinglist's discussion is all about, its design and yes, also soon,
the hereby needed algorithmic technology as to compute consistently
viewed hierarchical topologies. For that computation only a minor
enhancement of the Dijkstra is required, but not the entire All  Links
Spanning Tree (ALST). But step by step. Prior contributing this small
though important puzzle as to show the HOW, I think it's appropriate to
show at first WHAT shall be accomplished as well as WHY this protocol
development will get us out of the BGP-trap or better said
aggregation-trap (an imaginary world-wide OSPF would have the same
problems).

WHAT:The goal is that each router aquires a hierarchical network view,
where the current router is surrounded by a network of strict links,
which is surrounded by a network of looser  ... and looser links. For
proper understand WHY so, let me give the following example:

Imagine to be at some street junction in Munich, Germany, and you want
to get to Sausolito.

You have available road maps, for Munich, Bavaria, Germany, Europe and a
world map which e.g. contains only 4 US-cities: New York, Chicago, L.A.,
Miami. 

But let's assume, you also know the geographical coordinates of
Sausolito as well as of all nodes of all your nodes on your maps.( 1
degree precision is enough, no minute or second precision is required.).
Let's also assume you can by some procedure combine all your maps to a
single map whereby your closer zoomed available map information
replaces the respective part in the less zoomed map. You may find out
that L.A. is closest to your destination and use the L.A. node as the
destination node for determining the best next hop - here to the next
street in Munich towards the Munich airport. Later, you may arrive in
NY, and your current country map would also show San Francisco, but
still not Sausolito.So you would make the best next hop being bound to
S.F. Whenever you arrive in California, you may also see Sausolito on
your current state map and determine the best next hop bound to
Sausolito.  However, as soon as you have reached a router which has the
same geographical coordinates like your destination, this kind of
information cannot help you any further. Yes from now on you need
guidance based on aggregated prefix information as to determine the
proper destination node on your map as we are used to. So prefix
propagation can be limited to a 1-degree-square.

Note,  how powerful the"<=" operator was, when L.A. was selected,
compared to "==". 

Mathematical analogy:  If you want to find out whether the real number x
is between 0 and 1 you don't have to compare x with all real numbers in
this interval.

Now the big thing is to build the proper hierarchical network, i.e. the
combined topology of the various maps of different zoom. Each loose link
must have the right length (weight) !

There must be a clear understanding which   1-degree-squares would be
contained within which more upper map. This is subject to "well-known"
standardization information. 

Although the borders should be determined by clean longitude/latitude
values and not by political areas like counties, states, countries,
continents, let me, for better understanding, use such political terms
by the following.

Example: A state map shall be built based on all county maps thereof.
Each county node router computes the (same identical) county's
contribution for this state map, i.e that set of loose links by which it
shall be represented in the next upper topology. Hereby it is sufficient
that each node of the county knows all those county nodes that shall
show up in the state map.  This information needs to be exchanged across
the borders of neighboring counties of the same state. Not of different
states; that would be required in the next recursion cycle. The process
is similar to forming a PNNI hierarchy.

Like there we would  have to deal with uplinks (for combining maps of
different zoom) and hierarchical horizontal links, but there are some
important differences. An uplink is not the aggregation of a group of
border-to-border physical links.Instead its upper end is some
representative node of the neighboring county.

Instead of the inmature Logical Group Node Representation with spokes
and nucleus etc, we would  have well-computed representative topologies,
in the precisely same manner as when we have road maps for cities,
counties, states, countries, continents.

If  DNS-lookup not only provided the destination IPv4-address but also
the  longitude/latitude information, and if we computed for each visible
node the best next hop, which includes each visible hierarchically upper
node, then we could place the best next hop info into a matrix with 360
x 360 elements, and could retrieve it by means of a single access (at
least in case of hierarchically upper dest. nodes)

Yesterday I received the Internet Journal with contributions about the
IPv4 address depletion.

Maybe IPv4 addresses have only to be unique 1-degree-square-wide rather
than world-wide ?!  

It may of course be up to the ID-utilization (besides the
LOC-utilization), but eventually this solution may also avoid this
depletion dilemma. 

LISP-CONS: Look, there is no political quarrel about the proper
allocation of longitudes/latitudes. They are already properly positioned
and do not need any dissemination process. By taking geographical
coordinates also as address info, then it is appropriate to speak of
building some (hierarchical) topology that follows addressing :-) 

Routing churn: You will see, a loose link like Chicago---L.A. would only
go down in case of a power black out throughout the western part of the
USA. Hence the looser the link, the less the churn.

Rome was not built in one day.  Nor this concept. It may take some time
for being developed.

But it has immense beneficial objectives, which really can be
accomplished. 

Heiner

---

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

On 9 nov 2007, at 12:53, [email-masked] wrote:

[It seems that I can't reasonably quote anything from your message  
that shows the core idea.]

I understand this to be geographic routing, which goes even further  
than the geographic aggregation that is pretty much rejected out of  
hand whenever it comes up within the IETF (which is every couple of  
years or so).

Unless I'm mistaken, the idea is that geographic proximity equals  
topological proximity. I'm afraid that can't work in a wired network.  
If I'm in Holland I'm closer to Scotland than when I'm in Belgium. But  
if I want to travel to Scotland through the channel tunnel, I need to  
go through Belgium. So I need to get farther geographically to get  
closer topologically.

The way to solve this would be to lift the geo/topo alignment  
requirement as soon as you reach a certain zoom level. But then  
there's the traditional argument against geographic aggregation: how  
do you avoid ISPs having to carry traffic for free? In other words:  
who announces the aggregates to the rest of the world?

Are you familiar with Tony Hain's draft about geographic addressing?

--
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, 22 Nov 2007 07:16:17 EST

In einer eMail vom 22.11.2007 10:33:37 Westeuropäische Normalzeit schreibt  
[email-masked]:

I  understand this to be geographic routing, which goes even further   
than the geographic aggregation that is pretty much rejected out of   
hand whenever it comes up within the IETF (which is every couple of   
years or so).
But this one is different, and that's why ( my guess) you are mistaken  ,next.

Unless I'm mistaken, the idea is that geographic proximity  equals  
topological proximity. I'm afraid that can't work in a wired  network.  
If I'm in Holland I'm closer to Scotland than when I'm in  Belgium. But  
if I want to travel to Scotland through the channel  tunnel, I need to  
go through Belgium. So I need to get farther  geographically to get  
closer topologically.
The link weight for each loose =hierarchical link is equal to the number of  
hereby required physical hops.
Hence stretch is equal 1, and in case your router in Scotland is just one  
hop away than
If your router in Scotland is just one hop away than you are "closer to  
Scotland than to Belgium" though being in Holland. Nira works like in an  
OSPF-network, however whereby the network is deminished the more the nodes are  furth
er away.

>requirement as soon as you reach a certain zoom level. 
 
As soon as the current router is marked with the same geo-date as is the  
packet's destination, any other classic method shall apply (OSPF or BGP).
  
But then  
 
You mean to the rest of this geo-patch (remember: no worldwide routing  
churn! ) ! Well just like it is done in OSPF. Hereby, across any two adjacent  
ISPs, aggregates shall be announced : 
The representative node from ISP A which has a loose=hierarchical link to  
some representative node from ISP B shall indeed announce not only his own  
reachability info, but also that one of all its surrounding ISP-A- nodes, which  
are closer to it than to any other representative node. 

>Are you familiar with Tony Hain's draft about geographic  addressing?

No, I am not. But believe me, I am absolutely in accordance with  
link-state-protocols. I am not in favor of exploiting country codes, nor of  any other 
geo-political information. The goal is just to "thin" the too big  internet. If 
I want to travel von Munich to Manhattan 42 street, I do not care  about any 
road blockage as long as I haven't reached New York ! It wouldn't  impact by 
decision to make the best next hop towards the airport for  departure.

Heiner

---

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

On 22 nov 2007, at 13:16, [email-masked] wrote:

[...]

I'm sorry, I don't understand your message. In addition to setting an  
exceedingly tiny font, your mailprogram doesn't make a difference  
between the quoted text and new text, so it's extremely hard to figure  
out how every statement relates to what was said previously.

But most importantly, I couldn't detect anything that answers my  
questions. Unlike my own proposal in this area some years ago, Tony  
Hain's geo addressing is completely coordinate-based.

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Thu, 22 Nov 2007 13:46:47 +0100

Hi,

Sorry for jumping in the middle of the thread

> hand whenever it comes up within the IETF (which is every couple of  
Not sure what "geographic aggregation" you're referring to, but here  
is one that seems to work and avoids the pitfalls you mentioned bellow:
http://www.cs.ucla.edu/~rveloso/papers/giro.pdf

Comments are appreciated.
Thanks,

--Ricardo

> topological proximity. I'm afraid that can't work in a wired  
> network. If I'm in Holland I'm closer to Scotland than when I'm in  
> Belgium. But if I want to travel to Scotland through the channel  
> tunnel, I need to go through Belgium. So I need to get farther  
> geographically to get closer topologically.
>
> there's the traditional argument against geographic aggregation:  
> how do you avoid ISPs having to carry traffic for free? In other  
> words: who announces the aggregates to the rest of the world?
>

---

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

> Sorry for jumping in the middle of the thread

Why would you be sorry about that?

> Not sure what "geographic aggregation" you're referring to

Simple: 1. encode geography into addresses, 2. aggregate. See

http://www.muada.com/drafts/draft-van-beijnum-multi6-isp-int-aggr-01.txt

> but here is one that seems to work and avoids the pitfalls you  
> mentioned bellow:

> Comments are appreciated.

Ok:

- using imperial measurements in a research paper, is that allowed??

- as is remarked at the end of the paper, you don't need to encode  
geography into the address for BGP decision making

- now that AS numbers are 32 bits, something like this would probably  
use too much address space

- you're not aggregating on geography, but on AS. As such, a 1:4  
reduction is quite poor because the number of prefixes per AS is  
upwards of 1:8

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Thu, 22 Nov 2007 18:04:15 +0100

Thanks for the comments

> - using imperial measurements in a research paper, is that allowed??
yes

> geography into the address for BGP decision making
yes, each operator uses this info in BGP decision as they wish

>
> - now that AS numbers are 32 bits, something like this would  
> probably use too much address space
not in a ipv6 world

> reduction is quite poor because the number of prefixes per AS is  
I'm doing both. Per AS is termed "topological aggregation", while per  
geography is "geographical aggregation" .From the 75% reduction, 40%  
are topological aggregates and the rest some form of geographical  
aggregation. Note that this aggregation preserves AS path diversity,  
therefore it's bellow the ratio #ASes/#prefixes.

Thanks,

--Ricardo

---

From: [email-masked]
Date: Thu, 22 Nov 2007 14:06:39 EST

Topology aggregation, geographical aggregation, AS aggregation: 
While I am about to start writing a draft I am aware that using these  terms 
might generate even more confusion than clarity. The same applies to  the term 
"hierarchy". Because:
 
The ultimate NIRA-goal is that each router aquires the view of a flat  
topology of the entire internet, however such sparsed, that it comprises only a  
reasonable number of nodes and links (500 or 1000 nodes and e.g. twice or three  
times this number of links). The more remote the contained links, the  looser 
they become. 
Call this link aggregation, or better don't say so at all. Nodes:   there is 
no node aggregation or better said reachability info aggregation for  any more 
remote node. Only for nodes in the near proximity, yes,   reachability info 
aggregation is required to be disseminated just  within the lowest-level 
geo-patch vicinity.
 
For reaching this goal it still takes some hierarchically organized routing  
protocol procedural steps :-)
 
Terminology should help, not confuse, us.
 
Heiner
 
In einer eMail vom 22.11.2007 18:04:43 Westeuropäische Normalzeit schreibt  
[email-masked]:

Thanks  for the comments

yes

not in a ipv6 world

Thanks,

--Ricardo

In einer eMail vom 22.11.2007 18:04:43 Westeuropäische Normalzeit schreibt  
[email-masked]:

Thanks  for the comments

yes

not in a ipv6 world

Thanks,

--Ricardo

---

From: Tony Li <[email-masked]>
Date: Tue, 27 Nov 2007 11:52:36 -0800

On Nov 22, 2007, at 4:16 AM, [email-masked] wrote:

> You mean to the rest of this geo-patch (remember: no worldwide  
> routing churn! ) ! Well just like it is done in OSPF. Hereby,  
> across any two adjacent ISPs, aggregates shall be announced :
> The representative node from ISP A which has a loose=hierarchical  
> link to some representative node from ISP B shall indeed announce  
> not only his own reachability info, but also that one of all its  
> surrounding ISP-A- nodes, which are closer to it than to any other  
> representative node.

I'm pretty sure I don't understand that explanation.

Advertising all of ISP A's prefix isn't the issue at all. The real  
question is: what happens at the geo-patch abstraction (action)  
boundary?  Where is that boundary?  Who is responsible for traffic  
arriving into the geo-patch?  What happens if the topology within the  
geo-patch is internally disconnected?

The traditional explanation is that there must be regulations  
requiring an interconnect for the geo-patch and all providers must  
connect to that interconnect.  The alternative is that providers with  
links outside of the geo-patch end up receiving traffic destined for  
other providers and end up providing free transit.

More generally, if the entry point at an abstraction action boundary  
is not directly connected to all of the sub-abstractions, then you  
have a situation where traffic must traverse a sub-abstraction, which  
will violate commercial constraints.  Thus, the abstraction action  
boundary must be located where there is common (or free) connectivity  
to all of the sub-abstractions.  You can conceivably shift the  
abstraction action boundary away from the abstraction naming boundary  
to help with this (i.e., do proxy aggregation), but how is this  
maintained in the face of changing topology and across hierarchical  
levels?

The OSPF assumption that all routers are willing to carry all traffic  
simply doesn't hold in the inter-domain routing arena.

Tony

---

From: [email-masked]
Date: Tue, 27 Nov 2007 16:18:46 EST

In einer eMail vom 27.11.2007 20:54:53 Westeuropäische Normalzeit schreibt  
[email-masked]:

Advertising all of ISP A's prefix isn't the issue at all. The real  question 
is: what happens at the geo-patch abstraction (action) boundary?  Where is 
that boundary? 

I think I have explained this: At the event that an IP packet shall be  
forwarded, the  first (like the following) inside some geopatch realizes  that its 
own as well as the packet's destination have the same  longitude/latitude and 
therefore the next hop is determined based on the  recognized destination node 
which has a best suitable reachability info.
 
And I think I have explained the routing protocol. Maybe I should write  more 
about the recursion.

 Who is responsible for traffic arriving into the geo-patch?  

the receiving node, who else ? but maybe I do not understand the  question.

 What happens if the topology within the geo-patch is internally  
disconnected?  

Permanent partition ( I placed just a few line to show that I am aware of  
this problem which is certainly for further study). Maybe it should be requested 
 that at least one representative node must also show up in the next higher 
level  map. Then any node of one particular partition will learn via the next  
upper level map that there are more such representative nodes than  
disposed/contributed by this partition. Hence the partition is detected. I am  sure that 
there are several ways to treat this problem (partition id?, partition  
bridging area,...
I am optimistic. When we started PNNI we had much less available.

The traditional explanation is that there must be regulations requiring  an 
interconnect for the geo-patch and all providers must connect to that  
interconnect.  The alternative is that providers with links outside of  the geo-patch 
end up receiving traffic destined for other providers and end up  providing 
free transit.

COMMENT: At first it takes knowledge about shortest path routing. Then we  
can come up with provider constraints and assign QOS/policy attributes to  the 
loose links.

More generally, if the entry point at an abstraction action boundary is  not 
directly connected to all of the sub-abstractions, then you have a  situation 
where traffic must traverse a sub-abstraction, which will violate  commercial 
constraints. 
Thus, the abstraction action boundary must be located where there  is common 
(or free) connectivity to all of the sub-abstractions.  You can  conceivably 
shift the abstraction action boundary away from the abstraction  naming 
boundary to help with this (i.e., do proxy aggregation), but how is  this maintained 
in the face of changing topology and across hierarchical  levels?
I am not sure I understand your questions. Maybe I should write more about  
the adjacency of two different nxm-square-degree geo-patches.
Maybe this helps to avoid wrong understanding: In the past Germany  conquered 
parts of France, and vice versa France conquered parts of  Germany. But that 
did not change the shortest path between Paris and Berlin at  all.

The OSPF assumption that all routers are willing to carry all traffic  simply 
doesn't hold in the inter-domain routing arena. 

See COMMENT above. I assume, EBGP hops only won't deliver the packet  either, 
will they? Honestly, if you have a viewed topology (nicely sparsed to  become 
scalable), you can do better policies and TE than by just having AS-path  
strings, right?

Heiner

---

From: Tony Li <[email-masked]>
Date: Tue, 27 Nov 2007 18:38:35 -0800

> boundary?  Where is that boundary?
> I think I have explained this: At the event that an IP packet shall  
> be forwarded, the  first (like the following) inside some geopatch  
> realizes that its own as well as the packet's destination have the  
> same longitude/latitude and therefore the next hop is determined  
> based on the recognized destination node which has a best suitable  
> reachability info.
>
> And I think I have explained the routing protocol. Maybe I should  
> write more about the recursion.

I'm interested in the abstractions in the routing protocol, not the  
forwarding plane.

> the receiving node, who else ? but maybe I do not understand the  

Who administers that receiving node?  Can it receive traffic for a  
different AS?  If so, what does it do with it?  How do they get  
compensated for forwarding it?

> Permanent partition ( I placed just a few line to show that I am  
> aware of this problem which is certainly for further study). Maybe  
> it should be requested that at least one representative node must  
> also show up in the next higher level map. Then any node of one  
> particular partition will learn via the next upper level map that  
> there are more such representative nodes than disposed/contributed  
> by this partition. Hence the partition is detected. I am sure that  
> there are several ways to treat this problem (partition id?,  
> partition bridging area,...

I think that this needs to be made explicit.  Partition repair is a  
non-trivial subject, especially when it might have to be repaired at  
some arbitrarily higher level in the hierarchy.

> connect to that interconnect.  The alternative is that providers  
> with links outside of the geo-patch end up receiving traffic  
> destined for other providers and end up providing free transit.
> COMMENT: At first it takes knowledge about shortest path routing.  
> Then we can come up with provider constraints and assign QOS/policy  
> attributes to the loose links.

Sorry, but the constraints frequently make the topologically shortest  
path irrelevant.  Again, this is why today's inter-domain routing is  
so much more complicated than OSPF.

> More generally, if the entry point at an abstraction action  
> boundary is not directly connected to all of the sub-abstractions,  
> then you have a situation where traffic must traverse a sub- 
> abstraction, which will violate commercial constraints.  Thus, the  
> abstraction action boundary must be located where there is common  
> (or free) connectivity to all of the sub-abstractions.  You can  
> conceivably shift the abstraction action boundary away from the  
> abstraction naming boundary to help with this (i.e., do proxy  
> aggregation), but how is this maintained in the face of changing  
> topology and across hierarchical levels?
> I am not sure I understand your questions. Maybe I should write  
> more about the adjacency of two different nxm-square-degree geo- 
> patches.
> Maybe this helps to avoid wrong understanding: In the past Germany  
> conquered parts of France, and vice versa France conquered parts of  
> Germany. But that did not change the shortest path between Paris  
> and Berlin at all.

No, that doesn't help at all, sorry.

Let's see if I can explain the problem differently: suppose that we  
have a geo-patch that is "France".  This abstraction is circulated  
outside of France and is advertised outwards at each border.   
However, the administration of Alsace-Lorraine has a grudge with the  
national government of France.  All traffic that arrives in Alsace- 
Lorraine that is not destined within Alsace-Lorraine and is forwarded  
on to other areas has an associated charge of 1 Euro per packet.  If  
this is not paid, then the packet is dropped.  How do you prevent  
this situation?

>  The OSPF assumption that all routers are willing to carry all  
> traffic simply doesn't hold in the inter-domain routing arena.
> See COMMENT above. I assume, EBGP hops only won't deliver the  
> packet either, will they? Honestly, if you have a viewed topology  
> (nicely sparsed to become scalable), you can do better policies and  
> TE than by just having AS-path strings, right?

Yes, EBGP hops would compute paths around the non-transit domains and  
deliver the traffic, albeit with the cost of only being able to  
aggregate to the prefix/AS level.

Yes, we could do better TE if we had a full map everywhere, but we  
can't because propagating policy (and I include destination, transit,  
and source policies) requires disclosure of policy information that  
is today considered proprietary.

Tony

---

From: [email-masked]
Date: Wed, 28 Nov 2007 03:29:23 EST

In einer eMail vom 28.11.2007 03:39:10 Westeuropäische Normalzeit schreibt  
[email-masked]:

 
Which 1x1 square degree geo-patches are supposed to form a cluster for the  
next upper nxm-square degree patch, and which n1xm1-square-degree geopatches 
are  supposed  to form the next upper n2xm2 quare-degree geopatch - this is up  
to IANA directives. 

Who administers that receiving node?  Can it receive traffic for a  different 
AS?  If so, what does it do with it?  How do they get  compensated for 
forwarding it?

Can a border node of some geo-patch receive packets for different ISPs? Of  
course it can.
And of course policies can be implemented which mark certain loose links to  
be non-transit.
How do adjacent ISPs get paid ? I guess they make a mutual contract. 
I am convinced that a viewed topology provides more for  implementing 
policies which overrule the absolute shortest path principle, than  a multitude of 
AS-path strings. BGP-Question: Can/would/does some AS advertise  its access to 
some destinations and combine it with a withdrawal threat in case  that some 
other, disliked AS wants to append itself to the AS-PATH ? I don't  think so.

Permanent partition ( I placed just a few line to show that I am aware  of 
this problem which is certainly for further study). Maybe it should be  
requested that at least one representative node must also show up in the  next higher 
level map. Then any node of one particular partition  will learn via the next 
upper level map that there are more such  representative nodes than 
disposed/contributed by this partition. Hence the  partition is detected. I am sure that 
there are several ways to treat this  problem (partition id?, partition 
bridging area,...
I am optimistic. When we started PNNI we had much less  available.

I think that this needs to be made explicit.  Partition repair is a  
non-trivial subject, especially when it might have to be repaired at some  arbitrarily 
higher level in the hierarchy.
Right, partition repair is not trivial, but it starts out with recognizing  
that there is a partition.
There should be more than sufficient routing expertise all around to  a) 
define what is best, what is acceptable, what is not acceptable for any  solution 
and b) implement the respective solution.
If you look at the newest graph picture on my website you will see that  
there are many routes to the destination besides the blue shortest route.

Sorry, but the constraints frequently make the topologically shortest  path 
irrelevant.  Again, this is why today's inter-domain routing is so  much more co
mplicated than OSPF.

I would rather say, because the tools are less capable. With the current  
interdomain-routing protocol you can neither  afford nor do  the implementation 
of OSPF-MT like solutions.

More  generally, if the entry point at an abstraction action boundary is not  
directly connected to all of the sub-abstractions, then you have a  situation 
where traffic must traverse a sub-abstraction, which will  violate commercial 
constraints.  Thus, the abstraction action boundary must be located where  
there is common (or free) connectivity to all of the sub-abstractions.  You can 
conceivably shift the abstraction action boundary away from  the abstraction 
naming boundary to help with this (i.e., do proxy  aggregation), but how is 
this maintained in the face of changing topology  and across hierarchical levels?

Let's see if I can explain the problem differently: suppose that we have  a 
geo-patch that is "France".  This abstraction is circulated outside of  France 
and is advertised outwards at each border.  However, the  administration of 
Alsace-Lorraine has a grudge with the national government of  France.  All 
traffic that arrives in Alsace-Lorraine that is not destined  within 
Alsace-Lorraine and is forwarded on to other areas has an associated  charge of 1 Euro per 
packet.  If this is not paid, then the packet is  dropped.  How do you prevent 
this situation?

Advertise policy attributes for respective  loose links.

Yes, EBGP hops would compute paths around the non-transit domains and  
deliver the traffic, albeit with the cost of only being able to aggregate to  the 
prefix/AS level.

Yes, we could do better TE if we had a full map everywhere, but we can't  
because propagating policy (and I include destination, transit, and source  
policies) requires disclosure of policy information that is today considered  
proprietary.

Tony

=

Some additional remark:
The drafted core algorithm was already published in 1988. This is more than  
17 years ago. Hence no one can have IPRs on it. You may google for Voronoi,  
Delaunay, Mehlhorn.
 
Heiner