Software Infrastructure for Accurate Active Probing

Table of Contents

• Introduction to Active Probing Software
• Linux Probing Package
• TSC Based Clock
• TSC-Linux Probing Package
• TSC-RT-Linux Probing Package
• Robust Synchronisation of TSC Based Clock

Introduction to Active Probing Software

On this page we make available generic software supporting accurate active probing. As described in the introductory presentation on the Active Probing page, active probing involves both packet monitoring and precision packet sending. Both rely fundamentally on an accurate underlying clock, and a rapid and consistent timestamping operation. The software below, the same used in the work described on the publications page, supports each of these. The code was originally developed by Attila Pásztor as part of his PhD thesis. It is designed for use on common PC platforms running UNIX. Specifically, it was developed primarily on Pentium based machines running Linux (BSD is also possible).

The code provides a generic low level probing ability, where any probe stream can be defined, sent, and received. It does not apply higher level analysis methods to the resulting raw end-to-end data to measure quantities such as bottleneck bandwidth in the manner of pathchar. Such measurement `tools' could however be developed using the low level capabilities of the packages. Implementation of some of the estimation techniques developed in the testbed will be made available in due course in the form of probe stream definitions as input to the package(s), plus Matlab post-processing modules.

Five different packages are supplied below. The first provides the basic functions needed for one-way active probing based on UDP packets which should work on any Linux platform. It provides similar top level routines to the other packages, and can be used to begin probing work with a minimum of fuss. The software supports generic one-way measurements. Round-trip measurements can be performed simply by using the same machine as sender and receiver (however in this case the packets will have to be `turned around' by some other means).

The basic package however suffers from poor timing accuracy which seriously limits its capabilities for many purposes. To address this, we provide a TSC Clock package supplying an alternative to the standard system clock with several advantages. Building on this timing solution, the third package provides a Linux based sender, timestamping, and receiver solution for one-way active probing based on UDP packets with an order of magnitude superior performance. In the fourth a Real-Time Linux solution is described which, at the cost of greater installation difficulties, offers the same functionality with a performance limited only by that of hardware - an order of magnitude better again. Finally, for those lucky enough to have access to DAG card hardware monitoring, we also provide documentation and scripts to show how the monitoring components of probing, performed by a DAG, can be integrated into the sending components of the Linux, TSC-Linux, or TSC-RT-Linux flavours.

Robust Synchronisation : A sixth package is under development. It implements recent work allowing not just rate calibration/synchronisation, but also absolute synchronisation of the TSC clock. It is described further below.

In addition, a simulator package written in C, allowing the efficient simulation of active probing experiments with definable cross traffic, is also included. A set of simple Matlab routines are included which take the raw timestamp data from an experiment and perform some basic analysis and filtering.

Linux Probing Package

This package should work with any Linux system provided the basic utilities listed below are available. No special hardware, kernel or NIC drivers are required. It has been tested on the systems described in the testbed machines.

The main components of the probing infrastructure are as follows:

• Clock:   standard software clock.
• Clock Synchronisation:   None if NTP off, else NTP (see below).
• Timestamping:   via standard getimeofday system call to read the standard software clock.
• Sender:   user level program using standard system calls and `hybrid timing' (sleep then active wait).
• Sender monitor:   None. One hopes the system calls deliver the packets close to the desired `target times'.
• Receiver:   tcpdump can be used as a combined packet sink (avoids port-unreachable messages returning to sender), and monitor as explained below.
• Receiver monitor:   tcpdump (filter on known sender address and port). Timestamps are made via bpf filters which in turn use getimeofday.

To improve performance it is very strongly recommended that the sender and/or receiver machines be running in text rather than graphics mode, with a minimum of competing processes, to minimize timing errors due to operating system scheduling. Furthermore, it is strongly recommended that NTP be switched off. The software clock will deliver much better rate performance if this is done. The exception is for the measurement of one-way end-to-end delay where NTP should be switched on.

The software itself, documentation on its use, and a set of hints and tips, can be found at the links below.

• Software:  The only software required is the packet sending routines available in the Linux packet sender package.
• Documentation:  The linux packet sending package consists of the packet sender linuxps(8), and a user application which is used to interface to the packet sender linuxSend(8). You may also want to use the post-processing programs to analyse your results using Matlab, details of which can be found in the active probing software documentation, along with other useful pieces of information.
• Troubleshooting guide:  The troubleshooting guide contains additional tips for using the software.

TSC Based Clock

