The demand for more bandwidth on existing connections has been increasing rapidly the past few years and an explosion of new services depend, more then ever before, on a constant connection and higher amounts of data. Existing connection methods is becoming bottlenecks, and the cost of replacing them is starting to hold back development.
Now a new approach to understanding a basic concept in graph theory, known as “vertex connectivity,” could lead to future communications protocols that pushes as much bandwidth as possible from existing networks solutions.
In mathematics and computer science, graph theory plays a central role and is used to describe the relationship between different objects. Many practical problems can be represented by graphs.and in computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation and more. Each graph consists of a number of nodes, also called or vertices, that represent different objects, and the connecting lines between them. These lines are known as edges and these represent the relationships between the different objects.
One of the fundamental concepts within graph theory is connectivity, that has two variants: edge connectivity and vertex connectivity. Analyzing their values determine how many lines or nodes that have to be removed from a given graph to disconnect it. The lower the edge-connectivity or vertex-connectivity number of a graph, the easier it is to disconnect, or break apart.
Both variants can display how how stable a network is against failure, and how much flow can pass through it. This is useful not only when analyzing network communication but can for example also show the flow in a transportation system, or be used for crowd simulation when planning evacuation schemes in new arenas or other public buildings.
A lot of research has been carried out in mathematics to solve problems associated with edge connectivity, there has however been relatively little success in answering questions about vertex connectivity. However in January, Mohsen Ghaffari, a graduate student in the Computer Science and Artificial Intelligence Laboratory at MIT, will present a new technique for addressing vertex-connectivity problems at the ACM-SIAM Symposium on Discrete Algorithms in Portland, Ore.
“This could ultimately help us understand how to build more robust and faster networks”, says Ghaffari, who developed the new approach alongside Keren Censor-Hillel at the Technion and Fabian Kuhn at the University of Freiburg.
In the 1960s, mathematicians William Tutte and Crispin Nash-Williams separately developed theories about structures called edge-disjoint spanning trees, which now serve as one of the key technical tools in many problems about edge connectivity.
A spanning tree is a subgraph — or a graph-within-a-graph — in which all of the nodes are connected by the smallest number of edges. A set of spanning trees within a graph are called “edge-disjoint” if they do not share any of these connecting lines.
If a network contains three edge-disjoint spanning trees, for example, information can flow in parallel along each of these trees at the same time, meaning three times more bandwidth than would be possible in a graph containing just one tree. The higher the number of edge-disjoint spanning trees, the larger the information flow, Ghaffari says. “The results of Tutte and Nash-Williams show that each graph contains almost as many spanning trees as its edge connectivity,” he says.
Now 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.
So, in a similar way to Tutte and Nash-Williams’ results for edge connectivity, “each graph contains almost as many vertex-disjoint connected dominating sets as its vertex connectivity,” Ghaffari says.
“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 says. “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.”
Source: MIT
The team has developed an algorithm that can carefully separate a network into many connected dominating sets. Using this method they can create a structure of so-called wireless ad hoc networks, in which individual nodes can route data by passing it from one to the next. This ensures 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. And when a graph has a better vertex connectivity, it allows a larger flow of information”, Ghaffari says.
