Increasing content consumption by users and the expectation of a better Internet experience requires Internet service providers (ISPs) to expand the capacity of the access network continually. The ISPs have been demanding the participation of the content providers (CPs) in sharing the cost of upgrading the infrastructure. From CPs’ perspective, investing in the ISP infrastructure, termed as public investment, seems rational as it will boost their profit. However, the CPs can alternatively invest in making content delivery more efficient, termed as private investment, as it also boosts their profit. Thus, in this work, we investigate this trade-off between public and private investment of the CPs for a net-neutral ISP. Specifically, we consider centralized decision and non-cooperative forms of interaction between CPs and an ISP and determine the optimum public and private investments of the CPs for each model. In the non-cooperative interaction, we find that at most one CP contributes to the public infrastructure, whereas all invest in their private infrastructure.

We present the first model for a polling system in which the waiting customers renege continuously while they are waiting in their respective queues. Specifically, we consider a single-server polling system of N queues with the server using a gated service policy. The customers that arrive between server arrival instants and are waiting in the queue renege continuously at a fixed rate. We develop an embedded Markov chain model for this system with embedding at the instants at which the server starts its visit to a queue. The state is expressed as an N-dimensional vector of the number in the queues at each node. The exact Markov chain is not amenable to closed form solutions and we present an approximate solution based on the time spent by the server outside the tagged node. This approximation is a vacation model based analysis where the time spent by the server at a tagged station is regarded as the visit time and the time spent by the polling server outside the tagged station is considered as a vacation. Two candidate models for obtaining this vacation distribution are presented. We also analyse certain performance metrics for the symmetric system and provide observations on stability of system and mean number served per cycle at each station under conditions of heavy traffic or large number of stations.

Coded delivery has been found to improve content delivery by reducing the data transmitted over a broadcast network. The existing works are mostly theoretical, and do not focus on building coded delivery systems for the wireless edge, especially the WiFi edge. In this paper, we first analyze the potential gains of coded delivery that employs index coding at the WiFi edge. This includes designing a system model and the algorithms therein to study the gains of coded delivery. We also compare the gains due to coding with the gains due to caching. The algorithms include segment coding algorithm at the WiFi AP and a cache replacement policy (LFU-Index) at the end user. The system model is then used as the basis to design and implement Wi-Cache, a coded delivery system at the WiFi edge. Coded delivery in Wi-Cache specifically focuses on improving HTTP based video streaming to WiFi clients. The decoding module at the end user for the coded delivery is implemented as a browser plugin that does not require device side configuration changes. We also present the effect of variable and fixed length video segment size on the perceived performance of video streaming when coded delivery is used.

Content delivery networks (CDNs) have been providing the key engineering and economic mediation between content providers (CPs) and Internet service providers (ISPs) in content delivery over the Internet. They significantly improve the quality of service experience for today’s Internet traffic. We model the CDN as a business-to-business platform that provides caching and other services in the Internet content delivery chain between the CPs and the ISPs. The CPs and ISPs that subscribe to the CDN receive a traffic boost relative to their base traffic and in return the CDN prescribes a subscription charge to the CPs, and to the ISPs. We assume that the CDN provides its service without price or quality differentiation between the CPs (or between the ISPs). In this setting we analyze the revenue maximizing prices of the CDN on the two sides of the platform, and its effect on the connection structure on the two sides. We first consider the oligopoly model, where we formulate a full information, leader-follower game. The CDN is the leader and sets the subscription prices for the CPs and the ISPs. The ISPs and CPs are the followers and they make the binary decision of subscribing to the CDN or not. We extend this model to a retail CP market, where the CDN determines the revenue maximizing price using a heuristic and the CPs make the subscription decision. Using extensive numerical analyses, we show that the CDN will always provide sufficient resources to the CPs and that the revenue maximizing price will essentially price out the CPs and ISPs that have a low monetization capability.

