[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [RRG] Geographic aggregation-based routing



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 bill@herrin.us:
On Fri, Jul 11, 2008 at 2:32 AM,  <HeinerHummel@aol.com> wrote:
> Based on: http://bill.herrin.us/network/geoag.gif
>
> 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.

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


--
William D. Herrin ................ herrin@dirtside.com bill@herrin.us
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

--
to unsubscribe send a message to rrg-request@psg.com 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