MODELING AND SIMULATING FLOW PROPAGATION IN DYNAMIC BANDWIDTH SYSTEMS

• US 20080120081A1
• Filed: 11/16/2007
• Published: 05/22/2008
• Est. Priority Date: 11/17/2006
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Boyd, David, Znam, Stefan, Singh, Pradeep, Cohen, Alain J., Janes, Paul M., CHANDRASHEKAR, Karthikeyan
• Granted Patent: US 9,253,045 B2
• Time in Patent Office: Days
• US Class Current: 703/13
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]

Abstract

In a network that includes static bandwidth and dynamic bandwidth links, traffic flow at the OSI network layer is simulated at a traffic-flow level at interfaces to fixed bandwidth links, and simulated at a discrete-packet level at interfaces to dynamic bandwidth links. The resultant discrete-packet reception events at the receiving interface(s) of the dynamic bandwidth link are processed to determine the effective bandwidth/throughput of the link, as well as the allocation of this bandwidth among the individual flows through the link. The discrete-packet level receptions are used to reconstruct the parameters of the traffic flow at the network layer of the receiving interface, and this determined traffic flow is simulated accordingly at the next link, depending upon whether the next link is a static or dynamic bandwidth link.

Claims

1. A method of simulating a network comprising:

identifying one or more links of the network as a dynamic bandwidth link,

identifying one or more links of the network as a static bandwidth link,

defining a plurality of traffic flow demands, and

simulating application of the traffic flow demands on a model of the network,

wherein

simulating the application of the traffic flow demands includes

simulating each interface to each link identified as a static bandwidth link using a traffic-flow level model of the interface, and

simulating each interface to each link identified as a dynamic bandwidth link using a discrete-packet level model of the interface.

2. The method of claim 1, wherein

simulating the discrete-packet level model includes generating a plurality of packets for propagation from a transmitting interface to the link based on a received traffic flow at the transmitting interface.

3. The method of claim 2, wherein

simulating the discrete-packet level model includes generating a resultant traffic flow at a receiving interface to the link based on received packets of the plurality of packets from the transmitting interface.

4. The method of claim 3, including

determining traffic flow parameters based on the received packets.

5. The method of claim 3, wherein

simulating the traffic-flow level model includes determining traffic flow parameters based on a bandwidth of the link and a total amount of traffic flow demands on the link.

6. The method of claim 1, wherein

simulating the traffic-flow level model includes determining traffic flow parameters based on a bandwidth of the link and a total amount of traffic flow demands on the link.

7. The method of claim 1, including

updating the traffic flow demands at a transmitter interface to at least one link based on resultant flow parameters at a receiver interface to the at least one link.

8. The method of claim 1, wherein

defining the plurality of traffic flow demands includes defining traffic flow demands between each pair of a plurality of pairs of source nodes and destination nodes.

10. The method of claim 8, wherein

simulating the application of the traffic flow demands includes:

generating traffic-flow tracers at each source node of each pair based on the traffic flow demands from the source,

propagating the traffic-flow tracers along one or more paths from the source node of each pair to the destination node of the pair;

wherein

each traffic-flow tracer includes at least one traffic flow parameter, and

propagating the traffic-flow tracers includes modification of the at least one traffic flow parameter at one or more links along the one or more paths.

11. The method of claim 10, wherein

the traffic-flow level model of at least one interface to the one or more links is configured to update the at least one traffic flow parameter based on a bandwidth of the link and a total amount of traffic flow demand at the link,

the discrete-packet level model of at least one transmit interface to the one or more links is configured to generate a series of transmit packets corresponding to the at least one traffic flow parameter, and

the discrete-packet level model of at least one receive interface to the one or more links is configured to update the at least one traffic flow parameter based on a simulated receipt of received packets from the series of transmit packets.

12. The method of claim 1, including

providing a display of resultant flows at one or more links, based on the application of the traffic flow demands on the model of the network.

9. The method of claim 9, wherein

simulating the application of traffic flow demands provides resultant traffic flow parameters at each destination node, and

the method includes updating the traffic flow demand at the source node of at least one pair based on the resultant traffic flow parameters at the destination node of the at least one pair.

13. A method of simulating a network comprising:

defining traffic flow demand for each flow-pair of a plurality of flow-pairs of source and destination nodes,

generating traffic-flow tracers at each source node corresponding to the traffic flow demand for each flow-pair that includes the source node, each traffic-flow tracer including at least one traffic flow parameter corresponding to the traffic flow demand, and

propagating the traffic-flow tracers across links of paths from the source nodes to the destination nodes, the traffic flow parameter being updated at each link to reflect a resultant traffic flow across the link,

wherein at each link;

if the link is identified as a link having a fixed bandwidth, the traffic flow parameter is updated based on the fixed bandwidth and a total traffic flow demand at the link, the total traffic flow demand being based on the traffic flow parameters of the traffic-flow tracers arriving at the link, and

if the link is identified as a link having a dynamic bandwidth, the traffic flow parameter is updated based on a simulated receipt of discrete-packets propagated across the link, the discrete-packets being generated for propagation across the link based on the traffic flow parameters of the traffic-flow tracers arriving at the link.

14. The method of claim 13, including

updating the traffic flow demand at the source node of at least one flow-pair based on the traffic flow parameter of one or more traffic-flow tracers arriving at the destination node of the at least one flow-pair.

