Reallocation of paths of ABR services in a multistage interconnection network (MIN)-type ATM switch network

In this paper, we develop algorithms for reallocating paths of available bit rate (ABR) services in an asynchronous transfer mode (ATM) switch network. ATM traffic control for fair share bandwidth allocation is usually performed under the assumption that paths of all services in a switch network are fixed. However, each connection may have multiple paths from an ingress queue to an egress queue since most ATM switch networks have the structure of the multistage interconnection network of switch elements. Therefore, paths already established for ABR connections may have to be changed to enhance throughput of the switch, if the ATM switch has the capability of adjusting paths of ABR connections while they are being served. We present three algorithms, in which throughput for ABR connections is estimated to decide whether or not paths of the connections should be changed. These algorithms are compared with an existing traffic management algorithm through simulation experiments. Results of the experiments show that the suggested algorithms give higher throughput in terms of the number of transmitted ABR cells without increasing the delay time of ABR services as well as quality of service (QoS) guaranteed services or decreasing the number of transmitted cells of QoS guaranteed services.     

ATM Routing Algorithms for Multimedia Traffic in Private ATM Networks

The goal of this paper is to recommend a good Private Network-to-Network Interface (PNNI) routing algorithm for private ATM networks. A good routing algorithm has to work well with multimedia traffic with several quality of service (QoS) requirements (such as cell loss ratio, cell delay and its variation etc.) in different networks under various traffic conditions. The multiplicity of QoS requirements makes the routing problem NP-complete, so our approach to the problem is based on large scale simulations involving several empirical algorithms (compliant with the PNNI routing specification) which have been tested for different network topologies and traffic scenarios. Based on analysis of tradeoffs involving performance metrics (such as blocking rate, complexity, load distribution) we recommend a consistently good routing algorithm for single domain ATM networks.     

Analysis of a multicast switch via the arrival modulation technique

Multicast switching is emerging as a new switching technology that can provide efficient transport in a broadband network for video and other multipoint communication services. In this paper, we analyze the call blocking probability in a multicast switch via thearrival modulation technique. Our study shows that multicast traffic encounters higher blocking probability than point-to-point traffic because of simultaneous output port contentions. To ensure adequate performance for multicast traffic, we develop and analyze a simple call scheduling algorithm calledFixed Splitting. The results show that the fixed splitting algorithm reduces the call blocking probability significantly when it is applied with appropriately selected splitting parameters.     

Simulation and Analysis of a New Mobility Model for Mobile Communication Networks

The traffic generation models, which describe how the clients use the network services, as well as the mobility models, which describe how clients move within the service area covered by the network, are essential tools for QoS analysis in these environments. In this paper we present the simulation of a new mobility model implemented for the analysis of QoS parameters of a mobile network, such as channel occupation time, handoff and new call blocking probabilities.     

基于QoS协同关联的改进Skyline制造服务组合优化方法

服务社会网络环境下,云制造服务通过与其他参与同一任务的服务共享与竞争物理设备、信息、知识等资源形成协同效应,对双方实际执行效果具有重要影响,导致出现QoS偏离现象,现有服务选择模型难以适应这一情景。根据服务协同网络特点,本文提出基于QoS协同关联的制造服务组合方法。运用QoS协同关联和协同系数表达资源共享、冲突对QoS的影响程度,构建了新的服务选择优化模型。基于创新Skyline服务对概念,改善了Skyline算法在QoS协同关联条件下的搜索效率和结果,通过智能汽车制造仿真实验,验证了本文模型和算法的有效性。     

Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

QoS-Guided Bandwidth Management in Differentiated Time Scales

This paper presents an integrated approach to QoS-guided network bandwidth allocation where each traffic flow requires a sufficient bandwidth allocation to support its mean traffic rate and to meet a delay requirement. Under the assumption that the peak rate of each traffic flow is decreasing with the time interval within which the rate is measured, we derive an analytical relationship between the delay bound and the bandwidth requirement for each individual flow. Then, based on a Gaussian aggregate traffic model, we show that two key controllable parameters, the coefficient of variation and the provision for variation for the aggregate traffic flow, determine all three fundamental QoS attributes (throughput, delay, and loss). We illustrate by examples that these results can be used to design admission policies. We demonstrate also quantitatively a remarkable QoS advantage of larger channel bandwidth in a statistical multiplexing environment. The analytical contributions are expected to be generally useful in QoS-guided bandwidth management in broadband networks.     

Designing Least-Cost Nonblocking Broadband Networks

Integrated network technologies, such as ATM, support multimedia applications with vastly different bandwidth needs, connection request rates, and holding patterns. Due to their high level of flexibility and communication rates approaching several gigabits per second, the classical network planning techniques, which rely heavily on statistical analysis, are less relevant to this new generation of networks. In this paper, we propose a new model for broadband networks and investigate the question of their optimal topology from a worst-case performance point of view. Our model is more flexible and realistic than others in the literature, and our worst-case bounds are among the first in this area. Our results include a proof of intractability for some simple versions of the network design problem and efficient approximation algorithms for designing nonblocking networks of provably small cost. More specifically, assuming some mild global traffic constraints, we show that a minimum-cost nonblockingstarnetwork achieves near-optimal cost; the cost ratio is at most 2 if switch source and sink capacities are symmetric and at most 3 when the total source and sink capacities are balanced. In the special case of unit link costs, we can show that a star network is indeed the cheapest nonblocking network.     

