The Design and Implementation of the NCTUns 1.

0 Network
Simulator
S.Y. Wang, C.L. Chou, C.H. Huang, C.C. Hwang, Z.M. Yang, C.C. Chiou, and C.C. Lin

shieyuan@csie.nctu.edu.tw
Department of Computer Science and Information Engineering
National Chiao Tung University, Hsinchu, Taiwan

Abstract Simulation results are not as convincing as those pro-

duced by real hardware and software equipment. In
This paper presents the design and implementation of order to constrain their complexity and development
the NCTUns 1.0 network simulator, which is a high-fidelity cost, most existing network simulators can only simu-
and extensible network simulator capable of simulating late real-life network protocol implementations with
both wired and wireless IP networks. By using an enhanced limited detail, and this can lead to incorrect results. For
simulation methodology, a new simulation engine architec- example, OPNETs modeler product [1] uses a simpli-
ture, and a distributed and open-system architecture, the fied finite state machine model to model complex TCP
NCTUns 1.0 network simulator is much more powerful than protocol processing. As another example, in ns-2 [2]
its predecessor -- the Harvard network simulator, which package, it is documented that there is no dynamic
was released to the public in 1999. The NCTUns 1.0 receivers advertised window for TCP.
network simulator consists of many components. In this These simulators are not extensible in the sense that
paper, we will present the design and implementation of they lack the standard UNIX POSIX application pro-
these components and their interactions in detail. gramming interface (API). As such, existing or to-be-
Keyword: network simulator, simulation methodology developed real-life application programs cannot run
normally to generate traffic for a simulated network.
Instead, they must be rewritten to use the internal API
1. Introduction provided by the simulator (if there is any) and be com-
piled with the simulator to form a single big and com-
Network simulators implemented in software are valu- plex program. For example, since the ns-2 network
able tools for researchers to develop, test, and diagnose simulator itself is a user-level program, there is no way
network protocols. Simulation is economical because it can to let another user-level application program run on
carry out experiments without the actual hardware. It is top of it. As such, a real-life application program cannot
flexible because it can, for example, simulate a link with run normally to generate traffic for a network simulated
any bandwidth and propagation delay or a router with any by ns-2.
queue size and queue management policy. Simulation
results are easier to analyze than experimental results To overcome these problems, S.Y. Wang proposed a
because important information at critical points can be simulation methodology in [3, 4] and used it to implement
easily logged to help researchers diagnose network proto- the Harvard network simulator. The Harvard network simu-
cols. lator has two desirable properties as follows. First, it uses
the real-life UNIX TCP/IP protocol stack, real-life network
Network simulators, however, have their limitations. A application programs, and real-life network utility
complete network simulator needs to simulate networking programs. As such, it can generate more accurate simulation
devices (e.g., hosts and routers) and application programs results than a traditional TCP/IP network simulator that
that generate network traffic. It also needs to provide abstracts a lot away from a real-life TCP/IP implementation.
network utility programs to configure, monitor, and gather Second, it lets the system default UNIX POSIX API (i.e.,
statistics about a simulated network. Therefore, developing the standard UNIX system call interface) be provided on
a complete network simulator is a large effort. Due to every node in a simulated network. Any real-life UNIX
limited development resources, traditional network simula- application program, either existing or to be developed, thus
tors usually have the following drawbacks: can run normally on any node in a simulated network to
generate traffic. One important advantage of this property is
that since an application program that is developed for

1
simulation study is a real UNIX program, the programs that configure, monitor, or gather statistics about a simu-
simulation implementation can be its real implementation lated network, the TCP/IP protocol implementation on
on a UNIX machine. As such, when the simulation study is hosts, the IP protocol implementation on routers, and links
finished, we can quickly implement the real system by are all compiled together to form a single user-level
reusing its simulation implementation. program. Due to the enormous complexity, such a simulator
tends to be difficult to develop and verify. In addition, a
Although the methodology proposed in [3, 4] can simulator constructed using this approach cannot provide
provide the above two advantages, it has several limitations UNIX POSIX API for real-life application programs to run
and drawbacks. To remove these problems, we enhanced normally to generate network traffic. Although some simu-
the methodology, designed a new simulation engine archi- lators may provide their own internal API, real-life applica-
tecture, and used these improvements to develop a new tion programs still need to be rewritten so that they can use
network simulator called the NCTUns 1.0 network simu- the internal API, be compiled with the simulator success-
lator. In the rest of the paper, we will present these fully, and be concurrently executed with the simulator
enhancements as well as the features, components, design, during simulation.
and implementation of the NCTUns 1.0 network simulator.
ENTRAPID [9] uses another approach. It uses the
virtual machine concept [13] to provide multiple virtual
2. Related Work
kernels on a physical machine. Each virtual kernel is a
The predecessor of the NCTUns 1.0 is the Harvard process and simulates a node in a simulated network. The
network simulator [5], which was authored by S.Y. Wang in system calls issued by an application program are redirected
1999. Since its release in July 1999, as of January 1, 2002, to a virtual kernel. As such, UNIX POSIX API can be
the Harvard network simulator has been downloaded by provided by ENTRAPID and real-life application programs
more than 2,000 universities, research institutions, indus- can be run in separate address space normally. However,
trial research laboratories, and ISPs. because the complex kernel needs to be ported to and imple-
mented at the user level, many involved subsystems (e.g.,
As feedback about using the Harvard network simu- the file, disk I/O, process scheduling, inter-process commu-
lator gradually comes back, it becomes clear that the nication, virtual memory subsystems) need to be modified
Harvard network simulator has several limitations and extensively. As such, the porting effort is very large and the
drawbacks that need to be overcome and solved. Also, it is correctness of the ported system may need to be extensively
clear that some useful features and functions need to be verified.
implemented and added to it. For these reasons, S.Y. Wang
decided to develop the NCTUns 1.0.
3. High Level Architecture
In the literature, some approaches also use a real-life
TCP/IP protocol stack to generate results [6, 7, 8, 9, 10]. The NCTUns 1.0 uses a distributed architecture to
However, unlike our approach, these approaches are used support remote simulations and concurrent simulations. It
for emulation purposes, rather than for simulation purposes. also uses an open-system architecture to enable protocol
Among these approaches, Dummynet [10] most resembles modules to be easily added to the simulator. Functionally, it
our simulator. Both Dummynet and our simulator use tunnel can be divided into eight separate components described
interfaces to use the real-life TCP/IP protocol stack on the below:
simulation machine. However, there are some fundamental The first component is the fully-integrated GUI environ-
differences. Dummynet uses the real time, rather than the ment by which a user can edit a network topology, con-
simulated network's virtual time. Thus the simulated link figure the protocol modules used inside a network node,
bandwidth is a function of the simulation speed and the total specify mobile nodes' moving paths, plot performance
load on the simulation machine. As the number of simulated curves, play back animations of logged packet transfers,
links increases, the highest link bandwidth that can be simu- etc.
lated decreases. Moreover, in Dummynet, routing tables are
From a network topology, the GUI program can
associated with incoming links rather than with nodes. As
generate a simulation job description file suite. Since the
such, the simulator does not know how to route packets
GUI program uses Internet TCP/IP sockets to communi-
generated by a router, as they do not come from any link
cate with other components, it can submit a job to a
OPNET, REAL [11], ns-2, and SSFnet [12] represent remote simulation machine for execution. When the
the traditional network simulation approach. In this simulation is finished, the simulation results and gener-
approach, the thread-supporting event scheduler, applica- ated log files are transferred back to the GUI program.
tion programs that generate network traffic, utility programs The user then can either examine logged data, plot

2
 performance curves, or play back packet transfer anima- as a background job. Background jobs are managed by
tions, etc. the dispatcher. Various scheduling policies can be used
to schedule their service order.
While a simulation is running at the remote simulation
The fifth component is the coordinator. which is a user-
machine, the user can query or set an objects value at
level program. On every machine where a simulation
any time. For example, the user may query or set the
server program resides, a coordinator program needs to
routing table of a router or the switch table of a switch at
be executed and remain alive. Its task is to let the job
any time. If the user does not want to do any query or set
dispatcher know whether this machine is currently busy
operation during a simulation, the user can choose to
running a simulation or not. When executed, it immedi-
disconnect the currently running simulation so that he
ately registers itself with the dispatcher to join the dis-
(she) can use the GUI program to handle other simula-
patchers simulation machine farm. Later on, when its
tion cases. The user can later reconnect to a discon-
status (idle or busy) changes, it will notify the dispatcher
nected simulation at any time, whether it is still running
of its new status. This enables the dispatcher to choose
or has finished. A user thus can submit many simulation
an available machine from its machine farm to service a
jobs in a short period of time. This can increase simula-
job.
tion throughput if there are many simulation machines
available to service these jobs concurrently. When the coordinator receives a job from the
dispatcher, it forks (executes) a simulation server to
The second component is the simulation engine. A sim-
simulate the specified network and protocols. At certain
ulation engine is a user-level program. It functions like a
times during a simulation, the coordinator may also fork
small operating system. Through a defined API, it pro-
(start) or kill (end) some real-life application programs,
vides useful and basic simulation services to protocol
which are specified in the job to generate traffic for the
modules (to be described soon). Such services include
simulated network. Because the coordinator has the
virtual clock maintenance, timer management, event
process IDs of these forked traffic generators, the coor-
scheduling, variable registrations, etc. The simulation
dinator passes these process IDs into the kernel to
engine needs to be compiled with various protocol mod-
register these traffic generators with the kernel. From
ules to form a single user-level program, which we call
now on, all time-related system calls issued by these
the simulation server. When executed to service a job,
registered traffic generators will be performed based on
the simulation server takes a simulation job description
the virtual time of the simulated network, rather than the
file suite as its input, runs the simulation, and generates
real time.
data and packet transfer log files as its output. When a
simulation server is running, because it needs to use a When the simulation server is running, the coordinator
lot of kernel resources, no other simulation server can be communicates with the job dispatcher and the GUI
running at the same time. program on behalf of the simulation server. For
example, periodically the simulation server sends the
The third component is various protocol modules. A
current virtual time of the simulated network to the
protocol module is like a layer of a protocol stack. It
coordinator. The coordinator then forwards this infor-
performs a specific protocol or function. For example,
mation to the GUI program. This enables the GUI user
the ARP protocol or a FIFO queue is implemented as a
to know the progress of the simulation. During a simula-
protocol module. A protocol module is composed of a
tion, the user can also on-line set or get an objects value
set of functions. It needs to be compiled with the simula-
(e.g., to query or set a switchs switch table). Message
tion engine to form a simulation server. Inside the simu-
exchanges happening between the simulation server and
lation server, multiple protocol modules can be linked
the GUI program are all done via the coordinator.
into a chain to form a protocol stack.
The sixth component is the modifications that need to be
The fourth component is the simulation job dispatcher,
made to the kernel of the simulation machine so that a
which is a user-level program. It should be executed and
simulation server can correctly run on it. For example,
remain alive all the time to manage multiple simulation
during a simulation, the timers of TCP connections used
machines. We use it to support concurrent simulations
in the simulated network need to be triggered by the vir-
on multiple simulation machines. The job dispatcher can
tual time rather than by the real time.
operate between a large number of GUI users and a
large number of simulation machines. When a user sub- The seventh component is various protocol daemons
mits a simulation job to the job dispatcher, the dis- (programs) running at the user level. Like the routing
patcher will select an available simulation machine to daemon routed or gated running on UNIX machines
service this job. If there is no available machine at this that exchange routing messages and set up system rout-
time, the submitted job can be queued in the dispatcher ing tables, when the NCTUns 1.0 is running to simulate

3
 a network, some protocol daemons can run at the user user who has only one machine. Due to the nature of the
level to perform specific jobs. For example, the real-life Inter-Process Communication (IPC) design, the NCTUns
routed (using the RIP routing protocol) or gated 1.0 can be used for either mode without changing its
(using the OSPF routing protocol) daemons can run program code. Only the mode parameter in its configuration
with the NCTUns 1.0 to set up the routing tables used file needs to be changed.
by the routers in a simulated network.
The last component is all real-life application programs 4. Design and Implementation
running at the user level. As stated previously, any real-
life user-level application program can run on a simu- 4.1. Fully-Integrated GUI Environment
lated network to either generate network traffic, config-
ure network, or monitor network traffic, etc. For The NCTUns 1.0 has a fully-integrated GUI environ-
example, the tcpdump program can run on a simulated ment by which a user can easily perform simulation studies.
network to capture packets flowing over a link and the The GUI program is composed of four main components. In
traceroute program can run on a simulated network to the following, we will present each of them.
find out the routing path traversed by a packet.
The first component is the topology editor, which is
Figure 1 depicts the distributed architecture of the shown in Figure 2. The topology editor provides a conve-
NCTUns 1.0. It shows that, due to the nature of the distrib- nient and intuitive way to graphically construct a network
uted architecture, simulation machines can be very far away topology, specify various parameters of network devices
from the machines where the GUI programs run. For and protocols, and specify the application programs that
example, the simulation service center may be at NCTU in will be run during simulation to generate traffic. A
Taiwan while the GUI users come from many different constructed network can be either a fixed wired network or
places of the world. a mobile wireless network.

Simulation
Machine
GUI Boston
Simulation
Machine NCTU
GUI Rome
Simulation Dispatcher
Machine

Simulation GUI Paris

Machine
Simulation Background GUI Tokyo
Machine Job Queue

Simulation Service Center

Kernel Modifications +
Simulation Engine + Figure 2: The topology editor of the NCTUns 1.0 network
A Simulation Machine ==
Protocol Modules + simulator.
Coordinator

Figure 1: The distributed architecture of the NCTUns 1.0. The second component is the performance monitor,
which is shown in Figure 3. The performance monitor can
easily and graphically display the plots of some monitored
When the components of the NCTUns 1.0 are run on performance metrics such as a link's utilization or a TCP
multiple machines to carry out simulation jobs, we say that connection's achieved throughput.
the NCTUns 1.0 is operating in the multiple machine
The third component is the packet animation player,
mode. This mode can support remote simulations and
which is shown in Figure 4. By using the packet animation
concurrent simulations. These components can also run on
player, a logged packet transfer trace can be graphically
the same machine to carry out simulation jobs. This mode is
replayed at any speed. Both wired and wireless networks are
called the single-machine mode and is more suitable for a

4
 The last component is the node editor, which is shown
in Figure 5. A node in the NCTUns 1.0 represents a network
device such as a switch or an IEEE 802.11 (b) wireless LAN
access point. The node editor provides a convenient envi-
ronment to flexibly configure the protocol modules used
inside a network node. By using this tool, a user can use the
mouse to graphically add, delete, or replace a protocol
module with his (her) own module. As such, the node editor
enables a user to easily test the functionality and perfor-
mance of a new designed protocol. Figure 5 shows the
internal protocol stacks used by a router, which in this case
has four network interface ports. In Figure 5, each square
box represents a protocol module. We see that each network
interface port is configured with a chain of protocol
modules (i.e., a protocol stack). The protocol modules
supported by the NCTUns 1.0 are classified into different
Figure 3: The performance monitor of the NCTUns 1.0 categories (e.g., MAC, PHY, Packet Scheduling, etc.). They
network simulator. are displayed at the top of the node editor.

supported. The network at the top of Figure 2 is a fixed

wired network. When the packet animation player starts,
packets are represented as line segments with arrows
flowing smoothly on the links. The network at the bottom is
a mobile ad hoc network. When the player starts, a wireless
transmission is represented by two circles centered at the
transmitting node. These two circles represent the transmis-
sion and interference ranges of the wireless network inter-
face. Their display time is proportional to the packet
transmission time of this wireless transfer. The packet
animation player is a very useful tool because it can help a
researcher to visually debug the behaviors of a protocol. It is
also very useful for educational purposes.

Figure 5: The node editor of the NCTUns 1.0 network

simulator.

4.2. The Enhanced Simulation Methodology

The NCTUns 1.0 uses an enhanced simulation method-

ology, which enables it to be much more powerful and
useful than the Harvard network simulator. The enhance-
Figure 4: The animation player of the NCTUns 1.0 net-
work simulator. ments come from the desires to support multiple subnets in
a simulated network, simulate various network devices at
different layers, simulate various protocols, simulate
various types of networks, support both broadcast and

5
unicast transfer modes for application programs, let users tion server opens tunnel network interface is and js special
use the familiar real-life IP address and port number scheme file in /dev and then executes an endless loop until the simu-
to specify the network parameters of application programs, lated time elapses. In each step of this loop, it simulates a
etc. In summary, the goal of the enhanced simulation meth- packets transmission on the link from host i to host j by
odology is to allow users to simulate any desired network reading a packet from the special file of tunnel interface i,
and operate it in exactly the same way as they operate a waiting the links propagation delay time plus the packets
physical real network. transmission time on the link, and then writing this packet to
the special file of tunnel interface j.
In the following, we present the design and implemen-
tation of the enhanced simulation methodology.
(a)
TCP_sender TCP_receiver
4.2.1: Tunnel Network Interface Link 1

Tunnel network interfaces is the key facility in the used Link 2

