We study Bandwidth Reservation (BR) policies for the Bandwidth on Demand (BoD) problem in a class of multihop networks. We motivate an Erlang fixed-point BR heuristic for the general BoD problem by first establishing the optimality of BR on a class of multihop networks. The motivating problem is a wireline network comprising$k$links in tandem, each link of which is shared by two types of bandwidth demands, one type requiring one unit of bandwidth from every link, and the other type (being dedicated to the link) requiring one unit of bandwidth as well. First, for this$k$-hop tandem network, when each link has unit bandwidth, we demonstrate that a policy of BR form is optimal. We then study the BoD problem for a more general$k$-hop tandem network, in the “Kelly” limiting regime, where the arrival rates as well as the link bandwidths become large. For certain parameter regimes of the$k$-hop tandem network, we show that an admission control policy of BR form is asymptotically optimal. Motivated by these results, we propose an Erlang fixed-point based, link-by-link, heuristic algorithm for computing a BR policy for the BoD problem in a general network. We, finally, evaluate this proposal numerically.

Motivated by medium access control for resource-challenged wireless Internet of Things (IoT), we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a time-slotted scheduling model with $N$ sensor nodes, with pair-wise dependence, such that Nodes $i$ and $i + 1,~0 < i < N$ cannot transmit together. We develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue that we term Queue Nonemptiness-Based (QNB) policies. We propose a Policy Splicing technique to combine scheduling policies for small networks in order to construct throughput-optimal policies for larger networks, some of which also aim for low delay. For $N = 3,$ there exists a sum-queue length optimal QNB scheduling policy. We show, however, that for $N > 4,$ there is no QNB policy that is sum-queue length optimal over all arrival rate vectors in the capacity region. We then extend our results to a more general class of interference constraints that we call cluster-of-cliques (CoC) conflict graphs. We consider two types of CoC networks, namely, Linear Arrays of Cliques (LAoC) and Star-of-Cliques (SoC) networks. We develop QNB policies for these classes of networks, study their stability and delay properties, and propose and analyze techniques to reduce the amount of state information to be disseminated across the network for scheduling. In the SoC setting, we propose a throughput-optimal policy that only uses information that nodes in the network can glean by sensing activity (or lack thereof) on the channel. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability.

We consider a wireless network comprising two types of nodes, namely, sinks and relays. The sink nodes are connected to a wireline infrastructure, while the relay nodes are used to extend the region covered by providing multi-hop paths to the sink nodes. Restricting to the one-dimensional setting, our objective is to characterize the fraction of covered region as a function of sink and relay node densities. We first compare and contrast our infrastructure-based model with the traditional setting where every node is a sink, and hence a location is covered if it simply lies within the range of some node. Then, drawing an analogy between the connected components of the network and the busy periods of an M/D/∞ queue (and using renewal theoretic arguments) we derive a closed-form expression for the average vacancy (complement of coverage). We also compute an upper bound for vacancy by introducing the notion of left-coverage (i.e., coverage by a node on the left); a lower bound is derived by coupling our model with an independent-disk model, where the sinks' coverage regions are independent and identically distributed. Through an extensive theoretical and numerical study, we investigate the problem of minimizing network deployment cost subject to a constraint on the average vacancy. We also conduct simulations to understand the properties of a general notion of coverage, obtained by introducing hop-counts into the definition. Parameterized approximations for the hop-constrained cluster lengths (around a sink) are proposed, whose efficacy is evaluated numerically. In particular, there exists a range of parameter values where our cluster-length approximation is good. Finally, hop-constrained cost optimization is conducted to demonstrate the efficacy of the infrastructure-based design.

Motivated by medium access control for resource-challenged wireless sensor networks whose main purpose is data collection, we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a model with N sensor nodes, with pair-wise dependence, such that nodes i and i+1, 1 ≤ i ≤ N-1 cannot transmit together. For N=3, 4, and 5, we develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue, and also revisit previously proposed policies to rigorously establish their throughput-and delay-optimality. For N=3, there exists a sum-queue length optimal scheduling policy that requires only the empty-nonempty state of each queue. We show, however, that for N ≥ 4, there is no scheduling policy that uses only the empty-nonempty states of the queues and is sum-queue length optimal uniformly over all arrival rate vectors. We then extend our results to a more general class of interference constraints, namely, a star of cliques. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability. Our study throws up some counterintuitive conclusions: 1) knowledge of queue length information is not necessary to achieve optimal throughput/delay performance for a large class of interference networks, 2) it is possible to perform throughput-optimal scheduling by merely knowing whether queues in the network are empty or not, and 3) it is also possible to be throughput-optimal by not always scheduling the maximum possible number of nonempty queues. We also show the results of numerical experiments on the performance of queue length agnostic scheduling vs. queue length aware scheduling, on several interference networks.

We are motivated by the need, in emergency situations, for impromptu (or “as-you-go”) deployment of multihop wireless networks, by human agents or robots (e.g., unmanned aerial vehicles (UAVs)); the agent moves along a line, makes wireless link quality measurements at regular intervals, and makes on-line placement decisions using these measurements. As a first step, we have formulated such deployment along a line as a sequential decision problem. In our earlier work, reported in [1], we proposed two possible deployment approaches: (i) the pure as-you-go approach where the deployment agent can only move forward, and (ii) the explore-forward approach where the deployment agent explores a few successive steps and then selects the best relay placement location among them. The latter was shown to provide better performance (in terms of network cost, network performance, and power expenditure), but at the expense of more measurements and deployment time, which makes explore-forward impractical for quick deployment by an energy constrained agent such as a UAV. Further, since in emergency situations the terrain would be unknown, the deployment algorithm should not require a-priori knowledge of the parameters of the wireless propagation model. In [1], we, therefore, developed learning algorithms for the explore-forward approach. The current paper fills in an important gap by providing deploy-and-learn algorithms for the pure as-you-go approach. We formulate the sequential relay deployment problem as an average cost Markov decision process (MDP), which trades off among power consumption, link outage probabilities, and the number of relay nodes in the deployed network. While the pure as-you-go deployment problem was previously formulated as a discounted cost MDP (see [1]), the discounted cost MDP formulation was not amenable for learning algorithms that are proposed in this paper. In this paper, first we show structural results for the optimal policy corresponding to the average cost MDP, and provide new insights into the optimal policy. Next, by exploiting the special structure of the average cost optimality equation and by using the theory of asynchronous stochastic approximation (in single and two timescale), we develop two learning algorithms that asymptotically converge to the set of optimal policies as deployment progresses. Numerical results show reasonably fast speed of convergence, and hence the model-free algorithms can be useful for practical, fast deployment of emergency wireless networks.

We consider an opportunistic wireless communication setting, in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it becomes available (or arrives), offers a (possibly different) “reward” to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a common set of sleep-wake cycling relays. In general, our model can be considered as a game theoretic variant of the asset selling problem studied in the operations research literature. We study two variants of the generic relay selection problem, namely, the completely observable (CO) and the partially observable (PO) cases. These cases are based on whether a forwarder (in addition to observing its reward) can also observe the reward offered to the other forwarder. Formulating both problems as a two person stochastic game, we characterize the solutions in terms of Nash equilibrium policy pairs (NEPPs). For the CO case, we provide a general structure of the NEPPs. For the PO case, we prove that there exists an NEPP within the class of threshold policy pairs. Through numerical work, for a one-hop forwarding example, we compare the cost performance of various NEPPs with a simple forwarding (SF) policy, which causes each forwarder to act as if the other is not present. We find that if the forwarders are not very close then the SF policy suffices. Insights gained from this numerical work are then used in an end-to-end simulation of geographical forwarding in a large network, in which we are concerned with delivery of packets from a tagged source to a sink, in the presence of competition from other packet flows destined for the same sink.

Mixed vehicular traffic comprising small cars and two-wheeled vehicles (called motorcycles in this paper) arrive at a lane of a signalized road intersection. The traffic does not follow lane-discipline, in that the arriving vehicles do not necessarily queue up one behind the other. The motorcycles are small enough to stand side-by-side with cars or other motorcycles, so as to fill up the width of the lane. With such queue joining behavior, the waiting vehicles form batches, comprising motorcycles, and at most one car. During the green signal period the vehicles in the head-of-the-line batch exit the intersection together. In this paper, assuming a Poisson point process model for vehicle arrivals, we have provided an approximate analysis of such a queueing system. Our approach is to use an assembly queue model for the batching process. The batches generated by the assembly queue enter an interrupted M/SemiMarkov/1 (or M/SM/1) queue. By analyzing the assembly queue we characterize the batch input process for the interrupted M/SM/1 queue. We then develop an extension of the Webster mean delay formula for obtaining the approximate mean delay in the interrupted M/SM/1 queue. Numerical results from the analysis are compared with simulation results. The analysis is shown to be accurate in predicting the increase in the system capacity due to the batching behavior.

