IEN 196 11 September 1981
ISSUES INVOLVING NON-ROUTING GATEWAYS
B. Bowman & P. Cook
Ford Aerospace & Communications Corporation
Colorado Springs, Colorado
(303-471-9110)
IEN # 196
September 11, 1981
IEN 196 11 September 1981 INTRODUCTION This note presents some proposed modifications to the gateway routing algorithm and the protocol for exchanging routing information described in IEN #109, "How To Build A Gateway". The described algorithm modifications were defined as a result of problems encountered in the implementation of the gateway to gateway control protocol specified in IEN # 109. The problems encountered in implementing the algorithm involve the mechanisms for incorporating non-routing gateways in the catenet. Therefore, this discussion focuses on modifications designed to facilitate use of non-routing gateways in concert with routing gateways in the catenet. As indicated above, the issues discussed resulted from our implementation of the IEN # 109 algorithm. Some initial implementation questions concerning interpretation of the rules for assembling routing updates from non-routing gateways led to our analysis of the design of this routing strategy. From routing strategy design issues, our study progressed to questions regarding the intended/optimal role of non-routing gateways in the catenet. As a result, this note presents specific modifications to IEN # 109 necessary for successful implementation and also includes discussion of the broader issues of the role of the non-routing gateway in the catenet. Finally, we propose a modification to the routing information exchanged in the IEN # 109 algorithm, which we believe has significant advantages in reducing the logical complexity of the algorithm and traffic between gateways. Although we have looked at design approaches of other authors in this field, we have not done an exhaustive search to determine the "novelty" of our approach. We would also like to stress that our goal was not to design a new routing algorithm but simply to implement the IEN # 109 algorithm. In a very real sense, it can be said that we backed into these routing design issues as a natural consequence to our implementation efforts. I. Non-Routing Gateways It should be noted that any solution must be based on an understanding regarding the intended role of the non-routing gateway in the catenet. Unambiguous rules for incorporating non-routing gateways in the routing scheme can only be specified when the intended role is clearly defined. An optimal solution, then, would involve clarification of the role of the non-routing gateway followed by revision of the routing specification consistent with the defined role. -2-
IEN 196 11 September 1981
IEN # 109, "How to Build a Gateway", contains a section (Sect.9,
Page 7) discussing the interface between routing gateways and
non-routing gateways and, in particular, discussing the use of a
non-routing gateway by a routing gateway for routing packets.
Two areas of this section are problematic with respect to a
successful implementation. These are, (1) initialization with
respect to the non-routing gateway and (2) computation of the
minimum distance vector.
A. Initialization
IEN # 109 gives the following instructions for initializing with
respect to a non-routing neighbor gateway.
* "For each non-routing neighbor gateway of gateway G1, compute
the routing update that would be sent to G1 assuming that all
gateways and network connections are operational. These routing
updates are assembled in G1."
This rule can be interpreted in one of two ways. The first is to
assemble the non-routing gateway's routing update showing actual
distances to each network from the non-routing gateway. Figure 1
shows an example of this interpretation.
In this example, Gateway (B) is a non-routing gateway and Gateway
(A) is a routing gateway. Initially, G(A) assembles G(B)'s
update as actual distances from G(B) to the 3 networks. Based on
this initialization, G(A) assumes that it is a distance of 1 from
Net.#1 because the non-routing gateway provides the only path to
Net.#1. G(A) also assumes that it is directly (0) connected to
Nets.#2 and #3. G(A) builds its initial minimum distance vector
reflecting these distances.
Assume, then, that G(A)'s link to Net.#3 goes down at some time.
When this happens, G(A) recomputes it's minimum distance vector.
Since G(A) is no longer connected to Net.#3, there is no path
available unless the non-routing gateway's path is used. G(B)'s
update indicates a distance of 1 to Net.#3. Therefore, G(A)
assumes a path to Net.#3 of distance 2 through G(B). Of course,
there is no path to Net.#3 but G(B) does not accept or transmit
routing tables so any packets addressed to Net.#3 will shuttle
indefinitely (until the IP4 time to live field is decremented to
zero) from G(A) to G(B) to G(A), etc. When this example is
extended to larger catenets, the shuttling problem persists and
simply involves higher distance shuttles. Therefore, this
interpretation of the initialization instructions is unworkable.
-3-
IEN 196 11 September 1981
FIGURE 1: INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
"ACTUAL DISTANCE" METHOD
CATENET CONFIGURATION
__________ __________ __________
| | | | | |
| NET #1 |----G(B)----| NET #2 |----G(A)----| NET #3 |
|__________| |__________| |__________|
where
G(A) = Gateway A: Routing Gateway
G(B) = Gateway B: Non-Routing Gateway
G(A) DISTANCE MATRIX AFTER INITIALIZATION
NETWORKS
GATEWAYS 1 2 3
A 1 0 0
B 0 0 1
G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
NETWORKS
GATEWAYS 1 2 3
A 1 0 2
B 0 0 1
-4-
IEN 196 11 September 1981 The other possible interpretation of the IEN # 109 instructions is to assemble the non-routing gateway's update showing actual distances to each network from the non-routing gateway only when the non-routing gateway is as close to or closer to the network than the gateway assembling the routing update. This interpretation incorporates a rule from Section 7, page 7 regarding computation of routing updates. Figure 2 shows an example of this interpretation. In this example, Gateway (B is a non-routing gateway and Gateways A and C are routing gateways. The example is presented from the perspective of Gateway A. Gateway B's update is initialized showing 0 distance to Nets.#1 and #2. A distance of 1 is shown to Net.#3 because Gateway B is as close to Net.#3 as is Gateway A. An infinite distance is shown to Net.#4 because Gateway A is closer to Net.#4 than Gateway B. The example shows receipt of a routing update from Gateway C which shows Gateway C's distances calculated according to the rules for preparation of a routing update. Gateway A calculates its minimym distance vector as 0 distance from Nets.#2 and #4 because they are directly connected, distance 1 from Net.#1 because of the path through Gateway B and distance 1 from Net.#3 because of the path through Gateway C. Assuming that Gateway C loses connectivity to Network #3 at some time, Gateway C would send Gateway A a new routing update showing infinite distance to Network #3. Gateway A would then recalculate its minimum distance vector. G(A) would assume that the only path to Net.#3 is through the non-routing gateway (G(B)) and that this is a path of distance 2. This occurs because G(B) neither accepts nor transmits routing updates so it is unaware of the connectivity loss and G(A) is assembled with G(B)'s routing update so there is no provision for changes to this information in G(A). The situation is complicated by the fact that G(A), upon recalculation of its minimum distance vector, will transmit a routing update to G(C) showing the distance of 2 from G(A) to Network #3. G(C) will recompute its distance vector to show a path of distance 3 from G(C) to Network #3. Since no path actually exists and all 3 Gateways believe a path exists, packets addressed to Net.#3 will shuttle indefinitely (until the IP4 time to live field is decremented to zero). Thus it seems that Thus it seems that both interpretations of the IEN # 109 instruction for assembling the non-routing gateway's update present serious problems. -5-
IEN 196 11 September 1981
FIGURE 2: INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
"TAILORED UPDATE" METHOD
CATENET CONFIGURATION
__________
__________ __________ | |
| | | |----G(A)----| NET #4 |
| NET #1 |----G(B)----| NET #2 | |__________|
| | | | __________
| | | | | |
|__________| |__________|----G(C)----| NET #3 |
|__________|
where
G(A) = Gateway A: Routing Gateway
G(B) = Gateway B: Non-Routing Gateway
G(C) = Gateway C: Routing Gateway
G(A) DISTANCE MATRIX AFTER INITIALIZATION
NETWORKS
GATEWAYS 1 2 3 4
A 1 0 1 0
B 0 0 1 INF
C 1 0 0 INF
G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
NETWORKS
GATEWAYS 1 2 3 4
A 1 0 2 0
B 0 0 1 INF
C 1 0 INF INF
-6-
IEN 196 11 September 1981
B. Computation of the Minimum Distance Vector
IEN # 109 goes on to provide the following instructions for
calculating the minimum distance vector when non-routing gateways
are included.
* "The gateway, G(A), first computes its minimum distance
vector using only the routing updates from neighbors that
participate in routing. If the minimum distance to any
network is infinity, i.e., the network is unreachable via
any of the routing gateways, then the minimum distance to
that network is re-computed using the routing update
compiled for the non-routing neighbor gateway."
This rule appears inefficient if we look at the example shown in
Figure 3. In this example, Gateway B is a non-routing gateway
and Gateways A and C are routing gateways. The example is
presented from the perspective of Gateway A and the focus of the
example is on the distance to Network #1.
G(A) is assembled with the update of G(B) (the non-routing
gateway) and G(B) shows a distance of 0 from Net.#1 since it is
directly connected. In our example, G(A) has received an update
from G(C). G(C) shows a distance of 1 to Net.#1 based on its
path through G(B). According to the rule, G(A) has to prefer the
route through G(C) since G(C) is a routing neighbor and G(B) is
non-routing. Therefore, G(A) assumes a path of distance 2 to
Net.#1 and G(A) will route to G(C) any packets addressed to
Net.#1. On receipt of the packet addressed to Net.#1, G(C) will
route the packet to G(B) where it will be delivered to Net.#1.
This solution is not unworkable but it does cause delay and
inefficiency by forcing an additonal transfer with respect to the
optimal path. In a geographically dispersed network, this delay
and additional network traffic could become significant.
-7-
IEN 196 11 September 1981
FIGURE 3: COMPUTATION OF THE MINIMUM DISTANCE VECTOR
CATENET CONFIGURATION
__________
__________ __________ | |
| | | |----G(A)----| NET #4 |
| NET #1 |----G(B)----| NET #2 | |__________|
| | | | __________
| | | | | |
|__________| |__________|----G(C)----| NET #3 |
|__________|
where
G(A) = Gateway A: Routing Gateway
G(B) = Gateway B: Non-Routing Gateway
G(C) = Gateway C: Routing Gateway
G(A) DISTANCE MATRIX
NETWORKS
GATEWAYS 1 2 3 4
A 2 0 1 0
B 0 0 1 INF
C 1 0 0 1
-8-
IEN 196 11 September 1981
C. Proposed Solution to Non-Routing Gateway Problems
Role Clarification
As indicated above, a solution to the problems in incorporation
of non-routing gateways must address clarification of the role of
the non-routing gateway in the catenet. Three possible roles for
the non-routing gateway have been identified and are discussed in
this section. In general, we see potential for non-routing
gateways to be used to provide 1) the "only" route, 2)
"redundant" routes or 3) "parallel" routes. Use of the
non-routing gateway to provide "redundant" and "parallel" routes
is discussed in Section D.
Figure 4 illustrates use of the non-routing gateway to provide
the "only" route. This role basically restricts the use of
non-routing gateways to allow (i.e., recognize) them in the
catenet only when the non-routing gateway provides the "only"
connection to a network or network branches.
Although other possible roles will be discussed , this particular
role definition is the one we recommend. Using non-routing
gateways where they provide the "only" possible route seems the
most logical use of these gateways and also lends itself most
easily to unambiguous rule definition. The mechanisms for
incorporating non-routing gateways consistent with the "only"
route role are described in the following paragraphs.
-9-
IEN 196 11 September 1981
FIGURE 4: NON-ROUTING GATEWAY AS "ONLY" ROUTE
CATENET CONFIGURATION
__________ __________
| | | |
| NET #1 |----G(R)----| NET #3 |
|__________| |__________|
| |
| |
G(R) |
| |
| |
__________ |
| | |
| NET #2 |----G(R)----------|
|__________|
|
|
G(NR)
|
|
__________
| |
| NET #4 |
|__________|
|
|
etc. (network branch)
G(R) = Routing Gateway
G(NR) = Non-Routing Gateway
NOTE: In this configuration, the non-routing gateway provides
the only connection to Network #4.
-10-
IEN 196 11 September 1981
Rules for "Only" Route Role
It appears that the initialization and route computation problems
associated with non-routing neighbor gateways described above,
could be solved by a few rule changes. The proposed new rules
are as follows:
* IEN # 109 Rule:
For each non-routing neighbor gateway of gatewayG(A),
compute the routing update that would be sent to G(A)
assuming that all gateways and network connections are
operational. These routing updates are assembled in G(A).
New Rule:
F or each non-routing neighbor gateway of gateway G(A),
compute the routing update that would be sent to G(A)
assuming that all gateways and network connections are
operational. In computing these routing updates, show
actual (non-infinite) distances to networks which are
reachable only through the non-routing gateway. Networks
which are reachable by a routing gateway shall be
initialized with distance equal infinity. These routing
updates are assembled in G(A).
IEN # 109 Rule:
T he gateway, G(A), first computes its minimum distance
vector using only the routing updates from neighbors that
participate in routing. If the minimum distance to any
network is infinity, (i.e., the network is unreachable via
any of the routing gateways), then the minimum distance to
that network is re-computed using the routing update
compiled for the non-routing neighbor gateway.
New Rule:
The gateway, G(A), first computes its minimum distance
vector using all the routing updates (including updates from
both routing and non-routing gateways).
These proposed rule changes, taken together, cause non-routing
gateways to be used only when they provide the only path to a
network or string of networks. These rules also eliminate the
possibility of selecting any other path (i.e., through a routing
gateway) when a non-routing gateway provides the only path.
Thus, non-routing gateways are used for packet routing if and
only if they provide the only route to a destination.
-11-
IEN 196 11 September 1981
Figure 5 shows how the new rules solve the problems identified in
Examples 1, 2, and 3. In this example, Gateway B is a
non-routing Gateway and Gateways A and C are routing gateways.
The example is presented from the perspective of Gateway A. The
G(A) Distance Matrix after initialization shows that the problem
depicted in Figure 3 (computation of the minimum distance vector)
is resolved through application of the new rules. Since the
minimum distance vector is calculated based equally on the
routing and non-routing gateway updates, the shortest path (and
only path) to Network #1 is selected by both routing gateways
(G(A) and G(C)).
The G(A) Distance Matrix resulting from loss of connectivity to
Net.#4 shows that the problem depicted in Figure 1
(Initialization of non-routing gateway update) is resolved
through use of the new rules. Since the assembled non-routing
gateway update no longer shows paths to networks reachable by
routing gateways, G(A) is able to determine that Net.#4 is now
unreachable and does not attempt to route traffic to Net.#4
through Gateway (B).
The G(A) Distance Matrix resulting from loss of connectivity to
Net.#3 shows that the problem depicted in Figure 2
(Initialization of non-routing Gateway update) is also resolved
through application of the new rules. This problem is resolved
because the assembled non-routing gateway update no longer show
paths to networks reachable by routing gateways. Thus, when
Net.#3 is declared unreachable by Gateway C, G(A) determines that
Net.#3 is unreachable by all gateways.
-12-
IEN 196 11 September 1981
FIGURE 5: PROPOSED SOLUTION
CATENET CONFIGURATION
__________
__________ __________ | |
| | | |----G(A)----| NET #4 |
| NET #1 |----G(B)----| NET #2 | |__________|
| | | | __________
| | | | | |
|__________| |__________|----G(C)----| NET #3 |
|__________|
where
G(A) = Gateway A: Routing Gateway
G(B) = Gateway B: Non-Routing Gateway
G(C) = Gateway C: Routing Gateway
G(A) DISTANCE MATRIX AFTER INITIALIZATION
NETWORKS
GATEWAYS 1 2 3 4
A 1 0 1 0
B 0 INF INF INF
C 1 0 0 INF
G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#4)
NETWORKS
GATEWAYS 1 2 3 4
A 1 0 1 INF
B 0 INF INF INF
C 1 0 0 INF
G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
NETWORKS
GATEWAYS 1 2 3 4
A 1 0 INF 0
B 0 INF INF INF
C 1 0 INF INF
-13-
IEN 196 11 September 1981
D. Other Possible Approaches
Redundant Role
Restricting the use of non-routing gateways in the catenet to
locations where they provide the only configured path and
adoption of the corresponding rule changes is our recommended
solution to the implementation problems we've identified. In
reviewing IEN # 109 and it's predecessor IEN # 30, we find it
difficult to determine the intended role of the non-routing
gateways.
Both papers indicate that non-routing gateways are to be used to
forward traffic only when they provide the only route to a
network. This seems to indicate that the initial intent was to
use non-routing gateways in the role defined above (i.e. "only"
route role). On the other hand, it's possible that the authors
actually intended to use the non-routing gateways to provide the
only configured path and to provide backup routes to networks
connected by routing gateways. This role for non-routing
gateways is what we have called the "redundant " role. Figure 6
illustrates this use of non-routing gateways. This role is
basically an addition to the "only" route role.
Here the non-routing gateway can also be configured in parallel
with a routing gateway but the non-routing path is only used if
connectivity through the routing gateway is lost. Thus, the
non-routing gateway is used as a backup for the routing gateway.
As long as the routing gateway and its connections are
functional, the non-routing gateway is not used to forward any
traffic.
749/
-14-
IEN 196 11 September 1981
FIGURE 6: NON-ROUTING GATEWAY AS "REDUNDANT" ROUTE
CATENET CONFIGURATION
__________ __________
| |----G(NR)---| |
| NET #1 | | NET #2 |
|__________|----G(R)----|__________|
| |
| |
G(R) G(R)
| |
| |
__________________________________
| |
| NET #3 |
|__________________________________|
WHERE
G(R) = Routing Gateway
G(NR) = Non-Routing Gateway
-15-
IEN 196 11 September 1981
It seems that this second role interpretation is implementable.
Basically, the corresponding rules would be:
1) Assemble routing update showing direct network connections
and actual distances to networks reachable only by the
non-routing gateway.
2) Calculate minimum distance vector using non-routing gateway
paths only when they provide the only route.
Implementing this role concept, then, involves the added
complexity of the two stage minimum distance vector calculation
(with bias toward routing gateway paths). While this may be the
role anticipated by the authors of IEN # 109 and # 30, we feel
the backup role is of little added value for the additional
complexity involved. It seems unlikely to us that networks would
buy a processor which was to be idle the majority of the time.
Instead, if need existed for a backup, it seems a routing gateway
would be a better choice and cost efficient as it could increase
bandwidth as well as providing redundancy.
Parallel Role
At the other end of the spectrum, it is possible that some group
might wish to use non-routing gateways in any configuration where
routing gateways can be used. In this role, which we call the
"parallel" role, non-routing gateways are used to provide
additional (parallel) paths and thus effectively increase
bandwidth. This role differs from the "redundant" route role in
that non-routing gateways are used to forward traffic even when
they do not provide the only path. It is this facility which
allows the effective increase in real-time bandwidth.
Whether this intended role is implementable is an open question.
Obviously, it would be more complex to implement and would
basically require a redefinition of some of the ground rules. We
rejected this possible role application because it significantly
reduces catenet reliability and seems to defeat the whole idea
behind the routing algorithm function. If non-routing gateways
are used routinely to forward traffic in parallel with routing
gateways, connectivity changes occuring with the non-routing
gateways are unreported and therefore the non-routing gateways
could easily become traffic sinks.
-16-
IEN 196 11 September 1981
We felt that the only possibility for using non-routing gateways
to increase bandwidth would be to implement the role outside the
gateway-gateway control protocol. This function could be
implemented as a host function where there was an understanding
between hosts on two networks that traffic would be split on some
basis between routing and non-routing gateways. Thus, the
decision to sacrifice catenet reliability in favor of increased
traffic flow would be made by the parties involved without
involving any gateway control function awareness or
participation.
II. Routing Update Calculations
In the process of designing the gateway routing software IAW IEN
# 109, we determined that a subset of the routing algorithm rules
dictated a logically cumbersome implementation. These rules,
from IEN # 109 are as follows:
A. "The gateway reports its distance to a network to a
neighbor only if it is as close or closer to a network than
its neighbor." (p.7)
B. "The gateway maintains a copy of the most recent routing
updates that it sent to each of its neighbors. The gateway
computes the new routing updates to send to each of its
neighbors. If any of these routing updates are different
than the preceding updates, then the gateway sends new
routing updates to its neighbors." (p.7)
Rule A calls for "tailoring" routing updates for each neighbor
such that the transmitting gateway reports its distance relative
to the connectivity of each recipient gateway. Thus, when a
gateway calculates its routing update, it first calculates its
minimum distance vector and then compares that vector to the last
routing update from each neighbor. From this comparison, it
creates the "tailored" routing update for each neighbor which
reflects not only the transmitting gateway's connectivity but
also the connectivity of each neighbor. The comparison process
is performed as follows:
-17-
IEN 196 11 September 1981
DO (For each neighbor)
DO (For each network)
IF (Transmitting gateway is as close or closer to
the network)
Report actual distance
ELSE (Report infinity distance)
ENDDO
ENDDO
Rule B requires that, having performed the calculations based on
Rule A resulting in routing updates for each neighbor, these
updates be compared to the updates last sent to each neighbor.
If any of the updates are different from those last sent, all the
updates are transmitted. If there are no changes to any neighbor
since the last transmittal, no updates are sent. Implementation
of this rule requires that copies of the last updates sent be
maintained at the gateway.
The basis for these rules, particularly Rule A, is prevention of
shuttling which could occur if only one path existed to a network
and that network became disconnected. If gateways were allowed
to report actual distances rather than infinity, then two
gateways could, because of their dependent or relative distance
relationship, begin step increments of their distances to the
disconnected network eventually approaching infinity and thus
shuttle packets until the IP4 time to live field is decremented
to zero.
This shuttling problem is, in fact, a natural outcome of a
routing scheme which involves the exchange of distance
information only. Thus, the problem can be solved by the
addition of special rules such as Rule #1 above or can be solved
by going to a routing scheme which exchanges connectivity
information (distance and path).
-18-
IEN 196 11 September 1981
After studying the current solution of exchanging relative
distance vectors, it seems that going to a routing scheme
involving exchange of both connectivity information and distance
provides a simpler and more efficient solution. The added
information exchange proposed is more than offset by the
computational simplicity and the reduction in routing update
traffic afforded.
The routing scheme proposed provides for including in routing
updates both the actual distance vector (as opposed to the
current tailored relative distance vector) and the routing table.
Figure 7 is a configuration used as the basis for illustration of
the updates. To see how these routing updates are constructed,
examine the update from G3 in Figure 8 (Step 3). G3 is directly
connected to Nets.#2 and #26, so G3 shows a distance of 0 to each
with G3 as the "next" gateway address for routing. G3 is 1 away
from Net.#1 and this path to Net.#1 is through G2. Similarly, G3
is 1 away from Nets.#3 and #27 and these paths are through G5 and
G6 respectiviely. G3 is also a distance of 1 from Net.#10.
-19-
IEN 196 11 September 1981
FIGURE 7: CATENET CONFIGURATION
__________ __________
| | | |
| NET #1 | | NET #4 |
|__________| |__________|
| |
| |
G2 G4
| |
| |
__________ __________
| | | |
| NET #26 |-----G1----| NET #10 |
|__________|---- |__________|
| | |
| | |
G3 |------------G5
| |
| |
__________ __________
| | | |
| NET #2 | | NET #3 |
|__________| |__________|
|
|
G6
|
|
__________
| |
| NET #27 |
|__________|
NOTE: Gateways G1 - G6 are all routing gateways.
-20-
IEN 196 11 September 1981
FIGURE 8: ROUTING UPDATES BASED ON NEW ROUTING METHOD
(SEE FIGURE 7 FOR CONFIGURATION)
NETWORK DISTANCES/"NEXT" NEIGHBOR ADDRESS(ES)
STEP SOURCE DEST. 1 2 3 4 10 26 27
1. G1 ALL Distance INF INF INF INF 0 0 INF
"Next" G1 G1
2. G2 ALL Distance 0 1 1 2 1 0 2
"Next" G2 G3 G5 G1 G1 G2 G3
3. G2 ALL Distance 1 0 1 2 1 0 1
"Next" G2 G3 G5 G1 G1 G3 G6
G5 G5
4. G4 ALL Distance 2 2 1 0 0 1 3
"Next" G1 G1 G5 G4 G4 G1 G1
G5 G5 G5 G5
5. G5(10) ALL Distance 1 1 0 1 0 0 2
"Next" G2 G3 G5 G4 G5 G5 G3
6. G5(26) ALL Distance 1 1 0 1 0 0 2
"Next" G2 G3 G5 G4 G5 G5 G3
7. G1 ALL Distance 1 1 1 1 0 0 2
"Next" G2 G3 G5 G4 G1 G1 G3
Assume loss of connectivity by G2 to Net.#1
8. G2 ALL Distance INF 1 1 2 1 0 2
"Next" G3 G5 G5 G5 G2 G3
G1 G1
9. G1 ALL Distance INF 1 1 1 0 0 2
"Next" G3 G5 G4 G1 G1 G3
NOTE: G5(10) is gateway 5 on network 10. A gateway which is a
neighbor on two networks is treated as two gateways. Thus
G5 is identified as G5(10) and G5(26) by Gateway 1.
-21-
IEN 196 11 September 1981
FIGURE 9: ROUTING UPDATES BASED ON IEN # 109 METHOD
(SEE FIGURE 7 FOR CONFIGURATION)
NETWORK DISTANCES
SOURCE DEST. 1 2 3 4 10 26 27
G1 ALL INF INF INF INF 0 0 INF
G2 G1 0 1 1 2 1 0 2
G1 G2 INF INF INF INF 0 0 INF
G1 G3 1 2 2 3 0 0 3
G1 G4 1 2 2 3 0 0 3
G1 G5(10) 1 2 2 3 0 0 3
G1 G5(26) 1 2 2 3 0 0 3
G3 G1 1 0 1 2 INF 0 1
G1 G2 INF 1 INF INF 0 0 2
G1 G3 1 INF INF 2 0 0 INF
G1 G4 1 1 2 2 0 0 2
G1 G5(10) 1 1 2 2 0 0 2
G1 G5(26) 1 1 2 2 0 0 2
G4 G1 INF INF 1 0 0 INF INF
G1 G2 INF 1 INF 1 0 0 2
G1 G3 1 INF INF 1 0 0 INF
G1 G4 1 1 INF INF 0 0 2
G1 G5(10) 1 1 2 1 0 0 2
G1 G5(26) 1 1 2 1 0 0 2
G5(10) G1 1 1 0 1 0 0 2
G5(26) G1 1 1 0 1 0 0 2
G1 G2 INF 1 1 1 0 0 2
G1 G3 1 INF 1 1 0 0 INF
G1 G4 1 1 1 INF 0 0 2
G1 G5(10) 1 1 INF 1 0 0 2
G1 G5(26) 1 1 INF 1 0 0 2
Assume loss of connectivity by G2 to Net.#1.
G2 G1 INF 1 1 INF INF 0 2
G1 G2 7 1 1 1 0 0 2
G1 G3 INF INF 1 1 0 0 INF
G1 G4 INF 1 1 INF 0 0 2
G1 G5(10) INF 1 INF 1 0 0 2
G1 G5(26) INF 1 INF 1 0 0 2
-22-
IEN 196 11 September 1981
However, in this case, G3 has two paths of distance 1 through
which it can reach Net.#10. G3 can go through G1 to reach
Net.#10 in 1 hop or it can go through G5. Since both paths are
equal and minimum distance, both are reported in the routing
update.
When routing updates are constructed to include both distance and
connectivity information as described above, gateways receive
enough information to perform path checks. This capability
enables gateways to avoid shuttling problems.
The performance of path checks is illustrated in Figure 7. In
Figure 8, step 8, G2 sends a routing update which shows that G2
has lost connectivity to Net.#1 (i.e., distance =inf.). G1 then
recomputes its minimum distance and routing with respect to
Net.#1. In these calculations G1 wants to find the shortest path
but also wants to ensure that it is a "true" path. Therefore, G1
looks at the first path of distance 1. This path is provided by
G3. However, G3's "next" neighbor address on this path is G2.
G2 now shows a path of infinity to Net.#1, so G1 rejects the G3
route. In examining the other routes of distance 1 (i.e., G5(10)
and G5(26)), G1 finds that they all go through G2 which G1 knows
is disconnected. Thus, all the paths of distance 1 are rejected.
Next, G1 looks at the route of distance 2 provided by G4. G4
shows two "next" addresses, G1 and G5, G1 rejects the path
through "next" address G1 since this path would obviously result
in shuttling. G1 then traces the route through "next" address
G5. Looking at the routing update provided by G5, G1 sees that
G5 intends to route traffic addressed to Net.#1 through G2. G2
has already been identified as a dead-end. As G1 has examined
all known routes to Net.#1 and found no acceptable route, G1
determines that it is infinity distance to Net.#1 and sends a
routing update to all its neighbors showing infinity distance to
Net.#1 (step 9).
The rules involved in the routing scheme described in the example
plus a few additional rules of the proposed routing scheme are
defined as follows:
A. On transmission of routing updates, the gateway reports its
actual distance (minimum distance vector) from each
network. In addition, for each network, the gateway
reports the "next" gateway address through which it will
route any packets addressed to the network. If more than
one path of the same minimum distance exists, the gateway
will report all possible "next" gateway addresses
associated with that network. In IEN # 109 terminology,
then, each gateway exchanges its "minimum distance vector"
and its "routing table (list of neighbor gateways through
which to send traffic to each network)."
-23-
IEN 196 11 September 1981
B. On transmission of routing updates, the gateway sets a
timer The transmitting gateway does not recompute its
minimum distance vector or send any new routing updates
prior to timer expiration.
C. Gateways calculate their routing updates and routing tables
on the basis of the minimum distance rule. Having selected
the minimum distance path to a network, the gateway checks
the "next" gateway address.
1. If the "next" gateway address is this gateway this
path is considered unacceptable and the next
candidate path is checked.
2. If the "next" gateway address is other than this
gateway, use the information in the routing update
matrix to determine if this path (distance of 1 or
greater) is through a gateway which has reported
"infinite" distance to the network in question. If
any step of the path is through a gateway showing
"infinite" distance to the network, the path is
considered unacceptable and the next candidate path
is checked.
Figure 8 shows the routing updates transmitted for the
configuration shown in Figure 7 when routing is performed IAW IEN
# 109. Figure 8 shows the routing updates transmitted for the
same configuration (Figure 7) when the proposed routing scheme is
used. Both examples are worked from the perspective of G1.
The examples show the differences in the routing updates
generated under each rule. In both cases, packets would be
routed correctly. In the proposed routing scheme (see Figure 8),
fewer routing updates are transmitted with the same results
obtained. This reduced traffic is due, in part, to the rule
requiring the gateway to observe a time-delay between
transmission of routing packets. This rule is particularly
useful when bringing a gateway on-line because it allows the
gateway to receive updates from all or almost all of its
neighbors before responding with its next updates. In addition,
the gateway is able to respond to the loss of connectivity to
Net.#1 correctly based on the update input from G2 (see Figure 8)
following the new method whereas, following the old rules (see
Figure 9), G1 must receive updates from all neighbors before
correctly determining that it has no path to Net.#1.
-24-
IEN 196 11 September 1981
Under the proposed method, the gateway has a more complex
algorithm to calculate its routing table. However, once
calculated, the gateway does not need to "tailor" the updates to
each neighbor but sends the same information to all neighbors.
Also, the gateway does not maintain a copy of the last update
transmitted to determine whether there is new information to be
transmitted since it transmits updates only when its routing
table changes. Under IEN # 109, the gateway is required to
maintain copies of each update last sent to each neighbor and
compose the new "tailored" updates on an individual basis to
those last sent.
Finally, the proposed routing method can be correctly implemented
without requiring any special rules regarding treatment of
non-routing neighbors. The path checks built into the new
routing scheme preclude the shuttling problems described above
which could have occured if non-routing gateways were not treated
as exceptions.
References
1) V. Strazisar, "Gateway Dynamic Routting", IEN # 25, Bolt,
Beranek and Newman, January 25, 1978.
2) V. Strazisar, R. Perlman, "Gateway Routing, An
Implementation Specification", IEN # 30, April 11, 1978.
3) V. Strazisar, "How to Build a Gateway", IEN # 109, August
31, 1979.
-25-
mirror server hosted at Truenetwork, Russian Federation.