Network flow based resource brokering and optimization techniques for distributed data streaming over optical networks

ABSTRACT

This article analyzes the problem of optimizing access to and transport of large remote data through intelligent resource selection and configuration. With the availability of high speed optical networks, the main problem for remote data access is shifting from having enough network bandwidth to having enough data ready to saturate the network when requested by the application. Network bandwidth is now higher than disk bandwidth and this gives us the possibility of utilizing multiple distributed resources to saturate the network links. We are considering two types of scenarios, one where we use only disks as data sources and a more advanced scenario where compute resources in the network can be utilized as caches to increase instantaneous throughput.

The problem we are facing is choosing and configuring the resources for this scenario. This is a non-trivial problem however as we are using application-driven network resource allocation (which gives us predictability and determinism in terms of network performance) the problem becomes tractable. We discuss optimization algorithms that are applicable to this problem, and present an algorithm that divides the problem in two sub-problems that can be solved using existing network flow algorithms.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: M. Allalouf and Y. Shavitt. Maximum flow routing with weighted max-min fairness. First International Workshop on QoS Routing (WQoSR), 2004.
• 3: Micah Beck , Terry Moore , James S. Plank, An end-to-end approach to globally scalable network storage, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 4: I. Bowman, J. Shalf, and K.-L. Ma. Performance modeling for grid-based visualization. Technical report, Lawrence Berkeley National Laboratory, 2004.
• 5: Eric He , Jason Leigh , Oliver Yu , Thomas A. DeFanti, Reliable Blast UDP: Predictable High Performance Bulk Data Transfer, Proceedings of the IEEE International Conference on Cluster Computing, p.317, September 23-26, 2002
• 6: Bruce Edward Hoppe, Efficient dynamic network flow algorithms, Cornell University, Ithaca, NY, 1996
• 7: Andrei Hutanu , Gabrielle Allen , Stephen D. Beck , Petr Holub , Hartmut Kaiser , Archit Kulshrestha , Miloš Liška , Jon MacLaren , Luděk Matyska , Ravi Paruchuri , Steffen Prohaska , Ed Seidel , Brygg Ullmer , Shalini Venkataraman, Distributed and collaborative visualization of large data sets using high-speed networks, Future Generation Computer Systems, v.22 n.8, p.1004-1010, October 2006 [doi>10.1016/j.future.2006.03.026]
• 8: S.-H. Jang, X. Wu, V. Taylor, G. Mehta, K. Vahi, and E. Deelman. Using performance prediction to allocate grid resources. Technical Report 2004-25, GriPhyN, 2004.
• 9: Jin Liang , K. Nahrstedt , Yuanyuan Zhou, Adaptive multi-resource prediction in distributed resource sharing environment, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.293-300, April 19-22, 2004
• 10: Dong Lu , Yi Qiao , Peter A. Dinda , Fabian E. Bustamante, Characterizing and Predicting TCP Throughput on the Wide Area Network, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.414-424, June 06-10, 2005 [doi>10.1109/ICDCS.2005.17]
• 11: J. MacLaren. HARC: The Highly-Available Resource Co-allocator. In to appear in Proceedings of GADA'07, LNCS 4804 (OTM Conferences 2007, Part II). Springer-Verlag, 2007.
• 12: J. Plank, S. Atchley, Y. Ding, and M. Beck. Algorithms for High Performance, Wide-Area, Distributed File Downloads. Parallel Processing Letters, 13(2):207--224, 2003.
• 13: Valerie Taylor , Xingfu Wu , Rick Stevens, Prophesy: an infrastructure for performance analysis and modeling of parallel and grid applications, ACM SIGMETRICS Performance Evaluation Review, v.30 n.4, March 2003 [doi>10.1145/773056.773060]
• 14: S. R. Thorpe, L. Battestilli, G. Karmous-Edwards, A. Hutanu, J. MacLaren, J. Mambretti, J. H. Moore, K. S. Sundar, Y. Xin, A. Takefusa, M. Hayashi, A. Hirano, S. Okamoto, T. Kudoh, T. Miyamoto, Y. Tsukishima, T. Otani, H. Nakada, H. Tanaka, A. Taniguchi, Y. Sameshima, and M. Jinno. G-lambda and enlightened: Wrapped in middleware co-allocating compute and network resources across japan and the us. In Proceedings of GridNets - First International Conference on Networks for Grid Applications, 2007.
• 15: C. Toole. Broker services for distributed visualization. Master's thesis, Jackson State University, 2005.
• 16: Sudharshan Vazhkudai , Jennifer M. Schopf, Using Disk Throughput Data in Predictions of End-to-End Grid Data Transfers, Proceedings of the Third International Workshop on Grid Computing, p.291-304, November 18, 2002
• 17: Predicting the Performance of Wide Area Data Transfers, Proceedings of the 16th International Symposium on Parallel and Distributed Processing, p.34, April 15-19, 2002
• 18: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4 ]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Parallel I/O

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Keywords:
maximum network flow, optical grids, remote data access, resource brokering