Over the last few weeks, nearly 20 million Americans tried accessing a broken US 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 a deadlock, which occurs 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 (ECE, SE). “It has been attracting the efforts of many researchers for decades.”
Professors Levitin and (ECE) have been working with their students on this problem for several years, developing new 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 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 , 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.
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.”
Wu describes Levitin as open-minded, even when his student was questioning his own theories.
“Professor Levitin is the best professor I’ve ever known,” he said “Even when we had no idea how to begin a project, he’d point us in the right direction.”