We use information theoretic achievable rate formulas for the multi-relay channel to study the problem of as-you-go deployment of relay nodes. The achievable rate formulas are for full-duplex radios at the relays and for decode-and-forward relaying. Deployment is done along the straight line joining a source node and a sink node at an unknown distance from the source. The problem is for a deployment agent to walk from the source to the sink, deploying relays as he walks, given the knowledge of the wireless path-loss model, and given that the distance to the sink node is exponentially distributed with known mean. As a precursor to the formulation of the deploy-as-you-go problem, we apply the multi-relay channel achievable rate formula to obtain the optimal power allocation to relays placed along a line, at fixed locations. This permits us to obtain the optimal placement of a given number of nodes when the distance between the source and sink is given. Numerical work for the fixed source-sink distance case suggests that, at low attenuation, the relays are mostly clustered close to the source in order to be able to cooperate among themselves, whereas at high attenuation they are uniformly placed and work as repeaters. We also prove that the effect of path-loss can be entirely mitigated if a large enough number of relays are placed uniformly between the source and the sink. The structure of the optimal power allocation for a given placement of the nodes, then motivates us to formulate the problem of as-you-go placement of relays along a line of exponentially distributed length, and with the exponential path-loss model, so as to minimize a cost function that is additive over hops. The hop cost trades off a capacity limiting term, motivated from the optimal power allocation solution, against the cost of adding a relay node. We formulate the problem as a total cost Markov decision process, establish results for the value function, and provide insights into the placement policy and the performance of the deployed network via numerical exploration.

We consider single-hop topologies with saturated transmitting nodes, using carrier-sense multiple access with collision avoidance (CSMA/CA) for medium access, as standardized under the IEEE 802.11 distributed coordination function. We study systems where one or more backoff parameters of the CSMA/CA protocol (the initial backoff, the backoff multiplier, and the number of retries) are different from the standard. It is known that, for several classes of these protocol parameters, such systems exhibit a certain performance anomaly known as short term unfairness. We also find that the phenomenon of short term unfairness is observed in systems where the propagation delays among the participating nodes are not negligible compared with the duration of a backoff slot, even when the nodes use the default backoff parameters of the standard. It also turns out that the standard fixed point analysis technique (and its simple extensions) does not predict the system behavior well in such cases. For systems with large propagation delays, we observe that, as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what is predicted by the standard fixed point approximation. Our study of several example systems reveals some interesting connections between the protocol parameters, the number of nodes, the propagation delay, and the degree of unfairness. This paper reveals that the inability of the standard fixed point model to capture the performance in such cases is due to its state-independent attempt rate assumption. In this paper, we develop a novel approximate, but accurate, analysis that uses state-dependent attempt rates with a parsimonious state representation for computational tractability. The analytical method is also able to quantify the extent of short term unfairness in the system, something not possible with existing analytical techniques, and can, therefore, be used to tune the protocol parameters to achieve desired throughput and fairness objectives.

Motivated by the need for impromptu or as-you-go deployment of wireless sensor networks in some situations, we study the problem of optimal sequential deployment of wireless sensors and relays along a line (e.g., a forest trail) of unknown length. Starting from the sink node (e.g., a base station), a ”deployment agent„ walks along the line, stops at equally spaced points (”potential„ relay locations), placing relays at some of these points, until he reaches a location at which the source node (i.e., the sensor) needs to be placed, the objective being to create a multihop wireless relay network between the source and the sink. The deployment agent decides whether to place a relay or not at each of the potential locations, depending upon the link quality measurements to the previously placed relays. In this article, we seek to design efficient deployment algorithms for this class of problems, to achieve the objective of 2-connectivity in the deployed network. We ensure multi-connectivity by allowing each node to communicate with more than one neighbouring node. By proposing a network cost objective that is additive over the deployed relays, we formulate the relay placement problem as a Markov decision process. We provide structural results for the optimal policy and evaluate the performance of the optimal policy via numerical exploration. Computation of such an optimal deployment policy requires a statistical model for radio propagation; we extract this model from the raw data collected via measurements in a forestlike environment. To validate the results obtained from the numerical study, we provide an experimental study of algorithms for 2-connected network deployment.

We consider single-hop topologies with saturated transmitting nodes, using IEEE 802.11 DCF for medium access, where the propagation delays among the nodes are not negligible compared to the backoff slot duration. In this situation, we find that there is misaligned sensing of channel idleness, and also short-term unfairness in access to the medium. We demonstrate that existing analysis techniques (or, extensions thereof) are unable to account for these features, resulting in inaccurate prediction of the performance. Focusing on the case in which transmitters are equidistant from one another, and also each receiver is equidistant from all the transmitters, we provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Numerical experiments show, the approximate analysis predicts the system throughput to a relative accuracy of 2-3%, and collision probabilities to a relative accuracy of 3-8% compared to simulations. Interestingly, we observe that as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what one might intuitively expect. Finally, we also demonstrate how to optimize slot duration using the approximate analysis for maximizing system throughput.

We consider the Medium Access Control (MAC) problem in resource-constrained ad-hoc wireless networks typical of the Internet of Things (IoT). Due to the delay-sensitive nature of emerging IoT applications, there has been increasing interest in developing medium access control (TDMA) protocols in a slotted framework. The design of such MAC protocols must keep in mind the need for contention access at light traffic, and scheduled access in heavy traffic (leading to the long-standing interest in hybrid, adaptive MACs. In this paper, we consider the collocated node setting and require that each node acts autonomously only on the basis of locally available information. We propose EZMAC, a simple extension of ZMAC, and QZMAC which is designed using motivations from our extensions of certain delay-optimality and throughput-optimality theory from the literature. Practical implementation issues are outlined. Finally, we show, through simulations, that both protocols achieve mean delays much lower than those achieved by ZMAC and indeed, QZMAC provides mean delays very close to the minimum achievable in this setting, i.e., that of the centralized complete knowledge scheduler.

We consider an infrastructure-based wireless network comprising two types of nodes, namely, relays and sinks. The relay nodes are used to extend the network coverage by providing multi-hop paths to the sink nodes that are connected to a wireline infrastructure. Restricting to the one-dimensional case, our objective is to characterize the fraction of covered region for given densities of sink and relay nodes. We first compare and contrast our infrastructure-based model with the traditional setting, where a point is said to be covered if it simply lies within the range of some node. Then, drawing an analogy between the connected components of the network and the busy periods of an M / D /∞ queue, and using renewal theoretic arguments we obtain an explicit expression for the average vacancy (which is the complement of coverage). We also compute an upper bound for vacancy by introducing the notion of left-coverage (i.e., {coverage by a node from the left}). We prove a lower bound by coupling our model with an independent-disk model, where the sinks' coverage regions are independent and identically distributed. Through numerical work, we study the problem of minimizing network deployment cost subject to a constraint on the average vacancy. We also conduct simulations to understand the properties of a general notion of coverage, obtained by introducing hop-counts into the definition.

We are motivated by the need, in some applications, for impromptu or as-you-go deployment of wireless sensor networks. A person walks along a line, starting from a sink node (e.g., a base-station), and proceeds towards a source node (e.g., a sensor) which is at an a priori unknown location. At equally spaced locations, he makes link quality measurements to the previous relay, and deploys relays at some of these locations, with the aim to connect the source to the sink by a multihop wireless path. In this paper, we consider two approaches for impromptu deployment: (i) the deployment agent can only move forward (which we call a pure as-you-go approach), and (ii) the deployment agent can make measurements over several consecutive steps before selecting a placement location among them (the explore-forward approach). We consider a very light traffic regime, and formulate the problem as a Markov decision process, where the trade-off is among the power used by the nodes, the outage probabilities in the links, and the number of relays placed per unit distance. We obtain the structures of the optimal policies for the pure as-you-go approach as well as for the explore-forward approach. We also consider natural heuristic algorithms, for comparison. Numerical examples show that the explore-forward approach significantly outperforms the pure as-you-go approach in terms of network cost. Next, we propose two learning algorithms for the explore-forward approach, based on Stochastic Approximation, which asymptotically converge to the set of optimal policies, without using any knowledge of the radio propagation model. We demonstrate numerically that the learning algorithms can converge (as deployment progresses) to the set of optimal policies reasonably fast and, hence, can be practical model-free algorithms for deployment over large regions. Finally, we demonstrate the end-to-end traffic carrying capability of such networks via field deployment.

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.

In geographical forwarding of packets in a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has “custody” of a packet and has to choose one among a set of next-hop relay nodes to forward the packet toward the sink. Each relay is associated with a “reward” that summarizes the benefit of forwarding the packet through that relay. We seek a solution to this local problem, the idea being that such a solution, if adopted by every node, could provide a reasonable heuristic for the end-to-end forwarding problem. Toward this end, we propose a local relay selection problem consisting of a forwarding node and a collection of relay nodes, with the relays waking up sequentially at random times. At each relay wake-up instant, the forwarder can choose to probe a relay to learn its reward value, based on which the forwarder can then decide whether to stop (and forward its packet to the chosen relay) or to continue to wait for further relays to wake up. The forwarder’s objective is to select a relay so as to minimize a combination of waiting delay, reward, and probing cost. The local decision problem can be considered as a variant of the asset selling problem studied in the operations research literature. We formulate the local problem as a Markov decision process (MDP) and characterize the solution in terms of stopping sets and probing sets. We provide results illustrating the structure of the stopping sets, namely, the (lower bound) threshold and the stage independence properties. Regarding the probing sets, we make an interesting conjecture that these sets are characterized by upper bounds. Through simulation experiments, we provide valuable insights into the performance of the optimal local forwarding and its use as an end-to-end forwarding heuristic.

We are motivated by the problem of impromptu or as-you-go deployment of wireless sensor networks. As an application example, a person, starting from a sink node, walks along a forest trail, makes link quality measurements (with the previously placed nodes) at equally spaced locations, and deploys relays at some of these locations, so as to connect a sensor placed at some a priori unknown point on the trail with the sink node. In this paper, we report our experimental experiences with some as-you-go deployment algorithms. Two algorithms are based on Markov decision process (MDP) formulations, these require a radio propagation model. We also study purely measurement based strategies: one heuristic that is motivated by our MDP formulations, one asymptotically optimal learning algorithm, and one inspired by a popular heuristic. We extract a statistical model of the propagation along a forest trail from raw measurement data, implement the algorithms experimentally in the forest, and compare them. The results provide useful insights regarding the choice of the deployment algorithm and its parameters, and also demonstrate the necessity of a proper theoretical formulation.

We consider a setting in which a single item of content is disseminated in a population of mobile nodes by opportunistic copying when pairs of nodes come in radio contact. The nodes in the population may either be interested in receiving the content (referred to as destinations) or not yet interested in receiving the content (referred to as relays). We consider a model for the evolution of popularity, the process by which relays get converted into destinations. A key contribution of our work is to model and study the joint evolution of content popularity and its spread in the population. Copying the content to relay nodes is beneficial since they can help spread the content to destinations, and could themselves be converted into destinations. We derive a fluid limit for the joint evolution model and obtain optimal policies for copying to relay nodes in order to deliver content to a desired fraction of destinations, while limiting the fraction of relay nodes that get the content but never turn into destinations. We prove that a time-threshold policy is optimal for controlling the copying to relays, i.e., there is an optimal time-threshold up to which all opportunities for copying to relays are exploited, and after which relays are not copied to. We then utilize simulations and numerical evaluations to provide insights into the effects of various system parameters on the optimally controlled co-evolution model.

Social networking sites pervade the World Wide Web and have millions of users worldwide. This provides ample opportunity for brands and organisations to reach out to a large and diverse audience. They do so by creating content and spreading it across the social network. Most popular social networks follow a timeline based homepage to display such content to the end users. Content once posted on the timeline, remains visible for a limited time, determined by the rate of content generation in the network. There are various ways by which brands can become more visible on the timeline of their followers, for instance by retransmitting/advertising their content from time to time. Hence, with multiple content creators in the network, there is a competition over a user's timeline, which we analyse in this paper. We first characterise the occupancy distribution of a given user's timeline and then use queueing techniques to analyse the period of time a content is present on a given timeline. We then study the competition between different content creators and characterise the equilibrium rate of content generation. We finally provide some numerical results, which provide insights into the effect of various system parameters.

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. We seek to develop local forwarding algorithms that can be tuned so as to tradeoff the end-to-end delay against a total cost, such as the hop count or total energy. Our approach is to solve, at each forwarding node enroute to the sink, the local forwarding problem of minimizing one-hop waiting delay subject to a lower bound constraint on a suitable reward offered by the next-hop relay; the constraint serves to tune the tradeoff. The reward metric used for the local problem is based on the end-to-end total cost objective (for instance, when the total cost is hop count, we choose to use the progress toward sink made by a relay as the reward). The forwarding node, to begin with, is uncertain about the number of relays, their wake-up times, and the reward values, but knows the probability distributions of these quantities. At each relay wake-up instant, when a relay reveals its reward value, the forwarding node's problem is to forward the packet or to wait for further relays to wake-up. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate our local forwarding problem as a partially observable Markov decision process (POMDP) and obtain inner and outer bounds for the optimal policy. Motivated by the computational complexity involved in the policies derived out of these bounds, we formulate an alternate simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the inner and outer bound policies against the simple policy, and also against the optimal policy when the source knows the exact number of relays. Observing the good performance and the ease of implementation of the simple policy, we apply it to our motivating problem, i.e., local geographical routing of sporadic alarm packets in a large WSN. We compare the end-to-end performance (i.e., average total delay and average total cost) obtained by the simple policy, when used for local geographical forwarding, against that obtained by the globally optimal forwarding algorithm proposed by Kim et al.

We present a centralized integrated approach for: 1) enhancing the performance of an IEEE 802.11 infrastructure wireless local area network (WLAN), and 2) managing the access link that connects the WLAN to the Internet. Our approach, which is implemented on a standard Linux platform, and which we call ADvanced Wi-fi Internet Service EnhanceR (ADWISER), is an extension of our previous system WLAN Manager (WM). ADWISER addresses several infrastructure WLAN performance anomalies such as mixed-rate inefficiency, unfair medium sharing between simultaneous TCP uploads and downloads, and inefficient utilization of the Internet access bandwidth when Internet transfers compete with LAN-WLAN transfers, etc. The approach is via centralized queueing and scheduling, using a novel, configurable, cascaded packet queueing and scheduling architecture, with an adaptive service rate. In this paper, we describe the design of ADWISER and report results of extensive experimentation conducted on a hybrid testbed consisting of real end-systems and an emulated WLAN on Qualnet. We also present results from a physical testbed consisting of one access point (AP) and a few end-systems.

We study the tradeoff between delivery delay and energy consumption in a delay-tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the message and the number of destinations that have received the message. We formulate the problem as a controlled continuous-time Markov chain and derive the optimal closed-loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ordinary differential equation (ODE) (i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open-loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed-loop policy.

Mobile P2P technology provides a scalable approach for content delivery to a large number of users on their mobile devices. In this work, we study the dissemination of a single item of content (e.g., an item of news, a song or a video clip) among a population of mobile nodes. Each node in the population is either a destination (interested in the content) or a potential relay (not yet interested in the content). There is an interest evolution process by which nodes not yet interested in the content (i.e., relays) can become interested (i.e., become destinations) on learning about the popularity of the content (i.e., the number of already interested nodes). In our work, the interest in the content evolves under the linear threshold model. The content is copied between nodes when they make random contact. For this we employ a controlled epidemic spread model. We model the joint evolution of the copying process and the interest evolution process, and derive joint fluid limit ordinary differential equations. We then study the selection of parameters under the content provider's control, for the optimization of various objective functions that aim at maximizing content popularity and efficient content delivery.

We consider a dense, ad hoc wireless network, confined to a small region. The wireless network is operated as a single cell, i.e., only one successful transmission is supported at a time. Data packets are sent between source-destination pairs by multihop relaying. We assume that nodes self-organize into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention-based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first motivate that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc wireless network (described above) as a single cell, we study the hop length and power control that maximizes the transport capacity for a given network power constraint. More specifically, for a fading channel and for a fixed transmission time strategy (akin to the IEEE 802.11 TXOP), we find that there exists an intrinsic aggregate bit rate (\Theta_{opt} bits per second, depending on the contention mechanism and the channel fading characteristics) carried by the network, when operating at the optimal hop length and power control. The optimal transport capacity is of the form d_{opt}(\bar{P_t}) \times \Theta_{opt} with d_{opt} scaling as \bar{P_t}^{{1\over \eta}}, where \bar{P_t} is the available time average transmit power and \eta is the path loss exponent. Under certain conditions on the fading distribution, we then provide a simple characterization of the optimal operating point. Simulation results are provided comparing the performance of the optimal strategy derived here with some simple strategies for operating the network.

We study the question of determining locations of base stations (BSs) that may belong to the same or to competing service providers. We take into account the impact of these decisions on the behavior of intelligent mobile terminals that can connect to the base station that offers the best utility. The signal-to-interference-plus-noise ratio (SINR) is used as the quantity that determines the association. We first study the SINR association-game: We determine the cells corresponding to each base stations, i.e., the locations at which mobile terminals prefer to connect to a given base station than to others. We make some surprising observations: 1) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; 2) a cell corresponding to a BS may be the union of disconnected subcells. We then study the hierarchical equilibrium in the combined BS location and mobile association problem: We determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider hierarchical equilibria in two frequency systems with successive interference cancellation.

