October 2004

20 Years of Dynamic Routing in Telephone Networks: Looking Backward to the Future

Dr. Gerald R. Ash, Fellow, IEEE, Prosper Chemouil, Fellow, IEEE

      The 20th anniversary of the operational implementation of dynamic routing in circuit-switched networks represents a unique opportunity to look back on a subject that generated so much interest around the world and to analyze the influence of such studies in the design of new networks. It is first useful to recall the objectives of dynamic routing, briefly describe the methods that were developed, and review the current status of these networks throughout the world. The introduction of dynamic routing obviously represented a revolution, which incidentally occurred on 14 July, 1984; on Bastille Day, which celebrates the French Revolution. Both revolutions aimed to introduce more freedom and fairness: fortunately, the revolution that occurred two decades ago did not result in any chopped-off heads, as did the first one. Instead, this article represents a tribute to all scientists and engineers who took part in this Routing Revolution and deserve hats off! A more elaborated version of this overview, which contains a comprehensive bibliography, can be found at http://perso.rd.francetelecom.fr/chemouil/gcn_ieee/DynRout20.pdf.

Historical Background

      Hierarchical networks arose in the 1940s and ’50s with the development of common control switching systems that enabled the introduction of alternate routing. Networks were structured into different levels used to concentrate traffic from one region to another, and to prevent a call from returning to one of the switching centers along its routing path (the call looping phenomenon)‚ the selection of alternative paths was subject to hierarchical rules. In addition, due to limited measurement capabilities in the switches and lack of computing facilities, routing was determined at the design stage and remained fixed under normal conditions until the next design stage. Fixed hierarchical routing was then established.
      With the advent of digital switches, the emergence of new signaling systems, and the rise of data networks, new processing capabilities allowed for the evolution of traffic routing from fixed hierarchical to flexible nonhierarchical. Substantial improvements in network cost efficiency and robustness result from the introduction of dynamic routing. Dynamic routing allows routing decisions to adapt to load and network conditions. Studies have shown that significant economic and service benefits may accrue from implementing dynamic routing methods in national, private, metropolitan, or international networks. In fact the deployment of dynamic routing in telephone networks has known several stages:
Figure 1.
      Genesis (1975–1980): The possibility of flexible control of network traffic gave rise to the formulation of many theoretical problems, among which real-time traffic routing was recognized as the most promising. The early work concerned traffic control concepts for networks with alternate routing [1], but a first theoretical framework for dynamic routing was given in the mid-’70s by K. Narendra, inspired by the work of L. Mason, as he suggested the use of learning automata for telephone traffic routing [2]. A seminar he gave in 1975 at Bell Laboratories led to a concentrated effort by AT&T to study and then implement a DNHR network [3] on 14 July 1984.
      Expansion Age (1979–1991): The rise of dynamic routing occurred in the ’80s, when Bell Northern Research set up a field trial in Toronto, Canada, in 1979, based on real-time measurements [4]. At the same time, various research efforts by network operators and universities resulted in the large-scale deployment of DNHR in AT&T’s long distance network in 1984, followed by the field trial in Paris of a metropolitan network by France Telecom in 1987 [5]. Dynamic routing was thus recognized as a major research topic [6]: various seminars and workshops [7] were held. Special issues of IEEE Communications Magazine gave comprehensive coverage of the status of dynamic routing methods [8, 9], and ITU-T Recommendations were published that emphasized the importance of dynamic routing [10–12].
      Maturity Age (1991- 2000): During this decade, many operators implemented dynamic routing systems in their domestic and international networks. In particular, the WIN system in the early ’90s was a unique initiative that gathered several international network operators.
      Recession Age (from 2000): With emerging new technologies such as asynchronous transfer mode (ATM) and IP that are packet-oriented, the focus on time-division multiplexing (TDM) networks has rapidly decreased, and the work instead focused on similar principles of quality of service (QoS) and routing applied to all network types. It is expected that with the deployment of IP-based networks, present dynamic routing systems will be progressively turned down and replaced with new ones implementing IP protocols.

Dynamic Routing Methods

      Traffic routing methods are categorized into the following four types based on their routing table update [13]: fixed routing (FR), time-dependent routing (TDR), state-dependent routing (SDR), and event-dependent routing (EDR). Operational implementations of these methods are summarized in Table 1 and briefly introduced in the following paragraphs.

