TCUP - Trivial Call Up Protocol Version 1

High Level

The Topology

The topology of a TCUP network is simply a set of nodes all connected by one or more TCP connection. Any protocol with the same guarantees of TCP can be used, though, as TCUP does not take into account anything about the underlying protocols beyond the services it uses. The implementation, however assumes you are always running over TCP/IP.

TCUP communicates by sending messages which do not exceed a predetermined MTU size of 262143 bytes which includes the header. There are 6 types of messages which all have at least a destination address. The messages also have a message ID which is used in loop pruning, a hop count which guarantees that if loop pruning fails for some reason a message will eventually die, and a size field. Each message type, or PDU (Protocol Data Unit) is covered in its own section.

About Messages

TCUP messages propogate by being forwarded from node to node accross the established links, ussually by broadcast. This is the motivation for the loop pruning code and the TTL. There is no guarantee of delivery in TCUP so introducing some routing code which may fail to deliver some messages but will reduce the broadcast nature of the network while incresing performance is a very real consdieration for those implementing nodes.

TCUP does provide a mechanism for two nodes intending to exchange many messages to establish a point-to-point path accross other TCUP nodes. This call up of another node is the most complex algorithm in TCUP simply because of its scope and the number of variables it uses. A call up, though, is really represented only as a 6-tuple consisting of 2 connection ids and 4 channel ids.

Some quick vocabulary terms for dealing with Calls in TCUP.

  1. Call - A path for messages to flow through comprised of channels. When a call is made channels between directly connected nodes are build to carry the data for the call.
  2. Channel - The subsection of the path a call takes between two nodes over a single connection. A channel only ever services a single call.
  3. Terminating Node - The node where a call stops.
  4. Intermediate Node - A node that participates by relaying traffic for a particular call.

The Various Messages

There are only 6 messages in version 1 all of which share a simple header. I thought about making the following ascii art an HTML table, but tradition insists that I make it an ascii PDU diagram. I trust my readers will understand the nastalgia. 

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|    version    |     type      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |               message length                  |
+---------------+-----------------------------------------------+
|                      to or channel id                         |
+---------------------------------------------------------------+
The hops field is ussually initialized to be the diameter of the network. On small networks would be 3 or on heavily connected medium networks it might be 4 or 7. For huge, sparse networks a larger value is needed so that the message can propogate across the entire network. While TCUP is targeted for networks under 100 or 200 in size with sparse connectivity it does try to manage with larger networks.

Type 1 - Broadcast/Id-cast Message

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x01      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |               message length                  |
+---------------+-----------------------------------------------+
|                             to id                             |
+---------------------------------------------------------------+
|                            from id                            |
+---------------------------------------------------------------+
|                           user data                           |
+---------------------------------------------------------------+

Forwarding

While hops is greater than 0, this message may be forwarded and should be forwarded out all availabe connections except the one on which the message was recieved. The hops count should be decremented before this message is forwarded.

Also a unique hash of this message must be made and stored so that we do not rebroadcast this message. Hashing of a message is effectivly accomplished by taking the first 20 bytes of this message and copying them setting the hops field to 0. This hashing method works for all 6 types of messages though Unicast and Hangup messages may be shorter than 20 bytes in length. An implementation of this should be aware of that and either pad the hash with some known value or simply make a hash of a shorter length.

Note that if this is a broadcast id (0xffffffffff or -1), the node should recieve this message and still consider whether to forward it or not.

If this message is destine for this Node it should not consdier this message for forwarding.

Note: Any application that uses TCUP must be able to handle duplicate messages. TCUP should not prevent the delivery of duplicate messages to the application layer. This may be used in the future for constructing intelligent routing.

Type 2 - Unicast Message

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x02      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |               message length                  |
+---------------+-----------------------------------------------+
|                            channel id                         |
+---------------------------------------------------------------+
|                           user data                           |
+---------------------------------------------------------------+

How a node handles a unicast message is substantially different from how it handles a Broadcast or ID-cast message. Unicast messages are messages traveling along a Call from one node to a single destination node along an established path. Therefore any Unicast message recieved must be corrolated to a known Call or dropped.

To identify which channel a Unicast message has arived on (and then which channel to send the user data out on) the TCUP implementation must consider the connection and the channel id. A channel ID recieved on connection 3 is different from a Unicast message recieved with the same channel ID on connection 5.

Once the channel is found the call it is a part of can be found and the corrosponding outbound channel found. If there is no outbound channel, the call is considered to terminate at this node.

Forwarding

Once the outbound channel is found the only change that must happen is the channel id must be set to the new channel id. The message is then sent on only the connection associated with the channel. The hops need not be decremented.

Implementation Note

A simple way to implement this is to assign all connections an ID. Then create call records (not channel records) which contain all the information you need to lookup the connections and send with the correct id.

We will get into this more as we talk about building up calls, but simpl put the call record would need to have 6 ids in it: Two incoming ids and incoming connection ids to relate incomging traffic the correct call record, Two outgoing ids so as to send on either connecition with the correct channel id the remote node assigned on its end to this channel, and Two connection ids.

