Performance evaluation of dynamic routing based on the use of satellites and intelligent networks

A dynamic routing scheme for public switched telephone networks is introduced which employs satellite broadcast to distribute network load data. The proposed network architecture closely resembles the IN (Intelligent Network) architecture, whereby the IN SCPs (Service Control Points) serve as so‐called Routing Control Points (RCPs). The key functions of an RCP are (i) to execute the routing algorithm and issue routing instructions in response to routing queries it receives from its associated switches for calls which overflow from the default network links, and (ii) to monitor and evaluate the pattern of received routing queries to obtain an estimate for the traffic loads present in each RCP's domain of associated switches. Satellite broadcast is used to distribute the load information among all RCPs in the network in a periodic fashion. This paper also reports on the results of extensive call‐by‐call simulations. The objective of the simulations was to validate this new routing scheme and compare its performance with well‐known existing schemes. Real traffic and network data as measured in the Austrian PSTN were used in the simulations. The main results are that, under all realistic network and traffic conditions including link and node failures, the proposed scheme yields lower blocking rates and significantly less routing and crankback attempts than the existing dynamic routing schemes. Note that this is achieved in the absence of any load measurements within the switches. As regards the periodic satellite based RCP‐RCP broadcast for the PSTN studied, it was shown that an update period of 10 seconds yields an excellent routing performance which is close to the limit of a vanishing update period. This revised version was published online in June 2006 with corrections to the Cover Date.     

Tabu search for dynamic routing communications network design

This paper presents a tabu search approach for optimizing the link capacities in a dynamic routing telecommunications network. The traffic between any two nodes in the network is routed over a one‐link direct path or, if no direct capacity is available, over a two‐link alternate path. The alternate routing paths can be changed dynamically from hour to hour as the traffic between pairs of nodes may vary with the time of day. The problem is to determine the optimal capacity level for each link in the network to minimize cost while satisfying the grade‐of‐service constraints. Although the problem can be formulated as a nonlinear integer programming problem, no efficient solution procedures are available. In this paper, we develop a two‐level tabu search heuristic for solving the problem that utilizes probabilistic move selection and coordinated solution recovery strategies. The macro level of the algorithm iteratively determines an hour for possible improvement and then the micro level seeks to optimize the routing paths for that hour. Our computational experience with both real and simulated problems indicates that significant savings can be obtained by this approach over the conventional network designs. This revised version was published online in June 2006 with corrections to the Cover Date.     

Modified least loaded routing in virtual path based ATM networks

We consider a Virtual Path (VP) based ATM network supporting multiple traffic classes with heterogeneous traffic characteristics. Using simple FIFO scheduling policy at the ATM multiplexer, we assume that all traffic require identical end‐to‐end quality of service (QoS) requirement. The concept of effective bandwidth is used to determine the required bandwidth to guarantee the specified QoS requirement. We study the problem of using dynamic routing to VP‐based ATM networks by transforming it into an equivalent multi‐rate circuit‐switched network problem. To further simplify the analysis, we restrict the choice of path to single‐link and two‐link routes. We propose a dynamic routing algorithm based on the Least Loaded Routing (LLR) with packing. Simulation results are used to compare the performance of this algorithm with other dynamic routing schemes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Network architecture and traffic transport for integrated wireless communications over enterprise networks

A novel network architecture based on the IEEE 802.6 metropolitan area networks (MAN) is proposed to integrate the wireless and wired segments of a regional enterprise network (REN) within a city. This architecture functions like a distributed switch for all types of services, reducing traffic congestion by sharing the high capacity link dynamically and facilitating signaling, mobility management, call processing and network management through its distributed functions, transport facilities and broadcasting capability. It also serves as a peripheral gathering network of REN traffic for transport over a wide area ATM/BISDN, enabling integration of an enterprise's regional networks into a global EN. Two major wireless applications, i.e., wireless PABX (WPABX) and wireless LAN (WLAN) are discussed to illustrate the advantages of this MAN‐based architecture. Although a REN is likely to support a wide range of different services, voice and data will continue to be the predominant traffic generated by WPABXs and WLANs, respectively, and are also representative of isochronous and asynchronous multimedia traffic carried by future wireless networks. We compare the traffic capacity of several voice transport alternatives under integrated (voice/data) network traffic with various data traffic loads, and study voice and data integration under three different integration schemes by simulations. Results indicate that the MAN‐based architecture is most effective employing queue arbitrated (QA) access for asynchronous traffic, pre‐arbitrated access for constant bit‐rate isochronous traffic, and the new reservation arbitrated (RA) access for variable bit‐rate isochronous traffic, under a scheme that permits full sharing between QA and RA traffic. This revised version was published online in July 2006 with corrections to the Cover Date.     

