Online Scheduling of Large File Transfers over Lambda Grids

Abstract – Numerous large-scale applications need to aggregate at a central facility large quantities of data from distributed sites connected by a lambda grid (which is an optical backbone network with mesh connectivity); thus this is a many-to-one problem. In a lambda grid, dedicated wavelength channels are used to set up end-to-end lightpaths between end nodes. The objective of our problem is to find concurrent circuit-switched paths on which the files should be transferred from the multiple sources to the (same) destination, so that the total time required for the file aggregation (denoted as total finish time) is minimized and consequently support a large number of such file-transfer sessions. The grid links corresponding to the routes will be reserved in advance (during the transmission intervals) for our file-aggregation schedule. As a difference from previous work, we consider the realistic scenario, where bandwidth may be already reserved on the grid links because of existing similar file-aggregation schedules. We design a file-transmission schedule that eliminates both the route conflicts, and time-interval conflicts, in such a way that the total finish time is minimized. To get an exact solution, we modeled our scheduling problem as an Integer Linear Program. Due to the large number of constrains, the exact solution is computationally expensive. We propose several heuristic algorithms including FirstFit, OnePass and MultiPass MinConflicts, and MultiPath. Through simulation, we show that these heuristics are viable solutions. Index Terms—lambda grid, data/file aggregation, lightpath, end-to-end provisioning, routing, time-slot reservation, heuristics, MILP. I