Providing differentiated services to meet the unique requirements of different use cases is a major goal of the fifth generation (5G) telecommunication networks and will be even more critical for future 6G systems. Fulfilling this goal requires the ability to assure quality of service (QoS) end to end (E2E), which remains a challenge. A key factor that makes E2E QoS assurance difficult in a telecommunication system is that access networks (ANs) and core networks (CNs) manage their resources autonomously. So far, few results have been available that can ensure E2E QoS over autonomously managed ANs and CNs. Existing techniques rely predominately on each subsystem to meet static local QoS budgets with no recourse in case any subsystem fails to meet its local budgets and, hence will have difficulty delivering E2E assurance. Moreover, most existing distributed optimization techniques that can be applied to assure E2E QoS over autonomous subsystems require the subsystems to exchange sensitive information such as their local decision variables. This paper presents a novel framework and a distributed algorithm that can enable ANs and CNs to autonomously "cooperate" with each other to dynamically negotiate their local QoS budgets and to collectively meet E2E QoS goals by sharing only their estimates of the global constraint functions, without disclosing their local decision variables. We prove that this new distributed algorithm converges to an optimal solution almost surely, and also present numerical results to demonstrate that the convergence occurs quickly even with measurement noise.

We study the problem of minimizing the (time) average security costs in large systems comprising many interdependent subsystems, where the state evolution is captured by a susceptible-infected-susceptible (SIS) model. The security costs reflect security investments, economic losses and recovery costs from infections and failures following successful attacks. However, unlike in existing studies, we assume that the underlying dependence graph is only weakly connected, but not necessarily strongly connected. When the dependence graph is not strongly connected, existing approaches to computing optimal security investments cannot be applied. Instead, we show that it is still possible to find a good solution by perturbing the problem and establishing necessary continuity results that then allow us to leverage the existing algorithms.

We study the problem of minimizing the (time) average security costs in large networks/systems comprising many interdependent subsystems, where the state evolution is captured by a susceptible-infected-susceptible (SIS) model. The security costs reflect security investments, economic losses and recovery costs from infections and failures following successful attacks. We show that the resulting optimization problem is nonconvex and propose a suite of algorithms – two based on convex relaxations, and the other two for finding a local minimizer, based on a reduced gradient method and sequential convex programming. Also, we provide a sufficient condition under which the convex relaxations are exact and, hence, an optimal solution of the original problem can be recovered. Numerical results are provided to validate our analytical results and to demonstrate the effectiveness of the proposed algorithms.

We study the problem of minimizing the (time) average security costs in large systems comprising many interdependent subsystems, where the state evolution is captured by a susceptible-infected-susceptible (SIS) model. The security costs reflect security investments, economic losses and recovery costs from infections and failures following successful attacks. We show that the resulting optimization problem is non-convex and propose two algorithms - one for solving a convex relaxation, and the other for finding a local minimizer, based on a reduced gradient method. Also, we provide a sufficient condition under which the convex relaxation is exact and its solution coincides with that of the original problem. Numerical results are provided to validate our analytical results and to demonstrate the effectiveness of the proposed algorithms.

We study the influence of degree correlations or network mixing on interdependent security. We model the interdependence in security among agents using a dependence graph and employ a population game model to capture the interaction among many agents when they are strategic and have various security measures they can choose to defend themselves. The overall network security is measured by what we call the average risk exposure (ARE) from neighbors, which is proportional to the total (expected) number of attacks in the network. We first show that there exists a unique pure-strategy Nash equilibrium of a population game. Then, we prove that as the agents with larger degrees in the dependence graph see higher risks than those with smaller degrees, the overall network security deteriorates in that the ARE experienced by agents increases and there are more attacks in the network. Finally, using this finding, we demonstrate that the effects of network mixing on ARE depend on the (cost) effectiveness of security measures available to agents; if the security measures are not effective, increasing assortativity of dependence graph results in higher ARE. On the other hand, if the security measures are effective at fending off the damages and losses from attacks, increasing assortativity reduces the ARE experienced by agents.