We consider a network in which several service providers offer wireless access to their respective subscribed customers through potentially multihop routes. If providers cooperate by jointly deploying and pooling their resources, such as spectrum and infrastructure (e.g., base stations) and agree to serve each others' customers, their aggregate payoffs, and individual shares, may substantially increase through opportunistic utilization of resources. The potential of such cooperation can, however, be realized only if each provider intelligently determines with whom it would cooperate, when it would cooperate, and how it would deploy and share its resources during such cooperation. Also, developing a rational basis for sharing the aggregate payoffs is imperative for the stability of the coalitions. We model such cooperation using the theory of transferable payoff coalitional games. We show that the optimum cooperation strategy, which involves the acquisition, deployment, and allocation of the channels and base stations (to customers), can be computed as the solution of a concave or an integer optimization. We next show that the grand coalition is stable in many different settings, i.e., if all providers cooperate, there is always an operating point that maximizes the providers' aggregate payoff, while offering each a share that removes any incentive to split from the coalition. The optimal cooperation strategy and the stabilizing payoff shares can be obtained in polynomial time by respectively solving the primals and the duals of the above optimizations, using distributed computations and limited exchange of confidential information among the providers. Numerical evaluations reveal that cooperation substantially enhances individual providers' payoffs under the optimal cooperation strategy and several different payoff sharing rules.

We consider a small extent sensor network for event detection, in which nodes periodically take samples and then contend over a random access network to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center for processing the measurements. The Bayesian setting, is assumed, that is, the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is network--oblivious and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is network--aware and processes measurements as they arrive, but in a time-causal order. In this case, the decision statistic depends on the network delays, whereas in the network--oblivious case, the decision statistic does not. This yields a Bayesian change-detection problem with a trade-off between the random network delay and the decision delay that is, a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network--oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network--aware case, the optimal stopping problem is analyzed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient decision statistic is the network state and the posterior probability of change having occurred, given the measurements received and the state of the network. The optimal regimes are studied using simulation.

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization . Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h . This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

There have been several studies on the performance of TCP controlled transfers over an infrastructure IEEE 802.11 WLAN, assuming perfect channel conditions. In this paper, we develop an analytical model for the throughput of TCP controlled file transfers over the IEEE 802.11 DCF with different packet error probabilities for the stations, accounting for the effect of packet drops on the TCP window. Our analysis proceeds by combining two models: one is an extension of the usual TCP-over-DCF model for an infrastructure WLAN, where the throughput of a station depends on the probability that the head-of-the-line packet at the Access Point belongs to that station; the second is a model for the TCP window process for connections with different drop probabilities. Iterative calculations between these models yields the head-of-the-line probabilities, and then, performance measures such as the throughputs and packet failure probabilities can be derived. We find that, due to MAC layer retransmissions, packet losses are rare even with high channel error probabilities and the stations obtain fair throughputs even when some of them have packet error probabilities as high as 0.1 or 0.2. For some restricted settings we are also able to model tail-drop loss at the AP. Although involving many approximations, the model captures the system behavior quite accurately, as compared with simulations.

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbor. Hence, in choosing a relay node, we consider the problem of minimizing delay subject to a constraint on the progress. By constraint relaxation, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a simplified model in which the times between the wake up instants of successive candidate relay nodes are assumed to be i.i.d. and exponentially distributed. The optimal policy (SF (Simplified Forward)) for this model is a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for a reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF) and First Forward (FF), and an end-to-end delay minimizing policy proposed by Kim et al. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

We study in this paper the question of determining locations of base stations (BSs) that may belong to the same or to competing service providers, taking into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the base station that offers the best utility. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e. the locations at which mobile terminals prefer to connect to a given base station than to other. The signal to interference and noise ratio (SINR) is used as the quantity that determines the association. We make some surprising observations: (i) displacing a base station a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction; (ii) A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the Stackelberg equilibrium in the combined BS location and mobile association problem: we determine where to locate the BSs so as to maximize the revenues obtained at the induced SINR mobile association game. We consider the cases of single frequency band and two frequency bands of operation. Finally, we also consider Stackelberg equilibria in two frequency systems with successive interference cancellation.

We consider a network in which several service providers offer wireless access service to their respective subscribed customers through potentially multi-hop routes. If providers cooperate, i.e., pool their resources, such as spectrum and base stations, and agree to serve each others' customers, their aggregate payoffs, and individual shares, can potentially substantially increase through efficient utilization of resources and statistical multiplexing. The potential of such cooperation can however be realized only if each provider intelligently determines who it would cooperate with, when it would cooperate, and how it would share its resources during such cooperation. Also, when the providers share their aggregate revenues, developing a rational basis for such sharing is imperative for the stability of the coalitions. We model such cooperation using transferable payoff coalitional game theory. We first consider the scenario that locations of the base stations and the channels that each provider can use have already been decided apriori. We show that the optimum cooperation strategy, which involves the allocations of the channels and the base stations to mobile customers, can be obtained as solutions of convex optimizations. We next show that the grand coalition is stable in this case, i.e. if all providers cooperate, there is always an operating point that maximizes the providers' aggregate payoff, while offering each such a share that removes any incentive to split from the coalition. Next, we show that when the providers can choose the locations of their base stations and decide which channels to acquire, the above results hold in important special cases. Finally, we examine cooperation when providers do not share their payoffs, but still share their resources so as to enhance individual payoffs. We show that the grand coalition continues to be stable.

We provide a simple and accurate analytical model for multi-cell IEEE 802.11 WLANs. Our model applies if the cell radius, R, is much smaller than the carrier sensing range, Rcs. We argue that, the condition Rcs>> R is likely to hold in a dense deployment of access points (APs). We develop a scalable cell level model for such WLANs with saturated nodes as well as for TCP-controlled long file downloads. The accuracy of our model is demonstrated by comparison with ns-2 simulations. Based on the insights provided by our analytical model, we propose a simple channel assignment algorithm which provides static assignments that are Nash equilibria in pure strategies for the objective of maximizing normalized network throughput, and requires only as many steps as there are channels. Furthermore, our channel assignment algorithm does not require any a priori knowledge of topology and can be implemented in a decentralized manner. In contrast to prior work, our approach to channel assignment is based on the throughput metric.

We consider the problem ofquickestdetectionofanintrusionusing a sensor network, keeping only a minimal number of sensorsactive. By using a minimal number of sensor devices, we ensure that the energy expenditure forsensing,computationandcommunicationis minimized (and the lifetime of the network is maximized). We model the intrusion detection (or change detection) problem as aMarkovdecisionprocess(MDP). Based on the theory of MDP, we develop the following closed loopsleep/wakescheduling algorithms: (1) optimal control of Mk+1, the number of sensors in the wake state in time slot k + 1, (2) optimal control of qk+1, the probability of a sensor in the wake state in time slot k + 1, and an open loopsleep/wakescheduling algorithm which (3) computes q, the optimal probability of a sensor in the wake state (which does not vary with time), based on the sensor observations obtained until time slot k. Our results show that an optimum closed loop control on Mk+1significantly decreases the cost compared to keeping any number of sensors active all the time. Also, among the three algorithms described, we observe that the total cost is minimum for the optimum control on Mk+1and is maximum for the optimum open loop control on q.

We consider the problem of several users transmitting packets to a base station, and study an optimal scheduling formulation involving three communication layers, namely, the medium access control, link, and physical layers. We assume Markov models for the packet arrival processes and the channel gain processes. Perfect channel state information is assumed to be available at the transmitter and the receiver. The transmissions are subject to a long-run average transmitter power constraint. The control problem is to assign power and rate dynamically as a function of the fading and the queue lengths so as to minimize a weighted sum of long run average packet transmission delays.

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/log n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

