ACE/protocols/ace/RMCast/README

   1
   2
   3 Introduction
   4 ------------
   5
   6 RMCast is a reliable source-ordered multicast protocol implementation
   7 for message-oriented multi-sender group communication built on top of
   8 IPv4 multicast. It uses sequence numbers for re-ordering, duplicate
   9 suppression and loss detection. Negative acknowledgments (NAK) with
  10 retransmissions are used to recover from losses.
  11
  12 One new and interesting idea implemented in this protocol is history
  13 transmission (dubbed negative retransmission). In a nutshell, each
  14 sender, along with normal payload, transmits a list of other sender's
  15 IDs along with sequence numbers of last messages received from those
  16 senders by this member. This, in some sense, builds a pyramid of
  17 information: each subsequent message carries some information for a
  18 number of previous messages (from other senders). This helps other
  19 receivers detect losses.
  20
  21 The protocol does not track group membership. Messages are retained
  22 for retransmission for a predefined amount of time. The "last message
  23 or lost message" dilemma is solved by periodic history transmissions
  24 in cases when there is no useful traffic (idle network).
  25
  26
  27 Examples
  28 --------
  29
  30 There is a simple example available in examples/RMCast/Send_Msg with
  31 the corresponding README file.
  32
  33
  34 Protocol
  35 --------
  36
  37 Over-the-wire representation is little-endian CDR. The protocol is
  38 message-based with information encapsulated into one or multiple
  39 profiles (Protocol.h):
  40
  41
  42
  43 struct Profile
  44 {
  45   u16 id;    // Profile id.
  46   u16 size;  // Profile size.
  47 };
  48
  49 struct Message
  50 {
  51   u32 size;                   // Total size of the message.
  52   sequence<Profile> profiles; // Sequence of profiles.
  53 }
  54
  55
  56
  57 The following profiles are defined (Protocol.h):
  58
  59
  60
  61 struct From: Profile
  62 {
  63   u32 addr;  // IPv4 address.
  64   u16 port;
  65 };
  66
  67 The 'From' profile appears in each message. It is never transmitted
  68 over the wire. Instead the 'Link' layer (see below) adds it.
  69
  70
  71
  72 struct To: Profile
  73 {
  74   u32 addr;  // IPv4 address.
  75   u16 port;
  76 };
  77
  78 The 'To' profile also appears in each message. It is also never
  79 transmitted over the wire since all communications are done via
  80 well-known group address. It is added by the 'Link' layer and is used
  81 by a group member to identify messages from itself ('From' == 'To').
  82
  83
  84
  85 struct Data: Profile
  86 {
  87   sequence<octet> data;
  88 };
  89
  90 The 'Data' profile is used to transmit user payload.
  91
  92
  93
  94 struct SN: Profile
  95 {
  96   u64 sn;
  97 };
  98
  99 The 'SN' profile carries sequence number for 'Data' and 'NoData' profiles.
 100
 101
 102
 103 struct NAK: Profile
 104 {
 105   u32 addr;  // IPv4 address.
 106   u16 port;
 107
 108   sequence<u64> sns;
 109 };
 110
 111 The 'NAK' profile carries sequence numbers of all the messages originated
 112 from the member identified by addr:port that the receiver detected were
 113 lost.
 114
 115
 116
 117 struct NRTM: Profile
 118 {
 119   struct Pair
 120   {
 121     u32 addr;  // IPv4 address.
 122     u16 port;
 123
 124     u64 max_sn;
 125   };
 126
 127   sequence<Pair> nrtm;
 128 };
 129
 130 The 'NRTM' profile carries highest sequence numbers known to this member
 131 for (some sub-) set of members. It is used by other members to detect loses.
 132 This profile is normally combined with 'Data' transmission.
 133
 134
 135
 136 struct NoData: Profile
 137 {
 138 };
 139
 140 The 'NoData' profile is send in reply to 'NAK' when the lost message is
 141 no longer available.
 142
 143
 144
 145 Below is the list of actions that trigger messages with various
 146 profiles:
 147
 148
 149 user calls send():  SN
 150                     Data
 151                     NRTM
 152
 153 detected loss:      NAK
 154
 155
 156 received NAK:       SN     or   SN
 157                     Data        NoData
 158                     NRTM        NRTM
 159
 160
 161 Implementation
 162 --------------
 163
 164 This section describes high-level architecture of the implementation.
 165 The protocol is implemented as a stack (Stack.h) of the following
 166 elements:
 167
 168 'Socket'
 169 'Acknowledge'
 170 'Retransmit'
 171 'Link'
 172
 173 The 'Socket' element is the user interface of the member. When a user
 174 calls send() 'Socket' creates a new message with 'SN' and 'Data' profiles
 175 and forwards it to the 'Acknowledge' element. It also receives (from
 176 'Acknowledge') and queues incoming messages that are delivered to the user
 177 when recv() is called.
 178
 179 The 'Acknowledge' element is responsible for re-ordering, duplicate
 180 suppression, loss detection and negative acknowledgments. It maintains a
 181 dynamically changing "window" (which slides toward higher sequence
 182 numbers) of received messages. Messages that arrive out of order are held
 183 in this window. Presence of a hole in the windows for a long period of time
 184 indicates loss and triggers a negative acknowledgment.
 185
 186 The 'Retransmit' element is responsible for message retention, aging and
 187 retransmission in response to NAKs. Each message received from the 'Socket'
 188 element is held for predetermined amount of time in case retransmission is
 189 required. Upon reception of a NAK duplicate is send if the requested message
 190 is still available. Otherwise 'NoData' profile is sent.
 191
 192
 193 The 'Link' element is responsible for interfacing with the IPv4 multicast
 194 socket. It also parses over-the-wire representation into in-memory messages
 195 with individually-accessible profiles.
 196
 197 --
 198 Boris Kolpackov <boris@kolpackov.net>