Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks

Details Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks

2007-11-02

arxiv.org/abs/0711.0301v1

Computer Science

Networking and Internet Architecture

9 pages, 8 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-437584