This paper characterizes the outcomes of secondary spectrum markets when multiple providers compete for secondary demand. We study a competition model in which each provider aims to enhance its revenue by opportunistically serving a price-dependent secondary demand, while also serving dedicated primary demand. We consider two methodologies for sharing spectrum between primary and secondary demand: In coordinated access, spectrum providers have the option to decline a secondary access request if that helps enhance their revenue. We explicitly characterize a break-even price such that profitability of secondary access provision is guaranteed if secondary access is priced above the break-even price, regardless of the volume of secondary demand. Consequently, we establish that competition among providers that employ optimal coordinated access leads to a price war, as a result of which the provider with the lowest break-even price captures the entire market. This result holds for arbitrary secondary demand functions. In uncoordinated access, primary and secondary users share spectrum on equal basis, akin to ISM bands. Under this policy, we characterize a market sharing price that determines a provider's willingness to share the market. We show an instance where the market sharing price is strictly greater than the break-even price, indicating that market equilibrium in an uncoordinated access setting can be fundamentally different as it opens up the possibility of providers sharing the market at higher prices.

We introduce a private commons model that consists of network providers who serve a fixed primary demand and strategically price to improve their revenues from an additional secondary demand. For general forms of secondary demand, we establish the existence and uniqueness of two characteristic prices: the break-even price and the market sharing price. We show that the market sharing price is always greater than the break-even price, leading to a price interval in which a provider is both profitable and willing to share the demand. Making use of this result, we give insight into the nature of market outcomes.

We investigate profitability from secondary spectrum provision under unknown relationships between price charged for spectrum use and demand drawn at the given price. We show that profitability is governed by the applied admission policy and the price charged to secondary users. We explicitly identify a critical price (market entry price) such that if secondary demand is charged below that price, the licensee endures losses from spectrum provision, regardless of the applied admission policy. Furthermore, we show that an admission policy that admits secondary demand only when no channel is occupied is profitable for any price that exceeds the critical price. We prove that this policy is profit-robust to variations in secondary demand, i.e., if the policy is profitable for a certain price, it will be profitable for any secondary demand that the price generates, as long as the price generates demand. We also investigate profitability from a set of policies that allow more secondary users to access spectrum by defining the number of users that can be concurrently served. Our results demonstrate profit-robustness of these policies and explicitly characterize profitable prices. We provide a numerical study to verify our theoretical findings.

We consider a wireless provider who caters to two classes of customers, namely primary users (PUs) and secondary users (SUs). PUs have long term contracts while SUs are admitted and priced according to current availability of excess spectrum. The average rate at which SUs attempt to access the spectrum is a function on the currently advertised price, referred to as the demand function. We analyze the problem of maximizing the average profit gained by admissions of SUs, when the demand function is unknown. We introduce a new on-line algorithm, called Measurement-based Threshold Pricing (MTP), that requires the optimization of only two parameters, a price and a threshold, whereby SU calls are admitted and charged a fixed price when the channel occupancy is lower than the threshold and rejected otherwise. At each iteration, MTP measures the average arrival rate of SUs corresponding to a certain test price. We prove that these measurements of the secondary demand are sufficient for MTP to converge to a local optimal price and corresponding optimal threshold, within a number of measurements that is logarithmic in the total number of possible prices. We further provide an adaptive version of MTP that adjusts to time-varying demand and establish its convergence properties. We conduct numerical studies showing the convergence of MTP to near-optimal online profit and its superior performance over a traditional reinforcement learning approach.

We analyze packet delay in CSMA-based random access schemes in networks under the protocol interference model. Using a stochastic coupling argument we identify a subset of the throughput-region where queue lengths can be bounded uniformly for all network sizes. This conclusion provides a throughput-region of interest for delay sensitive applications and suggests that delay bounds based on mixing time analyses may be loose.

This paper analyzes opportunistic schemes for transmission scheduling from one of n homogeneous queues whose channel states fluctuate independently. Considered schemes consist of an LCQ policy that transmits from a longest connected queue in the entire system, and its low-complexity variant LCQ(d) that transmits from a longest queue within a randomly chosen subset of d ≥ 1 connected queues. A Markovian model is studied where mean packet transmission time is n-1and packet arrival rate is λ <; 1 per queue. Transient and equilibrium distributions of queue lengths are obtained in the limit as the system size n tends to infinity. It is shown that under LCQ almost all queues are empty in equilibrium, maximum queue length is 1, and the overall system occupancy is Θ(1) as n → ∞. Limiting distribution of the system occupancy is characterized. Limiting queue length distributions under LCQ(d) are also given. It is shown that if d is fixed then the system occupancy is Θ(n) and the queue length distribution has infinite support. If d = ω(1) but d = o(n) then the maximum queue length is 1 and the system occupancy reduces to O(n/d). Numerical comparison of the obtained asymptotic mean packet delays suggests that LCQ and LCQ(d) may have comparable delay performance for moderate values of n and d.

