IMA
Journal of Mathematical Control and Information 7 (1990) 77-11.
This paper considers various aspects of dynamic routing in fully connected circuit-switched networks. Bounds are obtained for the performance of any dynamic routing scheme, some theoretical considerations affecting the choice of trunk reservation parameters are presented, and a very simple dynamic routing scheme called dynamic alternative routing is described, which performs well under a variety of conditions. Finally, some of the capacity planning issues which arise for networks using dynamic routing are discussed.
Two approaches in particular have received considerable attention. In the United States, AT&T has implemented a scheme called dynamic nonhierarchical routing (DNHR) (Ash et al., 1981a,b; Ash, 1985), which uses traffic forecasts for different times of the day in a large-scale optimization procedure to predetermine a routing pattern. This pattern may be changed hourly, typically in relation to time-zone differences. In Canada, Bell-Northern Research has proposed a scheme, called dynamically controlled routing (DCR), based on a central controller which receives information on the current state of all links at regular intervals of about 5-10 seconds (Cameron et al, 1983; Carol, 1988). This information is used by the controller to determine a routing pattern which is then distributed back to the nodes.
Later in this paper, we discuss a third approach, which we believe has advantages for certain forms of network, and which is currently being implemented in the British Telecom main network (Stacey & Songhurst, 1987; Gibbens, 1988; Gibbens et al, 1988; Key & Whitehead, 1988). The scheme we describe does not use central control, detailed informating-passing between nodes, or advance planning of routing patterns. It is designed primarily for use in fully connected or almost fully connected networks, and employs a random search technique to hunt for beneficial routing patterns.
In this paper, we present some of the theoretical background to this work. A problem with any discussion of dynamic routing is the enormous variety of issues that arise, and the great range of possible network structures. Here, we concentrate on one particular network structure, the fully connected network, in the hope that for this structure at least we can illuminate the interaction between issues of efficiency, robustness, simplicity, and planning.
A dynamic routing scheme must decide whether an arriving call should be accepted and, if so, how the call should be routed. In a fully connected network, the natural first-choice rute for a call is via the corresponding direct link: the important question for a dynamic routing scheme then becomes whether a call blocked on its first-choice route should be accepted on a two-link alternative path and, if so, which one. We shall occasionally mention the possibility that a call might be connected along a path of more than two links, but for the networks we consider this possibility is rarely of interest and we shall exclude it from our formal development.
The organization of the paper is as follows. In Section 2, we derive bounds on the overall performance of a dynamic routing scheme under a fixed pattern of offered traffic. These bounds provide a measure of the extent to which it may be possible to improve on the performance of any given scheme. We discuss two distinct types of bound. The first we term a max flow bound. It is similar to the bound of Franks & Rishel (1973), and holds under minimal assumptions concerning the stochastic structure of the system. The second bound we consider, termed the Erlang bound, applies when streams of offered traffic are Poisson, and is obtained by consideration of the random flows across cuts of the network.
In Section 3, we study symmetric networks, making use of a fixed-point approximation procedure which has a long history in the telecommunications literature, and which provides considerable insight into the behaviour of circuit-switched networks. For example, it is well known that unrestricted use of alternative routes by a dynamic routing scheme may severely degrade the performance of a network, and that trunk reservation procedures provide a simple and effective method of restriction (Songhurst, 1980). In Section 3.1, we use the fixed-point approximation to model the effect of trunk reservation. In Sections 3.2 and 3.3, we use the approximation to assess the benefit to be obtained by allowing a wide choice of alternative routes for a call. A conclusion we reach in Section 3 is that in networks with well-matched traffic and capacity, there is limited potential for dynamic routing to improve network performance.
In Section 4, we describe the scheme referred to above, termed dynamic alternative routing (DAR), and analyse its behaviour under a variety of conditions. We show that many of the major benefits of dynamic routing can be achieved with a very simple scheme which is easy to comprehend, to analyse, and to adapt to special circumstances.
In Section 5, we consider how the capacities of links within a network should be chosen. This, the dimensioning problem, is an important aspect of any dynamic routing scheme: if the scheme is to deal with the failure or overloading of a link by rerouting traffic, then the network should be dimensioned so that there exist alternative routes that can cope. The results of Gomory & Hu (1961, 1962) and Ford & Fulkerson (1962) provide a framework for the study of this problem, and we show that their results can be used when paths are restricted in length to at most two links.
In pioneering early work on routing and control in communication networks, Weber (1964a,b) used a series of simulation studies to examine the effectiveness of various alternative routing schemes and their performance under overload, and to argue for the widespread use of trunk reservation schemes. These are some of the central issues of this paper, but here we are especially concerned with the development of analytical tools to complement simulation. For more information on simulation studies of DAR, the reader is referred to Gibbens (1988) and Gibbens et al. (1988).