Access Restriction

Author Agnew, Carson E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Alternate routing ♦ Adaptive routing ♦ Quadratic routing ♦ Distributed network ♦ Computer network ♦ Store-and-forward network ♦ Message switching ♦ Routing ♦ Routing algorithms
Abstract Two analytic models of a store-and-forward communications network are constructed, one to find the optimal message routing and the other to illustrate the equilibrium (stationary state) maintained by an adaptive routing algorithm. These models show that adaptive routing does not satisfy the necessary conditions for an optimal routing. Adaptive routing tends to overuse the direct path and underuse alternate routes because it does not consider the impact of its current routing decision on the future state of the network. The form of the optimality conditions suggests that a modification of the adaptive algorithm will result in optimality. The modification requires the substitution of a quadratic bias term instead of a linear one in the routing table maintained at each network node. Simulation results are presented which confirm the theoretical analysis for a simple network.
Description Affiliation: Mathematica, Inc., Princeton, NJ (Agnew, Carson E.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 19
Issue Number 1
Page Count 5
Starting Page 18
Ending Page 22

Open content in new tab

   Open content in new tab
Source: ACM Digital Library