Premium
A routing algorithm for virtual circuit data networks with multiple sessions per O—D pair
Author(s) -
Yee James R.,
Lin Frank Y. S.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220205
Subject(s) - heuristics , computer science , mathematical optimization , relaxation (psychology) , network packet , routing (electronic design automation) , heuristic , path (computing) , algorithm , mathematics , psychology , social psychology , computer network , programming language
In virtual circuit networks, all the packets in a session are transmitted over exactly one path established between the origin and the destination. For each origin–destination pair, it is assumed that there are multiple sessions. We consider the problem of choosing a path for each session so as to minimize the average packet delay in the network. We formulate this problem as a nonlinear multicommodity flow problem with integer decision variables. An iterative scheme that is similar to local search is developed to solve this problem. In each iteration, we apply Lagrangean relaxation and a multiplier adjustment procedure to solve a restricted problem. We show that the Lagrangean dual problem can be solved exactly by solving a convex program. In computational experiments, our algorithm determines solutions that are within 1% of an optimal solution in minutes of CPU time for networks with 26–61 nodes. In addition, we show that our proposed algorithm is better both theoretically and computationally than K(0)‐ordering, single‐path routing, or round‐off Frank–Wolfe heuristics.