Table 1. Operational dynamic routing systems.
Routing type Dynamic routing systems Network Start year End year Comments
TDR DNHR Dynamic nonhierarchical routing AT&T U.S. national network 1984 1991 DNHR replaced by RTNR in 1991.
AT&T FTS-2000 network 1987 2002 DNHR replaced by RTNR in 2002.
SDR centralized periodic GTAI (GTAI is an Italian acronym: management of the traffic transit Italcable switches) Italcable 1984 1985? This routing mechanism was implemented between the three intercontinental switches operated by Italcable.
DCR Dynamically Controlled Routing Stentor Canada national network 1991 In operation Known as high-performance routing (HPR).
Bell Canada network 1992 In operation Consists of one DCR network local to the Toronto area and one local to the Montreal area.
Sprint national network 1994 In operation  
MCI US national network 1995 In operation  
Qwest Communications national network 1999 In operation  
SDR distributed periodic WIN Worldwide intelligent network routing Worldwide intelligent network 1993 In operation WIN data is currently exchanged between AT&T/US, CHT-I/ Taiwan, and Alestra/Mexico.
SDR distributed call-by-call RTNR Real-time network routing AT&T U.S. national network 1991 In operation  
AT&T FTS-2000 network 2002 In operation  
RINR Real-time internetwork routing AT&T Global international network 1991 In operation  
EDR STR State- and time-dependent routing NTT Japan national network 1992 2002 The deployment of STR started in 1992, but operation stopped in 2002 when the D60 switches were replaced by new switches.
DAR Dynamic alternative routing British Telecom U.K. national network 1993 ?  
STT Success-to-the-top network routing AT&T U.S. national network 1995 1999 STT is a method used for a period of time to route calls with voiceenhancement devices in the path.
LAW Lastabehängige automatische wegesuche (in English, automatic last choice routing) Deutsche Telecom national network 1995 In operation LAW is implemented in the transit network as well as regional and international access networks).
AMI Acheminement multiple intelligent (in English, multiple intelligent routing — MIR) France Telecom long distance network 1998 In operation AMI/MIR is an EDR system with multiple overflow routes and crankback.

Fixed Routing

      In FR a routing table is fixed for a call. Hierarchical or nonhierarchical routing structures may be realized based on FR. In both hierarchical and nonhierarchical structures, the route set and route selection sequence are determined on a preplanned basis and maintained over a long period of time.

Time-Dependent Routing

      In TDR the routing tables are altered at a fixed point in time of the day or week. TDR routing tables are determined on a preplanned basis and implemented consistently over a time period. 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. DNHR is an example of TDR.
      In TDR, the routing tables are preplanned and designed offline using a centralized design system. The designed routing tables are loaded and stored in the switches in the TDR network, and periodically recomputed and updated (e.g., every week) by the offline system. In this way, an originating switch (OS) 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 SDR and EDR methods described below. 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.

State-Dependent Routing

      In SDR, routes are altered automatically according to the network state. For a given SDR method, the routing tables are updated 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 switches in the network. The information switch may be performed on a periodic or on-demand basis.
      The principle of SDR methods is to route calls on the best available route on the basis of network state information. For example, in the least loaded routing (LLR) method, residual capacity of the routes is calculated, and the route having the largest residual capacity is selected for the call. In general, SDR methods calculate a route cost based on various factors such as the load state or congestion state of circuit groups in the network.
      In SDR, the routing tables are designed by the OS or a central routing processor (RP) with the aid of network information obtained through information switched with other switches and/or a centralized RP. There are various implementations of SDR distinguished by 1) whether the computation of routing tables is distributed among the network switches or centralized and done in a centralized RP, or 2) whether the computation of routing tables is done periodically or call by call.
      This leads to three different implementations of SDR:
      Centralized periodic SDR: The centralized RP obtains circuit group status and traffic status information from the various switches on a periodic basis (e.g., every 10 s) and performs 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 switches on a periodic basis (e.g., every 10 s). DCR [14] is an example of centralized periodic SDR.
      Distributed periodic SDR: Each switch in the SDR network obtains circuit group status and traffic status information from all the other switches on a periodic basis (e.g., every 5 min) and performs computation of the optimal routing table on a periodic basis (e.g., every 5 min). To determine the optimal routing table, the OS executes a particular routing table optimization procedure such as LLR. WIN is an example of distributed periodic SDR.
      Distributed call-by-call SDR: An OS in the SDR network obtains circuit group status and traffic status information from the destination switch, and perhaps from selected via switches, on a call-by-call basis, and performs computation of the optimal routing table for each call. To determine the optimal routing table, the OS executes a particular routing table optimization procedure such as LLR. RTNR is an example of distributed call-by-call SDR.
       

Event-Dependent Routing

      In EDR the routing tables are updated locally on the basis of whether calls succeed or fail on a given route. In EDR, for example, a call is offered first to a fixed preplanned route, often encompassing only a direct route if it exists. If no circuit is available on the preplanned routes, the overflow traffic is offered to a currently selected alternate route. The alternate route choice is maintained as long as a call is successfully established on the route. If a call is blocked on the current alternate route choice, another alternate route is selected randomly or cyclically from a set of available alternate routes according to the given routing table rules. Examples of EDR are DAR, STR, AMI, and LAW.

