Plenary Lecture
Relation between Static and Dynamic Optimization in Computer Network
Routing
Professor Milan Tuba
Megatrend University Belgrade
Faculty of Computer Science
Serbia
Email: tuba@ieee.org
Abstract: Computer network routing is a very important and interesting
optimization problem. Many different routing algorithms have been used over
the years on the Internet, often with unexpected problems.
Dynamic systems, i.e. systems that change over time, can be optimized
statically with a fixed solution that corresponds to some average system
state, or dynamically where the solution tries to follow the system change
over time. It is a normal expectation that dynamic optimization has to give
better results than a static one. Dynamic optimization is more complex,
requires more computation, more advanced methods, but is superior to static
optimization because it can always be transformed to the static case simply by
neglecting change of the system in time and selecting a single state as a
representative. However, that expectation that dynamic optimization gives
better results than static one applies only to the perfect dynamic
optimization, which is impossible in practice. It takes some time to collect
information about the system current state, and optimization is always done
with that obsolete information. This situation is examined on computer network
routing.
By complete mathematical analysis of a simple network, we show that dynamic
routing gives better results than static, as expected, but that the margin is
much smaller then intuitively expected. Further analysis shows that that minor
advantage can easily be lost if there is even a small error in the dynamic
routing tables, and actually dynamic routing can easily become worse than
static. It takes time to collect information about network traffic . By the
time routing tables are calculated, they are already obsolete; they are about
some previous condition on the network, not the current one. Quantitative
analysis shows that delays in building routing tables can affect dynamic
routing performance unexpectedly strongly. This leads to the qualitative
recommendation: "Trying to optimize too hard will make things worse. Dynamic
routing should not try to adapt to traffic changes very fast." This hypothesis
is accepted today and implemented in routing algorithms.
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 about 20 graduate and undergraduate
courses, from VLSI Design and Computer Architecture to Computer Networks,
Image Processing, Calculus and Queuing Theory. His research interest include
mathematical, queuing theory and algorithmic optimizations applied in computer
networks, image processing and combinatorial problems. He is the author of
more than 60 scientific papers and a monograph. He was coeditor or member of
the board of editors of number of scientific journals and conferences. Member
ACM 1983, IEEE 1984, AMS 1995, New York Academy of Sciences 1987.
