Copyright 1998 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This article was published in the May 1998 issue of
IEEE Communications Magazine.

Abstract Network design is a compromise between two conflicting requirements: high network efficiency and high quality of service (QoS). High efficiency suggests full sharing of network resources. However, in a multiclass network, QoS differentiation among several traffic classes suggests traffic segregation and resource partitioning. High efficiency in a partitioned network can be realized by elastic time-varying partitioning of the network capacity. The network can be laterally divided into bands, and each band may be reconfigured frequently, under the constraint of the fixed total capacity. Rapid partitioning is facilitated by two main developments: the capability of high-speed transfer of control data, and the ease of dynamic partitioning of link capacity. This article describes how elastic network bands are used to realize an efficient network serving heterogeneous traffic. It also discusses the intraband management of independent connections and reserved end-to-end paths so that the connection-request processing load is reduced while a high transport-capacity utilization is maintained.

Adaptive Configuration of Elastic High-Speed Multiclass Networks

James Yan
Nortel

Multiservice networks may carry traffic connections of distinctly different characteristics and service requirements. The connections share network links, switching nodes, and processing facilities. Meeting the different service requirements is facilitated by sorting the traffic into classes which may be treated differently. The varying requirements of traffic classes are difficult to satisfy without traffic segregation and network partitioning into bands. Open-loop and closed-loop controls, for example, may have conflicting attributes, but both can operate efficiently in the same network if each is applied to a separate, but adjustable, network band.
In addition to varying service requirements, the traffic intensities of the individual traffic classes are unpredictable; hence the need for elastic boundaries between successive bands. Each network band should correspond to a traffic class, and a traffic class should be treated similarly across the network. It is well known that full sharing of resources yields the highest efficiency. However, the partitioned multiclass network can achieve a comparable efficiency if the class allocations are modified to closely follow the traffic variations.
In a multiservice elastic network, the network design process involves two main steps: determining the aggregate network topology and capacity, and the partitioning of the capacity among the network bands. The aggregate network design is a slow process based on a long-term forecast of the overall traffic, and is normally performed "offline." In contrast, network bands must be modified frequently (every few seconds), and based on fresh traffic data and network-state information.
The technique of dividing the network into bands, often called virtual networks, has been discussed extensively in the literature (e.g., [1–5] and the references therein).

Definitions and Background

Traffic Management

Traffic management refers to the allocation of network resources in order to satisfy the capacity and performance requirements of the services supported by the network. In an elastic multiclass network, this function also includes the sizing of each network band.
A pragmatic solution to traffic management is to divide the traffic into a manageable number of classes, whose definition may depend on:

The transaction format (STM, ATM, IP, etc.)
The method of transaction processing (connection-oriented or connectionless)
The method of flow control (open or closed loop)

The term "transaction" is used to denote the process of transferring information from a source to a sink in a single session. A class may include several connections of similar traffic descriptors, or may represent a single connection, naturally with a high-bit-rate requirement. A class may also include connectionless traffic with no quality of service (QoS) requirements.
Different routing schemes and admission criteria may apply to the network bands. For example, a voice-service class may use a simple routing scheme, while classes of higher-speed connections may use an elaborate state-dependent selective-routing scheme [6]. In addition to the difference in routing and admission criteria, operational measurements, tariff setting, and billing procedures may differ among the classes.
The creation of bands and the differing service requirements, given the potentially widely varying requirements of the traffic types, suggest that different connection admission and routing criteria be used independently within the bands. The allocation of the service-rates for the bands must observe the available capacity of the physical network.

Service-Rate Control

Service-rate discipline comes naturally in synchronous channelized circuit switching. In asynchronous communications, service-rate controllers are needed to regulate the service rate for connections or classes of connections. Two service-rate disciplines can be realized: a fixed service rate per class and a guaranteed-minimum rate per class. The selection of the service discipline depends on the traffic type. Figure 1 shows a node with rate regulators at each link. The capacity of each link is divided among the classes it supports. The links may be partitioned differently, as indicated in Fig. 1.

Paths and Connections

It is important to note the difference between a path and a connection. A path is a reserved route between two nodes, possibly traversing several intermediate nodes. The intermediate nodes in a path are involved in the path allocation process only when the path is first established or when its capacity allocation is modified. A path may accommodate a large number of connections, possibly several hundreds, between its end nodes. The originating node views the path as a direct connection to the destination node. The intermediate nodes in a path are not involved in the admission of the individual connections belonging to the path. A path may serve multiclass traffic. However, the class definition is only relevant to the end nodes.
A connection may belong to a reserved path or be independent, seeking acceptance at emanating links at its origin and, possibly, at a number of intermediate links to its destination. For brevity, an independent connection is occasionally called a connection throughout the text. A connection belonging to a path is identified as a path connection. Each node traversed by a connection is involved in the interrelated decisions regarding the admission, or otherwise, of the connection request and the actual selection of the end-to-end path (i.e., routing of the connections).
A path or a connection may or may not have capacity reservation. Capacity reservation is necessary to achieve a specified QoS. Without capacity reservation, the QoS can be based only on weighted priority or some other class differentiation, and the path or connection is used only to facilitate the forwarding of packets at the nodes. Figure 2 attempts to illustrate the difference between a path and an independent connection. A solid line through a node indicates that the node is not involved in the connection setup.

