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 This article presents a discrete-event simulator, called QUARTS-II, that can be used for the design and analysis of routing protocols for ATM networks. This simulator shares many high-level features of the ATM Forum's P-NNI routing protocol; topology-state advertisement, on-demand source routing, call admission control and generic call admission control, hierarchical routing, and crank-back and rerouting. Simulations can be carried out at both the call and cell levels. Although this simulation tool has been designed primarily to simulate routing protocol, it can easily be extended to simulate other elements of an ATM traffic control architecture.

QUARTS-II: A Routing Simulator for ATM Networks

M. Sivabalan and Hussein T. Mouftah
Queen's University

The driving force behind the operation of an ATM network is a set of complex protocols operating over various timescales. ATM networks are connection-oriented, in which a route for a call between two end users is derived through a routing protocol. An important feature of such networks is that they can support a wide range of services with different traffic characteristics and quality of service (QoS) requirements on a single platform. Thus, an ATM routing protocol should take user-specified QoS requirements into consideration while choosing routes. Furthermore, a high-performance ATM routing protocol should be dynamic. Such a routing protocol is capable of adjusting the routes in response to network congestion and failure, and hence leads to an efficient utilization of network resources. After choosing a route, the network invokes its signaling protocol to establish the call on the route. Once the call is established, the ATM cells corresponding to the call are switched from the input port to the required output port at the switches along the route.
Accurate analytical approaches to studying ATM routing protocols often result in models which are very complex with a large number of state variables. Also, the underlying relationships among the variables are nonlinear and therefore further complicate the analytical models. In order to obtain tractable analytical models, simplifying assumptions have to be made. However, such assumptions may be unrealistic in practice [1]. On the other hand, simulation is a flexible tool for evaluating the performance of complex routing protocols. It is possible to design simulation models that capture the important features of an ATM routing protocol with reasonable accuracy. Queen's University ATM Routing Testbed/Simulator (QUARTS) [2] is such a simulation package, designed primarily to simulate various aspects of ATM routing protocols. It can be used for both call- and cell-level simulations. It incorporates many high-level features of the private network-to-network interface (P-NNI) routing protocol recommended by the ATM Forum [3], such as topology state advertisement, on-demand source routing, call admission control (CAC), and generic CAC (G-CAC). QUARTS-II is a successor to QUARTS and supports two more sophisticated routing features of P-NNI: hierarchical routing, and crank-back and rerouting. The source code of the simulator has been written in C programming language on a UNIX platform.
The goal of this article is to give an overview of QUARTS-II and demonstrate its application through an example. The rest of the article is organized as follows. The second section describes the building blocks of the simulator. The routing protocol and signaling protocol implemented in the simulator are described in the third and fourth sections, respectively. The fifth section presents the implementation details and operation of the hierarchical routing protocol in the simulator. In the sixth section, we use the simulator to examine the performance of a sample network. Finally, the seventh section concludes this article.

Building Blocks

The simulator has been designed in a modular fashion using a number of building blocks: a graphical user interface (GUI), an event controller, and a number of network modules and control modules. These blocks interact with each other as shown in Fig. 1. We now describe each of these building blocks in more detail.

Graphical User Interface

A user-friendly GUI simplifies the process of creating the network topology and setting the parameters for simulation runs. A network component (a switch, link, etc.) is created by choosing an item from a menu and setting the parameters in the dialog box associated with that item. An existing network file can also be modified by adding and/or deleting components. A snapshot of the GUI is shown in Fig. 2.
The GUI provides control buttons to start and stop the simulator. It also permits the user to step through a simulation with respect to time or event. This feature is very helpful during the development or modification phase of the simulator. Moreover, the simulator enables the user to instantly monitor the output statistics during the course of a simulation. However, the use of the GUI has been made optional to speed up simulation runs. Once a network model is created and the appropriate parameters are set through the GUI, the network can be simulated without the GUI for a user-specified time. This approach significantly reduces simulation time.

Event Controller