We consider a wireless provider who caters to two classes of customers, namely primary and secondary users. Primary users have long term contracts while secondary users are admitted and priced according to current availability of excess spectrum. Secondary users accept an advertised price with a certain probability defined by an underlying demand function. We analyze the problem of maximizing profit gained by admission of secondary users. Previous studies in the field usually assume that the demand function is known and that the call length distribution is also known and exponentially distributed. In this paper, we analyze more realistic settings where both of these quantities are unknown. Our main contribution is to derive near-optimal pricing strategies under such settings. We focus on occupancy-based pricing policies, which depend only on the total number of ongoing calls in the system. We first show that such policies are insensitive to call length distribution except through the mean. Next, we introduce a new on-line, occupancy-based pricing algorithm, called Measurement-based Threshold Pricing (MTP) that operates by measuring the reaction of secondary users to a specific price and does not require the demand function to be known. MTP optimizes a profit function that depends on price only. We prove that while the profit function can be multimodal, MTP converges to one of the local optima as fast as if the function were unimodal. Lastly, we provide numerical studies demonstrating the near-optimal performance of occupancy-based policies for diverse sets of call length distributions and demand functions and the quick convergence of MTP to near-optimal on-line profit.

We consider packet transmission scheduling at the MAC-layer via adaptive backoff algorithms that are favorable in terms of queue occupancies in a wireless network. General network topologies are considered under the operational constraint that transmitters within close proximity of each other cannot be transmitting simultaneously. Transmitters probe the channel at random instants and transmit if the channel is idle. We adopt a measurement based framework in which channel probing rates are adaptively determined based on feedback measured from the network. We consider two separate objectives associated with minimization of packet delay and packet loss rate in the network. We obtain dynamic algorithms that strictly improve channel access rates in a related fluid model. Analytical development of the algorithms is based on a convenient decomposition technique that decouples channel access and queue occupancy statistics, and that leads to a favorable tradeoff between analytical insight and modeling accuracy. Obtained algorithms are oblivious to network load and topology. We also consider versions of these algorithms that are suitable for distributed implementation and study their effectiveness numerically.

Recent deregulation initiatives enable cellular providers to sell excess spectrum for secondary usage. In this paper, we investigate the problem of optimal spot pricing of spectrum by a provider in the presence of both non-elastic primary users, with long-term commitments, and opportunistic, elastic secondary users. We first show that optimal pricing can be formulated as an infinite horizon average reward problem and solved using stochastic dynamic programming. Next, we investigate the design of efficient single pricing policies. We provide numerical and analytical evidences that static pricing policies do not perform well in such settings (in sharp contrast to settings where all the users are elastic). On the other hand, we prove that deterministic threshold pricing achieves optimal profit amongst all single-price policies and performs close to global optimal pricing. We characterize the profit regions of static and threshold pricing, as a function of the arrival rate of primary users. Under certain reasonable assumptions on the demand function, we show that the profit region of threshold pricing can be far larger than that of static pricing. Moreover, we also show that these profit regions critically depend on the support of the demand function rather than specific form of it. We prove that the profit function of threshold pricing is unimodal in price and determine a restricted interval in which the optimal threshold lies. These two properties enable very efficient computation of the optimal threshold policy that is far faster than that of the global optimal policy.

We consider pricing secondary access to wireless spectrum in cellular CDMA networks. We study the case for a primary license holder interested in leasing the right of providing service in a given geographical region of its coverage network. The goal is to price access to the cells in that region under heterogeneous call traffic demand with the objective of profit maximization. While a revenue is gained from the leased region due to the exercised price, the primary license holder incurs a loss due to reduced spatial coverage of the network and also due to interference effect from the leased into the retained region. We exploit the spatial effect of interference due to geographical locations of the cells and set a price per cell rather than pricing the whole region by a scalar quantity. We employ reduced load approximations which have proved useful in classical telephony and characterize optimal prices for different pricing philosophies, e.g., flat pricing and demand-based pricing. The obtained formula of prices suggests charging per admitted call in proportion with the interference that the call generates. The charged amount balances the corresponding loss of revenue due to the influence of an admitted call. We present an iterative price computing technique and provide a numerical study in support of our analytical results.

