Patent ID: 8266268

Claim:
A method for determining on which network devices to deploy a network monitoring service within a communication network for the lowest cost for a selected percentage traffic coverage, the method comprising: collecting configuration files comprising configuration data from a set of routers in the communication network over the communication network; inputting parameters to a decision process based on the configuration data from the set of routers; defining a notation for one or more slots within the set of routers in the decision process using the configuration data from the set of routers; defining objective functions using the notation for the one or more slots within the set of routers in the decision process; defining decision variables; constraining relationships between the decision variables; and solving for the decision variables using the inputted parameters and the constraining relationships to determine which network devices to deploy the network monitoring service, wherein the parameters comprise upgrade options for a router type, upgrade cost for an upgrade option, and minimum amount of traffic covered by network monitoring service deployment, wherein the upgrade cost for an upgrade option comprises: calculating a cost to upgrade a subset of the set of routers requiring a base upgrade by summing a cost to upgrade each slot within the subset of routers and a cost for the base upgrade across the subset of routers requiring a base upgrade, and wherein the cost to upgrade one or more of a subset of routers requiring no base upgrade is defined as: F GSR = ∑ g ∈ G GSR ⁢ ⁢ ∑ t ∈ T ⁡ ( g ) ⁢ ⁢ v g ⁡ ( t ) ⁢ c ⁡ ( t ) , wherein v g (t) represents a set of slot indices where a linecard t is present, and wherein c(t) represents a cost to upgrade linecard t.