We analyze the effect of sponsored data when Internet service providers (ISPs) compete for subscribers and content providers (CPs) compete for a share of the bandwidth usage by customers. Our model is of a full information, leader-follower game. ISPs lead and set sponsorship prices. CPs then make the binary decision of sponsoring or not sponsoring their content on the ISPs. Lastly, based on both of these, users make a two-part decision-choose the ISP to subscribe to, and amount of data to consume from each CPs through the chosen ISP. User consumption is determined by a utility maximization framework, sponsorship decision is determined by a non-cooperative game between CPs, and ISPs set their prices to maximize their profit in response to prices set by competing ISP. We analyze the dynamics of the prices set by ISPs, the sponsorship decisions of CPs, the market structure therein, and surpluses of the ISPs, CPs, users. This is the first analysis of the effect sponsored data in the presence of ISP competition. We show that inter-ISP competition does not inhibit ISPs from extracting a significant fraction of CP surplus, leaving CPs no better off (and sometimes worse off) as compared to the scenario where data sponsoring is disallowed. Moreover, ISPs often have an incentive to significantly skew the CP marketplace in favor of the most profitable CP.

Caching content close to the end users, e.g., at cellular base stations (BSs), WiFi access points (APs), and end user devices is known to improve efficiency and effectiveness of content delivery. This motivates the development of caching-as-a-service where edge networks and devices provide storage capacity to content providers, and enable them to strategically populate these caches to improve user experience in the targeted network. In this paper, we describe Wi-Cache, a prototype for providing caching-as-a-service at the WiFi edge. Wi-Cache is an SDN (Software Defined Networking) based distributed content caching system at the WiFi edge that uses storage at the APs for caching content. Wi-Cache caches content on wireless APs and delivers them to mobile clients when they are requested. It allows content providers to have fine-grained control over the AP-caches and also execute efficient content placement and delivery algorithms at the WiFi edge using a set of APIs that are provided by Wi-Cache. We also show the effectiveness of the Wi-Cache system using an extensive set of experiments.

The Internet of symmetric traffic flows between networks and a hierarchical topology, has long given way to one with significantly asymmetric traffic flows and a flatter topology. The Internet topology of today may be characterized as having three key types of networks—content providers, user access providers, and transit providers. In this Internet, best-effort routing of centrally stored content using distributed protocols has been seen to be inadequate to provide a suitably reliable transport service with the requisite quality of service to the end user. Two important developments that mitigate this gap in the capability of the traditional Internet and the needs of modern content are (i) direct peering arrangements between content networks and ISPs, and (ii) widespread use of content distribution networks (CDNs), who also peer with ISPs. In this paper we first analyze the economics of such peering arrangements. Using microeconomic models from the industrial organization literature, we first develop the conditions for a content provider to connect directly to a service provider, possibly via a peering link. Further, when such a direct link is indeed sought, we analyze the quality of the link vis-a-vis the default option of using a transit service. We then extend our results to the case of CDN, and analyze the content provider market coverage by CDNs. Finally, we discuss the implications of these results on the objectives sought by net neutrality regimes.

Fragmentation of expensive resources, e.g., the spectrum for wireless services, between providers can introduce inefficiencies in resource utilization and worsen overall system performance. In such cases, resource pooling between independent service providers can be used to improve performance. However, for providers to agree to pool their resources, the arrangement has to be mutually beneficial. The traditional notion of resource pooling, which implies complete sharing, need not have this property. For example, under full pooling, one of the providers may be worse off and hence has no incentive to participate. In this paper, we propose partial resource sharing models as a generalization of full pooling, which can be configured to be beneficial to all participants. We formally define and analyze two partial sharing models between two service providers, each of which is an Erlang-B loss system with the blocking probabilities as the performance measure. We show that there always exist partial sharing configurations that are beneficial to both providers, irrespective of the load and the number of circuits of each of the providers. A key result is that the Pareto frontier has at least one of the providers sharing all its resources with the other. Furthermore, full pooling may not lie inside this Pareto set. The choice of the sharing configurations within the Pareto set is formalized based on the bargaining theory. Finally, large system approximations of the blocking probabilities in the quality-efficiency-driven regime are presented.

