Competitive Advanced Reservation with Bounded Path Dispersion - 09/19/2008

Niloofar Fazlollahi

Advance channel reservation is emerging as an important feature of ultra high-speed networks requiring the transfer of large files. In this talk, I will present two new delay-competitive algorithms for advance reservation, called BatchAll and BatchLim. Unlike existing algorithms in the literature, these algorithms are guaranteed to achieve optimal throughput performance, based on multi-commodity flow arguments.Unlike BatchAll, 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 have proposed 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 have shown 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. According to our simulations for a number of topologies, three to five parallel paths are sufficient to achieve close to optimal performance.