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