[Click] Announcement: IPMP for Click

Fri Nov 19 06:52:54 EST 2010

Hi all!

---
I have developed a Click module for IPMP, Matthew Luckie (et al.) 's IP
Measurement Protocol. IPMP is useful for per-hop path evaluation,
combining the advantages of traceroute and the IP record route option.

It can be downloaded at
https://github.com/hacklschorsch/click-packages/tree/ipmp . I'd be
grateful for any feedback. If you know how to publish the source so it's
most easily usable, please tell me (@Eddie: I initiated a pull request
to Click-Packages, as that's my best guess where to put this code.)
The userland utilies can be downloaded at
https://github.com/hacklschorsch/ipmp-userland .
---

Now the detailed (tl;dr) version:

In the course of my 80211-mesh related thesis I have created a Click
element that does the router-side ("server" side?) of IPMP, the IP
measurement protocol.

IPMP is useful for measuring the path an IP packet travels to its
destination (and back: the forward- and reverse paths are recorded).

At every hop, IPMP adds a so-called Route Record (the router IP and a
timestamp) into the payload of the packet before forwarding it. This
combines the advantages of the IP record route option and common
traceroute. Optionally, a flow counter on each router helps in
determining which links of a multi-hop path are lossy.

IP record route
* can record no more than 9 hops due to the limited IP header size
* does not have per-hop time stamps
* does not exist in IPv6

Traceroute
* uses lots of packets (compared to IP RR and IPMP)
* may infer a route that doesn't even exist (if routes flap
   during probing)
* cannot infer the reverse path

Here is some example output from the ipmp_ping tool, host 10.20.1.9 IPMP
pinging 10.20.5.9. The right-most number is the flow counter; The last
hop (4->5) lost one probe. Second-most to the right is the time stamp in
µs precision. (IPMP supports nanosecond precision, but our router
platform does not). As you can see, this link is asymmetric, having only
two hops on its reverse path.
# ipmp_ping -4 -R  -s 1200 10.20.05.09 -t 1 -c 1000
[...]
 > * 0   127.0.0.1  Oct  8 16:14:11 2010 367233000 0
 >   1  10.20.4.33  Oct  8 16:14:11 2010 370650000 7
 >   2   10.20.4.9  Oct  8 16:14:11 2010 372399000 7
 > * 3   10.20.5.9  Oct  8 16:14:11 2010 373934000 7
 >   4  10.20.4.33  Oct  8 16:14:11 2010 375663000 7
 > * 5   10.20.1.9  Oct  8 16:14:11 2010 378716000 6
 > forward path = 3 hops, reverse path = 2 hops
 > rtt: 11ms
[...]

This is sample output from the ipmp_pathchar tool, which uses IPMP and a
PacketPair technique to infer link bandwidth. Unfortunately, this
technique does not work well on wireless (especially multi-hop)
networks, for various reasons.
# ipmp_pathchar  -4 -R -s 1200 10.20.05.09
 > ipmp_pathchar 10.20.05.09: minsize 108, maxsize 1200, tx/rx 144/129,
paths 1     127.0.0.1 -> 10.20.4.33 : 2394 kbps [min 437 max 7131]
 > 10.20.4.33 ->  10.20.4.9 : 5560 kbps [min 4927 max 140903]
 >  10.20.4.9 ->  10.20.5.9 : 9972 kbps [min 859 max 30545]
 >  10.20.5.9 -> 10.20.4.33 : 2532 kbps [min 985 max 22285]
 > 10.20.4.33 ->  10.20.1.9 : 6938 kbps [min 2591 max 26234]

Both, ipmp_ping and ipmp_pathchar, are available from
https://github.com/hacklschorsch/ipmp-userland .

I have tested the ipmp_el Click element on

* i386 Linux 2.6
* x86_64 Linux 2.6 with Click-1.7.0, 1.8.0 and a recent master
* x86_64 on FreeBSD 8.something with Click 1.8.0
* mips Linux 2.6 (OpenWRT (WRT54GS routers))
* armv5teb Linux 2.6 (OpenWRT on avila (XScale))

I look forward to any feedback! My thesis is still running, maybe I can
cite you :)

Greetings from Munich,

Florian

PS: Also see my mail to this list from 2010-06-16:
Florian Sesser wrote:
 > Hi all!
 >
 > For my diploma thesis, I am analysing the performance of our MANET mesh
 > algorithm - SSR / Scalable Source Routing [1] - on a physical 802.11a
 > mesh network that is running Click (see BOWL [2]).
 >
 > I plan to compare SSR to OLSR and DSR.
 >
 > Now I need an underlay-agnostic measurement framework that will help me
 > analyse the paths taken by packets on their way through the network,
 > together with some performance statistics (read: timestamps).
 >
 > I envision something like IPMP [3], which I see as a "ip record route"
 > option on steroids.
 >
 > I haven't found something looking complete enough implementation-wise
 > for me to just use, with Click or without. In Click, all the primitives
 > ("stamp addr into packet payload", "stamp timestamp into packet
 > payload", etc) are there, so hacking together rudimentary IPMP support
 > should be very feasible. Still, I do not need to re-invent the wheel.
 >
 > Now, do you guys know of something simpler / quicker / more complete /
 > working? Or a better way of doing what I want? Would you be interested
 > in an IPMP implementation for Click, or is that already in progress and
 > I just didn't stumple over it?
 >
 > Thank you!
 >
 > Greetings from Munich,
 >
 > Florian
 >
 >
 > [1] http://www.so.in.tum.de/wiki/index.php5/Scalable_Source_Routing
 > [2] http://bowl.net.t-labs.tu-berlin.de/
 > [3] i.e. http://www.wand.net.nz/~mluckie/pubs/mluckie-thesis.pdf
 >      (not the IPMP you find on wikipedia, which is about multipathing)
 > _______________________________________________
 > click mailing list
 > click at amsterdam.lcs.mit.edu
 > https://amsterdam.lcs.mit.edu/mailman/listinfo/click