Adaptive Network Partitioning and Adaptive Routing: Two Degrees of Freedom

More flexible controls, with two degrees of freedom, are realized by employing adaptive routing in addition to adaptive network partitioning. Within each network band, adaptive alternate routing may be used to balance the traffic intensity across the network and hence increase the efficiency of the band. The elastic boundaries may vary slowly, typically in seconds between successive changes, while adaptive routing is applied on a per-connection basis. The two complement each other.

Connectivity

Connectivity may be defined in terms of the network average of the traffic-weighted mean number of hops between origin and destination. The higher the mean number of hops per connection, the lower the connectivity. Higher connectivity implies a lower processing load. Adaptive control enhances connectivity, and hence improves efficiency and service quality.

Network Bands in a Multiclass Network

The switching nodes can use rate controllers to divide the capacity of each link among the connection classes according to some rules. Because a large proportion of connections traverses more than one link, the rate allocations per band at the nodes cannot be done independently and must be coordinated among the nodes in order to ensure that the physical constraints are observed and the end-to-end service requirements satisfied.
Harmonious interworking among nodes requires a unified definition of the classes across the network. By requiring that a connection be contained within the same class as it traverses the end-to-end route, the network automatically breaks up into a set of lateral bands. Thus, the multiclass rate-regulated network may be viewed as a number of parallel network bands. A network band may adopt STM, ATM, IP, or any other transfer mode. Since the basic problem is that the knowledge of traffic intensities is unpredictable, the boundaries between successive layers must be elastic. Elastic boundaries may be modified adaptively with traffic variation. The traffic classes may arbitrarily be mapped to the network bands. However, it is simpler to let each traffic class correspond to a band.
A network band may comprise paths and connections. Low-bit-rate high-call-rate traffic, such as voice traffic, is a prime path candidate. By contrast, high-bit-rate connections are naturally requested at a lower rate and are better served by independent connections. With appropriate selection of path sizes, and with proper splitting of the traffic between paths and connections, a partitioned network can be almost as bandwidth-efficient as a fully shared network, while reducing the call-processing load and facilitating QoS differentiation.

Configuring a Network Band

The traditional approach to configuring a communication network is to seek an optimal trade-off between transport and processing efficiency. This results in splitting the traffic between a set of direct routes and transit routes. Direct routes consume less transport and processing resources than transit routes; however, due to the random fluctuations of traffic intensities, a direct route may occasionally suffer from low utilization. This is specially the case for low-intensity traffic streams which, naturally, have high variability (high ratio of the standard deviation to the mean of traffic intensity).
Transit routes require more transport facilities and processing at one or more intermediate nodes. With fixed link capacities, traffic consolidation through tandem nodes increases the overall network efficiency. An important characteristic of transit routes is that traffic deviation from estimate can be reduced by traffic consolidation. However, a direct route can also be quite efficient if its capacity can be modified to follow the slow variation of its aggregate traffic intensity, which leads to an efficient meshed network.
In a high-speed multiservice network serving bursty traffic, processing at the transit points naturally becomes more complex than in traditional telephony applications. This makes the relative cost of the transit routes higher and biases the network-sizing exercise toward selecting direct routes.

Processing Load

With extensive use of transit connections, a high-rate transaction processing capability is needed at tandem nodes. For example, a tandem switch of 1 Tb/s capacity, with a mean connection bit rate of 1 Mb/s, may handle about 1 MErl of traffic. At a mean holding time of 100 s/connection, say, the switch must be able to setup some 10,000 (one-way) connections/s if it is used as a pure tandem node. However, if, for example, 80 percent of the traffic which traverses the node does not need connection setup, being associated with already setup paths, the switch would have to setup only 2000 (one-way) connections/s.
A transit connection requires much more computational effort than a connection routed through a path. A path switch may be viewed as a flexible cross-connect which can modify the path capacity allocations between its inlet and outlet ports in a relatively short time, possibly on the order of a few microseconds. The rate at which the path capacity is modified would naturally be orders of magnitude lower than the rate at which independent connections are established. Thus, a path switch requires much less call-processing capacity than a connection switch.
A connection switch may require high processing capacity. In order to reduce the processing cost, a practical approach is to seek an optimal split of the traffic between path and connection modes so as to reduce the processing load while realizing an acceptable link utilization. In such a scheme, the path sizes are modified frequently according to traffic intensity and composition, and a common connection allocation in each link or band accommodates low-intensity traffic streams in addition to connection overflow from paths.
Figure 3 depicts three options for managing a network. At one extreme, a node handles purely path traffic, and only path setup is required. At the other extreme, connection setup is performed for each connection. The partitioning of capacity between paths and connections may differ from one link to the next, as illustrated in Fig. 4. In the figure, link 1 has a larger proportion of its capacity allocated to connections, while link 2 has a larger proportion allocated to paths.
In general, connections yield better transport efficiency than paths, while paths yield much better processing throughput. The compromise is a mixed path-connection switch with an adaptable boundary between the path and connection allocations. For a given traffic composition, a qualitative view of the dependence of transport efficiency and processing throughput on the proportion of switch capacity allocated to independent connections is shown in Fig. 5. As the connection proportion increases, the transport efficiency moderately increases and the connection-processing throughput rapidly decreases.
The traffic efficiency of a path can be increased by allowing limited queuing of connection requests at edge nodes. If a path does not have sufficient free capacity to accommodate a new arrival, the connection request is either overflowed to a transit band or blocked. Allowing the connection request to wait until sufficient free capacity in the designated path becomes available, or a timeout threshold is reached, may significantly improve the path efficiency and decrease the overall processing effort.
It is noted that the connection admission process for the connections belonging to a path takes place only at the edge node; in general, this requires less effort since the information required to handle the connection is available locally at the originating node.
A compromise arrangement is to use individual paths to reduce the processing effort, and a shared capacity allocation for connections. Other traffic streams whose low traffic intensities do not justify establishing a path may also use the shared connection allotment. This is illustrated in Fig. 6, which shows several paths overflowing to a common connection allotment, possibly within the same network band. Each path is sized to accommodate most of the traffic between its end nodes. At the call level, blocked path connections may overflow to the shared independent-connection allocation. At the data level, packet-type connection traffic may use vacant time slots allocated to paths, as illustrated in Fig. 7. This significantly increases the traffic capacity of the link and brings the overall bandwidth efficiency closer to that of a fully shared link without affecting the paths' performance. The optimal splitting of a link capacity between paths and connections is determined dynamically to follow the traffic load variation. The path-connection organization of Fig. 6 and Fig. 7 applies to a single-band or multiband network.

Sizing the Entire Network

Planning a telecommunications network requires traffic characterization, performance estimation as a function of traffic load, and estimates of the spatial traffic distribution. Given the difficulty of traffic characterization and performance estimation in a multiservice network, effective network controls may be based on real-time traffic and performance measurements and projection.
The total network must be provisioned to serve the combined traffic load of all classes. The total traffic is, of course, a moving target. However, the total traffic is less volatile than the traffic loads of the individual classes. Frequent restructuring of the class partition, under the constraints of the capacity limitation of the total network, results in high transport and processing efficiency.
Frequent capacity partitioning requires high-speed network analysis and synthesis algorithms as well as the capability of real-time reporting of traffic and network-state data. Computationally efficient algorithms capable of sizing networks of several hundred nodes are necessary for realizing this scheme. Algorithms for combined dimensioning and routing-table update can also be devised for connection-based networks, and other multiservice networks, as illustrated in [7].
Networkwide control in such an adaptive system can be complicated by the delays of transferring measurements from the nodal observation points to the controller, the processing time at the controller, and the transfer of commands from the controller to the controlled nodes. Even though the aggregate delay may be on the order of only a fraction of a second, the high transmission rate may require that the data received by the controller be projected to correspond to the likely traffic condition at the time the nodal control takes effect.
Capacity allocation of a network band cannot be done independent of the allocations for other bands, since the total allocations must be within the aggregate network capacity. A simple technique for multiband sizing is to size the bands sequentially while observing the total capacity limitation. A given band is sized to serve its traffic at the required QoS, under the constraints of the total network capacity. The next band is then sized under the constraint of the remaining capacity. The available capacity is updated after each band is considered, and each subsequent band, if any, bases its allocation on the updated available capacity. Allocation updates take place periodically, and to avoid unfairness the starting band may be selected in a cyclic fashion. The sequential approach, however, is slow and is not practical with a large number of bands. An alternative approach, which can benefit from parallel processing, is to size all the bands simultaneously, with iterative adjustments when the total computed capacity required to serve the traffic traversing a link exceeds the link's capacity, as illustrated in Fig. 8. The successive allocation process is terminated when no further progress is possible and the unserved demand, if any, is rejected.

