Abstract: Network design problem is a well known NP-hard 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.