As described in detail in the paper PC Based Precision Timing Without GPS, the standard software clock has numerous drawbacks which can be avoided through the definition of a clock based on the TSC register which counts CPU cycles. This clock replaces the first three of the components above. Note that here we provide a stand alone package for the clock only, with no application specific component. No special kernel support is needed, although optimising timestamping for a particular application may require it, as we see below for TSC-Linux monitoring.

• Clock:   TSC register based, called `TSC-Linux'. The underlying clock features high resolution (1ns for a Gigahertz processor), hardware updating, and rate stability of 0.1PPM in stable air conditioned environments.
• Clock Synchronisation:  
  • Rate:   measurement of the TSC period performed using the NTP synchronised standard software clock over long periods, using tscskewd (another method is described in the paper above but not implemented here).
  • Offset:   None (under development). None is needed when calculating time differences using the same clock (eg for traffic monitoring, needed only when measuring one-way delay). This includes any approach using probe inter-arrival times or delay variation values as a basis.
• Timestamping:  
  • Raw:   reading the TSC register (register updated by hardware) using the standard rdtsc assembly procedure.
  • Time units:   Register counter values can be converted to time units using clock calibration values (currently the TSC period value is meaningful) read out using readtscskew.

Whenever possible, raw TSC counter `time'stamps should be used because they require the lowest overhead. These can be obtaining via an assembly procedure as described in the section How can I read the TSC register directly in my programs? of the active probing documentation. Conversions to time measured in seconds should by ideally performed only in user space with low priority when necessary. This helps to minimize processor load which helps to prevent any scheduling based errors for other timestamps. A convenient function for converting TSC counter values to seconds will be made available soon. For the moment, please refer to this partial solution.

In this case, NTP should be switched on so that tscskewd can correctly estimate the TSC period over time. Thus an NTP disciplined software clock and a TSC-Linux clock co-exist in this scenario, but run independently. It is strongly recommended that a nearby, reliable stratum-1 NTP server be used with a close to symmetric out and return route to the host. X-Windows should not be used to help prevent any scheduling related delays.

• Software:   All that is needed to obtain the correct conversion constant is the tscskew daemon package. A convenient function for converting the TSC counter value to time using the available offset and TSC period estimates will be made available soon.
• Documentation:   The above tscskewd software package provides a daemon, tscskewd(8) which continually estimates the conversion constant, and user program readtscskew(1) which can be used to read out the current conversion constant estimate. Refer to the active probing software documentation page for further details including more detailed information about TSC accuracy and details on how to read out the conversion constant in C programs via the shared memory area that tscskewd sets up.
• Troubleshooting guide:   Continuously updated set of hints, tricks and examples.

Robust Synchronisation Package for TSC Clock

As described in detail in the preprint Robust Synchronisation of Software Clocks Across the Internet, by taking advantage of the high stability of the CPU oscillator via the TSC clock, it is possible to provide, not only efficient rate calibration, but also absolute synchronisation using NTP servers across a network with errors of the order of 0.1ms and below. The algorithms are very robust to a wide variety of network realities such as congestion, loss of connectivity, and also temperature variations and even problems with the NTP servers themselves. Note that the novelty of these clock is not simply that the TSC is employed, but the filtering algorithms used and the principles on which they are based.

A new C implementation of the synchronisation algorithm is now available. It is an enhanced version of the algorithms described in the IMC-2004 paper. It is being made available here to serve as a documented version of the full algorithm. A full set of routines will be made available soon for actual use.

The package is under development. When available, it will allow the standard NTP synchronised software clock to be entirely replaced by a TSC based clock with much enhanced performance. A stable implementation of the algorithms and the interfaces to the lower level (ie collecting raw timestamps out of NTP packets) and `upper' level (ie the function(s) which return(s) the time) is in progress. Initially this will be under BSD, however the core of the code will be user level and entirely transferable (the rate calibration part of this package will supersede that described above and will be much more robust).

TSC-Linux Probing Package

As described in detail in the paper PC Based Precision Timing Without GPS (see also A Precision Infrastructure for Active Probing), the TSC based clock described above can be used as a basis of an improved probing infrastructure. One possibility is to simply modify the Linux package above to make use of the TSC clock. However, better performance can be obtained by providing greater support to TSC-based timestamping via kernel data structures in the device independent networking code and/or via a modified NIC driver. Thus, the solution provided below requires a modified kernel (and for even more accuracy, a modified NIC driver). Here a 2.4.14 kernel with three modifications to network specific code, which we refer to as the 2.4.14-tsc kernel, is provided. For details about the three modifications read the section What changes were made to the original kernel to produce the 2.4.14-tsc kernel? on the software documentation page.

• Sender:   coordinated kernel and user level programs using raw TSC timestamps and `hybrid timing' (sleep then active wait).
• Sender monitors:  
  • Use modified tcpdump to get raw TSC timestamp and convert to standard timestamp format with 1 microsecond resolution.
  • Use normal tcpdump to get raw TSC timestamp, can be converted to time manually in user space.