Many flavors of differential data pricing are being practiced in different telecom markets. One popular version is zero-rating, where customers do not pay for consuming a certain basket of “zero-rated” content. These zero-rated services are in turn sponsored by payments to the Internet service provider (ISP) by the corresponding content providers (CPs). In this paper, we provide an analytical treatment of a zero-rating platform, highlighting the effect of zero-rating on the structure of the CP market and also on the surplus of ISPs, CPs, and users. A leader-follower game is assumed with the ISP setting the prices for users (for non-sponsored data) and CPs (for sponsored data), CPs making a binary decision on sponsorship and users consuming content based on the resulting data charges. User consumption is determined by a utility maximization, the sponsorship decision is determined by a Nash equilibrium between the CPs, and the ISP sets prices to maximize its profit. Several scenarios mimicking real-life practices are analyzed. Our results indicate that zero-rating grants the ISP significant power to determine the mix of content consumption and the profitability of the CPs. Furthermore, the ISP can also take away a significant portion of the surplus in the system.

We describe the current version of Wi-Cache, a SDN framework for caching at the WiFi edge. Wi-Cache is motivated by the belief that edge caching technologies are needed to augment emerging network technologies to meet the increasing (volume, quality, and variety) demand for content, which is itself changing its characteristics significantly. Wi-Cache is being used to test new ideas for edge caching. Specifically, Wi-Cache is a framework for edge caching which allows caching and delivery of content on WiFi APs. Apart from a network induced handoff of clients, it allows communication between the APs for content delivery. We have also developed an API that is exposed for implementation of algorithms for content delivery and placement, and cache replacement.

We consider optimal distributed computation of a given function of distributed data. The input (data) nodes and the sink node that receives the function form a connected network that is described by an undirected weighted network graph. The algorithm to compute the given function is described by a weighted directed acyclic graph and is called the computation graph. An embedding defines the computation communication sequence that obtains the function at the sink. Two kinds of optimal embeddings are sought, the embedding that: 1) minimizes delay in obtaining function at sink, and 2) minimizes cost of one instance of computation of function. This abstraction is motivated by three applications - in-network computation over sensor networks, operator placement in distributed databases, and module placement in distributed computing. We first show that obtaining minimum-delay and minimum-cost embeddings are both NP-complete problems and that cost minimization is actually MAX SNP-hard. Next, we consider specific forms of the computation graph for which polynomial-time solutions are possible. When the computation graph is a tree, a polynomial-time algorithm to obtain the minimum-delay embedding is described. Next, for the case when the function is described by a layered graph, we describe an algorithm that obtains the minimum-cost embedding in polynomial time. This algorithm can also be used to obtain an approximation for delay minimization. We then consider bounded treewidth computation graphs and give an algorithm to obtain the minimum-cost embedding in polynomial time.

In-network function computation (INFC) is becoming an essential aspect of large database systems where the data is distributed over the network. Such situations arise often in resource constrained wireless sensor network making them a natural candidate for INFC. We study the problem of maximizing the rate of INFC in wireless networks. In this paper, we develop a functional flow model for INFC when the function computation sequence is represented by a directed acyclic graph. We propose a linear program formulation to maximize the rate of INFC over all possible embeddings. We also formulate a mixed integer linear program (MILP) for maximizing the rate of computation for a single embedding on a capacity constrained wireless network. The MILP for finding the single embedding that yields maximum rate turns out to be NP hard; we develop a heuristic to solve this problem by formulating a linear program. We provide numerical results to illustrate the performance of these formulations.

We consider in-network computation of MAX and the approximate histogram in an n-node structure-free random multihop wireless network. The key assumption that we make is that the nodes do not know their relative or absolute locations and that they do not have an identity. For the Aloha MAC protocol, we first describe a protocol in which the MAX value becomes available at the origin in O(√{n/logn}) slots (bit-periods) with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Ω(1/(logn)2). Finally, we show how the protocol for computation of MAX can be modified to achieve approximate computation of the histogram. The approximate histogram can be computed in O(n7/2(logn)1/2) bit-periods with high probability.

