Efficient bandwidth algorithm

Question

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:

1. Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 Mbps network card.

2. Node 3 is connected to 5 at 50 Mbps. Node 3 has 100 Mbps card.

3. Node 4 is connected to Node 3 at 40 Mbps. Node 4 has 100 Mbps card.

(Sorry about not having a picture)

Problem: If Node 1 starts sending data to its immediate nodes (2 and 3), we can clearly see it's network card capacity will be drained out after Node 3. Whereas if it were to skip node 3 and start sending to node 4, the data will eventually reach to node 3 via 4 and hence, node 5 will be getting data via node 3. The problem becomes more complicated if all the links were of 50 Mbps and we can clearly see that node 2 and node 4 are the only way to reach all nodes.

Question: Is there an algorithm which gives the optimal path to ALL nodes keeping the network (card) capacity in mind?

I read the shortest path algorithm,max flow algorithms but none of them seem to address my problems. perhaps,im missing something. I'll appreciate if someone can help me out.

Answer 1

According to your description:

1. Each node in the network can relay a certain amount of traffic per time unit.
2. Each link has a certain capacity.

In order to convert your problem to an instance of network flow problem, one can do the following transformation. In the underlying graph of network, $G = (V,E)$, for any vertex $u \in V$ that has an outgoing edge $(u,v) \in E$, add an auxiliary vertex $u'$. Next, add an auxiliary edge $(u,u')$ with capacity equal to the capacity of $u$ for any auxiliary vertex $u'$. Finally, replace all $(u,v) \in E$ with $(u',v)$. Below is an illustration of how the network graph looks like before and after transformation.

The transformed graph can be seen as a flow network with node $1$ as source and nodes $2$ and $5$ as sinks. More generally, nodes with no incoming edges can be treated as source(s) and those with no outgoing edges as sink(s). Introducing an additional vertex to which all other sinks are connected with infinite capacity, you can further reduce your problem to a single-source single-sink flow network.

The goal is to find the optimal path to all nodes. Therefore, aside from the value of maximum flow itself, the algorithm you use for finding such a flow is also important. Edmonds-Karp algorithm uses BFS for finding the maximum flow over the shortest path. However, you want your maximum flow to go through as many nodes as possible. Thus, you need to make sure that your flows use longest paths between source and sink.

Luckily, for Directed Acyclic Graphs (DAGs), the longest path problem can be solved in linear time using dynamic programming. Thus, by modifying Edmonds-Karp algorithm such that it uses longest paths for flow augmentation, you ensure that the maximum number of nodes will be visited by each augmenting path.

In your example, the modified algorithm will output the following flows in order:

1. A flow of value $40$ over path $\langle 1,1',4,4',3,3',5 \rangle$.
2. A flow of value $10$ over path $\langle 1,1',3,3',5 \rangle$.
3. A flow of value $50$ over path $\langle 1,1',2 \rangle$.