Search

The data transmission performance of a network protocol is closely related to the amount of available information about the network state. In general, more network state information results in better data transmission performance. However, acquiring such state information expends network bandwidth resource. Thus, a trade-off exists between the amount of network state information collected, and the improved protocol performance due to this information. A framework has been developed in the previous efforts to study the optimal trade-off between the amount of collected information and network performance. However, the effect of information delay is not considered in the previous analysis. In this paper, we extend the framework to study the relationship between the amount of collected state information and the achievable network performance under the assumption that information is subject to delay. Based on the relationship we could then obtain the optimal resource allocation between the data transmission and network state information acquisition in a time-varying network. We have considered both memoryless and memory-exploited scenarios in our framework. Structures of the Pareto optimal information collection and decision-making strategies are discussed. Examples of multiuser scheduling and multi-hop routing are used to demonstrate the framework’s application to practical network protocols. [ABSTRACT FROM AUTHOR]

Today’s home networks are often composed of several technologies such as Wi-Fi or power-line communication (PLC). Yet, current network protocols rarely fully harness this diversity and use each technology for a specific, pre-defined role, for example, wired media as a backbone and the wireless medium for mobility. Moreover, a single path is generally employed to transmit data; this path is established in advance and remains in use as long as it is valid, although multiple possible paths offer more robustness against varying environments. We introduce HyMAB, an algorithm that explores different multipaths and finds the best one in a mesh hybrid network, while keeping congestion under control. We employ the multi-armed-bandit framework and prove that HyMAB achieves optimal throughput under a static scenario. HyMAB design also accounts for real-network intricacies and dynamic conditions; it adapts to varying environments and switches multipaths when needed. We implement HyMAB on a PLC/Wi-Fi test bed. This is, to the best of our knowledge, the first implementation on a real test bed of multi-armed-bandit strategies in the context of routing. Our experimental results confirm the optimality of HyMAB and its ability to adapt to dynamic network conditions, as well as the gains provided by employing multi-armed-bandit strategies. [ABSTRACT FROM AUTHOR]

We derive a modular fluid-flow network congestion control model based on a law of fundamental nature in networks: the conservation of information. Network elements such as queues, users, and transmission channels and network performance indicators like sending/acknowledgment rates and delays are mathematically modeled by applying this law locally. Our contributions are twofold. First, we introduce a modular metamodel that is sufficiently generic to represent any network topology. The proposed model is composed of building blocks that implement mechanisms ignored by the existing ones, which can be recovered from exact reduction or approximation of this new model. Second, we provide a novel classification of previously proposed models in the literature and show that they are often not capable of capturing the transient behavior of the network precisely. Numerical results obtained from packet-level simulations demonstrate the accuracy of the proposed model. [ABSTRACT FROM PUBLISHER]

The Ethernet switch is a primary building block for today's enterprise networks and data centers. As network technologies converge upon a single Ethernet fabric, there is ongoing pressure to improve the performance and efficiency of the switch while maintaining flexibility and a rich set of packet processing features. The OpenFlow architecture aims to provide flexibility and programmable packet processing to meet these converging needs. Of the many ways to create an OpenFlow switch, a popular choice is to make heavy use of ternary content addressable memories (TCAMs). Unfortunately, TCAMs can consume a considerable amount of power and, when used to match flows in an OpenFlow switch, put a bound on switch latency. In this paper, we propose enhancing an OpenFlow Ethernet switch with per-port packet prediction circuitry in order to simultaneously reduce latency and power consumption without sacrificing rich policy-based forwarding enabled by the OpenFlow architecture. Packet prediction exploits the temporal locality in network communications to predict the flow classification of incoming packets. When predictions are correct, latency can be reduced, and significant power savings can be achieved from bypassing the full lookup process. Simulation studies using actual network traces indicate that correct prediction rates of 97% are achievable using only a small amount of prediction circuitry per port. These studies also show that prediction circuitry can help reduce the power consumed by a lookup process that includes a TCAM by 92% and simultaneously reduce the latency of a cut-through switch by 66%. [ABSTRACT FROM AUTHOR]

CHOKe is a simple and stateless active queue management (AQM) scheme. Apart from low operational overhead, a highly attractive property of CHOKe is that it can protect responsive TCP flows from unresponsive UDP flows. Particularly, previous works have proven that CHOKe is able to bound both bandwidth share and buffer share of (a possible aggregate) UDP traffic (flow) on a link. However, these studies consider, and pertain only to, a steady state where the queue reaches equilibrium in the presence of many (long-lived) TCP flows and an unresponsive UDP flow of fixed arrival rate. If the steady-state conditions are perturbed, particularly when UDP traffic rate changes over time, it is unclear whether the protection property of CHOKe still holds. Indeed, it can be examined, for example, that when UDP rate suddenly becomes 0 (i.e., flow stops), the unresponsive flow may assume close to full utilization in sub-round-trip-time (sub-RTT) scales, potentially starving out the TCP flows. To explain this apparent discrepancy, this paper investigates CHOKe queue properties in a transient regime, which is the time period of transition between two steady states of the queue, initiated when the rate of the unresponsive flow changes. Explicit expressions that characterize flow throughputs in transient regimes are derived. These results provide additional understanding of CHOKe and give some explanation on its intriguing behavior in the transient regime. [ABSTRACT FROM AUTHOR]

Contemporary wireless multihop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper, we present XPRESS, a cross-layer backpressure architecture designed to reach the capacity of wireless multihop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11. [ABSTRACT FROM AUTHOR]

