US6061331A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for estimating source-destination traffic in a packet-switched communications network
Assignee: Verizon Laboratories Inc
•
Filing: 1998-07-28
•
Granted: 2000-05-09
•
Expires: 2018-07-28
Abstract
Abstract A real-time process estimates the source-destination traffic matrix in a packet-switched communications network. The inputs for the process are a set of aggregate link traffic measurements and a set of source node traffic measurements. The process uses a novel and computationally efficient decomposition method to estimate the traffic matrix. The process also makes uses of Linear Programming (LP) methods to estimate the source-destination traffic matrix.
Inventors
- 👤 Adrian E. Conway
- 👤 Man Li
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:40
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/64; H04Q3/66; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619; H04L2012/5623; H04L2012/5629; H04L2012/5631; H04L2012/5636; H04L2012/5678; H04L2012/5684; H04Q2213/00; H04Q2213/13103; H04Q2213/13106; H04Q2213/13141; H04Q2213/13146; H04Q2213/13148; H04Q2213/13164; H04Q2213/13166; H04Q2213/13167; H04Q2213/13296; H04Q2213/13335; H04Q2213/13349
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
298 words
A method for estimating source-destination traffic for a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node and including at least one link, the method comprising the steps of: providing a source traffic rate measurement for traffic coming into the network at each source node during each of a plurality of time periods and a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating from the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 2
Independent Claim
298 words
A method for estimating source-destination traffic for a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node and including at least one link, the method comprising the steps of: providing a source traffic rate measurement for traffic coming into the network at each source node during each of a plurality of time periods and a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating from the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 3
Dependent Claim
37 words
The method of claim 1, wherein the step of determining an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes includes the substep of solving a linear programming problem.
Claim 4
Dependent Claim
41 words
The method of claim 1, wherein the step of determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node includes the substep of solving a linear programming problem.
Claim 5
Dependent Claim
113 words
The method of claim 1, wherein, for each destination node and link, a traffic rate proportion for traffic originating at a source node and terminating at a destination node that flows on each link is stored in memory in a network management system, the method further comprising the step of retrieving from memory the traffic rate proportion for traffic originating at the source node and terminating at the destination node that flows on each link, and wherein the step of determining an estimate of a traffic proportion rate for traffic originating from each source node corresponding to traffic terminating at each destination node is further performed based on the retrieved traffic rate proportion.
Claim 6
Dependent Claim
315 words
In a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at one of the plurality of source nodes and terminating at one of the plurality of destination nodes and including at least one of the plurality of links, a method for estimating traffic from each source node to each destination node, the method comprising the steps of: measuring a source traffic rate for traffic coming into the network at each source node during each of a plurality of time periods; measuring a link traffic rate for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 7
Dependent Claim
315 words
In a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at one of the plurality of source nodes and terminating at one of the plurality of destination nodes and including at least one of the plurality of links, a method for estimating traffic from each source node to each destination node, the method comprising the steps of: measuring a source traffic rate for traffic coming into the network at each source node during each of a plurality of time periods; measuring a link traffic rate for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 8
Dependent Claim
37 words
The method of claim 5, wherein the step of determining an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes includes the substep of solving a linear programming problem.
Claim 9
Dependent Claim
41 words
The method of claim 5, wherein the step of determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node includes the substep of solving a linear programming problem.
Claim 10
Dependent Claim
113 words
The method of claim 5, wherein, for each destination node and link, a traffic rate proportion for traffic originating at a source node and terminating at a destination node that flows on each link is stored in memory in a network management system, the method further comprising the step of retrieving from memory the traffic rate proportion for traffic originating at the source node and terminating at the destination node that flows on each link, and wherein the step of determining an estimate of a traffic proportion rate for traffic originating from each source node corresponding to traffic terminating at each destination node is further performed based on the retrieved traffic rate proportion.
Claim 11
Independent Claim
311 words
A system for estimating traffic in a packet-switched network, wherein the network includes a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node, the system comprising: an interface for receiving from the network a source rate traffic measurement for traffic coming into the network at each source node during each of a plurality of time periods and for receiving from the network a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; a memory comprising a traffic estimation program; and a processor utilizing the traffic estimation program to determine, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determine an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the estimate of the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and compute a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 12
Independent Claim
311 words
A system for estimating traffic in a packet-switched network, wherein the network includes a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node, the system comprising: an interface for receiving from the network a source rate traffic measurement for traffic coming into the network at each source node during each of a plurality of time periods and for receiving from the network a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; a memory comprising a traffic estimation program; and a processor utilizing the traffic estimation program to determine, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determine an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the estimate of the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and compute a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 13
Dependent Claim
306 words
A computer-readable medium containing instructions for estimating source-destination traffic for a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node and including at least one link, by: receiving from the network a source rate traffic measurement for traffic coming into the network at each source node during each of a plurality of time periods and for receiving from the network a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the estimate of the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
Claim 14
Dependent Claim
306 words
A computer-readable medium containing instructions for estimating source-destination traffic for a packet-switched communications network, wherein the network includes a plurality of nodes, including a plurality of source nodes and a plurality of destination nodes, the nodes interconnected by a plurality of links, and wherein the network includes a plurality of traffic routes, each route originating at a source node and terminating at a destination node and including at least one link, by: receiving from the network a source rate traffic measurement for traffic coming into the network at each source node during each of a plurality of time periods and for receiving from the network a link traffic rate measurement for traffic on each of the plurality of links belonging to routes originating at the source nodes during each time period; determining, for each of the plurality of links belonging to routes originating at the source nodes, an estimate of a proportion of the link traffic rate corresponding to traffic originating from the source nodes over the plurality of time periods based on the link traffic rate measurement and the source traffic rate measurement during each time period; determining an estimate of a traffic rate proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods based on the estimate of the proportion of the link traffic rate corresponding to traffic originating from the source nodes for each of the plurality of links belonging to routes originating at the source nodes; and computing a rate of traffic from each source node to each destination node based on the source traffic rate measurement during each of the plurality of time periods and the traffic proportion for traffic originating from each source node corresponding to traffic terminating at each destination node over the plurality of time periods.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |