New algorithms for planning bulk transfer via internet and shipping networks

Brian Cho, Indranil Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Cloud computing is enabling groups of academic collaborators, groups of business partners, etc., to come together in an ad-hoc manner. This paper focuses on the group-based data transfer problem in such settings. Each participant source site in such a group has a large dataset, which may range in size from gigabytes to terabytes. This data needs to be transferred to a single sink site (e.g., AWS, Google datacenters, etc.) in a manner that reduces both total dollar costs incurred by the group as well as the total transfer latency of the collective dataset. This paper is the first to explore the problem of planning a group-based deadline-oriented data transfer in a scenario where data can be sent over both: (1) the internet, and (2) by shipping storage devices (e.g., external or hot-plug drives, or SSDs) via companies such as Fedex, UPS, USPS, etc. We first formalize the problem and prove its NP-Hardness. Then, we propose novel algorithms and use them to build a planning system called Pandora (People and Networks Moving Data Around). Pandora uses new concepts of time-expanded networks and delta-time-expanded networks, combining them with integer programming techniques and optimizations for both shipping and internet edges. Our experimental evaluation using real data from Fedex and from PlanetLab indicate the Pandora planner manages to satisfy deadlines and reduce costs significantly.

Original languageEnglish (US)
Title of host publicationICDCS 2010 - 2010 International Conference on Distributed Computing Systems
Pages305-314
Number of pages10
DOIs
StatePublished - Aug 27 2010
Event30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 - Genova, Italy
Duration: Jun 21 2010Jun 25 2010

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010
CountryItaly
CityGenova
Period6/21/106/25/10

Fingerprint

Data transfer
Freight transportation
Internet
Planning
Integer programming
Cloud computing
Costs
Industry
Hardness

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Cho, B., & Gupta, I. (2010). New algorithms for planning bulk transfer via internet and shipping networks. In ICDCS 2010 - 2010 International Conference on Distributed Computing Systems (pp. 305-314). [5541675] (Proceedings - International Conference on Distributed Computing Systems). https://doi.org/10.1109/ICDCS.2010.59

New algorithms for planning bulk transfer via internet and shipping networks. / Cho, Brian; Gupta, Indranil.