LMDS/LMCS hub interconnection alternatives and multiple access issues

LMDS/LMCS is a broadband wireless local loop, millimeter‐wave alternative to emerging integrated multiservice access networks. Significantly large amounts of bandwidth – in the order of one GHz of spectrum – are made available to residential subscribers or supported business users respectively that employ highly directional antennas and signal polarization to establish communication with a central hub. Besides the requirement for dynamic bandwidth allocation capabilities, these networks should be able to guarantee negotiated quality of service (QoS) levels to a number of constant‐length (ATM) – and possibly variable length (TCP/IP) – packet streams. In this context, we analyze the performance of contention, polling/probing and piggybacking mechanisms that will be used by the LMDS MAC protocol for the dynamic support of both real‐time and non‐real‐time traffic streams. More specifically, we focus on the end‐to‐end performance of a real‐time variable bit rate connection for which the LMDS link is only the access component of a multi‐link path through an ATM network. Results are presented on maximum end‐to‐end cell delays under a Weighted Round Robin service discipline and buffer requirements are calculated for no‐loss conditions. In parallel, we also consider the case in which variable length IP packet traffic is supported as such by the same wireless access network. Backbone interconnection alternatives of LMDS hubs, multiple access proposals and scheduling algorithms are addressed in this framework. This revised version was published online in July 2006 with corrections to the Cover Date.     

Performance analysis of session oriented data communications for mobile computing in cellular systems

Future cellular communication systems must seamlessly support services for a wide range of user needs, including voice, data, video and multi‐media. It is envisioned that mobile users may do much computer processing in an off‐line mode but must occasionally connect to a network in order to exchange data and/or files. For this purpose a communication session is initiated. During the session the user has access to network resources, although this access may be shared with others. Owing to the mobile environment, the user's connection to the network during a session may be severed. Since the mobile user can act semi‐autonomously, such disconnections can be transparent. That is, the mobile user can continue to function in an off‐line mode while the system will begin transparent automatic reconnection attempts to reestablish a link to the network. Only after a fixed (given) number of such attempts to reconnect have failed, is the session deemed to have failed. The issue is complicated by the hostile mobile radio environment and by user mobility. We consider session‐oriented communications and develop a tractable analytical model for traffic performance based on multi‐dimensional birth–death processes. The approach allows consideration of various platform types, such as pedestrians, automobiles, and buses, which may have very different mobility characteristics. Performance characteristics, such as: blocking, forced session termination, carried traffic, the average time per suspension, and the average number of suspensions per session, are calculated. This revised version was published online in July 2006 with corrections to the Cover Date.     

Design and analysis of an algorithm for fair service in error‐prone wireless channels

In order to support diverse communication‐intensive real‐time and non‐real‐time data flows over a scarce, varying and shared wireless channel with location‐dependent and bursty errors, we define a service model that has the following characteristics: short‐term fairness among flows which perceive a clean channel, long‐term fairness for flows with bounded channel error, worst‐case delay bounds for packets, short‐term throughput bounds for flows with clean channels and long‐term throughput bounds for all flows with bounded channel error, expanded schedulable region, and support for both delay sensitive and error sensitive data flows. We present the wireless fair service algorithm, and show through both analysis and simulation that it achieves the requirements of the service model in typical wireless network environments. The key aspects of the algorithm are the following: (a) an enhanced fair queueing based service scheme that supports decoupling of delay and bandwidth, (b) graceful service compensation for lagging flows and graceful service degradation for leading flows, (c) support for real‐time delay sensitive flows as well as non‐real‐time error sensitive flows, and (d) an implementation within the framework of the simple and robust CSMA/CA wireless medium access protocol. This revised version was published online in July 2006 with corrections to the Cover Date.     

