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]