Larry Hardesty | MIT News Magazine
MacArthur Fellow Dina Katabi, SM ’98, PhD ’03, exploits physical properties of radio waves to make computation more efficient.
Dina Katabi. Photo credit: MIT News Magazine
In 1989, Dina Katabi, SM ’98, PhD ’03, like all Syrian high school seniors, took a standardized test that would determine which courses of study she was eligible for at university. She finished sixth in the nation.
That meant she was bound for medical training—the most prestigious undergraduate placement, available only to the students with the highest scores on the exam. Moreover, she says, “I come from a family that is all medical doctors. My father is a doctor, most of my aunts and uncles are doctors, my grandfather is a doctor—there are so many medical doctors on both sides. So it was the path for me.”
But after a year of study, during which she was at the top of her class, Katabi had an epiphany. “I just decided, ‘I cannot live without math,’” she says. So she transferred into the less-prestigious electrical engineering curriculum at the University of Damascus. “That was a big fight with my parents,” she says.
Twenty-five years later, it looks like a pretty good decision: Katabi, now the Andrew (1956) and Erna Viterbi Professor of Electrical Engineering and Computer Science and a member of the Computer Science and Artificial Intelligence Lab (CSAIL), is in the third year of a MacArthur “genius” grant and just back from presenting some of her new work to President Obama at the White House. Networking protocols based on her work have found their way into commercial products, and her innovative reinterpretation of the problem of radio-frequency interference is changing the way engineers design wireless networks. But that doesn’t mean her parents’ opposition was unfounded. Not only was medicine the more highly esteemed profession in Syria, but it also offered many more employment opportunities there and drew larger numbers of women.
“Syrian society at the time was pretty liberal,” Katabi says. But even so, her parents worried that going into a profession with a low percentage of women would make her life harder. “It’s something that even in the U.S. we feel in certain fields,” she says. Katabi estimates that only 10 to 15 percent of her classmates in electrical engineering were women.
After graduating—again, at the top of her class—Katabi came to the United States for graduate school, following in the footsteps of her father, who had come for his medical specialization. After earning a master’s in computer science at MIT, she enrolled in the PhD program, under the supervision of David Clark, a senior research scientist at the Laboratory for Computer Science (which has since merged with the Artificial Intelligence Laboratory to produce CSAIL) and, for most of the 1980s, the Internet’s chief protocol architect.
“It became clear very quickly that she was going to do some outstanding work,” Clark says. “She brought a very distinctive background, because she had training in both electrical engineering and computer science, so she had a broader range of skills than a lot of computer science students, and that let her undertake a different set of problems.”
Katabi’s dissertation was on networking protocols, Clark’s area of expertise, but she took an unusual approach. A central problem in network management is congestion control—throttling back transmissions when they threaten to choke the network. The Internet’s congestion control mechanism was for each computer to monitor its own transmissions and, if it detected evidence of congestion, to unilaterally reduce its transmission rate.
That approach seemed to work in practice, but it didn’t have a very secure theoretical foundation. Katabi imported principles from control theory, which analyzes the behavior of large dynamic systems, into network protocol design. Using these principles, she and her collaborators could not only design better congestion control mechanisms but also provide mathematical assurance that they’d work at large scales.
Cisco, the world’s largest manufacturer of networking equipment, has since incorporated some of Katabi’s work on congestion control into one of its products, and 12 years after she defended her dissertation, it won the Test of Time award from the Association for Computing Machinery’s network and communication group, which honors past research that has proved particularly influential.
“I would say in some sense she shifted the standard for what it takes to publish in this space,” Clark says. “After she demonstrated the utility of control theory in understanding these algorithms, it became much harder to successfully publish a paper without using that kind of analysis.”
In 2003, on the strength of her dissertation, MIT snapped Katabi up as a junior faculty member. One of her first graduate teaching assignments was Data Communication Networks, which she taught with information theorist Muriel Médard, the Cecil H. Green Professor of Electrical Engineering and Computer Science.
At the time, Médard had been investigating network coding, which was then one of the most promising new topics in information theory. With conventional Internet routing, if a packet of data travels from a computer in Boston to a computer in California, it looks exactly the same on arrival as it did on departure. All the bits are in the same place. Each packet also follows a single, determinate route through the network. But if one of the links along that route is dead, the packet simply won’t go through.
With network coding, a given router in the network would instead mix together the contents of packets it receives within some time window, sending the combined packets out over all the links available to it. If packets get held up at a congested router, the router can simply drop them; each recipient can then extract the information intended just for it by identifying the overlap in hybridized packets arriving over other routes.
Médard and colleagues had devised elegant mathematical proofs establishing that network coding should increase networks’ data capacity. But it was Katabi, working with Médard, graduate students in Katabi’s own group, and researchers at the University of Cambridge, who demonstrated the first practical implementation of network coding, testing it out on a network of Wi-Fi routers blanketing two floors of MIT’s Stata Center. They found that their protocols increased the network’s capacity threefold.
In 2011, Katabi and Médard founded a company, Code On Technologies, to commercialize their work on network coding. Code On has since partnered with eight other wireless companies to begin building the infrastructure that will enable Wi-Fi users to take advantage of network coding, and in tests, they’ve shown their system to be as much as five times as fast as a conventional Wi-Fi network.
Thinking about how to realize the elegant abstractions of network coding, however, had drawn Katabi’s attention to one of the fundamental problems of wireless networks: interference. If nearby wireless devices transmit at the same time, their signals interfere with each other, producing what engineers call a “collision.” In a traditional wireless network, a collision would make both signals unintelligible, so engineers have treated interference as something to be avoided. Katabi’s research introduced a philosophical shift in how interference is perceived. Not only have she and her students shown how to reconstruct transmitted information in the presence of collisions, they’ve also been able to harness interference to increase the data rates of wireless networks.
For her dissertation, Katabi had analyzed communication networks at the level of the packets traveling over them. Her work with Médard “was kind of moving beyond the packet to the individual bit,” she says. “And at that point, it was like, why stop at the bit? Why don’t we go below that and go to the signal?”
Thereafter, using the physical properties of wireless signals to abet computations previously performed at the level of the bit became a theme of Katabi’s work. One high-profile example was zigzag decoding, which won the best-paper award at the 2008 Sigcomm, the main conference of the ACM network and communication group. (Katabi’s lab would win the award again three years later, for a system that prevents tampering with wirelessly accessible medical implants such as pacemakers and defibrillators.)
In their paper on zigzag decoding, Katabi and her students described algorithms that analyze successive collisions of the same transmissions and identify, in one of them, a stretch of signal that comes from only one sender. Then they subtract that signal from the other collision, recovering part of the transmission from the second sender, which they subtract from the first collision, recovering part of the transmission from the first signal, and so on, zigzagging back and forth between collisions. Though the decoding process is complex, the researchers were able to show that it used bandwidth more efficiently than other solutions to the collision problem.
In 2012, an algorithm Katabi helped develop for calculating the Fourier transform, which is essential to a host of signal processing tasks, was named one of MIT Technology Review’s 10 breakthrough technologies. That work was, in a way, the inverse of the process that led her from the theoretical abstractions of network coding to the physical properties of electromagnetic waves. One of her students was considering the practical problem of how to disentangle signals sent at different frequencies at the same time. If you know the frequencies in advance, it’s easy to filter out the ones you’re not interested in: that’s how FM radio works. But what if you don’t know the frequencies in advance?
After Katabi and her student had designed a highly efficient algorithm for this problem, they realized that their solution could help in speeding up the computation of the Fourier transform, which breaks a composite signal into its constituent frequencies. Originally devised for the analysis of heat transfer, the Fourier transform is widely used not only in signal processing but in data compression, financial analysis, and the solution of differential equations.
Working with Piotr Indyk, another MIT computer scientist, Katabi developed an algorithm that, for the first time since the 1960s, increases the speed with which the Fourier transform can be calculated. The algorithm works only in a specific range of cases, but in those cases, the speedup can be dramatic—up to tenfold. In addition to making it possible to compress terabytes of data quickly, Katabi says, the algorithm is likely to be useful for advanced MRI technology, graphics, astronomy, spectroscopy, and methods of studying protein structure with nuclear magnetic resonance.
In recent years, Katabi has been exploring medical applications of wireless technologies. Her award-winning system for protecting wireless medical implants involves a second wireless device, called a “shield,” that could, in principle, be worn as a watch or pendant. The shield jams unauthorized attempts to access the implant, but it relays transmissions that use the appropriate cryptographic key. In an emergency, a medical professional could simply remove the shield in order to send new instructions to the implant.
Katabi and her students have also explored a novel use of Wi-Fi-frequency radio waves: imaging. In their initial results, they demonstrated that they could detect motion even through solid objects. But more recently, they’ve shown that sophisticated processing of ultralow-power radio signals can measure human respiration rates, and even heart rates, from dozens of yards away.
The researchers founded a company, called Emerald, to develop medical applications of the technology, such as remote monitoring of vital signs to detect the onset of illness in the elderly. Emerald’s product can also alert caregivers if a patient suffers a fall. In August 2015, Katabi and the rest of the Emerald team were invited to the Oval Office to demonstrate the system to President Obama.
The potential medical applications of her latest work give Katabi the sense of having come full circle to her freshman year of college in Damascus. She hasn’t been back to Syria since the civil war erupted, though. Her parents have U.S. passports and could leave at any time. But they won’t.
“I’ll call them and they’ll say, ‘Oh, don’t worry—now it’s very normal, there are only explosions at night, but mostly the day is fine,’” she says. “What are you talking about? That’s normal? I worry about them all the time. But their friends are still there. Their life is there.”
Although Katabi hasn’t seen her parents in more than four years, there are aspects of their personalities that she finds inescapable. “I think I got the worst of my mom and my dad—the things I just hated in them,” she says. “I have my mom’s impatience, and I’m very fiery, and what I want, I want.”
And from her father? “I got from him that I’m a workaholic,” she says. “I don’t mind that, but people around me might.”
Read this article on Technology Review.