kNet Message Model

kNet Message Model

This page defines the kNet Message Model, which is a set of features that promotes the transport-level messages from bytes of raw data to a more complete model for communication, by associating with each message additional information that specifies how the messages are be treated in the channel and with respect to other messages.

In the kNet message model, a message is a structure containing the following fields:

kNet Message

MessageID	Specifies the type of the message.
IsReliable	A flag that denotes whether this message can be sent in an unreliable datagram.
Priority	Specifies the order in which this message should be sent with respect to other messages.
ContentID	Used to model when a message renders another message of the same type obsolete.
ChannelIDs	Denotes the virtual transmission channels inside which this message should be sent.
Data	The actual byte payload.

To understand this section, it is important to have fresh in mind the following common networking issues occurring at the IP segment level:

1. Segments are lost.
2. Segments are received out of order.
3. (For thoroughness, segments can be duplicated, but kNet transport layer detects this and removes all duplication, so this does not apply here.)

The approach taken by the TCP protocol is to hide these issues from the user, whereas the UDP protocol leaves it up to the application to handle these in whatever way it pleases.

Under perfect network conditions IP segments arrive in a timely manner and in their proper order without packet loss. In these cases, it matters very little whether kNet is used over TCP or UDP and they effectively perform the same (transport channel -wise).

It is during times of network congestion and packet loss when the differences are visible. It is not possible to develop a fit-all solution on the transport layer that would hide these problems from the application completely, while providing optimal bandwidth and latency. A robust network application should have proper mechanisms built into its application level protocol to give it resiliency against periods of network choke and loss.

Some network protocols take the approach of letting the application build virtual transmission channels inside a single established connection. Reliability and ordering are treated as parameters of the channels. kNet Message Model differs from this by defining these parameters at the level of individual message instances.

This page describes the different relationships that can be defined for application-level messages. The techniques presented here can be used to minimize unnecessary application-induced message latency. Applications that do not have a requirement for real-time messaging can benefit from these techniques as well by using the message replacement feature, which cuts down bandwidth consumption and eases network recovery in the presence of packet loss.

The page kNet Message Model describes these details in terms of the reference implementation.

Legend

The basic parameter of each message is whether its delivery needs to be guaranteed or not. The transfer of each reliable message is tracked and the message is resent in the channel periodically until its delivery is acknowledged by the receiver. If the delivery does not need to be guaranteed, the message can be sent unreliably, which saves slightly on bandwidth.

This is the only property that affects how message are treated individually. All other message parameters control how a message is handled with respect to other messages.

Messages without dependencies.

In the most ideal protocol, all messages are independent and can be applied on the receiving side without taking into account the order they are received. For example in the above case, the following results are possible (among others):

• A is received first, then B and then C.
• C is received first, then B and then A.
• B is received first, then A. Message C is lost.

The advantage of not having ordering requirements is that the messages can be applied immediately when they are received. Messages should be sent without ordering restrictions whenever possible.

Message Ordering Restrictions

The message on the top needs to be applied before the message on the bottom can be applied.

It is not always possible to develop a protocol where each message is logically independent from each other. In this case, the application can model a dependency chain between the messages. The transport layer guarantees that these ordering dependencies are satisfied. The above diagram shows the different cases that can be built using different reliability options. From left to right:

1. The reliable message A needs to be applied before the reliable message B can be applied. If the application receives B before A, the message B will be held in a queue until A is received. This is the main source of application-induced latency that occurs.
2. An unreliable message depends on a reliable message. In this case, if D is received before C, the message D is queued until C is received. It is possible that D is never received (it will not be resent).
3. A valid, but perhaps slightly nonrecommended case is to have two (or more) unreliable messages depend on each other. However, in this case if the message F is received but the message E is lost, then F can never be applied! (and is discarded after a timeout period)
4. This last case is not recommended at all. If your protocol has messages that follow this pattern, it is probably a logical bug. In this case, the delivery of message H will be guaranteed, but if the message G was never received, H is useless. To refactor this case, either demote H unreliable, or make G reliable as well.

Message Replacement

Some application-level messages can be seen "equivalent", in the sense that they either carry the same information, or the information in one message is a subset of the information carried in the other. It can be that the messages are of the same type and one is just a newer version of itself. In this case, we can conclude that the newer message renders the older message obsolete, and so the old message can be discarded immediately, even if the old message was marked as reliable. This optimization is implemented at two levels:

• In the outbound message queue of the sender, message replacement is constantly tracked and if a new message is admitted that replaces a message existing in the queue, the existing one is removed immediately. This feature is the major reason why kNet over UDP can utilize bandwidth effectively even in the presence of network congestion. Data will not "pile up" in the outbound queue as it would do with TCP, thus avoiding fat bursted transfers after the network recovers from a period of data loss. This optimization is commonly called late data choice in research papers.
• At the receiving end, when each message is decoded, it is checked whether the new message was already obsoleted by a previously received message. If so, the new message can be ignored. This effectively removes problems caused by possible out-of-order received messages while avoiding application-induced latency.

This optimization can only be applied when kNet is operating over UDP. Each message instance can be associated with a ContentID value. Messages of the same type (equal PacketIDs) that also have the same ContentID are understood to contain different versions of the same data. The send queue uses these IDs to recognize when old data is being replaced with a newer version of the same data, and will discard the old data.

For the same reasons as with message prioritization, using this method over a TCP connection has very little effect.

The message at the bottom logically replaces the message at the top.

The different possible combinations of message replacement and reliability are shown in the above diagram. From left to right:

1. A reliable message A is replaced by the message B. If A is received before B, both will get applied. If B is received before A, B is immediately applied, and later when A is received, it is ignored.
2. An unreliable message C is rendered obsolete by the reliable message D. This case is very similar to the previous one.
3. An unreliable message F replaces the unreliable message E. If F is received before E, E is ignored on arrival. Note that it can happen that neither E or F is received.
4. A reliable message G is obsoleted by an unreliable message H. This situation is best avoided and is most likely a logical bug. The final applied state of the receiver depends on whether the message H is received or not. Having the message G be reliable is dubious.

Message Priorities

Each message is associated with a priority value (u32). It can often happen that the amount of messages to send momentarily exceeds the capacity of the channel. In this case, message priorities are used to choose which messages are most urgent to be sent through the channel. A large priority value specifies that the message is urgent and requires low-latency transmission. A small value means that the message can be transferred on the background, while giving priority to other more immediate messages.

If the amount of data to send is within the bandwidth capabilities of the connection, message priorities do not have much effect, since all messages can be sent effectively in real-time anyway. Prioritization applies in the case that the application generates a large burst of messages in a short time frame, continuously generates more data than the bandwidth can sustain, or if the connection experiences congestion, packet loss or large delays.

Message prioritization is most effective when applied to a connection that works over UDP, since in the case of TCP, the driver manages its own send queue that cannot be manipulated after data is submitted to it. Setting a small TCP send buffer minimizes this problem at the risk of starving the outbound socket, whereas with a buffer too large, prioritization is effectively impossible to perform.

Messages with different priorities.

The above diagram shows three independent messages with different priorities. If these messages would be admitted into the outbound queue within a very short time period (or if the queue is already saturated), the messages will be eventually sent out in the order B, C, A. Note that this does not guarantee in any way the order in which the receiver will receive the messages.

If two messages have the same priority, they will be sent in the First Come, First Serve (or FIFO) order.

Reversed message order and priority.

In the above diagram, a high priority message depends on a low priority message being delivered first. In this case, the logical correctness takes precedence. The message A will be transferred first (with priority 100), which effectively demotes the priority of message B to 100 as well. In this case, it is naturally guaranteed that on the receiving side A is applied before B, even though B had higher priority.

Many-to-One Ordering Restrictions

It is somewhat common of the messages to form a graph of dependencies in many-to-one or one-to-many manners. The two diagrams below depict these cases.

Messages B, C and D depend on message A being applied first.

Message A depends on messages B, C and D being applied first.

kNet supports many-to-one and one-to-many message dependencies. However, every time when you face a situation like this, you may want to consider one of the following:

1. Model the dependency as is and preserve the plurality in the dependency chain.
2. Add a full barrier between the many-to-one messages. This is the best solution when the message depends on so many messages that it is not possible to keep track of individual messages.
3. Linearize the dependencies. For example, make it so that the order A->B->C->D is enforced, after which each message only depends on one message.
4. Merge the message types B, C and D together into a single message type.

Many-to-One Replacement

Message A replaces messages B, C and D.

Applying one of messages B, C or D replaces message A. Applying all messages F, G and H replace message E.

The above diagrams show cases where message replacement is applied in many-to-one or one-to-many cases. These are not supported. If your protocol contains messages that logically function in the above manner, it is recommended that the messages are refactored into simpler patterns.