5956143
Fast Update Algorithm for IP Forwarding Table Using Independent Sets
This paper describes a new update algorithm for Internet Protocol (IP) forwarding tables. The update algorithm is so general that it can be combined with many IP address lookup algorithms for fast update. This is done by partitioning the IP forwarding table into independent sets. Each independent set can be looked as a set of disjoint ranges, therefore any data structure for disjoint ranges search can be combined with this algorithm to support fast update. This algorithm achieves fast update by avoiding the worst-case update scenario. The number of independent sets is small, hence, the number of parallel data structures is small.
7393635
On a decomposition for infinite transition matrices
Heyman gives an interesting factorization of I-P, where P is the transition probability matrix for an ergodic Markov chain. We show that this factorization is valid if and only if the Markov chain is recurrent. Moreover, we provide a decomposition result which includes all ergodic, null recurrent as well as the transient Markov chains as special cases. Such a decomposition has been shown to be useful in the analysis of queues.
8245310
Packet classification using independent sets
This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is neither sensitive to the rule table nor to the percentage of wildcards in the fields. It also scales well from two dimensional classifiers to high dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed.
7249461
Equilibrium probability calculations for a discrete-time bulk queue model
Many problems in management science and telecommunications can be solved by the analysis of aDX/Dm/1 queueing model. In this paper, we use the zeros, both inside and outside the unit circle, of the denominator of the generating function of the model to obtain an explicit closed-form solution for the equilibrium probabilities of the number of customers in the system. The moments of the number of customers in the queue or in the system are also studied. When there are infinitely many zeros outside the unit circle, we propose an approximation method using polynomials. This method yields correct values for a finite number of the probabilities, the number depending on the degree of the polynomial approximation.
10152279
An on-chip IP address lookup algorithm
This paper proposes a new data compression algorithm to store the routing table in a tree structure using very little memory. This data structure is tailored to a hardware design reference model presented in this paper. By exploiting the low memory access latency and high bandwidth of on-chip memory, high-speed packet forwarding can be achieved using this data structure. With the addition of pipeline in the hardware, IP address lookup can only be limited by the memory access speed. The algorithm is also flexible for different implementation. Experimental analysis shows that, given the memory width of 144 bits, our algorithm needs only 400kb memory for storing a 20k entries IPv4 routing table and five memory accesses for a search. For a 1M entries IPv4 routing table, 9Mb memory and seven memory accesses are needed. With memory width of 1,068 bits, we estimate that we need 100Mb memory and six memory accesses for a routing table with 1M IPv6 prefixes.
12919460
Decay rate for a PH/M/2 queue with shortest queue discipline
In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates.
38902380
Construction Algorithm of Principal Curves in the Sense of Limit
Principal curves have been defined as self-consistent, smooth, one-dimensional curves which pass through the middle of a multidimensional data set. They are nonlinear generalization of the first Principal Component. In this paper, we take a new approach by defining principal curves as continuous curves based on the local tangent space in the sense of limit. It is proved that this new principal curves not only satisfy the self-consistent property, but also are the unique existence for any given open covering. Based on the new definition, a new practical algorithm for constructing principal curves is given. And the convergence properties of this algorithm are analyzed. The new construction algorithm of principal curves is illustrated on some simulated data sets.
32435431
Regularized Semi-supervised Classification on Manifold
Semi-supervised learning gets estimated marginal distribution PX with a large number of unlabeled examples and then constrains the conditional probability p(y | x) with a few labeled examples. In this paper, we focus on a regularization approach for semi-supervised classification. The label information graph is first defined to keep the pairwise label relationship and can be incorporated with neighborhood graph which reflects the intrinsic geometry structure of PX. Then we propose a novel regularized semi-supervised classification algorithm, in which the regularization term is based on the modified Graph Laplacian. By redefining the Graph Laplacian, we can adjust and optimize the decision boundary using the labeled examples. The new algorithm combines the benefits of both unsupervised and supervised learning and can use unlabeled and labeled examples effectively. Encouraging experimental results are presented on both synthetic and real world datasets.
13948740
Scalarization Using Loop Alignment and Loop Skewing
Array syntax, which is supported in many technical programming languages, adds expressive power by allowing operations on and assignments to whole arrays and array sections. To compile an array assignment statement to a uniprocessor, the language processor must convert the statement into a loop that has the same meaning. This process is called scalarization.Scalarization presents a significant technical problem because an array assignment needs to be implemented as if all inputs are fetched before any outputs are stored. Since a loop intermixes loads and stores, the compiler typically allocates a temporary array to hold the intermediate result. Because these extra temporary arrays can cause performance problems in cache, many techniques have been developed to avoid their use or minimize their size.In this paper, we present a novel application of two compiler strategies—loop alignment and loop skewing—to address this problem. We show that these strategies can achieve the asymptotically minimal memory allocation for stencil computations. Our experiments with loop alignment and loop skewing demonstrate that it is extremely effective in improving memory hierarchy performance of Fortran 90 array code on standard uniprocessors. The result should be applicable to other array languages, such as MATLAB.
9438100
Classification Based on Logical Concept Analysis
This paper studies the problem of classification by using a concept lattice as a search space of classification rules. The left hand side of a classification rule is composed by a concept, including its extension and its intension, and the right hand side is the class label that the concept implies. Particularly, we show that logical concepts of the given universe are naturally associated with any consistent classification rules generated by any partition-based or covering-based algorithm, and can be characterized as a special set of consistent classification rules. An algorithm is proposed to find a set of the most general consistent concepts.
3140808
Voxels on Fire
We introduce a method for the animation of fire propagation and the burning consumption of objects represented as volumetric data sets. Our method uses a volumetric fire propagation model based on an enhanced distance field. It can simulate the spreading of multiple fire fronts over a specified isosurface without actually having to create that isosurface. The distance field is generated from a specific shell volume that rapidly creates narrow spatial bands around the virtual surface of any given isovalue. The complete distance field is then obtained by propagation from the initial bands. At each step multiple fire fronts can evolve simultaneously on the volumetric object. The flames of the fire are constructed from streams of particles whose movement is regulated by a velocity field generated with the hardware-accelerated Lattice Boltzmann Model (LBM). The LBM provides a physically-based simulation of the air flow around the burning object. The object voxels and the splats associated with the flame particles are rendered in the same pipeline so that the volume data with its external and internal structures can be displayed along with the fire.