Cloud service providers such as AWS and Azure have recently begun to offer storage solutions that allow disk performance to be adjusted “on-the-fly”. Such offerings allow the user to make use of short-term predictions of storage requirements. For example, instead of provisioning a single storage solution that is never under-provisioned, but frequently over-provisioned, one can configure the storage system to support higher performance during peak times; and cheaper, lower performance during periods with less demand. This paper explores the possibility of using a prediction system that utilizes past storage demands to predict the storage requirements over the next hour. We sought a single predictor that could perform well for all types of demand. The predictors were developed using approximately 200 years of storage performance requirements collected from high-performance storage systems in hundreds of companies. We have found that over-provisioning can be greatly reduced, but only at the expense of under-provisioning with a non-zero probability. However, the probability of being under-provisioned can be as low as 0.01%, which is similar to the target service level of cloud vendors. In addition, we have developed novel methods to search for effective predictors that perform well both on average and for rare events.

MANETs will play a critical role for communication in future battlefields. However, wireless communications, especially MANETs are susceptible to jamming. While MANETs will adapt to continuous jamming, intermittent jamming can disrupt the routing protocol. In the intermittent case, the network topology during non-jamming is generally quite different from the one during jamming. In the case of jamming by the enemy, one can use physical means to stop the jamming. However, in recent conflicts, jamming by friendly forces has been widely used. In this paper, we propose the jamming-aware routing protocols for the friendly jamming scenario where the jamming schedule (i.e., when jamming is to occur) is known to the friendly mobile nodes, but hidden from all enemy mobile nodes. The key idea is that the routing protocol freezes during jamming, whereas it resumes during non-jamming. This simple, but very effective, algorithm significantly improves the packet delivery ratio and other metrics compared to other routing protocols where the categories of the routing protocols considered are proactive and unicast with single-path or multipath. Finally, this paper concludes with a discussion on a routing protocol, which combines game-theoretic routing with jamming detection and probabilistic forwarding to avoid and overcome malicious jamming.

It is well known that topology information from nodes that are many hops away has little impact on the selection of the next hop. Hazy-sighted routing and fish-eye routing attempt to take advantage of this behavior in order to reduce overhead without impacting path stretch, which is the increase in the number of hops a packet travels as a result of stale topology information. However, these previous efforts failed to quantify the impact of their approach on path stretch. This paper develops a model of the path stretch as a function of stale topology information. To this end, we find a Markov model that describes the quality of packet forwarding, where jumps occur with some probability whenever the topology changes. From this Markov model, a precise model of path stretch can be derived, and a new and less optimistic view of hazy-sighted flooding emerges.

Accurate identification of P2P (peer-to-peer) applications' flows is important for network capacity planning, provisioning, application traffic engineering, network service pricing, traffic shaping/policing, and flow prioritization. To this end, many identification methods have been developed based on the transport layer port, analysis of packet payloads, statistical observation on flows and graph-based structural properties. One deficiency of those methods is that they concentrate only on a decision of whether a single flow is P2P flow or not. This paper presents methods for detecting P2P flows by constructing a graph where each flow is a vertex. Edges are constructed by applying various rules that consider the ports used by previously detected P2P flows. In this graph, we find that around 90% of the P2P flows are within a large connected component. The remaining 10% is composed of many smaller connected components. Edges between the large connected component and these other components can be constructed with some heuristics. The methods proposed are tested on traffic traces that included signature matching, so that we are able to ensure that significant P2P applications are detected.

Interference and collisions greatly limit the throughput of mesh networks that use contention-based MAC protocols such as IEEE 802.11. Significantly higher throughput is achievable if transmissions are scheduled. However, traditional methods to compute optimal schedules are computationally in tractable (unless co-channel interference is neglected). This paper presents a practical technique to compute optimal schedules. The resulting algorithm searches for a low-dimensional optimization problem that has the same solution as the full problem. Such a low-dimensional problem is shown to always exist. The resulting algorithm converges arithmetically fast or geometrically fast, de pending on whether the objective is to maximize the proportional fair throughput or to maximize the minimum throughput, where the minimum is over all flows in the network. At each iteration of the algorithm, a graph-theoretic optimization known as the maximum weighted independent set (MWIS) problem must be solved. While the general MWIS problem is NP-hard in the worst case, we find that the MWIS can be solved efficiently. Specifically, computational experiments on over 17000 topologies indicate that the ratio of the time to solve the MWIS and the mean degree of the conflict graph grows polynomially with the number of nodes.