• Receivers:  
  • simple sink process listening to port (avoids port-unreachable messages returning to sender).
  • two combined sink and monitor solutions, as below.
• Receiver monitors:   (requires the modified kernel)
  • raw TSC timestamps are made within a modified NIC driver, and accessed using the kernel from within the receiver program.
  • modified tcpdump gets TSC timestamp, convert to time in standard format (also sinks packets).

To improve performance, the same comments apply as for the Linux solution regarding text mode. Regarding NTP, it must be turned on if the tscskewd daemon is being used to measure the TSC period, although it does not interfere with the clock itself.

• Software:   One first needs to download the TSC software as above. The 2.4.14-tsc modified kernel is also needed. The package includes the modified 3c59x-tsc driver. The other packages that should be downloaded are tscskewd-0.2 (as explained in the previous section) and the TSC-Linux packet sender package.
• Documentation:   Three routines use raw TSC "counter stamps" directly. Two of these support sending: the kernel level packet sending utility tsclinuxps(8), and the user level TSC-Linux packet sender tsclinuxSend(8), which is used to queue packets to be delivered by the kernel level sender as needed. The tscreceiver(8), program functions as a combined receiver and receiver monitor via the modified NIC driver. For details about what sections of the kernel were modified to enhance the timing of the 2.4.14-tsc kernel and more details regarding the TSC-based linux packet sender/receiver code refer to the active probing software documentation page.
• Troubleshooting guide:   Continuously updated set of hints, tricks and examples, including a patch to the 2.4.14-tsc kernel for ext3 file systems, an example .config file for compilation, and more.

TSC-RT-Linux Probing Package

As described in detail in the paper PC Based Precision Timing Without GPS and A Precision Infrastructure for Active Probing, the use of a real-time operating system can reduce scheduling problems, which are still present (although much reduced) in the TSC-Linux solution above, to zero, leaving only hardware limitations such as interrupt latency to limit timestamping and sender accuracy. The `proof of concept' package available here based on the freely available real-time Linux package (RT-Linux) has the following features:

• Clock:   TSC register based, called `TSC-RT-Linux'.
• Clock Synchronisation:  
  • Rate:   measurement of the TSC period performed using the NTP synchronised standard software clock over long periods.
  • Offset:   None (under study).
• Timestamping:  
  • Raw:   reading the TSC register (register updated by hardware) performed under RT-Linux.
  • Time units:   Register counter values converted to time units later in user space using measured period (read out using readtscskew).
• Sender:   coordinated RT-Linux and user level Linux programs using raw TSC timestamps and `hybrid timing' (sleep then active RT-Linux wait).
• Sender monitor:   None, and no point attempting it from within the sender itself, as the sending solution is already as good as it can be with the available hardware.
• Receiver:   simple sink process listening to port (avoids port-unreachable messages returning to sender).
• Receiver monitor:   raw TSC timestamps are made within a modified NIC driver.

As RT-Linux appears as part of the hardware to Linux, there is no problem with a normal Linux environment co-existing with this infrastructure. The caveat is that a separate NIC is needed to support networking under RT-Linux (using the RT networking package), and that the driver support for this package is very poor. The RT-Linux solution is not being actively supported at present, the package below is supplied very much as is.

• Software:  The package does not use the TSC package above but instead implements its own, analogous TSC based clock. However it does make use of the same period measurement modules in tscskewd-0.2 as explained in the previous section. The 2.2.14-rtl2.2 modified kernel is needed. The package includes the modified 3c59x_rt_old_tsc driver. The other packages that should be downloaded are the modified RTNet-0.9 RT networking package and the TSC-RT-Linux packet sender package.
• Documentation:  The original real-time packet sending documentation contain what is currently available for the packet sending software. Details about post-processing utilities are given in the general active probing software documentation guide. The troubleshooting guide below contains detailed installation instructions for the 2.2.14-rtl2.2 kernel and RTNet package.
• Troubleshooting guide:   The troubleshooting guide provides a detailed step-by-step installation guide for installing the 2.2.14-rtl2.2 kernel. Details about the real-time packet sending package are available in the documentation section above.

PSIM Simulator Package

This simulator is not a full simulator of router functionality across a network, but rather provides numerical evaluation of the analytic solution to a multi hop route model with FIFO store and forward nodes. Its features are...

More details to come...