14659770
Guaranteeing statistical QoS to regulated traffic: the single node case
Multimedia traffic can typically tolerate some loss but has rigid delay constraints. A natural QoS requirement for a multimedia connection is a prescribed bound on the the fraction of traffic that exceeds an end-to-end delay limit. We propose and analyze a traffic management scheme which guarantees QoS to multimedia traffic while simultaneously allowing for a large connection-carrying capacity. We study our traffic management scheme in the context of a single node. In order for the node to guarantee QoS, each connection's traffic is regulated. In order to support many connections, the link statistically multiplexes the connections' traffic. The scheme consists of (i) cascaded leaky-buckets for traffic regulation, (ii) smoothers at the ingresses, and (iii) bufferless statistical multiplexing within the node. For this scheme we show that loss probabilities are minimized with simple one-buffer smoothers which operate at specific minimum rates. We also show that the worst-case input traffic is extremal on-off traffic for all connections. These two results lead to a straightforward scheme for guaranteeing QoS to regulated traffic. Using MPEG video traces, we present numerical results which demonstrate the methodology. Finally, we compare the bufferless scheme with buffered statistical multiplexing.
32291503
On Nonblocking Multirate Interconnection Networks
In a recent paper, Melen and Turner [SIAM J. Comput., 18 (1989), pp. 301–313] determined sufficient conditions for multirate interconnection networks to be strictly nonblocking and rearrangeable. They considered the continuous bandwidth case, which permits the bandwidth of a connection to take an arbitrary value in a given closed interval. In this paper, simple necessary and sufficient conditions for multirate interconnection networks to be strictly nonblocking for both discrete and continuous bandwidth cases are determined. New results for rearrangeable multirate networks with discrete bandwidth requirements are also given.
31310473
Packet multiplexers with adversarial regulated traffic
We consider a finite-buffer packet multiplexer to which traffic arrives from several independent sources. The traffic from each of the sources is regulated, i.e., the amount of traffic that can enter the multiplexer is constrained by known regulator constraints. The regulator constraints depend on, the source and are more general than those resulting from cascaded leaky buckets. We assume that the traffic is adversarial to the extent permitted by the regulators. For lossless multiplexing, we show that if the original multiplexer is lossless it is possible to allocate bandwidth and buffer to the sources so that the resulting segregated systems are lossless. For lossy multiplexing, we use our results for lossless multiplexing to estimate the loss probability of the multiplexer. Our estimate involves transforming the original system into two independent resource systems, and using adversarial sources for the two independent resources to obtain a bound on the loss probabilities for the transformed system. We show that the adversarial sources are not extremal on-off sources, even when the regulator consists of a peak rate controller in series with a leaky bucket. We explicitly characterize the form of the adversarial source for the transformed problem. We also provide numerical results for the case of the simple regulator.
18166886
On Routing in ATM Networks
Alternative routing of calls has long been acknowledged as a means of increasing call throughput and robustness in the telephone network. Given these performance gains, it is natural to consider dynamic routing of Virtual Circuits (VCs) in Asynchronous Transfer Mode (ATM) networks. Unlike telephone networks, VCs have heterogeneous bandwidth characteristics and Quality of Service requirements that the routing algorithm must take into account in order to optimize performance. In this paper we attempt to classify ATM networks according to the network characteristics that have the greatest bearing on the performance of dynamic routing algorithms; we also discuss appropriate routing algorithms for diierent classes of ATM network. The classiication is based on the degree of heterogeneity of the sources and the degree of statistical multiplexing.
15937667
A dynamic programming methodology for managing prerecorded VBR sources in packet-switched networks
Broadband networks will increasingly carry prerecorded traffic, such as high-fidelity audio, short multimedia clips, and full-length movies. We study how to manage the transmission and transport of traffic from prerecorded VBR sources so that network resources are efficiently utilized and end users receive satisfactory service. Specifically, we study Piecewise Constant-Rate Transmission and Transport (PCRTT), whereby the server transmits and the network transports each connection's packets at different constant rates over a small number of intervals. We show how Dynamic Programming (DP) can be applied to find optimal PCRTT rates and intervals for a wide variety of optimization criteria, including criteria which explicitly account for delays to user interaction (pause, fast forward, and rewind). We also introduce two admission policies for PCRTT: peak-rate admission and packing admission. For peak-rate admission, for each video the network allocates an end-to-end CBR connection; the rate of the CBR connection is equal to the maximum PCRTT rate. For packing admission, for each video the network reserves a series of CBR connections of different rates over specific time intervals. Using public domain MPEG traces, we present several numerical examples which illustrate the traffic management schemes and the DP methodology.
6975415
Distributing Layered Encoded Video through Caches
The efficient distribution of stored information has become a major concern in the Internet which has increasingly become a vehicle for the transport of stored video. Because of the highly heterogeneous access to the Internet, researchers and engineers have argued for layered encoded video. We investigate delivering layered encoded video using caches. Based on the stochastic knapsack theory, we develop a model for the layered video caching problem. We propose heuristics to determine which videos and which layers in the videos should be cached in order to maximize the revenue from the streaming service. We evaluate the performance of our heuristics through extensive numerical experiments. We find that, for typical scenarios, the revenue increases nearly logarithmically with the cache size and linearly with the link bandwidth that connects the cache to the origin servers. We also consider service models with request queuing and negotiations about the delivered stream quality and find that both extensions provide only small revenue increases.
38852147
On Negation in HiLog
Abstract The logic HiLog of Chen, Kifer, and Warren has a second order syntax, while its semantics is first order. HiLog programs with negative literals in the body are considered. A stable-model semantics and a well-founded semantics for this class of program are defined, and it is shown that these semantics generalize the stable-model semantics and the well-founded semantics, respectively, for range-restricted normal programs. A second order property called preservation under extensions is proposed and investigated. Preservation under extensions ensures that the semantics of a program is not changed when rules having no symbols in common with the program are appended to the program. It is shown that for normal programs, domain independence and preservation under extensions are equivalent, while for HiLog programs, preservation under extensions is strictly stronger. Range restrictedness is generalized to HiLog programs in two ways, and it is shown that range restricted HiLog programs are preserved under extensions with respect to the well-founded semantics. Conditions under which the well-founded semantics is two-valued are investigated, and the class of modularly stratified programs is generalized to HiLog. An extension of magic-set techniques to modularly stratified HiLog programs is described.
7960269
Fast joins using join indices
Abstract. Two new algorithms, “Jive join” and “Slam join,” are proposed for computing the join of two relations using a join index. The algorithms are duals: Jive join range-partitions input relation tuple ids and then processes each partition, while Slam join forms ordered runs of input relation tuple ids and then merges the results. Both algorithms make a single sequential pass through each input relation, in addition to one pass through the join index and two passes through a temporary file, whose size is half that of the join index. Both algorithms require only that the number of blocks in main memory is of the order of the square root of the number of blocks in the smaller relation. By storing intermediate and final join results in a vertically partitioned fashion, our algorithms need to manipulate less data in memory at a given time than other algorithms. The algorithms are resistant to data skew and adaptive to memory fluctuations. Selection conditions can be incorporated into the algorithms. Using a detailed cost model, the algorithms are analyzed and compared with competing algorithms. For large input relations, our algorithms perform significantly better than Valduriez's algorithm, the TID join algorithm, and hash join algorithms. An experimental study is also conducted to validate the analytical results and to demonstrate the performance characteristics of each algorithm in practice.
578243
A Faceted Query Engine Applied to Archaeology
In this demonstration, we describe a system for storing and querying faceted hierarchies. We have developed a general faceted domain model and a query language for hierarchically classified data. We present here the use of our system on two real archaeological datasets containing thousands of artifacts. Our system is a sharable, evolvable resource that can provide global access to sizeable datasets in queriable format, and can serve as a valuable tool for data analysis and research in many application domains.
14743246
Independence Diagrams: A Technique for Visual Data Mining
An important issue in data mining is the recognition of complex dependencies between attributes. Past techniques for identifying attribute dependence include correlation coefficients, scatterplots, and equiwidth histograms. These techniques are sensitive to outliers, and often are not sufficiently informative to identify the kind of attribute dependence present. 
 
