Failsafe Distributed Optimal Routing in Data-Communication Networks,
Abstract
Iterative protocols for adaptive routing in line and message switched data communication networks are presented in this thesis. Distributed computation is used in the sense that each node in the network bases all its decisions on control messages received only from its neighbors. Thus, each node in the network determines individually onto which of its outgoing links to send the flow, addressed to a specific destination. The control messages exchanged between neighbors contain information about network connectivity, network congestion and link failures. Loop-free routing for each destination is maintained in the network at all times. Generally, prevention of loops results in saving resources and reduction in delay. In addition, loop-free routing establishes a partial ordering on the set of nodes of the network. The latter property is extensively utilized throughout this work. failsafe and deadlock-free operation of the protocols is guaranteed, meaning that after arbitrary failures and additions of links and nodes, the network recovers in finite time. Recovery means that routing paths are provided between all connected nodes. For stationary input traffic statistics and fixed topology the protocols are optimal. they reduce network delay at each iteration and minimum average delay over all routing assignments is obtained in steady-state.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1979
- Accession Number
- ADA068138
Entities
People
- A. Segall
- M. Sidi
Organizations
- Massachusetts Institute of Technology