ROUTING IN CIRCUIT-SWITCHED NETWORKS

ROUTING IN CIRCUIT-SWITCHED NETWORKS

In a large circuit-switched network, such as the AT&T long-distance telephone network,

many of the circuit connections will require a path through more than one

switch. When a call is placed, the network must devise a route through the network

from calling subscriber to called subscriber that passes through some number of

switches and trunks. There are two main requirements for the network's architecture

that bear on the routing strategy: efficiency and resilience. First, it is desirable

to minimize the amount of equipment (switches and trunks) in the network subject

to the ability to handle the expected load. The load requirement is usually

expressed in terms of a busy-hour traffic load; this is simply the average load

expected over the course of the busiest hour of use during the course of a day. From

a functional point of view, it is necessary to handle that amount of load. From a cost

point of view, we would like to handle that load with minimum equipment. However,

there is another requirement, namely, resilience. Although the network may

be sized for the busy hour load, it is possible for the traffic to temporarily surge

above that level (for example, during a major storm). It will also be the case that,

from time to time, switches and trunks will fail and be temporarily unavailable

(unfortunately, maybe during the same storm). We would like the network to provide

a reasonable level of service under such conditions.

The key design issue that determines the nature of the tradeoff between efficiency

and resilience is the routing strategy. Traditionally, the routing function in

public telecommunications networks has been quite simple. In essence, the switches

of a network were organized into a tree structure, or hierarchy. A path was constructed

by starting at the calling subscriber, tracing up the tree to the first common

node, and then tracing down the tree to the called subscriber. To add some

resilience to the network, additional high-usage trunks were added that cut across

the tree structure to connect exchanges with high volumes of traffic between them;

in general, this is a static approach. The addition of high-usage trunks provides

redundancy and extra capacity, but limitations remain both in efficiency and

resilience. Because this routing scheme is not able to adapt to changing conditions,

the network must be designed to meet some typical heavy demand. As an example

of the problems raised by this approach, the busy hours for east-west traffic and

those for north-south traffic do not coincide; they each place different demands on

the system. It is difficult to analyze the effects of these variables, which leads to

oversizing and, ultimately, inefficiency. In terms of resilience, the fixed hierarchical

structure with supplemental trunks may respond poorly to failures. Typically in

such designs, the result of a failure is a major local congestion at that location.

To cope with the growing demands on public telecommunications networks,

virtually all providers have moved away from the static hierarchical approach to a

dynamic approach. A dynamic routing approach is one in which routing decisions

are influenced by current traffic conditions. Typically, the circuit-switching nodes

have a peer relationship with each other rather than a hierarchical one. All nodes

are capable of performing the same functions. In such an architecture, routing is

both more complex and more flexible. It is more complex because the architecture

does not provide a "natural" path or set of paths based on hierarchical structure;

but it is also more flexible, as more alternative routes are available.

Two broad classes of dynamic routing algorithms have been implemented:

alternate routing and adaptive routing.

Alternate Routing

The essence of alternate-routing schemes is that the possible routes to be used

between two end offices are predefined. It is the responsibility of the originating

switch to select the appropriate route for each call. Each switch is given a set of preplanned

routes for each destination, in order of preference. The preferred choice is

a direct trunk connection between two switches. If this trunk is unavailable, then the

second choice is to be tried, and so on. The routing sequences (sequence in which

the routes in the set are tried) reflect an analysis based on historical traffic patterns,

and are designed to optimize the use of network resources.

If there is only one routing sequence delined for each source-destination pair,

the scheme is known as a fixed alternate-routing scheme. More commonly, a

dynamic alternate-routing scheme is used. In the latter case, a different set of preplanned

routes is used for different time periods, to take advantage of the differing

traffic patterns in different time zones and at different times of day. Thus, the routing

decision is based both on current traffic status (a route is rejected if busy)

and historical traffic patterns (which determine the sequence of routes to be

considered).

A simple example is shown in Figure 8.9. The originating switch, X, has four

possible routes to the destination switch, Y. The direct route (a) will always be tried

first. If this trunk is unavailable (busy, out of service), the other routes will be tried

in a particular order, depending on the time period. For example, during weekday