In a random key graph (RKG) of n nodes each node is randomly assigned a key ring of Kncryptographic keys from a pool of Pnkeys. Two nodes can communicate directly if they have at least one common key in their key rings. We assume that the n nodes are distributed uniformly in [0, l]2. In addition to the common key requirement, we require two nodes to also be within rnof each other to be able to have a direct edge. Thus we have a random graph in which the RKG is superposed on the familiar random geometric graph (RGG). For such a random graph, we obtain tight bounds on the relation between Kn, Pnand rnfor the graph to be asymptotically almost surely connected.

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., like sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. We then develop a fast combinatorial primal-dual algorithm to obtain near-optimal solutions to these linear programs. As a subroutine for this, we develop an algorithm for finding the minimum cost embedding of a tree in a network with any given set of link costs. We then briefly describe extensions of our techniques to the cases of multiple terminals wanting different functions, multiple computation schemas for a function, computation with a given desired precision, and to networks with energy constraints at nodes.

We consider in-network computation of an arbitrary function over an arbitrary communication network. We consider the same model as our earlier work in [1]. The given network consists of directed/undirected links with capacity constraints, some source nodes which generate data, and other intermediate forwarding nodes. An arbitrary function of this distributed data is to be computed at a terminal node. The structure of the function is described by a given computation schema represented by a directed tree. In our earlier work, we presented a linear program to define the maximum rate of computation, and then introduced a notion of flow-conservation suitable in this context so as to come up with a flow-conservation based linear program which can be solved in polynomial time. In this paper, we develop a combinatorial primal-dual algorithm to obtain (1-∈)-approximate solutions to these linear programs. As a part of this, we present an algorithm to find a minimum-cost embedding in a network of weighted links--which is of independent interest. We then describe application of our techniques to other practically interesting problems of multiple terminals wanting different functions, computation with a given desired precision, and to networks with energy constraints at nodes.

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We define a new notion of conservation of flow suitable in this setup and design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. Our approach introduces the network flow techniques to the distributed function computation setup where such a scope was hitherto unsuspected due to the lack of traditional conservation of flow.

There has been a considerable body of research devoted to the design and performance of PC based software routers running open source software. Most of the research on open software routers (OSRs) have focused on improving the performance of single PCs with a few proposals for a distributed design. Modern routers are equipped with enhanced functionality such as QoS features in addition to packet forwarding. However, providing enhanced functionality in distributed OSR architectures has largely remained unaddressed. A distributed design introduces challenges in its implementation due to looser coupling between different subsystems. WFQ is a widely used scheduler that enables QoS features in a router. The inherent centralized nature of the design of WFQ schedulers in most switches and routers creates several challenges when exported to distributed architectures. In this paper, we study the challenges of implementing WFQ in a distributed OSR, propose some novel techniques to address these challenges and compare the performance of our WFQ implementation in distributed OSR with that of a centralized WFQ scheme.

We propose a method to compute a probably approximately correct (PAC) normalized histogram of observations with a refresh rate of Θ(1) time units per histogram sample on a random geometric graph with noise-free links. The delay in computation is Θ(√n) time units. We further extend our approach to a network with noisy links. While the refresh rate remains Θ(1) time units per sample, the delay increases to Θ(√n log n). The number of transmissions in both cases is Θ(n) per histogram sample. The achieved Θ(1) refresh rate for PAC histogram computation is a significant improvement over the refresh rate of Θ(1/log n) for histogram computation in noiseless networks. We achieve this by operating in the supercritical thermodynamic regime where large pathways for communication build up, but the network may have more than one component. The largest component however will have an arbitrarily large fraction of nodes in order to enable approximate computation of the histogram to the desired level of accuracy. Operation in the supercritical thermodynamic regime also reduces energy consumption. A key step in the proof of our achievability result is the construction of a connected component having bounded degree and any desired fraction of nodes. This construction may also prove useful in other communication settings on the random geometric graph.

