Achieving timely message delivery quality-of-service in fixed and variable connectivity distributed routing networks

Variable connectivity distributed routing networks (VCDRNs) are networks designed with the goal of reliably delivering message traffic even when network connectivity (both routing node to routing node and subscriber to routing node) is continuously and unpredictably changing. A general-purpose point-to-point VCDRN which provides optimum (fewest hop) connectivity in a fixed network and adapts as network topology changes so as to automatically reroute traffic is presented. The routing algorithm includes the multimedia, multidata rate, multierror rate case. It is shown how to design the network to offer a quality-of-service (QoS) in terms of a numerical probability of successful message delivery in a specified time or to adjust the network to provide a users desired QoS on single and multihop paths. This is an important feature to users who want rapid message delivery, even as network topology changes. The case of multiple message priorities is also included. Routing knowledge is distributed by adding path and error rate information to packets as they traverse the network, without adversely impacting QoS. This methodology applies to all routing protocols that employ selective reject retransmission error control. The methodology also presents a means for comparing the performance of candidate protocols in terms of parameters meaningful to the user. While the methods presented herein are applicable to any network they are of particular value to the wireless network with limited bandwidth, high error rates, and variable connectivity, where the user wants message traffic to be delivered as fast as possible in that environment with some prior assurance as to the speed and certainty of delivery.