We present a practical approach to routing and anycasting with near-optimum delays taking into account the processing loads at routers and processing elements of a computer network. To accomplish this, the minimum-delay routing problem formulated by Gallager (1977) is generalized into the problem of minimum-delay routing with load-balancing to account for processing delays in network nodes (servers and routers). Gallager's theorem for necessary and sufficient conditions for minimum-delay routing is modified to include processing delays and changes of traffic levels at network nodes. The first distributed algorithm for load-balanced anycasting and routing in computer networks is presented. This algorithm, named MIDAS, provides approximate solutions to the modified necessary and sufficient conditions for minimum-delay routing. Simulations are use to compare the performance of the new algorithm with the performance of a traditional approach to sever load balancing.

We present a practical approach to internet routing that provides near-minimum delays over multiple loop-free paths to destinations. The new protocol, which we call NEAR-OPT, obtains multiple loop-free paths to destinations using long-term delay measures, and allocates destination-oriented flows over such paths using short-term delay measures to minimize delay. We compare the performance of NEAR-OPT with traditional single-path routing and the only known adaptation for dynamic networks of Gallager's minimum-delay routing algorithm. Using actual Internet traffic traces and other traffic source models, we show that NEAR-OPT provides delays comparable to the lower bounds achievable with Gallager's algorithm for static networks, provides lower delays than implementations of Gallager's algorithm in networks subject to fractal traffic, and renders far smaller delays and better use of resources than traditional single-path routing. NEAR-OPT does not depend on any global constant and is completely distributed, making it easy to implement as a loop-free distance-vector protocol similar to Cisco's EIGRP.

A new distributed algorithm for the dynamic computation of multiple loop-free paths from source to destination in a computer network or Internet are presented, validated, and analyzed. According to this algorithm, which is called DASM (diffusing algorithm for shortest multipath), each router maintains a set of entries for each destination in its routing table, and each such entry consists of a set of tuples specifying the next router and distance in a loop-free path to the destination. DASM guarantees instantaneous loop freedom of multipath routing tables by means of a generalization of Dijkstra and Scholten's diffusing computations. With generalized diffusing computations, a node in a directed acyclic graph (DAG) defined for a given destination has multiple next nodes in the DAG and is able to modify the DAG without creating a directed loop. DASM is shown to be loop-free at every instant, and its average performance is analyzed by simulation and compared against an ideal link-state algorithm and the diffusing update algorithm (DUAL).

The diffusing update algorithms (DUAL) constitute a family of distributed routing algorithms that has been shown to be loop-free at every instant, to converge after an arbitrary sequence of link-cost or topological changes, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities. Two hierarchical routing schemes based on DUAL are presented to make it more applicable to very large internets. A scheme based on McQuillan's (1974, 1980) hierarchical routing scheme and a backbone-oriented scheme, similar to the one used in OSPF, are introduced to reduce the amount of routing information maintained at each router. The performance of these schemes is compared by simulation to the performance of the basic DUAL, an ideal routing algorithm based on topology broadcast, and OSPF. The simulation results suggest that DUAL with areas outperforms OSPF, and provide additional insight on the performance of OSPF, EIGRP, and area-based routing algorithms in general.>

The dynamics of shortest-path routing algorithms bss.ed on distance vectors and link states are investigated.Detailed quantitative comparisons of the distributed Belhnen-Ford algorithm used in several routing protocols in the paa~an ideal link-state ttlgonthm similar to the one used in OSPF and in the 0S1 intradomain routing protocol, and a loop-free distance-vector algorithm, are made for the network topologies of the 1988 ARPANET, LOS-NE'ITOS, DOE-ESNET, and the NSFNET T1 Backbone.Comparisons include the response of the algorithms to link-cost changes and to link end node failures and recoveries.A variety of quantities, including the length of messages and the average nutnber of paths affected by routing lceps, are computed as a function of time after a link or node change.Probabilities of various conditions are also obtained as a function of time, including the existence of loops.As expected, the dwtributed Belhnen-Ford algorithm behaves poorly compared with the other two.However, deciding between a routing protocol based on a link-state algorithm and one based on a loop-free d~tance-vector algorithm depends on the particular network in which it will perform.

We have derived a new lower bound on intermodulation noise. This bound agrees with Maxenchuck and Schiff's bound for carrier plans with low IM noise, but gives significantly higher values as one approaches uniformly spaced plans. The bound is valid for carriers when carrier frequencies are chosen from a set of evenly spaced slots that are spaced by at least the bandwidth of each individual carrier. All carrier amplitudes are assumed to be identical.