Pocket Switched Networks take advantage of social contacts to opportunistically create data paths over time. This work employs empirical traces to examine the effect of the human contact process on data delivery in such networks. The contact occurrence distribution is found to be highly uneven: contacts between a few node pairs occur too frequently, leading to inadequate mixing in the network, while the majority of contacts occur rarely, but are essential for global connectivity. This distribution of contacts leads to a significant variation in the fraction of node pairs that can be connected over time windows of similar duration. Good time windows tend to have a large clique of nodes that can all reach each other. It is shown that the clustering coefficient of the contact graph over a time window is a good predictor of achievable connectivity. We then examine all successful paths found by flooding and show that though delivery times vary widely, randomly sampling a small number of paths between each source and destination is sufficient to yield a delivery time distribution close to that of flooding over all paths. This result suggests that the rate at which the network can deliver data is remarkably robust to path failures.

In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e.g., Join-the-Shortest-Queue policy and variants thereof). Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it. An important example is in wireless spectrum sharing where clients try to share a set of frequency bands in a distributed manner.

We consider the problem of traffic management in small networks with both wireless and wired devices, connected to the Internet through a single gateway. Examples of such networks are small office networks or residential networks, where typically traffic management is limited to flow prioritization through port-based filtering.

We consider k-coverage of a line by a two-dimensional, non homogeneous Poisson-Boolean model. This has applications in sensor networks. We extend the analysis of [1] to the case for k > 1. The extension requires us to define a vector Markov process that tracks the k segments that have the longest residual coverage at a point. This process is used to determine the probability of a segment of the line being completely covered by k or more sensors. We illustrate the extension by considering the case of k = 2.

We analyze the statistical properties of the k-coverage of a point-target moving in a straight line in a nonuniform dynamic sensor field. Sensor locations form a spatial point process. The environmental variation is captured by making the sensor locations form a non homogeneous spatial Poisson process with a fixed, spatially varying density function. The sensing areas of the sensors are circles of i.i.d. radii. The availability of each node is modeled by an independent, {0, 1}- valued, continuous time Markov chain. This gives a Markov-non homogeneous Poisson-Boolean model for which we perform a coverage analysis. We first obtain k-coverage of the target at an arbitrary time instant. We then obtain k-coverage statistics of the target during the time interval [0, T]. We also provide an asymptotically tight, closed form approximation for the duration for which the target is not k-covered in [0, T]. Numerical results illustrate the analysis. The environmental variation can also be captured by modeling the density function as a spatial random process resulting in the point process being a two-dimensional Cox process. For this model, we discuss issues in the coverage analysis.

We analyze the statistical properties of the coverage of a one-dimensional path induced by a two-dimensional nonhomogeneous random sensor network. Sensor locations form a nonhomogeneous Poisson process and sensing area for the sensors are circles of random independent and identically distributed radii. We first characterize the coverage of a straight-line path by the nonhomogeneous one-dimensional Boolean model. We then obtain an equivalent M t /G t /∞, queue whose busy period statistics is the same as the coverage statistics of the line. We obtain k -coverage statistics for an arbitrary point and a segment on the x -axis. We provide upper and lower bounds on the probability of complete k -coverage of a segment. We illustrate all our results for the case of the sensor deployment having a “Laplacian” intensity function.

We consider in-network computation of MAX in a structure-free random multihop wireless network. Nodes do not know their relative or absolute locations and use the Aloha MAC protocol. For one-shot computation, we describe a protocol in which the MAX value becomes available at the origin in O(radicn/ log n) slots with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Omega(1/(log2n)).

We develop generalized method of moments estimators to estimate the parameters of a two-dimensional Boolean random field from measurements made on the coverage process induced on a straight line in the field. This is distinct from earlier studies e.g. P. Hall (1988), I. Molchanov and D. Stoyan (2004), where the parameters of a two-dimensional Boolean field are obtained from the coverage properties of a two-dimensional set. This problem has applications in radio-active field monitoring.

We consider distributed computation of functions of distributed data in random planar networks with noisy wireless links. We present a new algorithm for computation of the maximum value which is order optimal in the number of transmissions and computation time. We also adapt the histogram computation algorithm of Ying et al [1] to make the histogram computation time optimal.

