Featured Research

from universities, journals, and other organizations

New approach to vertex connectivity could maximize networks' bandwidth

Date:
December 23, 2013
Source:
Massachusetts Institute of Technology
Summary:
Computer scientists are constantly searching for ways to squeeze ever more bandwidth from communications networks. Now a 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.

Technique advances understanding of a basic concept in graph theory, paralleling advances in edge connectivity.

Computer scientists are constantly searching for ways to squeeze ever more bandwidth from communications networks.

Now a 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.

Graph theory plays a central role in mathematics and computer science, and is used to describe the relationship between different objects. Each graph consists of a number of nodes, or vertices, which represent the objects, and connecting lines between them, known as edges, which signify the relationships between them. A communications network, for example, can be represented as a graph with each node in the network being one vertex, and a connection between two nodes depicted as an edge.

One of the fundamental concepts within graph theory is connectivity, which has two variants: edge connectivity and vertex connectivity. These are numbers that determine how many lines or nodes would have to be removed from a given graph to disconnect it. The lower the edge-connectivity or vertex-connectivity number of a graph, therefore, the easier it is to disconnect, or break apart.

In this way both concepts show how robust a network is against failure, and how much flow can pass through it -- whether the flow of information in a communications network, traffic flow in a transportation system, or fluid flow in hydraulics.

Reducing edge connectivity's edge

However, while a great deal of research has been carried out in mathematics to solve problems associated with edge connectivity, there has been relatively little success in answering questions about vertex connectivity.

But at the ACM-SIAM Symposium on Discrete Algorithms in Portland, Ore., 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.

"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."

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 says. "And when a graph has a better vertex connectivity, it allows a larger flow [of information]," he adds.

Applications in assessing robustness

The researchers can also use their new approach to analyze the robustness of a network against random failures. "These new techniques also allow us to analyze whether a network is likely to remain connected when its nodes fail randomly with some given probability," Ghaffari says. "Reliability against random edge failures is well understood, but we knew much less about that against node failures," he adds.

Noga Alon, a professor of mathematics and computer science at Tel Aviv University, says Ghaffari and his fellow authors have identified the notion that determines the largest achievable flow when broadcasting messages using routing in communication networks.

"The investigation of this notion, vertex disjoint connected dominating sets, is treated in this paper by an elegant combination of combinatorial, probabilistic, and algorithmic techniques," he says.


Story Source:

The above story is based on materials provided by Massachusetts Institute of Technology. The original article was written by Helen Knight. Note: Materials may be edited for content and length.


Cite This Page:

Massachusetts Institute of Technology. "New approach to vertex connectivity could maximize networks' bandwidth." ScienceDaily. ScienceDaily, 23 December 2013. <www.sciencedaily.com/releases/2013/12/131223181959.htm>.
Massachusetts Institute of Technology. (2013, December 23). New approach to vertex connectivity could maximize networks' bandwidth. ScienceDaily. Retrieved April 20, 2014 from www.sciencedaily.com/releases/2013/12/131223181959.htm
Massachusetts Institute of Technology. "New approach to vertex connectivity could maximize networks' bandwidth." ScienceDaily. www.sciencedaily.com/releases/2013/12/131223181959.htm (accessed April 20, 2014).

Share This



More Computers & Math News

Sunday, April 20, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Nintendo Changed Gaming World, but Its Future Uncertain: Upstone

Nintendo Changed Gaming World, but Its Future Uncertain: Upstone

AFP (Apr. 19, 2014) The Nintendo Game Boy celebrates its 25th anniversary Monday and game expert Stephen Upstone says the console can be credited with creating a trend towards handheld gaming devices. Duration: 01:21 Video provided by AFP
Powered by NewsLook.com
Nearly Two Weeks On, The Internet Copes With Heartbleed

Nearly Two Weeks On, The Internet Copes With Heartbleed

Newsy (Apr. 19, 2014) The Internet is taking important steps in patching the vulnerabilities Heartbleed highlighted, but those preventive measures carry their own costs. Video provided by Newsy
Powered by NewsLook.com
Facebook To Share Nearby Friends Data With Advertisers

Facebook To Share Nearby Friends Data With Advertisers

Newsy (Apr. 19, 2014) A Facebook spokesperson has confirmed the company will use GPS data from the new Nearby Friends feature for advertising sometime in the future. Video provided by Newsy
Powered by NewsLook.com
Man Claims He Found Loch Ness Monster With... Apple Maps?

Man Claims He Found Loch Ness Monster With... Apple Maps?

Newsy (Apr. 18, 2014) Andy Dixon showed the Daily Mail a screenshot of what he believes to be the mythical beast swimming just below the lake's surface. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins