2311753
Fundamental trade-offs in aggregate packet scheduling
In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.
3065647
A core stateless bandwidth broker architecture for scalable support of guaranteed services
We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.
14141879
Improving VoIP quality through path switching
The current best-effort Internet cannot readily provide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the quality of VoIP applications, and demonstrate its feasibility through the design and implementation of a prototype gateway. We argue for an application-driven path switching system that accounts for both network path characteristics and application-specific factors (e.g., codec algorithms, playout buffering schemes). We also develop an application path quality estimator based on the ITU-T E-model for voice quality assessment, and an application-driven path switching algorithm that dynamically adapts the time scales over which path switching decisions are made to maximize voice quality. Through network emulation and experiments over a wide-area multi-homed test bed, we show that, with sufficient path diversity, path switching can yield meaningful improvements in voice quality. Hence by exploiting the inherent path diversity of the Internet, application-driven path switching is a viable option in providing quality-of-service to applications.
16878671
Full-sharing: efficient bandwidth scheduling for video streaming over broadband cable networks (BCNs)
Broadband Cable Networks (BCNs) bring high-speed Internet access to home and make emerging multimedia streaming applications feasible. However, bandwidth contention is still a challenging problem in providing efficient IP-based Video-On-Demand (VOD) service on BCNs, due to the lack of effective approaches to exploit the unique characteristics of BCNs. To address the bandwidth contention issue, we propose an efficient video scheduling technique, called full-sharing scheduling in this paper. This technique fully exploits the unique characteristics of BCNs to reduce the bandwidth consumption of video sessions sharing a cable channel of fixed capacity, thereby maximizing the number of simultaneous video sessions on the single channel. Furthermore, we analyze the expected bandwidth and the session blocking probability of a video under the full-sharing scheduling. Based on this analysis, we design an efficient video assignment mechanism for maximizing the profit of a VOD system in scheduling videos on BCNs. Through both analysis and simulation, we show that our approach minimizes the bandwidth consumption of video sessions compared with the previous approaches and has significant advantages on BCNs. The proposed approach is also directly applicable on other broadcast/multicast networks in which clients have sufficient buffer and downstream bandwidth, e.g., satellite broadband networks.
5719748
Leopard: A Locality Aware Peer-to-Peer System with No Hot Spot
Recent research [7,12,2] has shown that Internet hosts can be efficiently (i.e., without excessive measurements) mapped to a virtual (Euclidean) coordinate system, where the geometric distance between any two nodes in this virtual space approximates their real IP network distance (latency). Based on this result, in this paper, we propose an alternative approach that inherently incorporates a virtual coordinate system into a P2P network. In our system, called Leopard, a node is assigned a coordinate in the so-called node geo space as it joins the network, and obtains neighbor relationships that reflects network proximity from the beginning. The object id space and the node geo space are then “weaved” together via a novel technique called geographically-scoped hashing. Through analysis and simulation, we show three major desirable properties of Leopard to exemplify the power of this paradigm shift: i) a constant routing stretch, i.e., IP level network latency of object look-up is proportional to the distance between a requesting node and the target object; ii) always locates a near-by copy when multiple copies exist; and iii) effectively handles “flash crowd” traffic with near optimal load balancing.
5876943
Adaptive packet sampling for flow volume measurement
Traffic measurement and monitoring are an important component of network management and traffic engineering. With high-speed Internet backbone links, efficient and effective packet sampling techniques for traffic measurement and monitoring are not only desirable, but also increasingly becoming a necessity. Since the utility of sampling depends on the accuracy and economy of measurement, it is important to control sampling error. In this paper we propose and analyze an adaptive, stratified random packet sampling technique for flow-level traffic measurement. In particular, we address the theoretical and practical issues involved. Through theoretical studies and experiments, we demonstrate that the proposed sampling technique provides unbiased estimation of flow size with controllable error bound, in terms of both packet and byte counts for elephant flows, while avoiding excessive oversampling.
46660413
Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability
In this paper we study optimal scheduling algorithms to resolve output contentions in time slotted WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion with arbitrary conversion capability, as it is easier to implement and more cost effective than full range wavelength conversion, and also includes full range wavelength conversion as a special case. We consider the conversion scheme in which each wavelength can be converted to multiple wavelengths belongs to an interval and the intervals for different wavelengths are “ordered”. To be specific, the conversion range of λ i can be written as [begin(i), end(i)], where begin(i) and end(i) are positive integers and if i < j then begin(i) ≤ begin(j) and end(i) ≤ end(j). We will present linear time optimal scheduling algorithms for both buffered and unbuffered WDM switches. We will also give performance studies of these switches when scheduled by these algorithms.
17015903
Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability
All optical networking is a promising candidate for supporting high-speed communications because of the huge bandwidth of optics. In this paper, we study optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability. We formalize the problem of maximizing network throughput and minimizing total delay as a problem of finding an optimal matching in a weighted bipartite graph. We then give a simple algorithm, called the Scan and Swap Algorithm, that finds the optimal matching in O(kB) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to directly adopting other existing algorithms that need at least O(k/sup 2/N/sup 2/ + k/sup 2/BN) time, where N is the number of input fibers.
6801587
Performance analysis of k-fold multicast networks
Multicast involves transmitting information from a single source to multiple destinations, and is an important operation in high-performance networks. A k-fold multicast network was recently proposed as a cost-effective solution to providing better quality-of-service functions in supporting real-world multicast applications. To give a quantitative basis for network designers to determine the suitable value of system parameter k under different traffic loads, in this paper, we propose an analytical model for the performance of k-fold multicast networks under Poisson traffic. We first give the stationary distribution of network states, and then derive the throughput and blocking probability of the network. We also conduct extensive simulations to validate the analytical model, and the results show that the analytical model is very accurate under the assumptions made. The analytical and simulation results reveal that by increasing the fold of the network, network throughput increases very fast when the fanouts of multicast connections are relatively small, compared with the network size.
14083998
Towards CST-enhanced summarization
In this paper, we propose to enhance the process of automatic extractive multi-document text summarization by taking into account cross-document structural relationships as posited in Cross-document Structure Theory (CST). An arbitrary multidocument extract can be CST-enhanced by replacing low-salience sentences with other sentences that increase the total number of CST relationships included in the summary. We show that CST-enhanced summaries outperform their unmodified counterparts using the relative utility evaluation metric. We also show that the effect of a CST relationship on an extract depends on its type.
22666885
A single-spike model of predictive coding
Abstract The standard cortical model assumes that the meaning of a neuron's signal is contained in its firing rate. While that model has been used to interpret a voluminous amount of experimental data, it does not address the question of timing, or how recipient neurons can decode this signal in time to predict behavioral results. We propose a model based on coincident firing of large groups of neurons. We show using an example of predictive coding, how the cortex can support vast amounts of non-interfering parallel computation.