In a sensor network, the points in the operational area that are suitably sensed are a two-dimensional spatial coverage process. For randomly deployed sensor networks, typically, the network coverage of two-dimensional areas is analyzed. However, in many sensor network applications, e.g., tracking of moving objects, the sensing process on paths, rather than in areas, is of interest. With such an application in mind, we analyze the coverage process induced on a one-dimensional path by a sensor network that is modeled as a two-dimensional Boolean model. In the analysis, the sensor locations form a spatial Poisson process of density \lambda and the sensing regions are circles of i.i.d. random radii. We first obtain a strong law for the fraction of a path that is k{\hbox{-}}{\rm sensed}, i.e., sensed by (\geq k) sensors. Asymptotic path-sensing results are obtained under the same limiting regimes as those required for asymptotic coverage by a two-dimensional Boolean model. Interestingly, the asymptotic fraction of the area that is 1-sensed is the same as the fraction of a path that is 1-sensed. For k = 1, we also obtain a central limit theorem that shows that the asymptotics converge at the rate of \Theta(\lambda^{1/2}) for k = 1. For finite networks, the expectation and variance of the fraction of the path that is k{\hbox{-}}{\rm sensed} is obtained. The asymptotics and the finite network results are then used to obtain the critical sensor density to k{\hbox{-}}{\rm sense} a fraction \alpha_{k} of an arbitrary path with very high probability is also obtained. Through simulations, we then analyze the robustness of the model when the sensor deployment is nonhomogeneous and when the paths are not rectilinear. Other path coverage measures like breach, support, "length to first sense,? and sensing continuity measures like holes and clumps are also characterized. Finally, we discuss some generalizations of the results like characterization of the coverage process of m{\hbox{-}}{\rm dimensional} "straight line paths? by n{\hbox{-}}{\rm dimensional}, n > m, sensor networks.

We analyze the statistical properties of the coverage of a one-dimensional path induced by a two dimensional non homogeneous random sensor network. Sensor locations form a non homogeneous Poisson process and coverage area of each sensor is a circle of random i.i.d. radius. We first describe the one-dimensional coverage process on the line and describe an equivalent time-inhomogeneous Mt/Gt/infin queue whose busy period statistics will be equal to the coverage statistics of the line. We also obtain properties like conditional forward and backward hole-lengths. Additional results for the case of fixed coverage radius are obtained. We also obtain some numerical results for a deployment that has a 'Laplacian' intensity function.

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

We propose and analyze a distributed control law that maintains the prescribed local properties of a wireless ad hoc network in the presence of node mobility, MAC layer power control and link fades. The control law uses a simple and intuitive power adaptation mechanism. We consider as an example the topology requirement of maintaining the out degrees of each node at prescribed values and keeping the in degree close to the out degree. The topology objective is achieved by adapting the transmission power based only on local information. This power adaptation algorithm is analyzed using the o.d.e. approach to stochastic approximation. Simulation results verify the analysis and demonstrate its effectiveness. We also study the ability of the proposed objective to maintain connectivity. Although many heuristics are described in the literature to maintain local topological properties, the algorithm proposed in this paper is the first one that has proven convergence properties.

Suppose that V = {v/sub 1/, v/sub 2/, ...v/sub n/} is a set of nodes randomly (uniformly) distributed in the d dimensional cube [0, x/sub 0/]/sup d/, and W = {w(i, j) > 0 : 1 /spl les/ i, j /spl les/ n} is a set of numbers chosen so that w(i, j) = w(j, i) = w(j, i). Construct a graph G/sub n,d,W/ whose vertex set is V, and whose edge set consists of all pairs {u/sub i/, u/sub j/} with /spl par/ u/sub i/ - u/sub j/ /spl par/ /spl les/ w(i, j). In the wireless network context, the set V is a set of labeled nodes in the network and W represents the maximum distances between the node pairs for them to be connected. We essentially address the following question: "if G is a graph with vertex set V, what is the probability that G appears as a subgraph in G/sub n,d,W/?" Our main contribution is a closed form expression for this probability under the l/sub /spl infin// norm for any dimension d and a suitably defined probability density function. As a corollary to the above answer, we also answer the question, "what is the probability that Q/sub n,d,W/ is connected?".