ICDCS 2010 - 2010 International Conference on Distributed Computing Systems. 2010. p. 305-314 5541675 (Proceedings - International Conference on Distributed Computing Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Cho, B & Gupta, I 2010, New algorithms for planning bulk transfer via internet and shipping networks. in ICDCS 2010 - 2010 International Conference on Distributed Computing Systems., 5541675, Proceedings - International Conference on Distributed Computing Systems, pp. 305-314, 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010, Genova, Italy, 6/21/10. https://doi.org/10.1109/ICDCS.2010.59
Cho B, Gupta I. New algorithms for planning bulk transfer via internet and shipping networks. In ICDCS 2010 - 2010 International Conference on Distributed Computing Systems. 2010. p. 305-314. 5541675. (Proceedings - International Conference on Distributed Computing Systems). https://doi.org/10.1109/ICDCS.2010.59
Cho, Brian ; Gupta, Indranil. / New algorithms for planning bulk transfer via internet and shipping networks. ICDCS 2010 - 2010 International Conference on Distributed Computing Systems. 2010. pp. 305-314 (Proceedings - International Conference on Distributed Computing Systems).
@inproceedings{64e87992ddf5403a8fac9513b5087bb5,
title = "New algorithms for planning bulk transfer via internet and shipping networks",
abstract = "Cloud computing is enabling groups of academic collaborators, groups of business partners, etc., to come together in an ad-hoc manner. This paper focuses on the group-based data transfer problem in such settings. Each participant source site in such a group has a large dataset, which may range in size from gigabytes to terabytes. This data needs to be transferred to a single sink site (e.g., AWS, Google datacenters, etc.) in a manner that reduces both total dollar costs incurred by the group as well as the total transfer latency of the collective dataset. This paper is the first to explore the problem of planning a group-based deadline-oriented data transfer in a scenario where data can be sent over both: (1) the internet, and (2) by shipping storage devices (e.g., external or hot-plug drives, or SSDs) via companies such as Fedex, UPS, USPS, etc. We first formalize the problem and prove its NP-Hardness. Then, we propose novel algorithms and use them to build a planning system called Pandora (People and Networks Moving Data Around). Pandora uses new concepts of time-expanded networks and delta-time-expanded networks, combining them with integer programming techniques and optimizations for both shipping and internet edges. Our experimental evaluation using real data from Fedex and from PlanetLab indicate the Pandora planner manages to satisfy deadlines and reduce costs significantly.",
author = "Brian Cho and Indranil Gupta",
year = "2010",
month = "8",
day = "27",
doi = "10.1109/ICDCS.2010.59",
language = "English (US)",
isbn = "9780769540597",
series = "Proceedings - International Conference on Distributed Computing Systems",
pages = "305--314",
booktitle = "ICDCS 2010 - 2010 International Conference on Distributed Computing Systems",

}

TY - GEN

T1 - New algorithms for planning bulk transfer via internet and shipping networks

AU - Cho, Brian

AU - Gupta, Indranil

PY - 2010/8/27

Y1 - 2010/8/27

N2 - Cloud computing is enabling groups of academic collaborators, groups of business partners, etc., to come together in an ad-hoc manner. This paper focuses on the group-based data transfer problem in such settings. Each participant source site in such a group has a large dataset, which may range in size from gigabytes to terabytes. This data needs to be transferred to a single sink site (e.g., AWS, Google datacenters, etc.) in a manner that reduces both total dollar costs incurred by the group as well as the total transfer latency of the collective dataset. This paper is the first to explore the problem of planning a group-based deadline-oriented data transfer in a scenario where data can be sent over both: (1) the internet, and (2) by shipping storage devices (e.g., external or hot-plug drives, or SSDs) via companies such as Fedex, UPS, USPS, etc. We first formalize the problem and prove its NP-Hardness. Then, we propose novel algorithms and use them to build a planning system called Pandora (People and Networks Moving Data Around). Pandora uses new concepts of time-expanded networks and delta-time-expanded networks, combining them with integer programming techniques and optimizations for both shipping and internet edges. Our experimental evaluation using real data from Fedex and from PlanetLab indicate the Pandora planner manages to satisfy deadlines and reduce costs significantly.

AB - Cloud computing is enabling groups of academic collaborators, groups of business partners, etc., to come together in an ad-hoc manner. This paper focuses on the group-based data transfer problem in such settings. Each participant source site in such a group has a large dataset, which may range in size from gigabytes to terabytes. This data needs to be transferred to a single sink site (e.g., AWS, Google datacenters, etc.) in a manner that reduces both total dollar costs incurred by the group as well as the total transfer latency of the collective dataset. This paper is the first to explore the problem of planning a group-based deadline-oriented data transfer in a scenario where data can be sent over both: (1) the internet, and (2) by shipping storage devices (e.g., external or hot-plug drives, or SSDs) via companies such as Fedex, UPS, USPS, etc. We first formalize the problem and prove its NP-Hardness. Then, we propose novel algorithms and use them to build a planning system called Pandora (People and Networks Moving Data Around). Pandora uses new concepts of time-expanded networks and delta-time-expanded networks, combining them with integer programming techniques and optimizations for both shipping and internet edges. Our experimental evaluation using real data from Fedex and from PlanetLab indicate the Pandora planner manages to satisfy deadlines and reduce costs significantly.

UR - http://www.scopus.com/inward/record.url?scp=77955914560&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955914560&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.2010.59

DO - 10.1109/ICDCS.2010.59

M3 - Conference contribution

AN - SCOPUS:77955914560

SN - 9780769540597

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 305

EP - 314

BT - ICDCS 2010 - 2010 International Conference on Distributed Computing Systems

ER -