Cellular network-based machine-to-machine (M2M) communication is fast becoming a market-changing force for a wide spectrum of businesses and applications such as telematics, smart metering, point-of-sale terminals, and home security and automation systems. In this paper, we aim to answer the following important question: Does traffic generated by M2M devices impose new requirements and challenges for cellular network design and management? To answer this question, we take a first look at the characteristics of M2M traffic and compare it to traditional smartphone traffic. We have conducted our measurement analysis using a week-long traffic trace collected from a tier-1 cellular network in the US. We characterize M2M traffic from a wide range of perspectives, including temporal dynamics, device mobility, application usage, and network performance. Our experimental results show that M2M traffic exhibits significantly different patterns than smartphone traffic in multiple aspects. For instance, M2M devices have a much larger ratio of uplink-to-downlink traffic volume, their traffic typically exhibits different diurnal patterns, they are more likely to generate synchronized traffic resulting in bursty aggregate traffic volumes, and are less mobile compared to smartphones. On the other hand, we also find that M2M devices are generally competing with smartphones for network resources in co-located geographical regions. These and other findings suggest that better protocol design, more careful spectrum allocation, and modified pricing schemes may be needed to accommodate the rise of M2M devices. [ABSTRACT FROM AUTHOR]

Opportunistic mobile ad hoc networks (MANETs) are a special class of sparse and disconnected MANETs where data communication exploits sporadic contact opportunities among nodes. We consider opportunistic MANETs where nodes move independently at random over a square of the plane. Nodes exchange data if they are at a distance at most r within each other, where r > 0 is the node transmission radius. The flooding time is the number of time-steps required to broadcast a message from a source node to every node of the network. Flooding time is an important measure of how fast information can spread in dynamic networks. We derive the first upper bound on the flooding time, which is a decreasing function of the maximal speed of the nodes. The bound holds with high probability, and it is nearly tight. Our bound shows that, thanks to node mobility, even when the network is sparse and disconnected, information spreading can be fast. [ABSTRACT FROM AUTHOR]

The unlicensed ISM spectrum is getting crowded by wireless local area network (WLAN) and wireless personal area network (WPAN) users and devices. Spectrum sharing within the same network of devices can be arbitrated by existing MAC protocols, but the coexistence between WPAN and WLAN (e.g., ZigBee and WiFi) remains a challenging problem. The traditional MAC protocols are ineffective in dealing with the disparate transmit-power levels, asynchronous time-slots, and incompatible PHY layers of such heterogeneous networks. Recent measurement studies have shown moderate-to-high WiFi traffic to severely impair the performance of coexisting ZigBee. We propose a novel mechanism, called cooperative carrier signaling (CCS), that exploits the inherent cooperation among ZigBee nodes to harmonize their coexistence with WiFi WLANs. CCS employs a separate ZigBee node to emit a carrier signal (busy tone) concurrently with the desired ZigBee's data transmission, thereby enhancing the ZigBee's visibility to WiFi. It employs an innovative way to concurrently schedule a busy tone and a data transmission without causing interference between them. We have implemented and evaluated CCS on the TinyOS/MICAz and GNURadio/USRP platforms. Our extensive experimental evaluation has shown that CCS reduces collision between ZigBee and WiFi by 50% for most cases, and by up to 90% in the presence of a high-level interference, all at negligible WiFi performance loss. [ABSTRACT FROM PUBLISHER]

Transport Control Protocol (TCP) incast congestion happens in high-bandwidth and low-latency networks when multiple synchronized servers send data to the same receiver in parallel. For many important data-center applications such as MapReduce and Search, this many-to-one traffic pattern is common. Hence TCP incast congestion may severely degrade their performances, e.g., by increasing response time. In this paper, we study TCP incast in detail by focusing on the relationships between TCP throughput, round-trip time (RTT), and receive window. Unlike previous approaches, which mitigate the impact of TCP incast congestion by using a fine-grained timeout value, our idea is to design an Incast congestion Control for TCP (ICTCP) scheme on the receiver side. In particular, our method adjusts the TCP receive window proactively before packet loss occurs. The implementation and experiments in our testbed demonstrate that we achieve almost zero timeouts and high goodput for TCP incast. [ABSTRACT FROM AUTHOR]

Network-wide migrations of a running network, such as the replacement of a routing protocol or the modification of its configuration, can improve the performance, scalability, manageability, and security of the entire network. However, such migrations are an important source of concerns for network operators as the reconfiguration campaign can lead to long, service-disrupting outages. In this paper, we propose a methodology that addresses the problem of seamlessly modifying the configuration of link-state Interior Gateway Protocols (IGPs). We illustrate the benefits of our methodology by considering several migration scenarios, including the addition and the removal of routing hierarchy in a running IGP, and the replacement of one IGP with another. We prove that a strict operational ordering can guarantee that the migration will not create any service outage. Although finding a safe ordering is NP-complete, we describe techniques that efficiently find such an ordering and evaluate them using several real-world and inferred ISP topologies. Finally, we describe the implementation of a provisioning system that automatically performs the migration by pushing the configurations on the routers in the appropriate order while monitoring the entire migration process. [ABSTRACT FROM AUTHOR]

In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless interference models. Given a set \cal Q of periodic aggregation queries, each query Qi\in {\cal Q} has its own period \bf pi and the subset of source nodes \cal Si containing the data. We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query task Qi\in {\cal Q} within a relative delay O(\bf pi) under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay. Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis. [ABSTRACT FROM PUBLISHER]