The simulator is based on discrete-event technique. A network is treated as a discrete-event system where the events of interest occur at discrete points in time, and nothing of interest takes place between these time intervals [4]. At any given time, the state of a network is determined by the states of its components. For instance, the state of a link can be represented by the available bandwidth on that link. An event is an activity that might change the network's state and is the basic executable unit in discrete-event simulation. Some typical events are call arrivals and departures, and cell arrivals and departures.
The function of the event controller is to maintain and update an event list consisting of events that are arranged in chronological order. It also maintains a global clock to keep track of the simulation time. A cycle of discrete-event simulation is depicted in Fig. 3. The event controller fires the event with the earliest occurrence time and advances the clock to the firing time of this event. When an event is fired it is removed from the event list, and the event routines associated with that event are executed. Furthermore, firing an event may create one or more future events which are then inserted at the appropriate locations in the event list. The heart of the simulation program is a loop executing the above cycle until the simulation is terminated.

Network Modules

The simulator decomposes an ATM network into three physical components: switches, links, and end systems (ESs). Each of these components is implemented by one or two network modules, as shown in Fig. 4. A link module is an abstraction of a physical link connecting two switches. A link is characterized by propagation delay, link bandwidth, operational status (whether or not the link is up), and administrative weight.
A physical switch is represented by two modules: a switch module and a route module. The switch module implements the cell-switching function of an ATM switch. A cell at an input port is switched to the corresponding output port decided at the call establishment time. The mapping between the input and output ports at each switch is implemented using a data structure called a translation table (TT). Calls originating from a given ES is uniquely identified by sequence numbers. An entry in a TT contains the identity of the originating ES and the sequence number of the call. Two kinds of buffer management schemes have been implemented: shared and output. Under the shared buffer scheme, there is a single pool of buffer space which is used on a first-come first-served basis by all the output ports of a switch. If an incoming cell finds that the buffer is full it is lost. With the output buffer scheme, each output port has its own buffer space. A switch is characterized by switching speed, cell processing delay, and buffer size. The buffer size used is the total buffer size in the shared buffer scheme and the size of each output buffer in the output buffer scheme.
The route module is the most important element that implements a topology-state (TS) routing protocol. A detailed description of this module is given in the next section. When creating a simulation network topology, a route module must be attached to a switch module. The separation of the route and switch modules facilitates the task of building an entirely different routing protocol without modifying the switch architecture.
The ESs are implemented using two modules: a source ES (SES) and destination ES (DES). An SES module generates call requests according to the specified arrival rate. It also generates the ATM cells for the active calls originated from it. The ATM cells are consumed by a DES module. An SES module should have at least one peer DES module, and only ES modules with a peer relationship are allowed to communicate. The GUI has the facility to visually provide peer relationship between an SES and one or more DES modules.
The simulator supports constant bit rate (CBR) and variable bit rate (VBR) traffic. A CBR source generates cells at the specified bit rate. The cell generation process of a VBR source is governed by a two-state on-off model. When the source is active it generates cells according to either a Poisson or deterministic process chosen before starting the simulation. The holding times of the calls from any SES is exponentially distributed with a specified mean. A switch can be attached to more than one SES module of any traffic type to create a heterogeneous environment.

Control Modules

In addition to the network modules, there are three other modules implemented to control simulations: console, output, and stopper. The console module is used to set some common simulation parameters (e.g., the seed for a random number generator). It is also used to set some particular parameters of interest globally rather than individually. For example, the bandwidths of all the links in a network can be simultaneously changed to a particular value by making a single change in the console module, rather than making a change in the dialog box of every single link. This feature is very useful, especially with a very large network, because it reduces the time required to configure and modify the simulation topology.
The output module is used to collect and display the values of performance measures of interest. This module is operated in two modes: periodical polling and event-driven update. In the former, the output module periodically visits the network modules to gather information. On the other hand, with event-driven updates whenever there is an event (e.g., a call is blocked), the associated network module invokes the output module to update the performance measures.
Finally, the stopper module is used to specify the running time of a simulation.

Components of the Routing Protocol

The TS routing protocol implemented in the route modules has two components: a routing information base (RIB) and a route computation algorithm. The RIB contains information regarding the connectivity and states of the links and switches in a network. The state of a link (switch) can be used to determine the desirability of using the link (switch) in a route. The route computation algorithm computes routes based on the contents of the RIB.
The route module supports both flat and hierarchical routing protocol. With flat routing protocol, a switch has detailed information (connectivity and state) about all the links and switches in the network. But, with hierarchical routing protocol a switch has detailed information about the links and switches that are close to it (in terms of some nearness measure) and progressively summarized information about the links and switches located further from it.

RIB