simulation methodology. A tunnel network interface, avail- Host 1 Host 2
able on most UNIX machines, is a pseudo network interface
that does not have a real physical network attached to it. The
functions of a tunnel network interface, from the kernels Simulation Server
(b)
point of view, are no different from those of an Ethernet
Link 1
network interface. A network application program can send
out its packets to its destination host through a tunnel TCP TCP
sender Link 2 receiver
network interface or receive packets from a tunnel network
interface, just as if these packets were sent to or received Read Write
from a normal Ethernet interface. user-level
Kernel
Each tunnel interface has a corresponding device TCP/IP TCP/IP
special file in the /dev directory. If an application program stack stack
opens a tunnel interfaces special file and writes a packet
into it, the packet will enter the kernel. To the kernel, the Tunnel Tunnel
packet appears to come from a real network and just be interface 1 interface 2
received. From now on, the packet will go through the Figure 6: (a) A TCP/IP network to be simulated. (b) By
kernels TCP/IP protocol stack as an Ethernet packet would using tunnel interfaces, only the two links need to be sim-
do. On the other hand, if the application program reads a ulated. The complicated TCP/IP protocol stack need not
packet from a tunnel interfaces special file, the first packet be simulated. Instead, the real-life TCP/IP protocol stack
in the tunnel interfaces output queue in the kernel will be is directly used in the simulation.
dequeued and copied to the application program. To the
kernel, the packet appears to have been transmitted onto a
link and this pseudo transmission is no different from an After performing the above two steps, the virtual simu-
Ethernet packet transmission. lated network has been constructed. Figure 6 (b) depicts this
simulation scheme. Since the trick of replacing a real link
4.2.2: Simulating Single-hop Networks with a simulated link happens outside the kernel, the kernels
on both hosts do not know that their packets actually are
Using tunnel network interfaces, we can easily simulate
exchanged on a virtual simulated network. The TCP sender
the single-hop TCP/IP network depicted in Figure 6 (a),
and receiver programs, which run on top of the kernels, of
where a TCP sender application program running on host 1
course do not know the fact either. As a result, all existing
is sending its TCP packets to a TCP receiver application
real-life network application programs can run on the simu-
program running on host 2. We set up the virtual simulated
lated network, all existing real-life network utility programs
network by performing the following two steps. First, we
can work on the simulated network, and the TCP/IP
configure the kernel routing table of the simulation machine
network protocol stack used in the simulation is the real-life
so that tunnel network interface 1 is chosen as the outgoing
working implementation, not just an abstract or a ported
interface for the TCP packets sent from host 1 to host 2, and
version of it.
tunnel network interface 2 is chosen for the TCP packets
sent from host 2 to host 1. Second, for the two links to be Note that in this simulation methodology, the kernel of
simulated, we run a simulation server to simulate them. For the simulation machine is shared by all nodes (hosts and
the link from host i to host j (i = 1 or 2, j = 3 - i), the simula- routers) in a virtual simulated network. Therefore, although

6
in Figure 6 (b) there are two TCP/IP protocol stacks is correct as in real-life networks an IP address is used
depicted, actually they are the same one -- the protocol stack for addressing a layer-3 network interface. Note that
of the single simulation machine. although the familiar network mask of 255.255.255.0 is
used as the network mask for a simulated network, it
4.2.3: Simulating Multi-hop Networks can be set to any valid value as well. In short, the IP
address scheme used in this methodology is the same as
The above simulation methodology can only simulate a
that used in real-life networks.
network composed of two hosts that are directly connected
by a full-duplex link. To simulate a multi-hop network Figure 7 (a) shows that tun1 is used by host 1 to
composed of layer-1 hubs, layer-2 switches, and layer-3 connect to subnet 8, tun2 used by router 1 to connect to
routers, to allow multiple subnets to exist in a simulated subnet 8, tun3 used by router 1 to connect to subnet 9,
network, and to let packets be routed automatically through tun4 used by host 2 to connect to subnet 9, and switch 1
routers as they are forwarded toward their destination does not have any IP address assigned to its interface
nodes, we need to enhance the basic simulation method- ports. We see that each tunnel interface is configured
ology. In the following, we use Figure 7 to illustrate the with an IP address and a MAC address. These MAC
enhanced simulation methodology. addresses can be arbitrarily chosen as long as they are
different on a subnet.
Suppose that we want to simulate the network depicted
in Figure 7 (a), which has two subnets. The first subnet is Source-Destination-Pair IP address scheme After
subnet 8 (its network address is 1.0.8.X) while the second assigning an IP address to each tunnel interface used in
subnet is subnet 9 (its network address is 1.0.9.X). A layer-3 a simulated network, now an application program run-
router (i.e., router 1) connects both of these two subnets ning on a node can send packets to an application pro-
together and forward packets between them. In subnet 9, a gram running on a different node. Assuming that the
layer-2 switch (i.e., switch 1) connects to both router 1 and sending node has a tunnel interface whose assigned IP
host 2 and switches packets between them. In the following, address is 1.0.A.B and the receiving node has a tunnel
we define the schemes used in the NCTUns 1.0. interface whose assigned IP address is 1.0.C.D, in this
methodology the sending application program should
Interface IP address scheme In a simulated network,
use A.B.C.D as the destination IP address when sending
multiple subnets can exist. For each layer-3 or above
packets to the receiving node.
network node (e.g., a host or a router), if it has multiple
network interfaces, each one is simulated by a tunnel We call such addresses the source-destination-pair
network interface. A tunnel network interface has an IP addresses. These addresses are not used by any interface
address assigned to it, just like a normal network inter- in a simulated network. Instead, they are used by send-
face does. Suppose that a tunnel interface connects to ing application programs to indicate their intended des-
subnet A and its host number on this subnet is B, its IP tination nodes. Using the source-destination-pair
address is configured as 1.0.A.B in this scheme. (In the address scheme enables packets to be automatically for-
rest of the paper, we assume that IPv4 addresses are warded through layer-3 routers in a simulated network.
used to construct a simulated network.) Arbitrarily cho- The details about the automatic routing scheme will be
sen, 1.0.X.X represents the network address of the explained later.
whole simulated network. Using the common netmask
of 255.255.255.0, a simulated network can have up to Although using source-destination-pair addresses to
255 subnets, each having up to 255 hosts or routers specify the address parameters of application programs
residing on it. This interface IP address scheme is the is unnatural to simulator users, by using the fully-inte-
same as the standard IP address scheme used in real-life grated GUI environment, a user need not know the con-
networks. cept and need not use the source-destination-pair
address scheme at all. In the GUI program, the user can
If a tunnel interface is used in a simulation, its IP still use 1.0.C.D as the destination address when speci-
address needs to be configured. We can use the UNIX fying the address parameters of application programs.
ifconfig program to do this task. For example, to config- On the simulation machine, the coordinator will auto-
ure tun1, we can use the ifconfig tun1 1.0.8.1 netmask matically translate the destination address to A.B.C.D
255.255.255.0 command. Other tunnel interfaces used before launching these application programs.
in Figure 7 (a) are configured in a similar way.
Automatic routing scheme To let the simulation
In the NCTUns 1.0, a layer-1 network node (e.g., a machines kernel automatically route a packet through
hub) or a layer-2 network node (e.g., a switch) does not many layer-3 routers in a simulated network, we can
have any IP address assigned to its interface ports. This properly configure the routing entries of the simulation

7
 (a) An example network to be simulated

TCP Sender TCP Receiver

Host 1 Router 1 Switch 1 Host 2
tun1 Link 1 tun2 tun3 Link 2 Link 3 tun4
1.0.8.1 1.0.8.2 1.0.9.3 Port 1 Port 2 1.0.9.4
MAC=AA MAC=BB MAC=CC MAC=DD
Node 1 Node 2 Node 3 Node 4
Subnet 1.0.8.X Subnet 1.0.9.X

(b) The automatic routing scheme

TCP_sender TCP_receiver
Host 1 Router 1 Switch 1 Host 1
tun1 Link 1 tun2 tun3 Link 2 Link 3 tun4

1.0.8.1 1.0.8.2 1.0.9.3 Port 1 Port 2 1.0.9.4

Packet
BB 1.0.9.4 DD 1.0.9.4 DD 1.0.9.4 1.0.9.4
DstMAC DstIP DstMAC DstIP DstMAC DstIP DstIP

9.4.9.4
8.1.9.4 9.3.9.4

