Managing a portfolio of overlay paths

ABSTRACT

In recent years, several architectures have been proposed and developed for supporting streaming applications that take advantage of multiple paths through the network simultaneously. We consider the problem of computing a set of paths and the relative amounts of data conveyed through them in order to provide the desired level of performance for data streams. Given the expectation, variance, and covariance of an appropriate metric of interest for overlay links, we attempt to solve the underlying resource allocation problem by applying methods used in managing a finance portfolio. We observe that the flow allocation problem requires constrained application of these methods, and we discuss the tractability of enforcing the constraints. We finally present some simulation results to evaluate the effectiveness of our proposed techniques.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: R. E. Bailey. Economics of Financial Markets. 2003.
• 3: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: A. C. Begen, Y. Altunbasak, and O. Ergun. Multi-path selection for multiple description encoded video streaming. In Proceedings of IEEE International Conference on Communications, 2003.
• 6: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 7: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 8: W. C. Cheng, C. Chou, L. Golubchik, S. Khuller, and Y. Wan. Large-scale Data Collection: a Coordinated Approach. In Proceedings of IEEE INFOCOM, 2003.
• 9: M. Claypool and J. Riedl. End-to-End Quality in Multimedia Applications. In Chapter 40 in Handbook on Multimedia Computing, 1999.
• 10: Mark Claypool , Jonathan Tanner, The effects of jitter on the peceptual quality of video, Proceedings of the seventh ACM international conference on Multimedia (Part 2), p.115-118, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319878.319909]
• 11: Allen B. Downey, Evidence for long-tailed distributions in the internet, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505230]
• 12: K. Harfoush , A. Bestavros , J. Byers, Robust identification of shared losses using end-to-end unicast probes, Proceedings of the 2000 International Conference on Network Protocols, p.22, November 14-17, 2000
• 13: R. Hogg and E. Tanis. Probability and Statistical Inference. Prentice Hall, Inc., 2001.
• 14: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 15: Andrew King , Jakob Nielsen, Speed Up Your Site: Web Site Optimization, Pearson Education, 2003
• 16: M. Levy and Y. Ritov. Portfolio Optimization with Many Assets: The Importance of Short-Selling, 2001.
• 17: Qingming Ma , P. Steenkiste, On path selection for traffic with bandwidth guarantees, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.191, October 28-31, 1997
• 18: Z. Ma, H.-R. Shao, and C. Shen. A new Multi-path selection Scheme for Video Streaming on overlay networks. In Proceedings of IEEE International Conference on Communications, 2004.
• 19: T. Nguyen and A. Zakhor. Path Diversity with Forward Error Correction (PDF) System for Packet Switched Networks. In Proceedings of IEEE INFOCOM, 2003.
• 20: Venkata N. Padmanabhan , Helen J. Wang , Philip A. Chou , Kunwadee Sripanidkulchai, Distributing streaming media content using cooperative networking, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507695]
• 21: Venkata N. Padmanabhan , Helen J. Wang , Philip A. Chou, Resilient Peer-to-Peer Streaming, Proceedings of the 11th IEEE International Conference on Network Protocols, p.16, November 04-07, 2003
• 22: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 23: Dan Rubenstein , Jim Kurose , Don Towsley, Detecting shared congestion of flows via end-to-end measurement, IEEE/ACM Transactions on Networking (TON), v.10 n.3, p.381-395, June 2002 [doi>10.1109/TNET.2002.1012369]
• 24: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.289-299, Oct. 1999
• 25: S. Shuzhong. What is CAPM without Short Selling? In NTU International Conference on Finance, 2002.
• 26: Stephen A. Vavasis, Nonlinear optimization: complexity issues, Oxford University Press, Inc., New York, NY, 1991
• 27: Eveline Veloso , Virgílio Almeida , Wagner Meira , Azer Bestavros , Shudong Jin, A hierarchical characterization of a live streaming media workload, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637220]
• 28: O. Verscheure, P. Frossard, and M. Hamdi. MPEG-2 Video Services over Packet Networks: Joint Effect of Encoding Rate and Data Loss on User-Oriented QoS. In Proceedings of NOSSDAV, 1998.
• 29: X. Wang and H. Schulzrinne. Adaptive Reservation: A New Framework for Multimedia Adaptation. In IEEE International Conference on Multimedia and Expo (II), 2000.
• 30: R. M. Z. Bodie. Finance. 2000.
• 31: M. Zhang, J. Lai, A. Krishnamurthy, L. Peterson, and R. Wang. Improving Performance and Reliability with Multi-Path TCP. In Proceedings of Usenix Annual Technical Conference, 2004.
• 32: Yin Zhang , Nick Duffield, On the constancy of internet path properties, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505228]
• 33: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
overlay networks, video streaming