In the simulator, the state of a link or switch is specified by metrics and attributes. A metric is quantitative and can be used to determine the cost of using a link or switch during a route computation. On the other hand, an attribute is qualitative and can be used to determine whether or not a switch or link can be considered for route computation. The total and available bandwidth, and the administrative weight of a link are used as metrics, whereas the operational status, available bandwidth, and QoS parameters of a link are used as attributes. Note that the available bandwidth is used as both an attribute and a metric. This is because if a link does not have the bandwidth required by a call it should not be considered during route computation. The QoS parameters of a link are specified in terms of cell transfer delay, cell delay jitter, and cell loss ratio experienced by the link. The metric used for a switch is its buffer occupancy. This metric represents the degree to which the switch is busy. The attribute of a switch is its operational status. Given the state and connectivity information, the routing protocol can choose routes avoiding heavily loaded links and switches.
A switch is assumed to be instantly aware of the activities associated with it and its outgoing links. Thus, it immediately updates its RIB in response to these activities. Furthermore, a switch advertises its local information (states of itself and its outgoing links) to all other switches in the network through topology-state advertisements (TSAs). TSA packets are disseminated using a flooding protocol [5]. Unnecessary duplication of TSA packets are prevented using sequence numbers. Note that with flat routing protocol, a TSA packet visits every switch in the entire network at least once. However, as we explain in the fifth section, with hierarchical routing protocol, the extent to which a TSA packet is distributed within a network is limited.
A switch triggers TSAs on both a periodic and an event-driven basis. In the former, a switch triggers TSAs periodically regardless of its own activities or those of its outgoing links. In the event-driven approach, a switch triggers a TSA if it detects a significant change in its local information. How to define a significant change is an important design issue of TS routing protocol. Currently, a change in available bandwidth on a link by a specified threshold is defined as significant. We note, however, that it is easy to define more sophisticated events with a minor modification in the route module. Using the local information as well as the information obtained through the TSAs from the other switches, a switch builds a complete RIB that has enough information to compute a route from itself to any other switch in the network. Note that the portion of the RIB containing the local information of a switch is always accurate. The accuracy of the remaining portion depends on the frequency of TSAs.

Route Computation Algorithm

As with the P-NNI routing protocol, on-demand source routing is used in the simulator. Upon receiving a call request from the SES, the source switch (SS) computes a route to the destination switch (DS). When computing a route, the SS does not use the links which do not have enough bandwidth to support the call. The bandwidth requirement of a call is its equivalent bandwidth [6]. The equivalent bandwidth is a function of the traffic descriptors of the call, and, depending on the implementation, it might as well be a function of the QoS requirements of the call. Currently, three traffic descriptors are defined in the simulator: peak and mean cell rates, and mean burst length. The QoS requirements are maximum cell transfer delay, cell delay jitter, and cell loss ratio.
The SS uses its CAC algorithm to compute the equivalent bandwidth to be reserved on its outgoing links. The purpose of the CAC algorithm is to check whether the new call can be accommodated without violating the QoS guarantee provided to the existing calls. As with the P-NNI routing protocol, the simulator allows each switch to use its own CAC algorithm. The simulator provides a set of CAC algorithms based on the notion of equivalent bandwidth, and it is also very easy to add new CAC algorithms. However, in order to compute the equivalent bandwidth to be allocated on links other than the outgoing links, the SS uses the Generic CAC (G-CAC) algorithm [7]. G-CAC is a standard algorithm that any switch can use to estimate the bandwidth reserved by a possibly different CAC algorithm in another switch. The simulator provides a set of G-CAC algorithms with varying complexity, and new G-CAC algorithms can easily be incorporated. Note that simulations can be run without G-CAC, in which case the equivalent bandwidth is computed purely based on the CAC algorithm of the SS.
The SS computes a route using Dijkstra's shortest path algorithm [5]. A sample link cost function used for the algorithm is given by the following equation:

where k_a is the administrative weight assigned to the link, k_l is a constant, and U_link is the bandwidth utilization (normalized to the full bandwidth) of the link. The switch then examines the computed route to see if it satisfies the QoS requirements of the call. If the QoS requirements are satisfied, the SS is successful in finding a route.

The Signaling Protocol

