This paper develops an effective randomized on-demand QoS routing algorithm on networks with inaccurate link-state information. Several new techniques are proposed in the algorithm. First, the maximum safety rate and ...
详细信息
This paper develops an effective randomized on-demand QoS routing algorithm on networks with inaccurate link-state information. Several new techniques are proposed in the algorithm. First, the maximum safety rate and the minimum delay for each node in the network are pre-computed, which simplify the network complexity and provide the routing process with useful information. The routing process is dynamically directed by the safety rate and delay of the partial routing path developed so far and by the maximum safety rate and the minimum delay of the next node. Randomness is used at the link level and depends dynamically on the routing configuration. This provides great flexibility for the routing process, prevents the routing process from overusing certain fixed routing paths, and adequately balances the safety rate and delay of the routing path. A network testing environment has been established and five parameters are introduced to measure the performance of QoS routing *** results demonstrate that in terms of the proposed parameters, the algorithm outperforms existing QoS algorithms appearing in the literature.
The famous max-flow min-cut theorem states that a source node s can send information through a network (V,E) to a sink node t at a data rate determined by the min-cut separating s and t. Recently it has been shown tha...
详细信息
ISBN:
(纸本)9781581136616
The famous max-flow min-cut theorem states that a source node s can send information through a network (V,E) to a sink node t at a data rate determined by the min-cut separating s and t. Recently it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to reencode the information they receive. In contrast, we present graphs where without coding the rate must be a factor Ω(log|V|) smaller. However, so far no fast algorithms for constructing appropriate coding schemes were known. Our main result are polynomial time algorithms for constructing coding schemes for multicasting at the maximal data rate.
We propose and analyze two randomized local election algorithms in an asynchronous anonymous graph. (C) 2001 Elsevier Science B.V. All rights reserved.
We propose and analyze two randomized local election algorithms in an asynchronous anonymous graph. (C) 2001 Elsevier Science B.V. All rights reserved.
The problem of document replacement in web caches has received much attention in recent research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in we...
详细信息
The problem of document replacement in web caches has received much attention in recent research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for, approximating any existing web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M < N least useful documents are retained for the succeeding iteration. When the next replacement is to be performed, the algorithm obtains N - M new samples from the cache and replaces the least useful document from the N - M new samples and the M previously retained. Using theory and simulations, we analyze the algorithm and find that it matches the performance of existing document replacement schemes for values of N and M as low as 8 and 2 respectively. Interestingly, we find. that retaining. a small number of samples from one iteration to the next leads to an exponential improvement in performance as compared to retaining no samples at all.
In this paper we study tire problem of assigning paths to packets oil N x N tori in an on-line and distributed fashion. By on-line we mean that the routing decisions must be made without any knowledge of future reques...
详细信息
In this paper we study tire problem of assigning paths to packets oil N x N tori in an on-line and distributed fashion. By on-line we mean that the routing decisions must be made without any knowledge of future requests. Being distributed is an equally important feature of our design. for Such algorithms need knot know the global configuration of the network in the process of routing packets. We use the technique of competitive analysis to measure the performance of our design, In addition to showing an Omega(log N) lower bound on the competitive ratio, we present both deterministic and randomized algorithms which are O(log N) competitive with respect to the maximum load (i.e., congestion) on communication links.
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently a...
详细信息
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random alpha-points drawn from the same schedule results in an on-line algorithm with competitive ratio (4)/(3). Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee A as well. On the other hand, we show that it is at best an (8)/(7)-relaxation. Copyright (C) 2002 John Wiley Sons, Ltd.
The main idea of the "black box"approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired resul...
详细信息
The main idea of the "black box"approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired result. Here good preconditioners will be used to ensure geometrical/algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We present new conditioners, including conditioners to preserve low displacement rank for Toeplitz-like matrices. We also provide new analyses of preconditioner performance and results on the relations among preconditioning problems and with linear algebra problems. Thus, improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields. (C) 2002 Elsevier Science Inc. All rights reserved.
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a model and accurate mo...
详细信息
For the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. There seems to be a dilemma between simple and flexible use of such a model and accurate modeling of details of the hardware. This paper explains how many aspects of this problem can be resolved. The programming model implements one large logical disk allowing concurrent access to arbitrary sets of variable size blocks. This model can be implemented efficiently on multiple independent disks even if zones with different speed, communication bottlenecks and failed disks are allowed. These results not only provide useful algorithmic tools but also imply a theoretical justification for studying external memory algorithms using simple abstract models. The algorithmic approach is random redundant placement of data and optimal scheduling of accesses. The analysis generalizes a previous analysis for simple abstract external memory models in several ways (higher efficiency, variable block sizes, more detailed disk model). (C) 2002 Published by Elsevier Science B.V.
The subset-sum problem (SSP) is defined as follows: given a positive integer bound and a set of n positive integers find a subset whose sum is closest to, but not greater than, the bound. We present a randomized appro...
详细信息
The subset-sum problem (SSP) is defined as follows: given a positive integer bound and a set of n positive integers find a subset whose sum is closest to, but not greater than, the bound. We present a randomized approximation algorithm for this problem with linear space complexity and time complexity of O(n log n). Experiments with random uniformly-distributed instances of SSP show that our algorithm outperforms, both in running time and average error, Martello and Toth's (1984) quadratic greedy search, whose time complexity is O(n2). We propose conjectures on the expected error of our algorithm for uniformly-distributed instances of SSP and provide some analytical arguments justifying these conjectures. We present also results of numerous tests. International Federation of Operational Research Societies 2002.
We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set S subset of or equal to V, and the oracle tells us the ver...
详细信息
We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set S subset of or equal to V, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k;lg n }) queries and a randomized algorithm using expected O(min{k, lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.
暂无评论