Optimal control in light traffic Markov decision processes

We consider Markov Decision Processes under light traffic conditions. We develop an algorithm to obtain asymptotically optimal policies for both the total discounted and the average cost criterion. This gives a general framework for several light traffic results in the literature. We illustrate the method by deriving the asymptotically optimal control of a simple ATM network.     

Optimizing the system of virtual paths by tabu search

In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

Symbolic models for infinite networks of control systems: A compositional approach

This paper presents a compositional framework for the construction of symbolic models for a network composed of a countably infinite number of finite-dimensional discrete-time control subsystems. We refer to such a network as infinite network. The proposed approach is based on the notion of alternating simulation functions. This notion relates a concrete network to its symbolic model with guaranteed mismatch bounds between their output behaviors. We propose a compositional approach to construct a symbolic model for an infinite network, together with an alternating simulation function, by composing symbolic models and alternating simulation functions constructed for subsystems. Assuming that each subsystem is incrementally input-to-state stable and under some small-gain type conditions, we present an algorithm for orderly constructing local symbolic models with properly designed quantization parameters. In this way, the proposed compositional approach can provide us a guideline for constructing an overall symbolic model with any desired approximation accuracy. A compositional controller synthesis scheme is also provided to enforce safety properties on the infinite network in a decentralized fashion. The effectiveness of our result is illustrated through a road traffic network consisting of infinitely many road cells.     

Many Sources Asymptotics for Networks with Small Buffers

In this paper, we obtain the overflow asymptotics in a network with small buffers when the resources are accessed by a large number of stationary independent sources. Under the assumption that the network is loop-free with respect to source–destination routes, we identify the precise large deviations rate functions for the buffer overflow at each node in terms of the external input characteristics. It is assumed that each type of source requires a Quality of Service (QoS) defined by bounds on the fraction of offered work lost. We then obtain the admissible region for sources which access the network based on these QoS requirements. When all the sources require the same QoS, we show that the admissible region asymptotically corresponds to that which is obtained by assuming that flows pass through each node unchanged.     

The output of a switch,or, effective bandwidths for networks

Consider a switch which queues traffic from many independent input flows. We show that in the large deviations limiting regime in which the number of inputs increases and the service rate and buffer size are increased in proportion, the statistical characteristics of a flow are essentially unchanged by passage through the switch. This significantly simplifies the analysis of networks of switches. It means that each traffic flow in a network can be assigned an effective bandwidth, independent of the other flows, and the behaviour of any switch in the network depends only on the effective bandwidths of the flows using it. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Remaining Service Time upon Reaching a Given Level in M/G/1 Queues

The ability of effectively finding the distribution of the remaining service time upon reaching a target level in M/G/1 queueing systems is of great practical importance. Among other things, it is necessary for the estimation of the Quality-of-Service (QoS) provided by Asynchronous Transfer Mode (ATM) networks. The previous papers on this subject did not give a comprehensive solution to the problem. In this paper an explicit formula for this distribution is given. This formula is general as it includes any initial level of the length of the queue, any type of service distribution (heavy tails) and any traffic intensity ρ. Moreover, it is easy to use and fast in computation. To show this several numerical examples are presented. In addition, a solution of the similar problem in G/M/1 queues (which is the distribution of the remaining interarrival time) is given.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

An algorithm for optimal minimax routing in ATM networks

Asynchronous Transfer Mode (ATM) has been adopted by the CCITT as the transport mode in which Broadband ISDN will be based. In this paper, we formulate the problem of routing cells in an ATM network as an optimization problem. The objective is to minimize the largest cell loss probability among all links. The constraints correspond to a multicommodity network flow problem with gains. An algorithm to determine a global optimal flow assignment is presented. The minimax routing algorithm was implemented and tested on several sample networks. The computational experiments show that the algorithm is computationally efficient.Supported by NSF grant NCR 92-23148.     

Robust connection acceptance control for ATM networks with incomplete source information

Consider an ATM resource where the statistics of each bursty traffic source are not precisely known. How should the resource decide when to accept fresh connections? We address this problem for the case where each source behaves as a simple “On-Off” model and only the peak bandwidth is known. A connection acceptance control algorithm is proposed that relies on the choice of a boundary. The performance of this algorithm is analysed using an approximation based on separation of timescales. The slowly changing call process behaves like the queue process at an infinite server queue, where the arrival process to the queue is dictated by the fast moving burst process. A technique for finding a suitable boundary is also given, based on the Bayesian principle. The algorithm, together with the proposed boundary, could be used in a network to control connection acceptance at each resource along a virtual path.     

Impact of source load and routing on QoS of packets delivery

We study how the number of packets in transit (NPT), that is an aggregate measure of a network quality of service (QoS) performance, is affected by routing algorithm coupled with volume of incoming traffic. We use our simulation model that is an abstraction of the Network Layer of the OSI Reference Model. We consider a static routing and two different types of dynamic routings and different volumes of incoming traffic in the network free flow state. Our study shows that the efficiency of performance of a routing changes with the volume of incoming traffic among the considered routings.