We study the impact of assortativity or network mixing on interdependent security. We employ a population game model to capture the interaction among many agents when agents are strategic and have various security measures they can choose to defend themselves. We model the interdependence in security among agents using a dependence network. The overall (local) network security seen by agents is measured by what we call the average risk exposure (ARE) from neighbors, which is proportional to the total (expected) number of attacks in the network. We first show that there exists a unique pure-strategy Nash equilibrium of a population game. Then, we prove that as the agents with larger degrees in the dependence network see higher risks than those with smaller degrees, the overall network security deteriorates in that the ARE experienced by agents increases and there are more attacks in the network. Finally, using this finding, we demonstrate that the effects of network mixing on ARE depends on the cost effectiveness of security measures available to agents; if the security measures are not effective, increasing assortativity of the dependence network results in higher ARE. On the other hand, if the security measures are effective in fending off the damages and losses, increasing assortativity reduces the ARE experienced by agents.

Multiple transmission point (TP) coordination is an effective tool for managing interference in heterogeneous networks. Using network-level MIMO coordination among TPs, multiple TPs can transmit independent data streams to a single user. We formulate our scheduling problem as a utility optimization problem over the set of user-TP pairs in each subframe, in which each user can be served by multiple TPs. We first prove that this optimization problem is NP-hard. Then, we propose a new scheme based on the difference-of-submodular-function optimization approach. We evaluate our scheme using detailed simulation and demonstrate that it performs on par with a more computationally demanding successive convex approximation optimization scheme. Moreover, the proposed scheme performs within a reasonable percentage of the optimal solution (Table IV). We also study its performance with varying network topology and parameters.

Deployment of low power pico basestations within cellular networks can potentially increase both capacity and coverage. However, such deployments require efficient frequency allocation schemes for managing interference from the pico and macro basestations that are located within each other's transmission range. Partitioning the available frequencies between the various basestations avoids the problem of interference, but can lead to inefficient spectrum usage. In this paper, we introduce a distributed frequency allocation scheme that shares frequencies between macro and pico basestations, and guarantees a minimum average throughput to users. The scheme seeks to minimize the total number of frequencies needed to honor the minimum throughput requirements. We evaluate our scheme using detailed simulations and show that it performs on par with the centralized optimum allocation. Moreover, our proposed scheme outperforms a static frequency reuse scheme and the centralized optimal partitioning between the macro and pico basestations.

We investigate cascades in networks consisting of strategic agents with interdependent security. We assume that the strategic agents have choices between (i) investing in protecting themselves, (ii) purchasing insurance to transfer (some) risks, and (iii) taking no actions. Using a population game model, we study how various system parameters, such as node degrees, infection propagation rate, and the probability with which infected nodes transmit infection to neighbors, affect nodes' choices at Nash equilibria and the resultant price of anarchy/stability. In addition, we examine how the probability that a single infected node can spread the infection to a significant portion of the entire network, called cascade probability, behaves with respect to system parameters. In particular, we demonstrate that, at least for some parameter regimes, the cascade probability increases with the average degree of nodes.

We study the interaction between a service provider (SP) and a content provider (CP) when the SP can provide higher quality-of-service (QoS) to content service under a private agreement with the CP. We model the interaction between the providers both as a Stackelberg game and as a two-person bargaining problem in order to understand how the relative bargaining power of these providers affects the resulting QoS and social efficiency. Our findings suggest that the social efficiency is identical under both the two-person bargaining problem model and the Stackelberg game model regardless of which provider is the leader with a stronger bargaining position. In addition, we prove that, under a mild technical condition, the QoS at Nash equilibrium and Nash bargaining solution improves as the contract duration increases.

