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 PROTECTED]:
On Fri, Jul 11, 2008 at 2:32 AM, <[EMAIL PROTECTED]> 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 ................ [EMAIL PROTECTED] [EMAIL PROTECTED]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004
--
to unsubscribe send a message to [EMAIL PROTECTED] 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
