I posted this over at episteme.arstechnica.com, but I figure people here will probably like it. Maybe somebody can take it and make a better general howto.

But here is a general concept:

* I am using Debian Unstable/Testing. Debian does a good job at system integration so things like VDE support is integrated into it's system for doing ifup/ifdown network interfaces. People with other distros may have to do more work.

* The default 'userspace tcp stack' was to limited for my purposes.
* I didn't want to run root scripts to add and remove tun/tap devices each time I wanted to start a new VM.
* The concept of creating a bridge to combine external and internal interfaces just runs totally counter to mobile laptop. Just a big pain. For desktops or servers it's perfect, of course.

On the software side:
KVM -- of course. (KVM-66 with Debian's 2.6.25 kernel)
vde2 -- Debian package name for the VDE userspace
Network-manager -- what I use to manage networks.
dnsmasq -- lightweight dns/dhcp server designed for making simple NAT SOHO-style routers (think Linksys home router)
Network-manager-dispatcher --- is a service that executes scripts whenever you bring a interface up or down. Like this:
scriptname wlan0 up
scriptname wlan0 down

So basically the network situation looks like this:

A = External Interfaces (interchanging between wlan0 and eth0 and getting randomly assigned network addresses)
B = VDE virtual ethernet switch.

Tun1 is assigned 172.17.0.1/16 and is the default gateway for the virtual network. (172.* networks seem rare. (tun0 is already used for VPNs on my laptop))

(internet) <---> (A) <----> (Iptables NAT firewall/router) <---> (Tun1) <----> (B) <----> (Qemu/KVM based virtual machines)

So a quick overview on how to set it up is:

FIRST:

install vde2 and dnsmasq packages.

SECOND:
Setup /etc/network/interfaces with a network interface that ties into Debian's vde scripts:

auto tun1
iface tun1 inet static
address 172.17.0.1
netmask 255.255.0.0
vde2-switch -

THIRD:
bring up tun1 (ifup tun1)

FORTH:
add your user to the vde2-net group to allow access to the VDE switch.
(addgroup username vde2-net)
(log out and log back in to make the changes go into effect)

FIFTH:

NOTE THAT THIS IS INCOMPATIBLE WITH EXISTING FIREWALLS. It's just a example. If you use a existing firewall it's your job to adapt it to work with either Debian's ifup/ifdown scripts or with network-manager dispatcher.

Add this script to:
/etc/NetworkManager/dispatcher.d/99routing

#!/bin/sh -e
# Script to dispatch NetworkManager events
#
# Runs ifupdown scripts when NetworkManager fiddles with interfaces.

if [ -z "$1" ]; then
echo "$0: called with no interface" 1>&2
exit 1;
fi

# Fake ifupdown environment
export IFACE="$1"
#export LOGICAL="$1"
#export ADDRFAM="NetworkManager"
#export METHOD="NetworkManager"
#export VERBOSITY="0"

# Run the right scripts
case "$2" in
up)
iptables -P INPUT ACCEPT
iptables -F INPUT
iptables -P OUTPUT ACCEPT
iptables -F OUTPUT
iptables -P FORWARD DROP
iptables -F FORWARD
iptables -t nat -F

iptables -A FORWARD -i $IFACE -o tun1 -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A FORWARD -i tun1 -o $IFACE -j ACCEPT
iptables -t nat -A POSTROUTING -o $IFACE -j MASQUERADE

iptables -A FORWARD -i $IFACE -o $IFACE -j REJECT
;;
down)
#
# reset the default policies in the filter table.
#
iptables -P INPUT ACCEPT
iptables -P FORWARD ACCEPT
iptables -P OUTPUT ACCEPT

#
# reset the default policies in the nat table.
#
iptables -t nat -P PREROUTING ACCEPT
iptables -t nat -P POSTROUTING ACCEPT
iptables -t nat -P OUTPUT ACCEPT

#
# reset the default policies in the mangle table.
#
iptables -t mangle -P PREROUTING ACCEPT
iptables -t mangle -P POSTROUTING ACCEPT
iptables -t mangle -P INPUT ACCEPT
iptables -t mangle -P OUTPUT ACCEPT
iptables -t mangle -P FORWARD ACCEPT

#
# flush all the rules in the filter and nat tables.
#
iptables -F
iptables -t nat -F
iptables -t mangle -F
#
# erase all chains that's not default in filter and nat table.
#
iptables -X
iptables -t nat -X
iptables -t mangle -X
;;
pre-up)
true
;;
post-down)
true
;;
*)
echo "$0: called with unknown action \`$2'" 1>&2
exit 1
;;
esac

SIXTH:
Configure Dnsmasq to issue DHCP leases and binding it to listen only on Tun1 (to avoid any conflicts with existing external networks)

I won't repeat the entire config, but lines that matter are:

# If you want dnsmasq to listen for DHCP and DNS requests only on
# specified interfaces (and the loopback) give the name of the
# interface (eg eth0) here.
# Repeat the line for more than one interface.
interface=tun1

and:

# On systems which support it, dnsmasq binds the wildcard address,
# even when it is listening on only some interfaces. It then discards
# requests that it shouldn't reply to. This has the advantage of
# working even when interfaces come and go and change address. If you
# want dnsmasq to really bind only the interfaces it is listening on,
# uncomment this option. About the only time you may need this is when
# running another nameserver on the same machine.
bind-interfaces

and:

# Uncomment this to enable the integrated DHCP server, you need
# to supply the range of addresses available for lease and optionally
# a lease time. If you have more than one network, you will need to
# repeat this for each network on which you want to supply DHCP
# service.
dhcp-range=172.17.0.2,172.17.0.200,12h

FINALLY:
Restart network-manager,
bring down then bring back up

That should be it.

----------------------------------------------------------

A sample Qemu/KVM launch command for Fedora9 is:
(note that Debian has the commands for KVM as 'kvm'. For custom compiled installs and other distros the executables will be named something else.

Also note that vdeq is vde-qemu and is used to bind the virtual machine to the switch.

Also also note that you need to make sure that each MAC address is unique)

export QEMU_AUDIO_DRV=alsa
export QEMU_AUDIO_DAC_FIXED_FREQ=48000
export QEMU_AUDIO_ADC_FIXED_FREQ=48000
export QEMU_ALSA_DAC_BUFFER_SIZE=4096

cd fedora9
vdeq kvm -smp 2 -drive file=fedora9.qcow2,if=scsi \
-hda fedora9Boot.qcow2 -cdrom /dev/cdrom \
-m 1024M -usb -soundhw es1370 -std-vga \
-usbdevice tablet -name fedora9 \
-net nic,model=virtio,vlan=1,macaddr=52:54:00:12:04:00 \
-net vde,vlan=1,sock=/var/run/vde2/tun1.ctl

(unfortunately for me the virtio block device wasn't stable...)

For Windows:

export QEMU_AUDIO_DRV=alsa
export QEMU_AUDIO_DAC_FIXED_FREQ=48000
export QEMU_AUDIO_ADC_FIXED_FREQ=48000
export QEMU_ALSA_DAC_BUFFER_SIZE=4096

cd windowsXP
vdeq kvm -hda windows.qcow2 \
-cdrom /dev/cdrom -m 512M -usb -std-vga \
-soundhw es1370 -usbdevice tablet \
-net nic,model=e1000,vlan=1,macaddr=52:54:00:12:02:01 \
-net vde,vlan=1,sock=/var/run/vde2/tun1.ctl

(e1000 is good enough for right now).

With this setup on Fedora 9 (as the guest) with the Virtio network drivers I was able to get 38.7MiB/s raw transfer speeds between the host and guest (as measured with netcat and dd) with this setup. That's 309 Mb/s in terms of network speeds. Roughly the same as non-tuned desktop performance on a gigabit ethernet line, more or less.