The Hole in my proposal

[Joel Halpern <[e-mail]>]

Talking with Yakov Rekhter about my proposal, Yakov found a serious hole.

The problem is a consequence of the intra/inter-domain split, and the fact
that metrics are not comparable across the split.  In the following figure,
upper case letters are inter-domain routers, while lower case are
intra-domain. There may easily be additional intra-domain routers in each
domain, as well as additional inter-domain routers.


                      Connection P1
          A-------Inter-domain_Connectivity--------Destination
          |                                             |
          |                                             | P2
           \ +======================================+   |
            \|          ATM Cloud                   |   B
             \                                      |   |
      AS1    |\                                     |   |  
             | \        ID Conn P3                  |  /
 Src-C-------d--k---E---------------------F---------g-m AS2
            /|                                      |  \
           l |                                      |   |
          /  +======================================+   |
         H                                              I
          \                                            /
           -------Inter-domain_Connectivity------------
                     Connection P4


The two domains are one surrounded by A, C, H, E and one surrounded by B, F,
I. P1, P2, P3, and P4 are inter-domain connectivity.  The two domains are each
an AS.  There may be additional domains along the inter-domain paths.
For the moment, we will assume that each domain is using a distance vector
intra-domain routing protocol.  (Thus, k hides the difference between A and E
from d, and m hides the difference between B and I from G.)

At the time when the Src begins transmitting, BGP in AS1 has selected an
interdomain path that goes from AS1 over P3 to AS2, thence over P2 to the
destination.  (Yes, I know that AS paths do not represent links.  But if there
are ASs on those links, they will occur.)

Therefore, the query from d, at the entry to the ATM cloud, would like to find
g at the exit.  Let us suppose it does.

Some time later, P2 fails to provide connectivity to the Destination.  AS1
still has connectivity through P1.  It advertises this connectivity over P4.
(Note that it may not even choose to advertise it over P3.)  Therefore, AS2s
chosen path to the Destination is AS2, P4, AS1, P1.
However, the metrics visible at d and g have not changed.  The cost from d to
the inter-domain exit to Dest is still 2.  The cost from g to the inter-domain
exit for getting to Dest is still 2.  (The fact that the inter-domain path is
longer is irrelevant.  And the picture could be adjusted so that the length
was the same, but policy had chosen different paths.)

Note that if domain AS1 were using OSPF, we could still have the problem if A
and E were the same box.  Similarly, in AS2, in B and I were the same even
OSPF would not help there either.

The result is that neither d nor g have seen ANY topological change.  In fact,
they have seen no change at all!  There are a couple of possible solutions:

1) Require d and g to be inter-domain routers.  Then InterDomain routing will
ensure stability and loop-freeness.  Note that this is not just an adjacency
between d and g, but full operation as inter-domain routers.
2) require E to have kept enough state to know when the inter-domain path has
changed. 
3) require E to intercept the answer to the query, note from the answer that
it is a router-router response that is about to transition from inter to intra
domain routing, and have E replace the answer with itself!

None of these are desirable answers.  Better answers are sought.

Thank you,
Joel M. Halpern			[e-mail]
Newbridge Networks Inc.