8.1.9.4 tun1 1.0.8.2 8.1.9.4 tun1 1.0.8.2 DD port2 8.1.9.4 tun1 1.0.8.2
9.3.9.4 tun3 9.3.9.4 tun3 CC port1 9.3.9.4 tun3
9.4.9.4 myself 9.4.9.4 myself 9.4.9.4 myself
8.2.9.4 tun3 8.2.9.4 tun3 8.2.9.4 tun3
Switch table
9.4.8.1 tun4 1.0.9.3 9.4.8.1 tun4 1.0.9.3 9.4.8.1 tun4 1.0.9.3
9.3.8.1 tun2 9.3.8.1 tun2 9.3.8.1 tun2
8.2.8.1 tun2 8.2.8.1 tun2 8.2.8.1 tun2
8.1.8.1 myself 8.1.8.1 myself 8.1.8.1 myself

Routing table Routing table Routing table

(c) Simulation of network (a)

Simulation Server

TCP Switch 1 TCP

Link 1 Link 2 Link 3 receiver
sender

User-level
Kernel
TCP/IP TCP/IP TCP/IP
stack stack stack

Tunnel Tunnel Tunnel Tunnel

interface interface interface interface
Host 1 Router 1 Host 2

Figure 7: (a) An example network to be simulated. (b) The automatic routing scheme is used to automatically forward
packets across layer-3 routers. (c) The simulation server participates in the simulation to simulate links and switches.

8
machines system routing table. The automatic routing module at router 1 then finds the MAC address used by
design has two main advantages. First, we can use the 1.0.9.4 (i.e., DD) and puts it into the MAC header of the
real-life IP protocol stack of the simulation machines packet. The completed MAC frame is then sent out
kernel to forward packets in a simulated network. Simu- through tun3.
lation results thus can be more accurate. Second, we can
reuse the system default routing scheme to add, delete, When the MAC frame arrives at switch 1, its destina-
or change routing entries and look up the routing table. tion MAC address is taken out by switch 1s MAC
As such, we need not waste time and effort to re-imple- module for looking up the switch table. Because the
ment the same scheme in the simulator. Note that found switch entry is [DD port2], which indicates that
although there may be many routers in a simulated net- this MAC frame should be forwarded out via port 2,
work, they all share and use the same system routing this MAC frame is forwarded out without modification
table. via port 2 of switch 1. Note that the switch is simulated
by the simulation server (which is compiled and linked
For example, in Figure 7 (b), several routing entries are with the switch protocol module). Unlike a layer-3
added to the system routing table of the simulation router, which is simulated by letting packets re-enter
machine. When host 1 wants to send packets to host 2, it the kernel IP protocol stack, a layer-2 switch or a layer-
uses the 8.1.9.4 source-destination-pair address to look 1 hub is simulated internally inside the simulation
up the routing table. The found entry is [8.1.9.4 tun1 server.
1.0.8.2]. This entry indicates that the packet needs to be
sent through tun1 and the used gateway IP address When the MAC frame arrives at host 2, its MAC
should be 1.0.8.2. The ARP module at the sending node header is stripped off. The destination IP address
then finds the MAC address used by 1.0.8.2 (by using 1.0.9.4 is taken out and translated to the source-destina-
the ARP request/reply protocol) and puts it (i.e., BB) in tion-pair address 9.4.9.4 before the kernel looks up the
the MAC header of the packet as the destination MAC routing table. Because the first two numbers 9.4 is the
address. The MAC module at the sending node then same as the second two numbers 9.4 in the source-
sends out the completed MAC frame, which will then destination-pair address 9.4.9.4, the kernel knows that
reach the interface whose assigned IP address is 1.0.8.2. this packet has reached its final destination node and
therefore there is no need to look up the routing table.
Note that the source-destination-pair address 8.1.9.4 is The kernel then delivers the packet to the TCP/UDP
used only for looking up the routing table. After the layer for further processing.
corresponding routing entry is found, the source-desti-
nation-pair address 8.1.9.4 is no longer used. The desti- 4.3. Simulation Engine
nation IP address carried in the IP header of the packet
is always 1.0.9.4. It remains the same from the source The NCTUns 1.0 is a network simulator, not a network
node to the destination node, no matter how many emulator. As such, it can simulate networks with a very
routers the packet needs to traverse. large number of links and nodes. Links with very high band-
width can also be simulated. As a simulator, when simu-
When the MAC frame arrives at router 1, its MAC
lating a network, the simulation engine needs to maintain a
header is stripped off by the MAC module at router 1.
virtual clock for the simulated network. Simulation events
At the IP layer of the simulation machines kernel
are triggered and executed based on the virtual clock, rather
protocol stack, the 1.0.9.4 address carried in the IP
than the real clock.
header is taken out and translated to 9.3.9.4 source-
destination-pair address for looking up the routing The virtual clock in the simulation engine is maintained
table. The reason why 9.3.9.4 is used is because 1.0.9.3 by a counter. The time unit represented by one tick of the
is one of router 1s IP addresses. Actually, because counter can be set to any value (e.g., one nanosecond) to
1.0.8.2 is also one of router 1s IP addresses, the 8.2.9.4 simulate high speed links. The current virtual time thus is
source-destination-pair address can also be used. In the current value of the counter times the time unit used.
Figure 7 (b), we see that both [9.3.9.4 tun3] and [8.2.9.4 The simulation engine uses the discrete-event simulation
tun3] routing entries exist in the system routing table. method to advance its virtual clock. During simulation, the
As such, whether 1.0.9.4 is translated to 9.3.9.4 or counter is continuously advanced to the timestamp of the
8.2.9.4, the found routing entry will indicate that the event to be processed next.
destination node (i.e., host 2) is already on the same
subnet as router 1 (because there is no gateway IP The simulation engine needs to pass the current virtual
address associated with this entry) and the packet time down into the kernel. This is required for many
should be sent out via tun3 directly to 1.0.9.4. The ARP purposes. First, the timers of TCP connections used in the

9
simulated network need be triggered by the virtual time protocol stack. A layer-3 interface (i.e., a tunnel interface)
rather than by the real time. Second, for those application uses such a protocol stack to simulate its layer-2 and below
programs launched to generate traffic in the simulated processing. For example, a layer-3 interface normally has
network, the system calls issued by them must be performed the following protocol modules. First, an ARP module is
based on the virtual time rather than the real time. For required to find the MAC address used by an IP address
example, if we launch a ping program in a simulated (i.e., the destination IP address of an outbound packet).
network to send out a ping request every one second, the Second, a packet scheduling and buffer management
sleep(1) system call issued by the ping program must be (PSBM) module is required for storing and scheduling
triggered by the virtual time, not the real time. Third, the in- outbound packets. (The simplest one is a FIFO queue.)
kernel packet logging mechanism (i.e., the Berkeley packet Third, a Medium Access Control (e.g., 802.3 or 802.11)
filter scheme used by tcpdump) needs to use timestamps module is required for controlling when to send a packet
based on the virtual time, rather than the real time, to log onto the link. Lastly, a physical layer (PHY) module is
packets transferred in a simulated network. required to simulate the characteristics of the transmission
medium (e.g., delay, bandwidth, Bit-Error-Rate, etc.).
The simulation engine needs to pass the current virtual These modules are chained together. When a layer-3 inter-
time to the kernel in a low-cost and fine-grain way. The face sends out a packet onto a link, the packet will be passed
simulation engine can pass the current virtual time into the down module-by-module to the PHY module. In the other
kernel by periodically making a system call. (For example, direction, when the PHY module of a layer-3 interface
the simulation engine can make the system call once every 1 receives a packet, the packet will be passed up module-by-
ms in virtual time.) However, the cost of this approach will module to the layer-3 interface if a lower-layer module does
be too high when we want the virtual time maintained in the not discard it (e.g., to simulate bit errors).
kernel to be as precise as that maintained in the simulation
engine. For example, the in-kernel packet logging mecha- Although by default each layer-3 interface (i.e., tunnel
nism needs a microsecond-resolution clock to generate interface) has an output queue (FIFO) associated with it
timestamps. To solve this problem, the simulation engine inside the kernel, the NCTUns 1.0 does not use it. Instead,
uses a memory-mapping technique. The simulation engine whenever the kernel enqueues a packet into a tunnel inter-
maps the memory location that stores the current virtual faces output queue, a notification event is immediately
time in the simulation engine to a memory location in the passed to the simulation server, which enables the simula-
kernel. As such, at any time the virtual time in the kernel is tion server to immediately dequeues the packet and reads it
as precise as that maintained in the simulation engine out from the kernel. This operation takes no time in virtual
without any system call overhead. time because the simulators virtual clock is stopped during
this period.
4.4. Protocol Modules
The simulation server then passes the packet to the
Protocol modules are compiled and linked with the ARP module associated with this tunnel interface, which in
simulation engine to simulate layer-2 and below devices, turn passes the packet down to the PSBM module below it.
protocols, and transmission medium. Although the auto- At the PSBM module, any sophisticated packet scheduling
matic routing scheme enables the simulation machines and buffer management scheme can be used. This design
kernel to use its layer-3 and above TCP/IP protocol stack to enables a host or a router to use various sophisticated packet
forward packets, layer-2 and below devices, protocols, and scheduling and buffer management scheme for its ports. For
transmission medium are not simulated when this scheme is example, a routers first port can use a PSBM module that
used. As such, the simulation server (i.e., the simulation implements the Round-Robin scheme while its second port
engine plus protocol modules) needs to simulate transmis- can use a PSBM module that implements the FIFO scheme.
sion medium, all layer-2 and below protocols, and devices. Another advantage of this design is that a PSBM module
For example, Figure 7 (c) shows that, to simulate the developed for layer-2 switches can be readily used for
network depicted in Figure 7 (a), the simulation server layer-3 routers. No extra time and effort are needed.
needs to simulate link 1, link 2, link 3, and switch 1. (It does As an example, Figure 8 (b) shows how the simulation
not need to simulate host 1, host 2, and router 1 because server simulates the network depicted in Figure 8 (a).
they are simulated by using the automatic routing Suppose that the TCP sender sends a packet to the TCP
scheme.) receiver. On host 1, the packet will pass through the TCP/IP
protocol stack and be enqueued into the output queue of
Layer-2 and below devices, protocols and transmission
tun1. The simulation server will immediately dequeue it and
medium are simulated as protocol modules. Several
read it out from the kernel. The simulation server then
protocol modules may be chained together to form a
delivers it to the protocol stack created for tun1. The packet

