architecture comments - part 2

[[e-mail]]

Hello Yakov,

Below, I discuss a couple of distance vector issues that I left out of
my first response to your comments on the IDPR architecture document.
Also, thank you for your second set of comments.  I have couple of
clarifications that I have included pertaining to those comments.

After receiving the recent comments on the IDPR documents, and your
comments in particular, I wonder whether separating the architecture
document from the protocol specification has been a good idea.  We
chose to separate the two documents so that people who wanted some
background and an overview of IDPR, but who did not want to deal with
protocol details, could have such a document to read.  Also, the
document separation helped to reduce the size of the protocol
specification.  I hesitate to combine the two documents for these
reasons.  Perhaps instead I should insert more pointers in the
architecture document to the relevant details contained in the other
IDPR documents.

Distance Vector Distribution Graphs
-------- ------ ------------ ------

The first of the distance vector issues concerns what I called the
distribution graph.  After I reread the paragraph in question (the
last full paragraph on page 7 of the text version), I could well
understand your confusion.  Let me restate here, in what I hope are
clearer terms, the idea I was trying to state in the architecture
document.  After reading this, please let me know if you still
disagree with my conclusions.

I intended that each domain administrator would construct a distance
vector distribution graph that governed the flow of the distance
vectors originally generated within that domain and would incorporate
into the distribution graph the distribution restrictions (transit
policies) of other domains.  I'm not saying that this is THE way
to go, simply a way to control distribution of distance vectors.

An example of a distance vector distribution graph for a domain
Z is as follows:

        |----> X ----|
        |            |
        |            \/
        Z            W ----> R
        |            /\
        |            |
        |----> Y ----|

This directed graph with no cycles means that it is impossible for two
domains A and B to select routes to Z, such that A's route contains B
and B's route contains A.  Yes, BGP/IDRP does a loop check on each
path vector received.  However, using a directed cycle-free graph for
distance vector distribution also provides freedom from forwarding
loops.

The problem with such a graph is that neither domain X nor Y can find
an alternate route to domain Z, if its direct link to Z fails.  The reason
is X and Z receive at most one distance vector from Z.  In order for
X or Y to receive more than one distance vector, there must be cycles
in the distribution graph.  An example of such a graph follows:

        |----> X <---|
        |            |
        |            \/
        Z            W ----> R
        |            /\
        |            |
        |----> Y <---|

Hop-by-Hop Forwarding
---------- ----------

Yakov, as you know we have argued about the example (on page 9 of the
text version of the architecture document) before, in the context of
your paper with Deborah Estrin and Steve Hotz.  I convinced Deborah
and I thought (but was apparently mistaken) that I had convinced you
as well that this state is not "transient".  While a distance vector
routing procedure could detect loops of this type, as far as I know,
neither BGP nor IDRP has such a detection mechanism - and with good
reason: it's expensive.  Hence, this loop will persist until either X
or Y chooses another route Z, which may not happen for a long time.

I actually saved all of the previous correspondence between you,
Deborah, and me concerning this problem.  And I can pass it along to
you and the rest of the idpr-wg list, if you'd like.

"Optimal" Routes
--------- ------

I was not sure how you intended the word "optimal".  You mentioned
that finding the "optimal" route takes exponential time.  If you mean
"optimal" in the sense of the following routing problem "find a route
between A and B that has delay no more that X and monetary cost no
more than Y", then you are correct.  This search does take exponential
time.  While an individual route server can do multi-criteria
optimization if it wishes, we recommend instead that the domain
administrator prioritize requested qualities of service according to
what is needed.  The route selected should provide the highest
priority type of service, but will be only "best effort" on the other
services requested.

However, if you mean "optimal" in the sense of minimizing delay,
minimizing cost, or maximizing bandwidth, then your statement isn't
true.  All of these functions can be performed in polynomial time,
using for example Dijkstra's SPF search or even a simple breadth-first
search.

BGP/IDRP
--------

Yakov, I used BGP as a comparison point for two reasons.  One is that
I did this comparison in the early part of 1991.  BGP was much more
solid than IDRP at that time.  The second reason was that I was
interested in IETF routing procedures.  At that point, IDRP was slated
for ANSI and not IETF.  I realize that much has happened since that
time, and that I should go back and make the comparison with IDRP.
However, at the time the comparison was a reasonable one to make.