mornings, route b is tried next.

A form of the dynamic alternate-routing technique is employed by the Bell

Operating Companies for providing local and regional telephone service [BELL90];

it is referred to as multialternate routing (MAR). This approach is also used by

AT&T in its long-distance network [ASH90], and is referred to as dynamic nonhierarchical

routing (DNHR).

Adaptive Routing

An adaptive-routing scheme is designed to enable switches to react to changing traffic

patterns on the network. Such schemes require greater management overhead,

as the switches must exchange information to learn of network conditions. However,

compared to an alternate-routing scheme, an adaptive scheme has the potential

for more effectively optimizing the use of network resources. In this subsection,

we briefly describe an important example of an adaptive-routing scheme.

Dynamic traffic managemenl (DTM) is a routing capability developed by

Northern Telecom and used in the Canadian national and local telephone networks

[REGN90].

DTM uses a central controller to find the best alternate route choices depending

on congestion in the network. The central controller collects status data from

each switch in the network every 10 seconds to determine preferred alternate

routes. Each call is first attempted on the direct path, if any exists. between source

and destination switches. If the call is blocked, it is attempted on a two-link alternate

path.

Each switch i communicates the following traffic measurements to the central

controller:

The use of a set of parameters based on network status provides a powerful

routing capability. Furthermore, it becomes an easy matter to experiment with various

ways of determining the values of parameters and assessing their effect on performance.

For example, the parameter PA, can be set to a fixed value in a relatively

stable network, or the overflow measurement 0, can be used.

8.5 CONTROL SIGNALING

In a circuit-switched network, control signals are the means by which the network

is managed and by which calls are established, maintained, and terminated. Both

call management and overall network management require that information be

exchanged between subscriber and switch, among switches, and between switch and

network management center. For a large public telecommunications network, a relatively

complex control-signaling scheme is required. In this section, we provide a

brief overview of control-signal functionality and then look at the technique that is

the basis of modern integrated digital networks: common channel signaling.

Signaling Functions

Control signals affect many aspects of network behavior, including both network

services visible to the subscriber and internal mechanisms. As networks become

more complex, the number of functions performed by control signaling necessarily

grows. The following functions, listed in [MART90], are among the most important:

1. Audible communication with the subscriber, including dial tone, ringing tone,

busy signal, and so on.

2. Transmission of the number dialed to switching offices that will attempt to

complete a connection.

3. Transmission of information between switches indicating that a call cannot be

completed.

4. Transmission of information between switches indicating that a call has ended

and that the path can be disconnected.

5. A signal to make a telephone ring.

6. Transmission of information used for billing purposes.

7. Transmission of information giving the status of equipment or trunks in the

network. This information may be used for routing and maintenance purposes.

8. Transmission of information used in diagnosing and isolating system failures.

9. Control of special equipment such as satellite channel equipment.

As an example of the use of control signaling, consider a typical telephone

connection sequence from one line to another in the same central office:

1. Prior to the call, both telephones are not in use (on-hook). The call begins

when one subscriber lifts the receiver (off-hook); this action is automatically

signaled to the end office switch.

2. The switch responds with an audible dial tone, signaling the subscriber that

the number may be dialed.

3. The caller dials the number, which is communicated as a called address to the

switch.

4. If the called subscriber is not busy, the switch alerts that subscriber to an

incoming call by sending a ringing signal, which causes the telephone to ring.

5. Feedback is provided to the calling subscriber by the switch:

a) If the called subscriber is not busy, the switch returns an audible ringing

tone to the caller while the ringing signal is being sent to the called

subscriber.

b) If the called subscriber is busy, the switch sends an audible busy signal to

the caller.

c) If the call cannot be completed through the switch, the switch sends an

audible "reorder" message to the caller.

6. The called party accepts the call by lifting the receiver (off-hook), which is

automatically signaled to the switch.

7. The switch terminates the ringing signal and the audible ringing tone, and

establishes a connection between the two subscribers.

8. The connection is released when either subscriber hangs up.

When the called subscriber is attached to a different switch than that of the

calling subscriber, the following switch-to-switch trunk signaling functions are

required:

1. The originating switch seizes an idle interswitch trunk, sends an off-hook indication

on the trunk, and requests a digit register at the far end, so that the

address may be communicated.

2. The terminating switch sends an off-hook followed by an on-hook signal,

known as a "wink." This indicates a register-ready status.

3. The originating switch sends the address digits to the terminating switch.

This example illustrates some of the functions performed using control signals.

Figure 8.11, based on a presentation in [FREE94], indicates the origin and

destination of various control signals. Signaling can also be classified functionally as

supervisory, address, call-information, and network-management.

The term supervisory is generally used to refer to control functions that have

a binary character (truelfalse; onloff), such as request for service, answer, alerting,

and return to idle; they deal with the availability of the called subscriber and of the

needed network resources. Supervisory control signals are used to determine if a

needed resource is available and, if so, to seize it; they are also used to communicate

the status of requested resources.

Address signals identify a subscriber. Initially, an address signal is generated

by a calling subscriber when dialing a telephone number. The resulting address may

be propagated through the network to support the routing function and to locate

and ring the called subscriber's phone.

The term call-information refers to those signals that provide information to

the subscriber about the status of a call. This is in contrast to internal control signals

between switches used in call establishment and termination. Such internal

signals are analog or digital electrical messages. In contrast, call information signals

are audible tones that can be heard by the caller or an operator with the proper

phone set.

Supervisory, address, and call-information control signals are directly involved

in the establishment and termination of a call. In contrast, networkmanagement

signals are used for the maintenance, troubleshooting, and overall

operation of the network. Such signals may be in the form of messages, such as a list

of preplanned routes being sent to a station to update its routing tables. These signals

cover a broad scope, and it is this category that will expand most with the

increasing complexity of switched networks.

Location of Signaling

Control signaling needs to be considered in two contexts: signaling between a subscriber

and the network, and signaling within the network. Typically, signaling operates

differently within these two contexts.

The signaling between a telephone or other subscriber device and the switching

office to which it attaches is, to a large extent, determined by the characteristics

of the subscriber device and the needs of the human user. Signals within the network

are entirely computer-to-computer. The internal signaling is concerned not

only with the management of subscriber calls but with the management of the network

itself. Thus, for internal signaling, a more complex repertoire of commands,

responses, and set of parameters is needed.

Because two different signaling techniques are used, the local switching office

to which the subscriber is attached must provide a mapping between the relatively

less complex signaling technique used by the subscriber and the more complex technique

used within the network.

Common Channel Signaling

Traditional control signaling in circuit-switched networks has been on a per-trunk

or inchannel basis. With inchannel signaling, the same channel is used to carry control

signals as is used to carry the call to which the control signals relate. Such signaling

begins at the originating subscriber and follows the same path as the call

itself. This process has the merit that no additional transmission facilities are

needed for signaling; the facilities for voice transmission are shared with control

signaling.

Two forms of inchannel signaling are in use: inband and out-of-band. Inband

signaling uses not only the same physical path as the call it serves; it also uses the

same frequency band as the voice signals that are carried. This form of signaling has

several advantages. Because the control signals have the same electromagnetic

properties as the voice signals, they can go anywhere that the voice signals go. Thus,

there are no limits on the use of inband signaling anywhere in the network, including

places where analog-to-digital or digital-to-analog conversion takes place. In

addition, it is impossible to set up a call on a faulty speech path, as the control signals

that are used to set up that path would have to follow the same path.

Out-of-band signaling takes advantage of the fact that voice signals do not use

the full 4-kHz bandwidth allotted to them. A separate narrow signaling band within

the 4 kHz is used to send control signals. The major advantage of this approach is

that the control signals can be sent whether or not voice signals are on the line, thus

allowing continuous supervision and control of a call. However, an out-of-band

scheme needs extra electronics to handle the signaling band, and the signaling rates

are slower because the signal has been confined to a narrow bandwidth.

As public telecommunications networks become more complex and provide a

richer set of services, the drawbacks of inchannel signaling become more apparent.

The information transfer rate is quite limited with inchannel signaling. With inband

signals, the voice channel being used is only available for control signals when there

