packet to reach its destination without exceeding the hop-count
limit.
When an exterior router receives a packet through the tunnel, it
examines the routing-table entry for that packet's destination
network to determine the remaining distance to that network. If the
distance already traversed by the packet-the packet's current hop
count-plus the distance to the destination network is less than 15
hops, the exterior router simply forwards the packet. If adding the
destination network's distance to the packet's current hop count
causes the hop count to exceed 15 hops, the exterior router sets the
hop count to the following value: 15 minus the distance in hops to
the destination network. The exterior router then forwards the
packet.
Using hop-count reduction, an exterior router must overcome the 15-
hop limits imposed by both DDP and RTMP. To overcome RTMP's 15-hop
limit, an exterior router should represent all networks accessible
through the tunnel to routers in its local internet as one hop away
when hop-count reduction is active on a tunneling port. This allows
routers to maintain and send routing information about networks
beyond the 15-hop limit and achieve full connectivity.
Constraints on Hop-Count Reduction
An interdomain loop exists when a redundant path connects two parts
of an internet that are connected through two exterior routers on a
tunnel. The proper operation of hop-count reduction requires that no
interdomain loops exist across a tunnel. For detailed information
about interdomain loops see the next section, "Routing Loops."
Because network-number remapping requires that no interdomain loops
exist on the internet, an exterior router can perform hop-count
reduction whenever network-number remapping is active, without any
risk of a packet being forwarded in an infinite routing loop.
Generally, an exterior router should not perform loop detection when
network-number remapping is inactive.
Routing Loops
A routing loop exists when more than one path connects two exterior
routers-both the path through the tunnel and a path through the
exterior routers' local internets. When network-number remapping is
not active on an exterior router, a routing loop can provide an
alternative path to a network. However, when network-number remapping
or hop-count reduction is active on an exterior router, all exterior
routers must avoid establishing loops across the tunnel. Otherwise,
if a routing loop went undetected, multiple routing-table entries
that referred to the same actual AppleTalk networks using different
remapping ranges might fill the routing tables of all of the exterior
routers on a tunnel.
First-Order Loops
In a first-order loop, a pair of exterior routers that are performing
network-number remapping across a tunnel are also connected through
another path, on which there are no remapping exterior routers. In
Figure 4-5, exterior routers A and B are remapping network numbers
across an AppleTalk tunnel, and exterior router C-which is not
remapping network numbers-creates a first-order routing loop.
Exterior router A's network range, 1 through 4, loops back to it
through the tunnel and may be remapped again.
<<Figure 4-5 A first-order loop>>
Second-Order Loops
In a second-order loop, one or more additional pairs of remapping
exterior routers are in the loop. In Figure 4-6, exterior routers A
and B are remapping network numbers across the AppleTalk tunnel that
connects them, and another pair of exterior routers, C1 and C2-which
are also performing remapping across the tunnel that connects them-
creates a second-order routing loop. Exterior router A's network
range, 1 through 4, is remapped by exterior router C2 to the network
range 101 through 104, then loops back to exterior router A through
the tunnel.
<<Figure 4-6 A second-order loop>>
Self-Caused and Externally Caused Loops
Routing loops can be either self-caused or externally caused. A self-
caused loop results when the detecting exterior router itself comes
on line. An externally caused loop results when another router comes
on line somewhere on the internet, after the detecting router has
been running for some time.
Loop-Detection Process
The following sections describe the phases of the minimal loop-
detection process that an exterior router must employ when either
network-number remapping or hop-count reduction is active. An
exterior router can implement an enhanced loop-detection scheme.
LOOP-INDICATIVE ROUTING INFORMATION: A remapping exterior router
should always examine routing information received through a tunnel
for indications that a routing loop may exist. Loop-indicative
routing information appears to refer to networks across the tunnel.
However, it may actually refer to networks in the exterior router's
own local internet if the networks' routing information has looped
back through the tunnel.
In the following definition of loop-indicative information,
the network range for the network connected to a given port of an
exterior router is referred to as ns through ne
the zone list for that network is referred to as z1 through zn
The routing information that a remapping exterior router receives
through a tunneling port is loop indicative if both of the following
conditions are true for some port on the router:
The size of the network range in the routing information is ne-
ns+1.
The zone list in the routing information consists precisely of z1
through zn.
Thus, the routing information could represent a remapping of the
network range for a network connected directly to one of the exterior
router's ports.
An exterior router most commonly receives loop-indicative information
at startup when the process of bringing up the tunnel may create a
self-caused loop. An exterior router may also receive loop-indicative
information if another router connects two AppleTalk domains that are
already connected through the tunnel and creates an externally caused
loop.
If a remapping exterior router receives loop-indicative routing
information through a tunnel, it should start a loop-investigation
process. For information about the loop-investigation process, see
the next section, "Loop-Investigation Process."
LOOP-INVESTIGATION PROCESS: To confirm or deny the existence of a
suspected loop, an exterior router performs a loop-investigation
process, in which it sends an AppleTalk data packet out the tunneling
port, then observes whether that packet loops back through a port
connected to its local internet. The exterior router sends the packet
to the address corresponding to its own address on the network that
it suspects may actually be a shadow copy of a network connected
directly to one of its ports.
LOOP PROBE PACKET: A Loop Probe packet is an AppleTalk data packet
that an exterior router sends out a tunneling port to confirm or deny
the existence of a loop. It is a new type of RTMP packet and has the
function code 4. Figure 4-7 shows the format of a Loop Probe packet.
<<Figure 4-7 Loop Probe packet format>>
The source node ID and source network number in a Loop Probe packet
should be those of the port for which the exterior router received
loop-indicative information. An exterior router can send a Loop Probe
packet through any socket.
A Loop Probe packet's destination network number is the network
number to which that port's network number would be remapped if the
loop-indicative information were actually a shadow copy of that
port's routing information. Refer to the port's actual network number
as nu(ns<=nu<=ne). If the network range in the loop-indicative
information were rs through re, the packet's destination network
number would be rs+nu-ns.
A Loop Probe packet's destination node ID is that of the exterior
router on the port for which the exterior router received loop-
indicative information. The packet's destination socket is socket 1-
the RTMP socket.
A Loop Probe packet's data field always begins with a long word that
has the value 0. The remainder of the data field should contain
information that the exterior router that sends the packet can use to
identify that packet if it receives the packet through its local
internet. An exterior router might receive a Loop Probe packet sent
by another exterior router if a loop did not actually exist and the
other exterior router sent a Loop Probe packet to a random node on
the internet rather than to itself. The node receiving the Loop Probe
packet might be an exterior router that also sent a Loop Probe
packet. To prevent an exterior router that receives such a Loop Probe
packet from falsely concluding that a loop exists, the exterior
router sending the packet must insert sufficient data in that
packet's data field to allow it to recognize the packet as the one it
sent.
An exterior router initiating a loop-investigation process should
forward a Loop Probe packet through the tunnel to the next internet
router for the packet's destination network-just as it would any
other AppleTalk data packet. This next internet router should always
be the exterior router that sent the loop-indicative information.
A remapping exterior router forwarding a Loop Probe packet into its
local internet must process that packet differently from other
AppleTalk data packets in one way. If the exterior router's remapping
database does not include the source network number in the packet's
DDP header, the exterior router should forward the packet without
remapping the source network number. At startup, remapping
information is generally unavailable. However, the absence of
remapping information should not affect the loop-detection process.
If a loop exists, the exterior router that originally sent the Loop
Probe packet receives that packet through its local internet. The
data in the packet remains unchanged. The exterior router can use
that data to confirm the existence of a loop on the internet.
If a Loop Probe packet returns to the exterior router through the
tunnel out which it was sent, a loop exists between two other
exterior routers on the tunnel, but does not involve the exterior
router that sent the packet. The sending router need take no action.
An exterior router should send a Loop Probe packet at least four
times. The retransmission timeout should be no less than two
seconds. Once the exterior router has retransmitted a Loop Probe
packet four times and that packet has not returned to the exterior
router through its local internet, the exterior router determines
that no loop exists.
If the exterior router receives a Loop Probe packet containing the
correct data field through its local internet, this confirms the
existence of a loop. The exterior router should deactivate the
tunneling port, log an error, and set the state of all routing-table
entries for exterior routers connected to that tunnel to BAD.
NOTE: The exterior router need not deactivate a tunneling port on
which it detects a loop. However, the exterior router must disconnect
with the exterior router that sent the loop-indicative information.
However, disconnecting from only that exterior router might
inadvertently result in a partially connected tunnel or in a lack of
connectivity through the tunnel that would be difficult to detect.
LIMITATIONS OF LOOP DETECTION: This loop-detection process becomes
ineffective if, at some point in the loop, another exterior router
hides networks connected directly to the ports of the exterior
router that sent the Loop Probe packet
clusters the network ranges of networks connected directly to the
exterior router's ports
is not remapping network numbers-resulting in partial network-
number remapping
In such cases, the exterior router that initiated the loop-detection
process may never receive loop-indicative information, even though a
loop exists.
Using Alternative Paths
AURP provides two mechanisms that allow a network administrator to
configure a port on an exterior router to forward packets over an
alternative path to a network only when the primary path to that
network is unavailable:
hop-count weighting
backup paths
By configuring hop-count weighting on a port or configuring a port as
a backup path, an administrator can reduce the amount of traffic on a
slow point-to-point link or tunnel. These mechanisms are also
available on links using RTMP.
Hop-Count Weighting
A network administrator can configure hop-count weighting on a port
to increase the routing distance through a port by counting a link to
another exterior router as more than one hop. Increasing the routing
distance through a port may cause traffic to traverse an alternative
path. The routers on an internet forward packets over an alternative
path to a network if
an alternative path is available
the perceived distance to that network is shorter over the
alternative path
However, a network administrator should not set the hop-count weight
for a link so high that distances between networks across that link
exceed the limit of 15 hops. Otherwise, if the link on which hop-
count weighting was active were the only available path, the exterior
router would be unable to provide full connectivity to all networks
on the internet.
To implement hop-count weighting, an exterior router should make the
following changes to RTMP and the DDP routing process:
When an exterior router uses RTMP or AURP to broadcast the
networks that are accessible through a link on which hop-count
weighting is active, the distance attributed to each network should
equal its actual distance plus the hop-count weight specified.
Before an exterior router forwards a DDP data packet to a network
across that link, it should add the specified hop-count weight to the
value in the hop-count field of the packet's DDP header.
Backup Paths
A network administrator can configure a port on an exterior router as
a backup path. The routers on an internet forward AppleTalk data
packets across a backup path only when an exterior router on which a
port is configured as a backup path determines that no other path to
a specific network or networks is available.
Regardless of the distance that routing packets must traverse across
a primary path to a network, routers on the internet use the primary
path as long as it remains available. When the exterior router on
which a port is configured as a backup path determines that the
primary path to a network is no longer available and that network is
accessible across the backup path, the exterior router broadcasts
routing information about networks accessible across the backup path
to its local internet.
NOTE: An exterior router at each end of the backup path maintains a
complete routing table for the entire internet, and sends AURP or
RTMP routing packets across the backup path, regardless of whether
the backup path is in use.
If an exterior router is currently providing access to a network
through a backup path and the primary path to that network again
becomes available, the exterior router starts broadcasting routing
information that indicates the primary path to the network, rather
than the backup path. The routers on the exterior router's local
internet can again use the primary path to that network.
PROBLEMS REACTIVATING THE PRIMARY PATH: When an exterior router is
providing access to a network through a backup path and the primary
path to that network again becomes available, it is possible that the
exterior router may not become aware that the primary path is
available. This can occur when other routers in the exterior
router's local internet use the backup path, rather than a newly
available primary path, because the backup path traverses a shorter
distance. The other routers have no way of knowing that an active
path is a backup path. They do not notify the exterior router
connected to the shorter backup path about the primary path's
availability.
Once the primary path becomes unavailable and routers on the internet
use the backup path, reconfiguring the exterior router so it will
again use the primary path may be necessary.
Network Management
A Simple Network Management Protocol (SNMP) Management Information
Base (MIB) allows the remote management of tunneling, routing-
information propagation, and the representation of wide area routing
information. Refer to the "IETF Draft: Macintosh System MIB" on
E.T.O. for detailed information about the structure and content of
AURP's many remotely manageable parameters.
Network-Number Remapping and Network Management
The packets of network-management protocols-regardless of whether
SNMP forms their basis-often contain information about specific
AppleTalk network numbers. An exterior router cannot remap network
numbers in data. Therefore, when querying devices across a tunnel,
network-management protocols always return network numbers that have
not been remapped. However, a remote network-management station using
SNMP could use the AURP MIB to query a remapping exterior router to
obtain remapped network numbers from the exterior router's remapping
database.
Network Hiding and Network Management
Even though an exterior router is hiding a network from a particular
port, that network's routing information should be available to a
network-management station across that port. Network hiding should
not affect network management. Thus, an exterior router should still
return routing information for hidden networks in responses to
network-management queries. A network-management station using SNMP
could use the AURP MIB to query an exterior router to obtain
information about hidden networks.
Unaffected Network-Management Packets
Network-management packets that network-number remapping and network
hiding should not affect include:
SNMP requests received through an AURP port
SNMP responses sent through an AURP port
RTMP responses sent through an AURP port
Route Data responses sent through an AURP port
ZIP queries received through an AURP port
ZIP requests received through an AURP port
ZIP replies sent through an AURP port
APPENDIX: IMPLEMENTATION DETAILS
This appendix provides information that may assist you in
implementing AURP. It does not specify protocol requirements.
Developers implementing AURP routers may want to purchase the Apple
Internet Router, a product of Apple Computer. The Apple Internet
Router provides many additional examples of how you might implement
the various features of AURP.
State Diagrams
Figure A-1 shows the state diagram for the AURP data receiver.
<<Figure A-1 AURP data receiver state diagram>>
Figure A-2 shows the state diagram for the AURP data sender.
<<Figure A-2 AURP data sender state diagram>>
AURP Table Overflow
It is possible for an AURP data receiver to have insufficient storage
capacity to maintain all of the routing information sent to it by a
peer data sender. Because the data sender does not retransmit routing
information, the data receiver should set a flag indicating that a
table-overflow condition exists. If additional storage later becomes
available, the data receiver should try to obtain the missing
information. If zone information is lost, the data receiver can
obtain complete zone information by sending the appropriate ZI-Req
packets. If network information is lost, the data receiver should
send an RI-Req to obtain the complete routing table.
A Scheme for Updates Following Initial Information Exchange
As described in the section "Sending Updates Following the Initial
Exchange of Routing Information" in Chapter 3, an exterior router
must present complete and accurate routing information to all
exterior routers, even if a new connection is established with that
exterior router when the exterior router has update events pending-
that is, update events not yet sent in RI-Upd packets. This section
details one scheme for presenting routing information to both new and
old connections correctly, even if multiple update events occur for a
given network in an update period during which the exterior router
establishes new connections. More complex schemes could provide more
up-to-date information, at the cost of greater implementational
complexity.
Assume that an exterior router has a number of AURP connections
established with other routers and that a series of update events for
a given network occur in the exterior router's local internet. Once
these events have occurred, but before the update interval expires-
that is, before the exterior router sends RI-Upd packets over its
connections-the exterior router establishes a new AURP connection
with another exterior router and receives an RI-Req packet from that
exterior router. This section describes the information about the
network that the RI-Rsp packet should contain. It also describes the
update event that the exterior router should send in the next RI-Upd
packet, assuming that it receives no additional update events for the
network.
Two scenarios are possible. In the first scenario, a network for
which the exterior router is not exporting information at the
beginning of an update interval either comes up in the exterior
router's local internet, or a new path to the network that is shorter
than the path through the tunnel comes up in the exterior router's
local internet. In either case, the RI-Rsp packet should not include
the new network.
By not including the new network in the RI-Rsp, the implementation
can simply continue to follow the state diagram provided in the
section "Sending Routing Information Update Packets" in Chapter 3. If
only an NDC event or no additional update event occurs for the
network, the next RI-Upd packet that the exterior router sends on
both old and new connections should contain an NA event for the
network. If an NRC or ND event occurs for the network, the exterior
router should not include an event tuple for the network in the RI-
Upd. This sequence matches the state diagram precisely. If the RI-Rsp
did contain information about the network, new connections would
require a different state diagram.
In the second scenario, the exterior router initially exports
information for a network, then an update event occurs for that
network. In all cases, the RI-Rsp packet should contain up-to-date
information about the network from the exterior router's central
routing table, and the next RI-Upd packet should contain the specific
event that the state table indicates for that network. For example,
if an ND or NRC event occurs for the network, the network should not
be included in the RI-Rsp, while if an NDC event occurs, it should be
included in the RI-Rsp.
This scheme may result in some exterior routers receiving unexpected
update events, which they must process as specified in the section
"Processing Inconsistent Update Events" in Chapter 3. For example,
another exterior router with which the exterior router establishes a
new connection might receive an ND or NRC event for a network of
which it was unaware. The receiving exterior router would ignore the
event.
In an alternative way of evaluating and possibly implementing this
scheme, the information for a given network that is sent in the
initial RI-Rsp packet depends on the particular update event that is
pending for that network when the exterior router sends the RI-Rsp.
Specifically, an exterior router should include a network for which
it has an update event pending in the RI-Rsp packet only if the
pending update event is an NDC. Otherwise, the exterior router should
not include the network in the RI-Rsp. Following this RI-Rsp, the
exterior router sends RI-Upd packets as usual, which include other
pending events, as necessary.
Implementation Effort for Different Components of AURP
AURP contains various enhancements to AppleTalk routing. The only
components of AURP that are required are those specified in Chapter
3. The required components of AURP provide the functionality needed
to replace RTMP and ZIP, completely and compatibly, on tunnels and
point-to-point links, without losing any functionality and with
greatly reduced routing traffic. Optional features of AURP provide
functionality beyond that of RTMP and ZIP. This functionality is
especially useful in a wide area network environment.
The chart shown in Figure A-3 provides rough estimates of the
percentage of development time needed to implement, debug, and test
the various components of a complete AURP implementation. It can
provide developers with some idea of the implementational complexity
of these components and help developers make tradeoffs between
features and development time.
<<Figure A-3 Implementation effort for AURP>>
Creating Free-Trade Zones
A useful feature of AURP is that it allows a network administrator to
create free-trade zones. A free-trade zone is a part of an internet
that is accessible by two other parts of the internet, neither of
which can access the other. An administrator might create a free-
trade zone to provide some form of interchange between two
organizations that otherwise want to keep their internets isolated
from each other, or between two organizations that otherwise do not
have physical connectivity with one another.
AURP allows the creation of free-trade zones in two ways. In one
method, described in the section "Fully Connected and Partially
Connected Tunnels" in Chapter 2, an administrator intentionally
creates a partially connected tunnel. The administrator configures
the exterior router to connect with two exterior routers between
which a free-trade zone is to be established, but does not configure
those exterior routers to connect with one another.
The second method of using AURP to create a free-trade zone involves
the use of network hiding. An administrator can configure a single
router to create a free-trade zone. No AURP tunnel need exist. As
shown in Figure A-4, three ports are configured on a router. One port
connects to the free-trade zone, while the other two ports connect to
the parts of the internets that are otherwise isolated from one
another.
<<Figure A-4 Creating free-trade zones>>
On the port connected to the free-trade zone, the administrator does
not configure the router to hide any networks. The exterior router
exports all networks from both organizations to the free-trade zone.
On each port connected to an organization's internet, the
administrator configures the router to export only the networks from
the free-trade zone. The exterior router hides all the networks from
the other organization's internet. In this way, each organization has
access to the networks in the free-trade zone, and vice versa, but
not to the networks in the other organization's internet.
Implementation Details for Clustering
The data structures that an exterior router uses to maintain
information about clustering are key to the implementation of
clustering. An exterior router should
maintain mappings between the actual domain identifier and network
range; the remapped network range; and the associated cluster
maintain zone lists for each actual network and for the cluster as
a whole
use data structures that allow parts of the information to be
marked for deletion, while maintaining that information for possible
later reuse-for example, if a network goes down, then comes back up
use data structures that are bidirectional-supporting both the
conversion of a single FwdReq into multiple FwdReq packets and the
manipulation of individual networks within the cluster
An exterior router can cluster any network numbers that is has
remapped into an available range of contiguous network numbers. From
both an implementation and a management point of view, it is
generally best for an exterior router to cluster all network numbers
that it receives from a particular exterior router at a given time.
For example, it may be desirable to cluster all of the network
numbers included in the initial information exchange with a
particular exterior router, then later, to cluster all of the network
numbers received in NA events in a given RI- Upd packet.
Maintaining compatibility with AppleTalk Phase 2 complicates the
implementation of clustering. An exterior router can include a
maximum of 255 zones in a cluster. This limit may prevent the
exterior router from clustering all of the network numbers that it
receives at one time. When an exterior router receives a list of
networks from another exterior router, it does not know how many
different zone names the networks use. The exterior router does not
have this information until it receives the associated ZI-Rsp
packets. Therefore, an exterior router should not build a cluster
until it has received a complete zone list for the network numbers
being clustered. Once the exterior router has complete zone
information for the network numbers, it can cluster the maximum
number of network numbers allowed by the 255 zone limit.
AURP does not specify the method by which an exterior router, when
forming a cluster, should determine the hop count for that cluster-
that is, the apparent distance in hops to the single extended network
that represents the cluster. Possible implementation options include
always setting the hop count to a constant value
setting the hop count to the minimum, average, or maximum of the
hop counts for the networks within the cluster
In a large internet, setting the hop count for a cluster too high may
make the networks in that cluster unreachable from some networks in
the local internet of the exterior router that is clustering the
network numbers.
Modified RTMP Algorithms for a Backup Path
In the following RTMP maintenance algorithms defined in Inside
AppleTalk, the backup path is an RTMP link. These algorithms can be
adapted to AURP according to the architectural model described in the
section "AURP Architectural Model" in Chapter 3. Proposed
modifications to these algorithms appear in boldface Courier font.
On Receiving an RTMP Data Packet Through a Port
IF P is connected to an AppleTalk network AND P's network
number range = 0
THEN BEGIN
P's network number range := packet's sender network
number range;
IF there is an entry for this network number range
THEN delete it;
Create a new entry for this network number range with
Entry's network number range := packet's sender
network number range;
Entry's distance := 0;
Entry's next IR := 0;
Entry's status := Good;
Entry's port := P;
END;
FOR each routing tuple in the RTMP Data packet DO
IF there is a table entry corresponding to the tuple's
network number range
THEN Update-the-Entry
ELSE IF there is a table entry overlapping with the
tuple's network number range
THEN ignore the tuple
ELSE IF P is not a backup path
THEN Create-New-Entry
ELSE Create-New-Tentative Entry;
Update-the-Entry
IF (Entry's port is not a backup port AND P is a
backup port)
THEN Return; {Ignore tuple}
IF (Entry's state = Bad) AND (tuple distance <15)
THEN Replace-Entry
ELSE
IF Entry's distance >= (tuple distance +1) AND (tuple
distance <15)
OR (Entry's port is a backup port and P is not a
backup port)
THEN Replace-Entry
ELSE IF Entry's next IR = RTMP Data packet's sender node
address AND Entry's port = P
THEN IF tuple distance <> 31 THEN BEGIN
Entry's distance := tuple distance + 1;
IF Entry's distance < 16
THEN Entry's state := Good
ELSE Delete the entry
END
Else Entry's state := Bad;
An exterior router uses the Create-New-Tentative-Entry algorithm when
it discovers a previously unknown network across a backup path. An
exterior router should not add an entry to the routing table being
broadcast to its local internet until it determines definitely that
no alternative path to a network is available. While waiting for
another path to a network to become available, the exterior router
temporarily stores the routing-table entry in a tentative routing
table, as defined by the following algorithm:
Create-New-Tentative-Entry
IF tentative entry for tuple's network number range does not
already exist
THEN BEGIN
Tentative entry's network number range =
tuple's network number range;
Tentative entry's distance := tuple's distance;
Tentative entry's next IR = packet's node address;
Tentative entry's port := P;
Start a TBD-minute timer for this entry;
END;
WHEN timer for this entry expires
IF there is a table entry corresponding to or
overlapping with the tentative entry's network
number range
THEN ignore the entry
ELSE Create-New-Entry; {using data from the tentative
entry}
Delete tentative entry;
Security Considerations
This memo discusses a weak form of security called network hiding or
device hiding. More general concerns about security are not
addressed.
Author's Address
Alan B. Oppenheimer
Apple Computer, M/S 35-K
20525 Mariani Avenue
Cupertino, California 95014
Phone: 408-974-4744
EMail: Oppenheime1@applelink.apple.com
Note: The author would like to acknowledge the contribution of Pabini
Gabriel-Petit here at Apple, who translated the engineering
specification into human-readable form.