We present a new hierarchical routing algorithm that combines the loop-free path-finding algorithm (LPA) with the area-based hierarchical routing scheme first proposed by McQuillan (1974) for distance-vector algorithms. The new algorithm, which we call the hierarchical information path-based routing (HIPR) agorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra's algorithm running over a hierarchical graph. The HIPR is verified to be loop-free and correct. Simulations are used to show that the HIPR is much more efficient than the OSPF in terms of speed, communication and processing overhead required to converge to correct routing tables. The HIPR constitutes the basis for future Internet routing protocols that are as simple as RIPv2, but with no looping and better performance than protocols based on link-states.

We analyze the security requirements of distance-vector routing protocols, identify their vulnerabilities, and propose countermeasures to these vulnerabilities. The innovation we propose involves the use of mechanisms from the path-finding class of distance-vector protocols as a solution to the security problems of distance-vector protocols. The result is a proposal that effectively and efficiently secures distance-vector protocols in constant space.

A loop-free path-finding algorithm (LPA) is presented; this is the first routing algorithm that eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops of the specification of complete or variable-size path information. Like other previous algorithms, the LPA operates by specifying the second-to-last hop and distance to each destination; this feature is used to ensure termination. In addition, the LPA uses an interneighbor synchronization mechanism to eliminate temporary routing loops. A detailed proof of the LPAs correctness and loop-freedom property is presented and its complexity is evaluated. The LPAs average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state (ILS) algorithm, a loop-free algorithm that is based on internodal coordination spanning multiple hops (DUAL) and a path-finding algorithm without the interneighbor synchronization mechanism. The simulation results show that the LPA is a more scalable alternative than DUAL and ILS in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change.

We present a framework for the modeling of multipath routing in connectionless networks that dynamically adapt to network congestion. The basic routing protocol uses a short-term metric based on hop-by-hop credits to reduce congestion over a given link, and a long-term metric based on end-to-end path delay to reduce delays from a source to a given destination. A worst-case bound on the end-to-end path delay is derived under three architectural assumptions: each router adopts weighted fair queueing (or packetized generalized processor sharing) service discipline on a per destination basis, a permit-bucket filter is used at each router to regulate traffic flow on a per destination basis, and all paths are loop free. The shortest multipath routing protocol regulates the parameters of the destination-oriented permit buckets and guarantees that all portions of a multipath are loop free.

The authors present a new distance-vector routing protocol for a packet radio network. The new distributed routing protocol, Wireless Routing Protocol (WRP), works on the notion of second-to-last hop node to a destination. WRP reduces the number of cases in which a temporary routing loop can occur and also provides a mechanism for the reliable transmission of update messages. The performance of WRP has been compared quantitatively by simulations with that of distributed Bellman-Ford (DBF), DUAL (a loop-free, distance-vector algorithm), and an ideal link-state algorithm (ILS) that represents the state of the art of Internet routing in a highly dynamic environment. The simulation results indicate that WRP is the most efficient of the algorithms simulated in a wireless environment.

A method is presented to improve the performance of the High-Performance Switching System (HPSS), a distributed switching system being designed for use in the campus-wide high-speed network prototype at the Lawrence Livermore National Laboratory. The HPSS uses protocols of the proposed ANSI Fibre Channel Standard (FCS). The system is based on a folded version of the Clos three-stage network, and its largest configuration has 4096 ports, each operating at 1.0625 Gb/s. The authors' approach improves the connection-setup time in the HPSS by queuing connection requests at destination ports, thus reducing the overhead associated with retries due to port-busy conditions. Results from a detailed simulation of the HPSS are presented to show the performance improvement for different traffic distributions and operating parameters.