The signaling protocol used to establish a call on the chosen route is implemented in the route module. We now describe the signaling protocol used in conjunction with the flat routing protocol. The signaling procedure used with the hierarchical routing protocol is slightly different, and we will elaborate on this aspect in the fifth section.
When an SES makes a call request to a DES, it submits a signaling packet to the SS. The packet is a data structure containing a number of fields, as shown in Fig. 5. The packet type is initially set to SETUP. Using the packet, the SES provides the source switch with the identity of the DES, and the traffic descriptors and QoS requirements of the call. Upon receiving the packet, the source switch attempts to find a route; if unsuccessful, it changes the packet type to REJECT and sends the packet back to the SES. In practice, if a call is blocked the caller may choose to try the call again. Currently, QUARTS-II does not support manual retrial. However, it is easy to incorporate such manual retrials via a probability of retrials and mean time between successive retrials.
If the SS successfully finds a route, a TT entry is created at the switch. The SS also appends an ordered list of all the switches in the chosen route to the packet. The packet is then forwarded to the next switch en route. The simulator supports automatic network rerouting when the chosen route cannot accept the call. The additional fields in the packet, namely the number of rerouting attempts (NRA), rerouting limit (RL), and blocking links, are provided to facilitate rerouting. The network will repeatedly try the call on alternate routes until either the call succeeds or the NRA exceeds the RL. Initially, the SS sets the value of the NRA and RL fields to zero and the specified rerouting limit (a network parameter), respectively.
As the packet progresses, each switch along the route performs an admissibility check via its CAC algorithm. If a call request passes the CAC test at a switch, a TT entry is created at the switch and the packet will be forwarded to the next switch. In the simulator, it is assumed that a DES does not deny a call request. Thus, upon receiving the signaling packet, the DS always changes the packet type to ACCEPT and sends it back to the SES. The call setup delay is the time elapsed between the arrival of the call request and the reception of the packet (of type ACCEPT) at the SES. Once the call is accepted, the SES starts to generate ATM cells according to the call's traffic descriptors.
On the other hand, if CAC rejects the call request at a switch, the switch appends the identity of the blocking link to the packet and sets the packet type to REJECT. The packet then cranks back to the SS (Fig. 6). When the SS receives the packet, it increments the value of NRA (Fig. 5). If NRA does not exceed RL, the SS attempts to compute an alternate route after excluding all the blocking links recorded in the packet from its RIB. If an alternate route is found, the SS will begin to establish the call on the alternate route; but if NRA exceeds RL, the SS will reject the call.

A Hierarchical Routing Protocol

As mentioned before, with a flat routing protocol a switch has the information about the connectivity as well as the states of the switches and links in the whole network. Even though this approach lets a switch make an accurate routing decision, it does not scale well with the network size. As networks get larger, the number of TSA packets disseminated can be overwhelmingly large and lead to a significant increase in processing, communication, and storage overheads. Hierarchical routing protocols are used to alleviate this problem [3, 8].
In the hierarchical routing approach, a network is logically divided into subnetworks called peer groups (PGs). At the lowest level of the hierarchy, each node represents a real physical switch and each link represents a physical link. A PG is represented by a single logical switch at the next level of hierarchy, and two logical switches are connected by a logical link. A switch has complete information (connectivity and state) about the switches and links in its own PG. However, it has only a partial information about the links and switches that belong to different PGs. The internal details of a PG are not revealed to the any other PG. Figure 7 shows an example of a two-level routing hierarchy with three PGs (A, B and C) at the first-level. For any switch in the PG A, for instance, the entire PG B appears as a single logical switch B. Similarly the entire PG C appears as a single logical switch C. Because of the hierarchical structure, the size of RIB at each switch is reduced. Also, as becomes evident shortly, the number of TSA packets disseminated in the network is reduced as well. The end result is the reduction in routing related overhead. However, hierarchical routing protocols are more complicated than their flat counterparts. Additionally, routes computed based on inaccurate RIB may be poor.
Currently, the simulator allows only up to two levels of hierarchy, and a future version will extend the number of levels. It is expected that even in a very large ATM network with several hundreds of thousands of switches the number of hierarchical levels will unlikely to be more than 6. So, we feel that a two-level routing hierarchy is adequate to examine the salient features of a hierarchical routing protocol in a network consisting of about 100 switches.

TSA

