01-10-2012, 11:31 AM
NIST Net – A Linux-based Network Emulation Tool
[attachment=34886]
Abstract
Testing of network protocols and distributed applications has become increasingly complex, as
the diversity of networks and underlying technologies increase, and the adaptive behavior of applications
becomes more sophisticated. In this paper, we present NIST Net, a tool to facilitate testing and
experimentation with network code through emulation. NIST Net enables experimenters to model
and effect arbitrary performance dynamics (packet delay, jitter, bandwidth limitations, congestion,
packet loss and duplication) on live IP packets passing through a commodity Linux-based PC router.
We describe the emulation capabilities of NIST Net; examine its architecture; and discuss some of
the implementation challenges encountered in building such a tool to operate at very high network
data rates while imposing minimal processing overhead. Calibration results are provided to quantify
the fidelity and performance of NIST Net over a wide range of offered loads (up to 1 Gbps), and a
diverse set of emulated performance dynamics.
Introduction
Testing network protocols and applications has always been a difficult task, but current trends in Internet
software and hardware complicate matters in many ways. Networks do not simply get “faster,” but more
diverse, carrying more diverse traffic as well. Link technologies vary widely in bandwidth, latency, and
error and loss rates, and may be highly asymmetric. Overall network dynamics can fluctuate wildly, with
spot congestion and failures common. The demands that applications make of networks vary widely as
well, often taking on near-real-time characteristics that differ fundamentally from the best-effort delivery
typically provided by current networks. Applications and protocols in consequence increasingly employ
adaptive mechanisms to makemore intelligent use of available network resources. But these, too, present
new testing challenges: the “correct” behavior of adaptive code cannot be defined statically or often even
in any simple deterministic fashion; and adaptive protocols at different levels or on different systems may
interact poorly with each other in ways not easily detectable while testing in isolation.
Related work
Network emulators have been implemented in the past for a variety of purposes on a variety of systems.
Among them we can mention Dummynet for FreeBSD [1], the Hitbox pseudo-device for SunOS [2], the
MOST Radio network emulator [3], the Ohio Network Emulator [4], the Orchestra fault injection tool
[5], Trace-based mobile network emulation [6], the emulation capabilities in the Vint/NS simulator [7],
and the X-kernel simulator/live test environment [8].
Of these, the NIST Net kernel design most closely resembles the SunOS-based Hitbox, while its
user interface was inspired in part by that of the MOST radio network emulator. However, none of these
were designed to operate at the high data rates, nor offer the same range of capabilities, as NIST Net.
In particular, none of these emulators make use of a separate high-speed clock for packet scheduling,
and hence they cannot achieve the same degree of precision in delay modeling. While some of the
emulators, such as Dummynet, employ sophisticated queuing models for bandwidth modeling, none
of them include delay models of much statistical sophistication. NIST Net’s approach of combining a
relatively powerful set of capabilities with a very simple and easily-understood interface seems unique
in this area.
NIST Net emulator architecture
The emulator which implements this functionality consists of an instrumented version of a live network
implementation, the Linux (2.0.xx – 2.4.xx) kernel. NIST Net consists of two main parts: (1) a loadable
kernel module, which hooks into the normal Linux networking and real-time clock code, implements
the run-time emulator proper, and exports a set of control APIs; and (2) a set of user interfaces which
use the APIs to configure and control the operation of the kernel emulator (see Figure 2).
This organization of the emulator provides several advantages. Since all of the kernel functionality is
incorporated into a loadable module, the emulator may be taken up or down, patched and reloaded during
runtime, without interrupting any active connections, including those flows currently being affected by
the emulator. The separation into a module also serves to insulate the NIST Net code to a large degree
from changes to the base kernel.
The separation between emulation proper and the user interface allows multiple processes to control
the emulator simultaneously. This is useful when controlling the emulator both interactively, and with
parameters generated from previously-taken traces. New emulator settings may be loaded continuously,
even to control currently-active flows; as discussed further below (section 3.1), kernel data structures
are handled in such a way as to minimize the locking required.
NIST Net indexing structures
Emulator entries are stored in a table, which must be accessible both at task time (so user-level code may
enter new settings) and at interrupt time (so that the packet matching code may look up entries when
new packets arrive). Table lookup needs to be relatively fast to keep up with packet arrival rates, and yet
needs to provide a flexible wildcard matching scheme. To meet these requirements, we use a two-level
hash table to hold the emulator settings. A two-level hash table is a hash table with chaining, where the
chains themselves are redistributed into secondary hash tables (using a secondary hash function) if they
become too long (Figure 4).
NIST Net statistical generation
NIST Net uses a set of statistical routines to generate the parameters for the impairments it applies to
network traffic. The routines used need not be realistic models of the actual internal mechanisms of
networks and routers, but should be computationally simple, and yet adaptable enough to imitate a wide
range of network behaviors. In this context, computationally simple means two things: that generation
of values needed for delays and other effects must be fast enough to keep up with packet receive rates
(up to hundreds of thousands per second); and that any kernel-based calculations must be done using
only integral or fixed-point arithmetic. (Linux does not support using the floating point unit in kernel
mode.) Calculations done outside the kernel may be arbitrarily complex, but kernel memory constraints
limit how much data (such as distribution table values) can be stored in the kernel at any one time.
Adaptable here means that the routines should be parameterized in terms of quantities (such as mean.
Improved generation methods
The method described above is computationally trivial and adequate for most purposes, but clearly can
be improved upon. Its most obvious drawback is that it only considers correlation between successive
delays and not longer-term correlation. Longer-term correlations as generated by NIST Net drop off
exponentially at a much faster rate than real delays (see Figure 7). At a user level, this results in a
perceptibly greater degree of “roughness” in the generated distribution – a greater degree of variability
over randomly-chosen segments of the generated delays than is seen on average in real delay data.
In the latest version of NIST Net, we take advantage of the ability to graft on external statistics
generation code, to introduce a more sophisticated method which better handles longer term correlations.
The external method itself uses a two-level approach. The first level is based on Riedi’s hybrid
multifractal wavelet model (MWM) [17]. Originally devised to model bandwidth utilization at routers,
MWM also works well at modeling end-to-end network delay patterns.
Conclusion
In this paper, we have described the design and implementation of the NIST Net emulator, in particular
the techniques employed to allow line-rate operation of emulation functions while still providing useful
models of real end-to-end network performance dynamics. We presented some of the initial results of
our ongoing efforts to improve the fidelity of the NIST Net statistical models, and to calibrate emulator
functions.
[attachment=34886]
Abstract
Testing of network protocols and distributed applications has become increasingly complex, as
the diversity of networks and underlying technologies increase, and the adaptive behavior of applications
becomes more sophisticated. In this paper, we present NIST Net, a tool to facilitate testing and
experimentation with network code through emulation. NIST Net enables experimenters to model
and effect arbitrary performance dynamics (packet delay, jitter, bandwidth limitations, congestion,
packet loss and duplication) on live IP packets passing through a commodity Linux-based PC router.
We describe the emulation capabilities of NIST Net; examine its architecture; and discuss some of
the implementation challenges encountered in building such a tool to operate at very high network
data rates while imposing minimal processing overhead. Calibration results are provided to quantify
the fidelity and performance of NIST Net over a wide range of offered loads (up to 1 Gbps), and a
diverse set of emulated performance dynamics.
Introduction
Testing network protocols and applications has always been a difficult task, but current trends in Internet
software and hardware complicate matters in many ways. Networks do not simply get “faster,” but more
diverse, carrying more diverse traffic as well. Link technologies vary widely in bandwidth, latency, and
error and loss rates, and may be highly asymmetric. Overall network dynamics can fluctuate wildly, with
spot congestion and failures common. The demands that applications make of networks vary widely as
well, often taking on near-real-time characteristics that differ fundamentally from the best-effort delivery
typically provided by current networks. Applications and protocols in consequence increasingly employ
adaptive mechanisms to makemore intelligent use of available network resources. But these, too, present
new testing challenges: the “correct” behavior of adaptive code cannot be defined statically or often even
in any simple deterministic fashion; and adaptive protocols at different levels or on different systems may
interact poorly with each other in ways not easily detectable while testing in isolation.
Related work
Network emulators have been implemented in the past for a variety of purposes on a variety of systems.
Among them we can mention Dummynet for FreeBSD [1], the Hitbox pseudo-device for SunOS [2], the
MOST Radio network emulator [3], the Ohio Network Emulator [4], the Orchestra fault injection tool
[5], Trace-based mobile network emulation [6], the emulation capabilities in the Vint/NS simulator [7],
and the X-kernel simulator/live test environment [8].
Of these, the NIST Net kernel design most closely resembles the SunOS-based Hitbox, while its
user interface was inspired in part by that of the MOST radio network emulator. However, none of these
were designed to operate at the high data rates, nor offer the same range of capabilities, as NIST Net.
In particular, none of these emulators make use of a separate high-speed clock for packet scheduling,
and hence they cannot achieve the same degree of precision in delay modeling. While some of the
emulators, such as Dummynet, employ sophisticated queuing models for bandwidth modeling, none
of them include delay models of much statistical sophistication. NIST Net’s approach of combining a
relatively powerful set of capabilities with a very simple and easily-understood interface seems unique
in this area.
NIST Net emulator architecture
The emulator which implements this functionality consists of an instrumented version of a live network
implementation, the Linux (2.0.xx – 2.4.xx) kernel. NIST Net consists of two main parts: (1) a loadable
kernel module, which hooks into the normal Linux networking and real-time clock code, implements
the run-time emulator proper, and exports a set of control APIs; and (2) a set of user interfaces which
use the APIs to configure and control the operation of the kernel emulator (see Figure 2).
This organization of the emulator provides several advantages. Since all of the kernel functionality is
incorporated into a loadable module, the emulator may be taken up or down, patched and reloaded during
runtime, without interrupting any active connections, including those flows currently being affected by
the emulator. The separation into a module also serves to insulate the NIST Net code to a large degree
from changes to the base kernel.
The separation between emulation proper and the user interface allows multiple processes to control
the emulator simultaneously. This is useful when controlling the emulator both interactively, and with
parameters generated from previously-taken traces. New emulator settings may be loaded continuously,
even to control currently-active flows; as discussed further below (section 3.1), kernel data structures
are handled in such a way as to minimize the locking required.
NIST Net indexing structures
Emulator entries are stored in a table, which must be accessible both at task time (so user-level code may
enter new settings) and at interrupt time (so that the packet matching code may look up entries when
new packets arrive). Table lookup needs to be relatively fast to keep up with packet arrival rates, and yet
needs to provide a flexible wildcard matching scheme. To meet these requirements, we use a two-level
hash table to hold the emulator settings. A two-level hash table is a hash table with chaining, where the
chains themselves are redistributed into secondary hash tables (using a secondary hash function) if they
become too long (Figure 4).
NIST Net statistical generation
NIST Net uses a set of statistical routines to generate the parameters for the impairments it applies to
network traffic. The routines used need not be realistic models of the actual internal mechanisms of
networks and routers, but should be computationally simple, and yet adaptable enough to imitate a wide
range of network behaviors. In this context, computationally simple means two things: that generation
of values needed for delays and other effects must be fast enough to keep up with packet receive rates
(up to hundreds of thousands per second); and that any kernel-based calculations must be done using
only integral or fixed-point arithmetic. (Linux does not support using the floating point unit in kernel
mode.) Calculations done outside the kernel may be arbitrarily complex, but kernel memory constraints
limit how much data (such as distribution table values) can be stored in the kernel at any one time.
Adaptable here means that the routines should be parameterized in terms of quantities (such as mean.
Improved generation methods
The method described above is computationally trivial and adequate for most purposes, but clearly can
be improved upon. Its most obvious drawback is that it only considers correlation between successive
delays and not longer-term correlation. Longer-term correlations as generated by NIST Net drop off
exponentially at a much faster rate than real delays (see Figure 7). At a user level, this results in a
perceptibly greater degree of “roughness” in the generated distribution – a greater degree of variability
over randomly-chosen segments of the generated delays than is seen on average in real delay data.
In the latest version of NIST Net, we take advantage of the ability to graft on external statistics
generation code, to introduce a more sophisticated method which better handles longer term correlations.
The external method itself uses a two-level approach. The first level is based on Riedi’s hybrid
multifractal wavelet model (MWM) [17]. Originally devised to model bandwidth utilization at routers,
MWM also works well at modeling end-to-end network delay patterns.
Conclusion
In this paper, we have described the design and implementation of the NIST Net emulator, in particular
the techniques employed to allow line-rate operation of emulation functions while still providing useful
models of real end-to-end network performance dynamics. We presented some of the initial results of
our ongoing efforts to improve the fidelity of the NIST Net statistical models, and to calibrate emulator
functions.