We consider a dense ad hoc wireless network comprising n nodes confined to a given two dimensional region of fixed area. For the Gupta-Kumar random traffic model and a realistic interference and path loss model (i.e., the channel power gains are bounded above, and are bounded below by a strictly positive number), we study the scaling of the aggregate end-to-end throughput with respect to the network average power constraint, P macr, and the number of nodes, n. The network power constraint P macr is related to the per node power constraint, P macr, as P macr = np. For large P, we show that the throughput saturates as Theta(log(P macr)), irrespective of the number of nodes in the network. For moderate P, which can accommodate spatial reuse to improve end-to-end throughput, we observe that the amount of spatial reuse feasible in the network is limited by the diameter of the network. In fact, we observe that the end-to-end path loss in the network and the amount of spatial reuse feasible in the network are inversely proportional. This puts a restriction on the gains achievable using the cooperative communication techniques studied in and, as these rely on direct long distance communication over the network.

We consider non-cooperative mobiles, each faced with the problem of which subset of WLANs access points (APs) to connect and multihome to, and how to split its traffic among them. Considering the many users regime, we obtain a potential game model and study its equilibrium. We obtain pricing for which the total throughput is maximized at equilibrium and study the convergence to equilibrium under various evolutionary dynamics. We also study the case where the Internet service provider (ISP) could charge prices greater than that of the cost price mechanism and show that even in this case multihoming is desirable.

In this paper, we consider the problem of association of wireless stations (STAs) with an access network served by a wireless local area network (WLAN) and a 3G cellular network. There is a set of WLAN Access Points (APs) and a set of 3G Base Stations (BSs) and a number of STAs each of which needs to be associated with one of the APs or one of the BSs. We concentrate on downlink bulk elastic transfers. Each association provides each ST with a certain transfer rate. We evaluate an association on the basis of the sum log utility of the transfer rates and seek the utility maximizing association. We also obtain the optimal time scheduling of service from a 3G BS to the associated STAs. We propose a fast iterative heuristic algorithm to compute an association. Numerical results show that our algorithm converges in a few steps yielding an association that is within 1% (in objective value) of the optimal (obtained through exhaustive search); in most cases the algorithm yields an optimal solution.

Segmentation of foreground and background has been an important research problem arising out of many applications including video surveillance. A method commonly used for segmentation is "background subtraction" or thresholding the difference between the estimated background image and current image. Adaptive Gaussian mixture based background modelling has been proposed by many researchers for increasing the robustness against environmental changes. However, all these methods, being computationally intensive, need to be optimized for efficient and real-time performance especially at a higher image resolution. In this paper, we propose an improved foreground/background segmentation method which uses experiential sampling technique to restrict the computational efforts in the region of interest. We exploit the fact that the region of interest in general is present only in a small part of the image, therefore, the attention should only be focused in those regions. The proposed method shows a significant gain in processing speed at the expense of minor loss in accuracy. We provide experimental results and detailed analysis to show the utility of our method

Abstract — In many cases, a mobile user has the option of connecting to one of several IEEE 802.11 access points (APs), each using an independent channel. User throughput in each AP is determined by the number of other users as well as the frame size and physical rate being used. We consider the scenario where users could multihome, i.e., split their traffic amongst all the available APs, based on the throughput they obtain and the price charged. Thus, they are involved in a non-cooperative game against each other. We convert the problem into a fluid model and show that under a pricing scheme, which we call the cost price mechanism, the total system throughput is maximized, i.e., the system suffers no loss of efficiency due to selfish dynamics. We also study the case where the Internet Service Provider (ISP) could charge prices greater than that of the cost price mechanism. We show that even in this case multihoming outperforms unihoming, both in terms of throughput as well as profit to the ISP. I.

In this paper we develop and numerically explore the modeling heuristic of using saturation attempt probabilities as state dependent attempt probabilities in an IEEE 802.11e infrastructure network carrying packet telephone calls and TCP controlled file downloads, using enhanced distributed channel access (EDCA). We build upon the fixed point analysis and performance insights. When there are a certain number of nodes of each class contending for the channel (i.e., have nonempty queues), then their attempt probabilities are taken to be those obtained from saturation analysis for that number of nodes. Then we model the system queue dynamics at the network nodes. With the proposed heuristic, the system evolution at channel slot boundaries becomes a Markov renewal process, and regenerative analysis yields the desired performance measures. The results obtained from this approach match well with ns2 simulations. We find that, with the default IEEE 802.11e EDCA parameters for AC 1 and AC 3, the voice call capacity decreases if even one file download is initiated by some station. Subsequently, reducing the voice calls increases the file download capacity almost linearly (by 1/3 Mbps per voice call for the 11 Mbps PHY)

We consider the classical problem of sequential detection of change in a distribution (from hypothesis 0 to hypothesis 1), where the fusion centre receives vectors of periodic measurements, with the measurements being i.i.d. over time and across the vector components, under each of the two hypotheses. In our problem, the sensor devices ("motes") that generate the measurements constitute an ad hoc wireless network. The motes contend using a random access protocol (such as CSMA/CA) to transmit their measurement packets to the fusion centre. The fusion centre waits for vectors of measurements to accumulate before taking decisions. We formulate the optimal detection problem, taking into account the network delay experienced by the vectors of measurements, and find that, under periodic sampling, the detection delay decouples into network delay and decision delay. We obtain a lower bound on the network delay, and propose a censoring scheme, where lagging sensors drop their delayed observations in order to mitigate network delay. We show that this scheme can achieve the lower bound. This approach is explored via simulation. We also use numerical evaluation and simulation to study issues such as: the optimal sampling rate for a given number of sensors, and the optimal number of sensors for a given measurement rate

In a dense multi-hop network of mobile nodes capable of applying adaptive power control, we consider the problem of finding the optimal hop distance that maximizes a certain throughput measure in bit-metres/sec, subject to average network power constraints. The mobility of nodes is restricted to a circular periphery area centered at the nominal location of nodes. We incorporate only randomly varying path-loss characteristics of channel gain due to the random motion of nodes, excluding any multi-path fading or shadowing effects. Computation of the throughput metric in such a scenario leads us to compute the probability density function of random distance between points in two circles. Using numerical analysis we discover that choosing the nearest node as next hop is not always optimal. Optimal throughput performance is also attained at non-trivial hop distances depending on the available average network power.

We consider a scenario where a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing the maximum value of the measurements and communicating it to an operator station. We view the problem as one of message passing distributed computation over a geometric random graph. The network is assumed to be synchronous; at each sampling instant each sensor measures a value, and then the sensors collaboratively compute and deliver the maximum of these values to the operator station. Computation algorithms differ in the messages they need to exchange, and our formulation focuses on the problem of scheduling of the message exchanges. We do not exploit techniques such as source compression, or block coding of the computations. For this problem, we study the computation time and energy expenditure for one time maximum computation, and also the pipeline throughput. We show that, for an optimal algorithm, the computation time, energy expenditure and the achievable rate of computation scale as /spl Theta/(/spl radic/ n/log n), /spl Theta/(n) and /spl Theta/(1/log n) asymptotically (in probability) as the number of sensors n/spl rarr//spl infin/. We also analyze the performance of three specific computational algorithms, namely, the tree algorithm, multihop transmission, and the ripple algorithm, and obtain scaling laws for the computation time and energy expenditure as n/spl rarr//spl infin/. Simulation results are provided to show that our analysis indeed captures the correct scaling; the simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized scheduler and hence our results can be viewed as providing bounds for the performance with a distributed scheduler.

We study a fixed point formalisation of the well known analysis of Bianchi. We provide a significant simplification and generalisation of the analysis. In this more general framework, the fixed point solution and performance measures resulting from it are studied. Uniqueness of the fixed point is established. Simple and general throughput formulas are provided. It is shown that the throughput of any flow will be bounded by the one with the smallest transmission rate. The aggregate throughput is bounded by the reciprocal of the harmonic mean of the transmission rates. In an asymptotic regime with a large number of nodes, explicit formulas for the collision probability, the aggregate attempt rate and the aggregate throughput are provided. The results from the analysis are compared with ns2 simulations, and also with an exact Markov model of the back-off process. It is shown how the saturated network analysis can be used to obtain TCP transfer throughputs in some cases.

We consider an optimal power and rate scheduling problem for a multiaccess fading wireless channel with the objective of minimising a weighted sum of mean packet transmission delay subject to a peak power constraint. The base station acts as a controller which, depending upon the buffer lengths and the channel state of each user, allocates transmission rate and power to individual users. We assume perfect channel state information at the transmitter and the receiver. We also assume a Markov model for the fading and packet arrival processes. The policy obtained represents a form of indexability

