Flow propagation analysis using iterative signaling

• US 7,139,692 B2
• Filed: 12/20/2002
• Issued: 11/21/2006
• 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
• Primary Examiner(s): THANGAVELU, KANDASAMY
• Application Number:
  US10/325,148
• Publication Number:
  US 20030117955A1
• Time in Patent Office: 1,432 Days
• Field of Search: 703/21, 703/13, 709/235, 709/234, 709/225, 709/223, 709/224, 709/246, 370/395.21, 370/229, 370/254, 370/216, 370/252, 370/244, 705/1, 714/4
• US Class Current: 703/21
• 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 one 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 one 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 flow analysis subsystem that is configured to propagate tracers along select paths from source nodes to destination nodes of traffic flows of the network, wherein

the tracers are configured to contain flow information corresponding to the traffic flows of the select paths, and

the flow analysis subsystem updates the flow information of the tracers based on changes to the tracers'"'"' corresponding traffic flows introduced by one or more network elements along the select paths.

12. The network simulator of claim 11, including:

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

the flow analysis subsystem is configured to determine flow rates associated with background traffic, and

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

13. The network simulator of claim 11, wherein the changes to the tracers'"'"' corresponding traffic flows are based on 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 11, 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 on a computer readable media that is configured to be executed on a computer system, comprising computer instructions for:

a flow analysis subsystem that is configured to propagate tracers along select paths from source nodes to destination nodes of traffic flows of the network, wherein

the tracers are configured to contain flow information corresponding to the traffic flows of the select paths, and

the flow analysis subsystem updates the flow information of the tracers based on changes to the tracers'"'"'corresponding traffic flows introduced by one or more network elements along the select paths.

18. The computer program of claim 17 including:

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.

19. The computer program of claim 17, wherein the changes to the tracers'"'"' corresponding traffic flows are based on at least one of:

a bandwidth limitation,

a bandwidth allocation scheme, and

one or more parameters of a queuing model.

20. The computer program of claim 17, wherein the flow information includes average flow rates along the select paths.

21. The computer 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 computer program of claim 17, 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.