We consider the clustering properties of one-dimensional sensor networks where the nodes are randomly deployed. Unlike most other work on randomly deployed networks, ours assumes that the node locations are drawn from a non uniform distribution. Specifically, we consider an exponential distribution. We first obtain the probability that there exists a path between two labeled nodes in a randomly deployed network and obtain the limiting behavior of this probability. The probability mass function (pmf) for the number of components in the network is then obtained. We show that the number of components in the network converges in distribution. We also derive the probabilities for different locations of the components. We then obtain the probability for the existence of a k-sized component and components of size /spl ges/k. Asymptotics in the number of nodes in the network are computed for these probabilities. An interesting result is that, as the number of nodes, n, in the network tends to infinity, a giant component, in which a specific fraction, /spl alpha/, of the nodes form a component, almost surely does not exist for any 0n/sub 0/, the network almost surely does not have a giant component.

DiffServ is an attractive candidate for providing relative QoS in the Internet. This is also easily amenable to simple and effective pricing mechanisms. By pricing access to a relative QoS, we can model a DiffServ node as a "join minimum cost queue" in which an arriving customer (packet or connection) determines the relative cost as a function of the congestion in the different queues and their access prices and decides to take service from that queue for which the cost is minimum. The Paris Metro pricing system and its work conserving variant called Tirupati pricing are analyzed in the presence of multiclass traffic and for static pricing. Two of the more interesting observations are that the disutility and revenue rate are not monotonic or convex functions of price and the revenue rate is very sensitive to the behavior of the delay sensitive class.

We consider a system of identical parallel queues served by a single server and distinguished only by the price charged at entry. A Poisson stream of customers joins the queue by a greedy policy that minimizes a 'disutility' that combines price and congestion. A special case of linear disutility is analyzed for which it is shown that the individually optimal greedy queue join policy is nearly socially optimal. For this queueing system, a Markov decision theoretic framework is formulated for dynamic pricing in the general case. This queueing system has application in the pricing of Internet services.

We consider crossbar switches for switching variable length packets. Analysis of such switches is important in the context of IP switches where the packet interarrival times and packet lengths are drawn from continuous distributions. Assuming a single stage M/spl times/N switch we obtain a very general throughput delay model for Poisson packet arrivals and exponential service times. We then analyze an M/spl times/N switch for self similar packet arrivals and exponential packet lengths. An MMPP (Markov modulated Poisson process) based self similar arrival process model corresponding to the arrival rate, the autocorrelation, the Hurst parameter and the time scales over which burstiness exists in the input process is first obtained using results from Andersen and Nielsen (1998). We then use queuing theory available for MMPP/G/1 queues to model the switch performance for self similar packet arrivals. The results from the analytical model are compared against those from a simulation model that is driven by traces that are statistically similar to the Bellcore traces. We also analyse the effect of link multiplicities (speedup) to the output and asymmetries in the input traffic.

In this paper we describe QNAT, a software tool developed at Indian Institute of Technology, Kanpur, India, for the analysis and simulation of queueing networks. Arbitrary configurations of open or closed networks of multi-server queues with infinite or finite capacity, fork-join queues with or without synchronization queues can be analyzed or simulated using QNAT. Queueing Networks with multiple classes of customers mall be specified with each class being a closed or an open class independently if there are finite capacity queues in the system, the type of blocking mechanism-transfer, repetitive service or rejection, can also be specified. For the applications where the accuracy of the results is important, an option to simulate the network is also provided. QNAT has proved to be a useful tool for the design of telecommunication systems, computer networks, modeling of industrial systems, design of banking systems, teaching courses and research on queueing theory etc. QNAT is a user-friendly analysis tool, developed with a Windows based Graphical User Interface (GUI). Mathematica forms the computing platform for QNAT due to its ability to perform symbolic computation.

