Signal Processing - January 2016 - 72
[TaBle 6] a coMParISon oF dIFFerenT algorIThMS.
m = 200.
aPProacheS
gurobi
synchronous bsumm
(ten ncs, one core)
synchronous bsumm
(ten ncs, ten core)
asynchronous bsumm
(ten ncs, ten core)
TIMe
11.4690 s
18.0679 s
nuMBer oF ITeraTIonS
n/a
264.71
5.80 s
264.71
4.23 s
2109.07
2) Flow conservation constraints. For any node v ! V and
data flow m, the total incoming flow should be equal to the
total outgoing flow:
/
fl, m + 1 v = s (m) rm =
l ! In (v)
/
fl, m + 1 v = d (m) rm,
l ! Out (v)
m = 1, g, M, 6v ! V,
(31)
where In (v) _ {l ! L d l = v} and Out (v) _ {l ! L s l = v}
denote the set of links going into and coming out of a node
v respectively; 1 v = x = 1 if v = x otherwise 1 v = x = 0.
To provide fairness to the users, we maximize the minimum
rate of all data flows. The problem can be formulated as the following linear program (LP)
max
rmin
f, r
s.t. f $ 0, rm $ rmin, m = 1, g, M
(30) and (31),
(32a)
(32b)
where f _ {fl l ! L} and r _ {rmin, rm m = 1~M}. Obviously,
one can use off-the-shelf optimization packages such as Gurobi
[96] to solve the LP (32), but this is only viable in a centralized
setting where all the flows are managed by a single controller.
To enable distributed/parallel network management across the
NCs, we need to allow each NC i to independently optimize the
variables belonging to the subnetwork N i. However, this task is
difficult because the optimization variables of (32) is coupled
(indeed each flow rate fm appears in exactly two flow conservation
constraints). To address this problem, we introduce a few sets of
new variables to decouple the flow conservation constraints across
different subnetworks (see [95] for the detailed reformulation).
The reformulated problem (32) is given by
max
rmin
x
s.t. {rmin, x 02} ! X 0, {x i1, x i2} ! X i1, x i3 ! X i2,
x i01 = x i02, x i1 = x i01, x i2 = x i3, i = 1gK,
14420443 1442
4403 >
i
i
inN
inN andN
inN
where X 0, X i1, and X i2 are some feasible sets, and
{rmin, x 02, x 01, x i1, x i2, x i3} are the block variables. By applying the
BSUMM, we can obtain a parallel/distributed algorithm. A few
remarks about the implementation of this algorithm are:
1) The replication of link/flow variables for links across different subnetworks allows each subnetwork to be considered
separately and independently. This feature makes the
BSUMM subproblems solvable in parallel. The requirement
of the replicated variables being the same as the original variables is enforced by the linear coupling constraints, and
they can be satisfied asymptotically as the BSUMM algorithm converges.
2) The subproblems of the proposed BSUMM-based algorithm can be solved by each NC very efficiently. For example,
the update of {rmin, x 02} can be performed by each NC in
closed form; the update of {x i, x i01} can be performed by running the well-known RELAX code [97].
3) A careful implementation of the BSUMM allows the NCs to
act asynchronously, in the sense that they do not need to
coordinate with each other for computation. Such asynchronous implementation has the potential of greatly
improving the computational efficiency.
We illustrate the BSUMM implementation over a mesh wireline network with 126 nodes, which is randomly partitioned into
nine subnetworks with 306 directed links within these subnetworks and 100 directed links connecting the subnetworks. The
capacities for the links within (resp. between) the subnetworks are
uniformly distributed in [50,100] megabits/second (resp. [20,50]
megabits/second). All simulation results are averaged over 200
randomly selected data flow pairs and link capacity.
To demonstrate the benefit of parallelization, we also utilize a
high-performance computing cluster, and make each computing
node to be an NC. We compare a few different approaches for
solving (32):
1) use Gurobi [96], a centralized LP solver
2) apply the synchronous BSUMM algorithm, with K = 10 NCs;
the computation is done by either a single or by ten distributed computing cores
3) apply the asynchronous BSUMM with K = 10 NCs; the
computation is done in ten distributed computing cores.
Note that the asynchrony in the network arises naturally
from the per-node computational delay and network communication delay. In Table 6, we demonstrate the performance of various algorithms when M = 200. Clearly, the asynchronous
BSUMM with a small number of NCs outperforms all the rest of
the algorithms.
The numerical results suggest that appropriate network
decomposition and asynchronous implementation are both critical for the fast convergence of BSUMM. In practice, we observe
that the network should be decomposed following a few
guidelines:
■ the computation burden across the subnetworks is well
balanced
■ the subroutine within the network can achieve its maximum efficiency
■ the total number of replicated auxiliary variables is small.
NONCONvEx CONStRAINtS
The BSUM idea can be straightforwardly extended to a nonconvex constraint scenario for single block optimization problems.
To proceed, consider the optimization problem:
IEEE SIGNAL PROCESSING MAGAZINE [72] jANuARy 2016
Table of Contents for the Digital Edition of Signal Processing - January 2016
Signal Processing - January 2016 - Cover1
Signal Processing - January 2016 - Cover2
Signal Processing - January 2016 - 1
Signal Processing - January 2016 - 2
Signal Processing - January 2016 - 3
Signal Processing - January 2016 - 4
Signal Processing - January 2016 - 5
Signal Processing - January 2016 - 6
Signal Processing - January 2016 - 7
Signal Processing - January 2016 - 8
Signal Processing - January 2016 - 9
Signal Processing - January 2016 - 10
Signal Processing - January 2016 - 11
Signal Processing - January 2016 - 12
Signal Processing - January 2016 - 13
Signal Processing - January 2016 - 14
Signal Processing - January 2016 - 15
Signal Processing - January 2016 - 16
Signal Processing - January 2016 - 17
Signal Processing - January 2016 - 18
Signal Processing - January 2016 - 19
Signal Processing - January 2016 - 20
Signal Processing - January 2016 - 21
Signal Processing - January 2016 - 22
Signal Processing - January 2016 - 23
Signal Processing - January 2016 - 24
Signal Processing - January 2016 - 25
Signal Processing - January 2016 - 26
Signal Processing - January 2016 - 27
Signal Processing - January 2016 - 28
Signal Processing - January 2016 - 29
Signal Processing - January 2016 - 30
Signal Processing - January 2016 - 31
Signal Processing - January 2016 - 32
Signal Processing - January 2016 - 33
Signal Processing - January 2016 - 34
Signal Processing - January 2016 - 35
Signal Processing - January 2016 - 36
Signal Processing - January 2016 - 37
Signal Processing - January 2016 - 38
Signal Processing - January 2016 - 39
Signal Processing - January 2016 - 40
Signal Processing - January 2016 - 41
Signal Processing - January 2016 - 42
Signal Processing - January 2016 - 43
Signal Processing - January 2016 - 44
Signal Processing - January 2016 - 45
Signal Processing - January 2016 - 46
Signal Processing - January 2016 - 47
Signal Processing - January 2016 - 48
Signal Processing - January 2016 - 49
Signal Processing - January 2016 - 50
Signal Processing - January 2016 - 51
Signal Processing - January 2016 - 52
Signal Processing - January 2016 - 53
Signal Processing - January 2016 - 54
Signal Processing - January 2016 - 55
Signal Processing - January 2016 - 56
Signal Processing - January 2016 - 57
Signal Processing - January 2016 - 58
Signal Processing - January 2016 - 59
Signal Processing - January 2016 - 60
Signal Processing - January 2016 - 61
Signal Processing - January 2016 - 62
Signal Processing - January 2016 - 63
Signal Processing - January 2016 - 64
Signal Processing - January 2016 - 65
Signal Processing - January 2016 - 66
Signal Processing - January 2016 - 67
Signal Processing - January 2016 - 68
Signal Processing - January 2016 - 69
Signal Processing - January 2016 - 70
Signal Processing - January 2016 - 71
Signal Processing - January 2016 - 72
Signal Processing - January 2016 - 73
Signal Processing - January 2016 - 74
Signal Processing - January 2016 - 75
Signal Processing - January 2016 - 76
Signal Processing - January 2016 - 77
Signal Processing - January 2016 - 78
Signal Processing - January 2016 - 79
Signal Processing - January 2016 - 80
Signal Processing - January 2016 - 81
Signal Processing - January 2016 - 82
Signal Processing - January 2016 - 83
Signal Processing - January 2016 - 84
Signal Processing - January 2016 - 85
Signal Processing - January 2016 - 86
Signal Processing - January 2016 - 87
Signal Processing - January 2016 - 88
Signal Processing - January 2016 - 89
Signal Processing - January 2016 - 90
Signal Processing - January 2016 - 91
Signal Processing - January 2016 - 92
Signal Processing - January 2016 - 93
Signal Processing - January 2016 - 94
Signal Processing - January 2016 - 95
Signal Processing - January 2016 - 96
Signal Processing - January 2016 - 97
Signal Processing - January 2016 - 98
Signal Processing - January 2016 - 99
Signal Processing - January 2016 - 100
Signal Processing - January 2016 - 101
Signal Processing - January 2016 - 102
Signal Processing - January 2016 - 103
Signal Processing - January 2016 - 104
Signal Processing - January 2016 - 105
Signal Processing - January 2016 - 106
Signal Processing - January 2016 - 107
Signal Processing - January 2016 - 108
Signal Processing - January 2016 - 109
Signal Processing - January 2016 - 110
Signal Processing - January 2016 - 111
Signal Processing - January 2016 - 112
Signal Processing - January 2016 - 113
Signal Processing - January 2016 - 114
Signal Processing - January 2016 - 115
Signal Processing - January 2016 - 116
Signal Processing - January 2016 - 117
Signal Processing - January 2016 - 118
Signal Processing - January 2016 - 119
Signal Processing - January 2016 - 120
Signal Processing - January 2016 - 121
Signal Processing - January 2016 - 122
Signal Processing - January 2016 - 123
Signal Processing - January 2016 - 124
Signal Processing - January 2016 - 125
Signal Processing - January 2016 - 126
Signal Processing - January 2016 - 127
Signal Processing - January 2016 - 128
Signal Processing - January 2016 - 129
Signal Processing - January 2016 - 130
Signal Processing - January 2016 - 131
Signal Processing - January 2016 - 132
Signal Processing - January 2016 - 133
Signal Processing - January 2016 - 134
Signal Processing - January 2016 - 135
Signal Processing - January 2016 - 136
Signal Processing - January 2016 - 137
Signal Processing - January 2016 - 138
Signal Processing - January 2016 - 139
Signal Processing - January 2016 - 140
Signal Processing - January 2016 - 141
Signal Processing - January 2016 - 142
Signal Processing - January 2016 - 143
Signal Processing - January 2016 - 144
Signal Processing - January 2016 - 145
Signal Processing - January 2016 - 146
Signal Processing - January 2016 - 147
Signal Processing - January 2016 - 148
Signal Processing - January 2016 - 149
Signal Processing - January 2016 - 150
Signal Processing - January 2016 - 151
Signal Processing - January 2016 - 152
Signal Processing - January 2016 - 153
Signal Processing - January 2016 - 154
Signal Processing - January 2016 - 155
Signal Processing - January 2016 - 156
Signal Processing - January 2016 - 157
Signal Processing - January 2016 - 158
Signal Processing - January 2016 - 159
Signal Processing - January 2016 - 160
Signal Processing - January 2016 - 161
Signal Processing - January 2016 - 162
Signal Processing - January 2016 - 163
Signal Processing - January 2016 - 164
Signal Processing - January 2016 - 165
Signal Processing - January 2016 - 166
Signal Processing - January 2016 - 167
Signal Processing - January 2016 - 168
Signal Processing - January 2016 - Cover3
Signal Processing - January 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com