DS-TE网络中自适应资源抢占策略及抢占算法研究
|
摘要
随着Internet的日益普及,Internet上的主要业务由传统的文件传送、电子邮件和远程登录等转向多媒体应用,多媒体通信要求网络能提供具有不同QoS等级的综合业务(如时延、带宽、分组丢失率的保证)。为此,IETF引入了支持区分服务的MPLS流量工程(DiffServ-aware MPLS Traffic Engineering, DS-TE),它结合了区分服务良好的可扩展性和MPLS流量工程的有效路由策略,允许按照服务类型对区域内的网络资源进行划分,从而将网络细分为具有不同QoS保证能力的虚拟网络。
在DS-TE网络中,资源抢占策略是带宽预留和管理问题的一种重要策略,用于保证在区分服务的环境中为高优先级的业务提供可靠的服务质量,尤其是当网络过载或者网络节点、链路发生故障时更加有效。连接抢占问题己被证明是一个NP完全问题,因此在实际网络中需要设计简单易行的启发式算法。本文在研究分析了Min-Conn、Min-BW、V-PREPT和H-PREPT等抢占算法的基础上,提出了一种新的抢占算法——自适应抢占算法,算法的基本思想是通过增强链路上节点LSR对LSP的资源控制能力,使LSR具备管理LSP占用带宽资源的能力。LSR实施硬抢占的同时,选择一部分优先级较低的LSP,减少它们的传输速率以适应新LSP的带宽需求。在起始端LSR选择减少速率后,标记分发协议将更新LSP每个LSR带宽。为了避免对参数的配置,自适应抢占算法分为自适应最小中断抢占算法(A-minconn)和自适应最小优先级抢占算法(A-minpri), A-minconn算法侧重于降低抢占数目和带宽浪费,A-minpri算法侧重于降低抢占优先级和带宽浪费,抢占时可通过侧重点不同灵活选用两种算法。仿真实验结果表明,与Min-Conn算法和V-PREPT算法相比,自适应抢占算法抢占代价更小、抢占结果更精确,并且避免了对代价函数参数的配置,适用于实际网络。
With the growing popularity of the Internet, the primary services are changing from the traditional file transfer, e-mail and Telnet to the multimedia application, which needs the network to provide integrated services with different QoS level (such as latency, bandwidth, packets losing rate guarantee). Thus, IETF introduced DiffServ-aware MPLS Traffic Engineering (DS-TE), which combines the good scalability of DiffServ and the effective routing strategy of MPLS traffic engineering and allows the regional network resources to be divided in accordance with the class of service. Thus the networks will be subdivided into virtual networks with different QoS capabilities.
In the DS-TE networks, resource preemption strategy is an important strategy for bandwidth set and management, which ensures the priority business reliable high quality on the DiffServ differentiated service environment. And it will be more effective especially when the network load or network node or link failure occur. It had been proven that the problem of deciding the combination of connections for preemption is NP-complete in nature, so in the actual network a simple heuristic algorithm should be designed. In this paper, based on the analysis of preemption algorithm such as Min-Conn, Min-BW, V-PREPT and H-PREPT, a new preemption algorithm is proposed--Adaptive preemption algorithm whose basic thought is to equip LSR with the capability of managing the LSP bandwidth resources by strengthening the node LSR resource control over the LSP on the links. When the LSR hard preemption occurs, LSR chooses some lower priority LSP and reduces their transmission rate to adapt to the new LSP bandwidth demand. When the LSR rate reduction occurs on the initiating terminal, LDP will update each LSR bandwidth of the LSP. To avoid the parameters configuration, the adaptive preemption algorithm is divided into A-minconn algorithm and A-minpri algorithm. A-minconn algorithm lays emphasis on reducing the numbers of preempted LSP and bandwidth waste, while A-minpri algorithm lays emphasis on reducing preemption priority and bandwidth waste. When the preemption occurs, the two algorithms can be chosen flexibly in accordance with different emphases. Simulation results show that compared with the Min-Conn algorithm and V-PREPT algorithm, the adaptive preemption algorithm is suitable for the actual network, paying less cost, having more accurate preemption results and avoiding the parameters configuration for the cost function.
在DS-TE网络中,资源抢占策略是带宽预留和管理问题的一种重要策略,用于保证在区分服务的环境中为高优先级的业务提供可靠的服务质量,尤其是当网络过载或者网络节点、链路发生故障时更加有效。连接抢占问题己被证明是一个NP完全问题,因此在实际网络中需要设计简单易行的启发式算法。本文在研究分析了Min-Conn、Min-BW、V-PREPT和H-PREPT等抢占算法的基础上,提出了一种新的抢占算法——自适应抢占算法,算法的基本思想是通过增强链路上节点LSR对LSP的资源控制能力,使LSR具备管理LSP占用带宽资源的能力。LSR实施硬抢占的同时,选择一部分优先级较低的LSP,减少它们的传输速率以适应新LSP的带宽需求。在起始端LSR选择减少速率后,标记分发协议将更新LSP每个LSR带宽。为了避免对参数的配置,自适应抢占算法分为自适应最小中断抢占算法(A-minconn)和自适应最小优先级抢占算法(A-minpri), A-minconn算法侧重于降低抢占数目和带宽浪费,A-minpri算法侧重于降低抢占优先级和带宽浪费,抢占时可通过侧重点不同灵活选用两种算法。仿真实验结果表明,与Min-Conn算法和V-PREPT算法相比,自适应抢占算法抢占代价更小、抢占结果更精确,并且避免了对代价函数参数的配置,适用于实际网络。
With the growing popularity of the Internet, the primary services are changing from the traditional file transfer, e-mail and Telnet to the multimedia application, which needs the network to provide integrated services with different QoS level (such as latency, bandwidth, packets losing rate guarantee). Thus, IETF introduced DiffServ-aware MPLS Traffic Engineering (DS-TE), which combines the good scalability of DiffServ and the effective routing strategy of MPLS traffic engineering and allows the regional network resources to be divided in accordance with the class of service. Thus the networks will be subdivided into virtual networks with different QoS capabilities.
In the DS-TE networks, resource preemption strategy is an important strategy for bandwidth set and management, which ensures the priority business reliable high quality on the DiffServ differentiated service environment. And it will be more effective especially when the network load or network node or link failure occur. It had been proven that the problem of deciding the combination of connections for preemption is NP-complete in nature, so in the actual network a simple heuristic algorithm should be designed. In this paper, based on the analysis of preemption algorithm such as Min-Conn, Min-BW, V-PREPT and H-PREPT, a new preemption algorithm is proposed--Adaptive preemption algorithm whose basic thought is to equip LSR with the capability of managing the LSP bandwidth resources by strengthening the node LSR resource control over the LSP on the links. When the LSR hard preemption occurs, LSR chooses some lower priority LSP and reduces their transmission rate to adapt to the new LSP bandwidth demand. When the LSR rate reduction occurs on the initiating terminal, LDP will update each LSR bandwidth of the LSP. To avoid the parameters configuration, the adaptive preemption algorithm is divided into A-minconn algorithm and A-minpri algorithm. A-minconn algorithm lays emphasis on reducing the numbers of preempted LSP and bandwidth waste, while A-minpri algorithm lays emphasis on reducing preemption priority and bandwidth waste. When the preemption occurs, the two algorithms can be chosen flexibly in accordance with different emphases. Simulation results show that compared with the Min-Conn algorithm and V-PREPT algorithm, the adaptive preemption algorithm is suitable for the actual network, paying less cost, having more accurate preemption results and avoiding the parameters configuration for the cost function.
引文
1. E. Rosen, A. Viswanathan, R.Callon. Multiprotocol Label Switching Architecture [S], IETF RFC 3031, January 2001.
2. D. Awduche, J.Malcolm, J. Agogbua, et al. Requirements for Traffic Engineering Over MPLS [S], IETF RFC 2702, September 1999.
3. F. Le Faucheur, L Wu, B. Davie, et al. Multi-protocol label switching (MPLS) support of differentiated services [S], IETF RFC 3270, May 2002.
4. F. Le Faucheur, W. Lai. Requirements for Support of Differentiated Services-aware MPLS Traffic Engineering [S], IETF RFC 3564, July 2003.
5. F. Le Faucheur. Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4127, June 2005.
6. F. Le Faucheur, W. Lai. Maximum Allocation Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4125, June 2005.
7. Jerry Ash, Max Alocation with Reservation Bandwidth Constraints Model for DiffServ-aware MPLS Trafic Engineering&Performance Comparisons [S], IETF Internet Draft, draft-ietf-tewg-diff-te-mar-06, December 2004
8. F. Le Faucheur Ed. Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4124, June 2005.
9. J. de Oliveira, JP. Vasseur, L. Chen, et al. Label Switched Path (LSP) Preemption Policies for MPLS Traffic Engineering [S]. IETF RFC 4829, April 2007.
10. Apostolopoulos G, Kama S, Williams D, et al. QoS Routing Mechanisms and OSPF extensions [S], IETF RFC 2676, August 1999.
11. S.Kamei, T.Kimura, Evaluation of routing algorithms and network topologies for MPLS traffic engineering [C]//Proceeding of IEEE GLOBECOM 2001, San Antonio, IEEE, Nov.2001,1:25-29.
12. Suri S, Waldvogel M, Warkhede PR. Profile-Based Routing and traffic engineering [J], computer communications,2003,26(4):351-365.
13. P. Kumar, N. Khanakoti, S. Gopalan, et al. CoS Based LSP Selection in MPLS Network [J], HSNMC,2004,3079:314-323.
14. R. Rabbat, K. Laberteaux, N. Modi, et al. Traffic engineering algorithms using MPLS for service differentiation [C]//Proceedings of IEEE ICC 2000, [S.l.], IEEE, June 2000, 2:791-795.
15. M. Peyravian, A. D. Kshemkalyani. Decentralized network connection preemption algorithms [J], Computer network and ISDN systems, June 1998,30(11):1029-1043.
16. J.A.Garay, I.S.Gopal. Call Preemption in Communication Networks [C]//Proceedings of the IEEE INFOCOM'92, [S.l.], IEEE, May 1992,3:1043-1050.
17. M. Peyravian, A.D. Kshemkalyani. Connection Preemption:Issues, Algorithms, and a Simulation Study [C]//INFOCOM'97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Kobe:[s.n.],1997:143-151.
18. V. Stanisic, M. Devetsikiotis. A dynamic study of providing quality of service using preemption policies with random selection [C]//Proceedings of IEEE ICC 2003, [S.l.], IEEE, May 2003,3:1543-1546.
19. S. Jeon, R.T. Abler, A.E.Goulart. The optimal connection preemption algorithm in a multi-class network [C]//Proceedings of IEEE ICC 2002, NY, IEEE,2002,4:2294-2298.
20. C. H. Lau, B. H. Soong, S. K. Bose. SERA:Service ratio based preemption for minimizing throughput loss in network [C]//TENCON-IEEE Region 10 Conference Proceedings, Melbourne, Australia, IEEE,2006:1196-1201.
21. F. Blanchy, L. Melon, G. Leduc. Routing in a MPLS network featuring preemption mechanisms [C]//Proceedings of ICT 2003, [S.I.], IEEE,2003,1:253-260.
22. I. Ahman, J. Kamruzzaman, S. Aswathanarayaniah. Dynamic look-ahead time in book-ahead reservation in QoS-enabled networks [C]//Proceedings of ICON 2004, [S.l.], IEEE,2004,2:566-571.
23. M. R. Meyer, D. Maddux, J.-P. Vasseur, et al. MPLS Traffic Engineering Soft Preemption [S], IETF Draft, October 2003.
24. C. H. Lau, B. H. Soong, S. K. Bose. Preemption with Rerouting to Minimize Service Disruption in Connection-Oriented Networks [J], IEEE transactions on systems man and cybernetics part A-system and humans, September 2008,38(5):1093-1104.
25. J. C. de Oliveira, C. Scoglio, I. F. Akyildiz, et al. New Preemption Policies for DiffServ-Aware Traffic Engineering to Minimize Rerouting in MPLS Networks [J], IEEE/ACM Transactions on Networking, August 2004,12(4):733-745.
26. J. C. de Oliveira, C. Scoglio, I. F. Akyildiz, et al. A New Preemption Policy for Diffserv-Aware Traffic Engineering to Minimize Rerouting [C]//Proceeding of IEEE INFOCOM 2002, [S.l.], IEEE,2002:695-704.
27. I. Ahman, J. Kamruzzaman, S. Aswathanarayaniah. An improved preemption policy for higher user satisfaction [C]//19th Informational Conference on Advanced Information Networking and Applications, Taipei:[s.n.],2005,1:749-754.
28. Mingying Zhu, Xiaoming He, Wu Ye. Minimizing Preemption Cost for DiffServ-Aware MPLS Traffic Engineering [J], Computer Communications, November 2006,29(18): 3825-3832.
29.李晓东.MPLS技术与实现[M],北京：电子工业出版社,2002,2-27.
30. Jim Guichand, Francois Le Faucheur, Jean-Philippe Vasseur. MPLS网络设计权威指南[M],北京：人民邮电出版社,2007,2-30.
31. Rita Puzmanova.路由与交换[M],北京：人民邮电出版社,2004,583-589.
32. L. Andersson, P. Doolan, N. Feldman, et al. LDP Specification [S], IETF RFC 3036, 2001.
33. E. Rosen, D. Tappan, G. Fedorkow, et al. MPLS Label Stack Encoding [S], IETF RFC 3032, January 2001
34. Luc De Ghein. MPLS技术构架[M],北京：人民邮电出版社,2008,2-19.
35. J. Moy. OSPF Version 2 [S], IETF RFC 2328, July 1997.
36. D. Oran. OSI IS-IS Intra-domain Routing Protocol [S], IETF RFC 1142, February 1990.
37. R. Braden, D. Clark, S. Shenker. Integrated Services in the Internet Architecture:an Overview [S], IETF RFC 1633, June 1994.
38. S. Blake, D. Black, M. Carlson, et al. An architecture for differentiated services [S], IETF RFC 2475, December 1998.
39. V. Jacobson, K. Nichols, K. Poduri. An expedited forwarding PHB [S], IETF RFC 2598, June 1999.
40. J. Heinanen, F. Baker, W. Weiss, et al. Assured forwarding PHB group [S], IETF RFC 2597, June 1999.
41. B. Jamoussi, L. Andersson, R. Callon, et al. Constraint-Based LSP Setup using LDP [S], IETF RFC 3212, January 2002.
42. D. Awduche, L. Berger, T. Li, et al. RSVP-TE:Extensions to RSVP for LSP Tunnels [S], IETF RFC3209, December 2001.
43. Adrian Farrel. Multiprotocol Label Switching Preemption [S], IETF Internet Draft,, April 2004.
44.徐雷鸣,庞博,赵耀.NS与网络模拟[M],北京：人民邮电出版社,2003,1-156.
45. J.-L. Le Roux, J.-P. Vasseur, J. Boyle. Requirements for Inter-Area MPLS Traffic Engineering [S], IETF RFC 4105, June 2005.
46. R. Zhang, J.-P. Vasseur. MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements [S], IETF RFC 4216, November 2005.
47. A.Farrel, J.-P. Vasseur. A Framework for Inter-Domain Multiprotocol Label Switching Traffic Engineering [S], IETF RFC 4726, November 2006.
2. D. Awduche, J.Malcolm, J. Agogbua, et al. Requirements for Traffic Engineering Over MPLS [S], IETF RFC 2702, September 1999.
3. F. Le Faucheur, L Wu, B. Davie, et al. Multi-protocol label switching (MPLS) support of differentiated services [S], IETF RFC 3270, May 2002.
4. F. Le Faucheur, W. Lai. Requirements for Support of Differentiated Services-aware MPLS Traffic Engineering [S], IETF RFC 3564, July 2003.
5. F. Le Faucheur. Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4127, June 2005.
6. F. Le Faucheur, W. Lai. Maximum Allocation Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4125, June 2005.
7. Jerry Ash, Max Alocation with Reservation Bandwidth Constraints Model for DiffServ-aware MPLS Trafic Engineering&Performance Comparisons [S], IETF Internet Draft, draft-ietf-tewg-diff-te-mar-06, December 2004
8. F. Le Faucheur Ed. Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering [S], IETF RFC 4124, June 2005.
9. J. de Oliveira, JP. Vasseur, L. Chen, et al. Label Switched Path (LSP) Preemption Policies for MPLS Traffic Engineering [S]. IETF RFC 4829, April 2007.
10. Apostolopoulos G, Kama S, Williams D, et al. QoS Routing Mechanisms and OSPF extensions [S], IETF RFC 2676, August 1999.
11. S.Kamei, T.Kimura, Evaluation of routing algorithms and network topologies for MPLS traffic engineering [C]//Proceeding of IEEE GLOBECOM 2001, San Antonio, IEEE, Nov.2001,1:25-29.
12. Suri S, Waldvogel M, Warkhede PR. Profile-Based Routing and traffic engineering [J], computer communications,2003,26(4):351-365.
13. P. Kumar, N. Khanakoti, S. Gopalan, et al. CoS Based LSP Selection in MPLS Network [J], HSNMC,2004,3079:314-323.
14. R. Rabbat, K. Laberteaux, N. Modi, et al. Traffic engineering algorithms using MPLS for service differentiation [C]//Proceedings of IEEE ICC 2000, [S.l.], IEEE, June 2000, 2:791-795.
15. M. Peyravian, A. D. Kshemkalyani. Decentralized network connection preemption algorithms [J], Computer network and ISDN systems, June 1998,30(11):1029-1043.
16. J.A.Garay, I.S.Gopal. Call Preemption in Communication Networks [C]//Proceedings of the IEEE INFOCOM'92, [S.l.], IEEE, May 1992,3:1043-1050.
17. M. Peyravian, A.D. Kshemkalyani. Connection Preemption:Issues, Algorithms, and a Simulation Study [C]//INFOCOM'97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Kobe:[s.n.],1997:143-151.
18. V. Stanisic, M. Devetsikiotis. A dynamic study of providing quality of service using preemption policies with random selection [C]//Proceedings of IEEE ICC 2003, [S.l.], IEEE, May 2003,3:1543-1546.
19. S. Jeon, R.T. Abler, A.E.Goulart. The optimal connection preemption algorithm in a multi-class network [C]//Proceedings of IEEE ICC 2002, NY, IEEE,2002,4:2294-2298.
20. C. H. Lau, B. H. Soong, S. K. Bose. SERA:Service ratio based preemption for minimizing throughput loss in network [C]//TENCON-IEEE Region 10 Conference Proceedings, Melbourne, Australia, IEEE,2006:1196-1201.
21. F. Blanchy, L. Melon, G. Leduc. Routing in a MPLS network featuring preemption mechanisms [C]//Proceedings of ICT 2003, [S.I.], IEEE,2003,1:253-260.
22. I. Ahman, J. Kamruzzaman, S. Aswathanarayaniah. Dynamic look-ahead time in book-ahead reservation in QoS-enabled networks [C]//Proceedings of ICON 2004, [S.l.], IEEE,2004,2:566-571.
23. M. R. Meyer, D. Maddux, J.-P. Vasseur, et al. MPLS Traffic Engineering Soft Preemption [S], IETF Draft, October 2003.
24. C. H. Lau, B. H. Soong, S. K. Bose. Preemption with Rerouting to Minimize Service Disruption in Connection-Oriented Networks [J], IEEE transactions on systems man and cybernetics part A-system and humans, September 2008,38(5):1093-1104.
25. J. C. de Oliveira, C. Scoglio, I. F. Akyildiz, et al. New Preemption Policies for DiffServ-Aware Traffic Engineering to Minimize Rerouting in MPLS Networks [J], IEEE/ACM Transactions on Networking, August 2004,12(4):733-745.
26. J. C. de Oliveira, C. Scoglio, I. F. Akyildiz, et al. A New Preemption Policy for Diffserv-Aware Traffic Engineering to Minimize Rerouting [C]//Proceeding of IEEE INFOCOM 2002, [S.l.], IEEE,2002:695-704.
27. I. Ahman, J. Kamruzzaman, S. Aswathanarayaniah. An improved preemption policy for higher user satisfaction [C]//19th Informational Conference on Advanced Information Networking and Applications, Taipei:[s.n.],2005,1:749-754.
28. Mingying Zhu, Xiaoming He, Wu Ye. Minimizing Preemption Cost for DiffServ-Aware MPLS Traffic Engineering [J], Computer Communications, November 2006,29(18): 3825-3832.
29.李晓东.MPLS技术与实现[M],北京：电子工业出版社,2002,2-27.
30. Jim Guichand, Francois Le Faucheur, Jean-Philippe Vasseur. MPLS网络设计权威指南[M],北京：人民邮电出版社,2007,2-30.
31. Rita Puzmanova.路由与交换[M],北京：人民邮电出版社,2004,583-589.
32. L. Andersson, P. Doolan, N. Feldman, et al. LDP Specification [S], IETF RFC 3036, 2001.
33. E. Rosen, D. Tappan, G. Fedorkow, et al. MPLS Label Stack Encoding [S], IETF RFC 3032, January 2001
34. Luc De Ghein. MPLS技术构架[M],北京：人民邮电出版社,2008,2-19.
35. J. Moy. OSPF Version 2 [S], IETF RFC 2328, July 1997.
36. D. Oran. OSI IS-IS Intra-domain Routing Protocol [S], IETF RFC 1142, February 1990.
37. R. Braden, D. Clark, S. Shenker. Integrated Services in the Internet Architecture:an Overview [S], IETF RFC 1633, June 1994.
38. S. Blake, D. Black, M. Carlson, et al. An architecture for differentiated services [S], IETF RFC 2475, December 1998.
39. V. Jacobson, K. Nichols, K. Poduri. An expedited forwarding PHB [S], IETF RFC 2598, June 1999.
40. J. Heinanen, F. Baker, W. Weiss, et al. Assured forwarding PHB group [S], IETF RFC 2597, June 1999.
41. B. Jamoussi, L. Andersson, R. Callon, et al. Constraint-Based LSP Setup using LDP [S], IETF RFC 3212, January 2002.
42. D. Awduche, L. Berger, T. Li, et al. RSVP-TE:Extensions to RSVP for LSP Tunnels [S], IETF RFC3209, December 2001.
43. Adrian Farrel. Multiprotocol Label Switching Preemption [S], IETF Internet Draft,
44.徐雷鸣,庞博,赵耀.NS与网络模拟[M],北京：人民邮电出版社,2003,1-156.
45. J.-L. Le Roux, J.-P. Vasseur, J. Boyle. Requirements for Inter-Area MPLS Traffic Engineering [S], IETF RFC 4105, June 2005.
46. R. Zhang, J.-P. Vasseur. MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements [S], IETF RFC 4216, November 2005.
47. A.Farrel, J.-P. Vasseur. A Framework for Inter-Domain Multiprotocol Label Switching Traffic Engineering [S], IETF RFC 4726, November 2006.