We consider the vector fixed point equations arising out of the analysis of the saturation throughput of a single cell IEEE 802.11e wireless local area network with nodes that have different back-off parameters, including different Arbitration InterFrame Space (AIFS) values. We consider balanced and unbalanced solutions of the fixed point equations arising in homogeneous and nonhomogeneous networks. We are concerned, in particular, with (i) whether the fixed point is balanced within a class, and (ii) whether the fixed point is unique. Our simulations show that when multiple unbalanced fixed points exist in a homogeneous system then the time behaviour of the system demonstrates severe short term unfairness (or multistability). Implications for the use of the fixed point formulation for performance analysis are also discussed. We provide a condition for the fixed point solution to be balanced within a class, and also a condition for uniqueness. We then provide an extension of our general fixed point analysis to capture AIFS based differentiation; again a condition for uniqueness is established. An asymptotic analysis of the fixed point is provided for the case in which packets are never abandoned, and the number of nodes goes to ∞. Finally the fixed point equations are used to obtain insights into the throughput differentiation provided by different initial back-offs, persistence factors, and AIFS, for finite number of nodes, and for differentiation parameter values similar to those in the standard.

In the recent years, IEEE 802.11 wireless local area networks (WLANS) have increasingly been deployed in a variety of situations, such as homes, business enterprises, academic campuses, and public places such as airports, hotels, and shopping centers. It has therefore become very important to understand the performance of such networks as well the effective network design, deployment and management. In this paper, our concern is mainly with the analytical performance evaluation of WLANs. We consider the aspect of network optimisation and discuss the saturation throughput analysis of single cell WLANs. We also have shown that the fixed point equation can be established using a renewal reward argument. For the case in which the mean back-off grows multiplicatively with collisions, we establish a sufficient condition for a system to have a unique fixed point.

IEEE 802.11 wireless local area networks that span large buildings or campuses must comprise multiple cells, several of which must necessarily be cochannel cells. It can be shown that in such multicell networks, typically, the radio ranges of cochannel cells overlap. The paper studies the saturation throughput performance of two cochannel cells with critical overlap, i.e., their interference ranges completely overlap but no node in either cell can decode any transmissions from the other cell. We identify that the difference between the two MAC parameters, EIFS (extended interframe space) and DIFS (DCF interframe space) is a key issue and incorporate this difference as a parameter into an analytical model. The model yields a fixed point equation that yields an approximation to the saturation throughputs of the two cells. The results from the analysis are validated against ns-2 simulations. We find that with EIFS>DIFS there is substantial temporal unfairness in the channel access between the two cells, but, because of fewer collisions, the critical overlap configuration has higher per cell throughput than if the cells' decoding ranges overlapped.

We consider a modification of TCP congestion control in which the congestion window is adapted to explicit bottleneck rate feedback; we call this RATCP (Rate Adaptive TCP). Our goal in this paper is to study and compare the performance of RATCP and TCP in various network scenarios with a view to understanding the possibilities and limits of providing better feedback to TCP than just implicit feedback via packet loss. To understand the dynamics of rate feedback and window control, we develop and analyze a model for a long-lived RATCP (and TCP) session that gets a time-varying rate on a bottleneck link. We also conduct experiments on a Linux based test-bed to study issues such as fairness, random losses, and randomly arriving short file transfers. We find that the analysis matches well with the results from the test-bed. For large file transfers, under low background load, ideal fair rate feedback improves the performance of TCP by 15%-20%. For small randomly arriving file transfers, though RATCP performs only slightly better than TCP it reduces losses and variability of throughputs across sessions. RATCP distinguishes between congestion and corruption losses, and ensures fairness for sessions with different round trip times sharing the bottleneck link. We believe that rate feedback mechanisms can be implemented using distributed flow control and recently proposed REM in which case, ECN bit itself can be used to provide the rate feedback.

We explore the possibility of using the well known processor sharing (PS) model for predicting the throughput performance of TCP controlled HTTP-like transfers on a single bottleneck link. We compare two commonly used-performance measures for average session throughput. For the PS model we derive bounds for one of these. We then compute these measures for a PS queue and compare them with average session throughputs on a single bottleneck link carrying TCP controlled data traffic. Analysis and simulations are used to obtain these results. We find that for file size distributions with a finite second moment, the PS model predicts TCP throughputs quite well. For the Pareto file size distribution, however, the PS model overestimates the session throughputs, the error getting worse as the Pareto tail gets thicker. It is also seen that the PS model breaks down as the link propagation delay increases.

The work in this paper is motivated by the idea of using randomly deployed, ad hoc wireless networks of miniature smart sensors to serve as distributed instrumentation. We argue that in such applications it is important for the sensors to self-organise in a way that optimizes network throughput. We then identify and discuss two main problems of optimal self-organisation: (i) building an optimal topology, and (ii) tuning network access parameters such as the transmission attempt rate. We consider a simple random access model for sensor networks and formulate these problems as optimisation problems. We then present centralized as well as distributed algorithms for solving them. Results show that the performance improvement is substantial and implementation of such optimal self-organisation techniques may be worth the additional complexity.

We consider the problem of on-line routing of bandwidth-guaranteed virtual paths. The basic idea is to route virtual paths such that enough spare capacity is left for accommodating weighted additional demands simultaneously between all other source-destination pairs. The problem formulation results in an integer linear program (ILP), the solution of which gives the optimal routing. However solving the ILP is NP-hard and so we resort to heuristics. We assign weights to the links in the network and then use shortest path routing. The novel aspect of the weight assignment is that the weights take into account the residual link capacities, as well as the number of source-destination pairs that could potentially use the link. Simulations show that the proposed algorithm performs better than existing algorithms in the literature (e.g. MIRA) for a variety of network topologies and traffic scenarios.

It is well known that the phenomenon of head-of-the-line (HOL) blocking limits the maximum achievable throughput of a pure input queuing cell switch. At each input, if instead of one queue for all the outputs, one queue for each output is used, and then 100% throughput can be achieved. This type of queuing, known as virtual output queuing (VOQ), removes the HOL blocking problem, but, in order to achieve 100% throughput, requires a scheduling algorithm to determine at each slot which input cells should be matched to their outputs. As the port speed is increased, the matching between inputs and outputs of the switch has to be found in a smaller time. Hence the speed of the scheduler has to be increased, which may not be possible owing to restrictions imposed by the hardware. We study a solution of this problem by the simple technique of skipping. In skipping, a new matching is found every k (> 1) slots instead of every slot. The effectiveness of skipping is shown using various traffic models.

An optimal power and rate scheduling problem for a single user transmitting to a base station on a fading wireless link with the objective of minimizing the mean delay subject to an average power constraint is considered. The base station acts as a controller which, depending upon the transmitter buffer lengths and the signal power to interference ratio (SIR) on the uplink pilot channel, allocates transmission rate and power to the user. We provide structural results for an average cost optimal stationary policy under a long run average transmitter power constraint. We obtain a closed form expression relating the optimal policy when the SIR is the best, to the optimal policy for any other SIR value. We also obtain lower and upper bounds for the optimal policy.

An Internet link carrying http-like traffic, i.e., transfer of finite volume files starting at random time instants is considered. These file transfers are controlled by an adaptive window protocol (AWP); an example of such a protocol is TCP. We provide an analysis for the auto-covariance function of the AWP controlled traffic into the link's buffer; this traffic, in general, is not an on-off process. The analysis establishes that, for Pareto distributed file sizes with infinite second moment, the traffic into the link buffer is long range dependent (LRD). We also develop an analysis for obtaining the stationary distribution of the link buffer occupancy under an AWP controlled transfer of files sampled from some distribution. The analysis provides a necessary and a sufficient condition for the finiteness of the mean link buffer content; these conditions have explicit dependence on the AWP used and the file size distribution. This establishes the sensitivity of the buffer occupancy process to the file size distribution. Combining the results from the above analyses, we provide an example in which the closed loop control of an AWP results in finite mean link buffer occupancy even though the file sizes are Pareto distributed (with infinite second moment), and the traffic into the link buffer is long range dependent. The significance of this work is threefold: (i) it provides a framework for analysing various processes related to the link buffer under AWP controlled transfer of files with a general file size distribution; (ii) it indicates that the buffer behaviour in the Internet may not be as poor as predicted from an open loop analysis of a queue fed with LRD traffic; and (iii) it shows that the buffer behaviour (and hence the throughput performance for finite buffers) is sensitive to the distribution of file sizes.

