Solution to Mobile IPv6 routing

Posted 4 Mar 2007 at 01:51 UTC (updated 5 Mar 2007 at 01:54 UTC) by lkcl Share This

This article outlines an algorithm for solving routing on IPv6 mobile IP networks: treating the internet as a 48-dimensional hypercube, and using zeroconf to find your local neighbours.

Could someone _please_ double-check this: these are my notes, and i would like to know if this is correct. i think it even works with broadcast, with a bit of tweaking.

basically, you use divide-and-conquer, by having routing on EVERY machine, not just gateways.

using zeroconf, you find out who is in your area - they get allocated unique IPv6 addresses (hooray). this is really important (the unique bit).

you then have 48 bit-buckets (32 for IPv4), and for every bit which matches in YOUR ip address, you drop them into that bit bucket:

        buckets = {}
        for i in range(48):
                buckets[i] = []

for (other_ip, interface) in zeroconf_neighbourhood(): xor_addresses = my_ip ^ other_ip for i in range(48): if xor_addresses & (1<

then - routing is _incredibly_ simple:

        if packet_ip == my_ip:
                return deliver_it(packet, my_interface)

xor_addresses = my_ip ^ packet_ip bits_match = 0 best_route = None for i in range(48): for (route_ip, route_interface) in buckets[i]: count_bits = count_bits(packet_ip ^ route_ip) if count_bits > bits_match: best_route= (route_ip, route_interface)

if best_route: route_ip, route_interface = best_route return deliver_it(packet, interface)

return None # drop the packet.

sending to the nearest destination is automatic. no hop-count needed. you always pass the packet to a location which has less bit-difference from you.

this is the n-cube algorithm.

comments, please.

ok..., posted 4 Mar 2007 at 10:21 UTC by lkcl » (Master)

this brilliant idea occurred to me in a flash - and then i realised that actually it was only a small part of the larger picture :)

the above idea assumes that interconnectivity is complete, otherwise, like the "maze walk" algorithm, you can only reach your destination by turning left, left, left, left...

so, the above algorithm can be applied in sub-stages, in a layered manner, to make it manageable.


the IP address shouldn't be the deciding factor: geographic location should be the deciding factor.

so, you route by geographic location, and you route up to a gateway (any gateway) which feeds onto a smaller grid, which "gloms" your "address" into less accurate groups (truncating the least significant bits).

by having a less accurate table, you can at least maintain that entire table in memory.

in this way, if you don't _know_ your geographic location, you can at least route to someone who does.

discovery and refinement of routing, posted 4 Mar 2007 at 11:06 UTC by lkcl » (Master)

orrr.... :)

the algorithm could be used as part of a larger picture to help determine a more efficient routing topology.

one of two ways.

1) use it as a traceroute algorithm.

2) record the links which have been walked already: this would allow you to back-track and _eventually_ reach the destination ip address.

each node that receives a packet which was back-tracked to it could then record "hmm, packets to this address don't work down there..."

heck - that might even work :)

for the record...., posted 20 Oct 2008 at 13:07 UTC by lkcl » (Master)

further thought on this, many many months later, leads me to realise that the algorithm i envisaged - that of hypercube routing - is identical to that of peer-to-peer "search".

flipping one or more bits, to get "nearer" to the destination node, take the packet along the edges of the 128-dimensional hypercube.

cool, huh?


New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

Share this page