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

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.

REFERENCES

• 1: B. Agarwalla, N. Ahmed, D. Hilley, and U. Ramachandran. Streamline: a scheduling heuristic for streaming application on the grid. In The 13th Multimedia Computing and Networking Conf., San Jose, CA, 2006.
• 2: S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111--121, 1980.
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Q. Wu, Y. Gu, M. Zhu, and N. Rao. Optimizing network performance of computing pipelines in distributed environments. In Proc. of the 22nd IEEE IPDPS, Miami, Florida, Apr. 14--18 2008.
• 5: Ying Zhu , Baochun Li, Overlay Networks with Linear Capacity Constraints, IEEE Transactions on Parallel and Distributed Systems, v.19 n.2, p.159-173, February 2008 [doi>10.1109/TPDS.2007.70726]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

General Terms:
Algorithms, Performance

Keywords:
dynamic programming, end-to-end delay, frame rate, heuristic algorithm, np-complete, optimization problem