10
then passes the ARP module, the PSBM module, the 802.3
module, and finally reaches the PHY module of this (a) A network to be simulated.
protocol stack.
TCP Sender TCP Receiver
Before being delivered to the other end of the link, the Link 1
packet needs to wait a certain amount of time to simulate
the delay of link 1 and its packet transmission time on link
Host 1 Host 2
1. While waiting, it is stored as a timeout event in the simu-
lation engines event heap. When the packets timer expires,
the simulation server then delivers the packet to the protocol
(b) Using the simulation server to simulate the network
stack created for tun2 by moving the packet to the PHY depicted in (a).
module of the second protocol stack. The packet then is
passed up and reaches the 802.3 module. At the 802.3 Simulation Server
module, the packets destination MAC address is checked
against tun2s MAC address to see whether this packet
should be accepted or discarded. If the packet should be
accepted, it is passed to the PSBM module. The PSBM ARP ARP
module simply passes the packet to the ARP module
because its packet scheduling and buffer management func- PSBM PSBM
tions are for outbound packets, not for inbound packets.
When the ARP module receives the packet, because ARP 802.3 802.3
protocol is for outbound packets only, it simply writes the
packet into the kernel. The packet then passes through the PHY PHY
TCP/IP protocol stack and finally reaches the TCP receiver. TCP TCP
sender receiver
To enable the user-level simulation server to quickly
detect that the kernel has enqueued a packet into a tunnel User-level
interfaces output queue, a memory-mapping technique Kernel
similar to that used for passing the current virtual time down TCP/IP TCP/IP
into the kernel is used. In the kernel, a bit-map is used to stack stack
record the empty or non-empty status of every tunnel inter-
faces output queue. The memory location that stores this Tunnel
Tunnel
bit-map in the kernel is mapped to a memory location in the interface 1 interface 2
simulation server. By using this technique, the simulation
server can immediately detect that a packet has been
enqueued into a tunnel interfaces output queue without any Figure 8: (a) A network to be simulated. (b) Using the
system call overhead. simulation server to simulate the network depicted in (a).

4.5. Kernel Modifications

be hidden from the user. The user need not know how we
Some parts of the simulation machines kernel need to use the source-destination-pair address to automatically
be modified. In the following, we present some important route packets.
kernel modifications. Internally, the kernel needs to perform the address
translation on each node that is on the path from the source
4.5.1: IP Address Translation
node to the destination node, and use the translated IP
The use of source-destination-pair IP address scheme address to look up the routing table. However, to translate
enables the kernel to automatically forward a packet toward the address, the kernel first needs to know the identity of the
its destination node. However, when a simulator user speci- current node. That is, when a packet is forwarded to and
fies an application programs destination IP address param- enters node i, the kernel should know that the identity of the
eter, he (she) should be able to use the normal IP address current node is i. After obtaining this information, the
scheme for this task. For example, in Figure 7 (a), the desti- kernel can look up the interface table associated with node i
nation IP address parameter given to the TCP sender should and pick up an interface IP address to perform the transla-
be 1.0.9.4, rather than 8.1.9.4. The internally-used and tion. (The kernel keeps an interface table for each node,
unnatural source-destination-pair IP address scheme should which records the IP addresses used by this node.) As an

11
example, in Figure 7 (a), when a packet is forwarded to application programs running on different nodes want to
node 2, the kernel can pick up an IP address (say 1.0.9.3) bind to the same port in a simulated network, a network
from node 2s interface table and translate 1.0.9.4 to 9.3.9.4 simulator user can solve this problem by letting them
before looking up the routing table. (Note: the kernel could choose different port numbers to bind. Although this solu-
pick up 1.0.8.2 and translate 1.0.9.4 to 8.2.9.4 as well. The tion works and does not affect the simulation result, it
reason has been explained in Section 4.2.3.) makes a simulated network unnatural to the simulator user,
which should be avoided. A better solution would be that
To pass the current node identity to the kernel when a these application programs are still allowed to bind to the
packet arrives at a node, the simulation server, after simu- same port when they are launched; however, the kernel
lating the packets transmission on a link, can put the iden- internally translates the port number used by them to
tity of the destination node of the link (e.g., i) into the different port numbers to avoid port number collisions.
packets header before writing it into the kernel.
To achieve this goal, the kernel maintains a bit-map to
Although the above method seems to work successfully record which port numbers have been used and which have
for all nodes on the path, actually it cannot work success- not been used. During a simulation, suppose that an applica-
fully for the source node. For a non-source node, before a tion program (say A) running on node i wants to bind to port
packet enters it, the packet must be transmitted on a link. As number j, the kernel will find an unused port number (say k)
such, the simulation server knows the identity of the desti- and instead let application program A bind to port number
nation node of this link. However, for the source node, since k. The kernel then creates an association (nodeID = i, real_
the packet does not come from any link, this information is port_num = j, remapped_port_num = k) and inserts it into a
unavailable and thus cannot be provided by the simulation hash table.
server.
With this arrangement, if an application program (say
We solve this problem by explicitly telling the kernel B) wants to send packets to application program A, applica-
the current node identity when an application program is tion program B can use the port number originally used by
launched. Since in the NCTUns 1.0 every application application program A (i.e., j) as the destination port
program is launched by the coordinator, the coordinator is number. Application program B need not know the port
designed to issue a system call to the kernel before number translation details. The simulated network looks
launching an application program. The system call passes like a real network to it.
the identity of the node on which the application program is
intended to run into the kernel. The kernel then stores this The port number translation process occurs at the desti-
information in one of its variables. Very soon when the nation node(s), not at the source node. When application
application program is launched, the kernel will store this program B sends a packet to application program A, before
information in the control block of this launched process. the packet reaches the destination node, the destination port
Form now on, every packet generated by this application number carried in the packet remains j, not k. Only after the
program can carry this information in its header when it is packet reaches the destination node is its destination port
sent down from the socket layer to the IP layer. This solves number translated to k. Finding k is achieved by searching
the address translation problem on the source node. the hash table using the key pair (i, j), where j is readily
available from the packet header. As for the value of i (the
4.5.2: Port Number Translation current node identity), the kernel can obtain this information
by using the method described in Section 4.5.1.
An inherent problem with the proposed simulation
methodology is that application programs cannot bind to the Translating the port number at the destination node(s),
same port in a simulated network, even though they are not at the source node, has two advantages. The first advan-
running on different nodes in the simulated network. The tage is that it supports broadcast transfers on a subnet. If the
reason is that, since these application programs are running translation is performed at the source node, only unicast
on a single machine (i.e., the simulation machine), they transfers can be supported. Broadcasting a packet on a
cannot choose the same port to bind. In real-life networks, subnet to multiple application programs that bind to the
however, this is possible and should be allowed. For same port but run on different machines (e.g., the routing
example, in a network, there may be a Web server binding daemons case) will be impossible. At present, we have not
to port 80 on every host and a RIP routing daemon binding investigated how to support multicast transfers. The second
to port 520 on every router. advantage is that we can use the tcpdump program to
correctly filter and capture packets in a simulated network.
From an application programs viewpoint, it does not
The tcpdump program can use port numbers to filter and
matter which port to use as long as it can use the port to
capture packets. When a user wants to capture the packets
communicate with its partners. As such, when multiple

12
sent from application program A to B, naturally he (she) interface. The user can run the traceroute command to see
will set the filtering destination port number to j. If we the routing path between any pair of nodes in the simulated
translate the port number at the source node, the destination network. This is useful for quickly checking the routing
port number carried in the packet will be k when it is paths generated by routing daemons. The user can also run
traversing the network. This will make the tcpdump the tcpdump command to monitor the packets flowing on
program unable to capture this packet. an interface. Actually, any real-life command can be
executed in the command console. The user can immedi-
4.5.3: Process Scheduling ately get the output of these commands without waiting
until the simulation is finished.
We modified the default UNIX process scheduler so
that the processes of the simulation server and all launched To make a command console totally natural to the user,
traffic generators can be scheduled in a controlled way. The we modified the system default shell program so that the
default UNIX process scheduler uses a priority-based user will not see anything inconsistent. The modification
dynamic scheme to schedule processes. As such, the order handles interface name conversion and filtering. On a real-
in which the simulation server and traffic generator life UNIX machine, a user may execute the ifconfig
processes are scheduled cannot be precisely controlled. command to check the settings of an (or all) interface(s).
Also, the CPU cycles allocated to each of these processes The output is useful as it includes the name assigned to the
cannot be guaranteed. This may result in a potential interfaces. (For example, the first Intel EtherExpress
problem. For example, after getting the control of CPU, the Ethernet interface is assigned the name fxp0, the second
simulation server may use the CPU too long before assigned the name fxp1, etc.) Knowing an interfaces name
releasing it to traffic generators. Because the simulation is important as some utility programs need this information.
server is responsible for advancing the virtual clock while it For example, if we run the tcpdump program to monitor the
is executing, if it monopolizes the CPU too long, no packets flowing on an interface, we need to know the inter-
network traffic can be generated during this long period of faces name and give it as a parameter to the tcpdump
time, which should not occur. To avoid this potential program.
problem, we modified the default UNIX process scheduler
so that the simulation server and all traffic generator If the default shell program is not modified, when the
processes are explicitly scheduled according to the times- user uses the ifconfig -a command to see all interfaces
tamp order of their events. used by this node, he (she) will see all the tunnel interfaces
used by the simulation machine and will not know which
4.6. System Functions tunnel interfaces are internally used for the interfaces of this
node. As such, the shell program needs to perform two
In addition to simulating network devices and proto- tasks. The first task is to filter out unrelated output and the
cols, to be a useful software, the NCTUns 1.0 provides second task is to convert interface names between tunXXX
many useful system functions. In the following, we present and fxpXXX, where XXX represents a number.
two of them. For example, suppose that 256 tunnel interfaces (tun0,
tun1, .., tun255) are used by the simulation machine to
4.6.1: Per-Node Command Console Shell
simulate a network, and among them, tun1, tun8 and tun9
For each node in a simulated network, we provide a are internally used to simulate the three interfaces used by a
command console. A GUI user can easily invoke a nodes node in the simulated network. Suppose that in the topology
command console by right-clicking the nodes icon in the editor, these three interfaces are given the names fxp0, fxp1,
topology editor. Immediately a terminal window (like the X and fxp2, respectively. Now in the nodes command
terminal window) will appear and automatically log into the console, if the user executes the ifconfig -a command,
(possibly remote) simulation machine. On the simulation what he (she) should see is the settings about fxp0, fxp1,
machine, a shell program is then executed to process the and fxp2, rather than the settings about tun0, tun1, ..., and
real-life UNIX commands that may be typed in by the GUI tun255. The shell program needs to internally convert tun1
user. to fxp0, tun8 to fxp1, and tun9 to fxp2 before displaying the
commands output. It also needs to filter out the settings of
The command console is a very useful feature. During all other tunnel interfaces before displaying the output. To
a simulation, in a nodes command console, a user can the user, the names of the interfaces used by this node are
launch application programs or execute UNIX commands at fxp0, fxp1, and fxp2. He (she) should be able to use any of
run time, just like he (she) is operating in a real-life network these interface names (fxpXXX) as a parameter for any
nodes command console. For example, a user can run the real-life command or program.
netstat command to get the packet transfer statistics of an

13
 To achieve this goal, the interface name conversion and design, however, some modifications are needed to let the
filtering operations must be performed for both the input tcpdump program generate correct output.
and output of the shell program. For example, after the user
finds that the node has three interfaces named fxp0, fxp1, In Section 4.4, we show that in the current design, the
and fxp2, he (she) may decide to execute the tcpdump packets that should be sent through a tunnel interface are no
program to monitor the packets flowing on fxp2. (The exact longer queued in the output queue of the tunnel interface.
command is tcpdump -i fxp2.) Before launching the Instead, they are immediately dequeued by the simulation
tcpdump command, the shell program needs to intercept this server as soon as they are enqueued into the tunnel inter-
command string and convert fxp2 back to tun9 so that the faces output queue. The only place where they may be
internally-launched tcpdump command will be tcpdump -i queued (and delayed) is in the PSBM module associated
tun9 rather than tcpdump -i fxp2. with this tunnel interface, which is in the simulation server.
This causes a problem as now the timestamps given by the
To intercept both the input and output of the shell tunnel interfaces device driver to these packets are incor-
program, we fork a process and insert it between the shell rect. On a real-life machine, the timestamp given to an
process and the system terminal device driver. This process outgoing packet represents the time when the packet is
acts as a relaying process. All input to and output from the transmitted to a link rather than the time when the packet is
shell process must be relayed by this process. As such, it has enqueued into the output queue. However, in the current
a chance to perform its tasks. This process actually performs design, if there is no modification, a packet will receive a
more tasks than those described here. This is because a timestamp that represents the time when it leaves the tunnel
command string may contain the shell I/O redirection (i.e., interface (or enters the PSBM module, they are the same.),
>) and pipe (i.e., |) operators. The interface name conver- rather than when it is transmitted to a link.
sion and filtering operations must still be handled properly
in such cases. To solve this problem, we disabled the part of the
tunnel interface device driver that is responsible for passing
The command console shell needs to perform two other each outgoing and incoming packet to the BPF module. We
tasks, which are also performed by the coordinator. First, also developed a tcpdump module and insert it between the
before launching an application program, the shell needs to MAC and PHY modules. This tcpdump module cannot hold
pass the current node identity into the kernel. (The reason is any packet. When receiving a packet from the MAC module
explained in Section 4.5.1.) Second, after launching an (if it is an outbound packet) or from the PHY module (if it is
application program, the shell needs to register the forked an inbound packet), the tcpdump module makes a copy of
process with the kernel. (The reason is explained in Section the packet, gives it a special tag, and associates it with the
4.5.) current timestamp. The tcpdump module then writes the
copy into the kernel through the tunnel interface that the
4.6.2: Tcpdump Packet Filtering and Capturing Tool user-level tcpdump program is currently operating on. The
tunnel interfaces device driver, when seeing this special
The tcpdump program is a packet filtering and
tag, passes the packet to the BPF module for evaluation. If
capturing tool. It is a user-level program that can pass
the BPF module decides to accept this packet, it then passes
filtering rules to the kernel and display captured packets.
this packet to the user-level tcpdump program.
Packet filtering operations are actually performed by the
Berkeley-Packet-Filter (BPF) module in the kernel. When a As an example, suppose that during a simulation a user
packet is sent or received at an interface, the device driver wants to monitor the traffic of a nodes interface and this
of the interface passes the packet to the BPF module for interface is internally simulated by tun4. In the nodes
evaluation. If the BPF module decides to accept this packet, command console, the user will execute the user-level
it will associate a timestamp with the packet. The module tcpdump program and the command console shell will inter-
gives each captured incoming packet a timestamp to record nally translate this command string to tcpdump -i tun4.
when it is received by the interface. The module also gives From now on, a user-level tcpdump program is running and
each captured outgoing packet a timestamp to record when monitoring packets on tun4. At the same time, the shell also
it is transmitted onto a link. asks the simulation server to insert a tcpdump module
between the MAC and PHY modules that are associated
The tcpdump program operates on an interface. Since
with tun4. From now on, when receiving a packet (either
from the kernels viewpoint, a tunnel interface is no
incoming or going), the inserted tcpdump module will make
different from a real interface, the tcpdump program should
a copy of this packet, give it a special tag, and associate it
be able to work correctly to capture packets flowing on a
with the current timestamp. The module will then write it
nodes interface in a simulated network. In the current
into the special file of tun4 (i.e., /dev/tun4). After entering
tun4, due to the special tag, the copy of the packet will be

