Int. J. Communications, Network and System Sciences, 2010, 3, 850-854
doi:10.4236/ijcns.2010.311115 Published O nline Novem ber 2010 (http:// www.SciRP.org/journal/ijcns)
Service Networks Topological Design
Boris S. Verkhovsky
Computer Scien ce Department, New Jersey Institute of Technology, Newark, USA
Received June 18, 2010; revised August 12, 2010; accepted September 23, 2010
Abstract
Topological design of service networks is studied in the paper. A quantitative model and algorithm minimiz-
ing cost of processing and delivery are described. An algorithm solving combinatorial problem of optimal
design based on binary partitioning, a parametric search and dynamic programming optimization of a binary
tree are described and demonstrated in numeric examples.
Keywords: Delivery/Processing Cost, Binary Partitioning, Dynamic Programming, First Responders,
Average Complexity, Service Provider, Water Desalination
1. Introduction and Problem Definition
Modern satellite communication networks with their
terrestrial users interconnected via terrestrial links with
earth stations are an example of a service providing net-
work (SPN).
Modern telecommunications is a highly competitive
business. To reduce service fees and to make it eco-
nomically attractive to potential customers, a communi-
cation company must decide how many earth stations of
each type it needs, where to allocate them, and how the
customers must be interconnected with the earth stations.
A correct decision can save hundreds of millions of dol-
lars annually and hence can attract more users.
In more general terms we consider a set of users that
require a service [1]. The type of service can be either
water desalination and/or purification and delivery to
customers. Or it can be a regional gas supply. Or emer-
gency services (ERs, fire departments, or police station
or a set of first responders). Or a set of special postal
service providers (mail deliverers, UPS offices, etc.).
From a computational point of view, the problem is
NP-complete, i.e., it requires brute-force algorithms or
heuristics with exponential time-complexity. These ap-
proaches must find an optimal way of clustering all users,
[2-5]. This paper describes a set of algorithms that solve
the problem of clustering-and-location of all serv ice pro-
viders with a polynomial time complexity. Preliminary
results are provided in [6]. For more insights on prob-
lems and algorithms related with network design see
[7-12].
2. Problem Statement
1) Let us consider locations of n users with coordinates
Pi = (ai, bi), i = 1, , n. Each user is characterized by a
“volume” of required service wi (“weight” of i-th user);

2) Let


,
kkk
Cuvbe a location of k-th service cen-
ter (server, for short), k = 1, 2, , m;

3) Let Sk be a set of all users connected with the k-th
server Ck;
4) Let f (wi, Pi, Ck) be a cost function of the link con-
necting the i-th user Pi and k-th server Ck;
here for all i = 1, 2, , n Pi are the inputs and for all k =
1, 2, , m Ck are decision variables.


Then a minimal total cost of all links and all servers
equals

11
,, ,,1
min min,()
mm kk
m
SSCCik ki
kiS iS
i
f
PC qw
 





 
 ,
(1)
where (
k
k
iS
q
)
i
w

is the cost of k-th server as a non-
linear function of all service flows. Thus the problem (1 )
requires a comprehensive analysis in order to find opti-
mal clusters (subsets) S1, , Sm. 
Models and methods of clustering in general has been
studied and described in [5]. Surveys on models and al-
gorithms related to clustering are provided in [5,9].
3. Special Cases
Case 1: The number m of servers is known and the cost
function of every server is independent of required proc-
essing volume. If locations of all servers are specified,
then it is easy to find the clusters Sk.

B. VERKHOVSKY
851

j

k
Indeed, in
 

1
:: ,,:min,,
kiikjmii
S ifwPCfwPC

 (2)
i.e., every user is connected with the closest or least ex-
pensive delivery link.
Case 2: If for k = 1, , m Sk ar e known, then the op-
timal allocation of every server can be determined inde-
pendently:


min, ,
kk
Cii
iS
f
wPC

 (3)
for k = 1, , m. 
Case 3: If f (wi, Pi, Ck) = wi × dist (Pi, Ck), then the
problem (3) is known as a Weber problem. This problem
has been investigated by m a ny authors over the last thirty
years. For references see [10,13-16].
Case4: ()is a linear or convex function,
i.e., k
k
iS
q

i
w




21
12kk
qw wqwqw 
k
Then






