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.     

Evaluating the impact of stale link state on quality-of-servicerouting

Quality-of-service (QoS) routing satisfies application performance requirements and optimizes network resource usage by selecting paths based on connection traffic parameters and link load information. However, distributing link state imposes significant bandwidth and processing overhead on the network. This paper investigates the performance tradeoff between protocol overhead and the quality of the routing decisions in the context of the source-directed link state routing protocols proposed for IP and ATM networks. We construct a detailed model of QoS routing that parameterizes the path-selection algorithm, link-cost function, and link state update policy. Through extensive simulation experiments with several network topologies and traffic patterns, we uncover the effects of stale link state information and random fluctuations in traffic load on the routing and setup overheads. We then investigate how inaccuracy of link state information interacts with the size and connectivity of the underlying topology. Finally, we show that tuning the coarseness of the link-cost metric to the inaccuracy of underlying link state information reduces the computational complexity of the path-selection algorithm without significantly degrading performance. This work confirms and extends earlier studies, and offers new insights for designing efficient quality-of-service routing policies in large networks     

Towards real‐time optimal VP management for ATM nets

We propose a mathematical model for VP configuration to find an optimal logical network topology of a given ATM‐based B‐ISDN. The model is essentially identical to the model proposed earlier by Kim [13] which finds a virtual path configuration in which an optimal trade‐off is achieved among the relevant gains of ATM technology. Unlike Kim’s model, however, our model explicitly considers the VP’s QoS to enhance the practicality and the bandwidth utilization. A difficulty is to find an efficient solution technique as it involves a large‐scale intractable optimization problem. We propose a heuristic algorithm tailored to the computational structure of the model. A computational experiment shows that the algorithm finds good solutions in dramatically reduced computation time compared to the existing algorithm. This suggests the possibility of a real‐time VP management system in which the optimal VP configuration is implemented on‐line with a dynamic routing (e.g., LLR), to maintain the optimality of the current solutions. This revised version was published online in August 2006 with corrections to the Cover Date.     

Dynamic bandwidth allocation scheme for multiple real‐time VBR videos over ATM networks

This paper considers VBR transmission of multiple real‐time videos over ATM networks. Multiple real‐time VBR video sources are multiplexed into an ATM switch to transmit cells into the network. Given the ATM switch capacity, the problem is to dynamically allocate the required channel bandwidth for each video source such that the encoder buffer occupancy is maintained at a target level. To solve the problem, we present a mathematical formulation and propose an algorithm for the bandwidth allocation. To allocate a suitable bandwidth at a given control period, QoS demand levels and traffic characteristics of the video sources are considered. The performance of the proposed scheme is examined in terms of the number of encoder rate controls required and the gap between the target and the current buffer occupancy at each control period. Numerical results are analyzed for different QoS environments as well as different levels of target buffer, ATM switch capacity, buffer size and leaky bucket token rate. 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.     

QoS routing in ad hoc wireless networks

The emergence of nomadic applications have generated much interest in wireless network infrastructures that support real-time communications. We propose a bandwidth routing protocol for quality-of-service (QoS) support in a multihop mobile network. The QoS routing feature is important for a mobile network to interconnect wired networks with QoS support (e.g., ATM, Internet, etc.). The QoS routing protocol can also work in a stand-alone multihop mobile network for real-time applications. This QoS routing protocol contains end-to-end bandwidth calculation and bandwidth allocation. Under such a routing protocol, the source (or the ATM gateway) is informed of the bandwidth and QoS available to any destination in the mobile network. This knowledge enables the establishment of QoS connections within the mobile network and the efficient support of real-time applications. In addition, it enables more efficient call admission control. In the case of ATM interconnection, the bandwidth information can be used to carry out intelligent handoff between ATM gateways and/or to extend the ATM virtual circuit (VC) service to the mobile network with possible renegotiation of QoS parameters at the gateway. We examine the system performance in various QoS traffic flows and mobility environments via simulation. Simulation results suggest distinct performance advantages of our protocol that calculates the bandwidth information. It is particularly useful in call admission control. Furthermore, “standby” routing enhances the performance in the mobile environment. Simulation experiments show this improvement     

Modelling and analysis of routing and resource allocation techniques in multi‐service networks