14
passed to the BPF module for evaluation. If accepted, the simulated network has only one subnet (and thus has no
copy will be received by tcpdump program operating on router), the kernel routing table need not be used and can be
tun4 at the user-level. empty.

The above design has two advantages. First, we can The NCTUns 1.0 supports the subnet concept. There-
fully exploit the power of the tcpdump program. Any fore, the more efficient subnet-routing scheme can be used
feature of the real-life tcpdump program can be used. instead of the less-efficient host-routing scheme. For
Second, we reuse the user-level tcpdump program and in- example, for the network depicted in Figure 7 (a), instead of
kernel BPF module code to the maximum extent. They need storing the two routing entries [8.1.9.3 tun1 1.0.8.2] and
not be modified at all. We only need to disable a very small [8.1.9.4 tun1 1.0.8.2] in the kernel routing table, we can
part of the tunnel device driver code and write a very simple store only one routing entry [8.1.9 tun1 1.0.8.2] in the table.
tcpdump module. Because the subnet-routing scheme can be used, suppose
that in a simulated network there are S different subnets and
on average there are H hosts residing on a subnet, the
5. Scalability Issues
number of source-destination-pair routing entries that need
Because in our scheme a single UNIX machine is used to be stored in the kernel routing table would be about S * H
to simulate a whole network (including nodes protocol * S. As an example, suppose that S is 30 and H is 20, the
stacks, traffic generators, etc.), the scalability of the simu- number of required routing entries would be about 18,000.
lator is a concern. In the following, we discuss several scal- We have tested several network configurations that
ability issues. need to store over 60,000 routing entries in the kernel
routing table. We found that because the BSD UNIX
5.1. Number of Nodes systems use the radix tree [14] to efficiently store and look
up routing entries, using a large number of routing entries in
Because our scheme simulates multiple routers and a simulation is feasible and does not slow down simulation
hosts by letting packets re-enter the simulation machines speed much.
kernel, there is no limitation on the maximum number of
routers and hosts that can be simulated in a network. For 5.4. Number of Application Programs
hubs and switches, since they are simulated in the simula-
tion server, there is no limitation on them either. Since application programs running on a UNIX simula-
tion machine are all real independent programs, the simula-
5.2. Number of Interfaces tion machines physical memory requirement would be
proportional to the number of application programs running
In our scheme, because each layer-3 interface uses a on top of it. Although, at first glance, this requirement may
tunnel interface, the maximum number of layer-3 interfaces seem severe and may greatly limit the maximum number of
that can be simulated is limited by the maximum number of application programs that can simultaneously run on a
tunnel interfaces that a BSD UNIX system can support, UNIX machine, we found that the virtual memory mecha-
which currently is 256. (This limitation is caused by UNIX nism provided on a UNIX machine together with the
using an 8-bit integer as a devices identity.) Since this working set property of a running program greatly alle-
problem can be easily solved, (for example, we can clone viate the problem. The reason is that, when an application
tunnel interfaces, give the cloned interfaces different names, program is running, only a small portion of its code related
and use them in the same way as we use the original tunnel to network processing will need to be present in the physical
interface.), there is no limitation on the maximum number memory. In addition, because UNIX machines support the
of layer-3 interfaces that can be simulated in a network. For uses of shared libraries and shared virtual memory pages,
layer-1 and layer-2 interfaces (used in hubs and switches the required memory space for running the same application
respectively), since they are simulated in the simulation program multiple times can be greatly reduced.
server, there is no limitation on them either.

5.3. Number of Routing Entries 6. Simulator Performance

Here we report the simulation speed of the NCTUns 1.0
In our scheme, the kernel routing table needs to store
under several network and traffic configurations. The used
many source-destination-pair IP addresses so that packets
machine for performance testing is an IBM A31 notebook
can be automatically forwarded across routers by the kernel.
computer equipped with a 1.6 GHz Pentium processor and
Since the kernel routing table is used only by routers, if a
128 MB RAM.

15
6.1. Variable CBR UDP on a Single-Hop Network
Case

In this test suite, the network topology is a single-hop

network in which a sending host and a receiving host are
connected together by a link. The bandwidth of the link is
set to 10 Mbps and the delay is set to 10 ms, in both direc-
tions. The traffic generated is a one-way constant-bit-rate
(CBR) UDP packet stream. Each UDP packet size is set to
576 bytes.

We varied the packet inter-arrival time of the CBR

packet stream to see how the simulators speed will change
when it needs to process more events in each simulated
second. The packet inter-arrival time is the time interval
between two successive packet transmissions. The tested Figure 9: The simulation performance under various con-
intervals are 0.001, 0.005, 0.025, 0.125, 0.625, and 3.125 stant-bit-rate UDP traffic loads. (A higher ratio means a
seconds, respectively. better performance.)

The performance metric reported is the ratio of the node, we can set up a greedy TCP connection by running
simulated seconds to the elapsed seconds for running the the stcp program on the source node and the rtcp program
simulation. In all of our tests, the simulated seconds is set to on the destination node. The length of TCP data packets is
999 seconds. A simulation case with a higher ratio means 1500 bytes, which is Ethernets MTU.
that it can be finished more quickly than a case with a lower
ratio. A simulation case with a ratio of 1 means that it needs In this test, we varied the number of greedy TCP
the same amount of time in real time to finish simulating the connections that are set up to compete for the bottleneck
amount of time that it wants to simulate. links bandwidth. The numbers tested are 1, 2, 3, 4, 5, and 6,
respectively. In all of these cases, the bottleneck links
Figure 9 shows the ratio vs. CBR packet inter-arrival bandwidth is always 100% utilized.
time performance plot. We see that due to the discrete-event
simulation engine design, a simulation case can be finished
very quickly if it does not have many events to process (i.e., stcp
traffic) per simulated second. We also see that the ratio (2.5)
of the high-load case (0.001 seconds) is still greater than 1. stcp
This means that the simulator can still run 2.5 times faster
than the real world under this load on the testing machine. stcp rtcp
stcp
rtcp
6.2. Multiple Greedy TCP Connections on a stcp rtcp
Single-Hop Network Case
stcp rtcp
Since during a simulation the applications that are run
rtcp
to generate traffic are real-world programs, we are inter- rtcp
ested to see how the simulators speed will change if more
Figure 10: The multi-source-node network topology used
applications need to be run at the same time. To perform
to test whether the simulation performance will degrade
this test, we used the network configuration depicted in when more applications need to be run to generate traffic.
Figure 10.

In this configuration, there are six source nodes, one Figure 11 shows that the simulators speed does not
destination node, and a bottleneck router node. The band- degrade as more applications (stcp and rtcp) are run to
width and delay of all links are set to 10 Mbps and 10 ms, generate traffic. This phenomenon can be explained because
respectively. The maximum packet queue length of the the number of events that need to be processed per simu-
FIFO queue in the bottleneck router is the default 50 lated second remains about the same. No matter how many
packets. Between a pair of a source and the destination greedy TCP connections (their stcp and rtcp programs) are

16
 1-hop

2-hop

3-hop

4-hop

5-hop

6-hop

Figure 12: The multi-hop networks used to test the simu-

Figure 11: The simulation performance remains about the lation performance. The source host is on the left while
same with different numbers of application programs the destination host is on the right. Intermediate forward-
(stcp and rtcp) running as traffic generators. These traffic ing nodes may be routers or switches.
generators compete for the bottleneck links bandwidth.

Figure 13 shows the performances of these two suites.

