Internet Draft
Internet Draft                                          Gerald R. Ash
                                                        AT&T Labs

                                                        October 1999

Expires: April 2000

             Routing Guidelines for Efficient Routing Methods

              <draft-ash-itu-sg2-routing-guidelines-00.txt>

STATUS OF THIS MEMO:

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task Force
(IETF), its areas, and its working groups.  Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and
may be updated, replaced, or obsoleted by other documents at any time.  It
is inappropriate to use Internet-Drafts as reference material or to cite
them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.  The list of Internet-Draft
Shadow Directories can be accessed at http://www.ietf.org/shadow.html.
Distribution of this memo is unlimited.

ABSTRACT:

This draft presents the ongoing work in ITU-T SG2 Question 2/2 on
Recommendation E.352 "Routing Guidelines for Efficient Routing Methods."
Routing policies typically used in ATM- and IP-based networks do not fully
consider the possible instabilities and drastic loss of throughput that can
occur under congestion.  Use of bandwidth reservation and avoidance of long
paths are recommended under such congestion, which can lead to more
efficient use of network resources.  Also, there is an emphasis in ATM- and
IP-based networks on the use of state-dependent-routing (SDR) methods.
However, the flooding methods typically used by these SDR methods to
disseminate network status information can lead to inefficient use of
network resources. Use of event-dependent-routing (EDR) methods and/or more
efficient dissemination of network status information are recommended as
other possible approaches to consider.  Finally, QoS routing rules are
recommended to ensure service performance quality, such as avoidance of
excessive transfer delay by limiting the number of satellite hops in an
end-to-end connection.

***************************************************************************
NOTE: A MICROSOFT WORD VERSION OF THIS DRAFT (WITH THE FIGURES) IS
       AVAILABLE ON REQUEST
***************************************************************************

Ash                       [Page 1]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

Table of Contents

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.0 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.0 Scope  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.0 Definitions  . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.0 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.0 Abbreviations  . . . . . . . . . . . . . . . . . . . . . . . . . 4
6.0 Recommended Routing Methods  . . . . . . . . . . . . . . . . . . 5
6.1 Bandwidth Reservation Methods  . . . . . . . . . . . . . . . . . 6
6.2 Route Selection . . . . . . .  . . . . . . . . . . . . . . . . . 8
6.3 QoS Routing . . . . . . . . .  . . . . . . . . . . . . . . . . . 9
7.0 Examples of Recommended Routing Methods. . . . . . . . . . . .  10
7.1 Example of Bandwidth Reservation Methods . . . . . . . . . . .  10
7.2 Example of Route Selection Methods . . . . . . . . . . . . . .  11
8.0 Author's Address  . . . . .  . . . . . . . . . . . . . . . . .  12
ANNEX A - TDM-BASED INTRANETWORK ROUTING METHODS . . . . . . . . .  12
A.1 Fixed Routing  . . . . . . . . . . . . . . . . . . . . . . . .  12
A.2 Time-Dependent Routing . . . . . . . . . . . . . . . . . . . .  13
A.3 State-Dependent Routing  . . . . . . . . . . . . . . . . . . .  14
A.4 Event-Dependent Routing  . . . . . . . . . . . . . . . . . . .  15
ANNEX B - BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . .  15

Ash                       [Page 2]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

1.0 Introduction

There are many network operators who have implemented multiple networks
using different protocols, which include Public Switched Telephone Networks
(PSTNs) which use Time Division Multiplexing (TDM) technology, Asynchronous
Transfer Mode (ATM) technology, and/or Internet Protocol (IP) technology.
Various routing protocols are used in TDM-, ATM-, and IP-based networks.  In
TDM-based networks, for example, Recommendation E.350 describes fixed and
dynamic routing methods for use in TDM-based networks.  In ATM-based
networks, for example, the Private Network-to-Network Interface (PNNI)
standard adopted by the ATM Forum [ATM960055] provides for exchange of node
and link status information, automatic update and synchronization of
topology databases, and dynamic route selection based on topology and status
information.  In IP-based networks, for example, the open shortest route
first (OSPF) and other standards adopted by the Internet Engineering Task
Force [M98, S95] provide for many of the same features as PNNI, but in a
connectionless IP-based packet network.  OSPF also provides for exchange of
node and link status information, automatic update and synchronization of
topology databases, and dynamic route selection based on topology and status
information.

This Recommendation addresses guidelines for efficient routing methods that
have been studied, learned, and implemented over many years of experience in
TDM-based networks.  These routing guidelines and methods are applicable as
well to ATM- and IP-based networks, and are recommended for these networks.
It is noted in the Recommendation that routing policies typically used in
ATM- and IP-based networks do not fully consider the possible instabilities
and drastic loss of throughput that can occur under congestion.  Use of
bandwidth reservation and avoidance of long paths are recommended under such
congestion, which can lead to more efficient use of network resources.
Also, there is an emphasis in ATM- and IP-based networks on the use of
state-dependent-routing (SDR) methods.  However, the flooding methods
typically used by these SDR methods to disseminate network status
information can lead to inefficient use of network resources. Use of
event-dependent-routing (EDR) methods and/or more efficient dissemination of
network status information are recommended as other possible approaches to
consider.  Finally, QoS routing rules are recommended to ensure service
performance quality, such as avoidance of excessive transfer delay by
limiting the number of satellite hops in an end-to-end connection.

