光交换网络中的多播调度算法及性能研究
|
摘要
近年来,随着信息技术的迅猛发展,互联网产生了很多新的应用,如视频会议、网络音频/视频广播、多媒体远程教育等已经超过了现在的网络所能提供的带宽。由于光纤的巨大带宽,光网络成为解决此问题的一种有效方法,DWDM光网络已经成为信息领域的骨干网。多播是将一个源节点的信息发送到多个目的节点。多播技术可以大大节省网络带宽,既提高数据的传送效率,又减少主干网络出现拥塞的可能性。将多播的概念引入到光交换网络中,多播光交换可以改善光网络的性能,提高光网络带宽利用率,促进新一代光交换网络技术的发展。具有多播功能的光交换核心节点是实现多播的关键技术,本文主要研究在DWDM光交换网络中,基于核心节点的多播调度算法及性能评价参数。
首先,介绍了三种典型的光分组交换结构,并对它们进行了比较。然后主要研究了基于共享有限波长变换器的SPL光交换结构的多播调度算法。在DWDM光交换网络中,每根光纤分为M个波长信道,当一根输出光纤上的连接请求多于M时就会发生冲突。多播调度算法选择一组无冲突的多播连接请求,在网络中同时调度最大数目的连接请求是一个非确定的多项式难题,因此需要采用近似调度算法。在现有算法的基础上,改进后提出了一种新的近似调度算法:NASA算法。通过实验仿真进行了验证,当光纤数和波长信道数都为8,负载率为1.0时,NASA算法的网络吞吐量提高了约14%。当光纤数和波长信道数都为16,负载率为1.0时,NASA算法的网络吞吐量提高了约11%。从而可以证明,新的调度算法提高了网络吞吐量。
其次,将优先级概念应用到多播光交换网络中,基于这个前提分析了区分优先级的多播调度算法。为方便讨论,本文中分为高、低两个优先级。对分组应用ASA算法,当负载率为0.6时,低优先级分组的吞吐量降为零,而高优先级分组的吞吐量约为0.71。对分组应用NASA算法,当负载率为0.6时,低优先级分组的吞吐量接近为零,而高优先级的分组的吞吐量约为0.75。从而可以证明:高优先级分组的网络吞吐量高于低优先级分组的网络吞吐量,保障了高优先级分组的性能。
最后,提出了DWDM光交换网络实现多播功能时评价其性能的参数:网络吞吐量,阻塞率和传输度。网络吞吐量定义为实现的多播连接请求数与连接请求总数之比;由于网络阻塞等原因造成的多播连接请求丢失的数目与网络中多播连接请求的总数之比即为阻塞率;传输度即为将所有多播连接请求传输完毕所需的传输次数,每次选择一组最大无冲突的多播连接请求。
With the rapid development of the communication technology, network applications, especially the application of multimedia video conference and distance learning, network audio/video frequency, need more bandwidth than the network at present can provide. This problem can be solved by the optical network because of the wide bandwidth of optical fiber, and the DWDM has become the bone network in the communication field. Multicast can send data to multiple receivers from one source or more in an efficient and extendable way, and that it can save bandwidth and reduce the possibility of congestion. The optical switching network introducing multicast can improve the performance of the optical network and the bandwidth usage efficiency. The core node of optical switching network with multicast function is the key technology of the multicast applications. Multicast scheduling algorithm and the performance parameters based on the optical switching network are analyzed in this paper.
First, we introduce three typical structures of optical packet switch, and compare their performance. The multicast scheduling algorithm based on the structure of the optical packet switch with shared limited range wavelength converters is studied in this paper. In DWDM switching networks, contention occurs when one output fiber is the destinations of more than M inputs, where M is the number of wavelengths on each fiber. The multicast scheduling algorithm selects a group of multicast connection requests that are contention-free, and it is a key technology in the DWDM switching network. It is proved that scheduling the maximum number of such connection requests through the network simultaneously is a NP-hard problem, so we have to develop approximation scheduling algorithms that can provide sub-optimal solutions. In this paper, we present a new approximation scheduling algorithm based on the algorithm has been presented before, and compare their performance. We can confirm that the new algorithm can improve the network throughput through simulations. For example, the network throughput of the new algorithm is improved by 14% when the number of fibers and wavelength channels is 8, the load is 1.0.
Next, the multicast scheduling algorithm is analyzed when the traffic at the inputs is divided into different priorities according to their significance. For simple, we only have two classes in the paper: class 1 and class 2. According to this problem, the multicast scheduling algorithm with priorities is proposed. Our results demonstrate that: the throughput of the class 1 is higher than the class 2, and the performance of the higher class can be guaranteed. For example, the throughput of the higher class is 0.75 while the throughput of the lower class is decreased to zero.
Finally, the parameters about multicast performance in the DWDM switching network are presented: throughput, blocking probability, transimitting rounds. The throughput is the number of connect requests which are realized to the total number. The rate of the number of connect requests which are lost to the total number of connect requests is called blocking probability. The transmitting rounds is defined as the times taken to transmit all the connection requests, and we have to select a group of multicast connection requests that are contention-free every time.
首先,介绍了三种典型的光分组交换结构,并对它们进行了比较。然后主要研究了基于共享有限波长变换器的SPL光交换结构的多播调度算法。在DWDM光交换网络中,每根光纤分为M个波长信道,当一根输出光纤上的连接请求多于M时就会发生冲突。多播调度算法选择一组无冲突的多播连接请求,在网络中同时调度最大数目的连接请求是一个非确定的多项式难题,因此需要采用近似调度算法。在现有算法的基础上,改进后提出了一种新的近似调度算法:NASA算法。通过实验仿真进行了验证,当光纤数和波长信道数都为8,负载率为1.0时,NASA算法的网络吞吐量提高了约14%。当光纤数和波长信道数都为16,负载率为1.0时,NASA算法的网络吞吐量提高了约11%。从而可以证明,新的调度算法提高了网络吞吐量。
其次,将优先级概念应用到多播光交换网络中,基于这个前提分析了区分优先级的多播调度算法。为方便讨论,本文中分为高、低两个优先级。对分组应用ASA算法,当负载率为0.6时,低优先级分组的吞吐量降为零,而高优先级分组的吞吐量约为0.71。对分组应用NASA算法,当负载率为0.6时,低优先级分组的吞吐量接近为零,而高优先级的分组的吞吐量约为0.75。从而可以证明:高优先级分组的网络吞吐量高于低优先级分组的网络吞吐量,保障了高优先级分组的性能。
最后,提出了DWDM光交换网络实现多播功能时评价其性能的参数:网络吞吐量,阻塞率和传输度。网络吞吐量定义为实现的多播连接请求数与连接请求总数之比;由于网络阻塞等原因造成的多播连接请求丢失的数目与网络中多播连接请求的总数之比即为阻塞率;传输度即为将所有多播连接请求传输完毕所需的传输次数,每次选择一组最大无冲突的多播连接请求。
With the rapid development of the communication technology, network applications, especially the application of multimedia video conference and distance learning, network audio/video frequency, need more bandwidth than the network at present can provide. This problem can be solved by the optical network because of the wide bandwidth of optical fiber, and the DWDM has become the bone network in the communication field. Multicast can send data to multiple receivers from one source or more in an efficient and extendable way, and that it can save bandwidth and reduce the possibility of congestion. The optical switching network introducing multicast can improve the performance of the optical network and the bandwidth usage efficiency. The core node of optical switching network with multicast function is the key technology of the multicast applications. Multicast scheduling algorithm and the performance parameters based on the optical switching network are analyzed in this paper.
First, we introduce three typical structures of optical packet switch, and compare their performance. The multicast scheduling algorithm based on the structure of the optical packet switch with shared limited range wavelength converters is studied in this paper. In DWDM switching networks, contention occurs when one output fiber is the destinations of more than M inputs, where M is the number of wavelengths on each fiber. The multicast scheduling algorithm selects a group of multicast connection requests that are contention-free, and it is a key technology in the DWDM switching network. It is proved that scheduling the maximum number of such connection requests through the network simultaneously is a NP-hard problem, so we have to develop approximation scheduling algorithms that can provide sub-optimal solutions. In this paper, we present a new approximation scheduling algorithm based on the algorithm has been presented before, and compare their performance. We can confirm that the new algorithm can improve the network throughput through simulations. For example, the network throughput of the new algorithm is improved by 14% when the number of fibers and wavelength channels is 8, the load is 1.0.
Next, the multicast scheduling algorithm is analyzed when the traffic at the inputs is divided into different priorities according to their significance. For simple, we only have two classes in the paper: class 1 and class 2. According to this problem, the multicast scheduling algorithm with priorities is proposed. Our results demonstrate that: the throughput of the class 1 is higher than the class 2, and the performance of the higher class can be guaranteed. For example, the throughput of the higher class is 0.75 while the throughput of the lower class is decreased to zero.
Finally, the parameters about multicast performance in the DWDM switching network are presented: throughput, blocking probability, transimitting rounds. The throughput is the number of connect requests which are realized to the total number. The rate of the number of connect requests which are lost to the total number of connect requests is called blocking probability. The transmitting rounds is defined as the times taken to transmit all the connection requests, and we have to select a group of multicast connection requests that are contention-free every time.
引文
[1] http://www.ofcconference.org/conference-program/OFC_s_Market_Watch_.aspx
[2] D.K.Hunter, I.Andonovic. Approaches to optical Internet packet switching. IEEE Communications Magazine, 2000, 116-122 [3 ]郑磊,吴德明,徐安士.光分组交换节点技术.中兴通讯技术,2002,8(5):14-18
[4] C.M.Qiao, M.Yoo. Optical burst switching (OBS)-a new paradigm for an optical Internet. Journal of High Speed Networks, 1999, 8(1):69-84
[5] J.S.Turner. Terabit burst switching. Journal of High Speed Networks, 1999, 8(1):3-16
[6] A.Ganjam, H.Zhang. Internet Multicast Video Delivery. Proceedings of the IEEE, 2005, 93(1):159-170.
[7] Deering. Multicast routing in internetworks and extended LANs. in Proc. ACM SIGCOMM, 1988
[8] Y.Chu, S.Rao, H.Zhang. A case for end system multicast. in Proc. ACM Sigmetrics, 2000
[9] J.Jannotti, D.Gifford, K.L.Johnson, et al. Overcast: Reliable multicasting with an overlay network. In Proc. 4th Symp. Operating System Design Implementation (OSDI), 2000
[10] Akamai [Online]: http://www.akamai.com/
[11] Real Broadcast Network [Online]: http://www.real.com/
[12] Yuanyang Yang, Jianchao Wang, Chunming Qiao. Nonblocking WDM Multicast Switching Networks. IEEE TRANSACTION ON PARALLEL AND DISTRIBUTED SYSTEM, 2000, 11(12):1274-1287
[13] Xijun Zhang, John Y.Wei, Chunming Qiao. Constrained Multicast Routing in WDM Networks with Spares Light Splitter. JOURNAL OF LIGHTWAVE TECHNOLOGY, 2000, 18(12):1917-1927
[14] Shuguang Yan, Jitender S.Deogun, Maher Ali. Routing in spares splitting optical networks with multicast traffic. Computer Networks, 2003, 41:89-113
[15]金明晔等. DWDM技术原理与应用.北京:电子工业出版社, 2003
[16]蒋玲,凌毓涛.光纤通信技术及应用.武汉:华中师范人学出版社,2006
[17] [美]Walter Goralski著.胡先志等译.光网络与波分复用.北京:人民邮电出版社,2004
[18] Walter J. Goralski. Optical Networking and WDM. 1st Edition, McGraw-Hill, 2001
[19] Ausiello.G, D’.Atri.A, Protasi.M. Lattice theoretic ordering properties for NP-complete optimization problems. Annales Societatis Mathematicae Polonae, 1981(4):83-94
[20] V.Eramo,M.Listanti. Packet loss in bufferless optical WDM switch employing shared tunable wavelength converters. J. Lightwave Technol, 2000, 18: 1818-1833
[21] V.Eramo,M.Listanti, P.Pacifici. A Comparison study on the number of wavelength converters needed in synchronous and asynchronous all-optical switching architectures. J. Lightwave Technol, 2003, 21: 340-355
[22] G. Shen et al. Performance study on a WDM packet switch with limited-range wavelength converters. IEEE Communication Letters, 2001, 5(10):432–434
[23] Zhenghao Zhang, Yuanyuan Yang. Performance modeling of bufferless WDM optical packet switching networks with limited range wavelength. San Francisco, Proceedings of IEEE GLOBECOM 2003, 2003, 2498-2502
[24] Xiangdong Qin, Yuanyuan Yang. Blocking Probability in WDM Multicast Switching Networks with Limited Wavelength Conversion. Cambridge, Second IEEE Symposium on Network Computing and Applications, 2003, 322-329
[25] Eramo V, Listanti M, Spaziani M. Resources sharing in optical packet switches with limited-range wavelength Converters. Journal of Lightwave Technology, 2005, 23(2):671-686
[26] V. Eramo, M. Listanti, M. Spaziani. Dimensioning models in optical packet switches equipped with shared limited-range wavelength converters .Global Telecommunication Conference, 2004, 3(29):1735-1741
[27] Zhenghao Zhang, Yuanyuan Yang. Multicast scheduling in WDM switching networks. Alaska, Proceedings of IEEE 2003 International Conference on Communications, 2003, 1458-1462
[28] Zhenghao Zhang, Yuanyuan Yang. Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capacity. IEEE TRANSACTION ON PARALLEL AND DISTRIBUTED SYSTEM, 2004, 18:1012-1026
[29] D.K.Hunter, M.C.Chia, I.Andonovic. Buffering in optical packet switches. Journal of Lightwave Technology, 1998, 16(12):2081-2094
[30] X. Chen, J.F. Hayes. Call scheduling in multicast packet switching. New York, Proc. IEEE ICC’92, 1992,895 - 899
[31] C. Lee, A.Y. Oruc. Design of Efficient and Easily Routable Generalized Connectors. IEEE Trans. Comm., 1995, 43:646-650
[32] Y. Yang, G.M.Masson. Nonblocking Broadcast Switching Networks. IEEE Trans. Computers, 1991, 40(9):1005-1015
[33] G.Bongiovanni, D.Coppersrsmtth, C.K.Wong. An optimum time slot assignment algorithm for an SS/TDMA system with variable number of transponders. IEEE TRANSACTION ON COMMUNICATION, 1981, 29(5):721-726
[34] Hwa-Chun Lin, Chun-Hsin Wang. Minimizing the number of multicast transmissions in the single-hop WDM networks. Photonic Network Communications, 2002, 4(2):191-203
[35] Guowen Han, Yuanyuan Yang. A Random Graph Approach for Multicast Scheduling and Performance Analysis. Computer Communications and Networks, 2003. ICCCN 2003. Proceedings, 2003, 270- 275
[36] Guowen Han, Yuanyuan Yang. Scheduling and performance analysis of multicast interconnects. The Journal of Supercomputing archive, 2007, 40(2):109-125
[37] Deering S. Multicast Routing in a Datagram Internetwork. PhD thesis,Stanford University, 1991
[38] Lawton G. Multicast: will it transform the Internet. IEEE Computer, 1998, 31(7): 13-15
[2] D.K.Hunter, I.Andonovic. Approaches to optical Internet packet switching. IEEE Communications Magazine, 2000, 116-122 [3 ]郑磊,吴德明,徐安士.光分组交换节点技术.中兴通讯技术,2002,8(5):14-18
[4] C.M.Qiao, M.Yoo. Optical burst switching (OBS)-a new paradigm for an optical Internet. Journal of High Speed Networks, 1999, 8(1):69-84
[5] J.S.Turner. Terabit burst switching. Journal of High Speed Networks, 1999, 8(1):3-16
[6] A.Ganjam, H.Zhang. Internet Multicast Video Delivery. Proceedings of the IEEE, 2005, 93(1):159-170.
[7] Deering. Multicast routing in internetworks and extended LANs. in Proc. ACM SIGCOMM, 1988
[8] Y.Chu, S.Rao, H.Zhang. A case for end system multicast. in Proc. ACM Sigmetrics, 2000
[9] J.Jannotti, D.Gifford, K.L.Johnson, et al. Overcast: Reliable multicasting with an overlay network. In Proc. 4th Symp. Operating System Design Implementation (OSDI), 2000
[10] Akamai [Online]: http://www.akamai.com/
[11] Real Broadcast Network [Online]: http://www.real.com/
[12] Yuanyang Yang, Jianchao Wang, Chunming Qiao. Nonblocking WDM Multicast Switching Networks. IEEE TRANSACTION ON PARALLEL AND DISTRIBUTED SYSTEM, 2000, 11(12):1274-1287
[13] Xijun Zhang, John Y.Wei, Chunming Qiao. Constrained Multicast Routing in WDM Networks with Spares Light Splitter. JOURNAL OF LIGHTWAVE TECHNOLOGY, 2000, 18(12):1917-1927
[14] Shuguang Yan, Jitender S.Deogun, Maher Ali. Routing in spares splitting optical networks with multicast traffic. Computer Networks, 2003, 41:89-113
[15]金明晔等. DWDM技术原理与应用.北京:电子工业出版社, 2003
[16]蒋玲,凌毓涛.光纤通信技术及应用.武汉:华中师范人学出版社,2006
[17] [美]Walter Goralski著.胡先志等译.光网络与波分复用.北京:人民邮电出版社,2004
[18] Walter J. Goralski. Optical Networking and WDM. 1st Edition, McGraw-Hill, 2001
[19] Ausiello.G, D’.Atri.A, Protasi.M. Lattice theoretic ordering properties for NP-complete optimization problems. Annales Societatis Mathematicae Polonae, 1981(4):83-94
[20] V.Eramo,M.Listanti. Packet loss in bufferless optical WDM switch employing shared tunable wavelength converters. J. Lightwave Technol, 2000, 18: 1818-1833
[21] V.Eramo,M.Listanti, P.Pacifici. A Comparison study on the number of wavelength converters needed in synchronous and asynchronous all-optical switching architectures. J. Lightwave Technol, 2003, 21: 340-355
[22] G. Shen et al. Performance study on a WDM packet switch with limited-range wavelength converters. IEEE Communication Letters, 2001, 5(10):432–434
[23] Zhenghao Zhang, Yuanyuan Yang. Performance modeling of bufferless WDM optical packet switching networks with limited range wavelength. San Francisco, Proceedings of IEEE GLOBECOM 2003, 2003, 2498-2502
[24] Xiangdong Qin, Yuanyuan Yang. Blocking Probability in WDM Multicast Switching Networks with Limited Wavelength Conversion. Cambridge, Second IEEE Symposium on Network Computing and Applications, 2003, 322-329
[25] Eramo V, Listanti M, Spaziani M. Resources sharing in optical packet switches with limited-range wavelength Converters. Journal of Lightwave Technology, 2005, 23(2):671-686
[26] V. Eramo, M. Listanti, M. Spaziani. Dimensioning models in optical packet switches equipped with shared limited-range wavelength converters .Global Telecommunication Conference, 2004, 3(29):1735-1741
[27] Zhenghao Zhang, Yuanyuan Yang. Multicast scheduling in WDM switching networks. Alaska, Proceedings of IEEE 2003 International Conference on Communications, 2003, 1458-1462
[28] Zhenghao Zhang, Yuanyuan Yang. Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capacity. IEEE TRANSACTION ON PARALLEL AND DISTRIBUTED SYSTEM, 2004, 18:1012-1026
[29] D.K.Hunter, M.C.Chia, I.Andonovic. Buffering in optical packet switches. Journal of Lightwave Technology, 1998, 16(12):2081-2094
[30] X. Chen, J.F. Hayes. Call scheduling in multicast packet switching. New York, Proc. IEEE ICC’92, 1992,895 - 899
[31] C. Lee, A.Y. Oruc. Design of Efficient and Easily Routable Generalized Connectors. IEEE Trans. Comm., 1995, 43:646-650
[32] Y. Yang, G.M.Masson. Nonblocking Broadcast Switching Networks. IEEE Trans. Computers, 1991, 40(9):1005-1015
[33] G.Bongiovanni, D.Coppersrsmtth, C.K.Wong. An optimum time slot assignment algorithm for an SS/TDMA system with variable number of transponders. IEEE TRANSACTION ON COMMUNICATION, 1981, 29(5):721-726
[34] Hwa-Chun Lin, Chun-Hsin Wang. Minimizing the number of multicast transmissions in the single-hop WDM networks. Photonic Network Communications, 2002, 4(2):191-203
[35] Guowen Han, Yuanyuan Yang. A Random Graph Approach for Multicast Scheduling and Performance Analysis. Computer Communications and Networks, 2003. ICCCN 2003. Proceedings, 2003, 270- 275
[36] Guowen Han, Yuanyuan Yang. Scheduling and performance analysis of multicast interconnects. The Journal of Supercomputing archive, 2007, 40(2):109-125
[37] Deering S. Multicast Routing in a Datagram Internetwork. PhD thesis,Stanford University, 1991
[38] Lawton G. Multicast: will it transform the Internet. IEEE Computer, 1998, 31(7): 13-15