A computationally efficient iterative solution of the multidestination optimal dynamic routing problem

 
see the original item page
in the repository's web site and access all digital files if the item*
share




1991 (EN)
A computationally efficient iterative solution of the multidestination optimal dynamic routing problem (EN)

Kazantzakis, MG (EN)
Stassinopoulos, GI (EN)

N/A (EN)

The dynamic routing problem for multiple destination networks is considered. The minimum time rather than total delay cost functional is employed. The problem is solved through an iterative link-by-link optimization. Each link capacity is optimally partitioned by examining the upper bounds for the evacuation time imposed through different capacity allocations for each origin/destination pair traffic. The computational complexity per iteration is polynomial in the number of network nodes. This is due to the examination of origin/destination pairs rather then destinations alone as in previous work where a similar approach led to exponential complexity. Sufficient conditions for the convergence of the iterative algorithm to the optimum are given. If these are not satisfied supplementary steps are described which conduct the algorithm to the desired solution. These involve exponential computational complexity. (EN)

journalArticle

Capacity Allocation (EN)
Dynamic Routing (EN)
Computer Software MULTDEST (EN)
Cost Function (EN)
Mathematical Techniques - Iterative Methods (EN)
Telecommunication (EN)
Iterative Algorithm (EN)
Multidestination Dynamic Routing (EN)
Optimization (EN)
Upper Bound (EN)
Mathematical Techniques - Differential Equations (EN)
Origin Destination (EN)
Optimal Dynamic Routing (EN)
Iterative Solution (EN)
Satisfiability (EN)
Mathematical Programming, Linear (EN)
Computational Complexity (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

IEEE Transactions on Communications (EN)

English

1991


IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC (EN)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)