CIF:Small:Network Tomography and Resource Allocation

George Mason University, Fairfax VA

Investigators

Abstract

Part 1. Communication networks, including the Internet and cellular networks, provide an infrastructure for information and data exchange that is critical to modern society. As networks have increased in size and complexity to meet the growing demands of users and new multimedia applications, they have also become more difficult to manage. Consequently, evaluating the performance of a network and allocating resources to improve performance are extremely challenging tasks. This project will develop an approach to evaluate the performance of a network through endpoint traffic measurements and by sending probe packets through the network. This approach is referred to as network tomography, since the concept is similar to medical tomography, whereby an image of an organ is reconstructed through virtual sectioning using some form of penetrating wave, e.g., X-rays or ultrasound. Current methods for network tomography do not scale well with the size of the network and cannot provide estimates of network performance in real-time. The project will investigate new methods that will be capable of evaluating the performance of large networks in real-time through endpoint measurements and statistical analysis. This information will in turn be used to allocate resources within the network in order to enhance network performance. The ultimate goal of the project is to develop a framework, based on new methodologies for network tomography, to alleviate congestion and service degradation in communication networks such as the Internet, data storage networks, future cellular networks, as well as transportation networks. The project will advance the field of networking via the development of real-time and scalable methods for network tomography and resource allocation, which will impact society through significant improvements in the performance, efficiency, and reliability of communication and transportation networks. The project will also involve the development of an educational software tool to simulate and graphically depict the operation of a network, with knobs to allow the user to control the allocation of network resources and visualize the effect of such allocations on network performance. Students, including some from underrepresented groups, will gain valuable experience from implementing algorithms, running computer simulations, and conducting empirical validation with real data from the Internet and cellular networks. Part 2: Performance evaluation and resource allocation of communication networks are extremely challenging tasks due to the tremendous scale and complexity of modern networks. Traditional approaches to network performance evaluation include queueing theory and computer simulation. In this project, a framework for network tomography of both traffic rate and delay on network links from endpoint traffic measurements, will be developed and investigated, with application to network resource allocation. Gallager's model for minimum delay routing in a network will be used to formulate the joint problem of traffic rate and delay estimation, and derive information that can be applied directly to resource allocation. A new approach to traffic rate tomography, which has the potential to improve upon the accuracy, computational efficiency, and generality of earlier methodologies will be explored. A recent approach to delay network tomography based on parameter estimation of a partially observable bivariate Markov chain model will be further developed in the context of the proposed framework. A major focus of the project will be on developing efficient online algorithms for network tomography and resource allocation that can be applied to improve network performance in near real-time. The proposed investigations are grounded in the theory and estimation of multivariate Markov processes, and explore the interplay between the existing theories of queueing networks and statistical inference. The research will involve the development of new models for network tomography, recursive estimation algorithms, and empirical validation. The proposed research will be applicable to the performance evaluation of a wide range of networks, including computer networks, cellular networks, and transportation networks. The research will contribute to new mechanisms to improve the quality-of-service and quality-of experience for users of the Internet and next generation wireless infrastructure. The proposed approach to network tomography will also help optimize the planning of transportation systems.