The following example shows the behavior of the demand circuit
extensions in the presence of oversubscribed interfaces. Note that
the example's topology excludes the possibility of alternative
paths. The combination of oversubscription and redundant topology
(i.e., alternative paths) poses special problems for the demand
circuit extensions. These problems are discussed later in Section
7.
Figure 4 shows a single Router (RT1) connected via demand circuits
to three other routers (RT2-RT4). Assume that RT1 can only have
two out of three underlying data-link connections open at once.
This may be due to one of the following reasons: Router RT1 may be
using a single Basic Rate ISDN interface (2 B channels) to support
all three demand circuits, or, RT1 may be connected to a data-link
switch (e.g., an X.25 or Frame relay switch) that is only capable
of so many simultaneous data-link connections.
The following events may transpire, starting with Router RT1
coming up.
Time T0: Router RT1 comes up.
Router RT1 attempts to establish neighbor connections and
synchronize OSPF databases with routers RT2-RT4. But,
+ +--+
+---+ |--|H2|
+---------|RT2|--| +--+
/ +---+ |
/ ODL +
+--+ + /
|H1|--| / +
+--+ | +---+ ODL +---+ | +--+
|--|RT1|------------|RT3|--|--|H3|
| +---+ +---+ | +--+
| \ +
+ \ODL
\ + +--+
\ +---+ |--|H4|
+--------|RT4|--| +--+
+---+ |
+
Figure 4: Example 3's internetwork.
because it cannot have data-link connections open to all
three at once, it will synchronize with RT2 and RT3, while
Hellos sent to RT4 will be discarded (see Section 1).
Time T1: Data-link connection to RT2 closed due to inactivity.
Assuming that no application traffic is being sent to/from
Host H2, the underlying data-link connection to RT2 will
eventually close due to inactivity. This will allow RT1 to
finally synchronize with RT4; the next Hello that RT1
attempts to send to RT4 will cause that data-link connection
to open and synchronization with RT4 will ensue. Note that,
until this time, H4 will have been considered unreachable by
OSPF routing. However, data traffic would not have been
deliverable to H4 until now in any case.
Time T2: RT2's LAN interface becomes inoperational
This causes RT2 to reissue its router-LSA. However, it may
be unable to flood it to RT1 if RT1 already has data-link
connections open to RT3 and RT4. While the data-link
connection from RT2 to RT1 cannot be opened due to resource
shortages, the new router-LSA will be continually
retransmitted (and dropped by RT2's ISDN interface; see
Section 1). This means that the routers RT1, RT3 and RT4
will not detect the unreachability of Host H2 until a data-
link connection on RT1 becomes available.
5. Topology recommendations
Because LSAs indicating topology changes are still flooded over
demand circuits, it is still advantageous to design networks so that
the demand circuits are isolated from as many topology changes as
possible. In OSPF, this is done by encasing the demand circuits
within OSPF stub areas or within NSSAs (see [3]). In both cases, this
isolates the demand circuits from AS external routing changes, which
in many networks are the most frequent (see [6]). Stub areas can even
isolate the demand circuits from changes in other OSPF areas.
Also, considering the interoperation of OSPF routers supporting
demand circuits and those that do not (see Section 2.5), isolated
stub areas or NSSAs can be converted independently to support demand
circuits. In contrast, regular OSPF areas must all be converted
before the functionality can take effect in any particular regular
OSPF area.
6. Lost functionality
The enhancements defined in this memo to support demand circuits come
at some cost. Although we gain an efficient use of demand circuits,
holding them open only when there is actual application data to send,
we lose the following:
Robustness
In regular OSPF [1], all LSAs are refreshed every
LSRefreshInterval. This provides protection against routers
losing LSAs from (or LSAs getting corrupted in) their link state
databases due to software errors, etc. Over demand circuits
this periodic refresh is removed, and we depend on routers
correctly holding LSAs marked with DoNotAge in their databases
indefinitely.
Database Checksum
OSPF supplies network management variables, namely
ospfExternLSACksumSum and ospfAreaLSACksumSum in [7], allowing a
network management station to verify OSPF database
synchronization among routers. However, these variables are sums
of the individual LSAs' LS checksum fields, which are no longer
guaranteed to be identical across demand circuits (because the
LS checksum covers the LS Sequence Number, which will in general
differ across demand circuits). This means that these variables
can no longer be used to verify database synchronization in OSPF
networks containing demand circuits.
7. Future work: Oversubscription
An internetwork is oversubscribed when not all of its demand
circuits' underlying connections can be open at once, due to resource
limitations. These internetworks were addressed in Section 4.3.
However, when all possible sources in the internetwork are active at
once, problems can occur which are not addressed in this memo:
(1) There is a network design problem. Does a subset of demand
circuits exist such that a) their data-link connections can be
open simultaneously and b) they can provide connectivity for all
possible sources? This requires that (at least) a spanning tree
be formed out of established connections. Figure 4 shows an
example where this is not possible; Hosts H1 through H4 cannot
simultaneously talk, since Router RT1 is limited to two
simultaneously open demand circuits.
(2) Even if it is possible that a spanning tree can form, will one?
Given the model in Section 1, demand circuits are brought up
when needed for data traffic, and stay established as long as
data traffic is present. One example is shown in Figure 5. Four
routers are interconnected via demand circuits, with each router
being able to establish a circuit to any other. However, we
assume that each router can only have two circuits open at once
(e.g., the routers could be using Basic Rate ISDN). In this
case, one would hope that the data-link connections in Figure 5a
would form. But the connections in Figure 5b are equally
likely, which leave Host H2 unable to communicate.
One possible approach to this problem would be for a) the OSPF
database to indicate which demand circuits have actually been
established and b) implement a distributed spanning tree
construction (see for example Chapter 5.2.2 of [9]) when
necessary.
(3) Even when a spanning tree has been built, will it be used?
Routers implementing the functionality described in this memo do
not necessarily know which data-link connections are established
at any one time. In fact, they view all demand circuits as being
equally available, whether or not they are currently
established. So for example, even when the established
connections form the pattern in Figure 5a, Router RT1 may still
believe that the best path to Router RT3 is through the direct
demand circuit. However, this circuit cannot be established due
to resource shortages.
+--+ + + +--+
|H1|--| +---+ ODL +---+ |--|H2|
+--+ |--|RT1|-------|RT2|--| +--+
| +---+ +---+ |
+ | \ / | +
| \ / |
| \ / |
|ODL / |ODL
| / \ODL |
| / \ |
+ | /ODL \ | +
+--+ | +---+ +---+ | +--+
|H4|--|--|RT4|-------|RT3|--|--|H3|
+--+ | +---+ ODL +---+ | +--+
+ +
Figure 5: Example of an oversubscribed
internetwork
+---+ +---+ +---+ +---+
|RT1|-------|RT2| |RT1| |RT2|
+---+ +---+ +---+ +---+
| | | \
| | | \
| | | \
| | | \
| | | \
| | | \
| | | \
+---+ +---+ +---+ +---+
|RT4|-------|RT3| |RT4|-------|RT3|
+---+ +---+ +---+ +---+
Figure 5a: One possible Figure 5b: Another possible
pattern of data-link pattern of data-link
connections connections
On possible approach to this problem is to increase the OSPF cost of
demand circuits that are currently discarding application packets
(i.e., can't be established) due to resource shortages. This may help
the routing find paths that can actually deliver the packets. On the
downside, it would create more routing traffic. Also, unwanted
routing oscillations may result when you start varying routing
metrics to reflect dynamic network conditions; see [10].
8. Unsupported capabilities
The following possible capabilities associated with demand circuit
routing have explicitly not been supported by this memo:
o When the topology of an OSPF area changes, the changes are
flooded over the area's demand circuits, even if this requires
(re)establishing the demand circuits' data-link connections. One
might imagine a routing system where the flooding of topology
changes over demand circuits were delayed until the demand
circuits were (re)opened for application traffic. However, this
capability is unsupported because delaying the flooding in this
manner would sometimes impair the ability to discover new
network destinations.
o Refining the previous capability, one might imagine that the
network administrator would be able to configure for each demand
interface whether flooding should be immediate, or whether it
should be delayed until the data-link connection is established
for application traffic. This would allow certain "application-
specific" routing behaviors. For example, a demand circuit may
connect a collection of client-based subnets to a collection of
server-based subnets. If the client end was configured to delay
flooding, while the server end was configured to flood changes
immediately, then new servers would be discovered promptly while
clients might not be discovered until they initiate
conversations. However, this capability is unsupported because
of the increased complexity of (and possibility for error in)
the network configuration.
A. Format of the OSPF Options field
The OSPF Options field is present in OSPF Hello packets, Database
Description packets and all LSAs. The Options field enables OSPF
routers to support (or not support) optional capabilities, and to
communicate their capability level to other OSPF routers. Through
this mechanism routers of differing capabilities can be mixed within
an OSPF routing domain.
The memo defines one of the Option bits: the DC-bit (for Demand
Circuit capability). The DC-bit is set in a router's self-originated
LSAs if and only if it supports the functionality defined in Section
2 of this memo. Note that this does not necessarily mean that the
router can be the endpoint of a demand circuit, but only that it can
properly process LSAs having the DoNotAge bit set. In contrast, the
DC-bit is set in Hello Packets and Database Description Packets sent
out an interface if and only if the router wants to treat the
attached point-to-point network as a demand circuit (see Section
3.2.1).
The addition of the DC-bit makes the current assignment of the OSPF
Options field as follows:
+------------------------------------+
| * | * | DC | EA | N/P | MC | E | T |
+------------------------------------+
Figure 5: The OSPF Options field
T-bit
This bit describes TOS-based routing capability, as specified in
[1].
E-bit
This bit describes the way AS-external-LSAs are flooded, as
described in [1].
MC-bit
This bit describes whether IP multicast datagrams are forwarded
according to the specifications in [4].
N/P-bit
This bit describes the handling of Type-7 LSAs, as specified in
[3].
EA-bit
This bit describes the router's willingness to receive and
forward External-Attributes-LSAs, as specified in [5].
DC-bit
This bit describes the handling of demand circuits, as specified
in this memo. Its setting in Hellos and Database Description
Packets is described in Sections 3.2.1 and 3.2.2. Its setting in
LSAs is described in Sections 2.1 and 2.5.
B. Configurable Parameters
This memo defines a single additional configuration parameter for
OSPF interfaces. In addition, the OSPF Interface configuration
parameter PollInterval, previously used only on NBMA networks, is now
also used on point-to-point networks (see Sections 3.1 and 3.2.2).
ospfIfDemand
Indicates whether the interface connects to a demand circuit.
When set to TRUE, the procedures described in Section 3 of this
memo are followed, in order to send a minimum of routing traffic
over the demand circuit. On point-to-point networks, this allows
the circuit to be closed when not carrying application traffic.
When a broadcast or NBMA interface is configured to connect to a
demand circuit (see Section 1.2 of [1]), the data-link
connections will be kept open constantly due to OSPF Hello
traffic, but the amount of flooding traffic will still be
greatly reduced.
C. Architectural Constants
This memo defines a single additional OSPF architectural constant.
DoNotAge
Equal to the hexadecimal value 0x8000, which is the high bit of
the 16-bit LS age field in OSPF LSAs. When this bit is set in
the LS age field, the LSA is not aged as it is held in the
router's link state database. This allows the elimination of the
periodic LSA refresh over demand circuits. See Section 2.2 for
more information on processing the DoNotAge bit.
References
[1] Moy, J., "OSPF Version 2", RFC1583, Proteon, Inc., March 1994.
[2] Meyer, G., "Extensions to RIP to Support Demand Circuits", RFC
1582, Spider Systems, February 1994.
[3] Coltun, R. and V. Fuller, "The OSPF NSSA Option", RFC1587,
RainbowBridge Communications, Stanford University, March 1994.
[4] Moy, J., "Multicast Extensions to OSPF", RFC1584, Proteon, Inc.,
March 1994.
[5] Ferguson, D., "The OSPF External Attributes LSA", Work in
Progress.
[6] Moy, J., Editor, "OSPF Protocol Analysis", RFC1245, Proteon,
Inc., July 1991.
[7] Baker F. and R. Coltun, "OSPF Version 2 Management Information
Base", RFC1253, ACC, University of Maryland, August 1991.
[8] Baker F., "OSPF Point-to-MultiPoint Interface", Work in Progress.
[9] Bertsekas, D., and R. Gallager, "Data Networks", Prentice Hall,
Inc., 1992.
[10] Khanna, A., "Short-Term Modifications to Routing and Congestion
Control", BBN Report 6714, BBN, February 1988.
Security Considerations
Security issues are not discussed in this memo.
Author's Address
John Moy
Cascade Communications Corp.
5 Carlisle Road
Westford, MA 01886
Phone: 508-692-2600 Ext. 394
Fax: 508-692-9214