Traffic matrix estimation method and apparatus

• US 7,293,086 B1
• Filed: 07/25/2003
• Issued: 11/06/2007
• Est. Priority Date: 07/25/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Zhang, Yin, Roughan, Matthew, Greenberg, Albert Gordon, Duffield, Nicholas G., Klincewicz, John G.
• Primary Examiner(s): Eng; David Y.
• Application Number:
  US10/627,767
• Time in Patent Office: 1,565 Days
• Field of Search: 709/223, 709/224
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity

Abstract

A method and apparatus for the estimation of traffic matrices in a network are disclosed. Mechanisms are disclosed for measuring traffic volume from a plurality of ingress points to a plurality of egress points in a large scanl network, such as an IP backbone network. The traffic matrix is advantageously inferred from widely available link load measurements such as SNMP data.

Claims

1. A method of measuring traffic volume from a plurality of ingress points to a plurality of egress points in a network, the method comprising:

collecting link load measurements on links between the ingress points and the egress points;

constructing a gravity model of link to link traffic utilizing the link load measurements to capture an overall distribution of the volume of traffic between the ingress points and the egress points; and

finding a traffic matrix that minimizes a distance metric subject to tomographic constraints to an initial tomographic solution based on the gravity model, the traffic matrix further comprising elements that specify the traffic volume from the plurality of ingress points to the plurality of egress points in the network.

2. The method of claim 1 wherein the initial tomographic solution is modified to remove empty demands based on simulations of routing in the network.

3. The method of claim 2 wherein simulations are run only on routes that are not topologically equivalent.

4. The method of claim 3 wherein the ingress points and the egress points are border routers in an Internet Protocol (IP) backbone network.

5. The method of claim 4 wherein the gravity model differentiates between customer and peering traffic in the IP backbone network.

6. A computer readable medium comprising executable instructions for performing a method of measuring traffic volume from a plurality of ingress points to a plurality of egress points in a network, the method comprising:

collecting link load measurements on links between the ingress points and the egress points;

constructing a gravity model of link to link traffic utilizing the link load measurements to capture an overall distribution of the volume of traffic between the ingress points and the egress points; and

finding a traffic matrix that minimizes a distance metric subject to tomographic constraints to an initial tomographic solution based on the gravity model, the traffic matrix further comprising elements that specify the traffic volume from the plurality of ingress points to the plurality of egress points in the network.

7. The computer readable medium of claim 6 wherein the initial tomographic solution is modified to remove empty demands based on simulations of routing in the network.

8. The computer readable medium of claim 7 wherein simulations are run only on routes that are not topologically equivalent.

9. The computer readable medium of claim 8 wherein the ingress points and the egress points are border routers in an Internet Protocol (IP) backbone network.

10. The computer readable medium of claim 9 wherein the gravity model differentiates between customer and peering traffic in the IP backbone network.