New technique could maximise networks' bandwidth

Researchers have developed a new technique that could coax as much bandwidth as possible from communication networks, allowing for high speed internet.
The new approach to understanding a basic concept in graph theory, known as "vertex connectivity," could ultimately lead to communications protocols - the rules that govern how digital messages are exchanged - that coax as much bandwidth as possible from networks, researchers said.
"This could ultimately help us understand how to build more robust and faster networks," said Mohsen Ghaffari, a graduate student in the Computer Science and Artificial Intelligence Laboratory at Massachusetts Institute of Technology (MIT).
The team has created an analogous theory about vertex connectivity. They did this by breaking down the graph into separated groups of nodes, known as connected dominating sets.

In graph theory, a group of nodes is called a connected dominating set if all of the vertices within it are connected to one another, and any other node within the graph is adjacent to at least one of those inside the group.
In this way, information can be disseminated among the nodes of the set, and then passed to any other node in the network.

"Each graph contains almost as many vertex-disjoint connected dominating sets as its vertex connectivity," said Ghaffari, who developed the new approach alongside Keren Censor-Hillel at the Technion and Fabian Kuhn at the University of Freiburg.

"So if you think of an application like broadcasting information through a network, we can now decompose the network into many groups, each being one connected dominating set," he said.
"Each of these groups is then going to be responsible for broadcasting some set of the messages, and all groups work in parallel to broadcast all the messages fast - almost as fast as possible," said Ghaffari.
The team has now developed an algorithm that can carefully decompose a network into many connected dominating sets.
In this way, it can structure so-called wireless ad hoc networks, in which individual nodes route data by passing it from one to the next to ensure the best possible speed of information flow.

"We want to be able to spread as much information as possible per unit of time, to create faster and faster networks," Ghaffari said.
"And when a graph has a better vertex connectivity, it allows a larger flow (of information)," he added.