Mixed mode network simulator

• US 6,820,042 B1
• Filed: 07/24/2000
• Issued: 11/16/2004
• Est. Priority Date: 07/23/1999
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Malloy, Patrick J., Cohen, Alain, Cathey, George
• Primary Examiner(s): THOMSON, WILLIAM D
• Application Number:
  US09/624,092
• Time in Patent Office: 1,576 Days
• Field of Search: 703/2, 703/17, 703/13, 703/21, 703/22, 703/20, 702/182, 702/186, 702/179, 702/181, 709/223, 709/220, 709/224, 709/221, 709/222
• US Class Current: 703/2
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]

Abstract

A simulation system and method that combines the advantages of both analytical modeling and discrete-event simulation is disclosed. In a preferred embodiment of this invention, traffic on the network is modeled as a combination of background-traffic and explicit-traffic. The background-traffic is primarily processed in an analytical form, except in the “time-vicinity” of an explicit-event. Explicit-events are processed using discrete-event simulation, and the modeled effects are dependent upon the background-traffic. At each occasion that the background-traffic may affect the explicit-traffic, the background-traffic is particularized into events that are modeled at the lower detail level of the explicit-traffic. In this manner, the portions of the network that are unaffected by the explicit-traffic and that have no effect on the explicit-traffic are modeled and processed at an analytical level, consuming minimal processing time and memory resources, while the portion of the network affected by the explicit-traffic and the background-traffic that affects the explicit-traffic are processed at the lower level of detail.

Claims

1. A method of enabling a simulation, comprising:

enabling an encoding of a network architecture, the network architecture comprising a plurality of elements and at least one link between two elements of the plurality of elements,

enabling an encoding of one or more background-traffic parameters associated with the at least one link of the network architecture,

enabling an encoding of one or more discrete event parameters that facilitates a generation of explicit-traffic, and

enabling a determination of properties associated with a propagation of the explicit-traffic across the at least one link in dependence upon an effect of the one or more background-traffic parameters, by simulating the background traffic as implicit-traffic events in the vicinity of each occurrence of explicit-traffic events, based on the explicit-traffic.

2. The method of claim 1, wherein the determination of the effect of the one or more background-traffic parameters includes a steady-state analysis of the network architecture based on a rate-based parameter of the one or more background-traffic parameters.

3. The method of claim 1, wherein

the one or more background-traffic parameters includes stochastic process parameters, and

the method further includes

enabling a determination of the effect of the one or more background-traffic parameters based on a stochastic process.

4. The method of claim 3, wherein,

the stochastic traffic parameters are associated with information items, and include at least one of:

a mean information item size,

a distribution parameter associated with the mean information item size,

a mean information item arrival rate, and

a distribution parameter associated with the mean information item arrival rate.

5. The method of claim 1, further including:

enabling an encoding of a protocol associated with the explicit-traffic, and

wherein

the determination of properties associated with the propagation of the explicit-traffic is further dependent upon an effect of the associated protocol.

6. The method of claim 1, further including:

enabling an encoding of a first time-parameter that is associated with the background-traffic parameters, and

enabling an encoding of a second time-parameter that is associated with the explicit-traffic, and

wherein

the determination of properties associated with the propagation of the explicit-traffic is further based on the first time-parameter and the second time-parameter.

7. The method of claim 1, wherein the enabling of the determination of the properties associated with the propagation of the explicit-traffic includes:

enabling a determination of a scheduled time that is associated with an explicit event that is associated with the explicit-traffic,

enabling a determination of an anticipation time based on the scheduled time,

enabling a determination of a composite background effect at the anticipation time based on the one or more background-traffic parameters,

enabling a determination of the implicit-traffic events that is based on the one or more background-traffic parameters, and

enabling the determination of the properties associated with the propagation of the explicit-traffic in dependence upon the implicit-traffic events.

8. The method of claim 7, wherein enabling the determination of the composite background effect at the anticipation time includes:

enabling a determination of a steady-state background effect, and

enabling a determination of the composite background effect at the anticipation time based on a function that asymptotically approaches the steady-state background effect.

9. The method of claim 1, wherein

the determination of the effect of the one or more background-traffic parameters includes:

a steady-state analysis of the network architecture based on the one or more background-traffic parameters, and

a particularization of implicit-traffic corresponding to the one or more background-traffic parameters, and

wherein

the effect is determined from at least one of the steady-state analysis and the particularization of implicit-traffic.

10. A simulator comprising:

an explicit-event generator that is configured to generate an explicit-event and an associated explicit-event time,

an analytic model processor that is configured to provide a background simulation state in the vicinity of the explicit-event time, based on at least one background-traffic parameter,