A wireless transmitter learns of a packet loss and infers collision only after completing the entire transmission. If the transmitter could detect the collision early [such as with carrier sense multiple access with collision detection (CSMA/CD) in wired networks], it could immediately abort its transmission, freeing the channel for useful communication. There are two main hurdles to realize CSMA/CD in wireless networks. First, a wireless transmitter cannot simultaneously transmit and listen for a collision. Second, any channel activity around the transmitter may not be an indicator of collision at the receiver. This paper attempts to approximate CSMA/CD in wireless networks with a novel scheme called CSMA/CN (collision notification). Under CSMA/CN, the receiver uses PHY-layer information to detect a collision and immediately notifies the transmitter. The collision notification consists of a unique signature, sent on the same channel as the data. The transmitter employs a listener antenna and performs signature correlation to discern this notification. Once discerned, the transmitter immediately aborts the transmission. We show that the notification signature can be reliably detected at the listener antenna, even in the presence of a strong self-interference from the transmit antenna. A prototype testbed of 10 USRP/GNU Radios demonstrates the feasibility and effectiveness of CSMA/CN. [ABSTRACT FROM PUBLISHER]

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 intractable (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, depending 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 17\,000 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. [ABSTRACT FROM PUBLISHER]

In cooperative networks, transmitting and receiving nodes recruit neighboring nodes to assist in communication. We model a cooperative transmission link in wireless networks as a transmitter cluster and a receiver cluster. We then propose a cooperative communication protocol for establishment of these clusters and for cooperative transmission of data. We derive the upper bound of the capacity of the protocol, and we analyze the end-to-end robustness of the protocol to data-packet loss, along with the tradeoff between energy consumption and error rate. The analysis results are used to compare the energy savings and the end-to-end robustness of our protocol with two non-cooperative schemes, as well as to another cooperative protocol published in the technical literature. The comparison results show that, when nodes are positioned on a grid, there is a reduction in the probability of packet delivery failure by two orders of magnitude for the values of parameters considered. Up to 80% in energy savings can be achieved for a grid topology, while for random node placement our cooperative protocol can save up to 40% in energy consumption relative to the other protocols. The reduction in error rate and the energy savings translate into increased lifetime of cooperative sensor networks. [ABSTRACT FROM PUBLISHER]

In wireless sensor networks, compromised sensor nodes can inject false data during both data aggregation and data forwarding. The existing false data detection techniques consider false data injections during data forwarding only and do not allow any change on the data by data aggregation. However, this paper presents a data aggregation and authentication protocol, called DAA, to integrate false data detection with data aggregation and confidentiality. To support data aggregation along with false data detection, the monitoring nodes of every data aggregator also conduct data aggregation and compute the corresponding small-size message authentication codes for data verification at their pairmates. To support confidential data transmission, the sensor nodes between two consecutive data aggregators verify the data integrity on the encrypted data rather than the plain data. Performance analysis shows that DAA detects any false data injected by up to compromised nodes, and that the detected false data are not forwarded beyond the next data aggregator on the path. Despite that false data detection and data confidentiality increase the communication overhead, simulation results show that DAA can still reduce the amount of transmitted data by up to 60% with the help of data aggregation and early detection of false data. [ABSTRACT FROM AUTHOR]

MPLS recovery mechanisms are increasing in popularity because they can guarantee fast restoration and high QoS assurance. Their main advantage is that their backup paths are established in advance, before a failure event takes place. Most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. However, this so-called Spare Capacity Allocation (SCA) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. In this paper, we present a comprehensive study on restorable throughput maximization in MPLS networks. We present the first polynomial-time algorithms for the splittable version of the problem. For the unsplittable version, we provide a lower bound for the approximation ratio and propose an approximation algorithm with an almost identical bound. We present an efficient heuristic which is shown to have excellent performance. One of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice. [ABSTRACT FROM AUTHOR]

This paper develops a simple and accurate stochastic model for the steady-state throughput of a TCP NewReno bulk data transfer as a function of round-trip time and loss behavior. Our model builds upon extensive prior work on TCP Reno throughput models but differs from these prior works in three key aspects. First, our model introduces an analytical characterization of the TCP NewReno fast recovery algorithm. Second, our model incorporates an accurate formulation of NewReno's timeout behavior. Third, our model is formulated using a flexible two-parameter loss model that can better represent the diverse packet loss scenarios encountered by TCP on the Internet. We validated our model by conducting a large number of simulations using the ns-2 simulator and by conducting emulation and Internet experiments using a NewReno implementation in the BSD TCP/IP protocol stack. The main findings from the experiments are: 1) the proposed model accurately predicts the steady-state throughput for TCP NewReno bulk data transfers under a wide range of network conditions; 2) TCP NewReno significantly outperforms TCP Reno in many of the scenarios considered; and 3) using existing TCP Reno models to estimate TCP NewReno throughput may introduce significant errors. [ABSTRACT FROM AUTHOR]

Short TCP flows may suffer significant response-time performance degradations during network congestion. Unfortunately, this creates an incentive for misbehavior by clients of interactive applications (e.g., gaming, telnet, web): to send "dummy" packets into the network at a TCP-fair rate even when they have no data to send, thus improving their performance in moments when they do have data to send. Even though no "law" is violated in this way, a large-scale deployment of such an approach has the potential to seriously jeopardize one of the core Internet's principles--statistical multiplexing. We quantify, by means of analytical modeling and simulation, gains achievable by the above misbehavior. Our research indicates that easy-to-implement application-level techniques are capable of dramatically reducing incentives for conducting the above transgressions, still without compromising the idea of statistical multiplexing. [ABSTRACT FROM AUTHOR]

In this paper, we provide the scaling laws for the transport capacity of a wide class of mobile wireless ad hoc networks. Our analysis generalizes previous results obtained under restrictive assumptions on the node mobility process and overall node density over the network area. The broader family of mobile networks that we consider is able to account for many important characteristics usually recognized in real traces of both human and vehicular mobility. In particular, we consider clustered networks of heterogeneous nodes, in which the shape of the spatial distribution of each node around one or more home-points plays a fundamental role in determining the overall transport capacity. We identify different operational regimes that arise within our general class of mobile networks, and for each regime we characterize the asymptotic network capacity. [ABSTRACT FROM AUTHOR]

As a result of perceived limitations of TCP/IP in supporting high-throughput applications, significant efforts have recently been devoted to develop alternative architectures based on the concept of advance channel reservation. In this paper, we develop a polynomial-time algorithmic framework, called graded channel reservation (GCR), to support the implementation of such architectures. This framework enables users to specify minimum bandwidth and duration requirements for their connections. Upon receiving a request, GCR returns the highest graded path, selected according to a general, multicriteria optimization objective. In particular, if the optimization criterion is delay, we prove that GCR returns the earliest time available to establish the connection. Thereafter, we present a generalization of GCR, called GCRswitch' that is capable of supporting path switching throughout a connection. We present practical methods for minimizing or limiting the number of path switches. Through extensive simulations, we evaluate the performance of GCR and its variants under various topological settings and applications workload. Our results show that, for certain traffic parameters, optimized path selection combined with path switching can reduce the average delay of requests by an order of magnitude and increase the maximum sustainable load by as much as 50%. [ABSTRACT FROM AUTHOR]

The BitTorrent (BT) file sharing protocol is very popular due to its scalability property and the built-in incentive mechanism to reduce free-riding. However, in designing such P2P file sharing protocols, there is a fundamental trade-off between keeping fairness and providing good performance. In particular, the system can either keep peers (especially those resourceful ones) in the system for as long as possible so as to help the system to achieve better performance, or allow more resourceful peers to finish their download as quickly as possible so as to achieve fairness. The current BT protocol represents only one possible implementation in this whole design space. The objective of this paper is to characterize the design space of BT-like protocols. The rationale for considering fairness in the P2P file sharing context is to use it as a measure of willingness to provide service. We show that there is a wide range of design choices, ranging from optimizing the performance of file download time, to optimizing the overall fairness measure. More importantly, we show that there is a simple and easily implementable design knob so that the system can operate at a particular point in the design space. We also discuss different algorithms, ranging from centralized to distributed, in realizing the design knob. Performance evaluations are carried out, both via simulation and network measurement, to quantify the merits and properties of the BT-like file sharing protocols. [ABSTRACT FROM AUTHOR]

We propose a model-based analytic approach for evaluating the overall efficacy of FEC coding combined with interleaving in combating packet losses in IP networks. In particular, by modeling the network path in terms of a single bottleneck node, described as a C/M/1/K queue, we develop a recursive procedure for the exact evaluation of the packet-loss statistics for general arrival processes, based on the framework originally introduced by Cidon et al., 1993. To include the effects of interleaving, we incorporate a discrete-time Markov chain (DTMC) into our analytic framework. We study both single-session and multiple-session scenarios, and provide a simple algorithm for the more complicated multiple-session scenario. We show that the unified approach provides an integrated framework for exploring the tradeoffs between the key coding parameters; specifically, interleaving depths, channel coding rates and block lengths. The approach facilitates the selection of optimal coding strategies for different multimedia applications with various user quality-of-service (Q0S) requirements and system constraints. We also provide an information-theoretic bound on the performance achievable with FEC coding in IP networks. [ABSTRACT FROM AUTHOR]

As service providers move more applications to their IP/MPLS (Multiple Protocol Label Switching [1]) backbone net- works, rapid restoration upon failure becomes more and more crucial. Recently MPLS fast reroute has attracted lots of attention as it was designed to meet the needs of real-time applications, such as voice over IP. MPLS fast reroute achieves rapid restoration by computing and signaling backup label switched path (LSP) tunnels in advance and re-directing traffic as close to failure point as possible. To provide a guarantee of bandwidth protection, extra bandwidth has to be reserved on backup paths. Using path merging technique as described in IETF RFC 4090 only, the network is able to share some bandwidth on common links among backup paths of the same service LSP, i.e., so-called intra-sharing. But no solution is provided on how to share bandwidth among backup paths of different service LSPs, i.e., so-called inter-sharing. In this paper, we provide an efficient distributed bandwidth management solution. This solution allows bandwidth sharing among backup paths of the same and different service LSPs, i.e., both intra-sharing and inter-sharing, with a guarantee of bandwidth protection for any single node/link failure. We also propose an efficient algorithm for backup path selection with the associated signaling extensions for additional information distribution and collection. To evaluate our schemes, we compare them via simulation with the basic MPLS fast reroute proposal, IETF RFC 4090, on two networks. Our simulation results show that using our bandwidth management scheme can significantly reduce restoration overbuild from about 250% to about 100%, and our optimized backup path selection can further reduce restoration overbuild to about 60%. [ABSTRACT FROM AUTHOR]

In this paper, we propose a simple protocol for building heterogeneous unstructured peer-to-peer (P2P) networks. The protocol consists of two parts—the joining process and the rebuilding process. The basic idea for the joining process is to use a random walk to assist new incoming peers in selecting their suitable neighbors in terms of capacity and connectivity to achieve load-balancing. The rebuilding process specifies how the nodes should react when they lose links. In particular, we examine two representative schemes, namely the probabilistic-rebuilding scheme and the adaptive-rebuilding scheme. Furthermore, we provide a detailed analysis to investigate our proposed protocol under any heterogenous P2P environment. We prove that the topology structure of the P2P network depends heavily on the node heterogeneity. The analytical results are validated by the simulations. Our framework provides a guideline to engineer and optimize a P2P network in different respects under a heterogeneous environment. The ultimate goal of this paper is to stimulate further research to explore the fundamental issues in heterogeneous P2P networks. [ABSTRACT FROM AUTHOR]

In optical burst switching (OBS) networks, a key problem is to schedule as many bursts as possible on wavelength channels so that the throughput is maximized and the burst loss is minimized. Most of the current research on OBS has been concentrated on reducing burst loss in an "average-case" sense, and little effort has been devoted to understanding the worst case performance. Since OBS itself is an open-loop control system, it may exhibit a worst case behavior when adversely synchronized. On the other hand, most commercial systems require an acceptable worst case performance. In this paper, we use competitive analysis to analyze the worst case performance of a large set of scheduling algorithms, called best-effort online scheduling algorithms, for OBS networks and establish a number of interesting upper and lower bounds on the performance of such algorithms. Our analysis shows that the performance of any best-effort online algorithm is closely related to a few factors, such as the range of offset time, maximum-to-minimum burst-length ratio, and the number of data channels. A surprising discovery is that the worst case performance of any best-effort online scheduling algorithm is primarily determined by the maximum-to-minimum burst-length ratio, followed by the range of offset time. Furthermore, if all bursts have the same burst length and offset time, all best-effort online scheduling algorithms generate the same optimal solution, regardless of how different they may look. Our analysis can also be extended to some non-best-effort online scheduling algorithms, such as the well-known Horizon algorithm, and establish similar bounds. Based on the analytic results, we give guidelines for several widely discussed OBS problems, including burst assembly, offset time setting, and scheduling algorithm design, and propose a new channel reservation protocol called virtual fixed offset-time (VFO) to improve the worst case performance. Our simulation shows that VFO can also reduce the average burst loss rate. [ABSTRACT FROM AUTHOR]

In this paper, we present experimental results evaluating the performance of the scalable-TCP, HS-TCP, BIC-TCP, FAST-TCP, and H-TCP proposals in a series of benchmark tests. In summary, we find that both Scalable-TCP and FAST-TCP consistently exhibit substantial unfairness, even when competing flows share identical network path characteristics. Scalable-TCP, HS-TCP, FAST-TCP, and BIC-TCP all exhibit much greater RTT unfairness than does standard TCP, to the extent that long RTT flows may be completely starved of bandwidth. Scalable-TCP, HS-TCP, and BIC-TCP all exhibit slow convergence and sustained unfairness following changes in network conditions such as the start-up of a new flow. FAST-TCP exhibits complex convergence behavior. [ABSTRACT FROM AUTHOR]

Supporting fast restoration for general mesh topologies with minimal network over-build is a technically challenging problem. Traditionally, ring-based SONET networks have offered close to 50 ms restoration at the cost of requiring 100% over-build. Recently, fast (local) reroute has gained momentum in the context of MPLS networks. Fast reroute, when combined with pre-provisioning of protection capacities and bypass tunnels, enables faster restoration times in mesh networks. Pre-provisioning has the additional advantage of greatly simplifying network routing and signaling. Thus, even for protected connections, online routing can now be oblivious to the offered protection, and may only involve single shortest path computations. In this paper, we are interested in the problem of reserving the least amount of the network capacity for protection, while guaranteeing fast (local) reroute-based restoration for all the supported connections. We show that the problem is NP-complete, and we present efficient approximation algorithms for the problem. The solution output by our algorithms is guaranteed to use at most twice the protection capacity, compared to any optimal solution. These guarantees are provided even when the protection is for multiple link failures. In addition, the total amount of protection capacity reserved by these algorithms is just a small fraction of the amount reserved by existing ring-based schemes (e.g., SONET), especially on dense networks. The presented algorithms are computationally efficient, and can even be implemented on the network elements. Our simulation, on some standard core networks, show that our algorithms work well in practice as well. [ABSTRACT FROM AUTHOR]

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees. [ABSTRACT FROM AUTHOR]

Link failures are part of the day-to-day operation of a network due to many causes such as maintenance, faulty interfaces, and accidental fiber cuts. Commonly deployed link state routing protocols such as OSPF react to link failures through global link state advertisements and routing table recomputations causing significant forwarding discontinuity after a failure. Careful tuning of various parameters to accelerate routing convergence may cause instability when the majority of failures are transient. To enhance failure resiliency without jeopardizing routing stability, we propose a local rerouting based approach called failure insensitive routing. The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. With this approach, when no more than one link failure notification is suppressed, a packet is guaranteed to be forwarded along a loop-free path to its destination if such a path exists. This paper demonstrates the feasibility, reliability, and stability of our approach. [ABSTRACT FROM AUTHOR]

In multi-hop ad hoc networks, stations may pump more traffic into the networks than can be supported, resulting in high packet-loss rate, re-routing instability and unfairness problems. This paper shows that controlling the offered load at the sources can eliminate these problems. To verify the simulation results, we set up a real 6-node multi-hop network. The experimental measurements confirm the existence of the optimal offered load. In addition, we provide an analysis to estimate the optimal offered load that maximizes the throughput of a multi-hop traffic flow. We believe this is a first paper in the literature to provide a quantitative analysis (as opposed to simulation) for the impact of hidden mires and signal capture on sustainable throughput. The analysis is based on the observation that a large-scale 802.11 network with hidden nodes is a network in which the carrier-sensing capability breaks down partially. Its performance is therefore somewhere between that of a carrier-sensing network and that of an Aloha network. Indeed, our analytical closed-form solution has the appearance of the throughput equation of the Aloha network. Our approach allows one to identify whether the performance of an 802.11 network is hidden-node limited or spatial-reuse limited. [ABSTRACT FROM AUTHOR]

This paper investigates the existence of scalable protocols that can achieve the capacity limit of c/√N per source-destination pair in a large wireless network of N nodes when the buffer space of each node does not grow with the size of the network N. It is shown that there is no end-to-end-protocol capable of carrying out the limiting throughput of c/√N with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of c/√ N log N when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available. [ABSTRACT FROM AUTHOR]

This paper examines some issues that affect the efficiency and fairness of the Transmission Control Protocol (TCP), the backbone of Internet protocol communication, in multi-hops satellite network systems. It proposes a scheme that allows satellite systems to automatically adapt to any change in the number of active TCP flows due to handover occurrence, the free buffer size, and the bandwidth-delay product of the network. The proposed scheme has two major design goals: increasing the system efficiency, and improving its fairness. The system efficiency is controlled by matching the aggregate traffic rate to the sum of the link capacity and total buffer size. On the other hand, the system mm-max fairness is achieved by allocating bandwidth among individual flows in proportion with their RTTs. The proposed scheme is dubbed Recursive, Explicit, and Fair Window Adjustment (REF WA). Simulation results elucidate that the REFWA scheme substantially improves the system fairness, reduces the number of packet drops, and makes better utilization of the bottleneck link. The results demonstrate also that the proposed scheme works properly in more complicated environments where connections traverse multiple bottlenecks and the available bandwidth may change over data transmission time. [ABSTRACT FROM AUTHOR]

The paper focuses on the assignment of a common bandwidth resource to TCP connections over a satellite channel. The connections are grouped according to their source-destination pairs, which correspond to the up- and down-link channels traversed, and each group may experience different fading conditions. By exploiting the tradeoff between bandwidth and channel redundancy (as determined by bit and coding rates) in the maximization of TCP goodput, an overall optimization problem is constructed, which can be solved by numerical techniques. Different relations between goodput maximization and fairness of the allocations are investigated, and a possible pricing scheme is proposed. The allocation strategies are tested and compared in a fading environment, first under static conditions, and then in a real dynamic scenario. The goodput-fairness optimization allows significant gains over bandwidth allocations only aimed at keeping the channel bit error rate below a given threshold in all fading conditions. [ABSTRACT FROM AUTHOR]

Concurrent multipath transfer (CMT) uses the Stream Control Transmission Protocol's (SCTP) multihoming feature to distribute data across multiple end-to-end paths in a multihomed SCTP association. We identify three negative side-effects of reordering introduced by CMT that must be managed before efficient parallel transfer can be achieved: (1) unnecessary fast retransmissions by a sender; (2) overly conservative congestion window (cwnd) growth at a sender; and (3) increased ack traffic due to fewer delayed acks by a receiver. We propose three algorithms which augment and/or modify current SCTP to counter these side-effects. Presented with several choices as to where a sender should direct retransmissions of lost data, we propose five retransmission policies for CMT. We demonstrate spurious retransmissions in CMT with all five policies and propose changes to CMT to allow the different policies. CMT is evaluated against AppStripe, which is an idealized application that stripes data over multiple paths using multiple SCTP associations. The different CMT retransmission policies are then evaluated with varied constrained receive buffer sizes. In this foundation work, we operate under the strong assumption that the bottleneck queues on the end-to-end paths used in CMT are independent. [ABSTRACT FROM AUTHOR]

We present a closed-loop architecture and protocols for rapid dynamic spreading gain adaptation and fast feedback between a transmitter and a receiver communicating with each other in CDMA networks. These protocols and architecture do not require the transfer of an explicit control message indicating the change of CDMA spreading gain from transmitter to receiver. Also, with these protocols, the transmitter can change the spreading gain symbol-by-symbol as opposed to frame-by-frame, and feedback information (e.g., the fast-varying channel condition) can be exchanged almost as frequently as the symbol rate. Thus, adaptation to the time-varying channel Conditions of wireless networks and/or to the rate variation of traffic can be much faster than is possible with the existing frame-by-frame approach. [ABSTRACT FROM AUTHOR]

In multiparty MAC, a sender needs to transmit each packet to a set of receivers within its transmission range. Band-width efficiency of wireless multiparty MAC can be improved substantially by exploiting the fact that several receivers can be reached at the MAC layer by a single transmission. Multiparty communication, however, requires new design paradigms since systematic design techniques that have been used effectively in unicast and wireline multicast do not apply. For example, a transmission policy that maximizes the stability region of the network need not maximize the network throughput. Therefore, the objective is to design a policy that maximizes the system throughput subject to maintaining stability. We present a sufficient condition that can be used to establish the throughput optimality of a stable transmission policy. We subsequently design a distributed adaptive stable policy that allows a sender to decide when to transmit using simple computations. The computations are based only on limited information about current transmissions in the sender's neighborhood. Even though the proposed policy does not use any network statistics, it attains the same throughput as an optimal offline stable policy that uses in its decision process past, present, and even future network states. We prove the throughput optimality of this policy using the sufficient condition and the large deviation results. We present a MAC protocol for acquiring the local information necessary for executing this policy, and implement it in ns-2. The performance evaluations demonstrate that the optimal policy significantly outperforms the existing multiparty schemes in ad hoc networks. [ABSTRACT FROM AUTHOR]

Incremental deployment of a new network service or protocol is typically a hard problem, especially when it has to be deployed at the routers. First, an incrementally deployable version of the protocol may be needed. Second, a systematic study of the performance impact of incremental deployment is needed to evaluate potential deployment strategies. Choosing the wrong strategy can be disastrous, as it may inhibit reaping the benefits of an otherwise robust service and prevent widespread adoption. We focus on two router-assisted reliable multicast protocols, namely PGM and LMS. Our evaluation consists of three parts: 1) selection and classification of deployment strategies; 2) definition of performance metrics; and 3) systematic evaluation of deployment strategies. Our study yields several interesting results: 1) the performance of different deployment strategies varies widely, for example, with some strategies, both PGM and LMS approach full deployment performance with as little as 5% of the routers deployed; other strategies require up to 80% deployment to approach the same level; 2) our sensitivity analysis reveals relatively small variation in the results in most cases; and 3) the impact associated with partial deployment is different for each of these protocols; PGM tends to impact the network, whereas LMS the endpoints. Our study clearly demonstrates that the choice of a strategy has a substantial impact on performance. [ABSTRACT FROM AUTHOR]