Recently, dynamic spectrum sharing has been gaining interest as a potential solution to scarcity of available spectrum. We investigate the problem of designing a secondary spectrum-trading market when there are multiple sellers and multiple buyers and propose a general framework for the trading market based on an auction mechanism. To this end, we first introduce a new optimal auction mechanism, called the generalized Branco's mechanism (GBM). The GBM, which is both incentive-compatible and individually rational, is used to determine the assigned frequency bands and prices for them. Second, we assume that buyers of the spectrum are selfish and model their interaction as a noncooperative game. Using this model, we prove that when the sellers employ the GBM to vend their frequency bands, they can guarantee themselves the largest expected profits by selling their frequency bands jointly. Third, based on the previous finding, we model the interaction among the sellers as a cooperative game and demonstrate that, for any fixed strategies of the buyers, the core of the cooperative game is nonempty. This suggests that there exists a way for the sellers to share the profits from the joint sale of the spectrum so that no subset of sellers will find it beneficial to vend their frequency bands separately without the remaining sellers. Finally, we propose a profit-sharing scheme that can achieve any expected profit vector in the nonempty core of the cooperative game while satisfying two desirable properties.

Supporting massive device transmission is challenging in machine-to-machine (M2M) communications. Particularly, in event-driven M2M communications, a large number of devices become activated within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S-ALOHA (FASA) scheme for random access control of M2M communication systems with bursty traffic. Instead of the observation in a single slot, the statistics of consecutive idle and collision slots are used in FASA to accelerate the tracking process of network status that is critical for optimizing S-ALOHA systems. With a design based on drift analysis, the estimate of the number of the active devices under FASA converges fast to the true value. Furthermore, by examining the T-slot drifts, we prove that the proposed FASA scheme is stable as long as the average arrival rate is smaller than e-1, in the sense that the Markov chain derived from the scheme is geometrically ergodic. Simulation results demonstrate that under highly bursty traffic, the proposed FASA scheme outperforms traditional additive schemes such as PB-ALOHA and achieves near-optimal performance in reducing access delays. Moreover, compared to multiplicative schemes, FASA shows its robustness under heavy traffic load in addition to better delay performance.

We study the issue of mobile wireless network (MWN) connectivity. In particular, we investigate the smallest communication or transmission range of the nodes necessary for connectivity of MWNs, which we call the critical transmission range (CTR). Unlike many of existing studies, however, the mobilities of the nodes are not assumed homogeneous, and the locations of the nodes are not identically distributed. We examine the distribution of CTR when the number of nodes in the network is large. We show that, under some conditions, the CTR is inversely proportional to the infimum of the average spatial density of the nodes in the network and its distribution goes through a phase transition over a small range.

Machine-to-Machine (M2M) communication is now playing a market-changing role in a wide range of business world. However, in event-driven M2M communications, a large number of devices activate within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S- ALOHA (FASA) scheme for M2M communication systems with bursty traffic. The statistics of consecutive idle and collision slots, rather than the observation in a single slot, are used in FASA to accelerate the tracking process of network status. Furthermore, the fast convergence property of FASA is guaranteed by using drift analysis. Simulation results demonstrate that the proposed FASA scheme achieves near-optimal performance in reducing access delay, which outperforms that of traditional additive schemes such as PB-ALOHA. Moreover, compared to multiplicative schemes, FASA shows its robustness even under heavy traffic load in addition to better delay performance.

We investigate the problem of estimating the average speeds of vehicles traveling in different types of lanes, e.g., express lanes and local lanes, without knowing which lanes individual vehicles were traveling in. In our study, we use the recordings at two spatially separated Bluetooth sensors, which contain the globally unique Bluetooth device addresses of Bluetooth-enabled devices inside vehicles. These recordings are used to compute the vehicle speeds. Unfortunately, these recordings do not tell us which lanes the vehicles were traveling in and hence do not allow us to directly estimate the separate average speeds of vehicles, for example, in express lanes and local lanes or in high occupancy vehicle (HOV) lanes and regular lanes. We propose a novel estimation scheme that can provide separate average speeds of the vehicles in different types of lanes. We demonstrate the feasibility and accuracy of our proposed scheme, using real data collected by Bluetooth sensors alongside highways.

