Bounded-budget monitor deployment in monitoring networks via end-to-end probes
AssigneeInternational Business Machines Corporation
InventorsChatschik Bisdikian, Ting He, Liang Ma, Bonnie K. Ray
Life of this patent
Estimating the term…
Abstract
The present disclosure relates generally to mechanisms for bounded-budget monitor deployment in monitoring networks via end-to-end probes. In various embodiments, methodologies may be provided that automatically perform bounded-budget monitor deployment in monitoring networks via end-to-end probes.
Claims20
A method of selective monitor deployment under budget constraints, the method comprising:
- obtaining a network topology, a structure of an overlay network having a plurality of layers of monitoring interest, and a deployment budget;
- and
- from a top layer of the overlay network towards a bottom layer of the overlay network:
- computing a minimum deployment cost to fully identify links in a current layer of the overlay network;
- if the computed minimum deployment cost is no more than a remaining portion of the deployment budget:
- then deploying monitors so that the current layer of the overlay network is identified with the minimum deployment cost, reducing the remaining portion of the deployment budget, and going to the next layer;
- otherwise, deploying monitors within the remaining portion of the deployment budget so as to identify a fraction of link metrics of the current layer of the overlay network.
A method of selective monitor deployment under budget constraints, the method comprising:
- obtaining a network topology and a deployment budget;
- decomposing the network topology into a plurality of components having a predetermined property;
- computing a benefit and a cost for identifying each of the components;
- selecting at least one targeted component based on the benefit and the cost for identifying each of the components;
- and
- deploying monitors to identify links in the at least one targeted component within a remaining portion of the deployment budget.
A computer readable storage medium, tangibly embodying a program of instructions executable by the computer for selective monitor deployment under budget constraints, the program of instructions, when executing, performing the following steps:
- obtaining a network topology, a structure of an overlay network having a plurality of layers of monitoring interest, and a deployment budget;
- and
- from a top layer of the overlay network towards a bottom layer of the overlay network:
- computing a minimum deployment cost to fully identify links in a current layer of the overlay network;
- if the computed minimum deployment cost is no more than a remaining portion of the deployment budget:
- then deploying monitors so that the current layer of the overlay network is identified with the minimum deployment cost, reducing the remaining portion of the deployment budget, and going to the next layer;
- otherwise, deploying monitors within the remaining portion of the deployment budget so as to identify a fraction of link metrics of the overlay network.
A computer readable storage medium, tangibly embodying a program of instructions executable by the computer for selective monitor deployment under budget constraints, the program of instructions, when executing, performing the following steps:
- obtaining a network topology and a deployment budget;
- decomposing the network topology into a plurality of components having a predetermined property;
- computing a benefit and a cost for identifying each of the components;
- selecting at least one targeted component based on the benefit and the cost for identifying each of the components;
- and
- deploying monitors to identify links in the at least one targeted component within a remaining portion of the deployment budget.
Dependencies are inferred from the claim text.