In this paper a novel call level model based on the extension of the classical Erlang multi‐rate model for broadband integrated services networks is proposed. We use the model to study routing strategies in multi‐service networks where service classes with/without QoS guarantees coexist. Examples for such networks include ATM and IP‐based integrated networks. In ATM, the CBR and VBR service classes provide QoS guarantees, while the ABR and UBR service classes are of the best effort type. In IP, traditional TCP/IP traffic is of the best effort type, while new protocols like the RSVP or the differentiated services with central resource handling attempt to support QoS parameters. The coexistence of guaranteed and best effort traffic gives rise to new challenging problems since for a given elastic (best effort) connection the bottleneck link determines the available bandwidth and thereby puts constraints on the bandwidth at the other links along the connection's path. Since the available bandwidth fluctuates in time following the load on the links, routing and link allocation in this environment together with blocking probability calculations and fairness issues need to be studied. By means of our proposed model we are able to conduct a survey of various routing and link allocation techniques as well as to develop a modified shortest path routing algorithm which, according to the numerical examples, performs well in this environment. Copyright © 1999 John Wiley & Sons, Ltd.     

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.     

Design of ATM Networks with Multiple Traffic Classes

In this paper, we propose a new heuristic design algorithm for the virtual path (VP)-based ATM network with multiple traffic classes, in which QoS constraints associated with traffic class are taken into account. The minimum bandwidth of VP required to carry given amount of traffic is obtained by utilizing an equivalent bandwidth concept, and the route of each VP is placed so that the network cost is minimized while the QoS requirement is fulfilled. To evaluate our design algorithm, we consider two kinds of traffic: voice traffic as low speed service and still picture traffic as high speed service. Through numerical examples, we demonstrate that our design method can achieve an efficient use of network resources, which results in providing a cost-effective VP-based ATM network.     

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 fast numerical algorithm for multi‐rate network synthesis

We consider here the problem of the optimal network design either for multi‐rate circuit switching or VC switching in an ATM network through the use of effective bandwidth models. We put the emphasis on the development of a fast and stable numerical algorithm for computing solutions of networks of up to 50 nodes. We show that the main difficulty is in the calculation of the gradient of the objective function in the presence of the Erlang fixed point system. We then propose an approximation for this calculation based on the power series of the inverse of a matrix. Next, we review explicit representation techniques for the matrices involved in this calculation and show that reductions in CPU time of factors as large as 20 can be obtained with practically no penalty in terms of memory requirement. We also show that the dimensioning problem is ill‐conditioned and that a simple scaling of the dimensioning variables is sufficient to speed up the convergence. As a final point, we use the algorithm to examine some features of the problem. We show that the objective function has no definite convexity property, that alternate routing is used mostly by wideband calls and that the grade of service constraints are generally binding only for these wideband calls. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multi-hour, multi-traffic class network design for virtualpath-based dynamically reconfigurable wide-area ATM networks

The virtual path (VP) concept has been gaining attention in terms of effective deployment of asynchronous transfer mode (ATM) networks in recent years. In a recent paper, we outlined a framework and models for network design and management of dynamically reconfigurable ATM networks based on the virtual path concept from a network planning and management perspective. Our approach has been based on statistical multiplexing of traffic within a traffic class by using a virtual path for the class and deterministic multiplexing of different virtual paths, and on providing dynamic bandwidth and reconfigurability through virtual path concept depending on traffic load during the course of the day. In this paper, we discuss in detail, a multi-hour, multi-traffic class network (capacity) design model for providing specified quality-of-service in such dynamically reconfigurable networks. This is done based on the observation that statistical multiplexing of virtual circuits for a traffic class in a virtual path, and the deterministic multiplexing of different virtual paths leads to decoupling of the network dimensioning problem into the bandwidth estimation problem and the combined virtual path routing and capacity design problem. We discuss how bandwidth estimation can be done, then how the design problem can be solved by a decomposition algorithm by looking at the dual problem and using subgradient optimization. We provide computational results for realistic network traffic data to show the effectiveness of our approach. We show for the test problems considered, our approach does between 6% to 20% better than a local shortest-path heuristic. We also show that considering network dynamism through variation of traffic during the course of a day by doing dynamic bandwidth and virtual path reconfiguration can save between 10% and 14% in network design costs compared to a static network based on maximum busy hour traffic     

