Signal Routing Algorithm

PhreaK

I'm in the process of putting together a module to handle signal routing in systems with complex signal distribution networks (stacked switchers, format conversion etc). At this point I'm thinking Dijkstra's algorithm may be a good solution and will allow paths to be mapped if I define the graph with a discrete vertex for each switch level on the matrix switchers and join them via nodes representing the video processors.

I'm just curious if others have implemented something similar in the past and if so what approach did you take?

P.S. once this gets to a functional state it'll be open sourced (along with the rest of the system) and should be pretty portable.


edit:
Done

jjames

You have to admit - you definitely take this AMX programming stint to a whole new level. I'd just make it work and be done with it . . . you make it fancy. :-)

DHawthorne

I've been going with a pseudo-OO approach by creating structures that contain the routing information needed for each zone, and making sure the modules have an interface that uses a common protocol. Very much the way you would make an object in a real OO language, and define methods for it, etc. That way I can send a standard command to select source 2 in room 1, and the structure data determines what device is controlling that room, and what control pages come up for that source.

jimmyw

I use a similar approach, I wrote a module that supports passing an array of arrays in to represent up to 224 objects and each object can support up to 64 inputs and outputs with flags for each device if the device can not be shared (private viewing of dvds, directv, etc), the maximum amount of layers I support though is only 4, I just got tossed in to a job where I had 7 layers and I butchered that poor module to make it happen fast. I dont like dijkstras method because it is shortest path routing, but alot of the time I want to route through a processor on purpose, even though the path would seems a bit backwards.

PhreaK

@jjames what can I say, I don't like repeating work. If I can implement this is should be pretty portable as far as handling signal routing in most scenarios. That being said I do have a habit of doing this.

@DHawthorne standard interfaces are the way. The concept is to connect it to Duet module's that implement the SwitchComponent or SourceSelectComponent so that this is purely handling abstracted routing across the system and device communication remains separated.

@jimmyw yes, Dijkstras is shortest path, but you can assign lengths to the edges to influence the routing.

There's some more information and a bit of a discussion on the question I posted on StackExchange

ericmedley

I used the "if the sales guy sells another stacked switcher system, I break a thumb" algorithm.

a_riot42

PhreaK wrote: »

I'm in the process of putting together a module to handle signal routing in systems with complex signal distribution networks (stacked switchers, format conversion etc). At this point I'm thinking Dijkstra's algorithm may be a good solution and will allow paths to be mapped if I define the graph with a discrete vertex for each switch level on the matrix switchers and join them via nodes representing the video processors.

I'm just curious if others have implemented something similar in the past and if so what approach did you take?

P.S. once this gets to a functional state it'll be open sourced (along with the rest of the system) and should be pretty portable.

I'm not sure what the problem you are trying to solve is. Is the shortest path the goal or some other metric, like least format conversions, etc? Typically networks use the (minimum) spanning tree algorithm to find a loop free path in a graph.
Paul

PhreaK

Shortest path but biased away from format conversion using edge weighting. If it can get a signal end to end in a native format do it, otherwise just get it there.

From my comment on the P.SE question:

The theory being this will allow it to be defined such that the higher the definition of the signal path, the lower the weighting. Edges which connect nodes that perform format conversion would then be given a weighting higher than that assigned to edges which connect non-conversion nodes. This would route the signal in it's native format if possible, only involving format conversion (and associated signal degradation and equipment utilisation) when necessary.

a_riot42

PhreaK wrote: »

Shortest path but biased away from format conversion using edge weighting. If it can get a signal end to end in a native format do it, otherwise just get it there.

From my comment on the P.SE question:

How are the switches wired together?
Paul

PhreaK

a_riot42 wrote: »

How are the switches wired together?
Paul

With either electrically or optically conductive material

The module should be flexible enough to work across different layouts. Basically instantiate, then pass in a identifiers for what's plugged in where (from channel names if you wish). This will then allow the edge data to be extrapolated and the graph formed.

a_riot42

PhreaK wrote: »

With either electrically or optically conductive material

The module should be flexible enough to work across different layouts. Basically instantiate, then pass in a identifiers for what's plugged in where (from channel names if you wish). This will then allow the edge data to be extrapolated and the graph formed.

Then that's tricky. You could easily end up with a situation where only a very limited number of paths are possible at the same time, and I assume concurrency is required. If they are daisy chained, a certain input/output selection could mean that few other independent, simultaneous paths are possible. If stacking 8 8x8 switches, and needing to route input 1 on switch 1 to output 1 on switch 8 would mean you couldn't route many other independent signals. Your graph would need to be redrawn for every i/o switch as the number of vertices available will shrink every time a switch is made, making many other routes impossible.

Wired that way you could have 54 inputs and 54 outputs available, but that severely limits how many simultaneous paths you can have. If you know you only have 8 inputs and 54 outputs, then you can wire things so that all sources go into one switch and then each output goes to its own switch. This limits the number of sources but then you can have all 8 inputs running independently on any or all of the 54 outputs, with the same switch hardware.

Since an input can be routed to any output(s), but an output can only receive one input, I guess you could use a modified Dijkstra's algorithm on whatever graph you are left with after pulling out any used outputs, to find the shortest vertex-independent path in the graph. Seems like overkill though.
Paul

PhreaK

