Traffic flow inference based on link loads and gravity measures
View Patent ↗Traffic flow between each pair of nodes in a network are determined based on loads measured at each link and based on gravity measures. The gravity measures correspond to a likelihood of the node being a source or a sink of traffic and may be assigned based on characteristics associated with each node, such as the demographics of the region in which the node is located, prior sinking and sourcing statistics, and so on. The gravity measures are used to generate an objective function for solving a system of linear equations, rather than as criteria that must be satisfied in the solution. The measured link loads are allocated among the traffic flows between nodes to at least a given allocation efficiency criteria by solving a system of linear equations with an objective of minimizing a difference between the assigned gravities and the resultant gravities corresponding to the determined flows.
1. A method of presenting traffic flowing through a network based on loads on links between nodes in the network, said method comprising:
determining a topology of the network, wherein the topology indicates at least a portion of nodes in the network and links among the nodes;
determining respective link loads for each of the links among the nodes in the topology;
assigning, to each node in the topology, a set of gravity estimates, wherein the set of gravity estimates indicate a likelihood of a node of originating traffic through the network and of terminating traffic from the network;
determining sets of traffic flow through the network comprising respective gravity measures allocated to nodes through which the traffic flows based on the link loads, and minimizing the difference between the assigned gravity estimates and the allocated gravity measures; and
outputting information for displaying at least some of the sets of traffic flow on a user interface.
2. The method of claim 1 , wherein determining respective link loads comprises receiving a parameter specifying an amount of a link load to be allocated to one or more traffic flows through the network.
3. The method of claim 1 , wherein assigning the set of gravity estimates comprises assigning gravity estimates that are specified as a relative measure.
4. The method of claim 1 , wherein assigning the set of gravity estimates comprises:
determining assignments of sets of gravity estimates omitted by a user; and
automatically assigning gravity estimates omitted by a user.
5. The method of claim 1 , wherein assigning the set of gravity estimates comprises receiving an input from a user indicating a classification of a node based on the node's capability to serve as at least one of a source or destination of traffic.
6. The method of claim 1 , wherein assigning the set of gravity estimates comprises receiving an input from a user indicating a soft measure of a node's likelihood of serving as a source or destination of traffic.
7. The method of claim 1 , wherein determining sets of traffic flow through the network comprises converting link loads between nodes through which traffic flows and minimizing the difference between the assigned gravity estimates and the allocated gravity measures.
8. The method of claim 1 , further comprising:
receiving a proposed traffic flow between a pair of nodes from a user; and
determining an impact of the proposed traffic flow on the determined set of traffic flows.
9. A computer system of modeling traffic flowing through a network based on converting link loads to traffic flows, said system comprising:
a capture element, running on a computer, configured to receive information from a user interface indicating a topology of the network, wherein the topology indicates at least a portion of nodes in the network and links among the nodes and receive information indicating at least some of the link loads for links among the nodes in the topology;
a user interface element, running on the computer, configured to assign, to each node in the topology, a set of gravity estimates based on user input, wherein the set of gravity estimates indicate a likelihood of a node of originating traffic through the network and of terminating traffic from the network;
a converter element, running on the computer, configured to convert the link loads into sets of traffic flow through the network comprising respective gravity measures allocated to nodes through which the traffic flows based on minimizing the difference between the assigned gravity estimates and the allocated gravity measures; and
a network model element, running on the computer, providing graphical information for displaying at least some of the sets of traffic flow via the user interface element.
10. The system of claim 9 , wherein the capture element is further configured to receive link load information reported from the network.
11. The system of claim 10 , wherein the capture element is further configured to receive link load information based on a time interval.
12. The system of claim 9 , wherein the capture element is further configured to receive link load information based on a load estimate provided from the user.
13. The system of claim 9 , wherein the network model element is configured to receive information from the user modifying at least one of the sets of traffic flows.
14. The system of claim 13 , wherein the network model element is configured to provide updated graphical information displaying at least some of the sets of traffic flow.
15. The system of claim 9 , wherein the network model element is configured receive information from the user adding at least one additional constraint to at least one of the sets of traffic flows.
16. A method of graphically displaying an impact of changes entered by a user on traffic flowing through a network, wherein the traffic flowing through the network is calculated from loads specified on links in the network and sets of gravity estimates assigned to nodes in the network, said method comprising:
determining a topology of the network, wherein the topology indicates at least a portion of nodes in the network and links among the nodes;
displaying, to a user, graphical information indicating sets of traffic flow through the network, wherein the traffic flows comprise gravity measures allocated to nodes carrying the traffic, and wherein the traffic flows are calculated based on the link loads and minimizing the difference between the assigned gravity estimates and the allocated gravity measures; and
receiving, from the user, input indicating changes to the network; and
displaying, to the user, graphical information indicating updated sets of traffic flows through the network based on the changes to the network.
17. The method of claim 16 , wherein displaying, to the user, graphical information indicating updated sets of traffic flows comprises displaying graphical information indicating updated link loads affected by the changes to the network.
18. The method of claim 16 , wherein receiving, from the user, input indicating changes to the network comprises receiving input indicating changes to at least one link load.
19. The method of claim 16 , wherein receiving, from the user, input indicating changes to the network comprises receiving input indicating changes to at least one gravity estimate.
20. The method of claim 16 , wherein receiving, from the user, input indicating changes to the network comprises receiving input indicating changes to at least one of the sets of traffic flow.