A call admission and control scheme for quality‐of‐service (QoS) provisioning in next generation wireless networks

We propose a framework for quality‐of‐service (QoS) provisioning for multimedia services in next generation wireless access networks. This framework aims at providing a differentiated treatment to multimedia traffic flows at the link layer, which can be broadly classified as real‐time (or delay‐sensitive) and non‐real‐time (or delay‐tolerant). Various novel schemes are proposed to support the differential treatment and guarantee QoS. These schemes include bandwidth compaction, channel reservation and degradation, with the help of which a call admission and control algorithm is developed. The performance of the proposed framework is captured through analytical modeling and simulation experiments. Analytically, the average carried traffic and the worst case buffer requirements for real‐time and non‐real‐time calls are estimated. Simulation results show up to 21% improvement in the admission probability of real‐time calls and up to 17% improvement in the admission probability of non‐real‐time calls, when various call control techniques like bandwidth compaction are employed. Using our channel reservation technique, we observe a 12% improvement in the call admission probability compared to another scheme proposed in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

An application‐ and management‐based approach to ATM scheduling

Two frame‐based ATM scheduling strategies, Delayed Frame Queueing (DFQ) and Virtual Frame Queueing (VFQ), are described for real‐time network applications. Both strategies guarantee explicit upper bounds on delay and jitter on a per virtual connection (VC) basis without relying on per‐VC queueing. They also resolve the disadvantages often associated with other frame‐based schedulers. The DFQ scheduler employs Resource Management cells to enable work‐conserving forwarding at intermediate nodes while retaining the option for non‐work‐conserving forwarding at terminal nodes. This allows delay bounds to be uncoupled from jitter bounds. The VFQ scheduler requires no such overhead cell transmissions, but is more limited in its ability to uncouple these two types of bounds. ATM network simulation results indicate that both proposed disciplines offer favorable multiplexing performance in comparison to a well documented high performance service discipline. Finally, we contrast our proposal against the significant difficulties that alternative scheduling strategies based on bandwidth guarantees will face with regard to network management and network synthesis issues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Communication capabilities of product networks

Instead of providing separate solutions for each individual network, a unified theory is desirable to cover the study of a class of networks. Cartesian product graphs provide a common framework to investigate the performance of several individual networks. This paper addresses communication capabilities of product networks. Communication cost is generally characterized by the diameter, the average distance, the total number of paths, the traffic intensity, the saturation level, the queue length in each node, the communication delay and the network throughput. The diameter and average distance of product networks have been studied. However, no work has addressed the remaining measures for product networks. This paper presents a unified theory to evaluate the traffic intensity and the saturation level of product networks. We have theoretically computed the traffic intensity and the saturation level. Intensive simulations have been conducted to validate the analytical results and to compute the other measures for different workloads, different networks, and different network sizes. Examples of product networks that have been investigated are multidimensional meshes, multidimensional toruses, and r‐ary n‐cube networks. We have also shown that the structure (geometry) of a network is a primary factor for network high performance. For meshes and toruses, square networks present an optimal structure. While in case of an r‐ary n‐cubes, networks with higher radix outperform those with smaller radix. In particular, cross‐cubes (4‐ary n‐cube) are shown to perform better than binary cubes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Design and analysis of low‐power access protocols for wireless and mobile ATM networks

This paper describes the design and analysis of a low‐power medium access control (MAC) protocol for wireless/mobile ATM networks. The protocol – denoted EC‐MAC (energy conserving medium access control) – is designed to support different traffic types with quality‐of‐service (QoS) provisions. The network is based on the infrastructure model where a base station (BS) serves all the mobiles currently in its cell. A reservation‐based approach is proposed, with appropriate scheduling of the requests from the mobiles. This strategy is utilized to accomplish the dual goals of reduced energy consumption and quality of service provision over wireless links. A priority round robin with dynamic reservation update and error compensation scheduling algorithm is used to schedule the transmission requests of the mobiles. Discrete‐event simulation has been used to study the performance of the protocol. A comparison of energy consumption of the EC‐MAC to a number of other protocols is provided. This comparison indicates the EC‐MAC has, in general, better energy consumption characteristics. Performance analysis of the proposed protocol with respect to different quality‐of‐service parameters using video, audio and data traffic models is provided. This revised version was published online in August 2006 with corrections to the Cover Date.     