LEO multi-service routing algorithm based on multi-objective decision making

In low earth orbit(LEO) satellite networks,in view of the unbalanced link resource,it's difficult to meet differentiated quality of service(QoS) requirements and easily lead to reduce the efficiency of the whole network.A routing algorithm based on multi-objective decision making was proposed which defined LEO satellite network transmission service as the delay sensitive,sensitive bandwidth and reliability sensitive three categories.It used the eigenvector method to calculate service weights,and used the consistency ratio to determine whether it can be accepted.Based on the multi-objective decision making theory,it combined with the actual state of satellite network nodes and links and the specific requirements of the business,calculating the path that meets the QoS requirements of the service,so as to realize the LEO satellite network multi objective dynamic routing optimization.Established simulation platform based on the iridium network system simulated network delay,the uncertain characteristics like the residual bandwidth and packet error rate,route planning for the randomly generated three classes of business.The simulation results show that,the algorithm not only satisfies the QoS constrain while balancing the traffic load of the satellite link effectively,but also improves the performance on the throughput.     

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.     

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 architecture of ATM‐based PCS network: Signaling traffic and capacity

In this paper, we propose an ATM‐based Personal Communication Service (PCS) network architecture with ring‐based access networks. We also propose a simple ring management scheme using ATM Add‐Drop‐Multiplexers (ADM). The ring has a Virtual Star topology, and we manage its bandwidth at two levels: Virtual Path (VP) level and Virtual Channel (VC) level. We consider four different types of configurations according to the locations of visitor location register (VLR) and mobile switching center (MSC) functions, and obtain signaling load and processing load. A 150 Mb/s‐dual ring can support about 5,500 homogeneous ON–OFF voice sources. This ring capacity corresponds to covering approximately 180 cells in the case of 30 connections per cell. Even though we are here concerned with evaluating the proposed network for voice traffic, we can extend this study to the analysis of the proposed ATM‐based PCS network accommodating various types of multimedia traffic as a further study. This revised version was published online in August 2006 with corrections to the Cover Date.     

Local and congestion-driven fairness algorithm in arbitrarytopology networks

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm: i) locality and congestion-driven-only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by “the maximal clique in what we call the conflict graph to which a node belongs,” and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes)     

Multiple access control with intelligent bandwidth allocation forwireless ATM networks

Two major challenges pertaining to wireless asynchronous transfer mode (ATM) networks are the design of multiple access control (MAC), and dynamic bandwidth allocation. While the former draws more attention, the latter has been considered nontrivial and remains mostly unresolved. We propose a new intelligent multiple access control system (IMACS) which includes a versatile MAC scheme augmented with dynamic bandwidth allocation, for wireless ATM networks. IMACS supports four types of traffic-CBR, VBR, ABR, and signaling control (SCR). It aims to efficiently satisfy their diverse quality-of-service (QoS) requirements while retaining maximal network throughput. IMACS is composed of three components: multiple access controller (MACER), traffic estimator/predictor (TEP), and intelligent bandwidth allocator (IBA). MACER employs a hybrid-mode TDMA scheme, in which its contention access is based on a new dynamic-tree-splitting (DTS) collision resolution algorithm parameterized by an optimal splitting depth (SD). TEP performs periodic estimation and on-line prediction of ABR self-similar traffic characteristics based on wavelet analysis and a neural-fuzzy technique. IBA is responsible for static bandwidth allocation for CBR/VBR traffic following a closed-form formula. In cooperation with TEP, IBA governs dynamic bandwidth allocation for ABR/SCR traffic through determining the optimal SD. The optimal SDs under various traffic conditions are postulated via experimental results, and then off-line constructed using a back propagation neural network (BPNN), being used on-line by IBA. Consequently, with dynamic bandwidth allocation, IMACS offers various QoS guarantees and maximizes network throughput irrelevant to traffic variation     

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.     

一种新型IP数据链网络路由算法模型

针对无线数据链网络,提出了一种新型的基于分层结构的IP路由算法模型,满足至少3种异构数据链网络的集成要求.仿真结果表明,该模型可有效支撑基于链路带宽、传输时延、链路质量等多种QoS的路由算法设计,为无线数据链网络层IP路由协议和算法设计提供了理论框架和实现指导.