覆盖网络QoS路由研究
|
摘要
通过配置自治系统中一系列智能节点,以IP层作为底层的,建立起了服务于多媒体通信的覆盖层网络。覆盖网中的智能节点能够提供应用多媒体服务,进行媒体数据的传输、网络资源分析和网络宏观调配资源。用户通过多媒体通信终端,连接到覆盖网中来,通过一系列的智能节点的发送,转发,满足用户对组合多媒体服务的需求。
本文主要研究覆盖网QoS路由问题。通过覆盖网中一系列的智能节点及其提供的多媒体服务,把两个客户终端连接在一起,满足客户的网络需求。本文的覆盖层路由区别于网络层的QoS路由,也区别于应用层的单播多播。在现存的各种解决方案都不能很好的解决这种覆盖网QoS路由问题,我们的解决方案包括智能连接IL方案和QSRON算法。IL拓扑结构通过创建隐性节点和显性节点的机制,在不增加各节点探测带宽的情况下,最大限度提高网络节点的连通性。在这个拓扑方案的基础上,QSRON算法方案,采用Dijkstra算法,把对网络传输非常重要的带宽、时延、时延抖动、丢失率等QoS值作为尺度建立度量权重,分别对单个服务区段进行最佳路径选择和对整个组合服务进行最佳路径选择,搜索最佳服务路径,获得较好的QoS满意率。
With the autonomous systems, an overlay media service proxy network is formed by a set of intelligent proxies deployed at strategic locations in the underlying network layer. Proxies in this overlay network are able to provide multimedia services, such as media data transcoding and analysis. Client points of multimedia communication can then connect to this network, and request a combination of media services delivered by one or more proxies in it.In this paper, we study the problem of QoS Service Routing in Overlay Network. A service path connects a pair of communicating end points via a chain of media service proxies. We show that service path finding is different from both network-level QoS routing and application-level multicast; and that existing solutions are not readily applicable. Our solution includes the Intelligent Link method and QoS Service Routing in Overlay Network. By using the recessive points, the IL method creates a highly connected mesh within the overlay network, without increasing bandwidth probing overhead. Based on the mesh, the QSRON algorithm uses Dijkstra algorithm and computes the 'safest' service paths with respect to end-to-end resource availability, thus achieving high overall service path success rate. Both simulation and analytical results demonstrate the soundness of our solution.
本文主要研究覆盖网QoS路由问题。通过覆盖网中一系列的智能节点及其提供的多媒体服务,把两个客户终端连接在一起,满足客户的网络需求。本文的覆盖层路由区别于网络层的QoS路由,也区别于应用层的单播多播。在现存的各种解决方案都不能很好的解决这种覆盖网QoS路由问题,我们的解决方案包括智能连接IL方案和QSRON算法。IL拓扑结构通过创建隐性节点和显性节点的机制,在不增加各节点探测带宽的情况下,最大限度提高网络节点的连通性。在这个拓扑方案的基础上,QSRON算法方案,采用Dijkstra算法,把对网络传输非常重要的带宽、时延、时延抖动、丢失率等QoS值作为尺度建立度量权重,分别对单个服务区段进行最佳路径选择和对整个组合服务进行最佳路径选择,搜索最佳服务路径,获得较好的QoS满意率。
With the autonomous systems, an overlay media service proxy network is formed by a set of intelligent proxies deployed at strategic locations in the underlying network layer. Proxies in this overlay network are able to provide multimedia services, such as media data transcoding and analysis. Client points of multimedia communication can then connect to this network, and request a combination of media services delivered by one or more proxies in it.In this paper, we study the problem of QoS Service Routing in Overlay Network. A service path connects a pair of communicating end points via a chain of media service proxies. We show that service path finding is different from both network-level QoS routing and application-level multicast; and that existing solutions are not readily applicable. Our solution includes the Intelligent Link method and QoS Service Routing in Overlay Network. By using the recessive points, the IL method creates a highly connected mesh within the overlay network, without increasing bandwidth probing overhead. Based on the mesh, the QSRON algorithm uses Dijkstra algorithm and computes the 'safest' service paths with respect to end-to-end resource availability, thus achieving high overall service path success rate. Both simulation and analytical results demonstrate the soundness of our solution.
引文
1. B.Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, J. D. Kubiatowicz, "Tapestry: A resilient global-scale overlay for service deployment", IEEE Journal on Selected Areas in Communications, 2004.1, 22 (1), pp. 41-53.
2. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications", in Proc. of the ACM SIGCOMM Symposium on Communication, Architecture, and Protocols, 2001.8, pp. 149-160.
3. A. Rowstron, P. Druschel, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems", IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, 2001.11, pp. 329-350.
4. Ratnasamy S, Francis P, Handley M, Karp R, Shenker S. "A scalable content-addressable network." In: Annual Conf of the Special Interest Group on Data Communication (SIGCOMM 2001). 2001. 168-175.
5. David Andersen, Hari Balakrishnan, Frans Kaashoek, and Robert Morris, "Resilient Overlay Networks", 18th ACM Symp on Operating Systems Principles (SOSP), Banff, Canada. 2001.10.
6. D. Malki, M. Naor, and D. Ratajczak, "Viceroy: A Scalable and Dynarnie Emulation of the Butterfly," Proc. ACM Principles of Distributed Computing, ACM Press, 2002, pp. 183-192.
7. Larry Peterson, Tom Anderson, David Culler, Timothy Roscoe, "A Blueprint for Introducing Disruptive Technology into the Internet [C]", Proceedings of the First ACM Workshop on Hot Topics in Networks (HotNets-Ⅰ), Princeton, NJ, 2002,10.
8. Y. Chen and R. Katz and J. Kubiatowicz: "Dynamic Replica Placement for Scalable Content Delivery", Proc. of International Workshop on Peer-to-Peer Systems, 2002.
9. Geoffrey Fox, "PEER-TO-PEER NETWORKS", WEB COMPUTING, 2001.5-6.
10. Yang-hua Chu, Rao S G, Seshan S, et al. "Enabling conferencing applications on the internet using an overlay multieast architecture". In: Proceedings of ACM SIGCOMM, August 2001
11. Francis P, "Yoid: extending the multieast interact architecture". White Paper, 1999
12. Chawathe Y. "Scattercast: an architecture for internet broadcast distribution as an infrastructure service", Ph. D Dissertation University of California, Berkeley, Sep 2000
13. Jannotti J, Gifford D K, Johnson K L, et al, "Overcast: reliable multicasting with an overlay network". In: Proceedings of 4th Symposium on operating Systems Design and Implementation(OSDI'00), October 2000
14. Pendarakis D, Shi S, Verma D. et al. "ALME: an application level multicast infrastructure". In: Proceedings of 3rd Usenix Symposium on Internet Technologies & Systems(USITS 2001), March 2001
15. Beichuan Zhang, Jamin S, Lixia Zhang, "Host multicast: a framework for delivering multicast to end users", In: IEEE Infocom20 2. June 2002
16. E. Rosen, A. Viswanathan, R. Callon, "Multiprotocol Label Switching Architecture". IETF RFC3031, 2001
17. R. Yavatkar, D. Hofrnan, Y. Bemet, F. Baker, M. Speer. "SBM (Subnet Bandwidth Manager): A Protocol for RSVP-based Admission Control over IEEE 802-style networks". IETF RFC28I4, 2000
18. Braden R, ed. Zhang L, Berson S, et al. "Resource ReSerVation Protocol(RSVP)-Version 1, Function Specification". IETFRFC 2205, 1997
19. K. Nichols, V. Jacobson, L. Zhang et al, "A two-bit differentiated services architecture for the Internet". IETF RFC 2638, 1999
20. D. Clark, W. Fang, "Explicit allocation of best-effort packet delivery service". IEEE/ACM Transaction on Networking, 1998, 6(4): 362-37
21. A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems," Proc. Int'l Conf Distributed Systems Platforms (Middleware), ACM Press, 2001, pp. 329-350.
22. D. Malki, M. Naor, and D. Ratajczak, "Viceroy: A Scalable and Dynamic Emulation of the Butterfly," Proc. ACMPrinciples of Distributed Computing, ACM Press, 2002, pp. 183-192.
23. Larry Peterson, Tom Anderson, David Culler, Timothy Roscoe. "A Blueprint for Introducing Disruptive Technology into the Internet [C]", Proceedings of the First ACM Workshop on Hot Topics in Networks (HotNets-I), Princeton, NJ, 2002.10
24.林闯,单志广,任丰原,“计算机网络的服务质量(Qos)”.北京,清华大学出版社 2004.4.
25. Z. Wang and J. Crowcroft, "QoS Routing for Supporting Resource Reservation", IEEE Journal on Selected Areas in Communication, vol. 14, no. 7, Sep 1996
26. R. Guerin, A. Orda, and D. Williams, "QoS Routing Mechanisms and OSPF Extensions", IETF Internet Draft, November 1996.
27. Z. Li and P. Mohapatra, "QRON: QoS-Aware Routing in Overlay Networks", IEEE Journal on Selected Areas in Communications, 2004.2, 22 (1), pp. 29-40.
28. Q. Ma and P. Steenkiste, "On path selection for traffic with bandwidth guarantees," in Proc. 5th IEEE ICNP, Oct. 1997, pp. 191-202.
29.朱孙镔,陈彪,陈惠芳,”覆盖网络的Qos路由研究”,硕士毕业论文,2005.1
30. Z. Li and P. Mohapatra, "HostCast: A New Overlay Multicasting Protocol," In Proc. IEEE Int. Communications Conference (ICC) 2003.
31. A. Nakao, L. Peterson, A. Bavier, "A Routing Underlay for Overlay Networks," to appear in Proc. ACM SIGCOMM 2003.
32. C-NET NEWS, Napster among fastest-growing Net technologies, 2000, http://news.com.com/2100-1023-246648.html
33. Clarke I, Sandberg O, Wiley B, Hong TW. "Freenet: A distributed anonymous information storage and retrieval system". In: Workshop on Design Issues in Anonymity and Unobservability. 2000. 25-31.
34. Gnutella. 2003. http://www.gnutella.com/
35. Jain S, Mahajan R, Wetherall D. "A study of the performance potential of DHT-based overlays". In: Proc. of the 4th USENIX Symp. on Internet Technologies and Systems (USITS 2003). 2003. 256-261.
36. Dabek F, Kaashoek MF, Karger D, Morris R, Stoica I. "Wide-Area cooperative storage with CFS". In: Proc. of the 18th ACM Symp. on Operating Systems Principles (SOSP 2001). Chateau Lake Louise, 2001. 344-352.
37. X. Fu, W. Shi, A. Akkerman, and V. Karamcheti. "CANS: Composable, Adaptive Network Services Infrastructure". Proceedings of USENIX Symposium on Internet Technologies and Systems (USITS'01), March 2001.
38. S. Gribble, M. Welsh, R. von Behren, E. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. Katz, Z. Mao, S. Ross, and B. Zhao. "The Ninja Architecture for Robust Interact-Scale Systems and Services", Computer Networks, Special Issue on Pervasive Computing, 2001
39. A. Nakao, A. Bavier, and L. Peterson, "Constructing End-to-End Paths for Playing Media Objects", Proceedings of IEEE OPENARCH 2001, April 2001
40. Z. Fu and N. Venkatasubramanian, "Combined Path and Server Selection in Dynamic Multimedia Environments", Proceedings of ACM Multimedia'99, November 1999.
41. Y. Chawathe. "Scattercast: an Architecture for Internet Broadcast Distribution as an Infrastructure Service", PhD Thesis, University of California at Berkeley, 2000.
42. Y. Chu, S. Rao, and H. Zhang, "A Case for End System Multicast", Proceedings of ACM SIGMETRICS 2000, June 2000.
43. Inktomi. Inktomi Content Networking Solutions, http://www.inktomi.com/products/cns.
44. J. Jannotti, D. Gifford, K. Johnson, F. Kaashoek, and Jr. J. O'Toole. "Overcast: Reliable Multicasting with an Overlay Network". Proceedings of USENIX Symposium on OS Design and Implementation (OSD12000), October 2000.
45. D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. "ALMI: An Application Level Multicast Infrastructure". Proceedings of USENLX Symposium on lnternet Technologies and Systems (USITS'01), March 2001.
46. S. Shi, J. Turner, and M. Waldvogel, "Dimensioning Server Access Bandwidth and Multicast Routing in Overlay Network", Proceedings of International Workshop on Network and OS Support for Digital Audio and Video (NOSSDAV'01), June 2001.
47. A. Shaikh, J. Rexford, and K. Shin. "Efficient Precomputation of Quality of Service Routes", Proceedings of International Workshop on Network and OS Support for Digital Audio and Video (NOSSDAV'98), July 1998.
48. S. Savage, "Sting: A TCP-based network performance measurement tools", in Proc. 2nd USENIX Symp. Internet Technologies and Systems, 1999.10, pp. 71-79.
49. Y. Chu, S. Rao, S. Seshan, and H. Zhang, "Enabling Conferencing Applications on the Internet Using an Overlay Multicast Architecture". Proceedings of ACM SIGCOMM2001, August 2001.
50. Z.Wang and J. Crowcroft. "Bandwidth-Delay Based Routing Algorithms". Proceedings of IEEE Globecom'95, November 1995.
2. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for internet applications", in Proc. of the ACM SIGCOMM Symposium on Communication, Architecture, and Protocols, 2001.8, pp. 149-160.
3. A. Rowstron, P. Druschel, "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems", IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, 2001.11, pp. 329-350.
4. Ratnasamy S, Francis P, Handley M, Karp R, Shenker S. "A scalable content-addressable network." In: Annual Conf of the Special Interest Group on Data Communication (SIGCOMM 2001). 2001. 168-175.
5. David Andersen, Hari Balakrishnan, Frans Kaashoek, and Robert Morris, "Resilient Overlay Networks", 18th ACM Symp on Operating Systems Principles (SOSP), Banff, Canada. 2001.10.
6. D. Malki, M. Naor, and D. Ratajczak, "Viceroy: A Scalable and Dynarnie Emulation of the Butterfly," Proc. ACM Principles of Distributed Computing, ACM Press, 2002, pp. 183-192.
7. Larry Peterson, Tom Anderson, David Culler, Timothy Roscoe, "A Blueprint for Introducing Disruptive Technology into the Internet [C]", Proceedings of the First ACM Workshop on Hot Topics in Networks (HotNets-Ⅰ), Princeton, NJ, 2002,10.
8. Y. Chen and R. Katz and J. Kubiatowicz: "Dynamic Replica Placement for Scalable Content Delivery", Proc. of International Workshop on Peer-to-Peer Systems, 2002.
9. Geoffrey Fox, "PEER-TO-PEER NETWORKS", WEB COMPUTING, 2001.5-6.
10. Yang-hua Chu, Rao S G, Seshan S, et al. "Enabling conferencing applications on the internet using an overlay multieast architecture". In: Proceedings of ACM SIGCOMM, August 2001
11. Francis P, "Yoid: extending the multieast interact architecture". White Paper, 1999
12. Chawathe Y. "Scattercast: an architecture for internet broadcast distribution as an infrastructure service", Ph. D Dissertation University of California, Berkeley, Sep 2000
13. Jannotti J, Gifford D K, Johnson K L, et al, "Overcast: reliable multicasting with an overlay network". In: Proceedings of 4th Symposium on operating Systems Design and Implementation(OSDI'00), October 2000
14. Pendarakis D, Shi S, Verma D. et al. "ALME: an application level multicast infrastructure". In: Proceedings of 3rd Usenix Symposium on Internet Technologies & Systems(USITS 2001), March 2001
15. Beichuan Zhang, Jamin S, Lixia Zhang, "Host multicast: a framework for delivering multicast to end users", In: IEEE Infocom20 2. June 2002
16. E. Rosen, A. Viswanathan, R. Callon, "Multiprotocol Label Switching Architecture". IETF RFC3031, 2001
17. R. Yavatkar, D. Hofrnan, Y. Bemet, F. Baker, M. Speer. "SBM (Subnet Bandwidth Manager): A Protocol for RSVP-based Admission Control over IEEE 802-style networks". IETF RFC28I4, 2000
18. Braden R, ed. Zhang L, Berson S, et al. "Resource ReSerVation Protocol(RSVP)-Version 1, Function Specification". IETFRFC 2205, 1997
19. K. Nichols, V. Jacobson, L. Zhang et al, "A two-bit differentiated services architecture for the Internet". IETF RFC 2638, 1999
20. D. Clark, W. Fang, "Explicit allocation of best-effort packet delivery service". IEEE/ACM Transaction on Networking, 1998, 6(4): 362-37
21. A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems," Proc. Int'l Conf Distributed Systems Platforms (Middleware), ACM Press, 2001, pp. 329-350.
22. D. Malki, M. Naor, and D. Ratajczak, "Viceroy: A Scalable and Dynamic Emulation of the Butterfly," Proc. ACMPrinciples of Distributed Computing, ACM Press, 2002, pp. 183-192.
23. Larry Peterson, Tom Anderson, David Culler, Timothy Roscoe. "A Blueprint for Introducing Disruptive Technology into the Internet [C]", Proceedings of the First ACM Workshop on Hot Topics in Networks (HotNets-I), Princeton, NJ, 2002.10
24.林闯,单志广,任丰原,“计算机网络的服务质量(Qos)”.北京,清华大学出版社 2004.4.
25. Z. Wang and J. Crowcroft, "QoS Routing for Supporting Resource Reservation", IEEE Journal on Selected Areas in Communication, vol. 14, no. 7, Sep 1996
26. R. Guerin, A. Orda, and D. Williams, "QoS Routing Mechanisms and OSPF Extensions", IETF Internet Draft
27. Z. Li and P. Mohapatra, "QRON: QoS-Aware Routing in Overlay Networks", IEEE Journal on Selected Areas in Communications, 2004.2, 22 (1), pp. 29-40.
28. Q. Ma and P. Steenkiste, "On path selection for traffic with bandwidth guarantees," in Proc. 5th IEEE ICNP, Oct. 1997, pp. 191-202.
29.朱孙镔,陈彪,陈惠芳,”覆盖网络的Qos路由研究”,硕士毕业论文,2005.1
30. Z. Li and P. Mohapatra, "HostCast: A New Overlay Multicasting Protocol," In Proc. IEEE Int. Communications Conference (ICC) 2003.
31. A. Nakao, L. Peterson, A. Bavier, "A Routing Underlay for Overlay Networks," to appear in Proc. ACM SIGCOMM 2003.
32. C-NET NEWS, Napster among fastest-growing Net technologies, 2000, http://news.com.com/2100-1023-246648.html
33. Clarke I, Sandberg O, Wiley B, Hong TW. "Freenet: A distributed anonymous information storage and retrieval system". In: Workshop on Design Issues in Anonymity and Unobservability. 2000. 25-31.
34. Gnutella. 2003. http://www.gnutella.com/
35. Jain S, Mahajan R, Wetherall D. "A study of the performance potential of DHT-based overlays". In: Proc. of the 4th USENIX Symp. on Internet Technologies and Systems (USITS 2003). 2003. 256-261.
36. Dabek F, Kaashoek MF, Karger D, Morris R, Stoica I. "Wide-Area cooperative storage with CFS". In: Proc. of the 18th ACM Symp. on Operating Systems Principles (SOSP 2001). Chateau Lake Louise, 2001. 344-352.
37. X. Fu, W. Shi, A. Akkerman, and V. Karamcheti. "CANS: Composable, Adaptive Network Services Infrastructure". Proceedings of USENIX Symposium on Internet Technologies and Systems (USITS'01), March 2001.
38. S. Gribble, M. Welsh, R. von Behren, E. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. Katz, Z. Mao, S. Ross, and B. Zhao. "The Ninja Architecture for Robust Interact-Scale Systems and Services", Computer Networks, Special Issue on Pervasive Computing, 2001
39. A. Nakao, A. Bavier, and L. Peterson, "Constructing End-to-End Paths for Playing Media Objects", Proceedings of IEEE OPENARCH 2001, April 2001
40. Z. Fu and N. Venkatasubramanian, "Combined Path and Server Selection in Dynamic Multimedia Environments", Proceedings of ACM Multimedia'99, November 1999.
41. Y. Chawathe. "Scattercast: an Architecture for Internet Broadcast Distribution as an Infrastructure Service", PhD Thesis, University of California at Berkeley, 2000.
42. Y. Chu, S. Rao, and H. Zhang, "A Case for End System Multicast", Proceedings of ACM SIGMETRICS 2000, June 2000.
43. Inktomi. Inktomi Content Networking Solutions, http://www.inktomi.com/products/cns.
44. J. Jannotti, D. Gifford, K. Johnson, F. Kaashoek, and Jr. J. O'Toole. "Overcast: Reliable Multicasting with an Overlay Network". Proceedings of USENIX Symposium on OS Design and Implementation (OSD12000), October 2000.
45. D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. "ALMI: An Application Level Multicast Infrastructure". Proceedings of USENLX Symposium on lnternet Technologies and Systems (USITS'01), March 2001.
46. S. Shi, J. Turner, and M. Waldvogel, "Dimensioning Server Access Bandwidth and Multicast Routing in Overlay Network", Proceedings of International Workshop on Network and OS Support for Digital Audio and Video (NOSSDAV'01), June 2001.
47. A. Shaikh, J. Rexford, and K. Shin. "Efficient Precomputation of Quality of Service Routes", Proceedings of International Workshop on Network and OS Support for Digital Audio and Video (NOSSDAV'98), July 1998.
48. S. Savage, "Sting: A TCP-based network performance measurement tools", in Proc. 2nd USENIX Symp. Internet Technologies and Systems, 1999.10, pp. 71-79.
49. Y. Chu, S. Rao, S. Seshan, and H. Zhang, "Enabling Conferencing Applications on the Internet Using an Overlay Multicast Architecture". Proceedings of ACM SIGCOMM2001, August 2001.
50. Z.Wang and J. Crowcroft. "Bandwidth-Delay Based Routing Algorithms". Proceedings of IEEE Globecom'95, November 1995.