In this paper, we investigate the problem of providing worst-case end-to-end delay guarantees to a token bucket constrained flow traversing a series of N packet schedulers. We consider a network of routers that support the guaranteed service class of the IETF Integrated Services (IntServ) Working Group; this service class is proposed to provide quality of service (QoS) in the Internet. Under this framework, a worst-case end-to-end delay bound to a flow is provided by allocating a rate at each network element on the path of the flow. We associate a cost with allocating a rate at each link. The cost is assumed to be a convex and non-decreasing function of rate. We investigate the problem of obtaining an optimal rate allocation for a flow that minimizes the total cost subject to the delay requirement and the available link capacity constraints. Allocating an identical rate at each link on the path of a flow is a widely used approach under the guaranteed service framework. We investigate the optimality of this approach and show that under certain conditions, it need not be optimal. Moreover, we investigate the optimal solution to the total cost minimization problem and give scenarios in which we can explicitly obtain the optimal solution. Based on these results, we present an algorithm for optimal rate allocation that is based on multiple rates. However, with blocking probability as the performance criterion, we find through simulations, that the optimal rate allocation algorithm is only marginally better for connections with longer path lengths at the expense of those with shorter path lengths. We also observe that the performances of both the algorithms are very close and so, in practice, the simpler identical rate algorithm may be sufficient.

This paper is about analytical models for calculating the average bandwidth shares obtained by TCP controlled finite file transfers that arrive randomly and share a single (bottleneck) link. Owing to the complex nature of the TCP congestion control algorithm, a single model does not work well for all combinations of network parameters (i.e., mean file size, link capacity, and propagation delay). We propose two models, develop their analyses, and identify the regions of their applicability. One model is obtained from a detailed analysis of TCP's AIMD adaptive window mechanism; the analysis accounts for session arrivals and departures, and finite link buffers. It is essentially a processor sharing (PS) model with time varying service rate; hence we call it TCP-PS. The other model is a simple modification of the PS model that accounts for large propagation delays; we call this model rate limited-PS (RL-PS). The TCP-PS model analysis accommodates a general file size distribution by approximating it with a mixture of exponentials. The RL-PS model can be used for general file size distributions. We show that the TCP-PS model converges to the standard PS model as the propagation delay approaches zero. We also observe that the PS model provides very poor estimates of throughput unless the propagation delay is very small. We observe that the key parameters affecting the throughput are the bandwidth delay product (BDP), file size distribution, the link buffer and the traffic intensity. Several numerical comparisons between analytical and simulation results are provided. We observe that the TCP-PS model is accurate when the BDP is small compared to the mean file size, and the RL-PS model works well when the BDP is large compared to the mean file size.

We consider an optimal power and rate scheduling problem for a single user transmitting to a base station on a fading wireless link with the objective of providing transmission delay guarantees. The base station acts as a controller which, depending upon the transmitter buffer lengths and the signal power to interference ratio (SIR) on the uplink pilot channel, allocates transmission rate and power to the user. We provide structural results for an average cost optimal policy under a long run average transmitter power constraint. We obtain a closed form expression relating the optimal policy when the SIR is the best, to the optimal policy for any other SIR value.

The general problem we consider is the analysis of a model in which there are several routes in a network, on each route elastic flows arrive randomly according to some arrival process, and each flow transfers a finite volume of data sampled from some distribution. We are interested in computing a measure of average flow throughput on each route, for a given bandwidth sharing mechanism. Such models arise in problems of network dimensioning and traffic engineering. In this paper, we assume Poisson arrivals of file transfer requests on each route, the transfer volumes are fluid and arbitrarily distributed. At each instant the network shares the bandwidth among the ongoing flows according to the max-min fair bandwidth sharing mechanism, ie, instantaneous max-min fair (IMMF) sharing. The measure of performance we consider is the time average bandwidth obtained by flows on each route. We propose a heuristic algorithm for obtaining an approximation for this performance measure for arbitrary routes in an arbitrary network topology. Simulations with various network topologies are used to evaluate the proposal. In spite of its simplicity, we find that the approximation works quite well in a variety or topologies that we have studied.

We develop a new class of asynchronous distributed algorithms for the explicit rate control of elastic sessions in an integrated packet network. Sessions can request for minimum guaranteed rate allocations (e.g., minimum cell rates in the ATM context), and, under this constraint, we seek to allocate the max-min fair rates to the sessions. We capture the integrated network context by permitting the link bandwidths available to elastic sessions to be stochastically time varying. The available capacity of each link is viewed as some statistic of this stochastic process [e.g., a fraction of the mean, or a large deviations-based equivalent service capacity (ESC)]. The ESC is obtained so as to satisfy an overflow probability constraint on the buffer length. For fixed available capacity at each link, we show that the vector of max-min fair rates can be computed from the root of a certain vector equation. A distributed asynchronous stochastic approximation technique is then used to develop a provably convergent distributed algorithm for obtaining the root of the equation, even when the link flows and the available capacities are obtained from on-line measurements. The switch algorithm does not require per connection monitoring, nor does it require per connection marking of control packets. A virtual buffer based approach for on-line estimation of the ESC is utilized. We also propose techniques for handling large variations in the available capacity owing to the arrivals or departures of CBR/VBR sessions. Finally, simulation results are provided to demonstrate the performance of this class of algorithms in the local and wide area network context.

Motivated by TCP over end-to-end ABR, we study the performance of adaptive window congestion control, when it operates over an explicit feedback rate-control mechanism, in a situation in which the bandwidth available to the elastic traffic is stochastically time varying. It is assumed that the sender and receiver of the adaptive window protocol are colocated with the rate-control endpoints. The objective of the study is to understand if the interaction of the rate-control loop and the window-control loop is beneficial for end-to-end throughput, and how the parameters of the problem (propagation delay, bottleneck buffers, and rate of variation of the available bottleneck bandwidth) affect the performance. The available bottleneck bandwidth is modeled as a two-state Markov chain. We develop an analysis that explicitly models the bottleneck buffers, the delayed explicit rate feedback, and TCP's adaptive window mechanism. The analysis, however, applies only when the variations in the available bandwidth occur over periods larger than the round-trip delay. For fast variations of the bottleneck bandwidth, we provide results from a simulation on a TCP testbed that uses Linux TCP code, and a simulation/emulation of the network model inside the Linux kernel. We find that, over end-to-end ABR, the performance of TCP improves significantly if the network bottleneck bandwidth variations are slow as compared to the round-trip propagation delay. Further, we find that TCP over ABR is relatively insensitive to bottleneck buffer size. These results are for a short-term average link capacity feedback at the ABR level (INSTCAP). We use the testbed to study EFFCAP feedback, which is motivated by the notion of the effective capacity of the bottleneck link. We find that EFFCAP feedback is adaptive to the rate of bandwidth variations at the bottleneck link, and thus yields good performance (as compared to INSTCAP) over a wide range of the rate of bottleneck bandwidth variation. Finally, we study if TCP over ABR, with EFFCAP feedback, provides throughput fairness even if the connections have different round-trip propagation delays.

Most on-line (i.e., not stored) variable bit rate sources would find it difficult to a priori declare the traffic parameters required by a connection admission control strategy. There is thus the problem of measurement-based on-line estimation of source parameters. In this paper we address the problem of selection of source parameters based on minimising a buffer-bandwidth cost function in the network, for a specified delay QoS violation probability. We consider the shaping delay plus first-hop multiplexing delay; this is adequate, for example, for n statistically identical packet voice sources being multiplexed at a PBX, or in approaches where the end-to-end delay bound is broken into per-hop delay bounds. Our approach yields a leaky bucket rate parameter /spl rho//sup */, and the sum of the shaper buffer and leaky bucket depth (B/sub s/+/spl sigma/). We show that, for a fluid source model, for a linear buffer-bandwidth cost function, and for lossless multiplexing, a sustainable rate parameter of /spl rho//sup */ and burst parameter of 0 yields the minimum cost. We propose and study a stochastic approximation algorithm for on-line estimation of /spl rho//sup */. We then use buffer-bandwidth cost considerations to arrive at an optimal leaky bucket depth /spl sigma//sup */>0 for lossy multiplexing of several statistically identical sources. The computation of /spl sigma//sup */ must be done at the network node. We show, by an example, the improvement in cost that is possible by lossy multiplexing and a positive /spl sigma//sup */.

The available bit rate (ABR) sessions in an ATM network share the bandwidth left over after guaranteeing service to constant bit rate (CBR) and variable bit rate (VBR) traffic. Hence the bandwidth available to ABR sessions is randomly varying. This bandwidth must be shared by the sessions in a max-min fair fashion. Our point of departure in this paper is to formulate the problem of determining the max-min fair session rates as the problem of finding the root of a certain nonlinear vector equation; the same formulation also arises with our notion of max-min fairness with positive minimum cell rates (MCRs). This formulation allows us to use a stochastic approximation algorithm for online distributed computation of the max-min fair rates. We use the well known ordinary differential equation technique to prove convergence of the algorithm in the synchronous update case. We provide simulation results using the NIST simulator to show that the algorithm is able to track the max-min fair rates for slowly varying random available link bandwidths.

