|
|||||||||
 |
|||||||||
|
|
||||||||||||||||
| |
||||||||||||||||
Network modeling and simulation
Modern data communication networks are extremely complex
and do not
lend well to theoretical analysis. It is common that network analysis
can be rigorously made after leaving out several (sometimes subtle)
details that cannot be easily captured in the analysis. Instead
packet-level, event-driven simulation studies are usually carried out
to better study the performance of network components, algorithms and
protocols, and their interaction. The main obstacle in packet-level
network simulation is, however, the vast number of packets that have
to be simulated in order to produce accurate results. Each packet will
generate a number of events (e.g., arrival of a packet at the router,
its departure, and the event that a queue becomes empty, just to name
a few) on the path from the source to the destination and each event
has to be executed at some specified time point. As the CPU time
required is roughly proportional to the number of events that have to
be executed, packet-level simulation easily becomes computationally
expensive, if not infeasible, for simulating large-scale networks.
Research Agenda (click here for details)
What seems to be reasonable is really to combine theoretical modeling with packet-level simulation so as to exploit the advantages of both techniques, while not significantly suffering from their drawbacks. The main intent of this project is thus to examine the feasibility of leveraging theoretical theories in large scale network simulation. Specifically we focus on
(1) Fluid
model-based simulation
(2) Network calculus-based simulation
(3) Rescaling-based simulation
(new, unfunded)
(4) Mixed mode simulation (new.
unfunded)
(5) Network emulation (new,
partially funded)
(6) Marriage made in J-Sim:
Integration of model checking with simulation (new, unfunded)
Detailed Description of Research Agenda
(1) Fluid model-based simulationWhat is not clear is whether or not the notion of fluid-model based simulation can be applied to analyze the behavior of network protocols in other layers. In this part of the project, we aim to investigate whether or not fluid-model based simulation is effective in simulating IEEE 802.11-operated WLANs and to develop such a simulation framework to expedite simulation, while not compromising the accuracy and fidelity of simulation results.
Specifically, we first abstract a large number of packets as a single fluid chunk, and develop analytical models to fully characterizes their operational behaviors in IEEE 802.11-operated WLANs. As compared to several existing IEEE 802.11 models, our derived models take into consideration of protocol details --- especially the system parameters specified in the IEEE 802.11 standard and the throughput overhead imposed by the physical and MAC layers, include both the cases in which the RTS/CTS mechanism is and is not employed, and characterize the binary backoff window behavior. In addition, they do not rest on any assumption on the input traffic. Another salient feature is that as compared to other existing analytical models, our derived models are better-suited for fluid-model based simulation, as it does not require as the input parameters that characterize packet level dynamics. We validate the model by comparing the numerical results against simulation results in J-Sim under a wide spectrum of traffic loads.
With the derived models, we then implement, based on the
notion of
fluid model-based simulation and with the use of the time stepped
simulation technique, the fast simulation framework for IEEE
802.11-operated WLANs in J-Sim. We conduct a comprehensive
simulation study to evaluate the performance of the simulation
framework, in terms of errors incurred in approximating a large number
of packets as a single fluid chunk, and degree of speed-up thus
achieved. Simulation results indicate that the proposed framework is
quite effective in studying transmission activities in WLANs equipped
with IEEE 802.11. The performance in terms of execution time improves
significantly, as the number of wireless nodes, traffic load (the
number of applications per node or the packet rate of each
application), and/or the number of WLANs within a network to be
simulated increases, and can be as significant as 100 times as
compared to packet-level simulation. The relative errors incurred
with the use of time stepping technique, on the other hand, fall
within 2%, as long as time step value is appropriately determined.
Simulation environment: all the simulations are
conducted on Linux 2.4.18 on a Pentium 4-1.9 Ghz PC with 1 GBytes
memory memory and with 2 GBytes swap memory. Each simulation
run lasts for 60 simulation seconds.
Simulation results:
(1) Error discrepancy
(2) Performance gain
In the next stage of the project, we will investigate in which layer (application, transport, network, or MAC other than IEEE 802.11) fluid model-based simulation will be effective, and quantify the performance speed-up thus achieved and the approximation errors thus incurred. We will also implement all the resulting fluid-model based simulation classes in J-Sim so as to provide a simulation environment that can render high-fidelity, faster-than-real-time simulation results.
(2) Network calculus-based simulation
In spite of its effectiveness in reducing the execution time incurred in simulation, fluid model based simulation may not be well-suited in the case of light and/or sporadic traffic. This is because fluid models are derived based on the assumption of existence of a large number of flows.
To tackle this problem, we propose to use network calculus models as an alternative to fluid models. Note that network calculus is grounded on the mathematical theory of Min-Plus (or Max-Plus algebra) and does not usually make the assumption of existence of a large number of flows. Specifically, we examine the feasibility of incorporating network calculus based models in simulating TCP/IP networks. By exploiting network calculus properties, we characterize how TCP congestion control --- additive increase and multiplicative decrease (AIMD), together with the queue management strategy used in routers, regulates TCP flows. Following the same line of approaches as in fluid model based simulation, we first divide the time axis into intervals (each of which consists of multiple round-trip times), and derive a TCP AIMD throughput model which derives the attainable throughput of a TCP flow, given the number of collisions in an interval. Then based on the derived throughput model, we define a set of network calculus based theorems that give upper and lower bounds on the attainable TCP throughput in each interval. Finally, we implement network calculus (NC) based simulation in J-Sim conduct simulation in both the packet mode and the network calculus-based mode, and measure the performance gain (in terms of the execution time thus reduced) and the error discrepancy (in terms of the discrepancy between NC-based simulation results and packet-level simulation results).
The simulation results indicate an order of magnitude or
more
(maximally 30 times) improvement in execution time and the performance
improvement becomes more pronounced as the network size increases (in
perspective of network capacities and number of flows). The error
discrepancy between NC-based simulation and packet-level simulation,
on the other hand, is minimally 1-2% and maximally 8-12% in a wide
spectrum of network topologies and traffic loads. The simulation
results also indicate the superiority of NC-based simulation over
fluid model based simulation (the latter realized using the time
stepped hybrid simulation (TSHS) technique). In several network
configurations, we found that fluid model based simulation not only
incurs slightly larger execution time, but also give an error
discrepancy (in the range of 5%-100%) that is several orders of
magnitude larger than that in NC-based simulation.
Simulation environment:
All the simulations are conducted on Linux 2.4.18 on a
Pentium 4-1.9 Ghz PC
with 1 GBytes memory memory
and with 2 GBytes swap
memory. Each simulation
run lasts for 1000 simulation seconds.
Simulation results:
(1) network configuration
(3) Performance gain
Execution time for 1000
simulation time versus # of nodes
(4) Comparison with TSHS simulation
Error discrepancy and
performance gain among packet level simulation,
NC-based simulation, and
TSHS simulation
(3) Rescaling-based simulation (new, unfunded)
Although network calculus-based simulation indeed gives encouraging results, it cannot provide the packet level dynamics, such as the instantaneous queue length and packet dropping probability, due to the use of network calculus. (Note that fluid model based simulation also suffers from this shortcoming.)
As such, we take a dramatic departure from the above approaches and propose a new rescaling simulation methodology (RSM) for simulating large-scale TCP/IP networks. As mentioned above, as the number of events increases with the network size and the amount of traffic, the computational cost increases accordingly. If we can scale down the network to one that can be simulated at the packet level in a short time interval to produce sufficient results and extrapolate, without loss of accuracy, results for the original network, we can significantly reduce the computational cost and yet preserve the network dynamics. Now the key issue is how to preserve the properties that characterize the original network in the downscaled network so that accurate results can be extrapolated after the packet-level simulation. In particular, the network property of interest should remain invariant in the process of scaling down and rescaling up the network.
For the purpose of simulating large-scale TCP/IP networks, we propose to use the bandwidth-delay product as the network property to be preserved, as it represents the capacity of the ``pipe,'' i.e., the amount of data packets that can be transmitted without waiting for the acknowledgment. That is, we scale down the original network by reducing the link capacity by a fraction α, increasing the link bandwidth by α, but keeping the bandwidth-delay product constant. (Note that we change neither the number of nodes/flows nor the queue (the maximum buffer size or the AQM parameters.) By preserving this product invariant during the down/up scaling operations, the network capacity as perceived by each TCP connection is preserved, and we are in the process of formally proving that the queue dynamics (e.g., the instantaneous queue length), the RTT dynamics, and the TCP window size dynamics remain unchanged in the operations.
We have also carried out a preliminary J-Sim
simulation study
comparing RSM based simulation against packet level simulation, with
respect to the capability of capturing the transient, packet-level
network dynamics, the execution time, and the discrepancy in
simulation results. The simulation results indicate an order of
magnitude or more improvement (maximally 50 times) in execution time
and the performance improvement becomes more prominent as the network
size increases (in terms of number of nodes and network capacity) or
as the scaling parameter decreases. The error discrepancy between RSM
based simulation and packet level simulation, on the contrary, is
minimally 1-2 % and maximally 10 % in a wide variety of network
topologies (with various AQM strategies) and traffic loads.
Simulation environment:
All the simulations are conducted on Linux 2.4.18 on a Pentium 4-1.9 Ghz PCSimulation results:
(1) Network configuration
(3) Error discrepancy in terms of queue dynamics
(4) Mixed mode simulation (new, unfunded)
A major drawback of theoretical model based simulation is that it trades accuracy for simulation performance. As a result, it may not be well-suited for studies in which packet-level details are of concern. To this end, we propose the notion of mixed-mode simulation to combine the performance gains of fluid-model based simulation with the accuracy afforded by packet-level simulation.
For example, in the case of studying the throughput behavior of TCP congestion control, we will lay a framework in which the foreground traffic (whose dynamic is being studied) is simulated at the packet-level and the background traffic (that comprise of possibly hundreds of flows) is modeled with a fluid model. As the first step, we will adopt the time-stepped simulation technique and capture the background traffic as ``fluid chunk packets'' that are relayed periodically. Specifically, flowchunk packets of the background traffic arrive and are processed at the queue every h time units. Let tf(j) denote the arrival time of the jth flowchunk packet and tf(j+1) - tf(j) = h. A flowchunk packet that arrives at the jth timestep carries information about the background flow from time tf(j) to tf(j+1), i.e., it carries information on future background traffic arrivals. This means that when a foreground packet, p, is to be processed, the fluid chunk that has arrived at the most recent timestep should contain a summary of traffic that will have arrived until p's arrival.
Let q(t) denote the estimate of the packet queue length at time t, qf(t) the estimate of the number of background packets in the queue at time t, rb the rate of background traffic, and rsb the proportional service rate received by background packets. Then we can characterize the queue occupancy at the time, ti+1, when the i+1th foreground packet event occurs in [tf(j), tf(j+1)] as
Note that ti, ti+1 denote the time instants when foreground packet events occur in between the arrivals of two fluidchunk packets, i.e. tf(j) <= ti < ti+1 <= tf(j+1). With the above queue characterization in place, we can then determine whether or not a packet should be dropped in the simulation, and consider the following issues:
We will design and implement necessary classes for realizing mixed-mode simulation of TCP congestion control in JavaSim, and validate the above framework and error bound derived. Should the notion of mixed-mode simulation be proven effective, we will then extend it to other layers.
(5) Network emulation (new, partially funded)
Network emulation is an inexpensive approach to testing, validating, and/or evaluating protocols/approaches in a realistic but well-controlled network environment. The protocol/mechanism to be tested is usually executed in the real environment, while other components that interact with the tested protocol/mechanism are executed in the well-controlled, virtual environment. We will realize network emulation in an top-down fashion in J-Sim by developing a Java-compliant socket layer, on top of which real applications (e.g., web browsers/servers and audio/video streams) can be ported (Figure 3). The socket layer essentially gives applications the illusion that they are interfacing with the operating system, rather than with a virtual network environment.
Figure 3. Top-down network emulation
Figure 4. Bottom-up network emulation
We will also develop techniques to interface J-Sim with real systems in a bottom-up fashion (Figure 4). That is, we will intercept real-life packets at the device driver level and transport them to J-Sim, and vice versa. We will use the packet capturing facility (e.g., pcap in Linux and Windows) to intercept real-life packets and re-direct them to a packet converter which will then convert the format of real-life packets to the format understood by J-Sim. Outbound packets will be processed by the packet converter and directed via IP raw sockets to real device drivers. With these utilities in place, we will be able to interface modeling and simulation modules with real systems, and validate on-line control systems prototype in much larger, but still well-controlled networking environments.
(6) Marriage made in J-Sim: Integration of model checking with simulation (new, unfunded)
One major deficiency of existing network simulators is that they only evaluate the performance of network protocols in several scenarios, but can not usually exhaust all the possible scenarios. If all the corner cases do not appear (and hence cannot be investigated) in the scenarios studied, subtle errors in the protocol specification/implementation may not be easily located in the simulation, and may manifest themselves after the protocol has been implemented and deployed. This could lead to serious, and sometimes disastrous, problems. For example, a routing protocol that may suffer from routing loops may cause data packets to loop in the network and not reach their destinations. Another example arises in the area of network security, where ``holes'' for security attacks may only be discovered after protocol implementation and deployment, causing severe damage to computer systems.
In the current practice, to check whether or not a network protocol contains any errors, a prototype that was specifically made for validation purpose has to be built (e.g., an interactive theorem prover and/or a model checker). This process is time-consuming, error-prone and requires tremendous efforts. An interesting question is then whether or not we can employ a single, integrated tool to provide both the performance evaluation and validation of network protocols. With such a tool, only one prototype will be built and used for the two purposes.
Motivated thus, we are in the process of extending J-Sim --- an open-source, component-based compositional network simulation environment --- with capability to explore the state space created by a network protocol until either the entire state space is explored (if the state space is finite) or an error (e.g., a violation of a user-defined safety assertion) is discovered. In this paper we will document our experiences in carrying out this research task. Note that our objective is to locate errors in the network protocol itself rather than errors in the simulation code. The basic idea is then to execute the simulation code in order to pinpoint errors in the network protocol. Specifically, we have implemented a model checker (written in Java so that it can be ready integrated with J-Sim), and incorporated this model checker into J-Sim. As a proof-of-concept, we have used the J-Sim model checker to locate errors in a simple automatic repeat request (ARQ) stop-and-wait protocol. This first step demonstrates the feasibility of integrating model checking with network simulation.
Figure 5: Overall framework of model checking in J-Sim
To carry out the above tasks, we have addressed several issues. First, we have laid a framework (Figure 5) that enables the model checker to take control of the simulation of a network protocol in order to explore the entire state space, rather than just exploring one single execution path as J-Sim does. Second we ensure that the implementation of this framework does not require the core design and implementation of J-Sim to be altered. Third, we have incorporated search techniques that are protocol specific to reduce the size of the explored state space and hence the time in detecting an error. Specifically, we make use of protocol-specific properties to reduce the size of the state space (e.g., by reducing the number of possible transitions), thereby reducing the time and/or space needed to locate a bug. We also explore how a model checker can make use of best-first search that exploits properties inherent to the network protocol being checked, in order to guide the search towards paths that can potentially locate errors in less time. As compared to the Maude Linear Temporal Logic (LTL) model checker, our framework enables discovery of errors with shorter counter examples and in quicker time. These results are encouraging because the performance of the Maude LTL model checker has been shown to be comparable to that of SPIN.
| |
|
|
 |
©Copyright 2003
University of Illionois. All Rights Reserved.
|
 |
 |
|||||
| |
|
|
 |
Contact webmaster
|
 |
