Estimating a traffic matrix of a communication network using network topology features
Systems and methods include receiving network topology information of a network including a plurality of routers; receiving link measurements defining bandwidth on links in the network; determining routes in the network based on the network topology information; and utilizing the routes and the link measurements to determine an estimate of an initial traffic matrix that includes the bandwidth between origin routers and destination routers.
1. A non-transitory computer-readable medium comprising instructions that, when executed, cause a processing device to perform steps of:
receiving network topology information of a network including a plurality of routers;
receiving link measurements defining bandwidth on links in the network;
determining routes in the network based on the network topology information; and
utilizing the routes and the link measurements to determine an estimate of an initial traffic matrix that includes the bandwidth between origin routers and destination routers;
wherein the determining routes includes determining edge betweenness centrality between the plurality of routers that are edges in a network graph.
2. The non-transitory computer-readable medium of claim 1 , wherein the determining routes assumes traffic flows on a shortest path between the plurality of routers.
3. The non-transitory computer-readable medium of claim 1 , wherein the steps further include
determining the routes from listening to routing protocol messages.
4. The non-transitory computer-readable medium of claim 1 , wherein the steps further include
receiving partial direct measurements for the bandwidth and subtracting the partial direct measurements from the link measurements before determining the estimate.
5. The non-transitory computer-readable medium of claim 1 , wherein the steps further include
iteratively adjusting the initial traffic matrix to refine the estimate using other network information.
6. The non-transitory computer-readable medium of claim 5 , wherein the other network information includes any of link capacity, network topology, queuing discipline, and link aggregation.
7. The non-transitory computer-readable medium of claim 5 , wherein the iteratively adjusting utilizes an iterative statistical estimation procedure.
8. The non-transitory computer-readable medium of claim 1 , wherein the initial traffic matrix is at a point in time, and wherein the steps further include
repeating the receiving steps, the determining step, and the utilizing step at different points in time; and
averaging results to determine a traffic matrix over the point in time and the different points in time.
9. An apparatus comprising:
one or more processors and memory storing instructions that, when executed, cause the one or more processors to
receive network topology information of a network including a plurality of routers;
receive link measurements defining bandwidth on links in the network;
determine routes in the network based on the network topology information; and
utilize the routes and the link measurements to determine an estimate of an initial traffic matrix that includes the bandwidth between origin routers and destination routers;
wherein the routes are determined by determining edge betweenness centrality between the plurality of routers that are edges in a network graph.
10. The apparatus of claim 9 , wherein the routes are determined by assuming traffic flows on a shortest path between the plurality of routers.
11. The apparatus of claim 9 , wherein the instructions that, when executed, further cause the one or more processors to
determine the routes from listening to routing protocol messages.
12. The apparatus of claim 9 , wherein the instructions that, when executed, further cause the one or more processors to
receive partial direct measurements for the bandwidth and subtract the partial direct measurements from the link measurements before determining the estimate.
13. The apparatus of claim 9 , wherein the instructions that, when executed, further cause the one or more processors to
iteratively adjust the initial traffic matrix to refine the estimate using other network information.
14. The apparatus of claim 9 , wherein the instructions that, when executed, further cause the one or more processors to
repeat the receive steps, the determine step, and the utilize step at different points in time; and
average results to determine a traffic matrix over the point in time and the different points in time.
15. A method comprising:
receiving network topology information of a network including a plurality of routers;
receiving link measurements defining bandwidth on links in the network;
determining routes in the network based on the network topology information; and
utilizing the routes and the link measurements to determine an estimate of an initial traffic matrix that includes the bandwidth between origin routers and destination routers;
wherein the routes are determined by determining edge betweenness centrality between the plurality of routers that are edges in a network graph.
16. The method of claim 15 , further comprising
determining the routes from listening to routing protocol messages.
17. The method of claim 15 , further comprising
receiving partial direct measurements for the bandwidth and subtracting the partial direct measurements from the link measurements before determining the estimate.
18. The method of claim 15 , further comprising
iteratively adjusting the initial traffic matrix to refine the estimate using other network information.