Skip to main content

A MILP Model to Solve the Problem of Loading Balance of Routing and Wavelength Assignment for Optical Transport Networks
draft-yin-milp-rwa-otn-02

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Expired".
Authors Shan Yin , Shanguo Huang , Dajiang Wang , Xuan Wang , Yu Zhang
Last updated 2016-04-19
RFC stream (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-yin-milp-rwa-otn-02
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
                                                          April 20, 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-02

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.

1.1.1.1.1.1.1. 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 October 20, 2016                [Page 1]
Internet-Draft       A MILP Model for LB OF OTN             April 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
   OTN ............................................................ 6
      5.1. Parameters ............................................. 6
      5.2. Variables .............................................. 7
      5.3. Objective Function...................................... 8
      5.4. Constraints ............................................ 8

Huang, et al.         Expires October 20, 2016                [Page 2]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   6. Beneficial effects ......................................... 10
   7. Security Considerations..................................... 10
   8. IANA Considerations ........................................ 11
   9. Conclusions ................................................ 11
   10. References ................................................ 11
      10.1. Normative References.................................. 11
      10.2. Informative References................................ 12
   11. Acknowledgments ........................................... 12

   2. 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.

2.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 October 20, 2016                [Page 3]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   OTN: Optical Transport Networks.

   3. 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].

   4. 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.

4.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 October 20, 2016                [Page 4]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

4.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.

   5. 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.

5.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.

5.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 October 20, 2016                [Page 5]
Internet-Draft       A MILP Model for LB OF OTN             April 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.

   6. 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.

6.1. Parameters

   o G=(V,E) Undirected graph topology for physical network

Huang, et al.         Expires October 20, 2016                [Page 6]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   o SUM_s,d [F_sd] The sum of F_sd for all valid s and d

   o [A c B]  A belongs to B

   o A /= B  A is not equal 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, [t c T]

   o D_t   The destination node of the traffic, [t c T]

   o B_t   The bandwidth occupied by the traffic, [t c T]

   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, [vi c V]

   o K     The order of the ODU, K={1,2,3,4}

6.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 ; [t c T]
         3; 10 < B_t <= 2.5
         4; 40 < B_t <= 100

Huang, et al.         Expires October 20, 2016                [Page 7]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   (3)The parameter X_t represents the status of the connection
      establishing:

        1, If the traffic t is established successfully
   X_t={0,                 Otherwise                   ; [t c T]

   (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           ;[t c T]

   (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                             ;[t c T],[l c L]
             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      ;[t c T],[l c L],[k c K]
                0,          Otherwise

6.3. Objective Function

   o Objective Function: min R=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

6.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;[t c T], [t c T], [l c L]

   (2)To prevent self-loop: for the source node or the destination node,
      there should be only one adjacent link to transmit traffic;

      SUM_[e c w(vi)] [X_t(e)] = 1;  [t c T],[vi c {s_t,d_t}]

Huang, et al.         Expires October 20, 2016                [Page 8]
Internet-Draft       A MILP Model for LB OF OTN             April 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_[e c w(vi)] [X_t(e)] <= 2;  [t c T],[vi c V\{s_t,d_t}]

      SUM_([e' c w(vi)],e'/=e) [X_t(e')] >= X_t(e);[t c T],[e c w(vi)],
                                                  [vi c V\{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);  [e c E],[l c L]

      SUM_l SUM_k [X_t(e,l,k)] <= X_t(e);  [e c E],[l c L]

      All of the links transmitting the traffic should provide the same
      wavelength and ODU_k:

      SUM_[e c w(vi)] SUM_l [X_t(e,l)] = 1;  [t c T],[l c L],
                                            [v_i c {s_t,d_t}]

      SUM_[e c w(vi)] [X_t(e,l)] <= 2;     [t c T],[l c L],
                                          [vi c V\{s_t,d_t}]

      SUM_([e' c w(vi)],e'/=e [X_t(e',l)]) >= X_t(e,l); [t c T],[l c L],
                                                   [vi c V\{s_t,d_t}]

   (4)The source node and the destination node of the same traffic
      should use the same wavelength:

      SUM_[e c w(s_t)] [X_t(e,l)] = SUM_[e' c w(d_t)] [X_t(e',l)];
                                                  [t c T],[l c L]

      The source node and the intermediate node should use the same
      wavelength:

      SUM_[e c w(s_t)] [X_t(e,l)] + SUM_eEw(d_t) [X_t(e,l)] >=
       SUM_[e c w(vi)][X_t(e,l)];   [t c T],[e c E],[l c L],
                                    [vi c V\{s_t,d_t}]

      SUM_[e c w(vi)] [X_t(e,l)] <= 2;  [t c T],[e c E],[l c L],
                                        [vi c V\{s_t,d_t}]

      To measure the average degree between resource utilizations of
      all links, we need two integer variables:

Huang, et al.         Expires October 20, 2016                [Page 9]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

      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];  [e c E]

      o S represents the maximum of the resource utilizations of all
         links:

         S >= R_e/(WB);  [e c E]

   7. 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.

   8. 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.

Huang, et al.         Expires October 20, 2016               [Page 10]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   9. IANA Considerations

   This informational document does not make any requests for IANA
   action.

   10. Conclusions

   <Add any conclusions>

   11. References

11.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.

Huang, et al.         Expires October 20, 2016               [Page 11]
Internet-Draft       A MILP Model for LB OF OTN             April 2016

   [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.

11.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.

   12. Acknowledgments

   This document was prepared using 2-Word-v2.0.template.dot.

Huang, et al.         Expires October 20, 2016               [Page 12]
Internet-Draft       A MILP Model for LB OF OTN             April 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 October 20, 2016               [Page 13]