Mobile multicasting in wireless ATM networks

Multicasting is a desired function in both wired and wireless networks. Currently, multicasting‐based applications have pervasive presence and influence in our Internet. Wireless ATM aims to support different traffic types over a high speed wireless network. In particular, traditional approaches towards multicasting in wired networks cannot be directly applied to mobile ATM networks. This includes the mechanism proposed to handle mobility in wired networks. In this paper, we address the issues behind multicasting in wireless ATM networks and the underlying mechanisms to support handoffs of both unicast and multicast connections. Through simulation, we evaluated the performance of optimal core‐based tree (CBT), late‐joined CBT, optimal source‐based tree (SBT), and late‐joined SBT during changing multicast host membership conditions. In addition, we evaluated the impact of multicast receivers' migration on the total link cost of the resultant multicast tree. Simulation results revealed that source‐based trees incur more total link costs under both dynamic host membership and receivers' migration scenarios. However, it generates less control messages than the distributed CBT and SBT approaches. This revised version was published online in June 2006 with corrections to the Cover Date.     

Design and evaluation of multicast GFR for supporting TCP/IP over hybrid wired/wireless ATM

The major challenges of designing multicast traffic control protocols for a combined wired/wireless network are the varying transmission characteristics (bandwidth, error, and propagation delay) of the wireless and wired media, and the different, possibly conflicting frame rate requests from multiple sources. To address these issues, in this paper we design and evaluate new unicast and multicast guaranteed frame rate (GFR) schemes for supporting TCP/IP traffic over a combined wired/wireless ATM network. We first propose a new, flexible weighted buffer management, and a frame‐based virtual spacing (VS) mechanism implementing weighted fair queueing. The unicast GFR scheme is based on the integration of the new weighted buffer management, and either cell‐based or frame‐based VS. It is then extended to support multicast GFR flows. The multicast scheme presented in this paper is the first multicast GFR scheme appeared in the literature. These schemes are carefully evaluated over several network configuration, supporting heterogeneous TCP/IP traffic with various frame rates. Simulation results show that the new schemes guarantee the minimum rates requested, provide excellent fairness, and achieve reasonably high efficiency. The new schemes may be extended to provide differentiated service in both IP and mobile IP frame work. This revised version was published online in July 2006 with corrections to the Cover Date.     

A simulation tool to validate and compare satellite TDMA access schemes

This paper proposes an architecture design for a tool suitable for emulating DA‐TDMA (demand‐assignment‐time division multiple access) satellite access schemes. The tool presented, named FRACAS, is particularly suitable for comparing the performance of different satellite channel allocation policies. Using FRACAS, a service provider can choose from different policies for sharing a satellite channel among a number of users. Some allocation policies, selected from those available in the literature, are built‐in, while others can be designed from scratch and added without much effort. The parameters of the built‐in allocation policies can easily be changed in order to exploit the full potential of the allocation schemes. FRACAS's features permit the optimisation of satellite resource usage in accordance with the traffic pattern supported. FRACAS enables research teams and students to explore and compare different multiple access schemes, and to develop simulation runs for various kinds of service‐induced traffic, including aggregate traffic, which is typical in a local area network (LAN) interconnection environment. This revised version was published online in June 2006 with corrections to the Cover Date.     

A modified offered load approximation for nonstationary circuit switched networks

In this paper, we develop approximation methods to analyze blocking in circuit switched networks with nonstationary call arrival traffic. We formulate generalizations of the pointwise stationary and modified offered load approximations used for the nonstationary Erlang loss model or M(t)/M/c/c queue. These approximations reduce the analysis of nonstationary circuit switched networks to solving a small set of simple differential equations and using the methods for computing the steady state distributions for the stationary versions of such loss networks. We also discuss how the use of time varying arrival rates literally adds a new dimension to the class of telecommunication networks we can model. For example, we can model the behavior of alternate routing due to link‐failure, which is a feature that the classical stationary version of the model cannot capture. Our nonstationary model can also describe aspects of the dynamic calling traffic behavior arising in cellular mobile traffic. For the special case of a two‐link, three node network, we present numerical results to compare the various approximation methods to calculations of the exact blocking probabilities. We also adapt these calculations to approximate the behavior of rerouting calling traffic due to link‐failure. The results are achieved by formulating some new recursions for evaluating the steady state blocking probabilities of such networks. We also generalize these techniques to develop analogous formulas for a linear N‐node circuit switched network. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fluid analysis of a TCP connection over ABR