We investigate the communication range of the nodes necessary for network connectivity, which we call bidirectional connectivity, in a simple setting. Unlike in most of existing studies, however, the locations or mobilities of the nodes may be correlated through group mobility: nodes are broken into groups, with each group comprising the same number of nodes, and lie on a unit circle. The locations of the nodes in the same group are not mutually independent, but are instead conditionally independent given the location of the group. We examine the distribution of the smallest communication range needed for bidirectional connectivity, called the critical transmission range (CTR), when both the number of groups and the number of nodes in a group are large. We first demonstrate that the CTR exhibits a parametric sensitivity with respect to the space each group occupies on the unit circle. Then, we offer an explanation for the observed sensitivity by identifying what is known as a very strong threshold and asymptotic bounds for CTR.

Current IP geoloation techniques can geolocate an IP address to a region approximately 700 square miles, roughly the size of a metropolitan area. We model geolocation as a pattern-recognition problem, and introduce techniques that geolocate addresses to within 5 miles inside a metropolitan area. We propose two complementary algorithms: The first algorithm, Pattern Based Geolocation (PBG), models the distribution of latencies to the target and compares it to those of the reference landmarks to resolve an address to within 5 miles in a metropolitan area. The second approach, Perturbation Augmented PBG (PAPBG), provides higher resolution by sending extra traffic in the network. While sending an aggregate of 600 Kbps extra traffic to 20 nodes for approximately 2 minutes, PAPBG geolocates addresses to within 3 miles.

We study routing overhead due to location information collection and retrieval in mobile ad-hoc networks employing geographic routing with no hierarchy. We first provide a new framework for quantifying overhead due to control messages generated to exchange location information. Second, we compute the minimum number of bits required on average to describe the locations of a node, borrowing tools from information theory. This result is then used to demonstrate that the expected overhead is Ω (n1.5log (n)), where n is the number of nodes, under both proactive and reactive geographic routing, with the assumptions that 1) nodes' mobility is independent, and 2) nodes adjust their transmission range to maintain network connectivity. Finally, we prove that the minimum expected overhead under the same assumptions is Θ (n log (n)).

The performance of a mobile wireless network depends on the time-varying connectivity of the network as nodes move around. Hence, there has been a growing interest in the distribution of intermeeting times between two nodes in mobile wireless networks. We study the distribution of intermeeting times under the generalized Hybrid Random Walk mobility model. We show that when 1) the (conditional) probability that two nodes can communicate directly with each other given that they are in the same cell is small and 2) node's transitions in locations are independent over time, the distribution of intermeeting times can be well approximated using an exponential distribution. Moreover, the mean of intermeeting times can be estimated using the number of cells in the network and the aforementioned conditional probability of having a communication link when the two nodes are in the same cell. We also offer some insight behind the emergence of an exponential distribution, borrowing well-known results in existing literature on rare events.

We study the problem of assigning wavelengths to a given set of multicast traffic requests with the objective of minimizing the number of wavelengths used per fiber. We assume that the underlying optical network is a tree and that all-optical networking paradigm is employed. First, we prove that the problem is NP hard even when the underlying network is a simple star or path. Since assigning wavelengths to a given set of unicast traffic requests on star and path networks is easy, this shows that the the multicast wavelength assignment problem is fundamentally harder than the unicast scenario. Next we present GREEDY and SUBTREE-BASED: two simple deterministic algorithms for assigning wavelengths to a given set of multicast traffic requests when the underlying network is a tree with maximum node degree 3 and 4 respectively. Of the two wavelength assignment schemes, GREEDY is a 5/2-approximation algorithm, and SUBTREE-BASED is an approximation algorithm with approximation ratio 10/3, 3 and 2 for the cases when the underlying network is a tree with degree 4, 3 and 2, respectively.

