(The paper: An Information-Theoretic Approach to Routing Scalability, http://conferences.sigcomm.org/hotnets/2014/papers/hotnets-XIII-final16.pdf)
He opens with a question for the audience: how much information is in a router's forwarding table? On an Internet router, Rétvári considers every possible IPv4 destination address in a row, and writes out (to a file) a byte representing the interface ID on which the router will forward datagrams destined to that address.
The result is 4.0 GiB in total. Rétvári then compresses the file using a command-line compression program (gzip or bzip2).
"I'll take bets from the audience," Rétvári says. "What do you think the result will be? How large?"
Brad Karp ventures a guess: "One megabyte?" (Nobody else is quite ready to jump in.) Karp: "That's my final offer."
A second guess is offered: "256 kilobytes."
It turns out the answer is only 116 kilobytes, a 37,000-fold reduction from the original file.
Rétvári: "I had trouble coming up with files intentionally that compress so well." Of course a large reason for the compressibility is the structure in the table. "When we stay within the same routing prefix we keep writing down the same next-hop label again and again. But even if we ignore all the structure in the address space, we still get very good compressibility. And this is what we don't understand," he says.
Hence the slide title: "The mysterious compressibility of IP forwarding tables."
This compressibility deserves further structure, Rétvári argues: "Forwarding tables are the single most important data structures that we need to understand to reason about the scabaility of hop-by-hop routing," and in particular, "What if we have to store in the data plane keeps increasing? Does hop-by-hop routing scale?"
The paper presents a detailed theoretical model and measurement evaluation that cautiously concludes that, yes, hop-by-hop routing does scale. "The model seems to produce way more precise results than we expected," Rétvári says.
"For some reason, forwarding tables in the Internet tend to compress really really well," he continues. "At the moment, we do not know the causes, but what turns out is 99% of the ASs, the routing-table entropy is below 1 bit. You need to pay only 1 bit for each and every prefix introduced, which is not too much. "We believe that there is something about compressibility of the forwarding tables."
He ends the talk with an urging for future study: "For some reason, large-scale forwarding produces tables that are small, and we need to understand why this is the case."
Next steps: Visit the authors' daily statistics at http://lendulet.tmit.bme.hu/fib_comp
A: This is an interesting idea.
Q (Bruce Maggs): Have you compared the compressed table with the actual amount of storage the router would use for its representation? Maybe there's some other data structure that uses less space but is still easily accessible.
A: We have a paper at SIGCOMM 2013 where we actually realized these bounds. Compressed prefix tries. (Ed.: Layer9 coverage of Rétvári's prior work is available here: http://www.layer9.org/2013/08/sigcomm2013-compressing-ip-forwarding.html)
Q (Anja Feldmann): You are treating the routing table as a string. But entries are not strings; they are integers. What if you use this fact?
A: We do not write down the IP addresses; just the next-hop label.
No comments:
Post a Comment