We present, prove correctness for, and evaluate a protocol for the reliable broadcast of topology and link-state information in a multihop communication network with a dynamic topology, such as a wireless network with mobile nodes. The protocol is called topology broadcast based on reverse path forwarding (TBRPF), and uses the concept of reverse-path forwarding (RPF) to broadcast link-state updates in the reverse direction along the spanning tree formed by the minimum-hop paths from all nodes to the source of the update TBRPF uses the topology information received along the broadcast trees to compute the minimum-hop paths that form the trees themselves, and is the first topology broadcast protocol based on RPF with this property. The use of minimum-hop trees instead of shortest-path trees (based on link costs) results in less frequent changes to the broadcast trees and therefore less communication cost to maintain the trees. Simulations show that TBRPF achieves up to a 98% reduction in communication cost compared to flooding in a 20-node network.

We present and evaluate new techniques for call admission control (in ATM networks) based on neural networks. The methods are applicable to very general models that allow heterogeneous traffic sources and finite buffers. A feedforward neural network (NN) is used to predict whether or not accepting a requested new call would result in a feasible aggregate scream, i.e., one that satisfies the QOS requirements. The NN input vector is a traffic descriptor for the aggregate stream that has the following beneficial properties: its dimension is independent of the number of traffic classes; and it is additive, allowing it to be updated efficiently by simply adding the traffic descriptor of the new call. A novel asymmetric error function for the NN helps achieve our asymmetric objective in which rejecting an infeasible stream is more important than accepting a feasible one. We present a NN design that provides an optimal linear compression of the NN inputs to a smaller number of traffic parameters. The special case of one compressed parameter corresponds to an NN version of the equivalent bandwidth. Experiments show our methods to be better than methods based on the equivalent bandwidth, with respect to call blocking probability and the percentage of feasible streams that an correctly classified.

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.

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.>

A distributed asynchronous algorithm is presented for finding two disjoint paths of minimum total length from each possible source node to a destination. The algorithm has both node-disjoint and link-disjoint versions, and provides each node with information sufficient to make incremental routing decisions for forwarding packets over the disjoint paths. For a network in which all links have unit length, it is shown that a synchronous implementation of the algorithm has communication and time complexities O( mod E mod +D mod N mod ) and O(D/sub 2/), respectively, where D is the networks diameter and D/sub 2/ is the maximum, over all nodes i, of the total number of links in the shortest pair of disjoint paths from i to the destination.>

Abstract A single‐source single‐sink dynamic network is considered where the link flows are real‐valued measurable functions defined on a time interval and where storage is allowed at the nodes. Piecewise‐constant link and storage capacities are given. A τ‐maximum flow is a dynamic flow assignment that maximizes the total amount of commodity reaching the sink before time τ. The problem considered is that of computing a flow which is simultaneously τ‐maximum for all τ. Such a flow solves a minimum‐delay dynamic routing problem. An algorithm is presented which computes an optimal flow in O ( | N | 4 T 4 ) time, where | N | is the number of nodes and T is the number of times that the capacities change. Previous polynomial‐time algorithms have been given only for the case of constant capacities.

Abstract New characterizations of optimal state‐dependent routing strategies are obtained for the continuous traffic network model proposed by Segall for linear cost with unity weighting at each node and for constant inputs. The concept of flow relaxation is introduced and is used t o transform the optimal routing problem into an initial flow optimization problem with convex cost and linear constraints. Three algorithms are given for open‐loop computation of the optimal initial flow. The first is a simple iterative algorithm based on gradient descent with bending and it is well suited for decentralized computation. The second algorithm reduces the problem t o a series of max‐flow problems and it computes the exact optimal initial flow in O(lN14) compu‐ tations, where IN1 is the number of nodes in the network. The third algorithm is based on a search for successive bottlenecks in the network.

In an earlier paper, recursive formulas for the causal filtering of two-dimensional random fields were developed. "Causality" in two dimensions is not a physical constraint but rather an artifact introduced to generate recursion, which in turn is motivated by computational efficiency. The earlier results are extended here in order to derive some recursive formulas for "smoothing" estimators which use all the data rather than just the data in the "past".