On The Optimal Monitor Placement For Inferring Additive Metrics Of Interested Paths

Authors:
Rongwei Yang University of Science and Technology of China & City University of Hong Kong, P.R. China
Cuiying Feng University of Victoria, Canada
Luning Wang City University of Hong Kong, Hong Kong
Weiwei Wu Southeast University, P.R. China
Kui Wu University of Victoria, Canada
Jianping Wang City University of Hong Kong, Hong Kong
Yinlong Xu University of Science and Technology of China, P.R. China

Abstract:

In the "network-as-a-service" paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. We show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

You may want to know: