trickle: userland bandwidth shaper

The networking session of this year's USENIX has a paper talking about a userland bandwidth shaper created by Google engineer Marius Aamodt Eriksen (need login to download the paper, but the source code is available here).

Form Trickle's man page:

trickle is a userspace bandwidth manager.  Currently, trickle supports
the shaping of any SOCK_STREAM (see socket(2)) connection established
via the socket(2) interface.  Furthermore, trickle will not work
with statically linked executables, nor with setuid(2) executables. 
trickle is highly configurable; download and upload rates can be
set separately, or in an aggregate fashion.

The trickle daemon, an LD_PRELOAD module, works by imposing a rate cap on the bandwidth (upload, download, or both) of a process or group of processes using socket connections.

LD_PRELOAD is a way to intercept dynamic function called. You set the environment variable to your own shared library, in which you define your own functions.

User Model Linux for Wireless Network Emulation

USENIX'05 has an emulation track of 3 papers, one of which, "Running virtualized native drivers in User Mode Linux", proposes a method of using User Mode Linux along with virtual wireless network interfaces for wireless network emulation. It uses the Hostap driver in the guest OS to communicate the virtual wireless interface via TCP. While the system can be used to test ad hoc routing or other protocols, it may be only useful when the wireless network (wireless LAN, for example) is small. Good thing is, there is no need to modify the protocol implementation because it is executed in a guest OS.

Linux Netfilter Revisit

The netfilter architecture in Linux kernel 2.4 and above makes packet filtering in kernel IP stack much easier: what you need to do is implementing your "hooks" and placing it into specific places in the kernel stack. Below is picture in Paul "Rusty" Russell's 2000 Linux Journal article "Writing Modules for Netfilter".



Note that connection tracking is done in PRE_ROUTE and LOCAL_OUT, while NAT is done in PRE_ROUTE (destination NAT, such as port forwarding, for incoming connections), LOCAL_OUT (destination NAT), and POST_ROUTE (source NAT including masquerading for outgoing connections).

A very nice figure of 2.4 kernel IP handling is here

Network Emulation: Multiple Network Stacks in One Kernel

While looking into the increasingly popular virtual machine technology, I realized my previous work on network emulation could be categorized into this broad area.

To be exact, "pure" machine virtualization refers to allowing for multiple complete OSes to run top of a middle layer (always called Virtual Machine Manager VMM). Systems falling into this class are VMWare, Microsoft Virtual PC, and User Mode Linux, among others.

But in the domain of network emulation/simulation, we don't really need to virtualize everything a general purpose OS will use. Instead, we may just focus on the network protocol stack in the kernel, and protocol instances.

IMUNES is such a multi-net-stack emulator. Based on a FreeBSD kernel, IMUNES adds a vnet kernel structure to maintain global and static symbols used by the network stack code for each virtual node of the underlying cloned stack. So within each virtual node, a process (for example, a routing daemon) will only see emulated interfaces, routing tables, etc, previously configured for the virtual node. The way to bind a process to a virtual node is done by modifying process control block of the kernel.

The creation of a virtual topology using multiple virtual nodes within a kernel is enabled by the netgraph framework in the FreeBSD kernel. Another way to build virtual links is to use virtual network interfaces. In both cases, packets are handed over between virtual nodes only by reference (the socket buffer sk_buf).

In IMUNES, queueing and traffic shaping are provided by a shaper called ng_pipe, a special netgraph node. Emulated network conditions include delay, bandwidth, and bit-error-rate.

As you may have already figured out, this approach performs much better than pure virtual machine based network emulation and user-space based virtual node in terms of supporting long route path with high throughput. The downside is apparently the heavy modification made to the FreeBSD kernel.

To dig further, read the IMUNES USENIX paper.

A very good summary of software tools for networking is here (IEEE COMSOC).

My outdated network emulation page @MSU has a list of emulators. I really need to update it.....

Running Linux 2.6.11 On Dell Inspiron 5100

This weekend I decided to make my Dell Inspiron 5100 dual-boot for both Windows XP and Linux. I already have Windows there working fine. Based on the fact that I have Fedora Core II CDs burned last year when I worked for Nextel, I chose to use Fedora but with latest kernel. At least 16 hours have been taken for this job. Be patient.

Section 0: Create a partition using ntfsresize in Knoppix, the well-known single-CD Linux system. This allows resizing an NTFS partition (the laptop only has one disk). The guide to this step is here. Now I have a 10G partition for Linux.

Section 1: Big trouble with the CD drive on my Inspirion 5100. It seems when it continues to read for sometime (let's say 1 hour), the CD drive will ALWAYS report read error as it is getting very hot. Thus there is no way to have a pretty complete installation of Fedora; I have to wait until it cools down. I ended up using my old Redhat 9 3-CD set, and chose "minimal" package selection - No KDE or GNOME, no kernel source, etc. Eventually I got a Redhat 9 with kernel 2.4.20 on my laptop. Now I wanted to make the network work.

Section 2: Old kernels (2.4.x) do not have support for the built-in Broadcom 4401 Ethernet interface in Dell Insprion. But Broadcom provides a Linux driver here. Download and compile, follow the readme, and it worked.

Section 3: Grab the 2.6.11 kernel from kernel.org. A good article about this step is here. The 2.6 kernel changed several modules names, as well as in-kernel module loader interfaces. So I must download the module-init-tools and replaced those "modprobe", "insmod" stuff with the new ones. The 2.6 kernel has bcm4400 support, and the module is named "b44". A kernel configuration is for the bcm 4400 support. After compilation, as the article suggested, I modified modprobe and rc.sysinit for usb mouse, etc. Then modified grub. Rebooted.

Section 4: Make the build-in TrueMobile (broadcom 1300) work. After some google search, I figured out (ndiswrapper + Dell TrueMobile driver) is the solution. Downloaded both of them and followed the installation guide. At some point, the "make" did not proceed because my system does not have the docbook2html tool. Then I configued the wlan0 to be automatically up and hook to my access point, with proper IP setting. Then in rc.local, added a default gateway through my desktop proxy server and bring down the built-in ethernet interface (eth0), which will automatically remove the routes associated with it in the routing table.

Section 5: Get apt, kde, firefox, etc. Installing rpms onto a Linux system always ends up with dependency hell. Apt makes this process extremely easire. I also tried Yum, but gave up later.

Section 6: Since I use ssh a lot from the laptop, I don't want to always use my gateway machine as the intermediate hop. I want to directly ssh to a remote box. The solution is to use connect.c (created by Shun-ichi Goto) with openssh.

Lessions learned:
a. Never underestimate the time you're gonna take to do a Linux installation on a laptop. You need a lot of time searching online and playing directly with packages, sometime you have to hack it your self.

b. RPM dependency is a hell. Because my CD drive does not always work, getting needed rpms for a special package is a pain in the neck. Get your network ready and use apt as sooner as possible.

c. Dell Inspiron is hot! (after the CD drive spins for some time).

Zero-Copy in Linux Kernel

Found a (supposedly) outdated doc on Zero Copy in Linux Kernel written by Dragan Stancevic. The article clearly explains how send() and "sendfile()" differ from kernel's perspective.

Using sendfile(socket, file, len), Data from a disk is first DMA-copied into kernel buffer, then the kernel socket buffer only collects descriptors (not the data!) of those skbs. Eventually the NIC performs DMA-gather over the socket buffer(skb descriptors) and the kernel buffer(data) into NIC's transmission ring buffer. Thus this operation (zero-copy in kernel) requires the NIC support scatter-gather DMA.