Better Codes for Communications
Muriel Médard teams with industry to make network data speedier and more secure
The way our cell phones grab their data is, frankly, embarrassing, says Muriel Médard.
“My phone gives me information such as which Wi-Fi networks I’m connected to and however many bars I have, whatever bars mean,” says Médard, the Cecil H. Green Professor of Electrical Engineering and Computer Science at MIT. “I cannot imagine other types of consumer technology products where that unveiling of the mess underneath is acceptable. For instance, my car doesn’t tell me that I have to tweak with the engine valves as I’m driving.”
This messiness could get worse with the introduction of fifth-generation (5G) cellular networks—but Médard and her colleagues have developed an alternative method to handle network data called random linear network coding (RLNC) that can help.
“5G wireless systems will marry a highly heterogeneous set of networks, including Wi-Fi and networks that are very similar to the current fourth-generation systems, but also emerging physical technologies such as millimeter waves,” she says. “Integrating all those different types of technologies rather than dealing with one at a time is almost impossible in the absence of a distributed network coding approach, and RLNC gives you that distributed approach.”
“By capturing all the little pieces that come from all over the network, whether they be over Wi-Fi or 4G or Bluetooth, RLNC makes all of those pieces count,” Médard says. “You don’t have to worry about exactly how many pieces you’re getting from what side, to allow networking in a ubiquitous and truly transparent way.”
That’s one example of benefits from her group’s research, which brings information theory to advances in the efficiency, robustness and resilience of networks.
“While much of our work is devoted to developing theory, we also pursue the application that relies on that theory,” she says. “It’s not a simple linear progression from theory to application. It’s more a dialectic: You start on the theory side, you go to practice, you realize that there are problems that you didn’t consider that throw you back to the theory side, and there is an oscillation between the two that enriches both.”
Random improvements Implemented in network hardware, RLNC can optimize how data shuffles around the Internet, where relatively small data packets travel by independent routes.
“Suppose I have a peer-to-peer system like BitTorrent and I need 10 pieces of data to reconstruct the movie I want to watch,” Médard says. “It’s very much like trying to assemble a collection of baseball cards.”
When you start a collection of baseball cards, you have nothing, so the first card you get is bound to be a new card, she says. But as you get closer to completing your collection, it’s harder and harder to find the missing cards you want, and you end up waiting a long time indeed for your final cards. There’s a mathematical description for this phenomenon: the coupon collector problem.
To grandly oversimplify, RLNC overcomes this problem through encoding each network data packet by applying randomly generated linear algebraic functions to its immediate predecessor packet to create a unique equation. With this scheme, if a packet is lost, its data can be reconstituted from a following packet’s equation.
RLNC avoids the coupon collector problem. “Everything that you see is new, because everything that you see is a new equation based on the original cards,” she says. “And the way to ensure that novelty is through random choice of the algebraic functions for those equations.”
This approach boosts performance because it can call data very efficiently and it doesn’t require endless tracking of the data. “With the emergence of the Internet of Things, which really means highly dispersed largely self-managed standalone wireless networks, that problem of keeping track of everything is one of growing importance,” she points out.
Médard is a co-founder of three startup firms that provide RLNC patent licensing, technology tools and consulting services, “to jump that treacherous gap that we call tech transfer,” as she puts it.
One startup, Code On Technologies of Cambridge, licenses the core portfolios of RLNC patents from MIT, Aalborg University in Denmark, the California Institute of Technology, the National University of Ireland in Maynooth, and the University of Illinois Urbana-Champaign. A second firm, Steinwurf in Aalborg, provides RLNC software development kits. And Chocolate Cloud, also located in Aalborg, uses Steinwurf tools to provide distributed storage systems based on RLNC.
RLNC typically has been embedded in the physical layer of network products, for instance in phone transceivers or Wi-Fi network cards, but it also offers significant advantages in other network and storage components, says Médard.
Another major plus of RLNC is its ability to boost the robustness and security of data transmission and storage. Médard’s group is now doing further research on ways that network coding can help to stand guard in situations where data must withstand many attacks, such as multiple attempts to guess a password.
She also studies how network coding can be applied more effectively to update data. “For instance, you may be editing a document online and you may have many different copies of it dispersed across many different locations,” she explains. “How do you make sure that all copies are not erroneously sent, say to somebody else who may have access to the document that you are editing, without a need to reload every document at every time? Can you tell me what’s new without necessarily telling me which version you have had, because you have to keep versions and exact changes that become extremely difficult to manage?”
In addition to her numerous academic partnerships, Médard works with a large set of industrial collaborators, ranging from Alcatel Lucent and British Telecom to Inmarsat and NBC Universal.
“For me, it’s necessary as an engineering professor to have that industry connection,” she says. “Even though much of my work is more theoretical, in the end there has to be something that does something, as I tell my students. I don’t believe in completely theoretical engineering; at some point you have to check if it works. The discipline that comes from having to consider the reality of problems in a clear and often inconvenient way is very important. My sponsors allow me to consider the problems in a relevant, realistic and much more satisfying way.”