Brief announcement: Complexity analysis and algorithm design for pipeline configuration in distributed networks

Yi Gu, Qishi Wu, Anne Benoit, Yves Robert

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

Abstract

Supporting high-performance computing pipelines in wide-area networks is crucial to enabling large-scale distributed scientific applications that require minimizing end-to-end delay for fast user interaction or maximizing frame rate for smooth data flow. We formulate and categorize the linear pipeline configuration problems into six classes with two mapping objectives, i.e. minimum end-to-end delay and maximum frame rate, and three network constraints, i.e. no, contiguous, and arbitrary node reuse. We design a dynamic programming-based optimal solution to the configuration problem for minimum end-to-end delay with arbitrary node reuse and prove the NP-completeness of the rest five problems, for each of which, a heuristic algorithm based on a similar optimization procedure is proposed. Performance superiorities of these heuristics are illustrated by extensive experimental results in comparison with existing methods.

Original languageEnglish (US)
Title of host publicationPODC'09 - Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing
Pages332-333
Number of pages2
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event2009 ACM Symposium on Principles of Distributed Computing, PODC'09 - Calgary, AB, Canada
Duration: Aug 10 2009Aug 12 2009

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other2009 ACM Symposium on Principles of Distributed Computing, PODC'09
CountryCanada
CityCalgary, AB
Period8/10/098/12/09

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Dynamic programming
  • End-to-end delay
  • Frame rate
  • Heuristic algorithm
  • NP-complete
  • Optimization problem

Fingerprint Dive into the research topics of 'Brief announcement: Complexity analysis and algorithm design for pipeline configuration in distributed networks'. Together they form a unique fingerprint.

Cite this