Components of the Capacity Allocation Process

The capacity control process is depicted in Fig. 9. The traffic data and network state information can be transported to the network controller through the broadband network in a fraction of a second. The controller determines the capacity partition for each link. One of the outputs of the controller is a set of alternate routes for each origin-destination pair. The classes may adopt different routing schemes, and the routing instructions from the controller may vary accordingly. Modifications of service rate allocations and possible changes in candidate route sets can be transferred from the controller to the individual nodes in milliseconds.
High-speed algorithms can be developed for capacity allocations in networks of several hundred nodes. The execution time would be on the order of several seconds. The individual nodes can implement rate allocation changes for each link in microseconds, based on new allocations communicated by the controller.

Networkwide Service Rate Control

Figure 10 is an illustration of networkwide capacity control in a network serving data, voice, and video traffic. A possible implementation is to use a central controller as a server connected to one of the switching nodes. The controller interacts with the participating nodes through high-priority connections. The controller must be aware of the network topology which is reported by the individual nodes as the need arises. In a network, or a network band, which employs dynamic selective routing, the controller determines -- for each node pair -- a set of direct routes and candidate alternate routes. If the routing is based on the shortest paths, the controller reports to each node the immediate outgoing link toward the destination. In a very-large-scale network, it may be advantageous to construct a hierarchy of controllers. Effective distributed control is also feasible.

Summary

The underlying methodology in an automated adaptive capacity management scheme is based on the following main components:

Adaptive partitioning of the physical network into network bands
A method of managing each network band based on an optimal split of the traffic between paths and independent connections, and using independent connections for low-intensity traffic streams
An algorithm for efficiently allocating the network capacity among the bands, taking into account the overall physical capacity
A method of controlling a multiclass network based on traffic measurements and projection, network state information, and the QoS requirement of each network band
A method of information collection and implementation of capacity allocation decisions using service rate controllers at each node

Concluding Remarks

It is recommended that a multiclass network adaptively divide its capacity among designated classes of service, and adaptively modify its routing parameters and other control functions. The article emphasizes the need for a real-time network configuration process based on traffic measurements and projection, and fast network analysis and synthesis algorithms. The approach applies to networks employing a variety of data transfer modes. Elastic network bands allow QoS differentiation among traffic classes, and also facilitate coexistence with connectionless traffic classes.
The objective is an elastic class-based network with class-defined QoS. The elastic network relies heavily on fast real-time configuration of each network band under the overall physical capacity constraints.

Acknowledgments

The author would like to thank Dr. S. Khorsandi and Dr. S. I. A. Shah for their contribution.

References
[1] H. Saito, "Measurement Driven Traffic Technologies in ATM Networks," ITC Specialists Sem., The Netherlands, 1995, pp. 263–72.
[2] J. Yan, S. Shah, and M. Beshai, "Service-Specific Networks within a Shared Network," IEEE Symp. Planning and Design of Broadband Networks, Montebello, Québec, Canada, Oct. 1996.
[3] S. Shah, J. Yan, and M. Beshai, "Designing for Uncertainties of ATM Traffic," Proc. Asia Telecom, Singapore, June 1997.
[4] S. Shioda et al., "Self-Sizing Network: A New Network Concept Based on Autonomous VP Bandwidth Adjustment," Proc. Int'l. Teletraffic Cong., ITC15, Washington, DC, June 1997, pp. 997–1006.
[5] Z. Dziong, J. Zhang, and L. Mason, "Virtual Network vs. Virtual Path Design for ATM Networks," Proc. Int'l. Teletraffic Cong., ITC15, Washington, DC, June 1997, pp. 1007–18.
[6] M. Beshai and J. Yan, "Conflict-Free Selective Routing in an ATM Network," Int'l. Network-Planning Symp., Sydney, Australia, Nov. 1996.
[7] J. Yan and M. Beshai, "Designing an ATM-Based Broadband Network: An Overview," GLOBECOM '95, Singapore, Nov. 1995.

Biography
James Yan [M] received his B.A.Sc., M.A.Sc., and Ph.D. degrees in electrical engineering from the University of British Columbia,Vancouver, Canada. Since joining Nortel (Northern Telecom) in 1976, he has worked on digital switching systems performance, private networks planning, network design tools development, transport products planning, operations systems planning, business services evolution, and corporate networks evolution planning. From 1988 to 1990 he participated in an exchange program with the Canadian Federal Government, where he was project prime for the planning of the evolution of the nationwide federal government telecommunications network. He is currently the senior manager of the Webtone Network Performance Department in Advanced Technology, Nortel. He is a member of the Professional Engineers of Ontario.