Internet quality of service (QoS) is still a highly debated topic for more than fifteen years. Even with the large variety of QoS proposals and the impressive research advances, there is little deployment yet of network layer QoS technology. One specific problem domain is QoS signalling, which has recently attracted increasing attention to bring forward new standardization approaches. In this paper, an extensive study of RSVP is presented, covering protocol design, software design, and performance aspects of the basic version of RSVP and of certain standardized and experimental extensions. This work is based on and presents the experience from implementing RSVP for UNIX systems and the ns-2 simulation environment. The implementation includes a variety of protocol extensions and incorporates several internal improvements. It has been subject to extensive functional and performance evaluations, the results of which are reported here. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the performance of TCP enhancements for a hybrid terrestrial-satellite network. While a large body of literature exists regarding modeling TCP performance for the wired Internet, and recently over a single-hop wireless link, the literature is very sparse on TCP analysis over a hybrid wired-wireless (multi-hop) path. We seek to make a contribution to this problem (where the wireless segment is a satellite uplink) by deriving analytical estimates of TCP throughput for two widely deployed approaches: TCP splitting and E2E (End-to-End) TCP with link layer support as a function of key parameters such as terrestrial/satellite propagation delay, segment loss rate and buffer size. Our analysis is supported by simulations; throughput comparisons indicate superiority of TCP splitting over E2E scheme in most cases. However, in situations where end-to-end delay is dominated by terrestrial portion and buffering is very limited at intermediate node, E2E achieves higher throughput than TCP splitting. [ABSTRACT FROM AUTHOR]

