Given the proximity of many wireless users and their diversity in consuming local resources (e.g., data-plans, computation and energy resources), device-to-device (D2D) resource sharing is a promising approach towards realizing a sharing economy. This paper adopts an easy-to-implement greedy matching algorithm with distributed fashion and only sub-linear$O(\log n)$parallel complexity (in user number$n$) for large-scale D2D sharing. Practical cases indicate that the greedy matching's average performance is far better than the worst-case approximation ratio 50% as compared to the optimum. However, there is no rigorous average-case analysis in the literature to back up such encouraging findings and this paper is the first to present such analysis for multiple representative classes of graphs. For 1D linear networks, we prove that our greedy algorithm performs better than 86.5% of the optimum. For 2D grids, though dynamic programming cannot be directly applied, we still prove this average performance ratio to be above 76%. For the more challenging Erdos-Rényi random graphs, we equivalently reduce to the asymptotic analysis of random trees and successfully prove a ratio up to 79%. Finally, we conduct experiments using real data to simulate realistic D2D networks, and show that our analytical performance measure approximates well practical cases.

While some mobile users in wireless networks may experience temporal scarcity of wireless network resources such as data plan, computation capacity and energy storage, some others may leave them underutilized. If the appropriate market existed, users connected locally with D2D links could exchange such resources with low communication cost and realize significant efficiency gains by reducing waste and achieving resource pooling. This paper proposes such a D2D trading market that scales for large numbers of users. Contrary to traditional resource allocation solutions that are mostly centralized, our double auction mechanism exploits local D2D connectivity and uses distributed computation to achieve near-optimal allocative efficiency. The final prices for each matched pair of buyer and seller are adjusted in a way to induce incentive compatibility and depend on their own declarations in terms of quantity and valuation. We prove that the overall mechanism has significant social welfare gains compared to other widely-used distributed pricing mechanisms. It is also individually rational, ex-ante budget balanced using a subscription fee, and robust to perturbations of the model parameters. To render the system fully manipulation-proof, we further propose a distributed auditing scheme that prevents users from altering the decentralized computation to increase their profits. Finally, we model the repeated execution of the mechanism and determine the best trading frequency by taking into account the arrivals and departures of new participants.

Given the proximity of many wireless users and their diversity in consuming local resources (e.g., data-plans, computation and even energy resources), device-to-device (D2D) resource sharing is a promising approach towards realizing a sharing economy. In the resulting networked economy, n users segment themselves into sellers and buyers that need to be efficiently matched locally. This paper adopts an easy-to-implement greedy matching algorithm with distributed fashion and only sub-linear O(log n) parallel complexity, which offers a great advantage compared to the optimal but computational-expensive centralized matching. But is it efficient compared to the optimal matching? Extensive simulations indicate that in a large number of practical cases the average loss is no more than 10%, a far better result than the 50% loss bound in the worst case. However, there is no rigorous average-case analysis in the literature to back up such encouraging findings, which is a fundamental step towards supporting the practical use of greedy matching in D2D sharing. This paper is the first to present the rigorous average analysis of certain representative classes of graphs with random parameters, by proposing a new asymptotic methodology. For typical 2D grids with random matching weights we rigorously prove that our greedy algorithm performs better than 84.9% of the optimal, while for typical Erdős-Rényi random graphs we prove a lower bound of 79% when the graph is neither dense nor sparse. Finally, we use realistic data to show that our random graph models approximate well D2D sharing networks encountered in practice.

In this paper, we analyse how a peer-to-peer sharing platform should price its service to maximize profit, when user participation increases the value of the service to others by causing positive externalities. Modelling the service as an excludable public good, we propose a bounded utility model to capture many infrastructure sharing applications with bounded network value, in which complete coverage generates finite user valuation (e.g., WiFi or hotspot). Unbounded utility models are used to capture the large-scale user interactions in social media, where the network value follows Metcalfe's or Zipf's law. For these utility models, we analyze the optimal pricing schemes in the case of heterogeneous users under complete and incomplete information of users' service valuations. We propose the concept of `price of information' (PoI) to characterize the profit loss due to lack of information, and present asymptotic PoI bounds for different utility models. We also show that the difficult-to-implement differentiated pricing scheme, which is optimal under incomplete user information, can be replaced by a simple uniform price scheme that is asymptotic optimal. Finally, we extend our pricing schemes to a two-sided market by including a new group of `pure' service users who do not contribute to the public good, and show that the platform may charge zero price to the original group of users in order to attract this pure user group.

Mobile users in future wireless networks face limited wireless resources such as data plan, computation capacity and energy storage. Given that some of these users may not be utilizing fully their wireless resources, device-to-device (D2D) resource sharing is a promising approach to exploit users' diversity in resource use and for pooling their resources locally. In this paper, we propose a novel two-sided D2D trading market model that enables a large number of locally connected users to trade resources. Traditional resource allocation solutions are mostly centralized without considering users' local D2D connectivity constraints, becoming unscalable for large-scale trading. In addition, there may be market failure since selfish users will not truthfully report their actual valuations and quantities for buying or selling resources. To address these two key challenges, we first investigate the distributed resource allocation problem with D2D assignment constraints. Based on the greedy idea of maximum weighted matching, we propose a fast algorithm to achieve near-optimal average allocative efficiency. Then, we combine it with a new pricing mechanism that adjusts the final trading prices for buying and selling resources in a way that buyers and sellers are incentivized to truthfully report their valuations and available resource quantities. Unlike traditional double auctions with a central controller, this pricing mechanism is fully distributed in the sense that the final trading prices between each matched pair of users only depend on their own declarations and hence can be calculated locally. Finally, we analyze the repeated execution of the proposed D2D trading mechanism in multiple rounds and determine the best trading frequency.

We introduce a queueing model for passengers waiting to get transport by drivers participating in a ridesharing system. The effect of available drivers' mobility pattern, their willingness to accept rides in a given location, and the incentives offered by the platform, on system throughput is considered. We characterize the largest set of passenger arrival rates which can be served by a fixed number of drivers under any policy dictating the mobility pattern of available drivers. It turns out that any rate in this set can be achieved by offering appropriate constant but region-dependent rewards to drivers for passenger pick up. Moreover, it is shown that dynamic rewards which scale in proportion to the number of passengers waiting for pick up in each region, not only maximize throughput but also significantly decrease pick up delays.

Mobile social network applications constitute an important platform for traffic information sharing, helping users collect and share sensor information about the driving conditions they experience on the traveled path in real time. In this paper we analyse the simple but fundamental model of a platform choosing between two paths: one with known deterministic travel cost and the other that alternates over time between a low and a high random cost states, where the low and the high cost states are only partially observable and perform respectively better and worse on average than the fixed cost path. The more users are routed over the stochastic path, the better the platform can infer its actual state and use it efficiently.At the Nash equilibrium, if asked to take the riskier path, in many cases selfish users (that are allowed to have access to the information collected by the platform) will myopically disregard the optimal path suggestions of the platform, leading to a suboptimal system without enough exploration on the stochastic path. We prove the interesting result that if the past collected information is hidden from users, the system becomes incentive compatible and even `sophisticated' users (in the sense that they have full capability to reverse-engineer the platform's recommendation and derive the path state distribution conditional on the recommendation) prefer to follow the platform's recommendations. In a more practical setting where the platform implements a model-free Q-learning algorithm to minimise the social travel cost, our analysis suggests that increasing the accuracy of the learning algorithm increases the range of system parameters for which sophisticated users follow the recommendations of the platform, becoming in the limit fully incentive compatible. Finally, we extend the two-path model to include more stochastic paths, and show that incentive compatibility holds under our information restriction mechanism.

Mobile data offloading is an emerging technology to alleviate cellular network congestion and improve user service quality. In this paper, we investigate the economics of mobile data offloading through access points (APs) deployed by small cell service providers (SSPs), implementing uniform volume prices for all the mobile users (MUs) in each SSP's coverage including the overlapping area. In particular, we consider a data offloading game with a single mobile network operator (MNO) and two SSPs with overlapping coverage areas, where each SSP announces a uniform price for serving the cellular traffic within its coverage, and the MNO determines the traffic volumes to offload. We show that there is no pure Nash equilibrium (PNE) under such price competition, and determine the corresponding mixed strategy Nash equilibrium (MNE) using price randomization. As a practical solution, we propose a simple one shot auction mechanism that is easy to implement and has PNEs which is payoff equivalent with the MNE under price competition. We believe that this simple mechanism due to its simplicity of determining the equilibrium prices could be used in the negotiation between the SSPs and the MNO to determine the average service prices. Finally, we study the strategic topological infrastructure placement problem using a 1-dimension (1D, linear) user traffic flow model and a 2-dimension (2D) user traffic flow model when SSPs compete assuming uniform price competition as above. We show that the first mover in the placement problem will deploy its APs to cover more than half of the total flow volume and has an advantage to obtain a higher equilibrium payoff.

