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.