Layouts for mobility management in wireless ATM networks

In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.     

竞争情形下服务商质量保证策略研究

质量保证策略是服务商获取竞争力的重要手段之一。本文在考虑服务商及其竞争对手的质量承诺水平和质量承诺补偿对其服务需求影响的基础上,构建了质量承诺水平、质量承诺补偿、质量承诺水平和质量承诺补偿三种竞争情形下的博弈模型,并系统分析了不同模型下的质量保证策略。研究发现:一旦有服务商提高质量承诺水平或质量承诺补偿,在质量承诺水平竞争模型下,其他服务商可适当地降低质量承诺水平,而在质量承诺补偿竞争模型下,其他服务商会同时提高质量承诺补偿。此外,在质量承诺水平和质量承诺补偿竞争模型下,若质量承诺水平的成本系数满足一定条件,各个服务商之间会存在纳什均衡。本文对服务市场竞争情形下服务商质量保证策略的制定具有一定的实践意义。     

A stochastic fluid model for an ad hoc mobile network

In conventional mobile telephone networks, users communicate directly with a base station, via which their call is transferred to the recipient. In an ad hoc mobile network, there is no base-station infrastructure and users need to communicate between themselves, either directly if they are close enough, or via transit nodes if they are not. A number of interesting questions immediately arise in the modeling of ad hoc mobile networks. One that has received attention in the literature concerns how to encourage users to act as transit nodes for calls that they are not partaking in. Solutions to this problem have involved each user maintaining a ‘credit balance’ which is increased by forwarding transit calls and decreased by transmitting one’s own calls. A second question concerns the ‘amount of resource’ that a network needs in order to be able to operate with a reasonable quality of service. We shall consider this question by modeling each user’s battery energy and credit balance as fluids, the rate of increase or decrease of which is modulated by the network occupancy. This results in a network of stochastic fluid models, each modulated by the same background process. In this paper, we shall assume that there is no bound on the energy or the credit that a user’s handset can accumulate. Using this model, we can calculate the critical rates of recharge that are necessary and sufficient to guarantee that no calls are lost. For recharge rates less than the critical values, we propose a reduced-load approach to the analysis of the network.     

Dynamic power control in a fading downlink channel subject to an energy constraint

A central controller chooses a state-dependent transmission rate for each user in a fading, downlink channel by varying transmission power over time. For each user, the state of the channel evolves over time according to an exogenous continuous-time Markov chain (CTMC), which affects the quality of transmission. The traffic for each user, arriving at the central controller, is modeled as a finite-buffer Markovian queue with adjustable service rates. That is, for each user data packets arrive to the central controller according to a Poisson process and packet size is exponentially distributed; an arriving packet is dropped if the associated buffer is full, which results in degradation of quality of service. The controller forwards (downlink) the arriving packets to the corresponding user according to an optimally chosen transmission rate from a fixed set A _i of available values for each user i, depending on the backlog in the system and the channel state of all users. The objective is to maximize quality of service subject to an upper bound on the long-run average power consumption. We show that the optimal transmission rate for each user is solely a function of his own packet queue length and channel state; the dependence among users is captured through a penalty rate. Further, we explicitly characterize the optimal transmission rate for each user. This project is partially supported by Motorola grant # 0970-350-AF24. The authors thank Phil Fleming,Randy Berry and Achal Bassamboo for helpful comments.     

Performance analysis of virtual circuit connections for bursty data sources in ATM networks

ATM is a packet-like transmission mode that has been proposed for BISDN. It is characterized by an asynchronous slotted transmission mechanism that provides a high bandwidth, low delay connection-oriented transport service to the end user. In this paper, we provide an analytical approach for determining the performance of a virtual circuit connection for data transmission in a high-speed ATM network with finite buffers at the network nodes. The analysis assumes that the network operates using thebest effort delivery strategy and that the end-to-end virtual circuit is responsible for guaranteeing the integrity of the connection. Since the normal Markovian assumptions do not apply, a concise exact solution is impossible to obtain. This provides motivation for developing approximate techniques such as those found in Whitt's QNA paper that allow us to use general distributions for the traffic streams and service times. However, even these techniques assume infinite buffer capacities and hence cannot model buffer overflow. We have therefore developed a hybrid model that allows us to incorporate finite buffers at the nodes. This enables us to study the effect on the performance of both link errors and buffer overflow in conjunction with an end-to-end packet loss recovery scheme.This work was supported in part by a grant from AT&T and in part by NSF under Grant No. 8914447.Work done while at the University of Pennsylvania, Philadelphia, PA 19104, USA     

Stochastic models of space priority mechanisms with Markovian arrival processes

In this paper, we study a single-server queue with finite capacity in which several space priority mechanisms are implemented. The arrival process is the general Markovian arrival process (MAP) which has been used to model the bursty arrival processes commonly arising in communication applications. The service times are generally distributed. These buffer mechanisms enable the Asynchronous Transfer Mode (ATM) layer to adapt the quality of the cell transfer to the quality of service requirements of the specific broadband ISDN services and to improve the utilization of the network resources. This is done by a selective discarding of cells according to the class they belong to. Computable expressions for various performance parameters are obtained. Numerical results are given for the case of a two-state Markov-modulated Poisson process (MMPP) and deterministic service times. The values derived can be used to evaluate the benefits of using priorities in an ATM network when the traffic is bursty and to make a comparative study of the buffer mechanisms. These results extend the models previously developed, which were limited to Poisson arrivals.     

Minisum collection depots location problem with multiple facilities on a network

We investigate the problem of locating a set of service facilities that need to service customers on a network. To provide service, a server has to visit both the demand node and one of several collection depots. We employ the criterion of minimizing the weighted sum of round trip distances. We prove that there exists a dominating location set for the problem on a general network. The properties of the solution on a tree and on a cycle are discussed. The problem of locating service facilities and collection depots simultaneously is also studied. To solve the problem on a general network, we suggest a Lagrangian relaxation imbedded branch-and-bound algorithm. Computational results are reported.     

Price and QoS competition in data communication services

Pricing of data communication services has been studied, but primarily in a monopolistic setting. We study the price competition in packet-switching networks with a quality-of-service (QoS) guarantee in terms of an expected per-packet delay. We propose a general framework in which service providers offering multi-class priority-based services compete to maximize their profits, while satisfying the expected delay guarantee in each class. We first examine the price competition with fixed delay guarantees and then extend it to the situation where providers compete in quality of service as well as price. In each case, we compare the duopoly pricing scheme with the case when two service providers merge to become a monopoly provider.     

网络众包社区服务质量感知对用户知识行为的影响——一个多重中介作用模型

网络众包社区是互联网环境下大众相互协作共同完成特定任务的信息交流平台。本文首先从环境质量、交互质量和结果质量3个方面来评价网络众包社区用户感知服务质量,再引入用户沉浸体验、社会临场感与社群卷入作为中介变量,探讨用户感知服务质量对其知识搜索和知识贡献的影响机理。基于216份调查问卷进行实证检验,结果表明:(1)环境质量、交互质量和结果质量均是构成用户对网络众包社区服务质量感知的关键维度;(2)沉浸体验在服务质量感知与知识搜索之间所起的中介作用更大,而社会临场感在服务质量感知与知识贡献之间所起的中介作用更大;(3)社群卷入在沉浸体验与知识贡献之间起着部分中介作用,而在社会临场感与知识贡献之间起着完全中介作用。     

A traffic control algorithm for Clos network type ATM switches