a discrete simulator that is configured to apply the explicit-event to an element model to determine an explicit-event-output and an associated explicit-event-output time that is dependent upon the explicit-event time and the background simulation state.

11. The simulator of claim 10, wherein

the at least one background-traffic parameter is a parameter of a stochastic process, and

the analytic model processor is configured to provide the background stimulation state based on the stochastic process.

12. The simulator of claim 10, further including

an implicit-event generator that is configured to generate an implicit-event and an associated implicit-event time, based on the at least one background-traffic parameter,

wherein:

the discrete simulator is further configured to apply the implicit-event to the element model to determine an implicit-event-output, and is configured to determine the explicit-event-output in further dependence upon the implicit-event-output.

13. The simulator of claim 12, wherein

the at least one background-traffic parameter is a parameter of a stochastic process, and

the implicit-event generator is configured to generate the implicit-event and the implicit-event time based on the stochastic process.

14. The simulator of claim 13, wherein

the parameter of the stochastic process is associated with information items, and includes at least one of:

a mean information item size,

a distribution parameter associated with the mean information item size,

a mean information item arrival rate, and

a distribution parameter associated with the mean information item arrival rate.

15. The simulator of claim 10, wherein the simulator is configured to evaluate a performance parameter of a network architecture,

the network architecture comprising a first element, a second element, and a link path between the first and the second elements,

the discrete event corresponding to an arrival of an information item at the first element at the discrete event time,

the background simulation state corresponding to a quantity of other information items being communicated between the first element and the second element via the link,

the element model corresponding to the first element and comprising

an input queue model having an initial queue length that is dependent upon the background simulation state, and

a processing model that determines the explicit-event-output and the explicit-event-output time based on the explicit-event time and the initial queue length, and

wherein

the performance parameter is dependent upon a difference between the explicit-event-output time and the explicit-event time.

16. A method of enabling a determination of a performance parameter associated with a network, the network comprising a plurality of elements and at least one link path between two elements of the plurality of elements, the method comprising:

defining a first background-traffic load on the link path via a first set of stochastic traffic parameters,

defining a second background-traffic load on the link path via a second set of stochastic traffic parameters,

defining a first time duration and a second time duration,

evaluating the performance parameter based on a stochastic process having the first set of stochastic traffic parameters during the first time duration, and having the second set of stochastic traffic parameters during the second time duration.

17. The method of claim 16, further including:

determining a first set of steady-state conditions based on the first background-traffic load,

determining a second set of steady-state conditions based on the second background-traffic load, and

evaluating the performance parameter based on a continuous change from the first set of steady-state conditions and the second set of steady-state conditions during a third time duration corresponding to a transition from the first time duration to the second time duration.

18. The method of claim 16, wherein

the stochastic process corresponds to a processing of information items, and

each of the first set and the second set of stochastic traffic parameters is associated with the information items, and includes at least one of:

a mean information item size,

a distribution parameter associated with the mean information item size,

a mean information item arrival rate, and

a distribution parameter associated with the mean information item arrival rate, and

the performance parameter is associated with a throughput parameter associated with the processing of the information items.

19. A network simulator comprising:

a simulation database that includes;

a model of a network that includes elements and links between elements,

background-traffic parameters that characterize background-traffic among the elements,

explicit-traffic parameters that characterize explicit-traffic among the elements;

a controller that is configured to control the network simulator, including control of a simulation time;

an explicit event generator that is configured to generate explicit events at scheduled simulation times, based on the explicit-traffic parameters;

an analytic model processor that is configured to determine steady-state conditions at the links between elements at select times, based on the background-traffic parameters;

an implicit event generator that is configured to generate implicit events at scheduled simulation times, based upon the steady-state conditions; and

a discrete event simulator that is configured to also generate explicit events at scheduled simulation times, based on the processing of the implicit events and explicit events at the elements;

wherein

the controller is configured to provide the select times to the analytic model processor based on the scheduled simulation times of the explicit event, and

the implicit event generator is configured to generate the implicit events in advance of the scheduled simulation times, so that processing of the explicit events at the elements includes effects caused by the background-traffic.

20. A method of simulating explicit-traffic in a network, comprising:

defining background-traffic that may affect traffic flow among elements of the network,

scheduling discrete explicit-traffic events in the network, based on the explicit-traffic,

scheduling discrete implicit-traffic events in the network preceding one or more of the explicit-traffic events, based on an analytic processing of the background-traffic,

simulating effects of the discrete implicit-traffic events before the explicit-traffic events, to define states of elements in the network upon occurrence of the explicit-traffic events, and

simulating effects of the discrete explicit-traffic events, based on the states of the elements in the network.