Plenary
Lecture
An Algorithm for the Network Design Problem Based on the
Maximum Entropy Method
Professor Milan Tuba
University Megatrend Belgrade
Faculty of Computer Science
Serbia
Email: tuba@ieee.org
Abstract: Network design
problem is a well known NPhard
problem which involves topology
selection (subset of possible
links), routing determination
(paths for the offered traffic)
and possibly capacity assignment.
The goal is to minimize the cost,
which can be a combination of the
link costs and delay penalties,
under possible additional
constraints. Network design and
analysis almost always involve
underdetermined systems,
especially when routing policy has
to be determined. The maximum
entropy method (MEM) is a
relatively new technique for
solving underdetermined systems
which has been successfully
applied in many different areas.
It is intuitively clear that an
optimal network should not have
overloaded or underutilized links.
The maximum entropy constraint
favors uniform distribution and
gives a starting topology and
routing with smoothly distributed
traffic that is expected to be
close to the optimal solution. We
adjusted the network design
problem, primarily the routing
feasibility, to the maximum
entropy method requirements.
Computationally feasible algorithm
is developed which implements the
standard maximum entropy method,
includes adjustments for problems
that do not involve probabilities
initially, calculates a function
that substitutes large sparse
matrix, includes heuristic that
speeds up calculations by avoiding
to invert Jacobian matrix at each
iteration, determines variables
that define constraints for the
routing feasibility, includes
additional constraints that direct
uniformity of the solution in the
desirable direction, cancels
opposing traffic and excludes
underutilized links. Mentioned
additional constraints are “soft”,
which is a unique feature of this
algorithm, in the sense that they
do not have to be satisfied; the
solution will be pulled in the
direction of satisfying them as
much as possible. Some theoretical
results are also established that
direct initial approximation.
Proposed algorithm computes a
reasonable solution that is robust
with respect to often required
dynamic changes of the cost
function. The maximum entropy
solution can be a good starting
point for further optimization
considering that the cost function
may include delay penalties which
involve queuing theory that is
usually computationally expensive.
Brief Biography of the Speaker:
Milan Tuba received B. S. in
Mathematics, M. S. in Mathematics,
M. S. in Computer Science, M. Ph.
in Computer Science, Ph. D. in
Computer Science from University
of Belgrade and New York
University. From 1983 to 1987 he
was a graduate student and
teaching and research assistant at
Vanderbilt University in Nashville
and Courant Institute of
Mathematical Sciences, New York
University. From 1987 to 1993 he
was Assistant Professor of
Electrical Engineering at Cooper
Union Graduate School of
Engineering, New York. During that
time he was the founder and
director of Microprocessor Lab and
VLSI Lab, leader of scientific
projects and supervisor of many
theses. From 1994 he was Associate
professor of Computer Science and
Director of Computer Center at
University of Belgrade, Faculty of
Mathematics, and from 2004 also
Professor of Computer Science and
Dean of the College of Computer
Science, Megatrend University
Belgrade. He was teaching more
than 20 graduate and undergraduate
courses, from VLSI Design and
Computer Architecture to Computer
Networks, Operating Systems, Image
Processing, Calculus and Queuing
Theory. His research interest
includes mathematical, queuing
theory and heuristic optimizations
applied to computer networks,
image processing and combinatorial
problems. He is the author of more
than 70 scientific papers and a
monograph. He is coeditor or
member of the editorial board or
scientific committee of number of
scientific journals and
conferences. Member of the ACM
since 1983, IEEE 1984, AMS 1995,
New York Academy of Sciences 1987.
Participated in many WSEAS
Conferences with plenary lectures
and articles in Proceedings and
Transactions.
