3 ms·

>More evidence for the core problem: fiat allocation doesn't work. If there was a functioning, liquid, accessible market for advertisable IP prefixes, you would

by lsc 14y ago

>More evidence for the core problem: fiat allocation doesn't work. If there was a functioning, liquid, accessible market for advertisable IP prefixes, you wouldn't have to convince anyone that a /8 was worth $1bn; it just would be. you are missing a big point. This isn't like real-estate. This is plumbing. Go do a search on "routing table growth" This is actually a much larger problem than IPv4 runout. I mean, it's a problem that is further out, but it is going to hit well within my expected lifetime, and it's going to be a dramatically more difficult problem to solve. The thing is, every time you break up a larger block into a smaller block, every router on the internet needs an entry in their routing tables[1] Usually, in content-addressable memory; Expensive stuff. The thing is, the size of the global routing table? it's growing faster than moore's law.[2] I mean, it's not a huge deal now; for the price of a new compact car, you can get a router that has enough content-addressable memory to handle full tables and two 10g uplinks with 48 1g downlinks. reasonable cost of entry, if you ask me, and if you use dram (good luck with line rate 10G. don't think about faster line-rate.) well, then the cost is trivial. The routing table is under 500,000 entries in IPv4, so it's a trivial amount of dram. The problem is that if this continues? (and all indications are that it's going to /massively accelerate/ if IPv6 catches on. At a minimum, you're gonna see the same number of ipv6 routes as ipv4 routes... and because IPv6 addresses are larger, ipv6 routes are larger) those routers are going to get more and more expensive. So yeah, really? we need a way of charging, not for each IP, but for each announced route. Of course, that comes down hard on the little guys, whereas a per-IP charge is much more progressive. (a /8 takes up as many routing table entries as a /24.) Getting by with a reduced number of IPs would be way easier for me than getting by without announcing my own block. Without BGP announcing my own block, my ISP has my balls in a vice. If they go down? I go down. More importantly, I need to change IPs when I switch to a new ISP. I know what this is like, because I started out on my ISPs IP addresses, like almost everyone does. My provider found out that it's hard for me to switch off those IPs, so now I'm paying them, in total, for all the services they provide me, about twice market rate. (It's actually really interesting, watching the dynamics of this problem play out on PPML or the like. Small players, like me, want to keep it easy to announce smaller blocks. We are fucked if you can only announce large blocks. Large players want tight restrictions on what size of a block you can announce, because they have the address space and they would rather not pay for more super-expensive CAM every time a Luke Crawford gets it in his head to start an ISP.) [1] This is not strictly true. "every router that matters" would be closer to the truth. If you don't have full tables from multiple upstreams, well, you will be effected by rather more partial outages than if you do. [2]http://bgp.potaroo.net/ http://bgp.potaroo.net/ [3]http://bgp.potaroo.net/index-bgp.html http://bgp.potaroo.net/index-bgp.html

jnw2 14y ago
A Xeon E3-1220 has an 8MB L3 cache and costs about $210. If you deaggregate the entire IPv4 routing table to /24s to support fast lookups and store one nibble of destination data per route (probably just a destination interface number, if you can live with only 15 or 16 possible destinations, but you probably don't have that many upstreams), doesn't that mean that the entire routing table can fit in the L3 cache on the CPU (with a bit of the L3 not used by class E space, which will leave a bit of space for code, assuming you aren't doing anything but routing on this CPU)? Now, it's quite possible that the Linux kernel's routing isn't dimensioned to provide this sort of performance, but if you want to avoid CAM in the IPv4 world, I don't see why you'd really need CAM... (Also, I haven't looked carefully at how the L3 cache actually works on the E3s to make sure that it's shared between code and data, etc etc etc. Also, if you're actually implementing this, you presumably do want to include class E in the table, and then hope/assume that when class E doesn't get used, the CPU will be smart enough to cache the code instead.)
- lsc 14y ago
  >A Xeon E3-1220 has an 8MB L3 cache and costs about $210. If you deaggregate the entire IPv4 routing table to /24s to support fast lookups and store one nibble of destination data per route (probably just a destination interface number, if you can live with only 15 or 16 possible destinations, but you probably don't have that many upstreams), doesn't that mean that the entire routing table can fit in the L3 cache on the CPU (with a bit of the L3 not used by class E space, which will leave a bit of space for code, assuming you aren't doing anything but routing on this CPU)? Hm. interesting. so, uh, for simplicity, we have 256^3 routes, right? each one is, uh, what,33 bits of data? I mean, you need 3 bytes for the network and then what, uh, 5 bits for the mask? then okay 4 bits for the dest so 33 bits per route, no? so (33*256^3)/8 is 69206016 bits, or what,66 megabytes? sweet jesus, you are right. I mean, you are off by an order of magnitude, but at this scale, who gives a shit about an order of magnitude. Interesting. 'cause none of the commercial routers do this. which is fucking weird. With this optimization (only store the first 3 octets, as you aren't routing anything smaller, have a lookup table for dest. addresses.) you could take full tables in puny amounts of CAM that come on, say, l3 switches. I will ask around as to why this isn't done. (of course, with IPv6, this does not come close to solving the problem. /32 is the 'standard' handout for ISPs, and usually the smallest prefix you accept is a /48. There are a lot of fucking /32s.) Also, you'd have some complications, as /32s are commonly used to blackhole DDoS targets, but you only have a handful of those, so that would add complexity but it wouldn't kill the idea. I bet I'm missing something- I mean, every two bit ISP would be really happy to give you ten grand for a 10G full-tables bgp router, and you can get l3 switches with enough cam for that and a few 10G ports for little more than half that.

by lsc 14y ago

jnw2 14y ago

A Xeon E3-1220 has an 8MB L3 cache and costs about $210. If you deaggregate the entire IPv4 routing table to /24s to support fast lookups and store one nibble of destination data per route (probably just a destination interface number, if you can live with only 15 or 16 possible destinations, but you probably don't have that many upstreams), doesn't that mean that the entire routing table can fit in the L3 cache on the CPU (with a bit of the L3 not used by class E space, which will leave a bit of space for code, assuming you aren't doing anything but routing on this CPU)? Now, it's quite possible that the Linux kernel's routing isn't dimensioned to provide this sort of performance, but if you want to avoid CAM in the IPv4 world, I don't see why you'd really need CAM... (Also, I haven't looked carefully at how the L3 cache actually works on the E3s to make sure that it's shared between code and data, etc etc etc. Also, if you're actually implementing this, you presumably do want to include class E in the table, and then hope/assume that when class E doesn't get used, the CPU will be smart enough to cache the code instead.)

lsc 14y ago
>A Xeon E3-1220 has an 8MB L3 cache and costs about $210. If you deaggregate the entire IPv4 routing table to /24s to support fast lookups and store one nibble of destination data per route (probably just a destination interface number, if you can live with only 15 or 16 possible destinations, but you probably don't have that many upstreams), doesn't that mean that the entire routing table can fit in the L3 cache on the CPU (with a bit of the L3 not used by class E space, which will leave a bit of space for code, assuming you aren't doing anything but routing on this CPU)? Hm. interesting. so, uh, for simplicity, we have 256^3 routes, right? each one is, uh, what,33 bits of data? I mean, you need 3 bytes for the network and then what, uh, 5 bits for the mask? then okay 4 bits for the dest so 33 bits per route, no? so (33*256^3)/8 is 69206016 bits, or what,66 megabytes? sweet jesus, you are right. I mean, you are off by an order of magnitude, but at this scale, who gives a shit about an order of magnitude. Interesting. 'cause none of the commercial routers do this. which is fucking weird. With this optimization (only store the first 3 octets, as you aren't routing anything smaller, have a lookup table for dest. addresses.) you could take full tables in puny amounts of CAM that come on, say, l3 switches. I will ask around as to why this isn't done. (of course, with IPv6, this does not come close to solving the problem. /32 is the 'standard' handout for ISPs, and usually the smallest prefix you accept is a /48. There are a lot of fucking /32s.) Also, you'd have some complications, as /32s are commonly used to blackhole DDoS targets, but you only have a handful of those, so that would add complexity but it wouldn't kill the idea. I bet I'm missing something- I mean, every two bit ISP would be really happy to give you ten grand for a 10G full-tables bgp router, and you can get l3 switches with enough cam for that and a few 10G ports for little more than half that.