2.0 Scope

This Recommendation provides guidelines for the design of routing methods
within TDM-, ATM-, and IP-based networks, and makes particular
recommendations on bandwidth reservation, route selection, and QoS routing.
It recommends these guidelines based on established practice, particularly
as applied within TDM-based PSTN networks, and addresses the cases when
PSTN's evolve to incorporate IP- or ATM-based technology.  Guidelines on
routing methods are covered in Section 6, and examples are given in Section
7 for the use of the routing methods.

3.0 Definitions

Link:                   a bandwidth transmission medium between nodes that
                        is engineered as a unit;

Ash                       [Page 3]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

Destination node:       terminating node within a given network;
Node:                   a network element (switch, router/switch, exchange)
                        providing switching and routing capabilities, or an
                        aggregation of such network elements representing a
                        network;
O-D pair:               an originating node to destination node pair for a
                        given connection/bandwidth-allocation request;
Originating node:       originating node within a given network;
Route:                  a concatenation of links providing a
                        connection/bandwidth-allocation between an O-D pair;
Route set:              a set of routes connecting the same O-D pair;
Routing table:          describes the route choices and selection rules to
                        select one route out of the route set for a
                        connection/bandwidth-allocation request
Traffic stream:         a class of  connection requests with the same
                        traffic characteristics;
Via node:               an intermediate node in a route within a given
                        network.

4.0 References

[E.164]  ITU-T Recommendation, The International Telecommunications
Numbering Plan.

[E.170]  ITU-T Recommendation, Traffic Routing.

[E.177]  ITU-T Recommendation, B-ISDN Routing.

[E.350]  ITU-T Recommendation, Dynamic Routing Interworking.

[E.351]  ITU-T Recommendation, Routing of Multimedia Connections Across
TDM-, ATM-, and IP-Based Networks

[E.412]  ITU-T Recommendation, Network Management Controls.

[E.525]  ITU-T Recommendation, Designing Networks to Control Grade of
Service.

[E.529]  ITU-T Recommendation, Network Dimensioning Using End-to-End GOS
Objectives.

5.0 Abbreviations

AAR                     Automatic Alternate Routing
ABR                     Available Bit Rate
AESA                    ATM End System Address
ARR                     Automatic Rerouting
AS                      Autonomous System
ATM                     Asynchronous Transfer Mode
BGP                     Border Gateway Protocol
B-ISDN                  Broadband Integrated Services Digital Network
BW                      Bandwidth
CAC                     Call Admission Control
CBR                     Constant Bit Rate
CCS                     Common Channel Signaling

Ash                       [Page 4]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

DADR                    Distributed Adaptive Dynamic Routing
DAR                     Dynamic Alternate Routing
DCR                     Dynamically Controlled Routing
DIFFSERV                Differentiated Services
DN                      Destination Node
DNHR                    Dynamic Nonhierarchical Routing
DTL                     Designated Transit List
EDR                     Event Dependent Routing
FR                      Fixed Routing
GCAC                    Generic Call Admission Control
GOS                     Grade of Service
IETF                    Internet Engineering Task Force
IP                      Internet Protocol
LLR                     Least Loaded Routing
LSA                     Link State Advertisement
LSP                     Label Switched Path
MPLS                    Multiprotocol Label Switching
N-ISDN                  Narrowband Integrated Services Digital Network
ODR                     Optimized Dynamic Routing
ON                      Originating Node
OSPF                    Open Shortest Route First
PNNI                    Private Network-to-Network Interface
PSTN                    Public Switched Telephone Network
PTSE                    PNNI Topology State Elements
QoS                     Quality of Service
RP                      Routing Processor
RSVP                    Resource Reservation Protocol
RTNR                    Real-Time Network Routing
SCP                     Service Control Point
SDR                     State-Dependent Routing
STR                     State- and Time-Dependent Routing
TDR                     Time-Dependent Routing
UBR                     Unassigned Bit Rate
VBR                     Variable Bit Rate
VC                      Virtual Circuit
VN                      Via Node
WIN                     Worldwide Intelligent Network (Routing)

6.0 Recommended Routing Methods

Routing policies typically used in ATM- and IP-based networks do not fully
consider the possible instabilities and drastic loss of throughput that can
occur under congestion.  In this Section we recommend the use of bandwidth
reservation and avoidance of long paths under such congestion to more
efficiently use network resources.

Also, there is an emphasis in ATM- and IP-based networks on the use of SDR
methods.  However, the flooding methods typically used by these SDR methods
to disseminate network status information can lead to inefficient use of
network resources. Use of EDR methods and/or more efficient dissemination of
network status information are recommended as other possible approaches to
consider.
Finally, QoS routing rules are recommended to ensure service performance
quality, such as avoidance of excessive transfer delay by limiting the
number of satellite hops in end-to-end connections for delay-sensitive

Ash                       [Page 5]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

connections to at most one hop.

6.1 Bandwidth Reservation Methods