22kkk
kik ik
iS iSiS
qwq wq
 

 
1
i
w
1
which means that the more clusters the better.
The difficulties arise if the clusters Sk are not known,
the cost of every server is neither small nor flow-inde-
pendent, and the number m of servers and their optimal
locations (uk, vk) for all k are not know n.
4. Division onto Two Clusters
It is important to stress that there is a substantial differ-
ence between the two cases: m = 1 and m = 2. In the lat-
ter case the problem can be solved by repetitive applica-
tion of an algorithm for the Weber problem. This must be
done for all possible pairs of clusters S1 and S2. Ther e are
different ways to partite n points onto two sub-
sets S1 and S2 and, for each clustering, two Weber prob-
lems must be solved. Thus, the total time complexity of
this brute-force approach {even for m = 2} is O(2n), [3].
1
2
n
5. Binary Parametric Partitioning
In this section we provide a procedure that divides a
network N1 with one server S1 onto two sub-networks N2
and N3 with two servers.
Step A1: {find optimal location of “center of gravity”
0 for all n users, [1]}; consider m = 1 and solve the
problem
C


1
min, ,
n
Cii
i
f
wPC

. (4)
Step A2: consider a straight line L and rotate it around
the center of gravity C0; {for every angle x of rotation the
line L divides all points onto two clusters S1(x) and
S2(x)}; i
P
Step A3: for every point (user) consider polar coordi-
nates (

i, di) using C0 as the origin of the coordinate sys-
tem; {here 
i is an angular coordinate of Pi};
Step A4: for i = 1 to n do
:mod
ii
x



; (5)
sort all xi in ascending order;
Step A5: if xi = 
i then chi = 1
else chi = 0;
Step A6: if (xi  x and chi = 1) or (xi > x and = 0)
then i
ch


1i
PSx else ;

2i
PSxiS
Step A7: for k = 1,2 and compute

kx



 
:min ,,
kk
kkC iik
iS

g
Sx fwPC

 ; (6)
Step A8: {compute the cost of two servers and all
links}:



   
12
12
112 2
:ii
iS iS
hxqw qw
gSx gSx






(7)
Remark 1: The line L divides all n points onto two clus-
ters, S1(x) and S2(x), by at most n different ways as the
angle x changes from 0 to

;
Step A9: Rotate the separating line L and find an angle
that minimizes the function






0
(7) ::minx hx seehrhx
 
 (8)
Robustness of partitioning: In Step A9, the angle of
rotation x of line L is the parameter. Several thousands
computer experiments demonstrate that L divides all
points/users onto two subsets S1 and S2 in such a way that
for k = 1, 2 the following property almost always holds:
if (),
k
iSr

then (9)
3
(, , )(, , )
ii kiik
fw PCfw PC


However, if n is larg e, the n with small probabilities there
are one or two points (called “fugitives”), for which (9)
does not hold;
Step A10: if for iS1(r)
f (wi, Pi, C1) > f (wi, Pi, C2),
then reassign iS2(r);
if for iS2(r)
f (wi, Pi, C2) > f (wi, Pi, C1),
then reassign iS1(r);
Remark 3: iS1(r), then
12
Prob [(, , )(, , )],
ii ii
fw PCfw PC


where 0,if400and 1/200if500nn



 
Therefore the separating like with very high probabil-
ity cluster the points onto two sets, for which (9) holds.
Step A11: using (7) and (8) update optimal locations

852 B. VERKHOVSKY
of C1 and C2 for new values of S1(r) and S2(r); {we de-
fine S1(r) and S2(r) as the optimal binary partitioning}.
Remark 4: The computer experiments for 25 600n


indicate remarkable robustness of the Binary Partitioning
Algorithm (BPA): the Step 10 and Step 11 do not create
instability of the BPA, [6].
6. Search for “Center of Gravity”
Step B1: assign flag: = 0;
11
11
:/
:/
ii i
iN iN
ii i
iN iN
uwa
vwb






;w
w

Step B2: for all
1
iN

22
:
ii
Ruavb
i


;
;
Step B3: old(u,v): = (u,v);


:///
:///
ii ii i
ii
ii ii i
ii
uwxRwR
vwyRwR




Step B4: while



,,,distolduvuv

 