launched to send and receive their data, the aggregate We see that as the number of hops increases, the simulation
amount of data that can be pumped into the bottleneck link performance decreases. This phenomenon is reasonable as
or received from the bottleneck link per simulated second is in such a case, the number of events that need to processed
always fixed to the 10 Mbps rate. As such, the stcp and rtcp in each simulated second increases.
programs of the six greedy TCP connections will take turns
to run, and their aggregate context-switching rate is about We also see that a router is more costly than a switch in
the same as in the single greedy TCP connection case. forwarding a packet. This phenomenon can be explained as
follows. When simulating a routers forwarding a packet,
the simulation engine needs to read a packet out of the
6.3. Fixed CBR UDP on Multi-Hop Networks
kernel and then write it into the kernel. However, to simu-
Case
late a switchs forwarding a packet, the forwarding opera-
tion can be simulated totally inside the simulation engine
For a discrete-event simulation engine, the more events
without issuing any read or write system call to the kernel.
it needs to process in each simulated second, the slower its
Since issuing system calls are costly, switches can forward
simulation speed will be. In Section 6.1, we shows that on a
packets more efficiently than routers in a simulation.
single-hop network if we decrease the CBR packet streams
packet inter-arrival time, the simulator will become slower.
6.4. Discussions
Here we show that, given a fixed CBR packet inter-arrival
time, if packets need to go through more hops, the simulator
will also become slower. For the following reasons, the NCTUns 1.0s speed
may be slower than that of a traditional network simulator
The network configurations used are multi-hop chain such as ns-2. First, real-life protocol stacks are executed
networks shown in Figure 12. The node on the left hand side rather than their abstractions. Second, real-life application
is the source host while the node on the right hand side is programs are executed to generate traffic. Third, real data
the destination host. The bandwidth and delay of all links payload are carried in each transmitted packet and thus they
are set to 10 Mbps and 10 ms, respectively. The packet need to be copied. Fourth, since packets need to be read out
inter-arrival time of the CBR UDP packet stream is set to of the kernel and then written into the kernel, a lot of system
0.025 seconds and the packet length of each UDP packet is calls need to be made.
set to 576 bytes.
The reported results show that the performance of the
We performed two suites of performance tests. In the NCTUns 1.0 in its current form is still satisfactory. When
first suite, all of the intermediate forwarding nodes are the network topology is not large and the traffic load is not
routers. In the second suite, all of them are switches. We high, its simulation speed is faster than the real world.
made these two cases to observe how much more costly a Currently, we are working to further improve its perfor-
router is in forwarding a packet than a switch. mance by first identifying its performance bottleneck and

17
 To confirm that the simulator can correctly simulate a
links bandwidth and delay, we also have performed exten-
sive validation tests covering various network configura-
tions. All of these results can be explained and shown to be
correct. Due to space limitation, we do not present these
cases here.

8. Discussions and Limitations

Since only a single UNIX machine (with its own
protocol stack) is used to simulate multiple nodes, the
NCTUns 1.0 has a limitation that it allows only one version
of TCP/IP protocol stack in a simulated network. Studying
interactions between different TCP versions (e.g., TCP
Figure 13: The simulation performance decreases as the tahoe and TCP reno) or between different TCP implementa-
number of hops increases. The cost of forwarding a pack- tions (e.g., FreeBSD and Linux) thus cannot be done by
et by a switch is less than that of forwarding a packet by using our simulator as is. One way to overcome this limita-
a router. tion is to use a distributed simulation approach. In such a
distributed approach, a UNIX machine with a particular
then using more efficient data structures and algorithms for protocol stack can be used to simulate nodes using the same
its execution. stack, while other UNIX machines with different stacks
may be used to simulate nodes using different stacks.

7. Simulation Result Validations Currently, the FreeBSD platform provides a user-level

sysctl -a or -w command to view or change various
The results generated by a simulator need to be care- parameters used by the in-kernel TCP/IP protocol stack. For
fully validated and shown to be correct before it can be example, a user can use this command to change the size of
trusted. In the following, we explain how we validated a socket send and receiver buffer, the TCP delay ACK time,
simulation results. whether to perform TCP delay ACK mechanism, whether to
use TCP newreno version, etc. Although right now this
For UDP traffic cases, our simulation results show that command can change a large number (93) of protocol
each packet is transmitted (and received) exactly at the parameters or options, a user may still need to change the
specified times. For example, if a CBR UDP packet stream kernel source code and recompile the kernel if his (her)
has a packet inter-arrival time of 0.001 seconds, our results changes cannot be performed by this command. Changing
show that the first packet is transmitted at 0 second, the the kernel source code, however, may not be comfortable to
second packet is transmitted at 0.001 seconds, and the third all users.
packet is transmitted at 0.002 second, etc. Actually, we
found that transmitting a packet stream with any packet When installing the NCTUns 1.0, the user needs to
inter-arrival time distribution is accurately simulated. This have the root privilege to be able to recompile the kernel.
is because the simulation engine can just advance its virtual This may be a problem for some users who do not have their
clock to the timestamps of these transmitting (and own computers. Since recompiling the kernel may not be
receiving) events. comfortable to all users, the NCTUns 1.0 package provides
an installation script to perform this task automatically
For TCP traffic cases, our simulation results also show without human intervention.
that each packet is transmitted or received under correct
TCP error and congestion control. We dumped all TCP Since the NCTUns 1.0 uses real-life protocol and appli-
timer timeout events (e.g., delay-ack and retransmission cation implementations to simulate a network and its
timers) and used the tcpdump packet trace to perform corre- traffic, its generated results may vary from one platform to
lation checks across TCP timer events and packet transfers. another platform (e.g., from FreeBSD to Linux) or from one
The checks confirm that the TCP protocol is correctly simu- release to another release (e.g., from FreeBSD 2.8 to
lated during a simulation. Actually, this is a natural result as FreeBSD 4.6), although they are all correct. Thus, when
the NCTUns 1.0 uses the in-kernel real-life TCP/IP protocol reporting or comparing simulation results generated by the
stack to generate simulation results. NCTUns 1.0, a user should report the used platform and
release version as well.

18
9. Ongoing Work [4] S.Y. Wang and H.T. Kung, "A New Methodology for Easily
Constructing Extensible and High-Fidelity TCP/IP Network
Simulators," Computer Networks, Vol. 40, Issue 2, October
Aimed to be a production-level and high-quality soft-
2002, pp. 257-278.
ware, the NCTUns 1.0 still has many places to improve in
its future versions. For example, its simulation speed needs [5] Harvard TCP/IP network simulator 1.0, available at http://
to be improved and many useful system functions (such as www.eecs.harvard.edu/networking/simulator.html.
print) need to be added. We are working on these to-do [6] Fall and K., Network Emulation in the Vint/NS simulator,
items. ISCC99, July 1999.
[7] Nist net, available at http://snad.ncsl.nist.gov/itg/nistnet.
10. Conclusions [8] Jong Suk Ahn, P. Danzig, Zhen Liu, and Limin Yan, Evalu-
ation of TCP Vegas: Emulation and Experiment, ACM
In this paper, we present the internal design and imple- SIGCOMM95.
mentation of the NCTUns 1.0. Based on an enhanced simu-
[9] X.W. Huang, R. Sharma, and S. Keshav, The ENTRAPID
lation methodology and a new simulation engine Protocol Development Environment, IEEE INFOCOM'99,
architecture, the NCTUns 1.0 provides much better func- March 21-25, 1999, New York, USA.
tionality and performance than its predecessor -- the
[10] L. Rizzo, Dummynet: A Simple Approach to the Evalua-
Harvard network simulator. Its distributed and open-system
tion of Network Protocols, Computer Communication
architecture design supports remote simulations and concur- Review, Vol. 27, No. 1, p.31-41, January 1997.
rent simulations, and allows new protocol modules to be
easily added to its simulation engine. With its fully-inte- [11] S. Keshav, REAL: A Network Simulator, Technical
Report 88/472, Dept. of computer Science, UC Berkeley,
grated GUI environment, non-real-life internal designs and 1988.
implementations are totally hidden from the user. A user,
when using the GUI environment to operate a simulated [12] SSF network module (SSFnet), available at http://
www.ssfnet.org.
network, will feel like he (she) is operating a real network.
[13] A. Meyer and L.H. Seawright, A Virtual Machine Time-
Due to its unique advantages, the NCTUns 1.0 was Sharing System, IBM Systems Journal, Vol. 9, No. 3, 1970,
selected as a research demonstration at ACM MobiCom02 pp. 199-218.
international conference, held in Atlanta, USA, from 09/23/
[14] Gary R. Wright and W. Richard Stevens, TCP/IP Illustrated
2002 to 09/28/2002. The NCTUns 1.0 has been released to Volume 2, Addison Wesley, 1995.
the networking community on 11/01/2002 and its web site
is set up at http://NSL.csie.nctu.edu.tw/nctuns.html.

Acknowledgements
The authors are very grateful to the three anonymous
reviewers for their detailed and valuable comments, which
make this paper much better than its original version. This
research was supported in part by MOE program for
promoting Academic Excellence of Universities under the
grant number 89-E-FA04-1-4 and 91-E-FA06-4-4, the Lee
and MTI Center for Networking Research, NCTU, and the
Institute of Applied Science and Engineering Research,
Academia Sinica, Taiwan.

References

[1] OPNET Inc. (http://www.opnet.com).

[2] S. McCanne, S. Floyd, ns-LBNL Network Simulator. (http://
www-nrg.ee.lbl.gov/ns/).
[3] S.Y. Wang and H.T. Kung, "A Simple Methodology for
Constructing Extensible and High-Fidelity TCP/IP Network
Simulators," IEEE INFOCOM'99, March 21-25, 1999, New
York, USA.

19