Over the last few weeks, nearly 20 million Americans tried accessing a broken United States health care site that couldn’t handle the traffic, among other problems. And even if you weren’t one of the many applying for health coverage, you’ve probably experienced network congestion at some point.
Typically, network congestion occurs if a link or node is carrying too much data; as a result, the quality of service drops. The most severe form of communication disruption is deadlocks. A deadlock happens when several messages mutually block each other so that their delivery is not just delayed but stopped permanently.
“This is a long-standing problem, which is practically important and theoretically challenging,” said Distinguished Professor Lev Levitin (ECE, SE). “It has been attracting the efforts of many researchers for decades.”
Professors Levitin and Mark Karpovsky (ECE) have been working with their students on this problem for several years, developing new algorithms, specifically turn prohibition algorithms, to help direct data and essentially prevent information from being stuck in a deadlock as it travels through communication networks. This work covered a lot of ground by establishing lower and upper bounds for an optimal solution, outlining their discovery of a new class of algorithms, and developing a few algorithms that could actually solve the initial optimization problem.
The last advance on this project was achieved this year by Levitin and his team – ECE alum, Ye Wu (MEng ’13), and Visiting Scholar, Mehmet Mustafa. They have been working on developing new algorithms, specifically turn prohibition algorithms, to help direct data and essentially prevent information from being stuck in a deadlock as it travels through communication networks.
“Without changing the topology of existing networks, we managed to improve saturation points so that congestion is less likely to happen and latency is reduced which means lower waiting time for users,” said Wu.
The team recently presented their work at OPNETWORK 2013, a conference that focused on advancing the state of application and network performance management. Impressed by their research, “A Study of Modified Turn Prohibition Algorithms for Deadlock Prevention in Networks,” the judges awarded them Best Technical Paper.
“Computer experiments, executed earlier and in the latest work by Ye Wu and other students under the guidance of Dr. Mustafa, clearly showed the superior performance of our algorithms versus different algorithms suggested by other research groups,” said Levitin. He went on to add that the majority of publications in the field are on ad hoc algorithms as opposed to the “tree-free” algorithms he and his team explored.
The work gave Wu a chance to travel to Washington, D.C., and deliver the presentation at the Ronald Reagan Building and International Trade Center.
“I met some really nice students and professors from different countries who were happy to talk about their research,” said Wu. “The audience, I think, was also smart enough to understand the key points of our project and asked really good questions.”
Now a Boston University graduate, Wu looks back at his professor fondly, describing Levitin as open-minded, even when his student was questioning his own theories.
“Professor Levitin is the best professor I’ve ever known,” said Wu. “Even when we had no idea how to begin a project, he’d point us in the right direction.”
-Rachel Harrington (firstname.lastname@example.org)