We propose a new approach, which we call independence diagrams. We divide each attribute into ranges; for each pair of attributes, the combination of these ranges defines a two-dimensional grid. For each cell of this grid, we store the number of data items in it. We display the grid, scaling each attribute axis so that the displayed width of a range is proportional to the total number of data items within that range. The brightness of a cell is proportional to the density of data items in it. 
 
As a result, both attributes are independently normalized by frequency, ensuring insensitivity to outliers and skew, and allowing specific focus on attribute dependencies. Furthermore, independence diagrams provide quantitative measures of the interaction between two attributes, and allow formal reasoning about issues such as statistical significance.
9519416
Selection conditions in main memory
We consider the fundamental operation of applying a compound filtering condition to a set of records. With large main memories available cheaply, systems may choose to keep the data entirely in main memory, in order to improve query and/or update performance.The design of a data-intensive algorithm in main memory needs to take into account the architectural characteristics of modern processors, just as a disk-based method needs to consider the physical characteristics of disk devices. An important architectural feature that influences the performance of main memory algorithms is the branch misprediction penalty. We demonstrate that branch misprediction has a substantial impact on the performance of an algorithm for applying selection conditions.We describe a space of "query plans" that are logically equivalent, but differ in terms of performance due to variations in their branch prediction behavior. We propose a cost model that takes branch prediction into account, and develop a query optimization algorithm that chooses a plan with optimal estimated cost for conjunctive conditions. We also develop an efficient heuristic optimization algorithm. We also show how records can be ordered to further reduce branch misprediction effects.We provide experimental results for a case study based on an event notification system. Our results show the effectiveness of the proposed optimization techniques. Our results also demonstrate that significant improvements in performance can be obtained by applying a methodology that takes branch misprediction latency into account.