This blog is subject the DISCLAIMER below.

Wednesday, January 20, 2010

Discrete Event Simulators : Simulating Networks

I've been told that this article doesn't present *why* we need discrete event simulators, or what is the problem solved by them.
The problem is, for one example, consider you are developing a peer to peer program, like bittorrent, and you want to try it to see how good it works when 1000 users run it. You can get 1000 of your friends and they'd start the program and there you go (Or use PlanetLab). However if there were a bug, you'd be completely lost how to debug it. Discrete event simulators, "simulate" that there is 1000 users (or more, if you want) on your machine. More than that, they are all in the same "process/thread". So it boils down to a single-threaded application that is so much easier to debug.
Another example is to test a network protocol for example (see NS-2 simulator). You want to modify the "IP" protocol and want to simulate a network of hosts and routers and switches instead of implementing it on the hardware level and testing it in real life. That's what discrete event simulators are useful for.

If you are familiar with windows event loop of event-driven applications (GUI, sockets), you know that pretty much applications can be defined in terms of events. We consider here network applications which are mostly defined by a "receive-message" event.

You write your network application and depend on a receive event as a black box to receive messages (ref: Apache Mina). Imagine now we have the same application but we just replaced that black box, instead of the OS socket APIs, we replaced it with a discrete event simulator of the same exact interface.

That interface is just the function send(msg) and a callback function that you provide called receive(msg).

Instead of having the sender and receiver on different machines, they both will be on the same machine and in the same application (it's a "simulation", you want to test them as "if" they were on a real network).

The first application calls send() unsuspectingly, and then the discrete event simulator instead of calling OS APIs to send it on the network card, he just creates a corresponding reception event in the second (receiving) application. And then the second application gets a callback that he has got a message from the first application.

This view is simplified a little bit. We want to model network delay and bandwidth constraints, especially if we are going to simulate3000 peers of bit-torrent for example. There is ns-2, which simulates these metrics using a complete IP stack implementation (IP/TCP). It splits messages into packets, and simulates routers and so . NS-2 is used to test real protocols like WiFi and routing algorithms. However its over head is unacceptable if we want to consider a peer to peer network of 1000 peers (running on the same machine).

Some approaches like peersim, models delay as a random function and not bandwidth. However there are other approaches like MyP2PWorld[1] that models bandwidth but obtains efficiency from approximating the bandwidth constraints on the "message" level not the packet level.

Most discrete event simulators are not designed to test a deployable system and requires implementation using it's own interfaces and tools and then you transform that into a real application. MyP2PWorld[1] was designed to adapt the Apache Mina interface (used in real application). So you can write you own deployable peer to peer application using Apache Mina (event-driven networking), and with a flip of a boolean variable, you test it on a discrete event simulator. So your code you use in simulation is the same code used in deployment.

[1] Roberto Roverso, Mohammed Al-Aggan, Amgad Naiem, Andreas Dahlstrom, Sameh El-Ansary, Mohammed El-Beltagy, Seif Haridi: MyP2PWorld: Highly Reproducible Application-Level Emulation of P2P Systems. SASO Workshops 2008:272-277

.. more.