One final note is that when a new call object is made it must be able to be looked up by both "sides" of it if the call does not terminate at this note. Remember that calls and the channels that comprise them are bi-directional.

Type 3 - Call Up Message

This message sets up half of the call from one node to another. The records created at each node by this message have a short expiration time unless a Call Establish message completes the Call by providing the other half of the information. 

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x03      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |               message length                  |
+---------------+-----------------------------------------------+
|                          to node id                           |
+---------------------------------------------------------------+
|                         from node id                          |
+---------------------------------------------------------------+
|                   timeout in milliseconds                     |
+---------------------------------------------------------------+
|                        from channel id                        |
+---------------------------------------------------------------+

A Call is a connection from node A to node Q via none or some other nodes. A Call consists of individual hops from node to node along what are called channels. The Call Up PDU facilitates the construction of channels between all the nodes along the path from node A to Q.

The Call Up PDU is broadcasted like any other message having a source and destination node id. These values do not change. Then follows the timeout field which contains the number of milliseconds which this connection is good for when it goes idle. Following that is the from channel id. The from channel id specifies on what channel a node must send data for that data to be recieved by A. Every node that forwards this PDU MUST generate its own from channel id and replace the value in the recieved Call Up PDU.

When forwarding, the hop count is decremented and the message is forwarded on all interfaces except the one it was recieved on. It is a good idea record the recieved message and the transitted message in whatever data structure is used to prevent loops.

The node should then record the half-up connection with a timestamp (so it can be deleted eventually). The rest of this process is completed when this node recieves a Call Establish message as discussed later on.

If this node recieves a Call Up message which is destine for it, it should construct and send a Call Establish message, again, as discussed below.

Timeouts

Regarding the timeout field in the message. It represents how long this connection may remain idle on this node before Hang Up messages are sent and the call is torn down. A note on implementations, some nodes implementations may wait until a timed out call is accessed before they realize the call has timed out and only then will the Call Hangup message be sent.

Type 4 - Hang Up Message

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x04      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |                    0x00000c                   |
+---------------+-----------------------------------------------+
|                           channel id                          |
+---------------------------------------------------------------+

This is sent along a channel. A node which recieves this should relay it along the call by sending it on the corrosponding channel and then destroy the call.

Type 5 - Call Establish Message

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x05      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |                     0x00000c                  |
+---------------+-----------------------------------------------+
|                            channel id                         |
+---------------------------------------------------------------+

When a node recieves this message it should look up the half-up call record it has stored, fill in the missing information (the other connection id, the incoming channel id) and generates the outgoing channel id for the other connection.

Note that if this node's half-up call record indicates that this node is the termination point of this call then we don't need to do anything more than make this call available to the user.

Type 6 - Call Error Message

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x06      |            msg id             |
+---------------+---------------+-------------------------------+
|      hops     |                   0x00000c                    |
+---------------+-----------------------------------------------+
|                            channel id                         |
+---------------------------------------------------------------+
|                          error number                         |
+---------------------------------------------------------------+

This is like a hangup message but is sent when a call is destroyed for some error such as the connection going down. A node should propogate this along the call and then destroy the call.

Here is a list of defined errors.

Type 7 - Link State

 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
+---------------+---------------+-------------------------------+
|      0x01     |     0x07      |            msg id             |
+---------------+---------------+-------------------------------+
|      0x02     |                   length                      |
+---------------+-----------------------------------------------+
|                           distance                            |
+---------------------------------------------------------------+
|                            from id                            |
+---------------------------------------------------------------+
|                             type                              |
+---------------------------------------------------------------+
|                         Encoded Address                       |
+---------------------------------------------------------------+

While TCUP seeks to be network agnostic it is highly desirable to add in a wrinkle by which TCUP nodes can learn about other TCUP nodes on the network indirectly connected to themselves.

The Link State message is only a positive declaration that a node has a link to a given host. Unlike other link state network algorithms there is no negative statement such as a node being an infinite distance to another node.

The distance value is the number of hops a node is to anothe node along the path that a particular PDU travels. To put that more simply, when the hop count decreases the distance count should increase.

Link State messages may be forwarded, though it is highly recommended that they do not go beyond 2 hops or so or networks quickly become unusable.

Excessive generation of Link State messages can also decrease performance. It is probably best to only announce links when a link goes up and every few hours so that new nodes more than 1 hop away can update their caches.

Nodes recieving these message should manage their local caches of known TCUP nodes taking care to filter themselves out of the list of nodes. Nodes that use more than 1 interface should filter for all the interfaces they know of or at least filter on the IP of the interface on which they recieved the update. Because it is permissable for this message to have a hop count greater than 1 it is not possible for a sending node to avoid sending the IP address of a reciving node to it as an update.

Below is a list of address types and their encodings.

  1. Type 0x0001 - A string of the format <hostname>:<port>.
  2. Type 0x0004 - 4 bytes of IPv4 address information and 2 bytes for the TCP port number.
  3. Type 0x0006 - 16 bytes of IPv6 address information and 2 bytes for the TCP port number.