MARC 主機 00000nam  2200397   4500 
001    AAI3359300 
005    20100629105602.5 
008    100629s2009    ||||||||||||||||| ||eng d 
020    9781109199130 
035    (UMI)AAI3359300 
040    UMI|cUMI 
100 1  Purkayastha, Punyaslok 
245 10 Multipath routing algorithms for communication networks: 
       Ant routing and optimization based approaches 
300    131 p 
500    Source: Dissertation Abstracts International, Volume: 70-
       06, Section: B, page: 3698 
500    Adviser: John S. Baras 
502    Thesis (Ph.D.)--University of Maryland, College Park, 2009
520    In this dissertation, we study two algorithms that 
       accomplish multipath routing in communication networks. 
       The first algorithm that we consider belongs to the class 
       of Ant-Based Routing Algorithms (ARA) that have been 
       inspired by experimental observations of ant colonies. It 
       was found that ant colonies are able to 'discover' the 
       shorter of two paths to a food source by laying and 
       following 'pheromone' trails. ARA algorithms proposed for 
       communication networks employ probe packets called ant 
       packets (analogues of ants) to collect measurements of 
       various quantities (related to routing performance) like 
       path delays. Using these measurements, analogues of 
       pheromone trails are created, which then influence the 
       routing tables 
520    We study an ARA algorithm, proposed earlier by Bean and 
       Costa, consisting of a delay estimation scheme and a 
       routing probability update scheme, that updates routing 
       probabilities based on the delay estimates. We first 
       consider a simple scenario where data traffic entering a 
       source node has to be routed to a destination node, with N
       available parallel paths between them. An ant stream also 
       arrives at the source and samples path delays  en route to
       the destination. We consider a stochastic model for the 
       arrival processes and packet lengths of the streams, and a
       queueing model for the link delays. Using stochastic 
       approximation methods, we show that the evolution of the 
       link delay estimates can be closely tracked by a 
       deterministic ODE (Ordinary Differential Equation) system.
       A study of the equilibrium points of the ODE enables us to
       obtain the equilibrium routing probabilities and the path 
       delays. We then consider a network case, where multiple 
       input traffic streams arriving at various sources have to 
       be routed to a single destination. For both the N parallel
       paths network as well as for the general network, the 
       vector of equilibrium routing probabilities satisfies a 
       fixed point equation. We present various supporting 
       simulation results 
520    The second routing algorithm that we consider is based on 
       an optimization approach to the routing problem. We 
       consider a problem where multiple traffic streams entering
       at various source nodes have to be routed to their 
       destinations via a network of links. We cast the problem 
       in a multicommodity network flow optimization framework. 
       Our cost function, which is a function of the individual 
       link delays, is a measure of congestion in the network. 
       Our approach is to consider the dual optimization problem,
       and using dual decomposition techniques we provide primal-
       dual algorithms that converge to the optimal routing 
       solution. A classical interpretation of the Lagrange 
       multipliers (drawing an analogy with electrical networks) 
       is as 'potential differences' across the links. The link 
       potential difference can be then thought of as 'driving 
       the flow through the link'. Using the relationships 
       between the link potential differences and the flows, we 
       show that our algorithm converges to a loop-free routing 
       solution. We then incorporate in our framework a rate 
       control problem and address a joint rate control and 
       routing problem 
590    School code: 0117 
650  4 Engineering, Electronics and Electrical 
650  4 Computer Science 
690    0544 
690    0984 
710 2  University of Maryland, College Park.|bElectrical 
773 0  |tDissertation Abstracts International|g70-06B 
856 40 |u