Mobile data offloading is an emerging technology to alleviate cellular network congestion and improve user service quality. In this paper, we investigate the economics of mobile data offloading through access points (APs) deployed by small cell service providers (SSPs), implementing uniform volume prices for all the mobile users (MUs) in each SSP's coverage including the overlapping area. In particular, we consider a data offloading game with a single mobile network operator (MNO) and two SSPs with overlapping coverage areas, where each SSP announces a uniform price for offloading the cellular traffic within its coverage, and the MNO determines the traffic volumes to offload. We show that there is no pure Nash equilibrium (PNE) in the data offloading game, and prove the existence of the mixed strategy Nash equilibrium (MNE) by price randomization. Furthermore, we propose a simple one shot auction mechanism that is easy to implement and has PNEs which yield SSPs the same equilibrium payoffs compared to the expected payoffs obtained at the above MNE.

Today, mobile users are intensively interconnected thanks to the emerging mobile social networks, where they share location-based information with each other when traveling on different routes and visit different areas of the city. In our model, the information collected is aggregated over all users' trips and made publicly available as a public good. Due to information overlap, the total useful content amount increases with the diversity in path choices made by the users, and it is crucial to motivate selfish users to choose different paths, despite the potentially higher costs associated with their trips. In this paper, we combine the benefits from social information sharing with the fundamental routing problem where a unit mass of non-atomic selfish users decides their trips in a non-cooperative game by choosing between a high-cost and a low-cost path. To remedy the inefficient low-content equilibrium where all users choose to explore a single path (the low-cost path), we propose and analyze two new incentive mechanisms that can be used by the social network application, one based on side payments and the other on restricting access to content for users that choose the low cost path. Under asymmetric information about user types (their valuations for content quality), both mechanisms efficiently penalize the participants that use the low-cost path and reward the participants that take the high-cost path. They lead to greater path diversity and hence to more total available content at the social cost of reduced user participation or restricted content to part of the users. We show that user heterogeneity can have opposite effects on social efficiency depending on the mechanism used. We also obtain interesting price of anarchy results that show some fundamental tradeoffs between achieving path diversity and maintaining greater user participation, motivating a combined mechanism to further increase the social welfare. Our model extends classical dynamic routing in the case of externalities caused from traffic on different paths of the network.

Congestion control protocols for background data are commonly conceived and designed to emulate low priority traffic, which yields to transmission control protocol (TCP) flows. In the presence of even a few very long TCP flows, this behavior can cause bandwidth starvation, and hence, the accumulation of large numbers of background data flows for prolonged periods of time, which may ultimately have an adverse effect on the download delays of delay-sensitive TCP flows. In this paper, we look at the fundamental problem of designing congestion control protocols for background traffic with the minimum impact on short TCP flows while achieving a certain desired average throughput over time. The corresponding optimal policy under various assumptions on the available information is obtained analytically. We give tight bounds of the distance between TCP-based background transfer protocols and the optimal policy, and identify the range of system parameters for which more sophisticated congestion control makes a noticeable difference. Based on these results, we propose an access control algorithm for systems where control on aggregates of background flows can be exercised, as in file servers. Simulations of simple network topologies suggest that this type of access control performs better than protocols emulating low priority over a wide range of parameters.

Paid peering is controversial. Generally speaking, large access ISPs favour it, while Content Providers (CPs) do not. But is CP opposition to paid peering irrational, especially if their transferred payments can incentivize the ISP to make greater investment in the common infrastructure? To answer this question we analyze an ecosystem consisting of a single access ISP that directly interconnects with multiple CPs, doing so in two extreme situations: when paid peering is used for all the involved CPs, and when all parties agree on a settlement-free deal. We analyse the equilibrium, finding the total amount of investments and profits of the various stakeholders, when their revenues are affected by the total investment in infrastructure and the charges that result from the different agreements. Interestingly, it turns out whether or not there is benefit to a CP, depends on whether its business model is to sell content, and so it can recover part of the paid peering charge by raising prices to its customers, or if the CP obtains its revenue from ads. It also depends on the volume (in traffic units) per customer transaction, since we find that CPs with high volume per transaction will be charged less per byte, and so will contribute proportionally less to the total paid peering revenue that subsidizes the common ISP infrastructure. We also find a crucial role for the end-users' evaluation of the level of investments of the various market players. Another relevant factor is the access price that an ISP charges its customers.

