Globally Optimal Bulk Data Transfers in Overlay Routing Networks

This report describes the results of a six-week research vis it by the first author to the INRIA RESO research group at ENS Lyon. We address the problem of scheduling bulk data transfers in routing overlays running over public networks, in a globally optimal manner. One challenge encountered in this endeavor is to jointly address the global optimization of routes taken by transfers in the r outing overlay, one one hand, and the transfer schedules in the time domain, on the other, such that a single global objective is optimized (we currently choose minimizing global network congestion as our objective). In this direct ion, we explore two alternative approaches, one based on a linear programming optimization, and another on oblivious routing strategies. A second challenge in scheduling deadline-constrained transfers in a public network settin g is dealing with uncertainties in future resource availabi lity (e.g. available bandwidths) given by the presence of cross-traffic. For this, we propose using distributions rather tha n fixed values for describing network links and further derivi ng probabilistic guarantees for deadlines to be met based on the distributions of transfer paths chosen by our algorit hm. Our system is currently still in a development and testing phase. We plan evaluations based on trace-driven simulations, using traces collected on PlanetLab by us and traces we downloaded from the S3 measurement project. We will use S3 traces we have been collecting for about two months. Depending on the outcome of the simulation approach and on other practical factors, we might also evaluate the system by running a full-fledged implementation over PlanetLab. Applications of our approach include p2p networks used for data transfers, QoS-enhancing routing overlays such as [5] [19] [12], SETI@home-like p2p computing, with deadline constraints, over large scale data (e.g. astronomic streams), as well as any scenario in which a distributed organization needs to transfer and process large amounts of data over public networks with deadline constraints.