This paper reports on an analytical study of the performances of the ATM‐ABR service category in transporting TCP/IP flows over an ATM network. We explore the behavior of a TCP connection over an ATM‐ABR VC, in presence of exogenous non‐controlled traffic. This fluid analysis of the system allows the study of the interaction between the window‐based end‐to‐end flow control TCP protocol and the rate‐based flow control ABR mechanism, which is restricted to the ATM part of the network. The main aim of this study is to give performance evaluation formulae to model the behavior of such a TCP over ABR connection. This revised version was published online in June 2006 with corrections to the Cover Date.     

Engineering ATM networks for congestion avoidance

With the combination of telecommunication, entertainment and computer industries, computer networking is adopting a new method called Asynchronous Transfer Mode (ATM) networking. Congestion control plays an important role in the effective and stable operation of ATM networks. Traffic management concerns with the design of a set of mechanisms which ensure that the network bandwidth, buffer and computational resources are efficiently utilized while meeting the various Quality of Service (QoS) guarantees given to sources as part of a traffic contract. In this paper, the most widely recognized congestion control schemes for ABR service are investigated. Some of these schemes show either lack of scalability or fairness while other well‐behaved schemes may require a highly complex switch algorithm that is unsuitable for implementation in cell‐switching high‐speed ATM networks. A new and improved congestion control scheme is proposed to support the best‐effort ABR traffic. This algorithm provides the congestion avoidance ability with high throughput and low delay, in addition to achieving the max–min fairness allocation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A measurement‐based performance evaluation method for IP networks and its implementation

In recent years, IP networks have become increasingly complex and the range of network applications has widened. As a result, the need for experimental evaluation of application performance has increased. We introduce a measurement‐based performance evaluation method that combines a function to generate various patterns of application traffic with one to measure end‐to‐end network performance at the application level. For our method, we also propose traffic models of various applications that can represent the characteristics of these applications, for example, the burstiness of traffic. This method has already been implemented as a benchmarking tool on UNIX operating systems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Cell‐level/call‐level ATM switch simulator

A B‐ISDN national project in Korea has been carried out to develop a National Information Superhighway since 1992. An ATM switching system has been developed as one of the most important parts in the project, and has been tested in the National Information Superhighway testbed. In this paper, we develop a cell‐level/call‐level ATM switch simulator using cell‐level and call‐level input traffic models for evaluating the ATM switching system. The cell‐level simulator models various cell‐level switching functions such as priority control and multicast, and evaluates the cell‐level performance indices of the ATM switch in terms of cell delay, throughput, and cell loss probability. On the other hand, the call‐level simulator uses call‐level traffic models and evaluates the call blocking rate as a call‐level quality of service (QoS). This revised version was published online in August 2006 with corrections to the Cover Date.     

Spread‐spectrum CDMA packet radio MAC protocol using channel overload detection and blocking

An analytical and simulation performance evaluation is presented for a multi‐access protocol for a data packet radio network with a limited user capacity. The network employs direct‐sequence code division multiple access (DS‐CDMA) in a centralised channel load‐sensing scheme with channel overload (collision) detection and blocking via a separate ancillary channel state information broadcast system. Traffic models that incorporate both a finite population and an infinite population and variable length data messages are considered. Results show that an improved throughput/delay performance can be obtained by implementing a channel overload detection (message dropping) scheme as well as a channel overload avoidance (message blocking) scheme. The channel overload threshold β is fixed at the system's maximum user capacity whereas it is shown that the overload avoidance blocking threshold α should be variable and dependent on the mean message arrival rate. This revised version was published online in July 2006 with corrections to the Cover Date.