Flow propagation analysis using iterative signaling

• US 20030117955A1
• Filed: 12/20/2002
• Published: 06/26/2003
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Popa, Marius, Singh, Pradeep K., Znam, Stefan, Cohen, Alain, Pasupathy, Arun
• Granted Patent: US 7,139,692 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A method and system for flow propagation analysis uses ‘tracers’ that are iteratively propagated through a simulated network between source and destination elements. These tracers are structured to contain traffic flow information from source to destination, and to reflect changes as the flow is affected by each element along the path from source to destination. The resultant flow information at the destination corresponds to the effective throughput from the source to the destination, and the flow information at the output of each intermediate element in the network corresponds to the potentially achievable throughput through that element for the given source-to-destination flow.

Claims

1. A method for analyzing traffic flow in a modeled network, comprising:

defining a plurality of traffic-flows,

each traffic-flow of the plurality of traffic-flows corresponding to a path from a source node to a destination node in the modeled network,

generating a plurality of streams of tracers,

each stream of tracers being associated with each traffic-flow of the plurality of traffic-flows, and

each tracer of each stream of tracers being structured to contain flow-information related to the traffic-flow corresponding to the tracer,

propagating each tracer through the modeled network along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow, and

updating the flow-information in each tracer based on changes to the tracer'"'"'s corresponding traffic-flow introduced by nodes in the modeled network along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow.

2. The method of claim 1, wherein

the changes to the tracer'"'"'s corresponding traffic-flow is based on at least one of:

a bandwidth limitation,

a bandwidth allocation scheme, and

one or more parameters of a queuing model,

associated with the nodes in the modeled network.

3. The method of claim 1, wherein

the flow-information includes an average flow-rate along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow.

4. The method of claim 3, wherein

the flow-information further includes at least one of:

a variance about the average flow-rate,

a size of a transmission unit,

a variance of the size of the transmission unit,

a probability distribution of sizes of a plurality of transmission units, and

a probability distribution of arrival-times of the plurality of transmission units.

5. The method of claim 1, wherein

the flow-information in each tracer includes other flow-information associated with other traffic-flows of the plurality of traffic-flows, and

updating the flow-information in each tracer includes updating some or all of the other flow-information.

6. A computer program for analyzing traffic flow in a modeled network, which, when executed on a computer system, causes the computer system to:

create a plurality of traffic-flows,

each traffic-flow of the plurality of traffic-flows corresponding to a path from a source node to a destination node in the modeled network,

generate a plurality of streams of tracers,

each stream of tracers being associated with each traffic-flow of the plurality of traffic-flows, and

each tracer of each stream of tracers being structured to contain flow-information related to the traffic-flow corresponding to the tracer,

propagate each tracer through the modeled network along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow, and

update the flow-information in each tracer based on changes to the tracer'"'"'s corresponding traffic-flow introduced by nodes in the modeled network along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow.

7. The program of claim 6, wherein

the changes to the tracer'"'"'s corresponding traffic-flow is based on at least one of:

a bandwidth limitation,

a bandwidth allocation scheme, and

one or more parameters of a queuing model,

associated with the nodes in the modeled network.

8. The program of claim 6, wherein

the flow-information includes an average flow-rate along the path from the source node to the destination node of the tracer'"'"'s corresponding traffic-flow.

9. The program of claim 8, wherein

the flow-information further includes at least one of:

a variance about the average flow-rate,

a size of a transmission unit,

a variance of the size of the transmission unit,

a probability distribution of sizes of a plurality of transmission units, and

a probability distribution of arrival-times of the plurality of transmission units.

10. The program of claim 6, wherein

the flow-information in each tracer includes other flow-information associated with other traffic-flows of the plurality of traffic-flows, and

updating the flow-information in each tracer includes updating some or all of the other flow-information.

11. A network simulator comprising:

a discrete-event simulator that is configured to simulate elements in a network based on explicit-traffic events and particularized background-traffic events, and

a flow-analysis subsystem that is configured to determine flow-rates associated with background-traffic,

wherein

the particularized background-traffic events are based on the determined flow-rates associated with the background-traffic.

12. The network simulator of claim 11, wherein

the flow-analysis subsystem is configured to propagate tracers along select paths of the network,

the tracers are configured to contain flow-information corresponding to the select paths, and

the flow-analysis subsystem updates the flow-information of the tracers based on one or more characteristics of network elements along the select paths.

13. The network simulator of claim 12, wherein

the one or more characteristic of the network elements include at least one of:

a bandwidth limitation,

a bandwidth allocation scheme, and

one or more parameters of a queuing model.

14. The network simulator of claim 12, wherein

the flow-information includes average flow-rates along the select paths.

15. The network simulator of claim 14, wherein

the flow-information further includes at least one of:

variances about the average flow-rates,

sizes of transmission units,

variances of the sizes of the transmission units,

probability distributions of sizes of a plurality of transmission units, and

probability distributions of arrival-times of the plurality of transmission units.

16. The network simulator of claim 12, wherein

the flow-information in each of the tracers includes other flow-information associated with other traffic-flows of the plurality of traffic-flows, and

updating the flow-information in each of the tracers includes updating some or all of the other flow-information.

17. A computer program that is configured to be executed on a computer system, comprising:

a discrete-event simulator that is configured to simulate elements in a network based on explicit-traffic events and particularized background-traffic events, and

a flow-analysis subsystem that is configured to determine flow-rates associated with background-traffic,

wherein

the particularized background-traffic events are based on the determined flow-rates associated with the background-traffic.

18. The program of claim 17, wherein

the flow-analysis subsystem is configured to propagate tracers along select paths of the network,

the tracers are configured to contain flow-information corresponding to the select paths, and

the flow-analysis subsystem updates the flow-information of the tracers based on one or more characteristics of network elements along the select paths.

19. The program of claim 18, wherein

the one or more characteristic of the network elements include at least one of:

a bandwidth limitation,

a bandwidth allocation scheme, and

one or more parameters of a queuing model.

20. The program of claim 18, wherein

the flow-information includes average flow-rates along the select paths.

21. The program of claim 20, wherein

the flow-information further includes at least one of:

variances about the average flow-rates,

sizes of transmission units,

variances of the sizes of the transmission units,

probability distributions of sizes of a plurality of transmission units, and

probability distributions of arrival-times of the plurality of transmission units.

22. The program of claim 18, wherein

the flow-information in each of the tracers includes other flow-information associated with other traffic-flows of the plurality of traffic-flows, and

updating the flow-information in each of the tracers includes updating some or all of the other flow-information.