In this paper, we present an algorithm for intra-domain traffic engineering. We assume that the traffic matrix, which specifies traffic load between every source-destination pair in the network, is unknown and varies with time, but that always lies inside an explicitly defined region. Our goal is to compute a fixed robust routing with best worst case performance for all traffic matrices inside the bounding region. We formulate this problem as a semi-infinite programming problem. Then, we focus on a special case with practical merits, where (1) the traffic matrix region is assumed to be a polytope specified by a finite set of linear inequalities, and (2) our objective is to find the routing that minimizes the maximum link utilization. Under these assumptions, the problem can be formulated as a polynomial size linear programming (LP) problem with finite number of constraints. We further consider two specific set of constraints for the traffic matrix region. The first set is based on the hose model and limits the total traffic rate of network point of presence (PoP) nodes. The second set is based on the pipe model and limits the traffic between source-destination pairs. We study the effectiveness of each set of constraints using extensive simulations.

In this paper we study the problem of efficient grooming of given non-uniform multicast traffic demands on a unidirectional SONET/WDM ring. The goal is to try to minimize the network cost as given by (i) the number of wavelengths required per fiber and (ii) the number of electronic add-drop multiplexers (ADMs) required on the ring. The problem is NP hard for both the cost functions. We observe that the problem with cost function (i) can be reduced to a corresponding traffic grooming problem for unicast traffic which can then be modelled as a standard circular-arc graph coloring problem. For cost function (ii), we construct a graph based heuristic and compare it against the multicast extension of the best known unicast traffic grooming heuristic (Zhang, 2000). We observe that our heuristic requires fewer ADMs than required by the multicast extension of the unicast heuristic given in (Zhang, 2000). We also develop a lower bound and compare it against some upper bounds to study the maximum penalty of not employing intelligent wavelength assignment and/or traffic grooming under the unidirectional SONET/WDM ring scenario.

We consider the problem of finding a single-path intra-domain routing for time-varying traffic. We characterize the traffic variations by a finite set of traffic profiles with given non-zero fractions of occurrence. Our goal is to optimize the average performance over all of these traffic profiles. We solve the optimal multi-path version of this problem using linear programming and develop heuristic single-path solutions using randomized rounding and iterated rounding. We analyze our single-path heuristic (finding the optimal single-path routing is NP-hard), and prove that the randomized rounding algorithm has a worst case performance bound of O(log(KN)/log(log(KN))) compared to the optimal multi-path routing with a high probability, where K is the number of traffic profiles, and N the number of nodes in the network. Further, our simulations show the iterated rounding heuristics perform close to the optimal multi-path routing on a wide range of measured ISP topologies, in both the average and the worst-case. Overall, these results are extremely positive since they show that in a wide-range of practical situations, it is not necessary to deploy multi-path routing; instead, an appropriately computed single-path routing is sufficient to provide good performance.

rdquoWe present a novel group-based mechanism to reconfigure the virtual topology of survivable MPLS/WDM networks by using the existing shared protection backup resource. With this mechanism, lightpaths are divided into groups and those in the same group can be reconfigured simultaneously at one step. Ideally, this mechanism won't incur any service disruption during the reconfiguration process. The optimal reconfiguration policy is obtained through solving following two problems: the Grouping problem which minimizes the reconfiguration steps, and the Sequencing problem which minimizes the network resource used during the reconfiguration process. We prove these two problems to be NP-hard and present efficient heuristic algorithms. A general mathematical method of rollout is applied to the heuristics to improve the solution quality. Numerical results are presented to show the optimal tradeoff between the reconfiguration duration and the required redundant capacity.

Abstract — We propose a measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple multicast sources. Multiple paths are established using application-layer overlaying. The proposed algorithm is able to converge under different network models, where each model reflects a different set of assumptions about the multicasting capabilities of the network. The algorithm is derived from simultaneous perturbation stochastic approximation and relies only on noisy estimates from measurements. Simulation results are presented to demonstrate the additional benefits obtained by incrementally increasing the multicasting capabilities. I.

