Networks, randomness, and hybrid vigor

The Internet takes your data and breaks it into packets; it gives each of those packets a delivery address and a return label, much like a postal packet, and sends it on its way. But once a message is broken up into packets, the packets stay sealed until they find their way to their destination, where they’re reassembled. It’s as if Ikea put your bookshelves on six different trucks instead of one; each piece arrives separately, and you put them together when they arrive. (It works because, among other things, your computer is better at following directions than you are.) This packet-switching system is the basis of the Internet as we know it, and it works brilliantly up to a point. As the sheer amount of data on networks grows, slowdowns are inevitable, and bigger pipes, in the form of faster transmission lines and routers, can only just keep up.

About ten years ago, computer scientists realized that the packets didn’t need to stay packets; they could be taken apart and recombined. Packets could be “hybridized” according to a given code hybridizing packets bound for or originating from similar destinations, or sharing a LAN or wifi node, for instance. Routers would be given the codes so that they could sort the hybrid packets out and deliver them intact. This approach is called “network coding,” and it offers greater efficiency in network transmissions but only if sufficiently elegant codes could be devised for sorting packets into happy hybrids. But writing rules for determining which packets play well together has proven exceedingly challenging.

And then professor Muriel Medard and colleagues at MIT’s Research Laboratory of Electronics discovered a surprising solution: packets can be combined randomly. Treating the information in the packet as a single number, Medard’s protocol multiplies that number and that of other packets by a random number, adds the results together, and sends them out as a single hybridized message. Routers down the line know the random number and the algorithm used to generate the hybrid, information they use to restore the hybrids to their original state.

Although specialists in network coding were skeptical at first, the approach Medard and her colleagues invented has proven effective in a number of projects. And with wired and wireless networks proliferating and combining in new ways, randomized network coding could offer a way to manage messages traveling over multiple systems simultaneously. It’s an ingenious solution, but maybe it should come as no surprise: mules, perhaps the most successful animals hybrids, have been managing packet delivery for thousands of years.

[via MIT]