We have developed a novel methodology for deriving bandwidth prices for premium direct peering between Access ISPs (A-ISPs) and Content and Service Providers (CSPs) that want to deliver content and services in premium quality. Our methodology establishes a direct link between service profitability, for example, from advertising, user and subscriber loyalty, interconnection costs, and finally bandwidth price for peering. Unlike existing work in both the networking and economics literature, our resulting computational model, built around Nash bargaining, can be used for deriving quantitative results comparable to actual market prices. We analyze the U.S. market and derive prices for video, that compare favorably with existing prices for transit and paid peering. We also observe that the fair prices returned by the model for high-profit/low-volume services such as search, are orders of magnitude higher than current bandwidth prices. This implies that resolving existing (fierce) interconnection tussles may require per service, instead of wholesale, peering between A-ISPs and CSPs. Our model can be used for deriving initial benchmark prices for such negotiations.

Today’s communication networks and networked systems are highly complex and heterogeneous \nand are often owned by profit-making entities. For new technologies or \ninfrastructure designs to be adopted, they must not only be based on sound engineering \nperformance considerations but also present the right economic incentives. Recent \nchanges in regulations of the telecommunication industry make such economic considerations \neven more urgent. For instance, new concerns such as network neutrality \nhave a significant impact on the evolution of communication networks. \nAt the same time, communication networks and networked systems support increasing \neconomic activity based on applications and services such as cloud computing, \nsocial networks, and peer-to-peer networks. These applications pose new challenges \nincluding the development of good pricing and incentive mechanisms to promote effective \nsystem-wide behavior. Similarly, the security and privacy of these applications are \nthemselves heavily dependent on economic considerations, which therefore need to be \nfully understood. \nTo address these questions, this special issue brings together a relevant set of state-of-the-art research contributions on complementary topics including communication \nnetworks, wireless networks, web content and security, and the use of multidisciplinary \napproaches ranging from game theory and economic modeling to algorithms \nand mechanism design, and including empirical studies.

In this paper we present a methodology for the design of congestion control protocols for background data transfers that have a minimal delay impact on short TCP transfers and compete for a target share of the leftover average capacity with other background TCP transfers. We analytically compute the optimal policy and show that it's delay performance can be well approximated by a weighted TCP policy, which maintains a target proportion of TCPs bandwidth at all times in order to achieve the same share of excess capacity. The relative approximation error is always less than 17.2% while it quickly decreases to zero as the number of coexisting background TCP flows increases. Next, we consider a general utility-based fairness criterion for sharing the leftover average capacity, including a penalty term capturing the delay impact to short flows. The criterion is jointly optimized over all allocations of excess capacity to background flows (including TCP ones) on long timescales, and all bandwidth sharing policies on fast time scales. Even though the delay optimal sharing policy that solves the above optimization problem does not lead to distributed congestion control algorithms and more significantly, requires knowledge of the number of competing background TCP flows, both problems disappear under the weighted TCP policy. A distributed weight adjustment policy is considered where, at equilibrium, the overall performance is nearly optimal, with a vanishing relative optimality error as the number of background TCP flows increases. We illustrate the methodology by giving two examples of congestion control algorithms for background transfers. Both achieve low delay for short flows relative to TCP, but at the same time they present strong incentives for adoption against incumbent low priority solutions in public environments.

In designing and managing a shared infrastructure, one must take account of the fact that its participants will make self-interested and strategic decisions about the resources that they are willing to contribute to it and/or the share of its cost that they are willing to bear. Taking proper account of the incentive issues that thereby arise, we design mechanisms that, by eliciting appropriate information from the participants, can obtain for them maximal social welfare, subject to charging payments that are sufficient to cover costs. We show that there are incentivizing roles to be played both by the payments that we ask from the participants and the specification of how resources are to be shared. New in this paper is our formulation of models for designing optimal management policies, our analysis that demonstrates the inadequacy of simple sharing policies, and our proposals for some better ones. We learn that simple policies may be far from optimal and that efficient policy design is not trivial. However, we find that optimal policies have simple forms in the limit as the number of participants becomes large.

The Internet has evolved towards a unique technology base for creating value-added services with worldwide connectivity. These services, enabled by the increasing bandwidth of access networks, result in new high-performance applications (e.g. e-health, high definition video streaming, network gaming etc.) To support and materialize the value of these emerging services, it is important for the operators to be able to provide some form of Quality of Service (QoS) assurance. This paper presents the main economic issues regarding the efficient provisioning of such services in inter-domain level and overviews some candidate economic mechanisms and game-theoretic tools that could be adopted.