We use a stochastic model to study the throughput performance of various transport control protocol (TCP) versions (Tahoe (including its older version that we call OldTahoe), Reno, and NewReno) in the presence of random losses on a wireless link in a local network. We model the cyclic evolution of TCP, each cycle starting at the epoch at which recovery starts from the losses in the previous cycle. TCP throughput is computed as the reward rate in a certain Markov renewal-reward process. Our model allows us to study the performance implications of various protocol features, such as fast retransmit and fast recovery. We show the impact of coarse timeouts. In the local network environment the key issue is to avoid a coarse timeout after a loss occurs. We show the effect of reducing the number of duplicate acknowledgements (ACKs) for triggering a fast retransmit. A large coarse timeout granularity seriously affects the performance of TCP, and the various protocol versions differ in their ability to avoid a coarse timeout when random loss occurs; we quantify these differences. We show that, for large packet-loss probabilities, TCP-Reno performs no better, or worse, than TCP-Tahoe. TCP-NewReno is a considerable improvement over TCP-Tahoe, and reducing the fast-retransmit threshold from three to one yields a large gain in throughput; this is similar to one of the modifications in the TCP-Vegas proposal. We explain some of these observations in terms of the variation of fast-recovery probabilities with packet-loss probability. The results of our analysis compare well with a simulation that uses actual TCP code.

Considers an N/spl times/N nonblocking, space division, input queuing ATM cell switch, and a class of Markovian models for cell arrivals on each of its inputs. The traffic at each input comprises geometrically distributed bursts of cells, each burst destined for a particular output. The inputs differ in the burstiness of the offered traffic, with burstiness being characterized in terms of the average burst length. We analyze burst delays where some inputs receive traffic with low burstiness and others receive traffic with higher burstiness. Three policies for head-of-the-line contention resolution are studied: two static priority policies [shorter-expected-burst-length-first (SEBF), longer-expected-burst-length-first (LEBF)] and random selection (RS). Direct queuing analysis is used to obtain approximations for asymptotic high and low priority mean burst delays with the priority policies. Simulation is used for obtaining mean burst delays for finite N and for the random selection policy. As the traffic burstiness increases, the asymptotic analysis can serve as a good approximation only for large switch sizes. Qualitative performance comparisons based on the asymptotic analysis are, however, found to continue to hold for finite switch sizes. It is found that the SEBF policy yields the best delay performance over a wide range of loads, while RS lies in between. SEBF drastically reduces the delay of the less bursty traffic while only slightly increasing the delay of the more bursty traffic. LEBF causes severe degradation in the delay of less bursty traffic, while only marginally improving the delays of the more bursty traffic. RS can be an adequate compromise if there is no prior knowledge of input traffic burstiness.

The cell loss priority (CLP) bit in the header of the ATM cell may be used either by the network to tag noncompliant cells, or by the application to declare two levels of quality-of-service (QoS) within the same virtual circuit (VC). We study the possibility of the use of this bit by the application alone. An application can offer two types of traffic streams to the network, namely, a precious traffic stream (with stringent QoS requirements, e.g., cell loss ratio (CLR) <10/sup -9/ and identified by the CLP bit=0) and a less precious stream (CLP=1 and less stringent QoS requirements, e.g., CLR <10/sup -4/). We study the performance of an ATM multiplexer with two traffic classes with different QoS requirements. The buffer priority schemes adopted are partial buffer sharing (PBS) and PBS+push-out (PO). We first obtain the engineering trade-off curves, between CLP=0 and CLP=1 traffic. To identify an operating point, we formulate a revenue optimization problem in which the constraints are the engineering trade-off curve and a simple model of the variation of CLP=1 demand with its price.

In this paper we consider an N x N non-blocking, space division ATM switch with input cell queueing. At each input, the cell arrival process comprises geometrically distributed bursts of consecutive cells for the various outputs. Motivated by the fact that some input links may be connected to metropolitan area networks, and others directly to B-ISDN terminals, we study the situation where there are two classes of inputs with different values of mean burst length. We show that when inputs contend for an output, giving priority to an input with smaller expected burst length yields a saturation throughput larger than if the reverse priority is given. Further, giving priority to less bursty traffic can give better throughput than if all the inputs were occupied by this less bursty traffic. We derive the asymptotic (as N --> infinity) saturation throughputs for each priority class.

The authors model a parallel processing system comprising several homogeneous computers interconnected by a communication network. Jobs arriving to this system have a linear fork-join structure. Each fork of the job gives rise to a random number of tasks that can be processed independently on any of the computers. Since exact analysis of fork-join models is known to be intractable, the authors resort to obtaining analytical bounds to the mean job response time of the fork-join job. For jobs with a single fork-join and, probabilistic allocation of tasks of the job to the N processors, they obtain upper and lower bounds to the mean job response time. Upper bounds are obtained using the concept of associated random variables and are found to be a good approximation to the mean job response time. A simple lower bound is obtained by neglecting queueing delays. They also find two lower bounds that include queueing delays. For multiple fork-join jobs, they study an approximation based on associated random variables. Finally, two versions of the join-the-shortest-queue (JSQ) allocation policy (i.e., JSQ by batch and JSQ by task) are studied and compared, via simulations and diffusion limits.>

A comparison is made of the end-to-end delay performance of two service disciplines that a terminal adaptor (TA) can use to multiplex the pipelined synchronous native protocol frames arriving over the low-speed lines. In one scheme, the TA pipelines one synchronous frame at a time, waiting, if it needs to, for the successive link-access protocol D-channel (LAPD) packets from this one synchronous frame to accumulate. In the other scheme, the TA interleaves the LAPD packets from various synchronous frames. Using an analytical model for the first scheme, it is concluded that if the trunk speed (TA-to-network switch) to line speed ratio is greater than or equal to four, then over the range of useful loading, interleaved pipelining yields smaller mean delays than noninterleaved pipelining. If the ratio is less than four, interleaving yields larger mean delays for negative protocols which require a buildout delay at the egress TA.>

A model comprising several servers, each equipped with its own queue and with possibly different service speeds, is considered. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. It is shown that if the arrival streams are all Poisson and all jobs have the same exponentially distributed service requirements, the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least-squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times if the service speeds are all equal. This result is used to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream when the load parameters are unknown. The algorithms utilize server idle-time measurements which are sent periodically to the central job scheduler. A model is developed for these measurements, and the result mentioned is used to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed.>

The author presents adaptive control techniques for controlling the flow of real-time jobs from the peripheral processors (PPs) to the central processor (CP) of a distributed system with a star topology. He considers two classes of flow control mechanisms: (1) proportional control, where a certain proportion of the load offered to each PP is sent to the CP, and (2) threshold control, where there is a maximum rate at which each PP can send jobs to the CP. The problem is to obtain good algorithms for dynamically adjusting the control level at each PP in order to prevent overload of the CP, when the load offered by the PPs is unknown and varying. The author formulates the problem approximately as a standard system control problem in which the system has unknown parameters that are subject to change. Using well-known techniques (e.g. naive-feedback-controller and stochastic approximation techniques), he derives adaptive controls for the system control problem. He demonstrates the efficacy of these controls in the original problem by using the control algorithms in simulations of a queuing model of the CP and the load controls.>

The authors formally state and discuss the response time minimization problem. They show the equivalence of this problem to a weighted least square load balancing problem. They also discuss the correct solution of these problems. Next they describe and analyze a class of server idle time measurements. Finally, a class of adaptive algorithms is presented, and their performance is studied via simulation experiments.>

Stochastic analyses of the Survivability of communication networks often include a simplifying assumption that failures of, or damages to, various components of the network are statistically independent. This assumption can be quite unrealistic and can lead one to conclusions that are grossly in error. Survivability analyses and syntheses of robust networks should incorporate dependencies introduced by single events that affect large geographical areas. In this paper, we construct a stochastic damage model, analyze it, and apply the results to the survivability analysis of some simple network topologies. We demonstrate how the results can differ significantly from those obtained when independence of damage is assumed. The damage model consists of a Poisson ensemble of events (damage centers) on the plane, of given intensity (level of attack), and a network resource is damaged, and hence dysfunctional, if it lies within a radius ρ (damage radius) of some damage-causing event. Statistical properties of the damage process are obtained (e.g., the covariance function, mean and variance of the damage extent on a line resulting from the Poisson ensemble) and used to evaluate dependence effects. The damage process on a line is shown to be an alternating renewal process corresponding to the busy/idle process of an appropriately definedM/G/\inftyqueue, and standardM/G//inftyand Type-II counter results can thus be exploited to obtain some desired quantities.