全光组播网络中的线性网络编码技术研究
|
摘要
随着新型数据业务(如VoIP、IPTV、视频会议、VOD、多媒体远程教育等)的增多,人们对组播业务,特别是宽带组播新型业务的需求量越来越大,对于组播业务的质量要求也不断提高。而最先发展起来的电层组播由于其自身带宽不足以及数据处理速度低等原因已不能很好地满足日益增长的宽带业务的需求,那么光网络以其独有的宽带宽和高速率的传输能力,智能和灵活的网络管理能力,良好的健壮性和生存性逐渐成为了组播技术的首选载体。而网络编码技术的出现,使得在光网络中实现高吞吐量,低时延的宽带数据业务组播传输有了无限的可能。网络编码技术是一种融合了编码和路由的信息交换技术,它通过允许网络节点对接收到的数据进行编码信息的融合,增加单次传输的信息量来提高组播网络的整体性能。但是,目前所研究的网络编码技术大多数仅限于电层的组播网络,对于网络编码在光网络中的相关研究还不够深入和成熟。鉴于网络编码技术在改善组播网络的性能方面的各种优越性,探讨如何成功地把网络编码技术,特别是线性网络编码技术应用于全光组播网络中来促进未来光网络朝着高吞吐量低时延高效率的方向发展显得尤为重要。
本文深入研究了线性网络编码技术及其在全光组播网络中的应用与实现,特别是对线性网络编解码构造过程中的编码向量分配问题进行了创新性地探讨,提出了上溯式编码向量分配方法和基于图着色的编码向量分配方法；另外,针对分布式网络编码的实现,提出了分布式网络编码资源自适应调度算法；最后,本文还研究了全光组播网络中的线性网络编码的策略,并在实验平台中采用基于半导体光放大器SOA的交叉增益调制效应的逻辑异或门实现了所提出的全光组播网络中的网络编解码算法,并验证了光网络编解码策略的有效性和可行性。
With the rapid development of network traffic, optical network, which has the properties of high speed, large bandwidth capacity and more flexible ability for network management, has been considered as the inevitable trend to support many future point-to-multipoint bandwidth-intensive applications,such as high-definition television(HDTV), multimedia document distribution and distributed games and so on.Besides,optical multicast can provide more superiorities than IP multicast when there are more and more demands in multicasting traffic.These intriguing observations prompt further investigation into optical multicast networks.However, the traditional optical multicast networks still cannot reach the maximum mujticast flow, while network coding, as a recently arisen technology, enables better resource utilization and improved throughput in optical multicast networks.Network coding allows the data from different incoming ports to be encoded instead of the conventional store-and-forward processing scheme in the multicast networks,the theoretical max-flow bound can be achieved, which is determined by the well known max-flow min-cut theorem. Furthermore, to achieve this upper flow bound, linear network coding is sufficiently enough. Accordingly, adapting network coding to optical multicast networks will facilitate the future development of effective optical networks.
However, most of the proposed network coding schemes so fa is designed for the Electrical Layer (EL). While in all-optical networks, due to the limited buffering capability and weak logic operation ability of the actual optical network, employing linear network coding in all-optical multicast networks is still a tough problem.
This paper pays much attention on the related fundamental theories and systemic concepts of linear network coding and its implement in all-optical multicast networks.Specially, the problem of the assignment of encoding vectors in the construction process of network coding is thoroughly investigated. Meanwhile, two methods to assign the encoding vectors have been proposed: the reversed method and the dynamic method based on the Graph Coloring for the assignment of the encoding vectors in multicast networks.Furthermore, another novel arithmetic which involves the scheduling arithmetic of the encoding source has been proposed for the distributed networks.Moreover, a hardware experimental platform, introducing the XOR gate based on the XGM in SOA, is put up to support and the proposed novel scheme for linear network coding in the practical all-optical multicast networks.Moreover, the experimental demonstration indicates that it is feasible and efficient to employing network coding in optical-layer multicast traffic.
本文深入研究了线性网络编码技术及其在全光组播网络中的应用与实现,特别是对线性网络编解码构造过程中的编码向量分配问题进行了创新性地探讨,提出了上溯式编码向量分配方法和基于图着色的编码向量分配方法；另外,针对分布式网络编码的实现,提出了分布式网络编码资源自适应调度算法；最后,本文还研究了全光组播网络中的线性网络编码的策略,并在实验平台中采用基于半导体光放大器SOA的交叉增益调制效应的逻辑异或门实现了所提出的全光组播网络中的网络编解码算法,并验证了光网络编解码策略的有效性和可行性。
With the rapid development of network traffic, optical network, which has the properties of high speed, large bandwidth capacity and more flexible ability for network management, has been considered as the inevitable trend to support many future point-to-multipoint bandwidth-intensive applications,such as high-definition television(HDTV), multimedia document distribution and distributed games and so on.Besides,optical multicast can provide more superiorities than IP multicast when there are more and more demands in multicasting traffic.These intriguing observations prompt further investigation into optical multicast networks.However, the traditional optical multicast networks still cannot reach the maximum mujticast flow, while network coding, as a recently arisen technology, enables better resource utilization and improved throughput in optical multicast networks.Network coding allows the data from different incoming ports to be encoded instead of the conventional store-and-forward processing scheme in the multicast networks,the theoretical max-flow bound can be achieved, which is determined by the well known max-flow min-cut theorem. Furthermore, to achieve this upper flow bound, linear network coding is sufficiently enough. Accordingly, adapting network coding to optical multicast networks will facilitate the future development of effective optical networks.
However, most of the proposed network coding schemes so fa is designed for the Electrical Layer (EL). While in all-optical networks, due to the limited buffering capability and weak logic operation ability of the actual optical network, employing linear network coding in all-optical multicast networks is still a tough problem.
This paper pays much attention on the related fundamental theories and systemic concepts of linear network coding and its implement in all-optical multicast networks.Specially, the problem of the assignment of encoding vectors in the construction process of network coding is thoroughly investigated. Meanwhile, two methods to assign the encoding vectors have been proposed: the reversed method and the dynamic method based on the Graph Coloring for the assignment of the encoding vectors in multicast networks.Furthermore, another novel arithmetic which involves the scheduling arithmetic of the encoding source has been proposed for the distributed networks.Moreover, a hardware experimental platform, introducing the XOR gate based on the XGM in SOA, is put up to support and the proposed novel scheme for linear network coding in the practical all-optical multicast networks.Moreover, the experimental demonstration indicates that it is feasible and efficient to employing network coding in optical-layer multicast traffic.
引文
[1]李成忠,张新有等,“计算机网络原理与设计”,北京：高等教育出版社,2003年
[2]B.Wang and J. C.Hou, "Multicast routing and its QoS extension:problems, algorithms, and protocols", IEEE Network, vol.14, no.1,January/February 2000, pp.22-36
[3]谢希仁,“计算机网络(第4版)”,北京：电子工业出版社,2003年
[4]Rouskas, G. N.,"Optical layer multicast:rationale, building blocks, and challenges", IEEE, Network, 2003, vol.17, no.l,2003, pp.60-65
[5]谢胡,范戈,许毅,“组播技术及其在光层的实现”光纤与电缆及其应用技术2006年05期
[6]A. E. Kamal,"1+N protection in optical mesh networks using network coding on p-cycles," in Proc. IEEE Globecom 2006.
[7]R. Ahlswede, N. Cai, S.R. Li, et al.,"Network information flow", IEEE Transactions on Information Theory, vol.46, no.4, July 2000, pp.1204-1216
[8]S.R. Li, R. W. Yeung, and N. Cai, "Linear network coding", IEEE Transactions on Information Theory, vol.49, no.2, February 2003, pp.371-381
[9]R. Kotter and M. Medard, "Beyond routing:an algebraic approach to network coding", in Proc. of the 2002 IEEE INFOCOM, vol.1,2002, pp.122-130
[10]R. Kotter and M. Medard, "An algebraic approach to network coding", IEEE/ACM Transactions on Networking, vol.11, no.5,2003, pp.782-795
[11]J Y Zhang,K Cai,K B Letaief,et al."A network coding unicast strategy for wireless multi-hop networks" [C] IEEE Wireless Communication & Networking Conf (WCNC), Hong Kong,2007
[12]P. Sanders, S.Egner, et al. "Polynomial time algorithms for network information flow", IEEE Transactions on Information Theory,vol.52,no.3,2006, pp.829-848
[13]S Jaggi,P Sanders,P A Chou,et al."Polynomial time algorithms for multicast network code construction" [J]IEEE Trans on Information Theory,2005,nol.51, no.6, pp.1973-1982
[14]P A Chou,Y N Wu,K Jain. "Practical network coding" [C] The 41st Annual Allerton Conf on Communication,Control,and Computing,Monticello, IL,2003
[15]Fragouli, C.;Soljanin, E."Decentralized network coding" Information Theory Workshop,2004. IEEE 24-29 Oct.2004, pp.310-314
[16]Y.Zhu, B.Li, and J.Guo, "Multicast with network coding in application-layer overlay networks", IEEE Journal on Selected Areas in Communications, vol.22, no.1, January 2004, pp.1-13
[17]T. Ho, M. Medard, et al. "On randomized network coding", In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing,2003
[18]Z. Li and B.Li, "Improving throughput in multihop wireless networks", IEEE Transaction on Vehicular Technology, vol.55, no.3, May 2006, pp.762-773.
[19]Y. E. Sagduyu and A. Ephremides, "On Joint MAC and network coding in wireless Ad Hoc networks", IEEE Transactions on Information Theory, vol.53, no.10, October 2007, pp.3697-3713
[20]Y. Wu, P.A. Chou and S. Kung, "Minimum-energy multicast in mobile ad-hoc networks using network coding", IEEE Transactions on Communications, Volume 53,Issue 11, Nov.2005, pp. 1906-1918
[21]Widmer J,Fragouli C,Le Boudec J-Y." Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding".In:Proc.WINMEE,RAWNET and NETCOD 2005Workshops, Apr.2005
[22]Y. Wu,P. A. Chou, et al. "Network planning in wireless ad hoc network:a cross-layer approach" IEEE Journal on Selected Areas in Communications, Vol.23,Issue.1, Jan.2005, pp.136-150
[23]H. L. Xuan, et al. "Minimum-energy data dissemination in coordination-based sensor networks",11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2005.
[24]X. Zhang, S.B.Wicker, et al. "Robustness vs. efficiency in sensor networks", Fourth International Symposium on Information Processing in Sensor Networks,2005.
[25]Jingyao Zhang, Pingyi Fan,"On Network coding in Wireless ad Hoc networks" International Journal of Ad Hoc and Ubiquitous Computing Vol.2, No.3,2007, pp.140-148
[26]刘亚杰,窦文华.“基于网络编码的P2P流媒体”计算机工程与科学,2006年第28卷第9期
[27]Jin Zhao, Fan Yang, Qian Zhang et al, "LION:Layered overlay multicast with network coding", IEEE Transactions on multimedia, vol.8, no.5, October 2006, pp.1021-1032
[28]Y. Liu, W. Dou and Z. Liu, "Layer allocation algorithms in layered peer-to-peer streaming", IFTP International Conference on Network and Parallel Computing (NPC2004), LNCS:3222, October 2004, pp.167-174
[29]K. Chi and X. Wang, "Analysis of network error correction based on network coding", IEE Proceedings-Communications, vol.152, issue 4, August 2005, pp.393-396
[30]K. Chi, C.Yang and X. Wang, "Performance of network coding based multicast", IEE Proceedings-Communications, vol.153, issue 3, June 2006, pp.399-404
[31]A. E. Kamal, "GMPLS-based hybrid 1+N link protection over p-cycles:design and performance", in Proc.2007 IEEE Global Telecommunications Conference (GLOBECOM'07), November 2007, pp. 2298-2303
[32]A. E. Kamal,"1+N protection against multiple link failures in mesh networks", in Proc.2007 IEEE International Conference on Communications (ICC'07), June 2007, pp.2224-2229
[33]R. C. Menendez and J. W. Gannett, "Efficient, fault-tolerant all-optical multicast networks via network coding", in Proc.2008 Optical Fiber Communication/National Fiber Optic Engineers Conference (OFC/NFOEC 2008), February 2008, pp.1-3
[34]Eric D. Manley, Jitender S. Deogun and Lisong Xu, "Network coding for optical layer multicast", in Proc. Broadband Communications, Network and Systems (BROADNETS 2008),2008, pp.452-459
[35]R K Ahuja,T L Magnanti,J B Orlin." Network Flows:Theory,Algorithms,and Applications" [M]. Englewood Cliffs,NJ:Prentice Hall,1993
[36]Minkyu Kim, Muriel Medard, Una-May O'Reilly, "Network Coding and Its Implications on Optical Networking"in Proc. OFC/NFOEC 2009
[37]D Wang,Q Zhang,J C Liu."Partial network coding:Theory and application in continuous sensor data collection" [C].The 14th IEEE Int'l Workshop on Quality of Service(IWQoS 2006),New Haven, CT, USA,2006
[38]Raymond W.Yeung,Shuo-Yen Robert Li,Ning Cai,Zhen Zhang,"Network Coding Theory",2006, pp.15-22
[39]S L Fong, R W Yeung. "Variable rate linear network coding"[C] IEEE Information Theory Workshop, Chengdu,2006
[40]Axel Davidian,"Network Coding:An Overview" in Seminar on Topics in Communications Engineering,2005
[41]Fragouli, C.;Soljanin, E. "Information flow decomposition for network coding" Information Theory, IEEE Transactions on Volume 52,Issue 3,March 2006,pp.829-848
[42]T Ho,D R Karger,M Medard,et al."The benefits of coding over routing in a randomized setting" [C] IEEE Int'l Symp on Information Theory(ISIT),Pacifico Yokohama, Yokohama,2003
[43]X. Zhang, G.Neglia, J. Kurose, and D.Towsley,"On the benefits of random linear coding for unicast applications in disruption tolerant networks", UMASS Computer Science, Technical Report 2006-15
[44]Y.Wu, "Network coding for multicasting" Ph.D. dissertation,Princeton Univ.,Princeton, NJ, Nov. 2005.
[45]H. Fan, C. Wu, N.K. Dutta, U. Koren, C.H. Chen, "Cross gain saturation in semiconductor optical amplifier", Lasers and Electro-Optics Society Annual Meeting,1998
[46]Jensen T R,Toft B."Graph Coloring Problems".New York:A Wiley-Interscience Publication,1995.
[47]Glass C A,Bennett A P. "Genetic algorithm for graph coloring:exploration of galinier and Hao's algorithm"[J].Journal of Combinatorial Optimization, vol.7,2003, pp.229-236.
[48]Liang J,Kumar R,Xi Y,Ross K W. Pollution inP2P File Sharing Systems.Proceedings of IEEE Infocom2005.24th Aunual Joint Conference of the IEEE Computer and Communications Societies. Miami FL.2005, pp.1174-1185
[49]Sun Microsystems, Inc. "introduction to cloud computing architecture" Web sun.com,2009
[50]E. Manley, J. Deogun, and L. Xu. "Network Coding for Optical-Layer Multicast" in Proceedings of the fifth International Conference on Broadband Communications, Networks, and Systems (BROADNETS), Lodon, UK,2008, pp.452
[51]M. Asghari, I.H.White, and R.V. Penty, Wavelength conversion using semiconductor optical amplifiers, J Lightwave Technol 15,1997, pp.1181-1190
[2]B.Wang and J. C.Hou, "Multicast routing and its QoS extension:problems, algorithms, and protocols", IEEE Network, vol.14, no.1,January/February 2000, pp.22-36
[3]谢希仁,“计算机网络(第4版)”,北京：电子工业出版社,2003年
[4]Rouskas, G. N.,"Optical layer multicast:rationale, building blocks, and challenges", IEEE, Network, 2003, vol.17, no.l,2003, pp.60-65
[5]谢胡,范戈,许毅,“组播技术及其在光层的实现”光纤与电缆及其应用技术2006年05期
[6]A. E. Kamal,"1+N protection in optical mesh networks using network coding on p-cycles," in Proc. IEEE Globecom 2006.
[7]R. Ahlswede, N. Cai, S.R. Li, et al.,"Network information flow", IEEE Transactions on Information Theory, vol.46, no.4, July 2000, pp.1204-1216
[8]S.R. Li, R. W. Yeung, and N. Cai, "Linear network coding", IEEE Transactions on Information Theory, vol.49, no.2, February 2003, pp.371-381
[9]R. Kotter and M. Medard, "Beyond routing:an algebraic approach to network coding", in Proc. of the 2002 IEEE INFOCOM, vol.1,2002, pp.122-130
[10]R. Kotter and M. Medard, "An algebraic approach to network coding", IEEE/ACM Transactions on Networking, vol.11, no.5,2003, pp.782-795
[11]J Y Zhang,K Cai,K B Letaief,et al."A network coding unicast strategy for wireless multi-hop networks" [C] IEEE Wireless Communication & Networking Conf (WCNC), Hong Kong,2007
[12]P. Sanders, S.Egner, et al. "Polynomial time algorithms for network information flow", IEEE Transactions on Information Theory,vol.52,no.3,2006, pp.829-848
[13]S Jaggi,P Sanders,P A Chou,et al."Polynomial time algorithms for multicast network code construction" [J]IEEE Trans on Information Theory,2005,nol.51, no.6, pp.1973-1982
[14]P A Chou,Y N Wu,K Jain. "Practical network coding" [C] The 41st Annual Allerton Conf on Communication,Control,and Computing,Monticello, IL,2003
[15]Fragouli, C.;Soljanin, E."Decentralized network coding" Information Theory Workshop,2004. IEEE 24-29 Oct.2004, pp.310-314
[16]Y.Zhu, B.Li, and J.Guo, "Multicast with network coding in application-layer overlay networks", IEEE Journal on Selected Areas in Communications, vol.22, no.1, January 2004, pp.1-13
[17]T. Ho, M. Medard, et al. "On randomized network coding", In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing,2003
[18]Z. Li and B.Li, "Improving throughput in multihop wireless networks", IEEE Transaction on Vehicular Technology, vol.55, no.3, May 2006, pp.762-773.
[19]Y. E. Sagduyu and A. Ephremides, "On Joint MAC and network coding in wireless Ad Hoc networks", IEEE Transactions on Information Theory, vol.53, no.10, October 2007, pp.3697-3713
[20]Y. Wu, P.A. Chou and S. Kung, "Minimum-energy multicast in mobile ad-hoc networks using network coding", IEEE Transactions on Communications, Volume 53,Issue 11, Nov.2005, pp. 1906-1918
[21]Widmer J,Fragouli C,Le Boudec J-Y." Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding".In:Proc.WINMEE,RAWNET and NETCOD 2005Workshops, Apr.2005
[22]Y. Wu,P. A. Chou, et al. "Network planning in wireless ad hoc network:a cross-layer approach" IEEE Journal on Selected Areas in Communications, Vol.23,Issue.1, Jan.2005, pp.136-150
[23]H. L. Xuan, et al. "Minimum-energy data dissemination in coordination-based sensor networks",11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2005.
[24]X. Zhang, S.B.Wicker, et al. "Robustness vs. efficiency in sensor networks", Fourth International Symposium on Information Processing in Sensor Networks,2005.
[25]Jingyao Zhang, Pingyi Fan,"On Network coding in Wireless ad Hoc networks" International Journal of Ad Hoc and Ubiquitous Computing Vol.2, No.3,2007, pp.140-148
[26]刘亚杰,窦文华.“基于网络编码的P2P流媒体”计算机工程与科学,2006年第28卷第9期
[27]Jin Zhao, Fan Yang, Qian Zhang et al, "LION:Layered overlay multicast with network coding", IEEE Transactions on multimedia, vol.8, no.5, October 2006, pp.1021-1032
[28]Y. Liu, W. Dou and Z. Liu, "Layer allocation algorithms in layered peer-to-peer streaming", IFTP International Conference on Network and Parallel Computing (NPC2004), LNCS:3222, October 2004, pp.167-174
[29]K. Chi and X. Wang, "Analysis of network error correction based on network coding", IEE Proceedings-Communications, vol.152, issue 4, August 2005, pp.393-396
[30]K. Chi, C.Yang and X. Wang, "Performance of network coding based multicast", IEE Proceedings-Communications, vol.153, issue 3, June 2006, pp.399-404
[31]A. E. Kamal, "GMPLS-based hybrid 1+N link protection over p-cycles:design and performance", in Proc.2007 IEEE Global Telecommunications Conference (GLOBECOM'07), November 2007, pp. 2298-2303
[32]A. E. Kamal,"1+N protection against multiple link failures in mesh networks", in Proc.2007 IEEE International Conference on Communications (ICC'07), June 2007, pp.2224-2229
[33]R. C. Menendez and J. W. Gannett, "Efficient, fault-tolerant all-optical multicast networks via network coding", in Proc.2008 Optical Fiber Communication/National Fiber Optic Engineers Conference (OFC/NFOEC 2008), February 2008, pp.1-3
[34]Eric D. Manley, Jitender S. Deogun and Lisong Xu, "Network coding for optical layer multicast", in Proc. Broadband Communications, Network and Systems (BROADNETS 2008),2008, pp.452-459
[35]R K Ahuja,T L Magnanti,J B Orlin." Network Flows:Theory,Algorithms,and Applications" [M]. Englewood Cliffs,NJ:Prentice Hall,1993
[36]Minkyu Kim, Muriel Medard, Una-May O'Reilly, "Network Coding and Its Implications on Optical Networking"in Proc. OFC/NFOEC 2009
[37]D Wang,Q Zhang,J C Liu."Partial network coding:Theory and application in continuous sensor data collection" [C].The 14th IEEE Int'l Workshop on Quality of Service(IWQoS 2006),New Haven, CT, USA,2006
[38]Raymond W.Yeung,Shuo-Yen Robert Li,Ning Cai,Zhen Zhang,"Network Coding Theory",2006, pp.15-22
[39]S L Fong, R W Yeung. "Variable rate linear network coding"[C] IEEE Information Theory Workshop, Chengdu,2006
[40]Axel Davidian,"Network Coding:An Overview" in Seminar on Topics in Communications Engineering,2005
[41]Fragouli, C.;Soljanin, E. "Information flow decomposition for network coding" Information Theory, IEEE Transactions on Volume 52,Issue 3,March 2006,pp.829-848
[42]T Ho,D R Karger,M Medard,et al."The benefits of coding over routing in a randomized setting" [C] IEEE Int'l Symp on Information Theory(ISIT),Pacifico Yokohama, Yokohama,2003
[43]X. Zhang, G.Neglia, J. Kurose, and D.Towsley,"On the benefits of random linear coding for unicast applications in disruption tolerant networks", UMASS Computer Science, Technical Report 2006-15
[44]Y.Wu, "Network coding for multicasting" Ph.D. dissertation,Princeton Univ.,Princeton, NJ, Nov. 2005.
[45]H. Fan, C. Wu, N.K. Dutta, U. Koren, C.H. Chen, "Cross gain saturation in semiconductor optical amplifier", Lasers and Electro-Optics Society Annual Meeting,1998
[46]Jensen T R,Toft B."Graph Coloring Problems".New York:A Wiley-Interscience Publication,1995.
[47]Glass C A,Bennett A P. "Genetic algorithm for graph coloring:exploration of galinier and Hao's algorithm"[J].Journal of Combinatorial Optimization, vol.7,2003, pp.229-236.
[48]Liang J,Kumar R,Xi Y,Ross K W. Pollution inP2P File Sharing Systems.Proceedings of IEEE Infocom2005.24th Aunual Joint Conference of the IEEE Computer and Communications Societies. Miami FL.2005, pp.1174-1185
[49]Sun Microsystems, Inc. "introduction to cloud computing architecture" Web sun.com,2009
[50]E. Manley, J. Deogun, and L. Xu. "Network Coding for Optical-Layer Multicast" in Proceedings of the fifth International Conference on Broadband Communications, Networks, and Systems (BROADNETS), Lodon, UK,2008, pp.452
[51]M. Asghari, I.H.White, and R.V. Penty, Wavelength conversion using semiconductor optical amplifiers, J Lightwave Technol 15,1997, pp.1181-1190