Networking Group S. Yin Internet Draft Sh.G. Huang Intended status: Informational BUPT Expires: March 2016 D.J. Wang ZTE Corporation X. Wang Y. Zhang BUPT January 6, 2016 A MILP Model to Solve the Problem of Loading Balance of Routing and Wavelength Assignment for Optical Transport Networks draft-yin-milp-rwa-otn-01 Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on March 10,2016. Copyright Notice Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this Huang, et al. Expires July 7, 2016 [Page 1] Internet-Draft A MILP Model for LB OF OTN January 2016 document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Abstract The RWA problem can be formulated as a Mixed-Integer linear program. Load balancing is a key factor for the optical transport networks. However, the existed approaches using mixed-Integer linear program to solve the RWA problem are not perfect enough without considering the load balancing of the networks. This documentary provides a model of Mixed-Integer Linear Programming to solve the problem of load balancing needed by routing and wavelength assignment (RWA) process in optical transport networks. Abstract The RWA problem can be formulated as a Mixed-Integer linear program. Load balancing is a key factor for the optical transport networks. However, the existed approaches using mixed-Integer linear program to solve the RWA problem are not perfect enough without considering the load balancing of the networks. This documentary provides a model of Mixed-Integer Linear Programming to solve the problem of load balancing needed by routing and wavelength assignment (RWA) process in optical transport networks. Table of Contents 1. Introduction ................................................ 3 1.1. Terminology ............................................ 3 2. Conventions used in this document............................ 4 3. Overview .................................................... 4 3.1. RWA Problem ............................................ 4 3.2. Optimization of Network Resources .......................5 4. Previous Work ............................................... 5 4.1. Definition ............................................. 5 4.2. Definition ............................................. 5 5. A MILP Model to Solve the Problem of Loading Balance of RWA for OT ............................................................ 6 5.1. Parameters ............................................. 6 5.2. Variables .............................................. 7 5.3. Objective Function...................................... 8 5.4. Constraints ............................................ 8 Huang, et al. Expires July 7, 2016 [Page 2] Internet-Draft A MILP Model for LB OF OTN January 2016 6. Beneficial effects ......................................... 10 7. Security Considerations..................................... 10 8. IANA Considerations ........................................ 10 9. Conclusions ................................................ 11 10. References ................................................ 11 10.1. Normative References.................................. 11 10.2. Informative References................................ 12 11. Acknowledgments ........................................... 12 1. Introduction With the development of communication technology, business demand for network bandwidth is also increasing. The routing algorithm is usually based on the shortest path algorithm (Dijkstra), and it will make the most of the businesses concentrate in a small number of links, drain seriously on the resources link, creating an unbalanced load on the network. Network load imbalances in turn affect the subsequent establishment of the business route, leading to higher rates of occlusion and reducing network performance. In order to achieve network load balancing, we propose an MILP model. In this paper, we consider the load balancing of the OTN and use the mixed-integer linear program (MILP) to solve the RWA problem. We find the existed MILP models can't have a perfect solution without considering load balancing. This model is applicable in the optical transport networks. The OTN networks have a lot of advantages over the WDM networks. It can transport a variety of client signals transparently, like 10GE/40GE/100GE etc. Flexible & efficient grooming of any rate services can be achieved with OTN switcher. Also service adjustments can be completed remotely by NMS. In this Model the network node has no wavelength conversion capability for static RWA problem. Our objective is to achieve load balancing of the optical transport networks, and improve network throughput. 1.1. Terminology RWA: Routing and Wavelength Assignment. Wavelength Conversion: The process of converting an information bearing optical signal centered at a given wavelength to one with "equivalent" content centered at a different wavelength. Wavelength conversion can be implemented via an optical-electronic-optical (OEO) process or via a strictly optical process. Huang, et al. Expires July 7, 2016 [Page 3] Internet-Draft A MILP Model for LB OF OTN January 2016 OTN: Optical Transport Networks. 2. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [RFC2119]. 3. Overview In dynamic optical transport network, research on the resource optimization and constraint-based routing problem mainly includes the following aspects: (1)path selection and wavelength assignment problem in optical layer. (2)Constraint-based routing problem under dynamic business in Multi- layer network. (3)resource optimization problem under dynamic business in the multi- layer network. 3.1. RWA Problem Optical layer path selection and wavelength assignment problem, which is called RWA (Routing and Wavelength Assignment, routing and wavelength assignment) problem, is mainly caused by the require of consistency and constraints of wavelength in the optical fiber link. Optical layer routing based on Dijkstra algorithm is usually started by the different parameters chosen as consideration to select the least costly path, common optical path selection algorithms are mainly fixed routing algorithm, fixed alternate routing algorithm, adaptive routing algorithm and adaptive shortest alternate routing algorithm. Wavelength assignment algorithm is usually based on heuristic algorithms, aiming to obtain the minimum blocking rate under a certain number of wavelengths. There are several common wavelength assignment algorithms such as randomly assigned wavelength method, first-fit, the minimum application method, the most widely used method and the lightest load method. The core problem of dynamic business constraints routing issue is the method for electrical and optical layers combined to find proper routes. Huang, et al. Expires July 7, 2016 [Page 4] Internet-Draft A MILP Model for LB OF OTN January 2016 3.2. Optimization of Network Resources We need to choose from all of the implementation designs for logical topology of the network to make the best performance of packet service delivery program. For small-scale networks we can use mixed integer linear programming (Mixed Integer Linear Programming, MILP); to optimize the design of large-scale networks, we often use heuristic algorithm. In this paper we focus on the MILP method to solve the RWA problem in optical transport networks considering the load balancing of the network. 4. Previous Work The existing MILP model to solve RWA problem is relatively simple, which cannot be a good solution without considering load balancing in optical transport network, so we improve the existing MILP-based mathematical model, and propose an improved MILP model which can be used under the condition of certain blocking rate with considering load balancing in the optical transport network. 4.1. Definition MILP: Mixed integer linear programming (Mixed-Integer Linear Programming, MILP) is a class of special mathematical program in which all or part of the variables are restricted to be integer values and the constraints are linear. It brings in the mixed integer based on the ILP. ILP: An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. The Static RWA problem can be attributed to a class of programming problems, of which the mathematical description of the problem has been fully discussed for. The basic idea of the algorithm is: write a column of equations for the objective to be optimized write a column of constraint equations solve the linear program. 4.2. Definition In the absence of wavelength convertors, an optical path would occupy the same wavelength on all fiber links through which it passes. This is called the wavelength-continuity constraint in wavelength-routed networks. Given a set of optical paths, we need to route and assign a wavelength to each of them; this is called the routing and wavelength Huang, et al. Expires July 7, 2016 [Page 5] Internet-Draft A MILP Model for LB OF OTN January 2016 assignment (RWA) problem. The RWA problem can be formulated as a mixed-integer linear program. The RWA problem, without the wavelength continuity constraint, can be formulated as a multi-commodity flow problem with integer link flows. This corresponds to an integer linear program (ILP) with the objective function being to minimize the flow in each link. Let t_sd denote the traffic (in terms of an optical path) from source s to destination d. We consider at most one optical path from a source to a destination, hence t_sd = 1 if there is an optical path from s to d, otherwise t_sd = 0. We do not consider bidirectional optical paths, i.e. t_sd = 1 does not necessarily imply t_sd = 1. Let F_sdij denote the traffic (in terms of number of optical paths) flowing from Source s to destination d on link ij. The linear Programming formulation is o Minimize: Such that F_max >= SUM_s,d [F_sdij],for any i and j. o -t_sd, s=j SUM_s,d [F_sdij] - SUM_s,d [F_sdjk] = { t_sd, d=j} 0,otherwise Since this model only solves the problem of RWA for the network, the constraint equation column does not include the wavelength continuity constraint equation. If we need to solve the routing problem and wavelength problem at the same time, we need to add an equation, which lead to the complexity increasing greatly for the question. 5. A MILP Model to Solve the Problem of Loading Balance of RWA for OTN With the development of communication technology, business demand for network bandwidth is also increasing. And because the routing algorithms are usually based on the shortest path algorithm, thus making the most of the businesses concentrate in a small number of links. Such lead to a serious drain on the resources for these links, creating an unbalanced network load. Network load imbalances in turn affect the subsequent establishment of the traffic route, resulting in the increase of blocking rate and reduce of network performance. In order to achieve network loading balance, we propose this MILP model. Nodes used in the model for the OTN network have no wavelength conversion capability for static RWA problem. Our aim is to achieve loading balance of the network and improve network throughput. 5.1. Parameters o G=(V,E) Undirected graph topology for physical network Huang, et al. Expires July 7, 2016 [Page 6] Internet-Draft A MILP Model for LB OF OTN January 2016 o SUM_s,d [F_sd] The sum of F_sd for all valid s and d o AEB A belongs to B o V Collection of nodes in the network, V={v1,v2,...,vn} o E Collection of the fiber links in the network, E {e1,e2,...,em} o T Collection of the traffics, T={t1,t2,...,ti}; each traffic t corresponds to a set of parameters (S_t,D_t,B_t) o S_t The source node of the traffic, tET o D_t The destination node of the traffic, tET o B_t The bandwidth occupied by the traffic, tET o L Collection of available wavelengths, L={l1,l2,...,lw} o W The maximum number of available wavelengths, W=|L| o B The maximum bandwidth of the available wavelength L o w(i) Collection of the adjacent edges of the node vi, viEV o K The order of the ODU, K={1,2,3,4} 5.2. Variables (1)The rate of the ODU_k is shown as follows: 2.5; k=1 ODU_k = { 10; k=2 ; (Gbps) 40; k=3 100; k=4 (2)The order of the ODU is determined by the following formula: 1; 0 < B_t <= 2.5 k = { 2; 2.5 <= B_t <= 10 ; tET 3; 10 < B_t <= 2.5 4; 40 < B_t <= 100 (3)The parameter X_t represents the status of the connection establishing: Huang, et al. Expires July 7, 2016 [Page 7] Internet-Draft A MILP Model for LB OF OTN January 2016 1, If the traffic t is established successfully X_t={0, Otherwise ; tET (4)The parameter X_t(e) represents whether the traffic t passes link e: 1, If the traffic t passes link e X_t(e)={0, Otherwise ; tET (5) The parameter X_t(e,l) represents whether the traffic t occupies the wavelength l on link e: 1,If the traffic t occupies the wavelength X_t(e,l)={ l on link e ; tET,lEL 0, Otherwise (6) The parameter X_t(e,l,k) represents whether the traffic t occupies ODU_k on wavelength l of link e: 1, If the traffic t occupies ODU_k X_t(e,l,k)={ on wavelength l of link e ; tET,lEL,kEK, 0, Otherwise 5.3. Objective Function o Objective Function: minR=S o S: The maximum utilization of links in the network. o Make the R to its minimum, to achieve the loading balance for the network 5.4. Constraints (1)The total bandwidth occupied by all traffics on each available wavelength of any link must be smaller than the maximum bandwidth of the wavelength SUM_t SUM_k [X_t(e,l,k)ODU_k] <= B; tET,eEE,lEL (2)To prevent self-loop: for the source node or the destination node, there should be only one adjacent link to transmit traffic; SUM_eEw(vi) [X_t(e)] = 1; tET,viE{s_t,d_t} Huang, et al. Expires July 7, 2016 [Page 8] Internet-Draft A MILP Model for LB OF OTN January 2016 for the node else, the adjacent links should be no more than 2, and once the node receives a traffic from one link, there should be another link to send the traffic again: SUM_eEw(vi) [X_t(e)] <= 2; tET,viEV\{s_t,d_t} SUM_e'Ew(vi),e' e) [X_t(e')] >= X_t(e); tET,eEw(vi), vi EV\{s_t,d_t } (3)Traffic in the network can only occupies one wavelength and one ODU_k: SUM_l [X_t(e,l)] <= X_t(e); eEE,lEL SUM_l SUM_k [X_t(e,l,k)] <= X_t(e); eEE,lEL All of the links transmitting the traffic should provide the same wavelength and ODU_k: SUM_eEw(vi) SUM_l [X_t(e,l)] = 1; tET,lEL,v_iE{s_t,d_t} SUM_eEw(vi) [X_t(e,l)] <= 2; tET,lEL,viEV\{s_t,d_t} SUM_e'Ew(vi),e' e [X_t(e',l)] >= X_t(e,l); tET,lEL,viEV\{s_t,d_t} (4)The source node and the destination node of the same traffic should use the same wavelength: SUM_eEw(s_t) [X_t(e,l)] = SUM_e'Ew(d_t) [X_t(e',l)]; tET,lEL The source node and the intermediate node should use the same wavelength: SUM_eEw(s_t) [X_t(e,l)] + SUM_eEw(d_t) [X_t(e,l)] >= SUM_eEw(vi) [X_t(e,l)]; tET,eEE,lEL,viEV\{s_t,d_t} SUM_eEw(vi) [X_t(e,l)] <= 2; tET,eEE,lEL,viEV\{s_t,d_t} To measure the average degree between resource utilizations of all links, we need two integer variables: o R_e represents the total bandwidth occupied by all traffics on link e: R_e= SUM_t SUM_l SUM_k [X_t(e,l,k)ODU_k]; eEE Huang, et al. Expires July 7, 2016 [Page 9] Internet-Draft A MILP Model for LB OF OTN January 2016 o S represents the maximum of the resource utilizations of all links: S >= R_e/(WB); eEE 6. Beneficial effects The MILP model we proposed can solve the loading balance of the RWA problem for the OTN network, and can be a good method to select route and wavelength. For example, there are two paths from the source node to the destination node. The upper path has two hops, the lower path has three hops. However, according to the allocation of resources, the lower path is better than the first path. According to the link resource consumption: the upper path does not guarantee the continuity and consistency of wavelength and the utilization of wavelength is relatively low, although it has small number of hops. While the lower path has more hops than the upper path, the idle slots of wavelength are continuous and it can ensure the continuity and consistency of the wavelength, and the wavelength utilization is higher than the upper path. When the upper path has a high loading balance, the two paths cannot balance the load, and the lower path utilization is relatively low. If we use MILP algorithm we proposed, we can get the most reasonable route, and the remaining business will choose the path which has a lower path utilization than the other, and thus achieve loading balance on the network. 7. Security Considerations This document discussed an information model for RWA computation in OTN. Such a model is very similar from a security standpoint of the information that can be currently conveyed via GMPLS routing protocols. Such information includes network topology, link state and current utilization, and well as the capabilities of switches and routers within the network. As such this information should be protected from disclosure to unintended recipients. In addition, the intentional modification of this information can significantly affect network operations, particularly due to the large capacity of the optical infrastructure to be controlled. 8. IANA Considerations This informational document does not make any requests for IANA action. Huang, et al. Expires July 7, 2016 [Page 10] Internet-Draft A MILP Model for LB OF OTN January 2016 9. Conclusions 10. References 10.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997. [3] Banerjee, D.; Mukherjee, B., "A practical approach for routing and wavelength assignment in large wavelength-routed optical networks," Selected Areas in Communications, IEEE Journal on , vol.14, no.5, pp.903,908, Jun 1996. [4] Jaumard, B.; Meyer, C.; Thiongane, B.; Yu, Xiao, "ILP formulations and optimal solutions for the RWA problem," Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE , vol.3, no., pp.1918,1924 Vol.3, 29 Nov.-3 Dec. 2004 [5] Barpanda, R.S.; Sahoo, B.; Turuk, A.K.; Majhi, B., "Solving large problem instances of the RWA problem using Genetic Algorithms," Industrial and Information Systems (ICIIS), 2010 International Conference on , vol., no., pp.41,46, July 29 2010-Aug. 1 2010. [6] Krishnaswamy, R.M.; Sivarajan, K.N., "Algorithms for routing and wavelength assignment based on solutions of LP- relaxations," Communications Letters, IEEE , vol.5, no.10, pp.435,437, Oct. 2001. [7] Wang, X.; Brandt-Pearce, M.; Subramaniam, S., "Dynamic grooming and RWA in translucent optical networks using a time-slotted ILP," Global Communications Conference (GLOBECOM), 2012 IEEE , vol., no., pp.2996,3001, 3-7 Dec. 2012. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997. Huang, et al. Expires July 7, 2016 [Page 11] Internet-Draft A MILP Model for LB OF OTN January 2016 10.2. Informative References [8] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in TCP and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 1573- 1583. [Fab1999] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in TCP and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 1573-1583. 11. Acknowledgments This document was prepared using 2-Word-v2.0.template.dot. Huang, et al. Expires July 7, 2016 [Page 12] Internet-Draft A MILP Model for LB OF OTN January 2016 Authors' Addresses Shan Yin BUPT No.10, Xitucheng Road,Haidian District Beijing 100876 P.R.China Phone: +8613488795778 Email: buptyinshan@126.com Shanguo Huang BUPT No.10, Xitucheng Road,Haidian District Beijing 100876 P.R.China Phone: +8613693578265 Email: shghuang@bupt.edu.cn Dajiang Wang ZTE Corporation No.55, Technology South Road,Nanshan District Shenzhen 518057 P.R.China Phone: +8613811795408 Email: wang.dajiang@zte.com.cn Xuan Wang BUPT No.10, Xitucheng Road,Haidian District Beijing 100876 P.R.China Phone: +8613581576907 Email: buptwangxuan@163.com Yu Zhang BUPT No.10, Xitucheng Road,Haidian District Beijing 100876 P.R.China Phone: +8618627519028 Email: yx8203731@126.com Huang, et al. Expires July 7, 2016 [Page 13]