Application to Emerging Technologies

      Much has been learned from these dynamic routing implementations, and the lessons and experience can be and have been carried forward as networks evolve to other technologies. While some principles of dynamic routing were implemented in first-generation data networks such as ARPANET and X.25, there are some key principles and lessons that are perhaps unique to lessons learned from circuit-switched dynamic routing, such as:       Some of these principles have been extended to packet-based networks [12]. They have been considered in ATM networks and are also extendable to traffic engineering within IP-based multiprotocol label switching (MPLS) networks. The analysis performed in [15] provides a performance analysis of lost/delayed traffic and control load for various dynamic routing methods for IP-based MPLS networks. Based on the results of these studies as well as established practice and experience, methods for dynamic routing and admission control are proposed for consideration in network evolution to IP-based technologies. In particular, we find that aggregated per-virtual-network bandwidth allocation compares favorably with per-flow allocation. We also find that event-dependent routing methods for management of label switched paths perform just as well as or better than the SDR methods with flooding, which means that EDR path selection has potential to significantly enhance network scalability.
      Lately, excellent surveys of QoS routing and traffic engineering for IP-based networks have been published [16–18]. A few early implementations of offline network-management-based traffic engineering approaches have been published, such as in the Global Crossing [19] and Level3 networks. Some studies have proposed more elaborate QoS routing and traffic engineering approaches in IP networks. However, sophisticated online QoS routing and traffic engineering methods widely deployed in TDM networks have yet to be extended to IP-based networks. Vendors have yet to announce full traffic engineering capabilities in their products. Network operator interest is also tempered by the current practice of overprovisioning IP networks, with concomitant low utilization and efficiency [20]. Anyway, there is still opportunity for increased profitability and performance in such networks through application of dynamic routing methods.
      The experience obtained in TDM networks obviously provides comprehensive knowledge for introducing dynamic routing in large-scale IP-based networks. Still, much remains to be done.

Acknowledgements

      The authors owe a debt of gratitude to the many esteemed colleagues who were kind enough to provide information contained in this article. These include Dave Allan (Nortel), Joyce Bradley (Nortel), Suching Chou (AT&T), Joachim Dressler (Deutsche Telekom), Frank Kelly (Cambridge University), Peter Key (Microsoft), Christopher Kwan (AT&T), Kenichi Mase (Niigata University), Deep Medhi (University of Missouri, Kansas City), Joyce Migdall (AT&T), Arne Oestlie (Telenor), Manuel Villèn-Altamirano (Telefonica), and Ben Vos (Sprint).

References

[1] J. H. Weber, “Some Characteristics of Communications Networks with Automatic Alternate Routing,” Bell Sys. Tech. J., vol. 41, no. 2, 1965.
[2] K. S. Narendra, E. A. Wright, and L. G. Mason, “Applications of Learning Automata to Telephone Traffic Routing and Control,” IEEE Trans. SMC, vol. 7, no. 11, 1977.
[3] G. R. Ash, R. H. Cardwell, and R. P. Murray, “Design and Optimization of Networks with Dynamic Routing,” Bell Sys. Tech. J., vol . 60, no. 8, 1981.
[4] E. Szybicki and A.E. Bean, “Advanced Traffic Routing in Local Telephone Network: Performance of Proposed Call Routing Algorithms,” Proc. Int’l. Teletraffic Cong., ITC 9, Torremolinos, Spain, 1979.
[5] P. Gauthier and P. Chemouil, “A System for Testing Adaptive Traffic Routing in France,” Proc. GLOBECOM ’87, Tokyo, Japan, 1987.
[6] P. Chemouil, J. Filipiak, and P. Gauthier, “Analysis and Control of Traffic Routing in Circuit-Switched Networks,” Comp. Networks and ISDN Sys., vol. 11, no. 3, 1986.
[7] ITU/UNDP Seminar on Intelligent Routing Strategies Including Network Management Aspects, Zruc, Czechoslovakia, 1986.
[8] Special Issue on Advanced Traffic Control Methods for Circuit-Switched Telecommunications Networks, IEEE Commun. Mag., vol. 28, no. 10, Oct. 1990.
[9] Special Issue on Dynamic Routing in Telecommunications Networks, IEEE Commun. Mag., vol. 33, no. 7, 1995.
[10] ITU-T Rec. E.170, “Traffic Routing Principles,” 1988.
[11] ITU-T Rec. E.350, “Dynamic Routing Interworking,” 1992.
[12] ITU-T Rec. E.360, “QoS Routing and Related Traffic Engineering Methods for Multiservice TDM-, ATM-, and IP-Based Networks,” 1997.
[13] G. R. Ash, Dynamic Routing in Telecommunications Networks, McGraw-Hill, 1998.
[14] J. Regnier and W. H. Cameron, “State-Dependent Dynamic Traffic Management for Telephone Networks,” IEEE Commun. Mag., vol. 28, no. 10, 1990.
[15] G. R. Ash, “Performance Evaluation of QoS-Routing Methods for IP-Based Multiservice Networks,” Comp. Commun., July 2003, http://www.research.att.com/~jrex/jerry/
[16] D. Awduche, “MPLS and Traffic Engineering in IP Networks,” IEEE Commun. Mag., vol. 17, no. 12, 1999.
[17] E. Crawley, F. Nair, B. Rajagopalan, and H. Sandick, “A Framework for QoS-Based Routing in the Internet,” RFC 2386, Aug. 1998.
[18] D. Awduche et al., “Overview and Principles of Internet Traffic Engineering,” May 2002.
[19] X. Xiao et al., “Traffic Engineering with MPLS in the Internet,” IEEE Network, March 2000.
[20] A. Odlyzko, “Data Networks Are Lightly Utilized, and Will Stay that Way,” Rev. Network Econ., vol. 2, no. 3, Sept. 2003.