15. The method of claim 13, wherein

the at least one traffic flow parameter includes a measure of quantity of traffic per unit time.

16. A computer-readable medium that includes a computer program that is configured to enable a processor to execute a simulation process that includes:

defining traffic flow demand for each flow-pair of a plurality of flow-pairs of source and destination nodes of a network,

generating traffic-flow tracers at each source node corresponding to the traffic flow demand for each flow-pair that includes the source node, each traffic-flow tracer including at least one traffic flow parameter corresponding to the traffic flow demand, and

propagating the traffic-flow tracers across links of paths of the network from the source nodes to the destination nodes, the traffic flow parameter being updated at each link to reflect a resultant traffic flow across the link,

wherein at each link;

if the link is identified as a link having a fixed bandwidth, the traffic flow parameter is updated based on the fixed bandwidth and a total traffic flow demand at the link, the total traffic flow demand being based on the traffic flow parameters of the traffic-flow tracers arriving at the link, and

if the link is identified as a link having a dynamic bandwidth, the traffic flow parameter is updated based on a simulated receipt of discrete-packets propagated across the link, the discrete-packets being generated for propagation across the link based on the traffic flow parameters of the traffic-flow tracers arriving at the link.

17. The computer-readable medium of claim 16, wherein the simulation process includes

updating the traffic flow demand at the source node of at least one flow-pair based on the traffic flow parameter of one or more traffic-flow tracers arriving at the destination node of the at least one flow-pair.

18. A system that includes:

a model of a network,

a dynamic link identifier that is configured to identify;

one or more links of the network as a dynamic bandwidth link, and

done or more links of the network as a static bandwidth link, and

a simulator is configured to simulate application of traffic flow demands on the model of the network,

wherein

simulating the application of the traffic flow demands includes

simulating each interface to each dynamic bandwidth link using a traffic-flow level model of the interface, including

determining traffic flow parameters based on a bandwidth of the link and a total amount of traffic flow demands on the link, and

simulating each interface to each dynamic bandwidth link using a discrete-packet level model of the interface, including;

generating a plurality of packets for propagation from a transmitting interface to the link based on a received traffic flow at the transmitting interface, and

generating a resultant traffic flow at a receiving interface to the link based on received packets of the plurality of packets from the transmitting interface.

19. The system of claim 18, wherein the simulator is configured to update traffic flow demands at the transmitting interface to at least one link based on resultant flow parameters at the receiving interface to the at least one link.

20. The system of claim 18, wherein

the traffic flow demands include traffic flow demands between each pair of a plurality of pairs of source nodes and destination nodes, and

the simulator is configured to update the traffic flow demand at the source node of at least one pair based on resultant traffic flow parameters at the destination node of the at least one pair.

21. The system of claim 18, wherein

the traffic flow demands include traffic flow demands between each pair of a plurality of pairs of source nodes and destination nodes, and

the simulator is configured to:

generate traffic-flow tracers at each source node of each pair based on the traffic flow demands from the source, and

propagate the traffic-flow tracers along one or more paths from the source node of each pair to the destination node of the pair;

wherein each traffic-flow tracer includes at least one traffic flow parameter, and

the simulator is configured to;

update the at least one traffic flow parameter at a static bandwidth link along the one or more paths using the traffic-flow level model, and

update the at least one traffic flow parameter at a dynamic bandwidth link along the one or more paths using the discrete-packet level model.

22. The system of claim 21, wherein

the discrete-packet level model of at least one transmit interface to the dynamic bandwidth link is configured to generate a series of transmit packets corresponding to the at least one traffic flow parameter, and

the discrete-packet level model of at least one receive interface to the dynamic bandwidth link is configured to update the at least one traffic flow parameter based on a simulated receipt of received packets from the series of transmit packets.

23. The system of claim 18, including

a user interface that is configured to provide a display of resultant flows at one or more links, based on the application of the traffic flow demands on the model of the network.

24. A system that includes:

a model of a network,

a dynamic link identifier, that is configured to identify;

one or more links of the network as a dynamic bandwidth link, and

one or more links of the network as a static bandwidth link, and a simulator that is configured to;

receive traffic flow demand for each flow-pair of a plurality of flow-pairs of source and destination nodes

generate traffic-flow tracers at each source node corresponding to a traffic flow demand for each flow-pair that includes the source node, each traffic-flow tracer including at least one traffic flow parameter corresponding to the traffic flow demand, and

propagate the traffic-flow tracers across links of paths from the source nodes to the destination nodes, the traffic flow parameter being updated at each link to reflect a resultant traffic flow across the link,

wherein at each link;

if the link is identified as a static bandwidth link, the traffic flow parameter is updated based on the fixed bandwidth and a total traffic flow demand at the link, the total traffic flow demand being based on the traffic flow parameters of the traffic-flow tracers arriving at the link, and

if the link is identified as a dynamic bandwidth link, the traffic flow parameter is updated based on a simulated receipt of discrete-packets propagated across the link, the discrete-packets being generated for propagation across the link based on the traffic flow parameters of the traffic-flow tracers arriving at the link.

25. The system of claim 24, wherein

the simulator is configured to update the traffic flow demand at the source node of at least one flow-pair based on the traffic flow parameter of one or more traffic-flow tracers arriving at the destination node of the at least one flow-pair.