This paper presents a new traffic control algorithm for asynchronous transfer mode (ATM) switches composed of Clos network type switch fabric. In most traffic control algorithms previously proposed, an ATM switch has been considered as a single node, although the switch fabric of an ATM switch is usually of a network type. In this paper, we suggest a new control algorithm that is designed not only for the ATM network but also for the switch fabric and that can maintain high speed even in cases where buffer capacity of the switch fabric is limited. Main modules of the suggested algorithm are a traffic status detection mechanism based on non-parametric statistical tests, a cell-loss detection mechanism, and a cluster-based fair share computation procedure. Results of simulation experiments show that the suggested algorithm satisfactorily adjusts traffic rate of available bit rate services according to changes in traffic rate used by quality of service (QoS) guaranteed services. The results also show that the algorithm prevents cell losses relatively well and keeps the delay time of QoS guaranteed services short enough.     

An Ergodic Algorithm for the Power-Control Games for CDMA Data Networks

In this paper, we consider power control for the uplink of a direct-sequence code-division multiple-access data network. In the uplink, the purpose of power control is for each user to transmit enough power so that it can achieve the required quality of service without causing unnecessary interference to other users in the system. One method that has been very successful in solving this purpose for power control is the game-theoretic approach. The problem for power control is modified as a Nash equilibrium problem in which each user can choose its transmit power in order to maximize its own utility, and a Nash equilibrium is an ideal solution of the power-control game. We present a noncooperative power-control game in which each user can choose the transmit power in a way that it gets the sufficient signal-to-interference-plus-noise ratio and maximizes its own utility. To ensure the existence of a solution, we also propose the variational inequality problem which is connected with the proposed game. On a linear receiver, we deal with the matched filter receiver. Next we present a new ergodic algorithm for the proposed power control because the existing iterative algorithms can not be applied effectively to the proposed power control. We also present convergence analysis for the proposed algorithm. In addition, applying the proposed algorithm to the proposed power control, we provide numerical examples for the transmit power, the signal-to-interference-plus-noise ratio and so on. Numerical results for the proposed algorithm shall show that as compared with the existing power-control game and its method, all users in the network can enjoy the sufficient signal-to-interference-plus-noise ratio and achieve the required quality of service.      

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.     

An incentive charging scheme for video-on-demand

Video-on-demand (VOD) systems can provide either an individual service or batch service. For individual service, a user can receive video immediately after making a request and he/she can perform interactive operations (such as pause, jump, fast forward and rewind), and the system uses one video stream to serve one user. For batch service, a user has to wait after making a request and cannot perform interactive operations, but the system can use one video stream to serve a batch of users. Therefore, individual service has a better quality while batch service requires less resources to serve each user. In this paper, we consider a VOD system providing both services and propose an incentive charging scheme to optimize the coexistence of both services. This scheme imposes a lower service charge on batch service in order to attract users to choose this service. Consequently, the service provider can get more revenue by serving more concurrent users via batch service and users can choose their preferred services. We analyze the incentive charging scheme and maximize the mean revenue subject to a given availability specification. The numerical results show that the incentive charging scheme is particularly effective in peak hours when the demand for the VOD service is large.     

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.     

The concert queueing game: strategic arrivals with waiting and tardiness costs

We consider the noncooperative choice of arrival times by individual users, who seek service at a first-come first-served queueing system that opens up at a given time. Each user wishes to obtain service as early as possible, while minimizing the expected wait in the queue. This problem was recently studied within a simplified fluid-scale model. Here, we address the unscaled stochastic system, assuming a finite (possibly random) number of homogeneous users, exponential service times, and linear cost functions. In this setting, we establish that there exists a unique Nash equilibrium, which is symmetric across users, and characterize the equilibrium arrival-time distribution of each user in terms of a corresponding set of differential equations. We further establish convergence of the Nash equilibrium solution to that of the associated fluid model as the number of users is increased. We finally consider the price of anarchy in our system and show that it exceeds 2, but converges to this value for a large population size.     

A two-server queueing system with periodic and credit-based server availabilities