In the simulator, there are two levels of TSAs, one for each level. The first-level TSA packets are exchanged (via flooding) only among the switches in the same PG. These packets are not sent out to the neighboring PGs. From these packets, a switch gains complete information about the links and switches in its own PG. The state information about the logical links are advertised through the second-level TSAs. These TSA packets are flooded throughout the network as in the case of flat routing. That is, when a switch receives a second-level TSA packet it passes the packet to its neighbors in not only its own PG but also in different PGs. Upon receiving a second-level TSA packet, a switch examines the packet to find the origin of the packet and updates its RIB only if the packet has not originated within its own PG. In a given PG, the second-level TSA packets are generated by a real switch called PG leader (Fig. 7). Currently, PG leaders are fixed and are manually selected before the simulations. However, an election protocol can be easily implemented in the route module to dynamically select the PG leaders according to some policy.
We now demonstrate how switch A.1 builds its RIBs using the information gathered from TSAs. Using first-level TSAs, A.1 gets the information about all the internal links and switches in PG A as well as the external outgoing links A.3

B and A.4

C, as shown in Fig. 8. Note that there are two physical links between A.3 and PG B. For all the switches in PG A other than A.3, these links appear as a single link A.3

B. When A.3 triggers a first-level TSA, it examines the physical links A.3

B.1 and A.3

B.4 and picks the one with the largest available bandwidth¹ and reports its state to all other switches in PG A. Furthermore, through the second-level TSAs from the PG leader B.2, A.1 gets the information about logical links B

A.3 and B

C. Similarly, from the second-level TSAs from the PG leader C.2, A.1 gets the information about logical links C

B and C

A.4, and builds its RIB as shown in the figure.
A second-level TSA packet originating from a PG contains information about the logical outgoing links from that PG to the neighboring PGs. The metrics and attributes of the external links are adjusted to reflect the cost of traversing the ingress PG of that external link. For example, the metrics of the physical external links B.3

C and B.1

A are modified to incorporate the aggregated metrics of the links in PG B. The aggregation is performed by the PG leader. How to perform aggregation is an important design issue in hierarchical routing. In the simulator, we use a simple averaging method proposed in [9]. It is very easy to incorporate more sophisticated aggregation techniques in the route module.

A Signaling Example

With a flat routing protocol, only one switch (i.e., the SS) is involved in route computation. However, with a hierarchical routing protocol, the SS creates a route which is only hierarchically complete. Such a route contains an ordered list of both the physical and logical switches to be visited by the signaling packet. Because of the incomplete RIB, the SS cannot compute a detailed route segment through a PG that is different from its own. As a result, the final route to the DES is decided by not only the SES but also the entry border switches. We now demonstrate the signaling procedure for establishing a call from the SES to the DES, shown in Fig. 9. We assume that the network keeps trying the call until either it succeeds or a route cannot be found (i.e., there is no limit on the number of rerouting attempts).
The following steps are taken by the signaling protocol when the SES submits a signaling packet of type SETUP to the SS (A.1):

Assume that A.1 successfully finds a route A.1 A.2 A.3 B based on its RIB. Note that the last switch in the list is logical, because A.1 does not have the information to determine how to route the call within PG B. A.1 now forwards the packet to the switch A.2.
A.2 runs its CAC algorithm to see if the incoming call can be accepted. Let's assume that the call request is rejected. Thus, A.2 includes the identity of the blocking link A.2 A.3 in the packet and sends it back to A.1 (now the packet type is REJECT).
A.1 computes an alternate route excluding the blocking link A.2 A.3 from its RIB. Let's assume that an acceptable alternate route A.1 A.5 A.4 A.3 B is found. So A.1 forwards the packet to the next switch, A.5 (the packet type is changed to SETUP). Assume that the call setup attempt is successful all the way up to A.4, which now forwards the packet to A.3.
From the route information in the packet, A.3 finds that it has to forward the packet to PG B. A.3 has two outgoing links, A.3 B.1 and A.3 B.4, leading to PG B, and therefore has to choose one of these links using some criteria. The simulator provides a few criteria: available bandwidth, delay, and administrative weight. It is also possible to include more criteria in the simulator. Let's assume that A.3 selects A.3 B.1 and forwards the packet to B.1.
B.1 finds that the DES is in its own peer group. Hence, it attempts to compute a route to the DS B.3 based on its RIB. Let's assume that B.1 successfully finds a route segment B.1 B.2 B.3. Note that this segment contains only physical switches. B.1 then forwards the packet to B.2.
B.2 runs its CAC algorithm, and finds that the link B.1 B.2 cannot support the call. Therefore, B.2 adds the link B.1 B.2 to the blocking link list in the packet and sends it back to B.1 (the packet type is now REJECT).
Since B.1 was involved in the route computation process, it attempts to compute a new route segment after excluding the blocking link B.1 B.2 from its RIB. Let's assume that B.1 successfully finds a route segment B.1 B.4 B.3 and forwards the packet to B.4 (the packet type is changed to SETUP).
B.4 runs its CAC algorithm and finds that the link B.4 B.3 cannot support the call. Therefore, B.4 adds the link B.4 B.3 to the blocking link list in the packet and sends it back to B.1 (the packet type is REJECT).
As before, B.1 attempts to compute another route segment (after excluding the blocking links B.2 B.3 and B.4 B.3 from its RIB) and finds that it can no longer reach B.3 through PG B. So it removes the blocking links B.2 B.3 and B.4 B.3 from the blocking link list, and sends the packet backward to the previous switch A.3.
A.3 adds the logical link A.3 B to the blocking link list to prevent the SS from using this virtual link during the next route computation. It then sends the packet to the previous switch A.2. Similarly, A.2 sends the packet back to A.1.
A.1 attempts to compute an alternate path by excluding the blocking links A.2 A.3 and A.3 B from its RIB. Let's assume that A.1 successfully computes an entirely new route, A.1 A.5 A.4 C B. Therefore, it sets the packet type to SETUP and initiates the setup procedure again.
Let's assume that a call setup attempt is successful on the new route. When B.3 receives the packet it sends the packet all the way back to the SES. When the packet reaches the SES the signaling procedure is completed, and the SES begins to transmit ATM cells.

