Advogato: Solution to Mobile IPv6 routing

Solution to Mobile IPv6 routing

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

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.
AND:
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 :)