A New AURP Loop Detection Mechanism

[Greg Bruell <[e-mail]>]

Here's a rough draft of a proposal for using BGP's loop detection
mechanism in AURP. The reason for making this proposal now is because
AURP will be discussed at the up coming Appletalk Networking Forum
at Mactivity and I'd like to give people a chance to think about it.

Greg.



Draft             A New AURP Loop Detection                Draft
                         Greg Bruell
                   Wellfleet Communications
                           4/27/93

AURP version 1 is limited to topologies that don't have loops.
This is because AURP allows the user to map network numbers
and in the context of a loop AURP can map the network recursively
such that the same network number is mapped multiple times within
a single domain. The mechanism employed by AURP to detect a loop
only finds out about the loop after it's created. This means that
possible recursive mapping behavior can happen before AURP can do
anything about it. In addition there is no mechanism for deciding
which path should be taken if a loop is discovered.

The Boarder Gateway Protocol has a loop detection mechanism that
detects the loop before it's created and can therefore be used
safely in the context of mapping. The way BGP does this is to
propogate the entire domain path through which each individual
route is learned.

In order for AURP to employ BGP's loop detection mechanism the
following changes must be made.
1) Each transit AURP speaker must prepend all routes that it learns
externally with its domain id. External networks consist of the
Appletalk routing tuple plus the entire domain path leading back to
the original source of the route. These changes effect:
a) the packet format for RI's (both parsing an generation)
b) the storage or AURP routes
c) the logic for AURP route selection

2) Each AURP speaker must open an AURP Tr connection with all other
AURP speakers in it's domain. All external routes learned by the
AURP router must be sent to all other AURP routers. This is done
so that AURP routers can distinguish between internal and external
routes. This is needed only for transit or multihomed AURP domains.
These changes effect:
a) the state machine for AURP connections
b) the logic for storage of AURP routes
c) a new ddp type should be reserved for AURP Tr
d) the internal connections must be configured (although one could
use NBP for router discovery)

A New AURP Loop Detection                            G. Bruell
Example:
 
    Domain A             Domain B
  ____________         ____________
 |    _1__BR1-----------BR3__1__   |              
 |   |        |       |         |  |
 |  IR1       |       |        IR2 |
 |   |_2__BR2-----------BR4__2__|  |
 |____________|       |____________|

IR = internal router
BR = boarder router
Note the network numbers in the two domains are the same (1, 2).

Mapping is enabled on both external links. Let's assume for this
example that the boarder routers come up in the order: BR1, BR2,
BR3, BR4 although it doesn't matter which order the routers come
up.

1) BR1 comes up and tries to establish all internal links and
external links.

2) BR2 comes up and establishes an internal link with BR1.

3) BR3 comes up and establishes an external link with BR1.
 a) BR3 advertises: B1-1,2-2
 b) BR1 advertises: A1-1,2-2

4) BR1 maps B1-1,2-2 to B3-3,4-4

5) BR3 maps A1-1,2-2 to A3-3,4-4

6) BR1 advertises B1-1,2-2 to BR2 and 3-3,4-4 internally

7) BR3 advertises 3-3,4-4 internally

8) BR4 comes up and establishes an internal link with BR3 and
an external link with BR2

9) BR3 advertises A1-1,2-2 to BR4

10) BR2 advertises A1-1,2-2 to BR4

11) BR4 finds A1-1,2-2 being advertised externally and applies
the policy of taking possibly mapped routes from internal
neigbors over external routes. (NOTE: One alternative is that
both mapped and unmapped versions of routes are sent internally
in which case it doesn't matter which path the router choses).
After thinking about this some more I've decided that AURP+
should use exactly the same policy as BGP. This means that
the router with the lowest BGP identifier (some equivalent
identifier would be need for AURP+) is the boarder router that
gets to advertise the route internally.