,
repeat Steps B2 and B3;
Step B5 {search of a stationary point SP;

is a
specified accuracy of location of the center of gravity}:
Assign SP: = (u,v);
Step B6: if for all {
1
jN

,j distSPP

 and fla g
= 0}, then SP is the “center of gravity”;
if for all {
1
jN

,j distSP P

 and 1flag

},
then ; flag: = 0; goto Step B2;

11
NN

nt:p
Step B7: if

,j distSPP



pnt
then ; pnt: =
k; .
1flag 
11
:N N
7. Minimax Search for Minimum of h(x)
Let h be a function computable on a set S of N discrete
points 1,,
N
x
x
,, . It is obvious that N evaluations of h at
points 1
N
x
x are enough to solve any problem by
total enumeration. However, since h is a periodic func-
tion with known period P, i.e., holds
for every integer k, and for every i = 1, , N, an opti-
mal algorithm with time complex ity of order

ii
hx kPhx




Nlog.is
developed and published in [16,17].
8. Binary Partitioning & Associated Binary
Tree
Let :
kkk
H
ts where Hk is a combined cost of the
network Nk. Let’s consider an algorithm that divides the
network N1 into two sub-networks N2 and N3 with corre-
sponding service delivery costs t2 and t3 and correspond-
ing costs of servers s2 and s3. We assume that the algo-
rithm divides N1 into two subnets in such a way that t2 +
t3 + s2 + s3 is minimal.
For further consideration we represent the binary par-
titioning as a binary tree where the root of the tree repre-
sents a cluster (set of all users) S1 and associated with it
the network N1. In general, a k-th node of the binary tree
represents a cluster Sk and associated with it a network Nk.
Two children of the k-th node represent two sub-net-
works N2k and N2k + 1 of the network Nk (as result of the
binary partitioning).
From the above definitions and from the essence of the
problem it is clear that fo r all k the following inequalities
hold
221 22
,and
kkkk kkk1
s
ss st tt


 . (10)
The latter inequality holds because each sub-network
N2k and N2k + 1 has a smaller number of users than Nk.
9. Non-Monotone Nature of Total Cost
If Hk > H2k + H2k + 1, then it is obvious th at a partitioning
into two clusters (sub-networks) is cost-wise beneficial.
However, Hk < H2k + H2k + 1 does not imply that any
further partitioning is not cost-wise beneficial. To illus-
trate that let’s consider a network Nk and its six subnet-
works N2k, N2k + 1, N4k, N4k + 1, N4k + 2, N4k + 3.
Remark 6: To demonstrate various cases we consider
two scenarios of inputs in the following table.
Case H1 = 91 (see Table 1): since H1 > H2 + H3, then
the binary partitioning of N1 into two sub-networks is
gainful;
Case H1 = 86 (see Table 2) illustrates that a local
analysis of the total costs does not provide a correct in-
sight.
Table 1. t1 = 67 and for t5 = 11.
Sub-networks Ni N1N2 N3 N4 N5 N6N7
Delivery-link cost ti67 25 29 12 11 107
Server cost sk 2419 17 10 14 129
Total cost Hk 9144 46 22 25 2216
Table 2. t1 = 62 and for t5 = 7.
Sub-networks Ni N1N2 N3 N4 N5 N6N7
Delivery-link cost ti62 25 29 12 7 107
Server cost sk 2419 17 10 14 129
Total cost Hk 8644 46 22 21 2216

B. VERKHOVSKY
853
k
In this case H1 < H2 + H3, which only implies that
there is no reason to divide the network N1 into two
sub-networks N2 and N3. However, further analysis
demonstrates that
H1 > H4 + H5 + H6 + H7 if H5 = 21;
{indeed, 86 > 22 + 21 + 22 + 16 = 81};
and H1 > H2 + H6 + H7 if H5 = 25;
{indeed, 91 > 44 + 22 + 16 = 82};
These examples illustrate that for a prop er partitioning
a global rather than a local analysis is required.
Definition 1: We say that a network Nk is indivisible if
there is no cost-wise advantage to divide it onto any
number of sub-networks.
In addition, some sub-networks may not be further di-
visible if they do not satisfy at least one of the following
threshold conditions:
a) Their request for service is lower than a specified
threshold;
b) The number of users in the cluster is smaller than a
specified threshold.
Definition 2: We say that an optimal configuration of a
service network is determined if all indivisible sub-net-
works of the initial network N1 are known.
10. Dynamic Programming Algorithm
{The algorithm assigns final labels to all nodes of the
associated binary tree; then determines all balanced
nodes and then all prime nodes};
Bottom-up mode: a) {assign to k-node a label};
:, 1,2,,
kk
LHkm; (11)
b) if i-th node is a leaf then its final label
:
k
F
L; (12)
c) if both children of k-th node ha ve fi nal lab e l s then

