Patent ID: 7486682

Claim:
A method for grooming traffic demands to be applied to a communications network having a set of predetermined mileage based tariffs associated therewith, the communications network specified as a set of nodes and a set of edges connecting said nodes, each edge having a distance associated therewith, the method comprising the steps of: generating a first graph based on the specified set of nodes and the set of edges; generating a second graph based on the first graph, the second graph having a set of edges which are a proper subset of the set of edges of the first graph; generating a liner program based on (i) the second graph, (ii) the set of predetermined mileage based tariffs, (iii) the distances associated with each of said edges in said set of edges of said second graph, and (iv) a set of traffic demands applied to said communications network; solving the generated linear program to groom said traffic demands for application to said communications network; and applying the groomed traffic demands to said communications network, wherein said second graph comprises a Delaunay Triangulation of said first graph.