Service prioritization among different traffic classes is an important goal for the Internet. Conventional approaches to solving this problem consider the existing best-effort class as the low-priority class, and attempt to develop mechanisms that provide ‘better-than-best-effort’ service. In this paper, we explore the opposite approach, and devise a new distributed algorithm to realize a low-priority service (as compared to the existing best effort) from the network endpoints. To this end, we develop TCP Low Priority (TCP-LP), a distributed algorithm whose goal is to utilize only the excess network bandwidth as compared to the ‘fair share’ of bandwidth as targeted by TCP. The key mechanisms unique to TCP-LP congestion control are the use of one-way packet delays for early congestion indications and a TCP-transparent congestion avoidance policy. The results of our simulation and Internet experiments show that: 1) TCP-LP is largely non-intrusive to TCP traffic; 2) both single and aggregate TCP-LP flows are able to successfully utilize excess network bandwidth; moreover, multiple TCP-LP flows share excess bandwidth fairly; 3) substantial amounts of excess bandwidth are available to the low-priority class, even in the presence of ‘greedy’ TCP flows; 4) the response times of web connections in the best-effort class decrease by up to 90% when long-lived bulk data transfers use TCP-LP rather than TCP; 5) despite their low-priority nature, TCP-LP flows are able to utilize significant amounts of available bandwidth in a wide-area network environment. [ABSTRACT FROM AUTHOR]

