Internet DRAFT - draft-yin-milp-rwa-otn
draft-yin-milp-rwa-otn
Networking Group S. Yin
Internet Draft Sh.G. Huang
Intended status: Informational BUPT
Expires: October 2023 D.J. Wang
ZTE Corporation
X. Wang
Y. Zhang
BUPT
June 19, 2023
A MILP Model to Solve the Problem of Loading Balance of Routing and
Wavelength Assignment for Optical Transport Networks
draft-yin-milp-rwa-otn-16
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 October 20,2023.
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 October 20, 2023 [Page 1]
Internet-Draft A MILP Model for LB OF OTN June 2023
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, 2023 [Page 2]
Internet-Draft A MILP Model for LB OF OTN June 2023
6. Beneficial effects ............................. !
7. Security Considerations ..................................... 10
8. IANA Considerations ........................................ 10
9. Conclusions ................................................ 10
10. References ................................................ 10
10.1. Normative References .................................. 10
10.2. Informative References ................................ 11
11. Acknowledgments ........................................... 11
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 October 20, 2023 [Page 3]
Internet-Draft A MILP Model for LB OF OTN June 2023
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 October 20, 2023 [Page 4]
Internet-Draft A MILP Model for LB OF OTN June 2023
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 October 20, 2023 [Page 5]
Internet-Draft A MILP Model for LB OF OTN June 2023
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 October 20, 2023 [Page 6]
Internet-Draft A MILP Model for LB OF OTN June 2023
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}
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 ; [t c T]
3; 10 < B_t <= 2.5
4; 40 < B_t <= 100
Huang, et al. Expires October 20, 2023 [Page 7]
Internet-Draft A MILP Model for LB OF OTN June 2023
(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
5.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
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;[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, 2023 [Page 8]
Internet-Draft A MILP Model for LB OF OTN June 2023
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, 2023 [Page 9]
Internet-Draft A MILP Model for LB OF OTN June 2023
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]
6. Formal Syntax
The following syntax specification uses the augmented Backus-Naur
Form (BNF) as described in RFC-2234 [RFC2234].
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.
9. Conclusions
<Add any 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.
Huang, et al. Expires October 20, 2023 [Page 10]
Internet-Draft A MILP Model for LB OF OTN June 2023
[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.
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 October 20, 2023 [Page 11]
Internet-Draft A MILP Model for LB OF OTN June 2023
Authors' Addresses
Shan Yin
BUPT
No.10, Xitucheng Road,Haidian District
Beijing 100876
P.R.China
Phone: +8613488795778
Email: yinshan@bupt.edu.cn
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, 2023 [Page 12]