We study the issue of handling unknown inter-cell interference in multi-cell environments with antenna arrays at the base stations. First, we demonstrate that the presence of unknown inter-cell interference that cannot be predicted accurately, can significantly degrade the system performance when unaccounted for. Second, we propose two algorithms that are aimed at providing a quality-of-service guarantee in the form of packet error rate (PER) in the presence of unknown inter-cell interference. The first algorithm is based on a derived expression for average PER as a function of the distribution of experienced signal to interference and noise ratio and dynamically adjusts the input parameters based on the channel condition and interference. The second algorithm makes use of the observation that the distribution of inter-cell interference experienced by a mobile can be well approximated by a log-normal distribution. We demonstrate that these algorithms achieve the target PER

We address the problem of adaptive dimensioning of bandwidth tunnels in a dynamic, real-time traffic environment. We consider a scenario where paths associated with the tunnels are fixed, but the associated bandwidth allocations can be adapted to variations in the incoming traffic. We present an approach for adjusting the tunnel bandwidths incrementally so as to maximize the system throughput. We show, through simulations, that our iterative algorithm converges to the optimal bandwidth allocation for stable traffic patterns. We also demonstrate that our dynamic bandwidth provisioning algorithm significantly outperforms the optimal static bandwidth provisioning policy. Although our policy is incremental in nature and is simple to implement, it yields a performance close to that of the optimal dynamic bandwidth provisioning policy.

We propose a measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple multicast sources. Multiple paths are established using application-layer overlaying. The proposed algorithm is able to converge under different network models, where each model reflects a different set of assumptions about the multicasting capabilities of the network. The algorithm is derived from simultaneous perturbation stochastic approximation and relies only on noisy estimates from measurements. Simulation results are presented to demonstrate the additional benefits obtained by incrementally increasing the multicasting capabilities.

We study the application of antenna arrays at the base stations in a multi-cell environment. Simulation results demonstrate that the inter-cell interference significantly degrades the system performance in terms of packet loss probability (PLP) and total throughput. In order to cope with the presence of inter-cell interference in multi-cell networks we propose two algorithms: the first algorithm replaces the noise term in the beamforming algorithm by the sum of average inter-cell interference and noise, and is shown to perform well for certain type of link curves. We derive an expression for the average PLP as a function of the target SINR value corresponding to the target PLP. This expression tells us that the average PLP does not equal the target PLP in general, and offers an explanation for the good performance of the first algorithm for some link curves. Based on this expression, the second proposed algorithm makes use of more than just the mean of the SINR distribution in the beamforming algorithm. The experimental results demonstrate that this algorithm achieves the target PLP with general link curves and different scheduling algorithms under various wireless channel models. We characterize the inter-cell interference distribution for different scheduling and beamforming algorithms under various channel models. It is shown that the inter-cell interference can be well approximated by a log-normal random variable and exhibits weak temporal correlation.

We introduce a new approach for QoS provisioning in packet networks based on the notion of differentiated traffic engineering (DTE). We consider a single AS network capable of source based multi-path routing. We do not require sophisticated queuing or per-class scheduling at individual routers; instead, if a link is used to forward QoS sensitive packets, we maintain its utilization below a threshold. As a consequence, DTE eliminates the need for per-flow (IntServ) or per-class (DiffServ) packet processing tasks such as traffic classification, queueing, shaping, policing and scheduling in the core and hence poses a lower burden on the network management unit. Conversely, DTE utilizes network bandwidth much more efficiently than simple over-provisioning. In this paper, we propose a complete architecture and an algorithmic structure for DTE. We show that our scheme can be formulated as a non-convex optimization problem, and we present an optimal solution framework based on simulated annealing. We present a simulation-based performance evaluation of DTE, and compare our scheme to existing (gradient projection) methods.

