An entropy-constrained algorithm for routing of communication networks

This paper introduces an entropy-constrained algorithm for routing of communication networks. The proposed formulation of the routing problem allows multiple nodes to compete for each position in the route, with the associated uncertainty measured by the connection entropy. The problem of determining the best route is subsequently formulated as the constrained minimization of an objective function formed as a linear combination of the routing cost and the corresponding connection entropy. The routing algorithm derived using the method of Lagrange multipliers is implemented by a deterministic annealing optimization process, with the number of accessible system states decreasing gradually with the system temperature. For comparison purposes, routing is also performed by an optimization approach similar with that proposed by Hopfield and Tank and by the routron, which was developed using elements of the Hopfield–Tank approach to optimization but relies on a different treatment of the optimization problem. This experimental study reveals the superiority of the entropy-constrained routing algorithm, which produces consistently the best routes in a small fraction of the time required for convergence by the neural optimization approaches.