# Algorithm for defragmenting cross-pipe issues in a network for routing signals through?

I have a network I'm responsible for routing signals through. You can think of the network as a directed graph of nodes (hardware) but each edge is really a pipe capable of fitting a specific bandwidth, I can route signals to any index on that pipe and may have multiple signals of different 'size' going across the pipe. For what it's worth the signals are predetermined sizes and will not always be simple multiple of twos.

I know how to defragment a single 'pipe' easily enough. However, it's theoretically possible that I could have to move signals around across multiple pipes to create enough room to fit a new signal. In a trivial example I could have two edges from A to B with enough space to fit a signal of size '4' available, and a signal of size '8'. To fit the signal across I would have to move some signals from pipe 2 to 1 so that 1 is completely freed, living a full '8' slots available for my new signal to routed in.

How to detect and properly defragment these sort of cross-pipe issues?

Of course in the real world I may have to route signals through completely different devices, perhaps having signals take less-direct routes, to free up enough space for my new signal on any given pipe.

So in short across an entire system of these networks I want to

1. find a method to get a signal from input to destination in a crowded environment where I may have to move multiple signals to take a different path to their destination in order to free up sufficient space on a given pipe

2. figure out how to do the above with the minimum number of signals physically moved

3. have an approach that minimizes the need of running the above steps by minimizing fragmentation as much as possible.

This is a complicated series of requirements on their own, and I'm not looking for an answer on how to do it all, though such an answer is welcome.

• Have you looked into max-flow algorithms? (en.wikipedia.org/wiki/Maximum_flow_problem) – Steven Evers Jan 17 '14 at 18:54
• This close, but not quite right. There are two main issues as far as I can tell. First, I'm working with a uni-directional graph. Second, Each signal has it's own destination, each flow has a specific sink. I'll look into it more though in hopes it will lead to a related concept. – dsollen Jan 17 '14 at 20:44
• As far as I know (and TBH, I'm not an expert here, it's a recent area of interest of mine) 1. most of the algorithms work with directed graphs 2. separate sinks on the same graph sounds problematic with the textbook/canonical algorithms – Steven Evers Jan 17 '14 at 21:38

I don't think you have a graph problem, I think you have a bin packing problem.

To my understanding, graph theory is worried about length of the route (shortest, longest, # of edges, etc...) whereas the bin packing issue is concerned with most efficient utilization of some container.

In your case, the network pipes are your containers and the bandwidth of the signals is what you're packing into your pipes.

The Wikipedia article on bin packing briefly describes a few algorithms or approaches to consider. It is an NP-hard problem, but optimal solutions can be found if you're able to "cheat" the rules. I suspect that a "good enough" solution can be readily found for your case, and there are some suggested implementations linked within the article.

In the simpler case, you'll have a cascaded series of bins to optimize for. Each layer in the series would represent one step across your network mesh. This approach assumes that you can either switch nodal paths on-the-fly or that the signal bandwidth remains fixed for the configuration interval. In essence, this is a divide-and-conquer approach using a bin packing algorithm to optimize bandwidth usage.

If you need to deal with the more complex case where you have to consider the capacity of the full, multi-step path, you'll need to modify your approach to the bin packing algorithm. You might run into this case if you can't configure on-the-fly. The challenge in this case is that any given signal could have multiple paths through the mesh, but you need to account for the capacity consumed by the signal based upon the path it actually takes.

I would cheat the more complex case by starting with the lesser of the number of signals or the number of potential paths. The first-fit algorithm may be a reasonable place to start in this case. You will likely need to roll through a number of iterations, and you'll need to implement some sort of memory within the algorithm to avoid starting scenarios that didn't end up resolving.

Another consideration in order to help the algorithm converge is to not worry about the "ideal" or "most efficient" utilization of the capacity. The reality is that "good enough" means all of the signals get through within a reasonable number of hops. Quibbling over the efficiency once you get past good enough is unlikely to provide as beneficial returns on your effort.

Finally, if there is a degree of variance within your signal capacities, then I would either add in a reserve capacity per pipe or overestimate the signal bandwidth in order to provide headroom for the excursions outside of the norm.

• I'm sorry, but I guess I'm missing something. I don't see how my situation can be approximated into a bin packing problem. I need to consider a path from A to B to C and eventually D to get from source to sink. I don't know how to make a 'bin' out of a path like that? – dsollen Jan 23 '14 at 21:49
• @dsollen: This merely establishes a lower bound on the complexity of your problem. Each link is treated as a bin, and each channel must use at least one link. In reality, you might need more links and not all links are applicable. But consider a very simple graph with two nodes and 3 links between them. In this case, you have a direct 3 bin packing problem. – MSalters Jan 24 '14 at 8:12

Per Steve Ever's comments I looked into flow graphs. I ultimately stumbled upon the concept of multi commodity flows (http://en.wikipedia.org/wiki/Multi-commodity_flow_problem) which basically states that the problem is known to be an NP-complete problem; there is no fancy algorithm to solve the problem as I had defined it apparntly.

However, I refuse to accept the sort of slow down a purely NP-complete approch would take. Instead I decided to redefine the problem slightly. By using a rather bastardized version of the buddy approch (http://en.wikipedia.org/wiki/Buddy_memory_allocation) I'm able to get my time allocation down to log(n) for most of my pipes. I still need an NP complete approch for the final step, but the final step can be limited to a situation with only a few dozen 'flows'/pipes to map, making even an NP approch doable. However, this approch is depending on specifics of my own system, it doesn't solve the problem as stated above, mearly simplifes the factors to such a small fraction as to make NP complete doable.

Sorry for anyone reading this problem that was hoping for a good solution to the stated problem. The best I can suggest is Linear Programming.