Space-based multicast switches use copy networks to generate the copies requested by the input packets. In this paper our interest is in the multicast switch proposed by Lee (1988). The order in which the copy requests of the input ports are served is determined by the copy scheduling policy and this plays a major part in defining the performance characteristics of a multicast switch. In any slot, the sum of the number of copies requested by the active inputs of the copy network may exceed the number of output ports and some of the copy requests may need to be dropped or buffered. We first propose an exact model to calculate the overflow probabilities in an unbuffered Lee's copy network. Our exact results improve upon the Chernoff bounds on the overflow probability given by Lee by a factor of more than 10. Next, we consider buffered inputs and propose queueing models for the copy network for three scheduling policies: cyclic service of the input ports with and without fanout splitting of copy requests and acyclic service without fanout splitting. These queueing models obtain the average delay experienced by the copy requests. We also obtain the sustainable throughput of a copy network, the maximum load that can be applied to all the input ports without causing an unstable queue at any of the inputs, for the scheduling policies mentioned above.

In this paper we describe an approximate method for the analysis of an open network of finite capacity queues. Finite buffer capacities at the nodes introduce blocking of jobs that finish service at a node and find that the destination node is full at that time. When this happens, we assume that the blocked job is held at the server of the queue where it just completed service, blocking that server until the destination can accommodate it. This is called transfer blocking or blocking after service. We also assume that an external arrival that finds a full queue is lost. We consider an open queueing network with inter-arrival times of external arrivals and service times at each queue having a generalized exponential (GE) distribution. Queues can have finite buffers. To solve this system we augment the network by adding a "holding node" for every stream that can be blocked to hold the blocked jobs during the period corresponding to them blocking the server. The mean time spent in the holding node will be equal to that spent while being blocked. Also, to account for the increased service time of a blocked job as seen by customers behind it in the queue, the service times of these customers need to be increased. We thus use an iterative procedure to converge on to the parameters of the GE distributions of the inter-arrival and service time distributions. Results from our analysis are compared against simulations and they compare very well.

Queue inferencing algorithms are used to derive estimates of queue lengths and/or customer waiting times from a priori information about the customer arrival process and the observed sequence of times at which each customer enters and leaves service. In this paper, we extend these techniques by decoupling the arrival time constraints from the customer departure times, which allows us to handle additional features like server vacations. We then show how these techniques can be used to monitor a single station in a polling system, or in a shared medium local area network such as Ethernet, token ring and FDDI. Using these results, passive, non-intrusive network monitoring tools could be developed to estimate waiting times and queue lengths for any host on the network by observing only the packet departure times from the nodes.

We consider the problem of allocating bandwidth fairly to each node in a shared, unidirectional bus network. We focus on the p/sub i/ persistent protocol, since these are open loop policies designed to operate well in high speed networks, which have a very large bandwidth-delay product and feedback in the upstream direction is not available in a timely manner. First, we introduce an improvement to the basic p/sub i/ persistent protocol, in which we replace random coin tosses with a deterministic counting algorithm, and thereby reduce the delays for all nodes for any given choice of {p/sub i/}. We then describe an exact method for calculating average packet delays and queue lengths in both the p/sub i/ persistent and our new deterministic n out of m protocols, based on the regenerative approach of Georgiades et al. (1987). These delay results, together with simulation measurements, show that both of these protocols still waste some bandwidth. After presenting a lower bounding argument to show that some wasted bandwidth is inevitable in all such distributed access control schemes, assuming a passive bus without feedback in the upstream direction, we show that changing the bus to unidirectional point-to-point links between (very simple) active interfaces at each node allows us to construct distributed access schemes that require no upstream feedback and are both work conserving and fair. To illustrate how this can be done, we introduce the p/sub i/ preemptive protocol, in which each node randomly inserts its own packets into the traffic arriving from upstream. We derive a simple and effective heuristic for calculating the preemption probability for each node, and use simulation to show how well it equalizes the delays at each node.>