RSE to RSE routing

In multi-RSE implementations, RSE uses a routing protocol to allow messages to be sent from any RSE to any other RSE, regardless of if there is a physical link between them. This may involve an intermediate RSE forwarding the message.

A routing table is used to indicate which is the next-hop for any message. This table is indexed by the destination RSE and contains an index indicating which hardware link should be used to send the message.

The table is located in OTP, which allows for it to be provisioned once the chip topology is known. This also allows BL1_2 code to be identical across all RSEs in a system.

The routing table is automatically constructed by the build system. Each platform must specify a .tgf (trivial graph format) file which describes the system topology, which is then used by the provisioning scripts to calculate the next-hop for each RSE to every other RSE. This generates individual provisioning bundles for each RSE containing their routing tables.

RSE System Topology Map

The system topology map is described as a .tgf file. The MULTI_RSE_TOPOLOGY_FILE cmake variable configures which system topology map tgf file will be used by the build system. This variable should be set in RSE subplatform default config for any subplatform which contains multiple RSEs.

Documentation of the TGF format can be found at https://en.wikipedia.org/wiki/Trivial_Graph_Format#Format.

In the system topology map, each node represents an RSE. The Label portion of the node is optional, but it is recommended to use it to describe which RSE the node represents. Each edge represents a physical link between the corresponding RSEs. The edges are directional, with the first index representing the RSE whose link IDs are described by the edge (henceforth referred to as the Local RSE) and the second index representing the RSE which is being communicated with (henceforth referred to as the Remote RSE).

An example graph node line is:

0 Primary RSE

Because knowing that a link exists does not encode which link should be used, the link ID is encoded as the name of the edge. The format of this name must be “Send <n> Receive <m>” where <n> is the index of the link which is used by the Local RSE to send to the Remote RSE, and <m> is the index of the link which is used by the Local RSE to receive from the Remote RSE.

An example graph edge line is:

0 1 Send 1 Receive 2

In this example, the Local RSE has index 0 and the Remote RSE has index 1. If the Local RSE wants to send a message to the Remote RSE, it should send the message via the link with index 1. If the Local RSE wants to listen for messages from the Remote RSE, it should listen on the link with index 2.

The following is an example topology map for a system with 4 RSEs, which are all connected to each other:

RSE 0
RSE 1
RSE 2
RSE 3

1 Send 1 Receive 1
2 Send 2 Receive 2
3 Send 3 Receive 3

0 Send 0 Receive 0
2 Send 2 Receive 2
3 Send 3 Receive 3

0 Send 0 Receive 0
1 Send 1 Receive 1
3 Send 3 Receive 3

0 Send 0 Receive 0
1 Send 1 Receive 1
2 Send 2 Receive 2

The following is a “hub-and-spoke” system topology with 5 RSEs:

Hub
Spoke 0
Spoke 1
Spoke 2
Spoke 3

1 Send 0 Receive 0
2 Send 1 Receive 1
3 Send 2 Receive 2
4 Send 3 Receive 3

0 Send 0 Receive 0
0 Send 0 Receive 0
0 Send 0 Receive 0
0 Send 0 Receive 0

RSE Routing Table

The RSE routing table is provisioned into OTP. It is provisioned as two distinct tables, as “send” table and a “receive” table. Each table entry is a uint32_t, which is used as an index into the link table in order to decide which link to send/receive on. The amount of elements in the routing table is the same as the number of RSEs in the system.

In order to find the link that should be used, the destination RSE should be used as an index in the correct routing table. The value in the routing table should then be used to select the link.

The size of the routing tables is 4 bytes * 2 * the number of RSEs in the system.

The value in the table which corresponds to the current RSE must be 0. It is invalid to send a message to the same RSE that is sending the message. 0 is also a valid link index.

Each RSE in the system is provisioned with different routing tables. The routing tables for each RSE are generated by running a shortest-path algorithm on the graph between the RSE whose table is being generated and every other RSE.

The link table for RSE 2 in the first example above (fully connected) is:

Send    = {0, 1, 0, 3}
Receive = {0, 1, 0, 3}

The link table for RSE 1 in the Second example above (hub-and-spoke) is:

Send    = {0, 0, 0, 0}
Receive = {0, 0, 0, 0}