Spanning Tree, Network Modelling

Question

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?

Answer 1

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!

Answer 2

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.