We consider a block-fading homogeneous broadcast channel with n users each receiving packets randomly and independently with a rate of lambda. Packets are stored in separate queues to await transmission using an opportunistic scheduling which exploits the multiuser diversity of the channel by serving the user with the most favorable channel condition at each coherence interval. In this paper, we consider a stochastic model in which mean packet transmission time is n-1and establish a convergence result for the occupancy distribution of all n queues under opportunistic scheduling. It is shown that if lambda1/lambdan + O(1) for large n. In order to improve the occupancy distribution while exploiting the multiuser diversity, we also study a scheme that serves the user with the longest queue among the d users with the most favorable channel conditions. It is shown that upper bound on the expected length of the longest queue improves to logd/lambdan + O(1). Simulation results are presented to validate our asymptotic results.

Nonloopy network topologies are considered under the limitation that a channel can be utilized only if it is idle at all neighboring sites. Random channel selection is studied under a standard circuit-switched traffic model. Upper and lower bounds for blocking probabilities are determined via an auxiliary network process whose equilibrium distribution admits a computationally convenient form. By way of another approximate characterization, it is argued that random channel selection incurs vanishing loss of optimality as the number of channels and the traffic load increase in proportion.

We propose a peer-to-peer architecture designed to overcome asymmetries in upload/download speeds that are typical in end-user dialup, broadband and cellular wireless Internet connections. Our approach allows users at remote locations to access information stored on their home computers at rates often exceeding their home connection’s upload capacity. The key to this approach is to share file data when communications are idle using random linear coding, so that, when needed, an end-user can download a file from several sources at a higher data rate than his home computer’s upload capacity. We prove that our proposed system is asymptotically fair, in that (even malicious) users are proportionally assigned idle bandwidth depending on how much bandwidth they contribute, and that there is a natural incentive to join and cooperate fairly in the system. In addition, our approach provides cryptographic security and geographic data robustness to the participating peers.

We consider feed-forward packet switched networks with fixed routing and random congestion losses. Users of the network are assumed to be greedy in the sense that each user increases its traffic rate in proportion to profit per packet that it generates. Using a deterministic fluid model, we propose perpacket pricing policies to control packet generation rates of users. The resulting rates are shown to stabilize at local maxima of two suitable choices of social welfare in the network. We give decentralized algorithms for network links to compute their prices in a stateless fashion based on piggybacking control messages on acknowledgements. The obtained analytical conclusions are verified via packet-level simulations.

We consider the problem of classifying among a set of M hypothesis with N distributed noisy sensors. The N sensors can collaborate over a finite link-capacity network. The task is to arrive at a consensus about the event after exchanging such messages. In contrast to the conventional decentralized detection approach, wherein the bit rates for each link is explicitly constrained, our approach is based on high-rate limit perspective. We apply a variant of belief propagation as a strategy for collaboration to arrive at a solution to the distributed classification problem. We show that the message evolution can be reformulated as the evolution of a linear dynamical system, which is primarily characterized by network connectivity. It turns out that consensus is almost always reached by the sensors for any arbitrary network. We then derive conditions under which the consensus is the centralized MAP estimate and show that this is achieved with O(M log/sub 2/ N) bits.

This paper concentrates on obtaining uniform weighted round robin schedules for input queued packet switches. The desired schedules are uniform in the sense that each connection is serviced at regularly spaced time slots, where the spacing is proportional to the inverse of the guaranteed data rate. Suitable applications include ATM networks as well as satellite switched TDMA systems that provide per packet delay guarantees. Three heuristic algorithms are proposed to obtain such schedules under the constraints imposed by the unit speedup of input queued switches. Numerical experiments indicate that the algorithms have remarkable performance in finding uniform schedules.

This paper concerns connection provisioning for optical networks employing wavelength division multiplexing. A heuristic algorithm is developed and numerically studied for routing and wavelength assignment of a set of static connection requests. The algorithm runs much faster than the optimum solution of this problem. An adaptation of the algorithm is proposed to design restorable networks which can handle a specified set of failures. The proposed algorithm is based on taking all failures into consideration simultaneously, and performs better than developing independent designs for each failure.

This paper concerns connection provisioning for optical networks employing wavelength division multiplexing. A heuristic algorithm is developed and numerically studied for routing and wavelength assignment of a set of static connection requests. The algorithm runs much faster than the optimum solution of this problem. An adaptation of the algorithm is proposed to design restorable networks which can handle a specified set of failures. The proposed algorithm is based on taking all failures into consideration simultaneously, and performs better than developing independent designs for each failure.

The paper focuses on the dynamic resource allocation problem. In communication networks such as wireless or circuit switching networks, resources correspond to base stations or links, and the load corresponds to the calls in the network. The principle of load balancing is examined for dynamic resource allocation. The question of interest is the performance of simple allocation strategies which can be implemented online. Either finite capacity constraints on resources or mobility of users can be incorporated into the setup. The load balancing problem is formulated as an optimal control problem, and variants of a simple "least loaded routing" policy are shown to be asymptotically optimal for large call arrival rates.