idnits 2.17.1 draft-yin-milp-rwa-otn-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. (A line matching the expected section header was found, but with an unexpected indentation: ' 2. Introduction' ) ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 8. Security Considerations' ) ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) (A line matching the expected section header was found, but with an unexpected indentation: ' 9. IANA Considerations' ) ** There are 7 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (October 19, 2016) is 2745 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Missing reference section? 'RFC2119' on line 511 looks like a reference -- Missing reference section? '1' on line 478 looks like a reference -- Missing reference section? '2' on line 481 looks like a reference -- Missing reference section? '3' on line 485 looks like a reference -- Missing reference section? '4' on line 490 looks like a reference -- Missing reference section? '5' on line 495 looks like a reference -- Missing reference section? '6' on line 501 looks like a reference -- Missing reference section? '7' on line 506 looks like a reference -- Missing reference section? 'RFC2234' on line 514 looks like a reference -- Missing reference section? '8' on line 520 looks like a reference -- Missing reference section? 'Fab1999' on line 524 looks like a reference Summary: 4 errors (**), 0 flaws (~~), 2 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Networking Group S. Yin 2 Internet Draft Sh.G. Huang 3 Intended status: Informational BUPT 4 Expires: April 2017 D.J. Wang 5 ZTE Corporation 6 X. Wang 7 Y. Zhang 8 BUPT 9 October 19, 2016 11 A MILP Model to Solve the Problem of Loading Balance of Routing and 12 Wavelength Assignment for Optical Transport Networks 13 draft-yin-milp-rwa-otn-03 15 Status of this Memo 17 This Internet-Draft is submitted in full conformance with the 18 provisions of BCP 78 and BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html 35 This Internet-Draft will expire on March 10,2016. 37 Copyright Notice 39 Copyright (c) 2015 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 1.1.1.1.1.1.1. This document is subject to BCP 78 and the IETF Trust's 43 Legal Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents carefully, 46 as they describe your rights and restrictions with respect to this 47 document. Code Components extracted from this document must include 48 Simplified BSD License text as described in Section 4.e of the Trust 49 Legal Provisions and are provided without warranty as described in 50 the Simplified BSD License. 52 Abstract 54 The RWA problem can be formulated as a Mixed-Integer linear program. 55 Load balancing is a key factor for the optical transport networks. 56 However, the existed approaches using mixed-Integer linear program to 57 solve the RWA problem are not perfect enough without considering the 58 load balancing of the networks. 60 This documentary provides a model of Mixed-Integer Linear Programming 61 to solve the problem of load balancing needed by routing and 62 wavelength assignment (RWA) process in optical transport networks. 64 Abstract 66 The RWA problem can be formulated as a Mixed-Integer linear program. 67 Load balancing is a key factor for the optical transport networks. 68 However, the existed approaches using mixed-Integer linear program to 69 solve the RWA problem are not perfect enough without considering the 70 load balancing of the networks. 72 This documentary provides a model of Mixed-Integer Linear Programming 73 to solve the problem of load balancing needed by routing and 74 wavelength assignment (RWA) process in optical transport networks. 76 Table of Contents 78 1. Introduction ................................................ 3 79 1.1. Terminology ............................................ 3 80 2. Conventions used in this document............................ 4 81 3. Overview .................................................... 4 82 3.1. RWA Problem ............................................ 4 83 3.2. Optimization of Network Resources .......................5 84 4. Previous Work ............................................... 5 85 4.1. Definition ............................................. 5 86 4.2. Definition ............................................. 5 87 5. A MILP Model to Solve the Problem of Loading Balance of RWA for 88 OTN ............................................................ 6 89 5.1. Parameters ............................................. 6 90 5.2. Variables .............................................. 7 91 5.3. Objective Function...................................... 8 92 5.4. Constraints ............................................ 8 94 6. Beneficial effects ......................................... 10 95 7. Security Considerations..................................... 10 96 8. IANA Considerations ........................................ 11 97 9. Conclusions ................................................ 11 98 10. References ................................................ 11 99 10.1. Normative References.................................. 11 100 10.2. Informative References................................ 12 101 11. Acknowledgments ........................................... 12 103 2. Introduction 105 With the development of communication technology, business demand for 106 network bandwidth is also increasing. 108 The routing algorithm is usually based on the shortest path algorithm 109 (Dijkstra), and it will make the most of the businesses concentrate 110 in a small number of links, drain seriously on the resources link, 111 creating an unbalanced load on the network. Network load imbalances 112 in turn affect the subsequent establishment of the business route, 113 leading to higher rates of occlusion and reducing network performance. 115 In order to achieve network load balancing, we propose an MILP model. 116 In this paper, we consider the load balancing of the OTN and use the 117 mixed-integer linear program (MILP) to solve the RWA problem. We find 118 the existed MILP models can't have a perfect solution without 119 considering load balancing. This model is applicable in the optical 120 transport networks. The OTN networks have a lot of advantages over 121 the WDM networks. It can transport a variety of client signals 122 transparently, like 10GE/40GE/100GE etc. Flexible & efficient 123 grooming of any rate services can be achieved with OTN switcher. Also 124 service adjustments can be completed remotely by NMS. 126 In this Model the network node has no wavelength conversion 127 capability for static RWA problem. Our objective is to achieve load 128 balancing of the optical transport networks, and improve network 129 throughput. 131 2.1. Terminology 133 RWA: Routing and Wavelength Assignment. 135 Wavelength Conversion: The process of converting an information 136 bearing optical signal centered at a given wavelength to one with 137 "equivalent" content centered at a different wavelength. Wavelength 138 conversion can be implemented via an optical-electronic-optical (OEO) 139 process or via a strictly optical process. 141 OTN: Optical Transport Networks. 143 3. Conventions used in this document 145 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 146 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 147 document are to be interpreted as described in RFC-2119 [RFC2119]. 149 4. Overview 151 In dynamic optical transport network, research on the resource 152 optimization and constraint-based routing problem mainly includes the 153 following aspects: 155 (1)path selection and wavelength assignment problem in optical layer. 157 (2)Constraint-based routing problem under dynamic business in Multi- 158 layer network. 160 (3)resource optimization problem under dynamic business in the multi- 161 layer network. 163 4.1. RWA Problem 165 Optical layer path selection and wavelength assignment problem, which 166 is called RWA (Routing and Wavelength Assignment, routing and 167 wavelength assignment) problem, is mainly caused by the require of 168 consistency and constraints of wavelength in the optical fiber link. 170 Optical layer routing based on Dijkstra algorithm is usually started 171 by the different parameters chosen as consideration to select the 172 least costly path, common optical path selection algorithms are 173 mainly fixed routing algorithm, fixed alternate routing algorithm, 174 adaptive routing algorithm and adaptive shortest alternate routing 175 algorithm. 177 Wavelength assignment algorithm is usually based on heuristic 178 algorithms, aiming to obtain the minimum blocking rate under a 179 certain number of wavelengths. There are several common wavelength 180 assignment algorithms such as randomly assigned wavelength method, 181 first-fit, the minimum application method, the most widely used 182 method and the lightest load method. The core problem of dynamic 183 business constraints routing issue is the method for electrical and 184 optical layers combined to find proper routes. 186 4.2. Optimization of Network Resources 188 We need to choose from all of the implementation designs for logical 189 topology of the network to make the best performance of packet 190 service delivery program. For small-scale networks we can use mixed 191 integer linear programming (Mixed Integer Linear Programming, MILP); 192 to optimize the design of large-scale networks, we often use 193 heuristic algorithm. In this paper we focus on the MILP method to 194 solve the RWA problem in optical transport networks considering the 195 load balancing of the network. 197 5. Previous Work 199 The existing MILP model to solve RWA problem is relatively simple, 200 which cannot be a good solution without considering load balancing in 201 optical transport network, so we improve the existing MILP-based 202 mathematical model, and propose an improved MILP model which can be 203 used under the condition of certain blocking rate with considering 204 load balancing in the optical transport network. 206 5.1. Definition 208 MILP: Mixed integer linear programming (Mixed-Integer Linear 209 Programming, MILP) is a class of special mathematical program in 210 which all or part of the variables are restricted to be integer 211 values and the constraints are linear. It brings in the mixed integer 212 based on the ILP. 214 ILP: An integer programming problem is a mathematical optimization or 215 feasibility program in which some or all of the variables are 216 restricted to be integers. In many settings the term refers to 217 integer linear programming (ILP), in which the objective function and 218 the constraints (other than the integer constraints) are linear. 220 The Static RWA problem can be attributed to a class of programming 221 problems, of which the mathematical description of the problem has 222 been fully discussed for. The basic idea of the algorithm is: write a 223 column of equations for the objective to be optimized write a column 224 of constraint equations solve the linear program. 226 5.2. Definition 228 In the absence of wavelength convertors, an optical path would occupy 229 the same wavelength on all fiber links through which it passes. This 230 is called the wavelength-continuity constraint in wavelength-routed 231 networks. Given a set of optical paths, we need to route and assign a 232 wavelength to each of them; this is called the routing and wavelength 233 assignment (RWA) problem. The RWA problem can be formulated as a 234 mixed-integer linear program. 236 The RWA problem, without the wavelength continuity constraint, can be 237 formulated as a multi-commodity flow problem with integer link flows. 238 This corresponds to an integer linear program (ILP) with the 239 objective function being to minimize the flow in each link. Let t_sd 240 denote the traffic (in terms of an optical path) from source s to 241 destination d. We consider at most one optical path from a source to 242 a destination, hence t_sd = 1 if there is an optical path from s to d, 243 otherwise t_sd = 0. We do not consider bidirectional optical paths, 244 i.e. t_sd = 1 does not necessarily imply t_sd = 1. Let F_sdij denote 245 the traffic (in terms of number of optical paths) flowing from Source 246 s to destination d on link ij. The linear Programming formulation is 248 o Minimize: Such that F_max >= SUM_s,d [F_sdij],for any i and j. 250 o -t_sd, s=j 251 SUM_s,d [F_sdij] - SUM_s,d [F_sdjk] = { t_sd, d=j} 252 0,otherwise 254 Since this model only solves the problem of RWA for the network, the 255 constraint equation column does not include the wavelength continuity 256 constraint equation. If we need to solve the routing problem and 257 wavelength problem at the same time, we need to add an equation, 258 which lead to the complexity increasing greatly for the question. 260 6. A MILP Model to Solve the Problem of Loading Balance of RWA for 261 OTN 263 With the development of communication technology, business demand for 264 network bandwidth is also increasing. And because the routing 265 algorithms are usually based on the shortest path algorithm, thus 266 making the most of the businesses concentrate in a small number of 267 links. Such lead to a serious drain on the resources for these links, 268 creating an unbalanced network load. Network load imbalances in turn 269 affect the subsequent establishment of the traffic route, resulting 270 in the increase of blocking rate and reduce of network performance. 271 In order to achieve network loading balance, we propose this MILP 272 model. Nodes used in the model for the OTN network have no wavelength 273 conversion capability for static RWA problem. Our aim is to achieve 274 loading balance of the network and improve network throughput. 276 6.1. Parameters 278 o G=(V,E) Undirected graph topology for physical network 279 o SUM_s,d [F_sd] The sum of F_sd for all valid s and d 281 o [A c B] A belongs to B 283 o A /= B A is not equal to B 285 o V Collection of nodes in the network, V={v1,v2,...,vn} 287 o E Collection of the fiber links in the network, E {e1,e2,...,em} 289 o T Collection of the traffics, T={t1,t2,...,ti}; 290 each traffic t corresponds to a set of parameters 291 (S_t,D_t,B_t) 293 o S_t The source node of the traffic, [t c T] 295 o D_t The destination node of the traffic, [t c T] 297 o B_t The bandwidth occupied by the traffic, [t c T] 299 o L Collection of available wavelengths, L={l1,l2,...,lw} 301 o W The maximum number of available wavelengths, W=|L| 303 o B The maximum bandwidth of the available wavelength L 305 o w(i) Collection of the adjacent edges of the node vi, [vi c V] 307 o K The order of the ODU, K={1,2,3,4} 309 6.2. Variables 311 (1)The rate of the ODU_k is shown as follows: 313 2.5; k=1 314 ODU_k = { 10; k=2 ; (Gbps) 315 40; k=3 316 100; k=4 318 (2)The order of the ODU is determined by the following formula: 320 1; 0 < B_t <= 2.5 321 k = { 2; 2.5 <= B_t <= 10 ; [t c T] 322 3; 10 < B_t <= 2.5 323 4; 40 < B_t <= 100 325 (3)The parameter X_t represents the status of the connection 326 establishing: 328 1, If the traffic t is established successfully 329 X_t={0, Otherwise ; [t c T] 331 (4)The parameter X_t(e) represents whether the traffic t passes link 332 e: 334 1, If the traffic t passes link e 335 X_t(e)={0, Otherwise ;[t c T] 337 (5) The parameter X_t(e,l) represents whether the traffic t occupies 338 the wavelength l on link e: 340 1,If the traffic t occupies the wavelength 341 X_t(e,l)={ l on link e ;[t c T],[l c L] 342 0, Otherwise 344 (6) The parameter X_t(e,l,k) represents whether the traffic t 345 occupies ODU_k on wavelength l of link e: 347 1, If the traffic t occupies ODU_k 348 X_t(e,l,k)={ on wavelength l of link e ;[t c T],[l c L],[k c K] 349 0, Otherwise 351 6.3. Objective Function 353 o Objective Function: min R=S 355 o S: The maximum utilization of links in the network. 357 o Make the R to its minimum, to achieve the loading balance for the 358 network 360 6.4. Constraints 362 (1)The total bandwidth occupied by all traffics on each available 363 wavelength of any link must be smaller than the maximum bandwidth 364 of the wavelength 366 SUM_t SUM_k [X_t(e,l,k)ODU_k] <= B;[t c T], [t c T], [l c L] 368 (2)To prevent self-loop: for the source node or the destination node, 369 there should be only one adjacent link to transmit traffic; 371 SUM_[e c w(vi)] [X_t(e)] = 1; [t c T],[vi c {s_t,d_t}] 372 for the node else, the adjacent links should be no more than 2, 373 and once the node receives a traffic from one link, there should 374 be another link to send the traffic again: 376 SUM_[e c w(vi)] [X_t(e)] <= 2; [t c T],[vi c V\{s_t,d_t}] 378 SUM_([e' c w(vi)],e'/=e) [X_t(e')] >= X_t(e);[t c T],[e c w(vi)], 379 [vi c V\{s_t,d_t }] 381 (3)Traffic in the network can only occupies one wavelength and one 382 ODU_k: 384 SUM_l [X_t(e,l)] <= X_t(e); [e c E],[l c L] 386 SUM_l SUM_k [X_t(e,l,k)] <= X_t(e); [e c E],[l c L] 388 All of the links transmitting the traffic should provide the same 389 wavelength and ODU_k: 391 SUM_[e c w(vi)] SUM_l [X_t(e,l)] = 1; [t c T],[l c L], 392 [v_i c {s_t,d_t}] 394 SUM_[e c w(vi)] [X_t(e,l)] <= 2; [t c T],[l c L], 395 [vi c V\{s_t,d_t}] 397 SUM_([e' c w(vi)],e'/=e [X_t(e',l)]) >= X_t(e,l); [t c T],[l c L], 398 [vi c V\{s_t,d_t}] 400 (4)The source node and the destination node of the same traffic 401 should use the same wavelength: 403 SUM_[e c w(s_t)] [X_t(e,l)] = SUM_[e' c w(d_t)] [X_t(e',l)]; 404 [t c T],[l c L] 406 The source node and the intermediate node should use the same 407 wavelength: 409 SUM_[e c w(s_t)] [X_t(e,l)] + SUM_eEw(d_t) [X_t(e,l)] >= 410 SUM_[e c w(vi)][X_t(e,l)]; [t c T],[e c E],[l c L], 411 [vi c V\{s_t,d_t}] 413 SUM_[e c w(vi)] [X_t(e,l)] <= 2; [t c T],[e c E],[l c L], 414 [vi c V\{s_t,d_t}] 416 To measure the average degree between resource utilizations of 417 all links, we need two integer variables: 419 o R_e represents the total bandwidth occupied by all traffics on 420 link e: 422 R_e= SUM_t SUM_l SUM_k [X_t(e,l,k)ODU_k]; [e c E] 424 o S represents the maximum of the resource utilizations of all 425 links: 427 S >= R_e/(WB); [e c E] 429 7. Beneficial effects 431 The MILP model we proposed can solve the loading balance of the RWA 432 problem for the OTN network, and can be a good method to select route 433 and wavelength. For example, there are two paths from the source node 434 to the destination node. The upper path has two hops, the lower path 435 has three hops. However, according to the allocation of resources, 436 the lower path is better than the first path. According to the link 437 resource consumption: the upper path does not guarantee the 438 continuity and consistency of wavelength and the utilization of 439 wavelength is relatively low, although it has small number of hops. 440 While the lower path has more hops than the upper path, the idle 441 slots of wavelength are continuous and it can ensure the continuity 442 and consistency of the wavelength, and the wavelength utilization is 443 higher than the upper path. 445 When the upper path has a high loading balance, the two paths cannot 446 balance the load, and the lower path utilization is relatively low. 447 If we use MILP algorithm we proposed, we can get the most reasonable 448 route, and the remaining business will choose the path which has a 449 lower path utilization than the other, and thus achieve loading 450 balance on the network. 452 8. Security Considerations 454 This document discussed an information model for RWA computation in 455 OTN. Such a model is very similar from a security standpoint of the 456 information that can be currently conveyed via GMPLS routing 457 protocols. Such information includes network topology, link state and 458 current utilization, and well as the capabilities of switches and 459 routers within the network. As such this information should be 460 protected from disclosure to unintended recipients. In addition, the 461 intentional modification of this information can significantly affect 462 network operations, particularly due to the large capacity of the 463 optical infrastructure to be controlled. 465 9. IANA Considerations 467 This informational document does not make any requests for IANA 468 action. 470 10. Conclusions 472 474 11. References 476 11.1. Normative References 478 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 479 Levels", BCP 14, RFC 2119, March 1997. 481 [2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax 482 Specifications: ABNF", RFC 2234, Internet Mail Consortium and 483 Demon Internet Ltd., November 1997. 485 [3] Banerjee, D.; Mukherjee, B., "A practical approach for routing 486 and wavelength assignment in large wavelength-routed optical 487 networks," Selected Areas in Communications, IEEE Journal on , 488 vol.14, no.5, pp.903,908, Jun 1996. 490 [4] Jaumard, B.; Meyer, C.; Thiongane, B.; Yu, Xiao, "ILP 491 formulations and optimal solutions for the RWA problem," Global 492 Telecommunications Conference, 2004. GLOBECOM '04. IEEE , vol.3, 493 no., pp.1918,1924 Vol.3, 29 Nov.-3 Dec. 2004 495 [5] Barpanda, R.S.; Sahoo, B.; Turuk, A.K.; Majhi, B., "Solving 496 large problem instances of the RWA problem using Genetic 497 Algorithms," Industrial and Information Systems (ICIIS), 2010 498 International Conference on , vol., no., pp.41,46, July 29 499 2010-Aug. 1 2010. 501 [6] Krishnaswamy, R.M.; Sivarajan, K.N., "Algorithms for routing 502 and wavelength assignment based on solutions of LP- 503 relaxations," Communications Letters, IEEE , vol.5, no.10, 504 pp.435,437, Oct. 2001. 506 [7] Wang, X.; Brandt-Pearce, M.; Subramaniam, S., "Dynamic grooming 507 and RWA in translucent optical networks using a time-slotted 508 ILP," Global Communications Conference (GLOBECOM), 2012 IEEE , 509 vol., no., pp.2996,3001, 3-7 Dec. 2012. 511 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 512 Requirement Levels", BCP 14, RFC 2119, March 1997. 514 [RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for 515 Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and 516 Demon Internet Ltd., November 1997. 518 11.2. Informative References 520 [8] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in TCP 521 and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 1573- 522 1583. 524 [Fab1999] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in 525 TCP and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 526 1573-1583. 528 12. Acknowledgments 530 This document was prepared using 2-Word-v2.0.template.dot. 532 Authors' Addresses 534 Shan Yin 535 BUPT 536 No.10, Xitucheng Road,Haidian District 537 Beijing 100876 538 P.R.China 539 Phone: +8613488795778 540 Email: yinshan@bupt.edu.cn 542 Shanguo Huang 543 BUPT 544 No.10, Xitucheng Road,Haidian District 545 Beijing 100876 546 P.R.China 547 Phone: +8613693578265 548 Email: shghuang@bupt.edu.cn 550 Dajiang Wang 551 ZTE Corporation 552 No.55, Technology South Road,Nanshan District 553 Shenzhen 518057 554 P.R.China 555 Phone: +8613811795408 556 Email: wang.dajiang@zte.com.cn 558 Xuan Wang 559 BUPT 560 No.10, Xitucheng Road,Haidian District 561 Beijing 100876 562 P.R.China 563 Phone: +8613581576907 564 Email: buptwangxuan@163.com 566 Yu Zhang 567 BUPT 568 No.10, Xitucheng Road,Haidian District 569 Beijing 100876 570 P.R.China 571 Phone: +8618627519028 572 Email: yx8203731@126.com