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