A discrete-time, two-server queueing system is studied in this paper. The service time of a customer (cell) is fixed and equal to one time unit. Server 1 provides for periodic service of the queue (periodT). Server 2 provides for service only when server 1 is unavailable and provided that the associated service credit is nonzero. The resulting system is shown to model the queueing behavior of a network user which is subject to traffic regulation for congestion avoidance in high speed ATM networks. A general methodology is developed for the study of this queueing system, based on renewal theory. The dimensionality of the developed model is independent ofT;T increases with the network speed. The cell loss probabilities are computed in the case of finite capacity queue.Research supported by the National Science Foundation under grant NCR-9011962.     

Generalized Fibonacci broadcasting: An efficient VOD scheme with user bandwidth limit

Broadcasting is attractive in delivering popular videos in video-on-demand service, because the server broadcast bandwidth is independent of the number of users. However, the required server bandwidth does depend on how much bandwidth each user can use, as well as on the user's initial waiting time. This paper addresses the issue of limiting the user bandwidth, and proposes a new broadcasting scheme, named Generalized Fibonacci Broadcasting (GFB). In terms of many performance graphs, we show that, for any given combination of the server bandwidth and user bandwidth, GFB can achieve the least waiting time among all the currently known fixed-delay broadcasting schemes. Furthermore, it is very easy to implement GFB. We also demonstrate that there is a trade-off between the user waiting time and the buffer requirement at the user.     

Service outsourcing under co-opetition and information asymmetry

Co-opetition refers to the phenomenon that firms simultaneously cooperate and compete in order to maximize their profits. This paper studies the contracting for an outsourcing supply chain (a user company vs. a service provider) in the presence of co-opetition and information asymmetry. The user company outsources part of his service capacity at a discount price to the service provider for sale. The service provider charges a commission for doing outsourcing work and competes with the user company for the service capacity to satisfy their respective demands. We solve for the service provider’s optimal commission decision and the user company’s optimal outsourcing decisions (outsourcing volume and price discount) when the user company has private information about his service capacity. Specifically, we highlight the following observations. For the service provider, a menu of two-part tariffs that consist of a fixed commission and a per-volume commission can reveal the true type of the user company’s capacity; the user company’s optimal outsourcing proportion is quasi-convex and the optimal price discount is non-decreasing in his capacity volume, which is counterintuitive.     

随机需求下物流服务供应链订购策略研究

针对由单个物流服务提供商和集成商组成的物流服务供应链,基于集中化模式、纳什博弈模式和Stackelberg博弈模式三种典型模式,考虑市场需求随机且受服务质量缺陷承诺水平的影响,探讨物流服务供应链的订购与质量缺陷承诺策略问题。通过分析发现:物流服务质量缺陷承诺水平随着市场需求弹性系数的增加而递减,但其受物流服务集成商观测水平的影响却因合作模式不同而变化不一致;集中化模式下的物流服务订购量随着物流服务集成商观测水平或市场需求弹性系数的增大而递减,但在其他两种合作模式下物流服务订购量随着物流服务集成商观测水平或市场需求弹性系数的增加而增加;在三种模式下,物流服务供应链的整体利润随着市场需求弹性系数的增加而递减,但其受物流服务集成商观测水平的影响却因合作模式不同而变化不一致。     

Bandwidth allocation and access control in high-speed networks

The problem of bandwidth allocation and access regulation arises in the congestion control of Broadband ISDN networks. This paper assumes that a single user, described by an on-off fluid model, is connected to the network via a leaky bucket access control mechanism. The bandwidth allocated to this user and the leaky bucket parameters are to be selected so as to guarantee a negotiated level of delay probability at the access point and packet loss probability in the network which is modelled as an output buffer. The design problem is to minimize the allocated bandwidth subject to service guarantees and stability conditions for the input and output buffers. We provide a desirable feasible solution to the design problem. The paper studies the effect of non-conforming users on the network performance using the leaky bucket access control corresponding to this feasible solution. We provide expressions that quantify the impact of the leaky bucket parameters in access regulation and the worst-case queueing behavior at the output buffer. Finally, we discuss the extension of this methodology to the multiple leaky buckets case.This research was supported in part by IBM Research Contract No. 1374.