Bandwidth reservation (the TDM-network terminology is "trunk reservation")
gives preference to the preferred traffic by allowing it to seize any idle
bandwidth in a link, while allowing the non-preferred routing traffic to
only seize bandwidth if there is a minimum level of idle bandwidth
available, where the minimum-bandwidth threshold is called the reservation
level.  P. J. Burke [Bur61] first analyzed bandwidth reservation behavior
from the solution of the birth-death equations for the bandwidth
reservation model.  Burke's model showed the relative lost-traffic level for
preferred traffic, which is not subject to bandwidth reservation
restrictions, as compared to non-preferred traffic, which is subject to the
restrictions.  Figure 1 illustrates the percent lost traffic of preferred
and non-preferred traffic on a typical link with 10 percent traffic
overload. It is seen that the preferred traffic lost traffic is near zero,
whereas the non-preferred lost traffic is much higher, and this situation is
maintained across a wide variation in the percentage of the preferred
traffic load. Hence, bandwidth reservation protection is robust to traffic
variations and provides significant dynamic protection of particular streams
of traffic.

Bandwidth reservation is a crucial technique used in nonhierarchical
networks to prevent "instability," which can severely reduce throughput in
periods of congestion, perhaps by as much as 50 percent of the
traffic-carrying capacity of a network [E.525]. The phenomenon of
instability has an interesting mathematical solution to network flow
equations, which has been presented in several studies [NaM73, Kru82,
Aki84].  It is shown in these studies that nonhierarchical networks exhibit
two stable states, or bistability, under congestion and that networks can
transition between these stable states in a network congestion condition
that has been demonstrated in simulation studies. A simple explanation of
how this bistable phenomenon arises is that under congestion, a network is
often not able to complete a connection request on the direct or shortest
route, which consist in this example of a single link. If alternate routing
is allowed, such as on longer, multiple-link routes, which are assumed in
this example to consist of two links, then the connection request might be
completed on a two-link route selected from among a large number of two-link
route choices, only one of which needs sufficient idle bandwidth on both
links to be used to route the connection.  Because this two-link connection
now occupies resources that could perhaps otherwise be used to complete two
one-link connections, this is a less efficient use of network resources
under congestion. In the event that a large fraction of all connections
cannot complete on the direct link but instead occupy two-link routes, the
total network throughput capacity is reduced by one-half because most
connections take twice the resources needed. This is one stable state; that
is, most or all connections use two links. The other stable state is that
most or all connections use one link, which is the desired condition. .

Bandwidth reservation is used to prevent this unstable behavior by having
the preferred traffic on a link be the direct traffic on the primary,
shortest route, and the non-preferred traffic, subjected to bandwidth
reservation restrictions as described above, be the alternate-routed traffic
on longer routes. In this way the alternate-routed traffic is inhibited from

Ash                       [Page 6]

Internet Draft   Routing Guidelines for Efficient Rtg Methods     Oct 99

selecting longer alternate routes when sufficient idle trunk capacity is not
available on all links of an alternate-routed connection, which is the
likely condition under network and link congestion. Mathematically, the
studies of bistable network behavior have shown that bandwidth reservation
used in this manner to favor direct shortest connections eliminates the
bistability problem in nonhierarchical networks and allows such networks to
maintain efficient utilization under congestion by favoring connections
completed on the shortest route.  For this reason, dynamic trunk reservation
is universally applied in nonhierarchical networks [E.529], and often in
hierarchical networks [Mum76].

There are differences in how and when bandwidth reservation is applied,
however, such as whether the bandwidth reservation for direct-routed
connections is in place at all times or whether it is dynamically triggered
to be used only under network or link congestion. This is a complex network
throughput trade-off issue, because bandwidth reservation can lead to some
loss in throughput under normal, low-congestion conditions. This loss in
throughput arises because if bandwidth is reserved for connections on the
shortest route, but these calls do not arrive, then the capacity is
needlessly reserved when it might be used to complete alternate-routed
traffic that might otherwise be blocked. However, under network congestion,
the use of bandwidth reservation is critical to preventing network
instability, as explained above [E.525].