A Simulation Example

In this section, we use the simulator to compare the performance of hierarchical and flat routing protocols in a network with 16 switches, shown in Fig. 10. For hierarchical routing the network is divided into four PGs, each with four switches. All the links have identical bandwidth of 50 Mb/s. Each switch is connected with an SES and a DES. An SES is peered with all the DESs except the one attached to the same switch as itself. Also, an SES picks its destination according to a uniform distribution.
The simulation runs are carried out at the call level. We consider only a single type of CBR call; each call requires a bandwidth of 1 Mb/s. Furthermore, it is assumed that calls do not impose any QoS constraints. The call holding times are exponentially distributed with a mean of 1 min. Calls arrive at an SES according to a Poisson process, and the mean arrival rates at all SESs are identical. During the simulation, the network load was varied by simultaneously changing the call arrival rates at all SESs.
Each switch periodically triggers TSAs every 90 s. It also triggers an event-driven TSA whenever it detects a significant change in available bandwidth in any of its outgoing links. A change in available bandwidth is considered significant if the new value differs from the previously advertised value by at least 10 percent. Also, route computations are carried out using the link cost function mentioned before with k_a = 1 and k_l = 0.005 for all links. G-CAC is used during route computation. A call is tried only once, and a rejected call is assumed to be lost.
Figure 11 compares the performance of the network with flat and hierarchical routing protocols. The performance measures used are the average values of call blocking ratio, call setup delay, bandwidth utilization, and TSA packets processed per second at each switch. Each point in the curves was obtained as an average of seven independent runs.
As mentioned before, with the hierarchical routing protocol the RIBs are incomplete, so we cannot expect a switch to make better routing decisions. This is evident from the blocking performance. With moderate to high load, the hierarchical routing protocol leads to a 3 percent increase in the call blocking ratio. Another observation is that bandwidth utilization is higher with the hierarchical routing protocol. This also can be attributed to the incomplete RIBs used for route computations. We have observed that the average route length (in number of hops) per call is longer with the hierarchical routing protocol than that with the flat routing protocol. The longer the route length the larger the bandwidth required per call, and hence the higher the bandwidth requirement. Another consequence of using longer routes is the increased call setup delay with the hierarchical routing protocol, as shown in the figure.
According to the above observations, the flat routing protocol outperforms the hierarchical routing protocol with respect to almost all the performance measures considered here. However, from the viewpoint of routing overhead the hierarchical routing protocol has an edge. In the simulations we have considered only the processing component of the routing overhead, which was measured as the average number of TSA packets processed per second at each switch. It can be seen from Fig. 11 that the hierarchical routing protocol yields approximately a sixfold reduction in the overhead under moderate to heavy loads.

Conclusions