A large number of algorithms focus on using scheduling to maximize the stability region. However, this goal does not necessarily result in good performance in terms of supporting a large number of users where users' average time to transfer a file meets a target. This paper develops several computationally efficient schemes for computing schedules for time-varying offered load. Two important findings are that when the traffic is time-varying, the computational complexity can be substantially reduced by using the previous schedule as an initial starting point of the optimization (i.e., warm start). Furthermore, very few iterations (e.g., one iteration) are needed to get a suitable schedule, that is, there is no need to wait for the optimization to converge. A second finding is that there is no need to repeatedly solve the maximum weighted independent set (MWIS) problem. Instead, the MWIS problem is only solved during initialization. Because of the computational efficiency, the schemes presented can be used to frequently update schedules, allowing schedules to quickly adapt to changes in the offered load. Consequently, as compared to other scheduling schemes, the schemes developed support a larger number of users for a given average service time.

In multihop wireless networks, the variability of channels results in some paths providing better performance than other paths. Although it is well known that some paths are better than others, a significant number of routing protocols do not focus on utilizing optimal paths. However, cooperative diversity, which is an area of recent interest, provides techniques for efficiently exploiting path and channel diversity. This paper examines the potential performance improvements offered by path diversity. Three settings are examined, namely, where the path loss and channel correlation are neglected, where path loss is considered, but channel correlation is neglected, and where path loss and channel correlation are both accounted for. It is shown that, by exploiting path diversity, dramatic improvements in the considered route metric may be achieved. Furthermore, in some settings, if the link statistics are held constant, then when path diversity is exploited, the route metric improves with path length. This implies that, if links statistics are fixed and if sufficient path diversity exists, then paths with more hops tend to support higher bit rates than paths with fewer hops. It is shown that such behavior occurs when a particular map has a nonzero fixed point.

Signal to interference plus noise ratio, SINR, is one of the main factors that affects the quality of wireless communication. While the impact of white Gaussian noise on a wireless channel is well understood, impact of interference remains one of the less explored areas. With the deployment of dense mesh networks, the interference will be a dominant factor that affects the transmission errors. This paper explores the performance of 802.11b/g when subject to interference. The findings are based on various controlled experiments in the laboratory setting. One finding of this work is that in contrast to communication over links where the noise is Gaussian, in 802.11b/g, the probability of successfully transmitting a packet is dominated by the ability of the receiver to synchronize with the carrier. As a result, changing to a lower bit-rate with same synchronization scheme will not make the transmission more resilient to interference. The significance of this result on bit-rate selection is briefly explored.

By posing the problem of bandwidth allocation as a constrained maximization problem, it is possible to study various features of optimal bandwidth allocation, and hence the capacity of the network. However, since the typical approach to this problem requires optimizing over a space that is exponential in the number of links, the problem has appeared to be computationally intractable for all but small networks. In this paper, the problem of computing optimal bandwidth allocation is examined and a new approach is presented. While the resulting allocation cannot be guaranteed to be optimal, we find that in the networks where checking optimality is computationally feasible (i.e., networks with fewer than 23 links), the performance of the found allocation is indistinguishable from the optimal allocation. In essence, the proposed iterative scheme focuses on the space of useful bandwidth allocations. The Lagrange multipliers are used to find useful allocations.

We introduce the game-theoretic stochastic routing (GTSR) framework, a proactive alternative to today's reactive approaches to route repair. GTSR minimizes the impact of link and router failure by 1) computing multiple paths between source and destination and 2) selecting among these paths randomly to forward packets. Besides improving fault tolerance, the fact that GTSR makes packets take random paths from source to destination also improves security. In particular, it makes connection eavesdropping attacks maximally difficult as the attacker would have to listen on all possible routes. The approaches developed are suitable for network layer routing, as well as for application layer overlay routing and multipath transport protocols such as the stream control transmission protocol (SCTP). Through simulations, we validate our theoretical results and show how the resulting routing algorithms perform in terms of the security/fault-tolerant/delay/throughput trade-off. We also show that a beneficial side effect of these algorithms is an increase in throughput, as they make use of multiple paths.

