2079839
Understanding CHOKe
A recently proposed active queue management, CHOKe, is stateless, simple to implement, yet surprisingly effective in protecting TCP from UDP flows. As UDP rate increases, even though the number of UDP packets in the queue rises, its bandwidth share eventually drops to zero, in stark contrast to the behavior of a regular FIFO buffer. We derive a detailed model of CHOKe that accurately predicts this, and other behaviors of CHOKe, and validate the model with simulations. Its key features are the incorporation of the feedback equilibrium of TCP with dropping probability and the spatial characteristics of the queueing process. CHOKe produces a "leaky buffer" where packets can be dropped as they move toward the head of the queue. This leads to a spatially nonuniform distribution of packets and their velocity, and makes it possible for a flow to simultaneously maintain a large number of packets in the queue and receive a vanishingly small bandwidth share. This is the main mechanism through which CHOKe protects TCP from UDP flows.
61565821
Modelling and stability of FAST TCP
We introduce a discrete-time model of FAST TCP that fully captures the effect of self-clocking and compare it with the traditional continuous-time model. While the continuous-time model predicts instability for homogeneous sources sharing a single link when feedback delay is large, experiments suggest otherwise. Using the discrete-time model, we prove that FAST TCP is locally asymptotically stable in general networks when all sources have a common round-trip feedback delay, no matter how large the delay is. We also prove global stability for a single bottleneck link in the absence of feedback delay. The techniques developed here are new and applicable to other protocols.
6239028
Understanding CHOKe: throughput and spatial characteristics
A recently proposed active queue management, CHOKe, is stateless, simple to implement, yet surprisingly effective in protecting TCP from UDP flows. We present an equilibrium model of TCP/CHOKe. We prove that, provided the number of TCP flows is large, the UDP bandwidth share peaks at (e+1)/sup -1/=0.269 when UDP input rate is slightly larger than link capacity, and drops to zero as UDP input rate tends to infinity. We clarify the spatial characteristics of the leaky buffer under CHOKe that produce this throughput behavior. Specifically, we prove that, as UDP input rate increases, even though the total number of UDP packets in the queue increases, their spatial distribution becomes more and more concentrated near the tail of the queue, and drops rapidly to zero toward the head of the queue. In stark contrast to a nonleaky FIFO buffer where UDP bandwidth shares would approach 1 as its input rate increases without bound, under CHOKe, UDP simultaneously maintains a large number of packets in the queue and receives a vanishingly small bandwidth share, the mechanism through which CHOKe protects TCP flows.
12186597
A Power-Saving Multi-Radio Multi-Channel MAC Protocol for Wireless Local Area Networks
Opportunistic spectrum access and adaptive power management are effective techniques to improve throughput, delay performance, and energy efficiency for wireless networks. In this paper, we consider the joint design of opportunistic spectrum access and adaptive power management under the setting of multi-radio nodes and multi-channel wireless local area networks (WLANs) under the distributed coordination function (DCF) mode. This design problem is particularly challenging due to the conflicting nature of the multi-radio capability of a node, i.e., multiple radios improve throughput and delay performance at the cost of increased energy consumption. To address this problem, we propose a power-saving multi-channel MAC protocol (PSM-MMAC), which is capable of reducing the collision probability and the waiting time in the ‘awake’ state of a node, resulting in improved throughput, delay performance, and energy efficiency. The key ideas of PSM-MMAC are the following: we first estimate the number of active links; given this estimation as well as queue lengths and channel conditions, we appropriately select channels, radios, and power states (i.e., awake or doze state); then we optimize the medium access probability in p-persistent CSMA used in the data exchange. Another contribution of this paper is an analytical model that characterizes the throughput performance. Simulation results validate the accuracy of our analytical model and show that our proposed protocol is able to significantly improve both throughput and energy efficiency.
1365809
New techniques for extracting features from protein sequences
In this paper we propose new techniques to extract features from protein sequences. We then use the features as inputs for a Bayesian neural network (BNN) and apply the BNN to classifying protein sequences obtained from the PIR (Protein Information Resource) database maintained at the National Biomedical Research Foundation. To evaluate the performance of the proposed approach, we compare it with other protein classifiers built based on sequence alignment and machine learning methods. Experimental results show the high precision of the proposed classifier and the complementarity of the bioinformatics tools studied in the paper.
53249335
Modeling and rendering of quasi-homogeneous materials
Many translucent materials consist of evenly-distributed heterogeneous elements which produce a complex appearance under different lighting and viewing directions. For these quasi-homogeneous materials, existing techniques do not address how to acquire their material representations from physical samples in a way that allows arbitrary geometry models to be rendered with these materials. We propose a model for such materials that can be readily acquired from physical samples. This material model can be applied to geometric models of arbitrary shapes, and the resulting objects can be efficiently rendered without expensive subsurface light transport simulation. In developing a material model with these attributes, we capitalize on a key observation about the subsurface scattering characteristics of quasi-homogeneous materials at different scales. Locally, the non-uniformity of these materials leads to inhomogeneous subsurface scattering. For subsurface scattering on a global scale, we show that a lengthy photon path through an even distribution of heterogeneous elements statistically resembles scattering in a homogeneous medium. This observation allows us to represent and measure the global light transport within quasi-homogeneous materials as well as the transfer of light into and out of a material volume through surface mesostructures. We demonstrate our technique with results for several challenging materials that exhibit sophisticated appearance features such as transmission of back illumination through surface mesostructures.
35286842
On the NP-Isomorphism Problem with Respect to Random Instances
This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomial-time computable and invertible bijections among NP-complete sets that preserve the underlying natural distributions on random instances. We show that there are natural NP-complete problems which are not polynomially isomorphic when instances are chosen at random because no polynomial-time isomorphisms can preserve the underlying natural distributions on instances of these problems, On the other hand, we show that all the known average-case NP-complete problems under many-one reductions are polynomially isomorphic with respect to their distributions on random instances. Simple and accessible proofs to the known average-case NP-complete problems are presented when establishing the isomorphism result. New average-case NP-complete problems are also presented.
393
Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
Given a multiset X={x1,. . .,xn} of real numbers, the floating-point set summation problem asks for Sn=x1 + . . . + xn. Let $E^*_n$ denote the minimum worst-case error over all possible orderings of evaluating Sn. We prove that if X has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to $E^*_n$. We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most $2(\lceil\log(n-1)\rceil+1)E^*_n$. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most $\lceil\log\log n\rceil E^*_n$. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most $\lceil\log n\rceil E^*_n$, while $E^*_n$ was known to be attainable in O(n log n) time using Huffman coding.