Toward Verifiable Services: Bound-Oriented Network Tomography

Network tomography has been an important research direction in the past decade.Roughly speaking, network tomography is to infer certain network performance that isdifficult or too costly, to be measured directly. The inference is derived based on alimited number of measurements that are partially or indirectly related to the target tobe inferred. In the past, people have studied network tomography for different purposes,such as inferring network topology and delay of links.In this project, we study a class of new network tomography problems, referred to asbound-oriented network tomography. The problems are particularly relevant to ISPs whoneed to continuously invigilate the status of network resources important to theiroperations, for example, when the ISPs are providing verifiable services to their clients.Effective and efficient network tomography is a basic problem faced by them.Concerning the need from ISPs, our problems have two important features that havebeen overlooked in the past. First, we focus on inferring performance bounds ratherthan the absolute values. The bound-oriented inference is consistent with the fact thatthe SLA terms between ISPs and their clients are commonly written in terms ofperformance bounds. Second, for each path to be inferred, we directly infer theperformance bounds of the path without always explicitly obtaining the performance ofeach link on the path. Knowing path performance is enough to ISPs because theirservice levels to clients depend on paths directly. These two features lead to new modelsthat are less restrictive and enable low-cost solutions.Regarding the plan and methodologies, we propose three concrete tasks, inferring delaybounds, inferring bandwidth bounds, and inference by network calculus. Among thethree, the first two are independent, both needing some measured bounds as input. Thethird task will provide valid input to the first two tasks; at the same time, the third taskwill also infer more information by a new concept termed as service curve decomposition.Successfully doing service curve decomposition will expand the applicable area ofnetwork calculus, making it a powerful tool for network tomography.In summary, we propose a framework for bound-oriented network tomography, whichcan be used for ISPs to fast gain network knowledge at low cost.?