Wireless links a subject to large deviations in quality. While such deviations may result in the failure of routes, it also means that some routes may be substantially better than others. In order to utilize these routes, the routing protocol must find these good routes. This paper presents a method for locally searching for routes. Specifically, through passive overhearing of data packets, nodes determine which control packets they should forward. Furthermore, nodes use CDMA with route metric-based power control in order to allow multiple nodes to transmit simultaneously and yet ensure that the control packets advertising the best routes are received. Packet level simulations indicate that these techniques result in significantly better packet delivery ratio, lower delay, and far fewer route failures. For example, in one scenario examined, it was found that the techniques presented resulted in 90% of the connections not requiring any route search after the initial route was found, whereas the other protocols were forced to perform between 4 and 25 route searches for each connection.

This paper examines the achievable performance gains when a particular class of cooperative relaying known as best-select is employed. In essence, best-select seeks to improve performance by exploiting diversity. We closely examine a particular topology when the number of nodes is finite as well when the node density goes to infinity. Determining the performance is complicated by the correlation of the channel gains between nearby channels (i.e., when the receivers are nearby and the transmitters are nearby). This challenge is overcome by modeling the channels as spatially continuous diffusion processes and as a random field and then using a Poisson clumping heuristic. In the example network and metric studied, it is found that in the limit, node cooperation can provide an increase in the end-to-end performance by 35 dB (i.e., a factor of ∼3000) in a 5-hop network. This result motivates further work in the design of multihop cooperative protocols.

This paper describes a technique to reduce the computational complexity of max-flow routing, based on a hierarchical decomposition of the network. The computational complexity of this hierarchical max-flow routing is comparable to that of Dijkstra's and Bellman-Ford's algorithms. It is shown that in many of today's networks, this hierarchical approach provides nearly the same performance as flat (i.e., non-hierarchical) routing, with significantly less computation.

Micro-bursts from TCP flows are investigated. The chip-rate is introduced and used to quantify the short-term bit-rate of TCP flows. This paper examines packets with chip-rates above the 90/sup th/ percentile. The examination is performed over time scales ranging from 244 /spl mu/s to 125 ms. Two issues are addressed, the impact and the causes of the micro-bursts. It is found that the packets with high chip-rate experience an elevated probability of burst losses. For example, the probability of a burst loss is up to 10 times larger for packets sent in micro-bursts. Furthermore, in some settings, these packets experience higher loss rate in general. It is also found that micro-bursts cause an increase in queuing delay. The causes of these micro-bursts are investigated. One finding is that at short-time scales, ACK clocking, which should reduce micro-bursts, is not functioning correctly. For example, in some cases, most of the packets contained in micro-bursts are ACKed at a rate that is less than half of the data rate.

Currently, large-scale deployments of mesh networks are being planned for Philadelphia as well as other cities. The performance of such networks has never been examined through simulation or through any other means. In this paper we perform detailed simulations of mesh networks in several urban environments and evaluate the performance of these networks. The simulations utilize realistic ray-tracing and other propagation models. The mobility of nodes is based on models derived from several movement and time use surveys including the US Department of Labor's recent time use study that includes travel diaries from over 20,000 people. Basic performance issues such as connectivity, capacity, and several application oriented performance metrics as a function of the density infrastructure (base stations and fix wireless relays) are examined. It is found that a high density infrastructure is required to achieve reasonable coverage, in particular, the density must be higher than is currently considered by most deployments. While allowing mobile nodes to act as relays improves coverage, it does not necessarily improve the performance received by the application. It is found that in general, there is a significant difference between the fraction of nodes that are able to communicate with a base station and the fraction of nodes that received acceptable application layer performance.

Link lifetime prediction is occurs frequently in MANET routing protocols. For example, in assigning cache timeout values and route durations, routing protocols make implicit predictions of link lifetime. Some protocols even make explicit predictions. In this paper the predictability of residual link lifetimes is examined. This investigation is performed via simulations that make use of detailed models of urban areas. Propagation is modeled using beam-tracing.

While many models of TCP's dynamics have been developed, few focus on the effects of timeout and high loss probability. Active queue management (AQM) is an important application of these dynamic models. However, recent work has shown that AQM provides little performance benefit over drop-tail queueing for HTTP traffic, except, possibly, at high utilizations. It is at these utilizations that the dynamic models of TCP are the least accurate. The paper presents a dynamic model of TCP that accurately models timeout. This model is also applicable to the static case. The paper also presents a model of the variance and the distribution of the congestion window. It is shown that, while the dynamics of the mean value of the congestion window are rather mild, the dynamics of timeout display large oscillations that take several seconds to decay. These oscillations cause the average bit-rate also to oscillate wildly. The paper includes results from several million simulations providing a detailed view of the dynamics of timeout.

Most standard implementations of TCP perform poorly when packets are reordered. In this paper, we propose a new version of TCP that maintains high throughput when reordering occurs and yet, when packet reordering does not occur is friendly to other versions of TCP. The proposed TCP variant, or TCP-PR, does not rely on duplicate acknowledgments to detect a packet loss. Instead, timers are maintained to keep track of how long ago a packet was transmitted. In case the corresponding acknowledgment has not yet arrived and the elapsed time since the packet was sent is larger than a given threshold, the packet is assumed lost. Because TCP-PR does not rely on duplicate acknowledgments, packet reordering (including out-of-order acknowledgments) has no effect on TCP-PR performance. Through extensive simulations, we show that TCP-PR performs consistently better than existing mechanisms that try to make TCP more robust to packet reordering. When the case that packets are not reordered, we verify that TCP-PR maintains the same throughput as typical implementations of TCP (specifically, TCP-SACK) and shares network resources fairly.

A stochastic model of TCP is developed. Unlike many other models, this model accounts for variations in latency and loss probability. A major strength of this model is that it easily produces the probability distribution of the congestion window. Thus, the mean as well as the median and percentiles can be found. It is shown that the mean congestion window can be far larger than the median. Other new insights include the effect of the rate of change of the latency on the performance of TCP. Specifically, this model predicts the well-known TCP-friendly formula only if the round-trip time rapidly varies. However, if the round-trip time does not vary quickly, then the TCP-friendly formula may not hold. Both rapidly and slowly varying round-trip times have been observed in real networks. As an application of the model, the question as to when a video can be fairly transmitted is addressed. If it is possible to transmit the video, the model yields the distribution of the size of the receiving buffer required to avoid underflow. Since the distribution can be found, it is possible to select a buffer size so that a specified percentage of users will view the video without interruption.

In this paper we present a general hybrid systems modeling framework to describe the flow of traffic in communication networks. To characterize network behavior, these models use averaging to continuously approximate discrete variables such as congestion window and queue size. Because averaging occurs over short time intervals, one still models discrete events such as the occurrence of a drop and the consequent reaction (e.g., congestion control). The proposed hybrid systems modeling framework fills the gap between packet-level and fluid-based models: by averaging discrete variables over a very short time scale (on the order of a round-trip time), our models are able to capture the dynamics of transient phenomena fairly accurately. This provides significant flexibility in modeling various congestion control mechanisms, different queuing policies, multicast transmission, etc. We validate our hybrid modeling methodology by comparing simulations of the hybrid models against packet-level simulations. We find that the probability density functions produced by ns-2 and our hybrid model match very closely with an L1-distance of less than 1%. We also present complexity analysis of ns-2 and the hybrid model. These tests indicate that hybrid models are considerably faster.

Shortest path routing leaves connections at risk of interception and eavesdropping since the path over which data packets travel is fairly predictable and easy to determine. To improve routing security, we propose a proactive mechanism, which we call secure stochastic routing, that explores the existence of multiple routes and forces packets to take alternative paths probabilistically. We investigate game theoretic techniques to develop routing policies which make interception and eavesdropping maximally difficult. Through simulations, we validate our theoretical results and show how the resulting routing algorithms perform in terms of the security/delay/throughput trade-off. We observe that a beneficial side-effect of these algorithms is an increase in throughput, as they make use of multiple paths. The Internet was designed to use redundancy to enhance reliability. We suggest that, through stochastic methods, redundancy be used to increase security.