We adopt an optimization framework for the rate allocation problem proposed by Kelly and investigate the stability of a discretized system with arbitrary communication delays between network elements. We show that there is an underlying market structure, and the stability of this market equilibrium is directly related to the stability of the rate control system. We first derive general stability conditions and use them to establish the stability of the system with a family of popular utility and resource price functions. Numerical examples are provided to validate our analyses.

We propose a new architecture for efficient network monitoring and measurements in a traditional IP network. This new architecture enables establishment of multiple paths (tunnels) between source-destination pairs without having to modify the underlying routing protocol(s). Based on the proposed architecture we propose a measurement-based multipath routing algorithm derived from simultaneous perturbation stochastic approximation. The proposed algorithm does not assume that the gradient of analytical cost function is known to the algorithm, but rather relies on noisy estimates from measurements. Using the analytical model presented in the paper we prove the convergence of the algorithm to the optimal solution. Simulation results are presented to demonstrate the advantages of the proposed algorithm under a variety of network scenarios. A comparative study with an existing optimal routing algorithm, MATE, is also provided.

We study the downlink scheduling problem in a cellular wireless network. The base stations are equipped with antenna arrays and can transmit to more than one mobile user at any time instant, provided the users are spatially separable. In previous work, an infinite traffic demand model is used to study the physical layer beamforming and power control algorithms that maximize the system throughput. We consider finite user traffic demands. A scheduling policy makes a decision based on both the queue lengths and the spatial separability of the users. The objective of the scheduling algorithm is to maintain the stability of the system. We derive an optimal scheduling policy that maintains the stability of the system if it is stable under any scheduling policy. However, this optimal scheduling policy is exponentially complex in the number of users which renders it impractical. We propose four heuristic scheduling algorithms that have polynomial complexity. The first two algorithms are for the special case of single cell systems, while the other two algorithms deal with multiple cell systems. Using a realistic multipath wireless channel model, we evaluate the performance of the proposed algorithms through computer simulations. The results demonstrate the benefits of joint consideration of queue length and dynamic base station assignment.

We develop a framework for studying the interaction of a probabilistic active queue management (AQM) algorithm with a generic end-user congestion-control mechanism. We show that as the number of flows in the network increases, the queue dynamics can be accurately approximated by a simple deterministic process. In addition, we investigate the sources of queue fluctuations in this setup. We characterize two distinct sources of queue fluctuations; one is the deterministic oscillations which can be captured through the aforementioned deterministic process. The other source is the random fluctuations introduced by the probabilistic nature of the marking schemes. We discuss the relationship between these two types of fluctuations and provide insights into how to control them. Concrete examples in this framework are given for several popular algorithms such as Random Early Detection, Random Early Marking and Transmission Control Protocol.

This work develops a discrete-time dynamical feedback system model for a simplified TCP network with RED control and provides a nonlinear analysis that can help in understanding observed parametric sensitivities. The model describes network dynamics over large parameter variations. The dynamical model is used to analyze the TCP-RED operating point and its stability with respect to various RED controller and system parameters. Bifurcations are shown to occur as system parameters are varied. These bifurcations, which involve the emergence of oscillatory and/or chaotic behavior, shed light on the parametric sensitivity observed in practice. The bifurcations arise due to the presence of a nonlinearity in the TCP throughput characteristic as a function of drop probability at the gateway. Among the bifurcations observed in the system are period doubling and border collision bifurcations. The bifurcations are studied analytically, numerically, and experimentally.

In this work, we investigate flow migration as a mechanism to sustain QoS to network users during short-term overloads in the context of an MPLS IP network. We experiment with three different control techniques: static long-term optimal mapping of flows to LSPs; on-line locally optimal mapping of flows to LSPs at flow set-up time; and dynamic flow migration in response to transient congestion. These techniques are applicable over different timescales, have different run-time overheads, and require different levels of monitoring and control software inside the network. We present results both from detailed simulations and a complete implementation using software IP routers. We use voice-over-IP as our test application, and show that if end-to-end quality is to be maintained during short unpredictable bursts of high load, then a fast-timescale control such as migration is required.

