idnits 2.17.1 draft-yin-milp-rwa-otn-06.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: ' 3. Overview' ) ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 7. 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: ' 8. IANA Considerations' ) ** There are 13 instances of too long lines in the document, the longest one being 41 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 (April 10, 2018) is 2170 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Missing reference section? 'RFC2119' on line 493 looks like a reference -- Missing reference section? 'RFC2234' on line 496 looks like a reference -- Missing reference section? '1' on line 460 looks like a reference -- Missing reference section? '2' on line 463 looks like a reference -- Missing reference section? '3' on line 467 looks like a reference -- Missing reference section? '4' on line 472 looks like a reference -- Missing reference section? '5' on line 477 looks like a reference -- Missing reference section? '6' on line 483 looks like a reference -- Missing reference section? '7' on line 488 looks like a reference -- Missing reference section? '8' on line 502 looks like a reference -- Missing reference section? 'Fab1999' on line 506 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: October 2019 D.J. Wang 5 ZTE Corporation 6 X. Wang 7 Y. Zhang 8 BUPT 9 April 10, 2018 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-06 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 12,2019. 37 Copyright Notice 39 Copyright (c) 2015 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 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 ............................. ! 95 7. Security Considerations ..................................... 10 96 8. IANA Considerations ........................................ 10 97 9. Conclusions ................................................ 10 98 10. References ................................................ 10 99 10.1. Normative References .................................. 10 100 10.2. Informative References ................................ 11 101 11. Acknowledgments ........................................... 11 103 1. 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 1.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 2. 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 3. 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 3.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 3.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 4. 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 4.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 4.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 5. A MILP Model to Solve the Problem of Loading Balance of RWA 261 for 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 5.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 5.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 5.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 5.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 6. Formal Syntax 431 The following syntax specification uses the augmented Backus-Naur 432 Form (BNF) as described in RFC-2234 [RFC2234]. 434 7. Security Considerations 436 This document discussed an information model for RWA computation in 437 OTN. Such a model is very similar from a security standpoint of the 438 information that can be currently conveyed via GMPLS routing 439 protocols. Such information includes network topology, link state and 440 current utilization, and well as the capabilities of switches and 441 routers within the network. As such this information should be 442 protected from disclosure to unintended recipients. In addition, the 443 intentional modification of this information can significantly affect 444 network operations, particularly due to the large capacity of the 445 optical infrastructure to be controlled. 447 8. IANA Considerations 449 This informational document does not make any requests for IANA 450 action. 452 9. Conclusions 454 456 10. References 458 10.1. Normative References 460 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 461 Levels", BCP 14, RFC 2119, March 1997. 463 [2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax 464 Specifications: ABNF", RFC 2234, Internet Mail Consortium and 465 Demon Internet Ltd., November 1997. 467 [3] Banerjee, D.; Mukherjee, B., "A practical approach for routing 468 and wavelength assignment in large wavelength-routed optical 469 networks," Selected Areas in Communications, IEEE Journal on , 470 vol.14, no.5, pp.903,908, Jun 1996. 472 [4] Jaumard, B.; Meyer, C.; Thiongane, B.; Yu, Xiao, "ILP 473 formulations and optimal solutions for the RWA problem," Global 474 Telecommunications Conference, 2004. GLOBECOM '04. IEEE , vol.3, 475 no., pp.1918,1924 Vol.3, 29 Nov.-3 Dec. 2004 477 [5] Barpanda, R.S.; Sahoo, B.; Turuk, A.K.; Majhi, B., "Solving 478 large problem instances of the RWA problem using Genetic 479 Algorithms," Industrial and Information Systems (ICIIS), 2010 480 International Conference on , vol., no., pp.41,46, July 29 481 2010-Aug. 1 2010. 483 [6] Krishnaswamy, R.M.; Sivarajan, K.N., "Algorithms for routing 484 and wavelength assignment based on solutions of LP- 485 relaxations," Communications Letters, IEEE , vol.5, no.10, 486 pp.435,437, Oct. 2001. 488 [7] Wang, X.; Brandt-Pearce, M.; Subramaniam, S., "Dynamic grooming 489 and RWA in translucent optical networks using a time-slotted 490 ILP," Global Communications Conference (GLOBECOM), 2012 IEEE , 491 vol., no., pp.2996,3001, 3-7 Dec. 2012. 493 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 494 Requirement Levels", BCP 14, RFC 2119, March 1997. 496 [RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for 497 Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and 498 Demon Internet Ltd., November 1997. 500 10.2. Informative References 502 [8] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in TCP 503 and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 1573- 504 1583. 506 [Fab1999] Faber, T., Touch, J. and W. Yue, "The TIME-WAIT state in 507 TCP and Its Effect on Busy Servers", Proc. Infocom 1999 pp. 508 1573-1583. 510 11. Acknowledgments 512 This document was prepared using 2-Word-v2.0.template.dot. 514 Authors' Addresses 516 Shan Yin 517 BUPT 518 No.10, Xitucheng Road,Haidian District 519 Beijing 100876 520 P.R.China 521 Phone: +8613488795778 522 Email: yinshan@bupt.edu.cn 524 Shanguo Huang 525 BUPT 526 No.10, Xitucheng Road,Haidian District 527 Beijing 100876 528 P.R.China 529 Phone: +8613693578265 530 Email: shghuang@bupt.edu.cn 532 Dajiang Wang 533 ZTE Corporation 534 No.55, Technology South Road,Nanshan District 535 Shenzhen 518057 536 P.R.China 537 Phone: +8613811795408 538 Email: wang.dajiang@zte.com.cn 540 Xuan Wang 541 BUPT 542 No.10, Xitucheng Road,Haidian District 543 Beijing 100876 544 P.R.China 545 Phone: +8613581576907 546 Email: buptwangxuan@163.com 548 Yu Zhang 549 BUPT 550 No.10, Xitucheng Road,Haidian District 551 Beijing 100876 552 P.R.China 553 Phone: +8618627519028 554 Email: yx8203731@126.com