The authors consider the problem of finding a routing strategy that minimizes the worst-case expected delay from every source to a single destination in an unreliable network, given a constraint on the number of outgoing links at each node that can be inoperational at any point in time. Subject to this constraint, links can fail and recover arbitrarily often. A node having a packet to forward must choose a single link on which to transmit the packet, but does not know in advance which links will be inoperational during the transmission. If a transmission fails, the packet is retransmitted (not necessarily on the same link) after some fixed amount of time. It is shown that the optimal routing strategy is a stationary randomized strategy in which each node selects the forwarding link according to a fixed probability distribution. An efficient algorithm that computes an epsilon -optimal solution in O( mod E mod log( mod V mod / epsilon )) time, for any positive number epsilon , is presented.>

Link-state updating in communication networks undergoing topological changes is addressed. It is concluded that the best way of disseminating link-state information is through event-driven (ED) updating, and it is shown how to overcome the traditional drawbacks of ED updating. An efficient algorithm that extracts the maximum implicit information from ED topology updates by computing the latest time for which each processing node can be certain of the state of each network link is given. It is shown that the information obtained is equivalent to that obtained by continuous flooding of link-state information. A method that allows each node to refresh the above information continuously without running the algorithm more than once for each received update is presented, as is an approximate version of the algorithm that reduces communication overhead by limiting the radii of propagation.>

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied.>

The authors consider the problem of finding a routing strategy that minimizes the expected delay from every source to a single destination in a network in which each link fails and recovers according to a Markov chain. It is assumed that each node knows the current state of its own outgoing links and the state-transition probabilities for every link of the network. It is shown that the general problem is #P-complete, and two special cases are considered: case 1 assumes the network is a directed acyclic graph oriented toward the destination, and case 2 assumes that the link states are independent from slot to slot. For each case, it is proved that the optimal routing strategy has a simple state-independent representation. An efficient algorithm is presented for finding the optimal strategy.

Distributed algorithms are presented for finding two maximally disjoint paths of minimum total length from each possible source node to a destination, including both node-disjoint and link-disjoint versions of the algorithm. A synchronous algorithm having communication complexity O( mod E mod log D+ mod mod V mod D) and time complexity O( mod V mod W), where mod V mod and mod E mod denote the number of nodes and links in G, W is the maximum link length, and D is the depth of a shortest-path spanning tree directed toward the destination, is presented. For the important case W=O(1), the time complexity becomes O( mod V mod ). In this case, the asynchronous algorithm obtained by applying Synchronizer alpha of B. Awerbuch (1987) has communication complexity O( mod E mod V mod ) and time complexity O( mod V mod ). Serial, centralized versions of the algorithms with time complexity O( mod E mod + mod V mod log mod V mod ) and space complexity O( mod E mod ) are also presented.>

An economics-based definition of fair pricing is proposed, and fair, simple, and mathematically sound charging policies are derived that properly handle costs and risks in lossy internetworks. Also described are simple and efficient source-based algorithms (having both link-state and distance-vector versions) for computing the optimal routing tables with respect to the new charging measures. These charging measures and algorithms have the property that, by minimizing the individual domain's expenses, they also minimize the global resource consumption. In addition, a distributed destination-based algorithm is presented for computing optimal paths that allows for faster response time in highly dynamic and unreliable internets. Finally, preliminary accounting procedures are presented for implementing the proposed charging policies.>