Introduction

Message routing is a feature that allows for sending individual messages to different destinations based on the content of the message (also called content-based routing).

This article explores different aspects of the routing. It proposes algorithm to use for generic routing, i.e. message passing in a generic directed acyclic graph-like network.

Scope of the problem

Message routing makes sense in data-distribution messaging style. Routing in context of load-balancing messaging style has unclear semantic and little or no real-world applications.

In a point-to-point messaging style, routing can be useful is some scenarios. With 1:1 communication, routing boils down to the simple message filtering. More research should be done on routing in the context of point-to-point messaging style.

Layering

One of the problems with routing is that it requires inter-layer interactions. Think of a ØMQ (zmq.tcp) wire-level protocol where each message consist of length and message payload. Message payload is filled in by the application on the top of ØMQ - the application uses it's own wire-level protocol to format the message. Following picture shows how appication protocol is encapsulated in zmq.tcp protocol:

As can be seen, application have decided to compose the message from a string ("A" in this case) and some other data that are irrelevant for the routing.

Now, we would like ØMQ to send the message to different destinations depending on the string incorporated to the message payload by the sending application. However, ØMQ has no idea of how the application protocol looks like.

The situation is similar to traffic shaping. Traffic shaping is done mostly on layer 2 or 3 of the OSI stack while the criteria to route on (like TCP port) are defined on layers above it.

The solution used by say IOS or Linux "tc" utility is to make shaping algorithms completely generic, so that they can be used whatever the higher level protocol looks like. Thus, what you say is: "Apply this traffic shaping strategy to every packet that contains value 45 in the 32-bit value located on position 12 of the packet."

It would be nice if ØMQ can this level of generality - user can define/implement almost any routing mechanism needed. However, most common routing scenarios should be provided out of the box so that users don't have to mess with the routing details.

The current design doesn't include a mechanism to ensure that sender and receiver are using the same application protocol. Such mechanism is subject to further research.

Algorithm

Subscriptions are issued by terminal message consumers. However, routing should be moved as far upstream as possible to eliminate excessive network traffic and CPU consumption. To achieve it subscriptions are passed upstream. Following algorithm applies:

In mux (object aggregating several feeds) subscription should be passed to each attached upstream element.
In demux (object distributing messages to several destinations) subscription should be both kept locally (associated with the particular downstream element) and forwarded upstream. demux object does the actual message matching and passes message only to the downstream elements that have subscribed for it.
Network protocol engines pass subscriptions upstream if technically possible.
For performance reasons it's necessary to avoid redundant routing. Following rule applies: If all the subscriptions are passed upstream and there's exactly one element downstream (and there never was more then one element downstream), routing can be skipped.

Examples

Simple in-process messaging (1-to-1)

Messages are passed from one thread to another, subscriptions are passed in the opposite direction.

1-to-many in-process messaging

Subscriptions are passed upstream. Demux component stores the subscriptions on per-downstream-element basis. When message is to be sent, message matching is performed and the message is passed to the matching downstream elements.

Many-to-1 in-process messaging

Subscriptions are passed to each upstream element. This way client can be agnostic about number of upstream elements. Also, it's important to send all subscriptions to a newly attached upstream element. Thus, mux has to store all the subscriptions.

Over-the-network messaging

The basic principle is to pass the subscription upstream via the network connection. Note that this is not possible in some cases. Say PGM reliable multicast is uni-directional, there's no way to pass subscriptions upstream.

Following diagram shows the simplest possible scenario for over-the-network communication. Note that subscription is passed all the way upstream, thus unneeded messages are filtered out immediately in sender's API thread.

Additionally, demux object on the receiver side can skip routing as all the subscriptions are passed upstream and there's only one element downstream:

Following scenario shows the situation where the routing on receiver side cannot be skipped. There are two user threads receiving messages, each of them has different subscription ("A" vs. "B"). Both subscriptions are passed upstream over the network, meaning that both "A" and "B" messages are delivered to the receiver application. Receiver application still has to route the messages to one of the two client threads:

Here's the other situation where routing in receiver cannot be skipped. The network protocol in this case is PGM multicast. It's uni-directional thus the subscriptions cannot be passed upstream. Consequently, all the messages are multicast over the network. Receiver application has to receive all of them and filter out those matching the subscriptions.

Complex messaging topologies

Simple scenarios described above can be combined into complex networks of messaging elements. It's essential for the network to be acyclic so that the messages and subscriptions are not passed on in infinite cycles. Strategy to prevent infinite loops is a subject for further research.