221
:min ,
kkk
FLFF



k
; (13)
d) if the final labels Fk are computed for all nodes then
goto the next mode;
Top-down mode: Starting from k=1 we find a node j,
for which holds
j
j
F
L. (14)
It can be shown that it is not cost-wise advantageous
to consider the d escendants of this node, i.e., this nod e is
indivisible.
Definition 3: We say that j-th node is balanced if
j
j
F
L holds.
Definition 4: A node that does not have a balanced
ancestor is a prime node.
Proposition: The set of all prime nodes repre-
sents the optimal partitioning.
opt
P
Proof: Let’s prove by reduction that (13) is always
computable, i.e., when we need to compute a final label
for the k-th node, the final nodes of its both children are
already computed.
Indeed, consider a sub-tree T1 with five nodes {A, B,
C, D, E} and sub-tree T2 with seven nodes {A, B, C, D,
E, G, H}, where in both sub-trees node A is a root.
Sub-tree T1: Let B and E be the children of A; and C
and D be the children of B. In addition, let the nodes C,
D and E be leaves.
Then by definition (1 2),
:;:and :
CCDD EE
F
LFLF L

. (15)
Therefore, :min(, )
B
BC D
F
LFF


and :min(, )
AABE
F
LF F

. (16)
Thus, if T1 is a sub-tree of a larger tree, we can com-
pute five final labels, i.e., we reduce the number of un-
known final labels by five.
Sub-tree T2: Let B and E be the children of A; C and
D be the children of B; G and H be children of E. In T2
nodes C, D, G and H are the leaves.
It is easy to see that this case can be reduced to the
previous case by computing the final label of E. Indeed,
by definition (12), :and :
GG HH
F
LFL

 (17)
Therefore, :min(, )
E
EG H
F
LF F

 (18)
Thus, after the final label of node E is known, we can
consider it as a virtual leave. In other words, we reduced
the sub-tree T2 to the su b-tree T1.
Hence, if T2 is a sub-tree of a larger tree, we can
compute the all final labels of its nodes, i.e. , we reduce
the number of unknown final labels by seven.
It is clear that in order to compute a final label for
every node we need one addition and one comparison.
Hence the overall complexity to compute the fin al labels
has order O(M), where M is the number of nodes in the
initial tree. In the worst case every leave has at least 2
users. Thus the total number of nodes M on the tree does
not exceed n – 1, where n is the number of the users.
Therefore the complexity equals O(n).
11. Optimal Algorithm for Large n
It is easy to see that the parametric partitioning requires
in general case exactly n rotations of the separating line
L. As a result, the time-complexity f(n) to divide n users
onto two clusters is equal f (n) = an2 + O1(n) for large n.
However, from computer experiments for large number
of users n h(x) has one maximum and one minimum
when L is rotated on 180 degrees. In this case the search
algorithm requires O(logn) rotations of the separating
line L. As a result, f (n) = bnlogn + O2(n) for large n and

B. VERKHOVSKY
854
overall worst-case complexity is of order .

2lognn
As it shown in [18] an average complexity of the
problem can be further improved. The developed ap-
proach demonstrates that the average complexity of the
overall binary partitioning is of order .

2
lognn
12. Conclusions
The ideas and algorithms described in this paper have
numerous applications. In the set of algorithms provided
above the Binary Partitioning algorithm (BPA) is a core
sub-algorithm for solutions of many problems dealing
with configuration/topological design of networks and
other clustering problems. As the core sub-algorithm, the
BPA has to be repeatedly executed many times; therefore
it is essential to make the BPA computationally as effi-
cient as possible. There are several computational blocks
within the BPA:
 To determine an optimal location of the “centre
of gravity”;
 To detect of a minimum of computable function
