The banding problem, or Pretend You're a Router

[Roedy Green]

I expect there will be great interest in efficiently solving the
banding problem as we move to IPv6.

It is akin to the problem of adding case ranges to Java.
See http://mindprod.com/projects/caserange.html

A router in IPv6 has packets coming in each labelled with an 128-bit
destination. The router is directly connected to N other nodes. You
have a giant table of IP bands/ranges, and which node each range goes
to.

You might also have some pseudo nodes which mean "alternate between
node a and b".

You have to very rapidly take the ultimate destination address and
find which band/range it belongs in.

There might not be enough molecules in the universe to build a direct
RAM table lookup. You need something clever to home in on it.

How would you do it?

Can you do better than binary search?

Perhaps some sort of nested partitioning by the high order bits with
direct RAM lookup.

If I let you design some parallel hardware, can you think of how it
might work? If you don't know anything about hardware design, imagine
how you might solve this with a Java machine with 1024 cpus and a
multithreaded design where synchronisation overhead was negligible.

If you think of something terribly clever, you might NOT want to post
it, but have a talk with a lawyer, then go see Cisco.

 

[Rene]

How would you do it?

Can you do better than binary search?

Perhaps some sort of nested partitioning by the high order bits with
direct RAM lookup.

Have a look at http://www.acm.org/sigcomm/sigcomm97/papers/p182.ps

This works well if you don't have many changes in the structure (ie if it
gets read far more often than changed as it builds a fast structure that
needs to be (partially) rebuilt when changes occur)

I actually hope the link above is correct, I cannot verify it at the moment
myself and the PDF which I can verify is not in english. The solution is
for IPv4 but should work for v6 as well, although v6 has optimizations
built in like regional routing, that could be exploited as well.

If you think of something terribly clever, you might NOT want to post
it, but have a talk with a lawyer, then go see Cisco.

This is not by me, just to set things straight

CU

René

 

[Roedy Green]

Have a look at http://www.acm.org/sigcomm/sigcomm97/papers/p182.ps

Unfortunately that is in PostScript designed to be printed. You would
have to install something like GhostScript to view it. Perhaps
someone could convert it to PDF.

 

[ak]

Have a look at http://www.acm.org/sigcomm/sigcomm97/papers/p182.ps

Unfortunately that is in PostScript designed to be printed. You would
have to install something like GhostScript to view it. Perhaps
someone could convert it to PDF.

Roedy,

this document contains 12 pages.
should I send it to you?

 

[Roedy Green]

this document contains 12 pages.
should I send it to you?

I have the document. It is just my PS printer is dead.

 

[ak]

this document contains 12 pages.

I have the document. It is just my PS printer is dead.

I mean of course PDF.

 

[Roedy Green]

I mean of course PDF.

That would be great. Thanks.

 

[Gordon Beaton]

A router in IPv6 has packets coming in each labelled with an 128-bit
destination. The router is directly connected to N other nodes. You
have a giant table of IP bands/ranges, and which node each range goes
to.

You might also have some pseudo nodes which mean "alternate between
node a and b".

You have to very rapidly take the ultimate destination address and
find which band/range it belongs in.

There might not be enough molecules in the universe to build a direct
RAM table lookup. You need something clever to home in on it.

How would you do it?

Can you do better than binary search?

Routing is done using prefix matching.

Look up "patricia tree" or "radix tree".

/gordon

 

[Roedy Green]

Routing is done using prefix matching.

Internet routers have to search their database for the longest prefix
matching a destination IP address. Thus standard techniques for exact
matching, such as perfect hashing, binary search, and standard Content
Addressable Memories (CAMs) cannot directly be used for Internet
address lookups.

According to the Computer Engineering and Networks Laboratory
ETH Zurich paper, they don't think of it in terms of bands mapping to
a destination, but varying length prefixes matching. Bands are more
general.

 

[Roedy Green]

If I let you design some parallel hardware, can you think of how it
might work? If you don't know anything about hardware design, imagine
how you might solve this with a Java machine with 1024 cpus and a
multithreaded design where synchronisation overhead was negligible.

What you might do for example is have 128 different hashtables, one
for each length of ip prefix. You do the lookup in parallel on all of
them, and take the longest one.

 

[Roedy Green]

A router in IPv6 has packets coming in each labelled with an 128-bit
destination. The router is directly connected to N other nodes. You
have a giant table of IP bands/ranges, and which node each range goes
to.

It might turn out in the long run, ironically that 128 bit IP
switching is actually faster than 32 bit. Why? It would be easier to
keep a 128-bit address space more closely matched to physical
geography. You might actually need fewer entries in a router mapping
table to describe the routing. As IPv4 gets more and more full, the
routing tables explode in complexity dealing with the little
exceptions.

I was happy to read in that ETH paper that there does exist a
reasonably scaleable algorithm for IPv6 lookup.

It quite amazing that the Internet has managed to deal with the growth
with so little problem. Imagine what would happen if the electric or
phone system had to grow that fast.

I further suppose that if worse came to worse, you could use
approximate routing using abbreviated tables on packets with a long
TTL, and accurate routing on ones about to die soon if they don't get
to their destinations.

 

[Roedy Green]

A router in IPv6 has packets coming in each labelled with an 128-bit
destination.

If IP addresses were assigned strictly geographically, it would
simplify the routing tables. You might by default get a geographic ip
created by interleaving the latitude and longitude bits of your GPS
location. This IP could automatically belong to you simply because
you occupy that space grid. Geographic IPs could be carved out of a
small fraction of the entire 128-bit address space.

The problem then is you still can have dozens of wireless companies
serving the same physical location. You need some intermediate bits
in there to encode the carrier.