are no voice signals on the circuit. With out-of-band signals, a very narrow bandwidth

is available. With such limits, it is difficult to accommodate, in a timely fashion,

any but the simplest form of control messages. However, to take advantage of

the potential services and to cope with the increasing complexity of evolving network

technology, a richer and more powerful control signal repertoire is needed.

A second drawback of inchannel signaling is the amount of delay from the

time a subscriber enters an address (dials a number) to when the connection is

established. The requirement to reduce this delay is becoming more important as

the network is used in new ways. For example, computer-controlled calls, such as

with transaction processing, use relatively short messages; therefore, the call setup

time represents an appreciable part of the total transaction time.

Both of these problems can be addressed with common-channel signaling, in

which control signals are carried over paths completely independent of the voice

channels (Table 8.1). One independent control signal path can carry the signals for

a number of subscriber channels, and, hence, is a common control channel for these

subscriber channels.

The principle of common-channel signaling is illustrated and contrasted with

inchannel signaling in Figure 8.12. As can be seen, the signal path for commonchannel

signaling is physically separate from the path for voice or other subscriber

signals. The common channel can be configured with the bandwidth required to

carry control signals for a rich variety of functions. Thus, both the signaling protocol

and the network architecture to support that protocol are more complex than

inchannel signaling. However, the continuing drop in computer hardware costs

makes common-channel signaling increasingly attractive. The control signals are

messages that are passed between switches as well as between a switch and the network

management center. Thus, the control-signaling portion of the network is, in

effect, a distributed computer network carrying short messages.

Two modes of operation are used in common-channel signaling (Figure 8.13).

In the associated mode, the common channel closely tracks along its entire length

the interswitch trunk groups that are served between endpoints. The control signals

are on different channels from the subscriber signals, and, inside the switch, the control

signals are routed directly to a control signal processor. A more complex, but

more powerful, mode is the nonassociated mode; with this, the network is augmented

by additional nodes, known as signal transfer points. There is now no close

or simple assignment of control channels to trunk groups. In effect, there are now

two separate networks, with links between them so that the control portion of the

network can exercise control over the switching nodes that are servicing the subscriber

calls. Network management is more easily exerted in the nonassociated

mode as control channels can be assigned to tasks in a more flexible manner. The

nonassociated mode is the mode used in ISDN.

With inchannel signaling, control signals from one switch are originated by a

control processor and switched onto the outgoing channel. On the receiving end,

the control signals must be switched from the voice channel into the control processor.

With common-channel signaling, the control signals are transferred directly

from one control processor to another, without being tied to a voice signal; this is a

simpler procedure, and one of the main motivations for common-channel signaling

as it is less susceptible to accidental or intentional interference between subscriber

and control signals. Another key motivation for common-channel signaling is that

call-setup time is reduced. Consider the sequence of events for call setup with

inchannel signaling when more than one switch is involved. A control signal will be

sent from one switch to the next in the intended path. At each switch, the control

signal cannot be transferred through the switch to the next leg of the route until the

associated circuit is established through that switch. With common-channel signaling,

forwarding of control information can overlap the circuit-setup process.

With nonassociated signaling, a further advantage emerges: One or more central

control points can be established. All control information can be routed to a

network control center where requests are processed and from which control signals

are sent to switches that handle subscriber traffic; in this way, requests can be

processed with a more global view of network conditions.

Of course, there are disadvantages to common-channel signaling; these primarily

have to do with the complexity of the technique. However, the dropping cost

of digital hardware and the increasingly digital nature of telecommunication networks

makes common-channel signaling the appropriate technology.

All of the discussion in this section has dealt with the use of common-channel

signaling inside the network-that is, to control switches. Even in a network that is

completely controlled by common-channel signaling, inchannel signaling is needed

for at least some of the communication with the subscriber. For example, dial tone,

ringback, and busy signals must be inchannel to reach the user. In a simple telephone

network, the subscriber does not have access to the common-channel signaling

portion of the network and does not employ the common-channel signaling protocol.

However, in more sophisticated digital networks, including ISDN, a

common-channel signaling protocol is employed between subscriber and network,

and is mapped to the internal-signaling protocol.