using the smallest number of its probes;
 To estimate an average complexity of a di-
vide-and-conquer algorithm.
We developed an appropriate quantitative analysis to
handle efficiency of the BPA.
Finally, it is shown how to apply a dynamic program-
ming to tackle combinatorial complexity of reconstruct-
ing the best network after numerous binary partitions.
13. Acknowledgement
I express my appreciation to D. Nowak for his assistance.
14. References
[1] M. Fiddler and V. Sander, “A Parameter Based Admis-
sion Control for Differentiated Services Networks,”
Computer Networks, Vol. 44, No. 4, March 2004, pp.
463-479.
[2] A. Chaves and L. Lorena, “Clustering Search Algorithm
for the Capacitated Centered Clustering Problem,” Com-
puters and Operations Research, Vol. 37, No. 3, March
2010, pp. 552-558.
[3] G. Diehr, “Evaluation of a Branch-and-Bound Algorithm
for Clustering,” SIAM Journal on Scientific and Statisti-
cal Computing, Vol. 6, No. 2, April 1985, pp. 268-284.
[4] J. Heath, M. Fu and W. Jank, “New Global Optimization
Algorithms for Model-Based Clustering,” Computational
Statistics and Data Analysis, Vol. 53, No. 12, October
2009, pp. 3999-4017.
[5] A. Kusiak, A. Vannelli and K. R. Kumar, “Clustering
Analysis: Models and Algorithms,” Control and Cyber-
netics, Vol. 15, No. 2, 1986, pp. 139-154.
[6] B. Verkhovsky, “Satellite Communication Networks:
Configuration Design of Terrestrial Subnetworks”, Jour-
nal of Telecommunications Management, 2010.
[7] M. Gen and R. Cheng, “Evolutionary Network Design:
Hybrid Genetic Algorithms Approach,” International
Journal of Computational Intelligence and Applications,
Vol.3, No. 4, December 2003, pp. 357- 380.
[8] H. L. Chen and R. Tim, “Network Design with Weighted
Players,” Theory of Computing Systems, Vol. 45, No. 2,
June 2009, pp. 302-324.
[9] D. S. Johnson, J. K. Lenstra and A. H. G. Rinooy Kan,
“The Complexity of the Network Design Problem,” Net-
works, Vol. 8, No. 4, 1978, pp. 279-285.
[10] P. McGregor and D. Shen, “Network Design: An Algo-
rithm for the Access Facility Location Problem,” IEEE
Transactions on Communications, Vol. COM-25, No. 1,
January 1977, pp. 61-73.
[11] J. Smith, F. Cruz and T. V. Woensel, “Topological Net-
work Design of General, Finite, Multi-Server Queuing
Networks,” European Journal of Operational Research,
Vol. 201, No. 2, March 2010, pp. 427-441.
[12] B. Verkhovsky, “Constrained Shortest Path Algorithm for
Network Design,” International Journal of General Sys-
tems, Vol. 23, No. 2, 1996, pp. 183-195.
[13] M. Bischoff and K. Dächert, “Allocation Search Methods
for a Generalized Class of Location–Allocation Prob-
lems,” European Journal of Operational Research, Vol.
192, No. 3, February 2009, pp. 793-807.
[14] R. Bellman, “An Application of Dynamic Programming
to Location–Allocation Problems,” SIAM Review, Vol. 7,
No. 1, January 1965, pp. 126-128.
[15] J. Zhou and B. Liu, “Modeling Capacitated Loca-
tion–Allocation Problem with Fuzzy Demands,” Com-
puters and Industrial Engineering, Vol. 53, No. 3, Octo-
ber 2007, pp. 454-468.
[16] B. Veroy (Verkhovsky), “An Optimal Algorithm for
Search of Extreme of a Bimodal Function,” Journal of
Complexity, Vol. 2, 1986, pp. 323-332.
[17] B. Veroy, “Optimal Search Algorithms for Extrema of a
Discrete Periodic Bimodal Function," Journal of Com-
plexity, Vol. 5, No. 2, June 1989, pp. 238-250.
[18] B. Veroy, “Average Complexity of a Divide-and-Con-
quer Algorithms,” Information Processing Letters, Vol.
29, No. 6, December 1988, pp. 319-326.