TY - JOUR
T1 - On source-based route computation for quickest paths under dynamic bandwidth constraints
AU - Grimmell, William C.
AU - Rao, Nageswara S.V.
PY - 2003
Y1 - 2003
N2 - Routing in the newer generation of network transmission methods may be performed at various levels of the IP stack such as datagram, TCP stream, and application levels. It is important in the use of these methods to compute the routes that minimize the endtoend delays for the specific routing mechanism. We formulate an abstract network path computation problem, the dynamic quickest path problem, to encompass a number of message forwarding mechanisms including circuit switching, Internet Protocol, and their variations. This problem deals with the transmission of a message from a source to a destination with the minimum endtoend delay over a network with propagation delays and dynamic bandwidth constraints on the links. The available bandwidth for each link is specified as a piecewise constant function. We present for each message forwarding mechanism or mode an algorithm to compute a path with the minimum endtoend delay for a given message size. Our algorithms with suitable network restrictions have polynomial time complexity in the size of the network and total number of segments in the bandwidth list.
AB - Routing in the newer generation of network transmission methods may be performed at various levels of the IP stack such as datagram, TCP stream, and application levels. It is important in the use of these methods to compute the routes that minimize the endtoend delays for the specific routing mechanism. We formulate an abstract network path computation problem, the dynamic quickest path problem, to encompass a number of message forwarding mechanisms including circuit switching, Internet Protocol, and their variations. This problem deals with the transmission of a message from a source to a destination with the minimum endtoend delay over a network with propagation delays and dynamic bandwidth constraints on the links. The available bandwidth for each link is specified as a piecewise constant function. We present for each message forwarding mechanism or mode an algorithm to compute a path with the minimum endtoend delay for a given message size. Our algorithms with suitable network restrictions have polynomial time complexity in the size of the network and total number of segments in the bandwidth list.
KW - Communications protocols
KW - dynamic bandwidths
KW - quickest paths
KW - routing
UR - http://www.scopus.com/inward/record.url?scp=0347615435&partnerID=8YFLogxK
U2 - 10.1142/S0129054103001868
DO - 10.1142/S0129054103001868
M3 - Article
AN - SCOPUS:0347615435
SN - 0129-0541
VL - 14
SP - 503
EP - 523
JO - International Journal of Foundations of Computer Science
JF - International Journal of Foundations of Computer Science
IS - 3
ER -