On a Graph-theoretic Approach to Scheduling Large-scale Data Transfers

dc.contributor.authorCheng, William C.en_US
dc.contributor.authorChou, Cheng-Fuen_US
dc.contributor.authorGolubchik, Leanaen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorWan, Yungchun (Justin)en_US
dc.date.accessioned2004-05-31T23:15:37Z
dc.date.available2004-05-31T23:15:37Z
dc.date.created2002-02en_US
dc.date.issued2002-04-04en_US
dc.description.abstractIn this paper we consider the problem of moving a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of paths by the network may be poor. By choosing an indirect route at the application level, we may be able to obtain substantially higher performance in moving data through the network. We formulate this data transfer (collection) problem as a network flow problem. We show that by using a min-cost flow algorithm on an appropriately defined time-expanded (network) graph, we can obtain a data transfer schedule. We show that such schedules can be an order of magnitude better than schedules obtained by transferring data directly from each host to the destination. In fact, this holds, even though we make no assumptions about knowledge of the topology of the network or the capacity available on individual links of the network. We simply use end-to-end type information and compute a schedule for transferring the data. Finally, we also study the shortcomings of this approach in terms of the gap between the network flow formulation and data transfers in a wide-area network. Also UMIACS-TR-2002-04en_US
dc.format.extent523048 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/1175
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4322en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2002-04en_US
dc.titleOn a Graph-theoretic Approach to Scheduling Large-scale Data Transfersen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-4322.ps
Size:
510.79 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-4322.pdf
Size:
252.04 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-4322.ps