Research On Network Performance Monitoring For Interested Paths

Network tomography,which indirectly infers various network performance met-rics through a small number of path measurements,is an important research area in the past decade.With 5G around the corner,the future Internet is expected to evolve from"one-size-fits-all" paradigm toward "network-as-a-service" paradigm where a variety of applications,services,and devices can be supported with performance guarantees.The performance guarantee requirement in the future Internet makes it compulsory for network service providers to know the metrics of the critical paths running services to their users/tenants.In the literature,most research in network tomography has focused on inferring the performance of all paths,all links,or a subset of links in a network through a small number of monitoring nodes.A missing piece in this line of research is how to infer the performance of a set of interested paths,instead of all paths,in a network through a small number of monitoring nodes.This missing piece is not only theoretical important to complete the research in this area,but also important in practice,since a network service provider may only concern the performance of a set of critical paths to avoid the SLA violation.In this thesis,we aim to solve this missing piece in network tomography.To this end,we study the following three problems and provide optimal solutions to each of them.The first problem is to determine whether a path is identifiable or not with given monitors.The work in the literature addresses how to infer the performance of all paths,all links,or a set of links in a network with given monitors.All such work starts with link identifiability.Our work differs from the literature work as it is not necessary to identify every link in order to identify a set of paths.We develop an efficient method to determine the identifiability of a path with at least two monitors.To solve this problem,we first convert the path identifiability problem in a network with more than two monitors to an equivalent problem that determines the path identifiability in an extended graph with only two monitors.And the extended graph can be partitioned into some subnetwork with the same structure.We then study the link identifiability in each subnetwork.At last,we answer whether a path is identifiable or not under different cases.The second problem is to determine the smallest number of monitors and the posi-tions to place such monitors so that a set of interest paths are identifiable.We develop an optimal algorithm to minimize the number of extra monitors needed in order to identify a set of interested paths in a graph.And then an optimal monitor placement algorithm is developed to identify all interested paths without any given monitors.Experiments show a saving of up to 40%fewer monitors that guarantee the identifiability of a given set of paths.The last problem is to construct the measurement paths for obtaining the metrics with a partial monitor placement.Existing work cannot be used for solving this prob-lem,since they require the completely monitor placement that all links are identifiable with given monitors,such that a set of pairwise independent spanning trees can be con-structed.In this thesis,we develop an efficient algorithm of constructing measurement paths for an identifiable link with a partial monitor placement.And we also provide the methods of measurement path construction for a cross-link or shortcut in a 3-vertex-connected graph.The solutions of the aforementioned three problems form a complete solution to the missing piece in network tomography.They can be used together for the network service providers to determine the optimal monitor placement.They can also be used separately.For example,when a new path is added to the interest path set,the network service provider can make use of the solution of the first problem to determine whether the path is identifiable or not,then decide whether a new monitor shall be added.With the solutions to these problems,a network service provider will have a clear picture about which set of monitors the identifiability of a path counts on.Thus,when a monitor is down,it is easy to know it will affect the identifiability of paths.The work in this thesis is based on the assumption that a path is either identifiable or unidentifiable.When a path is unidentifiable,no information about the path performance will be provided.In the future,we will study bound-based network tomography where we are interested in whether a tight performance bound can be inferred when a path is unidentifiable.