We study TCP performance over the wireless links deploying a wireless rate-control technique, whose link characteristics are identified by variable link rate and bursty transmission error. We present a TCP enhancement scheme, called rate-adaptive snoop (RA-Snoop). RA-Snoop caches TCP packets selectively based on the wireless channel condition and the cached packets are retransmitted locally over the wireless link in case corruption loss is detected. In addition, for effective adaptation to variable bandwidth, RA-Snoop calculates the window feedback based on the bandwidth-delay product estimation and the queue level, then conveys this feedback information on the receiver's advertised window field in the acknowledgements returning to TCP sources. We compare the performance of RA-Snoop with that of existing schemes in the aspect of goodput and fairness. Results from simulations reveal that RA-Snoop achieves significant improvements over the existing schemes for various traffic scenarios. [ABSTRACT FROM AUTHOR]

The retransmission timeout (RTO) algorithm of Transmission Control Protocol (TCP), which sets a dynamic upper bound on the next round-trip time (RTT) based on past RTTs, plays an important role in reliable data transfer and congestion control of the Internet. A rigorous theoretical analysis of the RTO algorithm is important in that it provides insight into the algorithm and prompts optimal design strategies. Nevertheless, such an analysis has not been conducted to date. This paper presents such an analysis from a statistical approach. We construct an auto-regressive (AR) model for the RTT processes based on experimental results that indicate: 1) RTTs along a certain path in the Internet can be modeled by a shifted Gamma distribution and 2) the temporal correlation of RTTs decreases quickly with lag. This model is used to determine the average reaction time and premature timeout probability for the RTO algorithm. We derive a closed-form expression for the first measure and a formula for numerically calculating the second. Both measures are validated through tests on simulated and real RTT data. The theoretical analysis strengthens a number of observations reported in past experiment-oriented studies. [ABSTRACT FROM AUTHOR]

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-or-order acknowledgments) has no effect on TCP-PR's 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. In 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. Furthermore, TCP-PR only requires changes to the TCP sender side making it easier to deploy. [ABSTRACT FROM AUTHOR]

We study network protocol system monitoring for fault detection using a formal technique of passive testing that is a process of detecting system faults by passively observing its input/output behaviors without interrupting its normal operations. After describing a formal model of event-driven extended finite state machines, we present two algorithms for passive testing of protocol system control and data portions. Experimental results on OSPF and TCP are reported. [ABSTRACT FROM AUTHOR]

To disseminate data to a heterogeneous body of receivers efficiently, congestion control protocols for IP multicast compose a session from several multicast groups and prescribe guidelines that enable each receiver to subscribe to an appropriate subset of the groups. However, a misbehaving receiver can ignore the group subscription rules and inflate its subscription to acquire unfairly high throughput. In this paper, we present the first solution for the problem of inflated subscription. Our design guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access)—a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture)—a generic architecture for key-based group access at edge routers. We apply DELTA and SIGMA to derive robust versions of prominent RLM and FLID-DL protocols. [ABSTRACT FROM AUTHOR]

We introduce Probabilistic Resilient Multicast (PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols especially when there are high packet losses and host failures. Through detailed analysis in this paper, we show that this loss recovery technique has efficient scaling properties—the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10 000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (>97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1%–5 %) and high topology change rates (5 changes per second) while incurring very low overheads (<5%). [ABSTRACT FROM AUTHOR]

Next-generation SONET/SDH technologies—namely, generic framing procedure, virtual concatenation, and link-capacity-adjustment scheme—enable network operators to provide integrated data and voice services over their legacy SONET/SDH infrastructure to generate new revenue. An important open research problem on data over SONET/SDH (DOS) is survivability: SONET automatic protection switching is too resource inefficient for data services, and the protection mechanisms of data networks are too slow for mission-critical applications. We propose two approaches for provisioning survivable DoS connections. Our approaches exploit the tradeoff between resource overbuild and fault-recovery time while utilizing the inverse-multiplexing capability of virtual concatenation to increase backup sharing. Our results show that one approach achieves low resource overbuild and much faster fault recovery than that of data networks, and the other approach achieves fast fault recovery comparable to SONET 50-ms protection (for typical U.S. backbone networks) while still achieving modest backup sharing. We further investigate the tradeoff between network blocking performance and network control and management complexity resulting from the number of paths M a connection can be inversely multiplexed onto: larger M leads to more freedom in routing and better network performance but increases network control and management complexity. Our results indicate that the network blocking performance for small values of M (e.g., M = 2 for some representative backbone network topologies) is almost as good as the case in which M is infinity. [ABSTRACT FROM AUTHOR]

When many parties share network resources on an overlay network, mechanisms must exist to allocate the resources and protect the network from overload. Compared to large physical networks such as the Internet, in overlay networks the dimensions of the task are smaller, so new and possibly more effective techniques can be used. In this work we take a fresh look at the problem of flow control in multisender multigroup reliable multicast and unicast and explore a cost-benefit approach that works in conjunction with Internet standard protocols such as TCP. In contrast to existing window-based flow control schemes, we avoid end-to-end per sender or per group feedback by looking only at the state of the virtual links between participating nodes. This produces control traffic proportional only to the number of overlay network links and independent of the number of groups, senders, or receivers. We show the effectiveness of the resulting protocol through simulations and validate the simulations with live Internet experiments. We demonstrate near-optimal utilization of network resources, fair sharing of individual congested links, and quick adaptation to network changes. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are event-based systems that rely on the collective effort of several microsensor nodes. Reliable event detection at the sink is based on collective information provided by source nodes and not on any individual report. However, conventional end-to-end reliability definitions and solutions are inapplicable in the WSN regime and would only lead to a waste of scarce sensor resources. Hence, the WSN paradigm necessitates a collective event-to-sink reliability notion rather than the traditional end-to-end notion. To the best of our knowledge, reliable transport in WSN has not been studied from this perspective before. In order to address this need, a new reliable transport scheme for WSN, the event-to-sink reliable transport (ESRT) protocol, is presented in this paper. ESRT is a novel transport solution developed to achieve reliable event detection in WSN with minimum energy expenditure. It includes a congestion control component that serves the dual purpose of achieving reliability and conserving energy. Importantly, the algorithms of ESRT mainly run on the sink, with minimal functionality required at resource constrained sensor nodes. ESRT protocol operation is determined by the current net- work state based on the reliability achieved and congestion condition in the network. This self-configuring nature of ESRT makes it robust to random, dynamic topology in WSN. Furthermore, ESRT can also accommodate multiple concurrent event occurrences in a wireless sensor field. Analytical performance evaluation and simulation results show that ESRT converges to the desired reliability with minimum energy expenditure, starting from any initial network state. [ABSTRACT FROM AUTHOR]