Advanced channel reservation is emerging as an important feature of ultra high-speed networks requiring the transfer of large files. Applications include scientific data transfers and database backup. In this paper, we present two new, on-line algorithms for advanced reservation, called BatchAll and BatchLim, that are guaranteed to achieve optimal throughput performance, based on multi-commodity flow arguments. Both algorithms are shown to have polynomial-time complexity and provable bounds on the maximum delay for 1+epsilon bandwidth augmented networks. The BatchLim algorithm returns the completion time of a connection immediately as a request is placed, but at the expense of a slightly looser competitive ratio than that of BatchAll. We also present a simple approach that limits the number of parallel paths used by the algorithms while provably bounding the maximum reduction factor in the transmission throughput. We show that, although the number of different paths can be exponentially large, the actual number of paths needed to approximate the flow is quite small and proportional to the number of edges in the network. Simulations for a number of topologies show that, in practice, 3 to 5 parallel paths are sufficient to achieve close to optimal performance. The performance of the competitive algorithms are also compared to a greedy benchmark, both through analysis and simulation.
Most of the works regarding competitive approaches to routing focused mainly on call admission, without the ability of advance reservation. For some results in this field see, e.g., @cite_20 @cite_3 . Some results involving advanced reservation are presented in @cite_6 . However, the path selection there is based on several alternatives supplied by a user in the request rather than a path selection using an automated mechanism attempting to optimize performance, as discussed here. In @cite_27 a combination of call admission and circuit switching is used to obtain a routing scheme with a logarithmic competitive ratio on the total revenue received. A competitive routing scheme in terms of the number of failed routes in the setting of ad-hoc networks is presented in @cite_15 . A survey of on-line routing results is presented in @cite_22 . A competitive algorithm for admission and routing in a multicasting setting is presented in @cite_18 . Most of the other existing work in this area consists of heuristic approaches which main emphasis are on the algorithm correctness and computational complexity, without throughput guarantees.
@cite_18 @cite_22 @cite_3 @cite_6 @cite_27 @cite_15 @cite_20
2114641109 2173141774 2008126942 2546896278 2096909875 2118792918 2099684070
We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is O((logn + loglogM)(logn + logM)logn), where M is the number of multicast groups and n is the number of nodes in the graph. We show that this is close to optimum by presenting an Ω(lognlogM) lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when M is much larger than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary.As in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups. In this chapter we have described competitive on-line algorithms for on-line network routing problems. We have concentrated on routing in electrical and optical networks, presented algorithms for load minimization and throughput maximization problems, and mentioned some of the most popular open problems in the area. We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission problem. We then give randomized algorithms with logarithmic competitive ratios for specific topologies in switchless and reconfigurable optical networks. We conclude by considering full duplex communications. Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known probabilistic model. A new on-line routing framework, based on the notion of competitive analysis, was proposed. This framework is geared toward design of strategies that have provably good performance even in the case where there are no statistical assumptions on the arrival pattern and parameters of the virtual circuits. The on-line strategies motivated by this framework are quite different from the min-hop and reservation-based strategies. This paper surveys the on-line routing framework, the proposed routing and admission control strategies, and discusses some of the implementation issues. > An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediary nodes. Routing in ad hoc networks is a challenging problem as a result of highly dynamic topology as well as bandwidth and energy constraints. In addition, security is critical in these networks due to the accessibility of the shared wireless medium and the cooperative nature of ad hoc networks. However, none of the existing routing algorithms can withstand a dynamic proactive adversarial attack. The routing protocol presented in this work attempts to provide throughput-competitive route selection against an adaptive adversary. A proof of the convergence time of our algorithm is presented as well as preliminary simulation results. The authors examine routing strategies for fast packet switching networks based on flooding and predefined routes. The concern is to get both efficient routing and an even balanced use of network resources. They present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. Efficient algorithms are presented for choosing routes along breadth-first search trees and shortest paths. It is shown that in both cases a balanced use of network resources can be guaranteed. >