Yep, definitely a 'thorough' solution, no argument there. As Dijkstra searches the graph each time it has to locate a path the edge waiting's can be dynamic. This will allow me to increase them when in use so signal flow is prioritized elsewhere. Alternatively I'm also going to play with having a flag in each of the edge objects so that it can be ignored if in use.

ROO

PhreaK wrote: »

Yep, definitely a 'thorough' solution, no argument there. As Dijkstra searches the graph each time it has to locate a path the edge waiting's can be dynamic. This will allow me to increase them when in use so signal flow is prioritized elsewhere. Alternatively I'm also going to play with having a flag in each of the edge objects so that it can be ignored if in use.

For coversion to different signal types by switching in a converter (Translator), just to get to the device input that's available, you'll want to have a flag that ignores the path, so I don't see it as something that's optional for your approach. The ability to distiguish between signal types to get the best native resolution would be great for your algothithm to handle. It might be as easy as maintaining another edge components that give you the best signal type as part of your selection criteria.

I like your idea!
ROO

grissler

Just did this last week

This is actually my first post. Got on here to look for a solution to something else and I saw this post. I actually just created a module to do a similar task. It allows me to use up to four switchers with unlimited inputs/outputs, an unlimited number of receivers and an unlimited number of displays. I execute a simple function call Route(source,zone,'audio'). The 'audio' can be either 'audio','video' or 'both'. It will exceute the switching, turn on or off the Receiver and/or display and select the proper input on the receiver or display. It currently only allows you to cascade two switchers, but it allows for all other configurations of Receiver to Display or even Display to Receiver. All the parameters are set in Structures. There is a structure for each Source, Zone, Receiver, and Display as well as one for each Switcher. To get around the different resolutions or Audio modes, I just create a second source with different parameters. It may not be the best way to do it, but all I have to do is set the structures up with the IO path and it works.

PhreaK

Finally got round to building this. I've managed to create an implementation of Dijkstra's algorithm in NetLinx by using some helper functions to initialize structures and assign unique ID's. This then allows them to be set up to act as linked lists which was the key to getting this to work.

I've moved the functionality into a reusable graph library which I've added to the NetLinx Common Libraries project. It's currently in its own branch but I'm merge it into the master once the API is a bit more stable.

To use it for signal routing simply define a node for each signal source and sink as well as for each input and output on any switchers. From there add an edge for each cable in your system and an edge connecting each input to each output in each switcher. eg:

...

for (i = max_length_array(PRIMARY_MATRIX_INPUTS); i > 0; i--) {
	for (j = max_length_array(PRIMARY_MATRIX_OUTPUTS); j > 0; j--) {
		graph_create_edge(signalNetwork, PRIMARY_MATRIX_INPUTS[i], PRIMARY_MATRIX_OUTPUTS[j])
	}
}

...

graph_create_edge(signalNetwork, PROSECUTION_LAPTOP, SECONDARY_MATRIX_INPUTS[1])
graph_create_edge(signalNetwork, DEFENCE_LAPTOP, SECONDARY_MATRIX_INPUTS[2])

graph_create_edge(signalNetwork, SECONDARY_MATRIX_OUTPUTS[1], PRIMARY_MATRIX_INPUTS[14])

graph_create_edge(signalNetwork, PRIMARY_MATRIX_OUTPUTS[1], PRIMARY_LCD)
graph_create_edge(signalNetwork, PRIMARY_MATRIX_OUTPUTS[2], GALLERY_LCD1)
graph_create_edge(signalNetwork, PRIMARY_MATRIX_OUTPUTS[3], GALLERY_LCD2)

...

For signal processors (scalers etc) define a node for the input and output and add a weighted edge joining them so that signal flow is biased towards keeping things in native formats.

If you've got multiple trunk lines connecting switchers simply vary the edge weight when they're in use to redirect to unused links. Also, if you are monitoring devices and a device fails simple set the edge weighting to and from it to GRAPH_MAX_DISTANCE. This allows you to have an auto healing signal network in high availability systems with redundant links.

After that is done just run graph_compute_paths() for a source node then use graph_get_shortest_path() with your destinations of interest to get the optimum path. By inspecting the nodes that form the path you can then make any switching changes.

I'm going to try and put together a little helper library that wraps this for use within signal routing. It should then give you some pretty simple features for graph creation like defineSource(), defineSink(), defineSwitcher(inputs, outputs) and a route(source, destination) which will give a list of switches that need to be made in SNAPI format.

Anyway, here it is in its current unoptimized state: https://github.com/KimBurgess/netlinx-common-libraries/blob/graph/graph.axi.

If you can make it better fork it and submit a pull request. Otherwise if you just want to use it go for. I've built it with handling signal distribution in mind by if you think of another use I'd love to hear about it.

PhreaK

Here's an example of the library wrapped for handling source distribution: https://gist.github.com/2225173.

Basically define your switching gear, define your sources and sinks (displays, recorders etc) then just call route(source, sink) and it will send any SNAPI commands to the switchers that need to do things. It's still pretty rough but you get the idea.

PhreaK

And a massive update: https://gist.github.com/2246182.

This will only create nodes and edges where needed which drastically reduces the graph complexity. With this even in a rather sizable network with multiple layers of stacking and rather complex routes you should expect sub 100ms graph traversal for the initial computation. As this is buffered sequential calls to route the same source to any sink take around 1ms. Basically this thing will now generate the control strings for your switching gear faster than they can be executed.

As always, improvements can always be made so if you can make it better please forking* do it.

*full geek pun intended.