# Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server sends too all clients). I'm looking at adding some intelligence to the way it sends voice packets around, to find the best route depending on link latency, a user's free bandwidth etc.

Hopefully this will behave so that in a particular network, each node is aware of the overall network and can decide on how best to send voice packets to minimize the net total delay for all nodes to receive the packet. So for a user with a very limited, slow internet connection, the best route may be to send the packet to a user with a high capacity, fast connection and have him forward the packets on. For average users, perhaps the best route is a mix of sending directly to nodes and having some forwarded on. Forwarding on packets adds a 'hop', and increases delay so the optimum solution will look to minimise this, but not violate bandwidth limits.

I am trying to model this as a spanning tree, where all vertices are connected to each other with a weight associated to each edge that represents network latency (and other factors). The weight needs to be different depending on direction. In addition to this, there is a bandwidth limit (or flow limit) on each vertex which limits the number of edges you can use from a single vertex. Broadcast will be one node sending packets to every other node, which essentially creates a minimum spanning tree.

My first thoughts are to model it on a simple spanning tree diagram, and use a well established algorithm to find a near optimum solution. However, I'm a bit confused as my network has different weights for different directions, flow limits through a node and weights added by the fact you are repeating through another node. I'm not really sure where to start with this. Are there algorithms designed to find solutions to a problem like this, if not how would I go about finding a solution?

EDIT: I think the main problem I have at the moment is working out how to classify the problem. It's like a minimum spanning tree, but there is a maximum number of edges to each vertex. It's like a flow network, but it has weights on the edges and the flow capacity is through a vertex not along an edge. Is there a classification for this kind of problem?

• From what I understand, it seems like the problem is to find the cheapest paths from a given vertex to every other vertex. Is that right? If so Dijsktra's algorithm does this (assuming your edge costs are nonnegative. If some are, you can try Bellman-Ford). – Casteels May 15 '14 at 12:21
• Hire a mathematics consultant. – Gerry Myerson May 15 '14 at 12:32
• @Casteels Thats correct, from one vertex to every other vertex. But there are flow limits, which represent maximum available bandwidth. So there cannot be more than x edges connected to a vertex. – Oliver May 15 '14 at 12:40
• @GerryMyerson That would make life easier, but it's not an option. This isn't in a professional environment where there is budget for consultancy, it's a hobby exercise. Otherwise I would get a consultant in. – Oliver May 15 '14 at 12:42

After spending some more time on this, I tried to work out how I intuitively find the best route and turn it into an algorithm. I eventually came up with a greedy algorithm, that by no means finds perfect results, but runs very quickly and serves as a starting point.

I wrote it myself, however it probably belongs to someone else (or adaptation of someone else's) so I'm not asserting any kind of ownership. I probably read it, forgot I read it, then re-invented it.

Its written as pseudo-code.

Start the avenues list, set to the starting vertex.

Start the remaining vertices list (all except starting vertex)

Start list of all edges, set to the entire edge list

Loop while remaining vertices list is NOT empty
{
Set current vertex to top of avenues list

Loop while vertex has unused edges and edge limit has not been reached
{
Find cheapest edge, add to the edge spanning tree

Remove cheapest edge from edges list

Add the vertex connected to the cheapest edge to the avenues list
}

Vertex has no more available edges, remove from avenues list
}

Done, return spanning tree


I welcome comments on it, or improvements. I have an implementation in python that runs pretty quickly. A fully connected network of 100 nodes takes around 77ms (2.6Ghz, i5, 8GB RAM) on a fairly standard machine. That's running with debug printing and python interpreter delays etc. I need to add some more code to analyse how good the resulting spanning tree is, and see if it varies much.

I think you have two different problems, First, you need to solve a Flow Network problem.

Then you should somehow create a minimum spanning tree from the solution you previously obtained.

I think you are not the first to stumble with this problem, a little serch might help you start familiarizing with this problem.

Good luck with the program!

• Thanks for the pointers, I will start looking in this direction. Cheers. – Oliver May 19 '14 at 10:57