Network Modeling and Simulation

1. Overview
2. Research Agenda
3. Participants
4. Major Publications
5. Funding Source
6. Related Links

Overview

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) 

Participants

• Daniel Chi (M.S.E. 2005)
• Hwangnam Kim (Ph.D. 2005)
• Luke Kung (Ph.D. Pre-candidate)
• hyuk Lim (Postdoc 2003-2006)
• Ahmed Sobeih (Ph.D. candidate)

Major Publications

1. Hwangnam Kim and Chao-Ju Hou, ``How good is fluid simulation for simulating IEEE 802.11 operated WLANs?'' Proc. 2003 SCS Western Multiconference on Computer Simulation -- communication networks and distributed systems modeling and simulation conference, January 2003.
2. Hwangnam Kim and Chao-Ju Hou, ``Improving protocol capacity with model-based frame scheduling in IEEE 802.11-operated WLANs,'' Proc. ACM MobiCom, September 2003 (acceptance ratio = 9.6%).
3. Hwangnam Kim and Chao-Ju Hou, ``Network calculus based simulation: theorems, implementation, and evaluation,'' IEEE INFOCOM 2004, March 2004 (acceptance ratio = ~18%).
4. Hwangnam Kim and Chao-Ju Hou, ``Throughput analysis for IEEE 802.11-operated WLANs: mathematical modeling and its application to fluid model based simulation," ACM SIGMETRICS 2004, June 2004 (acceptance ratio = ~12%).
5. Hwangnam Kim, Hyuk Lim, and Jennifer C. Hou, "Network invariant-based fast simulation for large scale TCP/IP networks," submitted to ACM SIGCOMM 2004, February 2004.
6. Ahmed Sobeih, Jennifer C. Hou, and Mahesh Viswanathan, "Check and Simulate: A Case for Incorporating Model Checking in Network Simulation," Proc. 2nd ACM-IEEE Int'l Conf. on Formal Methods and Models for Codesign, June 2004.
7. Ahmed Sobeih, Wei-Peng Chen, Jennifer C. Hou, Lu-Chuan Kung, Ning Li, Hyuk Lim, Honghai Zhang, ``J-Sim: a simulation and emulation environment for wireless sensor networks,'' Proc. 38th Annual Simulation Symposium, April 2005, San Diego, CA.
8. Hung-Ying Tyan, Ahmed Sobeih, and Jennifer C. Hou, ``Towards composable and extensible network simulation,'' Proc. of NSF Next Generation Software Program Annual Meeting, in conjuction with IEEE International Parallel and Distributed Processing Symposium (IPDPS), Denver, Colorado, April 2005 (invited paper).
9. Chunyu Hu and Jennifer C. Hou, ``A reactive channel model for expediting wireless network simulation,'' Proc. ACM SIGMETRICS poster session, June 2005 (31 full papers and 23 posters out of 237 submissions).
10. Hwangnam Kim and Jennifer C. Hou, ``Mixed-mode simulation for IEEE 802.11-operated WLANs: achieving the best of all worlds performance'' Proc. International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2005), July 2005.
11. Ahmed Sobeih, Mahesh Viswanathan, Darko Marinov, and Jennifer C. Hou, "Finding bugs in network protocols using simulation code and protocol-specific heuristics," Proc. of Seventh International Conference on Formal Engineering Methods (ICFEM 2005), November 2005.
12. Hwangnam Kim, Hyuk Lim, and Jennifer C. Hou, " Accelerating simulation of large-scale IP networks: an network invariant preserving approach," Proc. of IEEE INFOCOM 2006, March 2006 (acceptance ratio = 18%).
13. Ahmed Sobeih, Wei-Peng Chen, Jennifer C. Hou, Lu-Chuan Kung, Ning Li, Hyuk Lim, Hung-Ying Tyan, and Honghai Zhang, ``J-Sim: a simulation and emulation environment for wireless sensor networks,'' IEEE Wireless Communications Magazine, Vol. 13, No. 4, pp. 104--119, August 2006.
14. Ahmed Sobeih, Mahesh Viswanathan, Darko Marinov and Jennifer C. Hou, "J-Sim: An Integrated Environment for Simulation and Model Checking of Network Protocols," Proc. of IEEE International Symposium on Parallel and Distributed Processing (IEEE IPDPS 2007), NSF Next Generation Software Program Workshop, Long Beach, CA, March 2007 (invited).
15. Hwangnam Kim and Jennifer C. Hou, ``Mixed mode simulation for IEEE 802.11-operated WLANs: integration of packet mode and fluid model based simulation'', Computer Networks, Vol.51, No. 6, Pages 1379--1402, April 2007.
16. Hung-Ying Tyan, Ahmed Sobeih and Jennifer C. Hou, ``Design, ralization, and evaluation of a component-based, compositional network simulation environment,'' conditionally accepted for publicatoin in Simulation: Transaction of the Society for Modeling and Simulation International, July 2007.

Demo and Software Release

Funding Source

Related Links

• Computer Networks Research Groups at University of Masschusetts, Amherst
  led by Professsors Jim Kurose and Don Towsley
  1. Fluid models for Large, Heterogenous Networks to develop novel fluid-based methodologies that will enable the solution of large networks handl ing large numbers of responsive flows (e.g., TCP) and non-responsive flows (e.g., video)
  2. Fluid simulation to propose to perform fundamental research on developing a fluid simulation methodology that will enable efficient, multi-time-scale, hierarchical performance modeling of complex networks such as the next generation Internet
• Modeling Of SEcurity and Systems at University of Illinois, Urbana-Champaign
  led by Professor David M. Nicole
  1. Temporal-Spatio Analysis of the Global internet to consider both spatial scales (having to do with physical resolution of models) and time scales. The SSFNet network simulation package is a visable result of their work, in which they partner closely with the Renesys Corporation
  2. Network Simulation for Cyber-attack Exercise Scenarios to build the simulation infrastructure needed for detailed high performance network simulations used in scenario-based exercises (e.g. TOPOFF)
• Wireless Networking and Communications Group (WNCG) at University of Texas, Austin
  led by Professor Sanjay Shakkottai
  1. Network Architectures, Software, and Protocol Performance to research various aspects of traffic engineering, network planning and pricing of communication services, resource management, network modeling and control, as well as methodologies for large- scale network simulation

Detailed Description of Research Agenda

Fluid model-based simulation has been proposed as a solution to alleviate the computational overhead in large scale network simulation. In fluid model-based simulation, a cluster of closely-spaced packets is modeled as a fluid chunk at a specific time point, and the behavior that a fluid chunk exhibits is characterized by a set of mathematical models (usually differential equations) in the time domain. A fluid model-based simulator then keeps track of fluid chunks and their rate changes at each network component on the communication path from the source to the destination. As a large number of packets are abstracted as a single fluid chunk, the computational overhead is expected to be lessoned. Fluid models have been also used to study the throughput behavior of TCP and congestion control algorithms, together with active queue management in the steady state. These fluid models, when applied in fluid model-based simulation, have been shown to expedite simulation performance.

What 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

(a) The total number of received packets versus packet size when the number of nodes is 100

(b) The total number of received packets versus the number of nodes  when packet size is 25 bytes

(2) Performance gain

(a) The total number of received packets versus packet size when the number of nodes is 100

(b) The total number of received packets versus the number of nodes when packet size is 25 bytes

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:

Simulation results:

(1) Network configuration

 The total number of packets received during 1000 seconds versus the number of nodes

• Drop-tail case:
  

• RED case:

(3) Error discrepancy in terms of queue dynamics

Queue dynamics in case when # of nodes is 20

• Drop Tail case

• RED case

Execution time required to carry out a 1000-second simulation run versus # of nodes

• Drop Tail case

• RED case

(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 t_f(j) denote the arrival time of the j^th flowchunk packet and t_f(j+1) - t_f(j) = h. A flowchunk packet that arrives at the j^th timestep carries information about the background flow from time t_f(j) to t_f(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, q_f(t) the estimate of the number of background packets in the queue at time t, r_b the rate of background traffic, and r_sb the proportional service rate received by background packets. Then we can characterize the queue occupancy at the time, t_i+1, when the i+1^th foreground packet event occurs in [t_f(j), t_f(j+1)] as

Note that t_i, t_i+1 denote the time instants when foreground packet events occur in between the arrivals of two fluidchunk packets, i.e. t_f(j) <= t_i < t_i+1 <= t_f(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:

• (i) How do we capture the effect of the foreground traffic in the fluid model that characterizes the background traffic (and vice versa)? In particular, how should the flow rate of the fluid model be adjusted in the case of buffer overflow and packet losses?
• (ii) Is the error that results from mixed-mode simulation bounded? Intuitively mixed-mode simulation will suffer from a higher probability of error when the traffic is bursty, because packets in a fluid chunk are assumed to be {\em evenly} spaced. We will analyze errors incurred in worst-case scenarios in which the background packets that are captured in a fluid chunk packet all arrive in bursts at the beginning (or end) of a fluid chuck period.

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.