A distributed routing algorithm for virtual circuit date networks

Author

Lin, Yeong-Sung ; Yee, J.R.

Author_Institution

Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA

fYear

1989

fDate

23-27 Apr 1989

Firstpage

200

Abstract

In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. The problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network is considered here. The usual formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables is considered. A distributed algorithm is developed to solve the optimization problem, using Lagrangean relaxation as the basic approach. A multiplier update technique is developed which facilitates the solution of the nonlinear integer programming problem using distributed computation

Keywords

computer networks; data communication systems; nonlinear programming; packet switching; Lagrangean relaxation; distributed routing algorithm; integer decision variables; multiplier update technique; nonlinear integer programming; nonlinear multicommodity flow; optimization problem; origin-destination pair; virtual circuit date networks; Communication networks; Computer network reliability; Computer networks; Distributed algorithms; Distributed computing; Lagrangian functions; Military computing; Packet switching; Routing; Switching circuits;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM '89. Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies. Technology: Emerging or Converging, IEEE

Conference_Location

Ottawa, Ont.

Print_ISBN

0-8186-1920-1

Type

conf

DOI

10.1109/INFCOM.1989.101453

Filename

101453