The virtual network algorithm
Christopher Philip Ferguson, Leonard Kleinrock · 1999
This thesis describes the Virtual Network Algorithm, which is a communications protocol for the Wireless Adaptive Mobile Information System (WAMIS) project. It is an algorithm for adjusting the transmission powers and code assignments for a large number of mobile hand-held spread spectrum radios operating in a multihop environment. This protocol allows the creation of an “instant infrastructure” over which the radios may communicate, and also facilitates well-structured multihop communication of voice, video, and data between the radios by creating a communications environment similar to a wired network. Thus, standard routing, virtual circuit, admission control and congestion control algorithms can be used. The resulting radio network provides services similar to a cellular telephone environment, but adds both data and video capabilities. Furthermore, it can be instantly deployed without the use of ground links or base stations and is scalable to hundreds of radios. We present the algorithm and give several proofs of its effectiveness. We examine a number of routing algorithms and present a proof that finding routes in this environment is an NP-complete problem. We then look at the problem of setting up virtual circuits, propose a new approach which is shown to be deadlock free, and compare it to a conventional approach and a more ideal system. We also look at the general problem of determining when to update out-of-date information, and show how it applies to the Virtual Network environment itself, where topology and routing information require periodic updating, We present a methodology for determining optimal update times for a simple case. We also solve a case where there are delays associated with sending a request and receiving an update back, a case where the user is mobile and has a changing cost of obtaining an update, and a case where there is no explicit cost of an update, but the information cannot be used while it is being updated.