Abstract The concept of service‐oriented architectures (SOA) has recently emerged as a design principle for the next generation of IT solutions. The main idea behind SOA lies in treating software applications as composed of simpler, cooperating services, implemented by components that communicate over networks through open standards. Such a modular structure is expected to question the effectiveness of current business models for building and distributing software, which generate revenue through license fees. Under SOA, the license fee is replaced by more flexible schemes, whereby users are charged according to their actual usage of services and the corresponding hardware infrastructure. Our work constitutes a first step toward exploring the economic aspects of a market for software components, as well as the incentives of software manufacturers to support this trend. In particular, we examine the factors that affect profitability in an open market for services, we build simple models to predict and explain market growth and we also suggest ways to accelerate this growth, while also achieving a higher level of economic efficiency. Copyright © 2009 John Wiley & Sons, Ltd.

We investigate the problem of efficient resource control for elastic traffic over the EDCA (Enhanced Distributed Channel Access) and HCCA (Hybrid Coordination Function - HCF - Controlled Channel Access) mechanisms of IEEE 802.11e. Our approach considers an economic modelling framework based on congestion pricing that captures how various factors, such as the probability of attempting to transmit a frame, the transmission opportunity (TXOP), and the physical layer transmission rate, contribute to congestion. Additionally, we consider the joint control of the EDCA and HCCA mechanisms, which allows us to determine the optimal sharing of the wireless channel between the two access mechanisms.

We investigate the problem of efficient resource control for elastic traffic in IEEE 802.11e's enhanced distributed channel access (EDCA) mechanism. Our approach considers an economic modelling framework based on congestion pricing that captures how various factors, such as the probability of attempting to transmit a frame, the use of the basic CSMA/CA or the RTS/CTS procedure, and the physical layer transmission rate, contribute to congestion. We discuss the application of the framework for achieving class-based throughput differentiation, for performing explicit congestion notification (ECN) marking based on the level of congestion in the wireless channel, and for modelling the performance of TCP congestion control over EDCA. In these application scenarios we discuss how to estimate the optimum minimum contention window and the congestion prices based on the 802.11e parameters and actual measurements, in order to achieve efficient channel utilization