Simulation plays an important role in computer-aided analysis and design of communications networks. QUARTS-II is one such simulation package, written in C programming language on the UNIX platform. This simulator can guide the design and performance analysis of ATM routing protocols. It allows one to simulate various high-level features of the ATM Forum's P-NNI routing protocol. A user-friendly GUI facilitates the task of creating and modifying the simulation network models. Also, the discrete-event simulation paradigm makes the simulator execution-efficient.
Even though this tool has been designed specifically for ATM routing protocols, its modular structure permits one to include additional ATM traffic control schemes (flow control, usage parameter control, etc). It is also possible to design an entirely different routing protocol by creating a new kind of route module without significantly modifying the other modules.

Acknowledgments

We thank I. A. Ali of Helwan University, Helwan, Cairo, Egypt, for the valuable discussions we had during the development of the simulation package. We also gratefully acknowledge the use of event-handling and GUI routines of the MaRS simulator [10].

References
[1] R. H. Hwang, J. F. Kurose, and D. Towsley, "The Effect of Processing Delay and QoS Requirements in High Speed Networks," Proc. INFOCOM '92, vol. 1, Florence, Italy, May 1992, pp. 160–69.
[2] C. Liu, H. T. Mouftah, and M. Sivabalan, "QUARTS: A Test-bed for Dynamic Routing over ATM Networks," Canadian J. Elec. and Comp. Eng., vol.20, no. 3, 1995, pp. 117–20.
[3] The ATM Forum, "ATM Private Network-Network Interface Specification," v. 1.0, Mar. 1996.
[4] V. S. Frost and B. Melamed, "Traffic Modeling for Telecommunications Networks," IEEE Commun. Mag., vol. 32, no. 3, Mar. 1994, pp.70–81.
[5] D. Bertsekas and R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice Hall, 1992.
[6] R. Guerin, H. Ahmadi, and M. Naghshineh, "Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks," IEEE JSAC, vol. 9, no. 6, Sept. 1991, pp. 968–81.
[7] C. Liu and H. T. Mouftah, "Virtual Call Admission Control -- A Strategy for Dynamic Routing over ATM Networks," Proc. ICC '95, vol. 1, Seattle, WA, Apr. 1995, pp. 201–5.
[8] F. Amer and Y. Lien, "A Survey of Hierarchical Routing Algorithms and a New Hierarchical Hybrid Adaptive Routing Algorithm for Large Scale Computer Communication Networks," Proc. ICC '88, vol. 2, Philadelphia, PA, June 1988, pp. 999–1003.
[9] I. A. Ihab and H. T. Mouftah, "Design of Dynamic Hierarchical Routing for ATM Networks," Proc. 18th Biennial Symp. Commun., Kingston, Ontario, Canada, June 1996, pp.79–81.
[10] C. Alaettinoglu et al., "Design and Implementation of MaRS: A Routing Testbed," Tech. rep. UMIACS-TR-92-103, CS-TR-2964, Univ. of Maryland, College Park, May 1990.

Biographies
M. Sivabalan received a B.Sc. degree in electrical engineering from the University of Peradeniya, Sri Lanka, and an M.Sc. degree in the area of cryptography from the Department of Electrical and Computer Engineering, Queen's University, Kingston, Ontario, Canada, where he is now a Ph.D. candidate. His current research area is routing in high-speed networks.
Hussein T. Mouftah [F] has been a professor in the Department of Electrical and Computer Engineering, Queen's University, Kingston, Ontario, Canada since 1979. Prior to that he worked with the Data Systems Planning Department at Nortel Technology (then BNR), Ottawa, Canada, for three years. He has also spent his sabbatical years, 1986–1987 and 1993–1994, with Nortel Technology working in the area of high-speed integrated networks, routing, and traffic management. Since 1989 he has been a principal investigator for the Telecommunications Research Institute of Ontario (TRIO), a government Centre of Excellence in Communications responsible for a project on broadband packet switching Networks. He is the recipient of the 1989 Engineering Medal for Research and Development of the Professional Engineers of Ontario (PEO). He is the joint holder of an Honorable Mention for the Frederick W. Ellersick Prize paper award for the best paper in IEEE Communications Magazine in 1993. He is also the joint holder of the Outstanding Paper Award for a paper presented at the IEEE 14th International Symposium on Multiple-Valued Logic (ISMVL '84). He is the recipient of the IEEE Canada (Region 7) Outstanding Service Award (1995). He is a member of the PEO and the Canadian Association of University Teachers.