It is recommended that bandwidth reservation techniques be included in ATM-based and IP-based routing methods, in order to ensure the efficient use of network resources especially under congestion conditions. Currently recommended route-selection methods, such as methods for "Traffic Engineering" in IP-based MPLS networks [AMAOM98], or route selection in ATM-based PNNI networks [ATM960055], give no guidance on the necessity for using bandwidth-reservation techniques. Such guidance is essential for acceptable network performance. Examples are given in [A98] for dynamically triggered bandwidth reservation techniques, where bandwidth reservation is triggered only under network congestion. Such methods are shown to be effective in striking a balance between protecting network resources under congestion and ensuring that resources are available for sharing when conditions permit. In [A98] the phenomenon of network instability is illustrated through simulation studies, and the effectiveness of bandwidth reservation in eliminating the instability is demonstrated. Bandwidth reservation is also shown to be an effective technique to share bandwidth capacity among services integrated on a direct link, where the reservation in this case is invoked to prefer direct link capacity for one particular service as opposed to another service when network and link congestion are encountered. These .two aspects of bandwidth reservation, that is, for avoiding instability and for sharing bandwidth capacity among services, are illustrated in Section 7. In addition to the use of bandwidth reservation procedures at the time of connection request set-up, a priority of service queuing capability is often used during the time the connection is established. For example, at each link in an established connection, a queuing discipline is maintained such that the packets or cells being served are given priority in some particular order, such as: 1) constant-rate services, 2) variable-rate, delay-sensitive Ash [Page 7] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 services, 3) variable-rate, non-delay-sensitive services, and 4) variable-rate, best-effort services. The IETF Differentiated Services (DIFFSERV) protocol [B99], for example, has queuing priorities designated as expedited forwarding (EF), in which bandwidth can be reserved for guaranteed throughput, and various categories of assured forwarding (AF), in which bandwidth is not reserved or guaranteed. Use of bandwidth reservation on connection set-up, therefore, should also be linked to bandwidth reservation used in the queuing priority discipline. 6.2 Route Selection A specific traffic routing method is characterized by the routing table used in the method. The routing table consists of a route set and rules to select one route from the route set for a given connection or bandwidth-allocation request. When a connection/bandwidth-allocation request is initiated by an originating node (ON), the ON implementing the routing method executes the route selection rules associated with the routing table for the connection/bandwidth-allocation to find an admissible route from among the routes in the route set that satisfies the connection/bandwidth-allocation request. In a particular routing method, the set of routes assignable to the connection/bandwidth-allocation request may be determined according to the rules associated with the routing table. In a network with originating connection/bandwidth-allocation control, the ON maintains control of the connection/bandwidth-allocation request. If crankback/bandwidth-not-available is used, for example, at a via node (VN), the preceding node maintains control of the connection/bandwidth-allocation request even if the request is blocked on all the links outgoing from the VN. Routing tables consist of routes, and routes may be set up for individual connection requests such as on switched virtual circuits (SVC). Routes may also be set up for bandwidth-allocation requests associated with "bandwidth pipes" or "virtual trunking", such as on switched virtual paths (SVPs) in ATM-based networks or constraint-based routing label switched paths (CRLSPs) in IP-based networks. Routes are determined by (normally proprietary) algorithms based on the network topology and reachable address information. These routes can cross multiple peer groups in ATM-based networks, and multiple autonomous systems in IP-based networks, as discussed in [E.351]. An ON may select a route from the routing table based on the routing rules and the QoS resource management criteria, which must be satisfied on each link in the route. If a link is not allowed based on the QoS criteria, then a release with crankback/bandwidth-not-available parameter is used to signal that condition to the ON in order to return the connection/bandwidth-allocation request to the ON, which may then select an alternate route. It is recommended that route selection rules used within routing tables should allow the use of fixed routing (FR), time-dependent routing (TDR), state-dependent routing (SDR), and event-dependent routing (EDR) route selection, as discussed in ANNEX A, and the use of multilink shortest routes in a sparse network topology. Current IP-based routing techniques, such as OSPF, and ATM-based routing techniques, such as PNNI, emphasize SDR route selection with link-state flooding used to convey dynamic link-status information. Typically the available-cell-rate (AvCR) is used to determine the least-loaded-route in the SDR routing method. The least-loaded-route is Ash [Page 8] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 the one having the maximum available capacity across all links the route. However, the flooding of the AvCR information on each link, which is highly-variable, dynamic information, is very resource intensive [ACFM99]. That is, significant link capacity is used to carry the flooded AvCR information, and significant processor capacity is used to process the flooded status messages. However, alternatives to SDR route selection are available, such as using EDR route selection methods, or more efficient status update techniques in place of link-state flooding, such as described in [E.350]. For instance, in one EDR route selection method, the connection/bandwidth-allocation admission control for each link in the route is learned based on the local status of each link in a route and not on the basis of flooded link status information. The ON normally selects the shortest route first, and attempts to set up a connection on this route by identifying each via node (VN) in the route in the setup procedure. Each VN in the route then tests for available capacity on the link to the next VN. If capacity is not available on any link in the route, the VN returns control of the connection to the ON through a crankback/bandwidth-not-available procedure. At this point the ON then selects the last successful alternate route, denoted as the success-to-the-top (STT) route. The STT route is tested for available capacity in the same manner as for the shortest route. If the current STT alternate route is not available, the ON may then selects another alternate route and tests that route for available capacity in the same manner. That is, if a link is not allowed on the selected route, as determine by each VN in the route based on the local link status information, then a release with crankback/bandwidth-not-available is used to return control to the ON and select an alternate route. The ON can check other candidate alternate routes in this way until either a new, successful STT via is found, or the ON blocks the connection request. This EDR route selection method finds routes through learning and local status information, and does not require the flooding of frequently changing link-state parameters such as AvCR. This EDR approach then allows a major reduction in the frequency of link-state flooding, and as a consequence of the reduction in the link and processor resources consumed, allows for larger peer group sizes. 6.3 QoS Routing QoS routing constraints are recommended to be taken into account in the route selection methods. These include end-to-end transfer delay, delay variation [G99a], and transmission quality considerations such as loss, echo, and noise [D99, G99a, G99b]. Additionally, link capability selection [E.351] is recommended, which allows connection requests to be routed on specific transmission media that have the particular characteristics required by these connection requests. For example, if fiberoptic transmission is required, then only routes with links having Fiberoptic=Yes are used. If we prefer the presence of fiberoptic transmission, then routes having all links with Fiberoptic=Yes are used first, then routes having some links with Fiberoptic=No. A particular QoS routing recommendation is the end-to-end transfer delay introduced by satellite transmission. Typically, each satellite transmission link introduces about 500 milliseconds of delay, which is above the threshold of being noticeable. Therefore, routing of delay sensitive Ash [Page 9] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 connections, such as interactive voice connections, are recommended to maintain a constraint of at most one satellite hop in the end-to-end connection. This is typically achieved by keeping a count of the satellite links traversed in the call setup procedure, and inhibiting further routing on satellite links once a single such link has been traversed. 7.0 Examples of Recommended Routing Methods In this Section we give examples of bandwidth reservation and route selection methods that might be implemented in an ATM- or IP-based network, to illustrate the recommendations in Section 6. 7.1 Example of Bandwidth Reservation Methods As discussed in Section 6, bandwidth reservation can be used to favor one category of traffic over another category of traffic. A simple example of the use of this method is to reserve bandwidth in order to prefer traffic on the shorter primary routes over traffic using longer alternate routes. This is most efficiently done by using a method which reserves bandwidth only when congestion exists on links in the network. We now give an illustration of this method, and compare the performance of a network in which bandwidth reservation is used under congestion to the case when bandwidth reservation is not used. In the example, traffic is first routed on the shortest route, and then allowed to alternate route on longer routes if the primary route in not available. In the case where bandwidth reservation is used, five percent of the link bandwidth is reserved for traffic on the primary route when congestion is present on the link. Table 1 illustrates the performance of bandwidth reservation methods for a high-day network load pattern. In Table 1, the average business day loads for 65-switch national network model were inflated uniformly by 30 percent [A98]. The Table gives the average hourly lost traffic due to blocking of connection admissions in load-set-periods 2, 3, and 5, which correspond to the two early morning busy hours and the afternoon busy hour. Table 1 Performance of Bandwidth Reservation Methods (Percent Lost Traffic under 30% Overload; 65-Node Network Model) ---------------------------------------------------------------------------- Hour Without Bandwidth Reservation With Bandwidth Reservation ---------------------------------------------------------------------------- 2 12.19 0.22 3 22.38 0.18 5 18.90 0.24 We can see from the results of Table 1 that performance improves when bandwidth reservation is used. The reason for the poor performance without bandwidth reservation is due to the lack of reserved capacity to favor traffic routed on the more direct primary routes under network congestion conditions. Without bandwidth reservation nonhierarchical networks can exhibit unstable behavior in which essentially all connections are Ash [Page 10] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 established on longer alternate routes as opposed to shorter primary routes, which greatly reduces network throughput and increases network congestion [Aki84, Kru82, NaM73]. If we add the bandwidth reservation mechanism, then performance of the network is greatly improved. 7.2 Example of Route Selection Methods We now illustrate a comparison of state dependent routing (SDR) in comparison to event dependent routing (EDR). As discussed in Section 6, use of link-state flooding to implement SDR, as is often the case in the implementation of PNNI routing in ATM networks, or OSPF routing in IP-based networks, can be very resource-utilization intensive. EDR is an alternative to SDR and can be considered if the flooding overhead is deemed to be too great. As discussed in Section 6, EDR can be implemented without the use of dynamic link-state information and here we show that EDR methods can still achieve good performance in comparison to SDR methods. We now illustrate a simple comparison of SDR and EDR route selection methods. In the EDR route selection model, the ON first routes a connection request on the shortest route. If each link has sufficient available bandwidth according to the QoS resource management criteria, the connection is completed. Otherwise, the ON offers the overflow from the primary shortest route to the last successful alternate route (the success-to-the-top, or STT via route). If the connection is blocked on the current alternate route choice, the ON selects another alternate route from the set of candidate alternate routes. A VN uses crankback if necessary to return control to the ON if the VN finds a selected link to have insufficient bandwidth. The ON can search through all the candidate routes before blocking a connection request. In the SDR route selection model, the ON again routes a connection request on the shortest route, but selects alternate routes according to link status information. The link status is obtained by dynamic flooding of status between all network switches as in PNNI and OSPF. Table 2 Performance Comparison of EDR & SDR Route Selection Methods (Percent Lost/Delayed Traffic under 10% Overload; 135-Node Network Model) ---------------------------------------------------------------------------- SERVICE CATEGORY EDR SDR ---------------------------------------------------------------------------- BUSINESS-VOICE 1.64 1.46 CONSUMER-VOICE 1.62 1.49 INTERNATIONAL-OUT 3.93 5.53 INTERNATIONAL-IN (KEY) 0.00 0.00 KEY VOICE 0.00 0.00 64-KBPS SWITCHED DIGITAL SERVICES 1.51 1.74 64-KBPS ISDN DATA (KEY) 0.00 0.00 384-KBPS ISDN DATA 0.00 0.00 VARIABLE-RATE DELAY-SENSITIVE VOICE 1.09 0.41 VARIABLE-RATE NON-DELAY-SENSITIVE MULTIMEDIA 1.01 0.38 VARIABLE-RATE BEST-EFFORT MULTIMEDIA 24.9 30.4 Table 2 gives performance results for a 10% general overload in a 135-switch Ash [Page 11] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 network model in which various categories of service are modeled [ACFM99]. In the model, bandwidth reservation is used not only to protect traffic on the primary shortest route, but also to allocate bandwidth among the various services categories. "Key" services are given a higher priority of service than other services under congestion, through the use of the bandwidth reservation mechanisms [A98]. The results show the performance of the route selection methods in terms of lost traffic due to connection admission blocking plus delayed traffic due to queuing (priority queuing was also modeled). We can see that EDR and SDR route selection methods are quite comparable for this and other network overload/failure scenarios modeled, and suggest that EDR is an alternative that can be considered if the overhead of dynamic link-state flooding proves to be too resource-utilization intensive. 8.0 Author's Address Gerald R. Ash AT&T Labs Room MT E3-3C37 200 Laurel Avenue Middletown, NJ 07748 Phone: 732-420-4578 Fax: 732-368-6687 Email: gash@att.com ANNEX A - TDM-BASED INTRANETWORK ROUTING METHODS TDM-based routing methods described in this ANNEX include various route selection techniques. A specific traffic routing method is characterized by the routing table used in the method. The routing table consists of a route and rules to select one route from the route for a given connection request. When a connection request arrives at its ON, the ON implementing the routing method executes the route selection rules associated with the routing table for the connection to determine a route among the routes in the route for the connection request. In a particular routing method, the set of routes assignable to the connection request may be altered according to a certain route alteration rule. In ITU-T Recommendations E.170, E.177, and E.350, traffic routing methods are categorized into the following four types based on their routing pattern: fixed routing (FR), time-dependent routing (TDR), state-dependent routing (SDR), and event-dependent routing (EDR). We discuss each of these methods in the following paragraphs. A.1 Fixed Routing (FR) In a fixed routing (FR) method, a routing pattern is fixed for a connection request. A typical example of fixed routing is a conventional hierarchical alternate routing where the route and route selection sequence are determined on a preplanned basis and maintained over a long period of time. FR is more efficiently applied when the network is nonhierarchical, or flat, as compared to the hierarchical structure [A98]. Ash [Page 12] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 A.2 Time-Dependent Routing (TDR) Time-dependent routing (TDR) methods are a type of dynamic routing in which the routing tables are altered at a fixed point in time during the day or week. TDR routing tables are determined on a preplanned basis and are implemented consistently over a time period. The TDR routing tables are determined considering the time variation of traffic load in the network. Typically, the TDR routing tables used in the network are coordinated by taking advantage of noncoincidence of busy hours among the traffic loads. Dynamic Nonhierarchical Routing (DNHR) is an example of TDR, which is illustrated in Recommendation E.350. In TDR, the routing tables are preplanned and designed off-line using a centralized design system, which employs the TDR network design model. The off-line computation determines the optimal routes from a very large number of possible alternatives, in order to minimize the network cost. The designed routing tables are loaded and stored in the various nodes in the TDR network, and periodically recomputed and updated (e.g., every week) by the off-line system. In this way an ON does not require additional network information to construct TDR routing tables, once the routing tables have been loaded. This is in contrast to the design of routing tables in real time, such as in the state dependent routing and event dependent routing methods described below. Routes in the TDR routing table may consist of time varying routing choices and use a subset of the available routes. Routes used in various time periods need not be the same. Several TDR time periods are used to divide up the hours on an average business day and weekend into contiguous routing intervals, sometimes called load set periods. Route selection rules employed in TDR routing tables, for example, may consist of simple sequential routing. In the sequential method all traffic in a given time period is offered to a single route, and lets the first route in the route overflow to the second route which overflows to the third route, and so on. Thus, traffic is routed sequentially from route to route, and the route is allowed to change from hour to hour to achieve the preplanned dynamic, or time varying, nature of the TDR method. Other TDR route selection rules can employ probabilistic techniques to select each route in the route and thus influence the realized flows [A98]. Routes in the TDR routing table may consist of the direct link, a two-link route through a single VN, or a multiple-link route through multiple VNs. A TDR connection set-up example is now given. The first step is for the node to identify the DN and routing table information to the DN. The ON then tests for spare capacity on the first or shortest route, and in doing this supplies the VNs and DN on this route, along with the bandwidth reservation threshold parameter, to all nodes in the route. Each VN tests the available bandwidth capacity on each link in the route against the bandwidth reservation threshold. If there is sufficient capacity, the VN forwards the connection setup to the next node, which performs a similar function. If there is insufficient capacity, the VN sends a release message with crankback/bandwidth-not-available parameter back to the ON, at which point the ON tries the next route in the route as determined by the routing table rules. As described above, the TDR routes are preplanned, loaded, and stored in each ON Ash [Page 13] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 A.3 State-Dependent Routing (SDR) In state-dependent routing (SDR), the routing tables are altered automatically according to the state of the network. For a given SDR method, the routing table rules are implemented to determine the route choices in response to changing network status, and are used over a relatively short time period. Information on network status may be collected at a central processor or distributed to nodes in the network. The information exchange may be performed on a periodic or on-demand basis. SDR methods use the principle of routing connections on the best available route on the basis of network state information. For example, in the least loaded routing (LLR) method, the residual capacity of candidate routes is calculated, and the route having the largest residual capacity is selected for the connection. In general, SDR methods calculate a route cost for each connection request based on various factors such as the load-state or congestion state of the links in the network. dynamically controlled routing (DCR), worldwide intelligent network (WIN) routing, and real-time network routing (RTNR) are examples of SDR, which are illustrated in Recommendation E.350. In SDR, the routing tables are designed on-line by the ON or a central routing processor (RP) through the use of network status and topology information obtained through information exchange with other nodes and/or a centralized RP. There are various implementations of SDR distinguished by a) whether the computation of the routing tables is distributed among the network nodes or centralized and done in a centralized RP, and b) whether the computation of the routing tables is done periodically or connection by connection. This leads to three different implementations of SDR: a) centralized periodic SDR -- here the centralized RP obtains link status and traffic status information from the various nodes on a periodic basis (e.g., every 10 seconds) and performs a computation of the optimal routing table on a periodic basis. To determine the optimal routing table, the RP executes a particular routing table optimization procedure such as LLR and transmits the routing tables to the network nodes on a periodic basis (e.g., every 10 seconds). DCR is an example of centralized periodic SDR, as illustrated in E.350. b) distributed periodic SDR -- here each node in the SDR network obtains link status and traffic status information from all the other nodes on a periodic basis (e.g., every 5 minutes) and performs a computation of the optimal routing table on a periodic basis (e.g., every 5 minutes). To determine the optimal routing table, the ON executes a particular routing table optimization procedure such as LLR. WIN is an example of distributed periodic SDR, as illustrated in E.350. c) distributed call-by-call SDR -- here an ON in the SDR network obtains link status and traffic status information from the DN, and perhaps from selected VNs, on a connection by connection basis and performs a computation of the optimal routing table for each connection. To determine the optimal routing table, the ON executes a particular routing table optimization procedure such as LLR. RTNR is an example of distributed Ash [Page 14] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 connection-by-connection SDR, as illustrated in E.350. Routes in the SDR routing table may consist of the direct link, a two-link route through a single VN, or a multiple-link route through multiple VNs. Routes in the routing table are subject to DoS restrictions on each link, and the connection setup mechanisms are similar to the example given in Section A.2. A.4 Event-Dependent Routing (EDR) In event-dependent routing (EDR), the routing tables are updated locally on the basis of whether connections succeed or fail on a given route choice. In EDR, a connection is routed first to the shortest route, if it has sufficient available bandwidth. Otherwise, overflow from the shortest route is offered to a currently selected alternate route. If a connection is blocked on the current alternate route choice, another alternate route is selected from a set of available alternate routes for the connection request according to the given EDR routing table rules. For example, the current alternate route choice can be updated randomly, cyclically, or by some other means, and may be maintained as long as a connection can be established successfully on the route. Note that for either SDR or EDR, as in TDR, the alternate route for a connection request may be changed in a time-dependent manner considering the time-variation of the traffic load. Dynamic alternate routing (DAR), distributed adaptive dynamic routing (DADR), optimized dynamic routing (ODR), and state- and time-dependent routing (STR) are examples of event-dependent routing, which are illustrated in Recommendation E.350. In EDR, the routing tables are designed by the ON using network information obtained during the connection setup function. Typically the ON first selects the shortest route, and if that has insufficient bandwidth for the connection then the current successful via route is tried. If the current successful via route has insufficient bandwidth, this condition is indicated by a busy ON-VN link as determined by the ON or a busy VN-VN link or VN-DN link as indicated by a release message sent from the VN to the ON. At that point the ON selects a new via route using the given EDR routing table design rules. Hence the routing table is constructed with the information determined during connection setup, and no additional information is required by the ON. Routes in the EDR routing table may consist of the direct link, a two-link route through a single VN, or a multiple-link route through multiple VNs. Routes in the routing table are subject to DoS restrictions on each link, and the connection setup mechanisms are similar to the example given in Section A.2. ANNEX B - BIBLIOGRAPHY [A98] Ash, G. R., Dynamic Routing in Telecommunications Networks, McGraw-Hill, 1998. [AAFJLLS99] Ash, G. R., Ashwood-Smith, P., Fedyk, D., Jamoussi, B., Lee, Y., Li, L., Skalecki, D., LSP Modification Using CRLDP, draft-ash-crlsp-modify-00.txt, July 1999. Ash [Page 15] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 [Aki84] Akinpelu, J. M., The Overload Performance of Engineered Networks with Nonhierarchical and Hierarchical Routing, Bell System Technical Journal, Volume 63, 1984. [ACFM99] Ash, G. R., Chen, J., Fishman, S. D., Maunder, A., Routing Evolution in Multiservice Integrated Voice/Data Networks, International Teletraffic Congress ITC-16, Edinburgh, Scotland, June 1999. [ADFFT98] Anderson, L., Doolan, P., Feldman, N., Fredette, A., Thomas, B., LDP Specification, IETF Draft, draft-ietf-mpls-ldp-01.txt, August 1998. [AL99] Ash, G. R., Lee, Y., Routing of Multimedia Connections Across TDM-, ATM-, and IP-Based Networks, IETF Draft, draft-ash-itu-sg2-qos-routing-01.txt, July 1999. [AM98] Ash, G. R., Maunder, A., Routing of Multimedia Connections when Interworking with PSTN, ATM, and IP Networks, AF-98-0927, Nashville TN, December 1998. [AAJL99] Ash, G. R., Aboul-Magd, O. S., Jamoussi, B., Lee, Y., QoS Resource Management in MPLS-Based Networks, IETF Draft, draft-ash-qos-routing-00.txt, Minneapolis MN, March 1999. [AM99] Ash, G. R., Maunder, A., QoS Resource Management in ATM Networks, AF-99-, Rome Italy, April 1999. [AMAOM98] Awduche, D. O., Malcolm, J. Agogbua, J., O'Dell, M., McManus, J., Requirements for Traffic Engineering Over MPLS, IETF Draft, draft-ietf-mpls-traffic-eng-00.txt, October 1998. [ATM95] ATM Forum Technical Committee, B-ISDN Inter Carrier Interface (B-ICI) Specification Version 2.0 (Integrated), af-bici-0013.003, December 1995. [ATM960055] ATM Forum Technical Committee, Private Network-Network Interface Specification Version 1.0 (PNNI 1.0), af-pnni-0055.000, March 1996. [ATM960056] ATM Forum Technical Committee, Traffic Management Specification Version 4.0, af-tm0056.000, April 1996. [ATM960061] ATM Forum Technical Committee, ATM User-Network Interface (UNI) Signaling Specification Version 4.0, af-sig-0061.000, July 1996. [ATM98] ATM Forum Technical Committee, Specification of the ATM Inter-Network Interface (AINI) (Draft), ATM Forum/BTD-CS-AINI-01.03, July 1998. [ATM990097] ATM Signaling Requirements for IP Differentiated Services and IEEE 802.1D, ATM Forum, Atlanta, GA, February 1999. [B99] Bernet, Y., et. al., A Framework for Differentiated Services, IETF draft-ietf-diffserv-framework-02.txt, February 1999. Ash [Page 16] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 [BZBHJ97] Bradem. R., Zhang, L., Berson, S., Herzog, S., Jamin, S., Resource ReSerVation Protocol (RSVP) - Version 1 Functional Specification, IETF Network Working Group RFC 2205, September 1997. [Bur61] Burke, P. J., Blocking Probabilities Associated with Directional Reservation, unpublished memorandum, 1961. [CDFFSV97] Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G., Viswanathan, A., IETF Network Working Group Draft, A Framework for Multiprotocol Label Switching, draft-ietf-mpls-framework-02.txt, November 1997. [CNRS98] Crawley, E., Nair, R., Rajagopalan, B., Sandick, H., A Framework for QoS-based Routing in the Internet, IETF RFC 2386, August 1998. [D99] Dvorak, C., IP-Related Impacts on End-to-End Transmission Performance, ITU-T Liaison to Study Group 2, Temporary Document TD GEN-22, Geneva Switzerland, May 1999. [DN99] Dianda, R. B., Noorchashm, M., Bandwidth Modification for UNI, PNNI, AINI, and BICI, ATM Forum Technical Working Group, April 1999. [G99a] Glossbrenner, K., Elements Relevant to Routing of ATM Connections, ITU-T Liaison to Study Group 2, Temporary Document 1/2-8, Geneva Switzerland, May 1999. [G99b] Glossbrenner, K., IP Performance Studies, ITU-T Liaison to Study Group 2, Temporary Document GEN-27, Geneva Switzerland, May 1999. [GWA97] Gray, E., Wang, Z., Armitage, G., Generic Label Distribution Protocol Specification, IETF Draft, draft-gray-mpls-generic-ldp-spec-00.txt, November 1997. [J99] Jamoussi, B., Editor, Constraint-Based LSP Setup using LDP, IETF draft-ietf-mpls-cr-ldp-01.txt, February 1999. [Kru82] Krupp, R. S., Stabilization of Alternate Routing Networks, IEEE International Communications Conference, Philadelphia, 1982. [LKPCD98] Luciani, J., Katz, D., Piscitello, D., Cole, B., Doraswamy, N., NBMA Next Hop Resolution Protocol (NHRP), IETF RFC 2332, April 1998. [LR98] Li, T., Rekhter, Y., A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE), IETF RFC 2430, October 1998. [M98] Moy, J, OSPF Version 2, IETF RFC 2328, April 1998. [Mum76] Mummert, V. S., Network Management and Its Implementation on the No. 4ESS, International Switching Symposium, Japan, 1976. [NaM73] Nakagome, Y., Mori, H., Flexible Routing in the Global Communication Network, Seventh International Teletraffic Congress, Stockholm, 1973. [RVC99] Rosen, E., Viswanathan, A., Callon, R., Multiprotocol Label Switching Architecture, IETF draft-ietf-mpls-arch-04.txt, February 1999. Ash [Page 17] Internet Draft Routing Guidelines for Efficient Rtg Methods Oct 99 [S94] Stevens, W. R., TCP/IP Illustrated, Volume 1, The Protocols, Addison-Wesley, 1994. [S95] Steenstrup, M., Editor, Routing in Communications Networks, Prentice-Hall, 1995. [SCFJ96] Schulzrinne, H., Casner, S., Frederick, R., Jacobson, V., RTP: A Transport Protocol for Real-Time Applications, IETF RFC 1889, January 1996. [ST98] Sikora, J., Teitelbaum, B., Differentiated Services for Internet2, Internet2: Joint Applications/Engineering QoS Workshop, Santa Clara, CA, May 1998. [T1S198] ATM Trunking for the PSTN/ISDN, Committee T1S1.3 (B-ISUP), T1S1.3/98, NJ, December 1998. [ZSSC97] Zhang, Sanchez, Salkewicz, Crawley, Quality of Service Extensions to OSPF or Quality of Service Route First Routing (QOSPF), IETF Draft, draft-shang-qos-ospf-01.txt, September 1997. Ash [Page 18]