We study the problem of dynamic resource allocation of a GPS server with two traffic classes when the leaky bucket scheme is employed as a traffic policing mechanism. Three popular input traffic models - independent Poisson arrival, autoregressive model, and partially observed traffic (hidden Markov model) - are investigated. Theoretically, optimal control can be obtained by a basic dynamic programming algorithm. However, such a solution is computationally prohibitive due to the curse of dimensionality. Instead, we propose several heuristic policies with improvements using rollout, parallel rollout, and hindsight optimization techniques under the aforementioned traffic models and show that these techniques can significantly reduce the penalty associated with delays and dropped packets.

Random early detection (RED) mechanism has been proposed to control the average queue size at the bottlenecks inside the network. It has been shown that the interaction between a RED gateway and TCP connections can lead to a rich set of nonlinear phenomena in single bottleneck cases. In this paper we extend this model and study the interaction of TCP connections with RED gateways in a simple tandem network, using a nonlinear first-order discrete-time model. We demonstrate, using bifurcation diagrams, that the nonlinear behavior of TCP can result in both smooth and non-smooth bifurcations, leading to chaos. We show that the instabilities can be induced at both bottlenecks while fixing the parameters at the other, thus demonstrating the propagation of instability. Moreover, we show that locally sufficient conditions for stability based on single node analysis are not sufficient for global network stability.

In a communication network, a good rate allocation algorithm should reflect the utilities of the users while being fair. We investigate this fundamental problem of achieving the system optimal rates in the sense of maximizing aggregate utility, in a distributed manner, using only the information available at the end hosts of the network. This is done by decomposing the overall system problem into subproblems for the network and for the individual users by introducing a pricing scheme. The users are to solve the problem of maximizing individual net utility, which is the utility less the amount they pay. We provide algorithms for the network to adjust its prices and the users to adjust their window sizes such that at an equilibrium the system optimum is achieved. Further, the equilibrium prices are such that the system optimum achieves weighted proportional fairness. It is notable that the update algorithms of the users do not require any explicit feedback from the network, rendering them easily deployable over the Internet. Our scheme is incentive compatible in that there is no benefit to the users to lie about their utilities.

We investigate the fundamental problem of achieving the system optimal rates, which maximize the total user utility, in a distributed network environment using only the information available at the end hosts. This is done by decomposing the overall system problem into subproblems for the network and for the individual users and introducing an incentive-compatible pricing scheme. The users are to solve the problem of maximizing individual net utility, which is their utility less the amount they pay. This is done using a window based algorithm. We provide an algorithm for the network to adjust its prices and the users to adjust their window sizes such that at an equilibrium the system optimum is achieved. It is notable that our algorithm does not require any explicit feedback from the network and can be deployed over the Internet with modifications only at the end hosts. Our scheme is incentive compatible in that there is no benefit to the users to lie about their utilities.

We investigate the fundamental problem of achieving the system optimal rates in a distributed environment, which maximize the total user utility, using only the information available at the end hosts. This is done by decomposing the system problem into two subproblems-network and user problems-and introducing an incentive-compatible pricing scheme, while maintaining proportional fairness. We demonstrate that when users update their parameters by solving their own optimization problem, at an equilibrium the system optimum is achieved. Furthermore, this algorithm does not require any explicit feedback from the network and can be deployed over the Internet with modifications only on the end hosts. In the second part of the paper we model as a noncooperative game the case where the choice of each user's action has nonnegligible effect on the price per unit flow at the resources and investigate the Nash equilibria of the game. We show, in the simple case of a single bottleneck, that there exists a unique Nash equilibrium of the game. Further, as the number of users increases, the unique Nash equilibrium approaches the system optimum.

We propose some improvements of TCP Vegas and compare its performance characteristics with TCP Reno. We argue through analysis that TCP Vegas, with its better bandwidth estimation scheme, uses the network resources more efficiently and fairly than TCP Reno. Simulation results are given that support the results of the analysis.