Mathematical Models for Quality of Service Driven Routing in Networks

摘要

Very large networks with varying topologies, unreliable components, and highly time varying traffic, are not amenable to traditional techniques of analysis based on traffic engineering and simulations. Traffic flows in such networks will traverse a number of hops which cannot be determined in advance and encounter traffic conditions that are also unknown. During the flow of a particular traffic stream, the network topology may change (e.g., when wireless links are numerous) and other critical conditions (such as network security) may vary. We address the control of traffic flows in such networks with the objective of meeting the needs of the military end user. Novel results obtained in this research include distributed sensible network techniques that provide a hierarchy of provably better flow control algorithms that apply to any specific QoS metric of interest, and estimates for search times of destinations in highly unknown random environments. We prove the existence and uniqueness of solutions of the non-linear equations for the computation of QoS in the presence of sensible decision algorithms. In addition, we compute the average travel time of a packet that is routed in a random environment, with and without time-outs for packet re-transmission when the packet is lost.