CHAPTER 5    

Overlay (OL) Message Formats

5.1  Overview

Data between overlay sockets is exchanged as formatted messages. As shown in Figure 5.1, an overlay socket provides two endpoints for communications. The node adapter exchanges protocol messages with node adapters at other overlay sockets. The socket adapter exchanges overlay (OL) messages with socket adapters at other overlay sockets. The handling of protocol and overlay messages is completely separate.

Figure 5.1. Messages transmitted by the overlay socket.

·       Protocol Messages: These are messages that are exchanged between overlay nodes. Protocol messages are mostly sent to neighbors in the overlay network. Some overlay protocols may define protocol messages that are broadcast to all nodes in the overlay network (e.g., Beacon messages in the HC protocol). The format of protocol messages are specific to a given overlay protocol, and are completely defined by the overlay node component of the overlay node (see Figure 5.1). Currently, there are two types of protocol messages, DT message and HC message.

·       Overlay (OL) Messages: These are messages that are exchanged between socket adapters of overlay sockets that are neighbors in the overlay network, and are forwarded by the forwarding engine. All application data is transmitted as OL messages. Overlay messages can be multicast to all overlay sockets in an overlay network, unicast to one specific overlay socket. In addition to transferring application data OL messages can be used for monitoring and control functions, e.g., to perform functions similar to traceroute or provide error reporting similar to ICMP. The message format of OL messages is the same across all versions of HyperCast 2.0 overlay sockets.

Currently, both protocol and overlay messages are transmitted using an Internet transport protocol, i.e., TCP, UDP unicast, or UDP multicast. In principle, non-Internet protocols can be used to provide transport services for overlay sockets. The adapters (see Figure 5.1) are responsible for encapsulating messages and interfacing to the underlying transport protocol. The transport addresses of the underlying transport protocol are maintained at the overlay node.

This chapter is about OL messages. The message formats of overlay messages are described in the sections, which contain the overlay protocols.

Note: This chapter describes many message formats which are not used in HyperCast 2.0. Specifically, the ADF packet format is not used in HyperCast 2.0.

5.2  Overlay Messages

All overlay (OL) messages have a header and a payload field. The header of an OL message specifies, among others, the message format, the delivery mode, and source and destination addresses. All addresses in the OL message header are logical addresses. Recall that logical addresses are defined by the overlay topology and the overlay protocol. In the DT protocol, logical addresses are a pair of coordinates (x,y), where x and y are numbers. In the HC protocol, logical addresses are a 32-bit binary number. 

Figure 5.2. Types of OL Messages.

The payload of an HyperCast 2.0 OL message can have a different type, each type has its own header format.

·       Application Data (AD) Messages: These messages perform delivery of application-level data. There are three basic types of AD messages:

o      Raw AD messages: Raw AD messages send unformatted application level data, and have a minimal header. If Raw AD messages are used, the application program is responsible for maintaining sequence numbers, performing acknowledgments, and others.

Note: In HyperCast 2.0, only Raw AD messages are used.

The notion of ADF messages is tightly coupled to the message store, which is not part of HyperCast 2.0. The discussion of ADF messages is not relevant to the HyperCast 2.0 software.

o      ADF messages: ADF messages are formatted AD messages.  Each ADF message has a unique identifier, and may contain control information such as acknowledgements. ADF messages may contain application data or control information (such as acknowledgments).

ADF messages are used if the overlay sockets provides services such as retransmission, or others. Each ADF message carries an identifier for a finite state machine, that can interpret the format of that message.

o      ADF stream messages: ADF stream messages are formatted AD messages, which define a sequence of formatted AD messages. The difference to an ADF message is that, instead of a message identifier, the ADF stream message has a stream identifier and a sequence number. ADF messages are used to implement streaming services.

Each ADF stream message carries an identifier for a finite state machine, that can interpret the format of the message and associate the message with other message from the same stream.

·       Control Messages: Control messages are sent through the overlay to provide maintenance, control, and management. They can be used to implement utilities such as ping, traceroute, and can provide reporting functions similar to ICMP. An important role of control message is to help with congestion and rate control services.
Note: HyperCast 2.0 does not specify or implement control message formats.

The delivery mode of an OL message can be specified as multicast, Flood, Unicast, or Anycast. A multicast OL message is transmitted from the source to all overlay sockets in the overlay network, using routing trees that are embedded in the overlay network. A unicast message is a point-to-point message between any two overlay sockets in an overlay network. A flood message is transmitted using a simple flooding algorithm.

The design of the OL message header is intended to be similar to the IPv6 packet format. Specifically, the OL header uses the notion of extension headers, to concatenate multiple headers. Currently the defined OL message headers are shown in Table 5.1. Of these, only the RAW format is used in HyperCast 2.0. Future OL message headers are listed in Table 5.2 .

In HyperCast, any number of extension headers can be concatenated. Especially, using extension headers, multiple ADF messages may be transmitted in the same OL message.

Table 5.1. OL Message header extensions defined in HyperCast 2.0.

Table 5.2. Future OL Message header extensions.

5.3  Format of OL messages

This section describes the OL message format. All OL messages have a header that is at least twelve bytes long and a payload field. Multiple payloads can be concatenated by using extension headers, as indicated in the Next Header field.

Figure 5.3. OL Message Header.

Version (4 bit):                           Version of the protocol. The current version is 0x0

LAS (2 bit):                                Size of the logical address field

Dmd (2 bit)                                  Delivery mode. Currently defined delivery modes are:

                                                            0x0      Multicast

                                                            0x1      Flood

                                                            0x2      Unicast

                                                            0x3      Anycast (not implemented)

Traffic Class (8 bit):                  Specifies Quality of Service (QoS) class (not used)

Flow Label (16 bit)                     Assigned for QoS purposes (not used)

OL Message Length (16 bits)   Length of  entire payload following this header

Next Header (8 bit)                    Specifies the type of the following header. Currently the following headers are allowed:

·       Raw (0x05)
Identifies an AD RAW message. This data is interpreted by the application program.

·       AD Message (0x01, 0x02)
Contains a formatted AD message that uses the Message ADF format. There are two versions, with different lengths for the Message ID field.

·       AD Stream (0x03, 0x04)
Contains a formatted AD message or an ADF message that uses the Stream ADF format. There are two versions, with different lengths for the Stream ID field.

Hop Limit (8 bit):                       Corresponds to Time-to-Live (same as in IP data)

SrcLA ((LAS+1)*4 bytes)         Logical address of the source of the OL Message

DestLA ((LAS+1)*4 bytes)       Logical address of the destination of the OL Message                                                            

5.4  Format of AD Raw Messages

Figure 5.4. Message Header of AD Raw Message.

Payload Length (16 bits)           Length of Payload field in bytes.

Next Header (8 bit)                    Specifies the type of the next header.

5.5  Format of ADF Messages

ADF messages are associated with a Finite State Machine (FSM), which knows how to process and interpret the ADF message. The FSM is identified by a FSM Identifier. For each FSM, there may be different ADF message types. These are identified by the Type field. Note that the Type field is specific to the FSM ID.

Recall: The finite state machines are part of the message store which is not included in HyperCast 2.0.

Figure 5.5. Message Header of ADF Message.

Next Header (8 bit)                    Specifies the type of the next header.

Payload Length (16 bits)           Length of Payload field in bytes.

FSM ID (16 bits)                         Identifies a Finite State machine, which processes this message. The finite state machine is implemented in the message store. Each finite state machine provides a certain service, which is defined in the message store.

·       0x00: No service (best effort delivery)

·       0x01: Local acknowledgements (Local ACK)

·       0x02: Global acknowledgments (Global ACK)

·       0x03: Stateful flooding

·       0x03: Synchronization

·       0x04: Incast (reverse multicast)

Type (8 bits)                               ADF Message type. The interpretation of the message type may be dependent on the FSM ID.
The following types are defined for all FSM’s:

·       Payload Data (Type = 0x80): The message contains payload data

·       Retransmission (Type = 0x81): The message contains a retransmission of payload data

·       Mergeable Payload (Type = 0x82): The payload of this message is “mergeable” . This type is used for transmission of Incast messages.

The FSM specific types are specified in Table

For each service, different types of ADF_Control messages are necessary.

Table 5.3. Interpretation of Type field in ADF message header.

MsgID (8 or 10 bytes):              Message Identifier. This should be a unique number, for example, a random number, or “Physical address + Transport layer Port number + Counter”. Uniqueness is not enforced.

Sender LA:                                 Logical address of the overlay socket which originally generated this message. This fields is used for control data (such as acknowledgments) which hare sent to the sender of an ADF message. The Sender LA is needed to calculate the next hop (parent) in the tree with Sender LA as root. The LAS size is  known from the OL Header.

5.6  Message format of ADF Stream messages (preliminary)

ADF stream messages are similar to ADF messages in that they have a finite state machine and different message types. The main difference is that the message identifier in the ADF message (MsgID) is replaced by a stream identifier (Stream ID) with a sequence number. The ADF stream message is used to associate multiple ADF messages with a “stream”.

Figure 5.6. Message Header of ADF Message.

StreamID (8 or 10 bytes):         A number that identify the stream. For each stream there can be only a single sender.

FSM ID                                       Identifies a Finite State machine. Has the same interpretation as in the ADF message.

·       0x06: Best Effort Ordering

Type                                            (Not worked out yet)
Currently, only one type is defined:
0x80 Payload = Data message

Sequence number:                      A number that indicates the order of the payload within a  stream. The sequence number can be byte oriented or message oriented.