We consider problems of provisioning an excludable public good amongst n potential members of a peer-to-peer system who are able to communicate information about their private preferences for the good. The cost of provisioning the good in quantity Q depends on Q, and may also depend on n, or on the final number of participating peers m. Our aim is to maximize the expected social welfare in a way that is incentive compatible, rational and budget-balanced. Although it is unfortunately almost never possible to calculate or implement a truely optimal mechanism design, we show that as the number of participants becomes large the expected social welfare that can be obtained by the optimal design is at most a factor 1+O(1/n) or 1+O(1//spl radic/n) greater than that which can be obtained with a very simple scheme that requires only payment of a fixed contribution from any agent who joins the system as a participating peer. Our first application is to a model of file sharing, in which the public good is content availability; the second concerns a problem of peering wireless local area networks, in which the public good is the availability of connectivity for roaming peers. In both problems, we can cope with the requirement that the payments be made in kind, rather than in cash.

We revisit the network-wide Progressive Second Price auction (PSP) proposed by Lazar and Semret in cite2. In this mechanism, each bidder submits the same bid in each link of the path he is interested in, taking into account the overall competition in the path. We propose a new strategy in which each bidder apportions his total bid-price in the various links, while taking into account the competition in each link separately. We have carried out a wide variety of experiments and compare our strategy with the original one with respect to efficiency and bidders' net benefit. We show that our strategy yields an outcome closer to the optimal social welfare as well as higher expected net benefit for bidders in most of the cases.

We investigate the problem of efficient resource control for loss-sensitive traffic in CDMA networks, using an economic modelling framework that takes into account the joint control of the transmission rate and the signal quality. Although the corresponding global optimization problem has a non-trivial structure, and we cannot in general guarantee that a solution can be found using the Lagrangian method, we have strong experimental evidence that this is possible for a wide range of user utilities. In this case the global optimum can be achieved in a decentralized manner, using shadow prices to influence the individual user resource requests. Based on this evidence, the main contribution of the paper is to discuss how existing rate control and outer-loop power control procedures can obtain a simple and attractive form that takes into account, through shadow prices, the level of demand and supply in order to achieve efficient resource utilization. Moreover, we describe and evaluate approximations of the proposed resource control model that can simplify its application, and we present extensions of the model for the case where the packet success ratio depends on the transmission rate in addition to the signal quality, and for network paths containing multiple wireless links.

We address the incentive issues that arise in a peer-to-peer WLAN consortium (P. Antoniadis et al., 2003). We explore the use of flexible rules on reciprocity to guide domain policies and develop a suitable economic model that demonstrates the basic characteristics of our system.

For a multiplexer fed by a large number of sources, we derive conditions under which a given subset of the sources can be substituted for a single source while preserving the buffer overflow probability and the dominant timescales of buffer overflows. This notion of traffic equivalence is stronger than simple effective bandwidth equality and depends on the multiplexing context. We propose several applications of the above traffic substitution conditions. First, we show that fractional Brownian motion as a single source substitute can effectively model a large number of multiplexed sources using information obtained purely from traffic traces; this has direct application to simple but accurate traffic generation. Second, we focus on dynamic (i.e., on-line) estimation of available capacity and buffer overflow probability. This requires the solution of a double optimization problem expressed in terms of functions whose values are obtained from time averages of the traffic traces over a large range of timescales. We show how to solve this problem on-line by reducing it to the calculation of a fixed-point equation that can be solved iteratively by combining traffic substitution using fractional Brownian motion with dynamic measurements of the actual traffic. We have validated this approach by extensive experimentation with large numbers of real traffic sources that are fed to a high bandwidth link, and comparing our on-line estimation of available capacity and the resulting dynamic call admission control with other existing approaches. The superior accuracy of our approach also suggests that taking the buffer size into account, as does our on-line algorithm, may be vital for achieving approximations of practical interest.

This paper introduces a framework for answering questions regarding the conditions on the network load that allow a best-effort network like the Internet to support connections of given duration that require a certain quality of service. Such quality of service is expressed in terms of the percentage of time the bandwidth allocated to a connection may drop below a certain level or the maximum allowable delay in placing the call through the network waiting for more favorable loading conditions. The call-acceptance conditions, which depend on the behavior of the system over the lifetime of accepted calls, are thus based on transient models for the congestion (instead of looking at the average behavior) and attempt to exploit the time-scales of the fluctuations of the number of connections competing for bandwidth. Extensions of the model consider the case of dynamic pricing which allows connections that pay more to get larger shares of the bandwidth, and investigate the trade-off between quality of service, the size of the acceptance region, and the charge to be paid by the connection. Under this framework we introduce an option contract that reduces the risk of quality disruption, if a user has a fixed budget at his disposal, and calculate its price. One potential use of this methodology is towards developing a simple admission control mechanism for placing voice calls through an IP network, where the decisions can be taken by edge devices.

We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution U{j,k}, $1 < j \leq k,$ where each item size in {1/k,2/k,. . .,j/k} has probability 1/j of being chosen. Note that for fixed j,k as $m\rightarrow\infty$ the discrete distributions U{mj,mk} approach the continuous distribution U(0,j/k], where the item sizes are chosen uniformly from the interval (0,j/k]. We show that average-case behavior can differ substantially between the two types of distributions. In particular, for all j,k with j < k-1, there exist on-line algorithms that have constant expected wasted space under U{j,k}, whereas no on-line algorithm has even o(n 1/2 ) expected waste under U(0,u] for any $0 < u \leq 1$. Our U{j,k} result is an application of a general theorem of Courcoubetis and Weber [C. Courcoubetis and R.R. Weber, Probab. Engrg. Inform. Sci., 4 (1990), pp. 447--460] that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or O(1), depending on whether certain"perfect" packings exist. The perfect packing theorem needed for the U{j,k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper.

For a multiplexer fed with a large number of sources, we derive conditions under which a single source can be substituted for a given subset of the sources while preserving the buffer overflow probability and the dominant time scales of buffer overflows. This equivalence is stronger than simple effective bandwidth equality and takes into account the context in which multiplexing takes place. This allows a substitution to be made for arbitrarily large proportions of the traffic without changing the operating point of the multiplexer as experienced by the rest of the traffic. It corresponds to defining a single source which is equivalent in a sense "local" to a given context, rather than equivalent in a sense which is "universal" to all contexts. The proposed methodology does not rely on traffic models and obtains the necessary information from the actual traffic traces. We study the case of fractional Brownian motion as a single source substitute and provide theoretical and experimental results that validate our approach.

We evaluate usage-based pricing schemes that are based on bounds of the effective bandwidth. The schemes include ones that require simple measurements (time and volume) for the whole duration of a call, and two schemes that require measurements in distinct time intervals, smaller than the duration of a call: pricing with renegotiation and the virtual bucket scheme. Using MPEG-1 compressed video, the schemes are compared for different link capacities and buffer sizes in terms of their fairness, i.e., the ability to capture the relative amount of resources used by connections.

Accurate yet simple methods for traffic engineering are important for efficient dimensioning of broadband networks. The goal of this paper is to apply and evaluate large deviation techniques for traffic engineering. In particular, we employ the recently developed theory of effective bandwidths, where the effective bandwidth depends not only on the statistical characteristics of the traffic stream, but also on a link's operating point through two parameters, the space and time parameters, which are computed using the many sources asymptotic. We show that this effective bandwidth definition can accurately quantify resource usage. Furthermore, we estimate and interpret values of the space and time parameters for various mixes of real traffic demonstrating how these values can be used to clarify the effects on the link performance of the time scales of burstiness of the traffic input, of the link parameters (capacity and buffer), and of traffic control mechanisms, such as traffic shaping. Our approach relies on off-line analysis of traffic traces, the granularity of which is determined by the time parameter of the link, and our experiments involve a large set of MPEG-1 compressed video and Internet Wide Area Network (WAN) traces, as well as modeled voice traffic.

We study the problem of uniquely identifying the initial state of a given finite-state machine from among a set of possible choices, based on the input-output behavior. Equivalently, given a set of machines, the problem is to design a test that distinguishes among them. We consider nondeterministic machines as well as probabilistic machines. In both cases, we show that it is Pspace-complete to decide whether there is a preset distinguishing strategy (i.e. a sequence of inputs fixed in advance), and it is Exptime-complete to decide whether there is an adaptive distinguishing strategy (i.e. when the next input can be chosen based on the outputs observed so far). The probabilistic testing is closely related to probabilistic games, or Markov Decision Processes, with incomplete information. We also provide optimal bounds for deciding whether such games have strategies winning with probability 1. 1 Introduction Finite-state machines have been widely used to model systems in diverse areas o...

We determine the complexity of testing whether a finite state, sequential or concurrent probabilistic program satisfies its specification expressed in linear-time temporal logic. For sequential programs, we present an algorithm that runs in time linear in the program and exponential in the specification, and also show that the problem is in PSPACE, matching the known lower bound. For concurrent programs, we show that the problem can be solved in time polynomial in the program and doubly exponential in the specification, and prove that it is complete for double exponential time. We also address these questions for specifications described by ω-automata or formulas in extended temporal logic.

Addresses the issue of call acceptance and routing in ATM networks. The goal is to design an algorithm that guarantees bounds on the fraction of cells lost by a call. The method proposed for call acceptance and routing does not require models describing the traffic. Each switch estimates the additional fraction of cells that would be lost if new calls were routed through the switch. The routing algorithm uses these estimates. The estimates are obtained by monitoring the switch operations and extrapolating to the situation where more calls are routed through the switch. The extrapolation is justified by a scaling property. To reduce the variance of the estimates, the switches calculate the cell loss that would occur with virtual buffers. A way to choose the sizes of the virtual buffers in order to minimize the variance is discussed. Thus, the switches constantly estimate their spare capacity. Simulations were performed using Markov fluid sources to test the validity of the approach.>

We present a general framework for the formal specification and algorithmic analysis of hybrid systems. A hybrid system consists of a discrete program with an analog environment. We model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. For verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. We provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. In particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. The procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. We also present approximation techniques for dealing with systems for which the iterative procedures do not converge.

The authors consider buffer asymptotics for feed-forward networks shared by heterogeneous traffic streams. This is done by identifying the effective bandwidth of the departure processes from shared queues. They introduce the idea of decoupling bandwidths and constraints which guarantee "decoupled" asymptotics within the network. They discuss these results in the context of resource management for ATM networks.>

Three algorithms for checking the emptiness of a timed transition system have been implemented. The first algorithm performs a straightforward reachability analysis on sets of states of the system, rather than on individual states. This corresponds to stepping symbolically through the system many states at a time. The other two algorithms are minimization algorithms. These simultaneously perform reachability analysis and minimization from an implicit system description. The paradigm for verification is to test for the emptiness of the set of all timed system executions that violate a requirements specification. Preliminary results over two simple examples indicate that memory usage is a more limiting factor than time.>

We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ' 'dficrete uniform" distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen.Note that for fixed j,k the distributions U{?nj;mk]' approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik].In this paper, we show that average case behavior can differ substantially under the two types of distributions.We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1'2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2,

The authors present the architecture of a general-purpose broadband-ISDN (B-ISDN) switch chip and, in particular, its novel feature: the weighted round-robin cell (packet) multiplexing algorithm and its implementation in hardware. The flow control and buffer management strategies that allow the chip to operate at top performance under congestion are given, and the reason why this multiplexing scheme should be used under those circumstances is explained. The chip architecture and how the key choices were made are discussed. The statistical performance of the switch is analyzed. The critical parts of the chip have been laid out and simulated, thus proving the feasibility of the architecture. Chip sizes of four to ten links with link throughput of 0.5 to 1 Gb/s and with about 1000 virtual circuits per switch have been realized. The results of simulations of the chip are presented.>

This research extends CTL model-checking to the analysis of real-time systems, whose correctness depends on the magnitudes of the timing delays. For specifications, the syntax of CTL is extended to allow quantitative temporal operators. The formulas of the resulting logic, TCTL, are interpretation over continuous computation trees, trees in which paths are maps from the set of nonnegative reals to system states. To model finite-state systems the notion of timed graphs is introduced-state-transition graphs extended with a mechanism that allows the expression of constant bounds on the delays between the state transition. As the main result, an algorithm is developed for model checking, that is, for determining the truth of a TCTL formula with respect to a timed graph. It is argued that choosing a dense domain, instead of a discrete domain, to model time does not blow up the complexity of the model-checking problem. On the negative side, it is shown that the denseness of the underlying time domain makes TCTL II/sub 1//sup 1/-hard. The question of deciding whether a given TCTL formula is implementable by a timed graph is also undecidable.>

Informal specifications of protocols are often imprecise and incomplete and are usually not sufficient to ensure the correctness of even very simple protocols. Consequently, formal specification methods, such as finite-state models, are increasingly being used. The selection/resolution (S/R) model is a finite-state model with a powerful communication mechanism that makes it easy to describe complex protocols as a collection of simple finite-state machines. A software environment, called SPANNER, has been developed to specify and analyze protocols specified with the S/R model. SPANNER provides the facility to compute the joint behavior of a number of finite-state machines and to check if the “product” machine has inaccessible states, states corresponding to deadlocks, and loops corresponding to livelocks. So far, however, SPANNER has had no facility to systematically deal with liveness conditions. For example, one might wish to specify that, although a communication channel is unreliable, a message will get through if it is sent infinitely often, and to check that the infinite behavior of the protocol viewed as an infinite sequence will always be in some ω-regular set (possibly specified in terms of a formula in temporal logic or as an ω-automata). In this paper we show that with very minor modifications to the implemented system it is possible to substantially extend the type of properties that can be specified and checked by SPANNER. This is done by extending the S/R model to include acceptance conditions found in automatons on infinite words, which permits the incorporation of arbitrary liveness conditions into the model. We show how these extensions can be easily incorporated into SPANNER (and into essentially any finite-state verification system) and how the resulting system is used to automatically verify the correctness of protocols.

The complexity of testing whether a finite-state (sequential or concurrent) probabilistic program satisfies its specification expressed in linear temporal logic. For sequential programs an exponential-time algorithm is given and it is shown that the problem is in PSPACE; this improves the previous upper bound by two exponentials and matches the known lower bound. For concurrent programs is is shown that the problem is complete in double exponential time, improving the previous upper and lower bounds by one exponential each. These questions are also addressed for specifications described by omega -automata or formulas in extended temporal logic.>

Resource sharing systems, such as database management systems, utilize various types of locking to maintain consistency. Most locking mechanisms cause some resources to remain idle at certain times when there is work for them to do, inducing a decrease in the system’s capacity. This decrease of capacity is reflected in the stability condition for the locking system as compared to the system without locking. We consider the following locking system. There are N servers operating in parallel and two types of incoming customers. The first type corresponds to simple customers, i.e., customers with no locking requirements, and the second corresponds to customers that have to be processed simultaneously by all N servers. When a server is ready to serve such a customer, it has to wait until all servers are ready to serve that same customer. We determine a necessary and sufficient condition for stability of this system, which can be expressed in terms of the mean of the maximum of N random variables, each representing the amount of work due to simple customers arriving at a station between successive locking customers. For a particular case we provide an asymptotic analysis which indicates that the wasted capacity in such a system grows as $\log N$.

Article Reasoning about fair concurrent programs Share on Authors: C Courcoubetis AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJView Profile , M Y Vardi IBM Almaden Research Center, Department K55/801, 650 Harry Road, San Jose, CA IBM Almaden Research Center, Department K55/801, 650 Harry Road, San Jose, CAView Profile , P Wolper AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 283–294https://doi.org/10.1145/12130.12159Online:01 November 1986Publication History 19citation247DownloadsMetricsTotal Citations19Total Downloads247Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access