Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-07-24
2004-11-16
Thomson, William (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S013000, C703S017000, C703S021000, C703S022000, C702S182000, C702S186000, C702S179000, C702S181000
Reexamination Certificate
active
06820042
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of network systems, and in particular to the simulation of network architectures and configurations to evaluate performance.
2. Description of Related Art
Modeling is a proven technique for estimating the performance of systems. Such modeling is typically based on models of the components of the system and the interactions among components. In a typical performance model, the architecture of the system is encoded as a network of interconnected elements. Each element includes input and output nodes, and a corresponding functional model that describes the production of output node values, based on the input node values, and the state of the element. The network description specifies the interconnections among the input and output nodes of the elements comprising the system. The specification of the interconnections, or links, determines the correspondence between the output node values of each element to the input nodes of other elements.
An analytical evaluation of the performance of the modeled system is effected by specifying a set of initial conditions, if any, to each element, and a set of input values or parameters to the input nodes of the system. Various modeling techniques may be employed, depending upon the function of the system being modeled and the performance factors of interest. Information processing and communications systems are often modeled using stochastic models that describe the information transfer via a statistical generalization of the information being transferred and the performance and limitations of each element and link of the system. For example, an input to a processing element is described using statistics that describe an expected pattern of inputs, such as, for example, an average arrival rate of new messages, an average size of each message, and so on. Similarly, the capability of the processing element is described in terms of the average throughput rate, maximum queue length, and so on. The determination of the output characteristics of each processing element is typically based on classical “Queuing Theory” models that can provide estimates of delay time, queue size, and other parameters associated with a sequential process. As is known in the art, queuing theory models provide a “steady-state” estimate of these output parameters. That is, statistically, if an average number of items having an average number of units arrives at a element that can process an average number of units per unit time, the output of the element will be an average number of items having an average processing delay relative to the input, the element itself will have an average queue length, and so on. Of particular significance, because the analytical model provides a “steady-state” estimate, the initial conditions of the system are not significant, because any out-of-the ordinary effects of initial conditions can be expected to diminish in time, as the system approaches the steady-state condition.
The analytical model processing system computes the results associated with each element, based on the element model, or transfer equation. Because one element's computed output may affect another elements input, as determined by the interconnections within the modeled system, this computation is repeated until each of the elements provides a stable output. This process is similar to a conventional “spread sheet” program that computes the overall effect of a change to a value of a cell in the spread sheet by repeatedly processing the equations associated with the spread sheet until the effect of the changed value, if any, is reflected in every cell.
In the field of network simulations, analytical modeling techniques are particularly well suited for estimating such parameters as: a link utilization factor that identifies the volume of traffic flowing in each link, relative to the size, or bandwidth, of each link; a network latency factor associated with each pair of nodes in the network that identifies a composite of queuing delays, processing delays, and path delays between any two nodes in the network; and so on.
Analytical models, however, are not well suited for assessing the effects of protocol handling, including, for example, the effects of the segmentation of information items into packets, congestion control and packet discarding, retransmissions, weighted fairness algorithms, and so on. In like manner, the steady-state analytical models do not address the dynamics of traffic patterns nor, as mentioned above, the effects of initial or abnormal conditions. The steady-state analytical models primarily rely on traffic volume to determine the aforementioned link utilization and network latency performance measures. Also, the analytical modeling of the extremes of behavior is substantially more complex than merely modeling the average behavior, and the determination of such parameters as the peak delay time, or a profile of response times, in general, is rarely available using analytical models.
An alternative to analytical modeling is discrete-event simulation. In a discrete-event simulation, the network is also modeled using elements and links that interconnect elements, but the models utilized for each element are designed to provide a specific output response to a specific input event, rather than a statistical model. That is, for example, a model of a transmitter includes a model of a queue to receive a group of packets corresponding to an information item, and an output generator that removes each packet from the queue and places it at its output after a specified processing time, at the transmitter's transmission rate. If additional packets arrive at the transmitter's input, they are placed in the modeled queue, and wait their turn to be transmitted. Statistical parameters, such as the average number of packets in the transmitter's queue, are determined by periodically monitoring the modeled queue to determine the actual number of packets that are in the queue at each monitored time. The packets that are placed at the output node of an element are propagated via the interconnection links, and arrive at the node at the other end of the link after a propagation delay associated with the link. Upon arrival, the packets are each similarly processed by the model associated with the receiving element.
Because discrete events are modeled, the models associated with each element or link can be explicit, and need not contain a closed-form analytical model. For example, the aforementioned transmitter may have alternative transmission paths for communicating each packet, based on a destination address contained within the packet. The transmitter model need merely contain a conditional statement that places each packet in the queue onto the appropriate output, based on the destination address of each packet. In like manner, the effects of transmission errors can be modeled by randomly introducing errors into each packet, depending upon parameters associated with the elements or links. A receiving device can be modeled to reject a packet if the number of randomly introduced errors exceed a given threshold, and the transmitter can be modeled to effect a retransmission of the packet upon notification of the rejection. In this manner, the actual packet throughput in the presence of random noise can be determined based on simulated packet transmissions in the presence of simulated noise. Depending upon the level of detail of the model, packet transformations can also be modeled, for example, by modeling a packet as it is processed by its associated protocol. For example, using the ISO-OSI protocol reference model, packets may be generated at an application layer and transformed through the various layers until the simulation models the transfer of bits at the physical layer. At each stage of the transformation, processing and queue delays may be introduced, error detection and processing may be modeled, and so on. Attempting to model such explicit behavior in a closed
Cathey George
Cohen Alain
Malloy Patrick J.
McDermott Robert M.
Opnet Technologies
Thomson William
LandOfFree
Mixed mode network simulator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mixed mode network simulator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixed mode network simulator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277043