d38af9da378592765f9eb49ccd850375b1d12919
[barrelfish] / doc / 006-routing / Routing.tex
1 \documentclass[a4paper,twoside]{report} % for a report (default)
2
3 \usepackage{bftn,color} % You need this
4 \usepackage{verbatim} % for comment
5
6 \title{Routing in Barrelfish}   % title of report
7 \author{Akhilesh Singhania, Alexander Grest}    % author
8 \tnnumber{006}  % give the number of the tech report
9 \tnkey{Routing} % Short title, will appear in footer
10
11 % \date{Month Year} % Not needed - will be taken from version history
12
13 %% \newcommand{\note}[1]{}
14 \newcommand{\note}[1]{[\textcolor{red}{\textit{#1}}]}
15
16 \begin{document}
17 \maketitle
18
19 %
20 % Include version history first
21 %
22 \begin{versionhistory}
23 \vhEntry{1.0}{09.06.2010}{AS}{Initial version}
24 \vhEntry{1.01}{14.06.2010}{AS}{Added discussion of design and unresolved issues}
25 \vhEntry{1.02}{23.07.2010}{AS}{More work on design and API}
26 \vhEntry{2.0}{31.05.2011}{Alexander Grest}{Multi-hop messaging}
27 \end{versionhistory}
28
29 % \intro{Abstract}              % Insert abstract here
30 % \intro{Acknowledgements}      % Uncomment (if needed) for acknowledgements
31 % \tableofcontents              % Uncomment (if needed) for final draft
32 % \listoffigures                % Uncomment (if needed) for final draft
33 % \listoftables                 % Uncomment (if needed) for final draft
34
35 \chapter{Motivation}
36
37 All inter-core communication in Barrelfish is performed using explicit messages, which are carried over ''Interconnect Drivers'' (ICDs), specialized messaging subsystems that carry data between cores. At present, all communication happens over direct point-to-point ICD links. However, there are multiple motivations for extending this. In this chapter, we motivate the introduction of a routing layer in Barrelfish.
38
39
40 \section{Partial connectivity}
41 Most current multicore machines are fully connected via shared memory. This means that any core in the system can communicate with any other core in the system
42 by using shared memory. Most applications are also designed accordingly. However, this assumption is not necessarily true on modern hardware, as the following two examples illustrate:
43
44 \begin{itemize}
45
46 \item On the \emph{Intel Single Chip Cloud Computer} (SCC), the set of memory a core can access is determined by the setup of its Look Up Tables (LUTs). It is possible that these tables are set-up in such a manner that
47 two or more cores do not have access to the same region of memory. In such cases to communication these cores will have to route via another set of cores if such a path exists.
48
49 \item If Barrelfish is operated on a cluster of machines, there is only an Ethernet-based ICD link between the core(s) where the network stack is running. In order to allow every core to communicate with every other core, the available link must be multiplexed. 
50
51 \end{itemize}
52
53 This are two examples of current set-ups which lead to partial connectivity. A routing layer akin to the one in IP routing will allow applications to communicate in
54 such environments, without having to worry about the concrete path a message takes from one core to another. The routing layer will properly route messages in a transparent way.
55
56 \section{Resource usage}
57 ICD links require resources. In particular, a link uses the following resources:
58
59 \begin{itemize}
60 \item \textbf{Memory}: Any ICD link will require some memory to buffer unsent messages and messages that have been received but not yet delivered. Some links will require additional memory for the channel itself. For instance, the shared-memory UMP driver on x86 requires two pages of physical memory per binding. In general, the amount of memory required is governed by the number of messages in flight and
61 the number of messages in buffer.
62
63 \item \textbf{CPU}: Some ICDs, as for example the UMP driver on x86, require explicit polling to check for incoming messages. The more links a core has, the more time it has to spend polling.
64
65 \item \textbf{Cache}: If an ICD  uses polling to check for incoming messages, the polled cache line will be placed in the cache. If the core has many ICD links, a significant part of its cache will be flushed due to polling.
66
67 \end{itemize}
68
69 The more ICD links a core has, the more of its resources will be used for them. This is detrimental to a high-performance system. By limiting the number of links, we will limit the amount of resources required. One way to limit the number of links is to multiplex multiple channels over one ICD link and therefore not construct a fully connected network. 
70
71 % Still valid?
72 %\section{Heterogeneous IDC}
73 %Barrelfish supports various IDC mechanisms.
74 %Different mechanisms provide different semantics and guarantees such as maximum frame
75 %size, notification mechanism, synchrony, etc.
76
77 %An application can utilize multiple IDC mechanisms.
78 %This can happen if a homogeneous machine supports multiple IDC mechanisms or if the
79 %application runs on a heterogeneous machine.
80 %To avoid the need for the application to understand the different semantics of all IDC,
81 %it can conform to the semantics provided by the routing library.
82
83 %The semantics provided by the routing layer are discussed in section \ref{sec:semantics}.
84
85 \section{Group communication}
86
87 Various parallel computing abstractions such as barriers
88 require communication among a group of threads.
89 When any thread enters a barrier, it waits for all other threads to enter
90 the barrier as well before continuing.
91
92 Various distributed communication abstractions such as achieving consensus
93 also require communication among a group of nodes.
94 A group of nodes that want to come to agreement on some value
95 need to communicate with each other.
96
97 \cite{nishtala:optimizing-collective:hotpar09, barrelfish:sosp09}
98 showed that even in a fully connected 
99 machine, using some form of routing can improve the performance of group communication.
100 The sender sends the message to a subset of nodes it wishes to communicate with.
101 The subset will in turn forward it to the remaining set of nodes.
102 The work has also shown that the order in which messages are sent also matters.
103 The optimal route and ordering of messages is machine dependent.
104
105 If applications were written with the abstraction of a group layer,
106 it will allow the library sufficient flexibility in
107 selecting the optimal route based on the machine type.
108
109
110 \chapter{Multi-hop messaging}
111
112 Multi-hop messaging is an important part of the routing layer. It gives applications a possibility to create a logical channel between two cores, that is routed over multiple nodes. This requires that available ICD links are multiplexed.
113
114 A multi-hop channel can only be set up between two dispatchers running on different cores. It always leads through the two monitors running on each dispatcher's core. Between those two monitors the multi-hop channel can lead through an arbitrary number of additional monitors. We call all the monitors that lie on a multi-hop channel \emph{nodes}. All the nodes of a multi-hop channel must be connected by means of other ICD-links (such as LMP or UMP ICD-links).
115
116 Once a multi-hop channel is set up, it can be used to exchange messages between the two dispatchers. The multi-hop channel transports messages by passing them to the underlying interconnect driver on each link between the nodes of the multi-hop channel. 
117
118 The multi-hop interconnect driver consists of
119 \begin{itemize}
120 \item A mechanism to set up new multi-hop channels between dispatchers addressed by end-point identifiers
121 \item A mechanism to send messages along a multi-hop channel
122 \item A mechanism to receive messages from the channel
123 \end{itemize}
124
125
126 \section{Design goals}
127
128 \subsection{Independence of the underlying interconnect driver}
129
130 The multi-hop interconnect driver was designed to be independent of the type of the underlying ICD links between the nodes on the multi-hop channel. This means that it uses the common flounder interface supported by all ICDs when interacting with the underlying ICD link and uses no ICD-specific knowledge. This design involves a performance penalty: Interacting directly with the underlying ICDs instead of via the common flounder-interface would certainly perform better. Nevertheless, we chose this design, as it gives us more flexibility: The multi-hop interconnect channel can run over all present and future interconnect drivers in Barrelfish, as long as they support the common flounder interface.
131
132 \subsection{Reliability}
133
134 Interconnect drivers in Barrelfish generally provide a reliable messaging service: A message is delivered only once and each message sent is eventually delivered and its content is not corrupted. Furthermore, messages are delivered in FIFO order. The multi-hop interconnect driver is designed to provide a reliable messaging service in principle. However, contrary to the end-to-end argument, it does not provide any \emph{end-to-end} reliability, but builds on the reliability provided by the interconnect drivers of the underlying links. We accept that the multi-hop interconnect driver can fail in case any of the interconnect drivers of the underlying link fail.
135
136 \subsection{Resource usage}
137 Because it is our goal to optimize resource usage, the multi-hop interconnect driver is designed to perform considerably better in terms of resource usage compared to the scenario where we only use direct point-to-point ICD links. In particular, we save memory, because the multi-hop driver has a comparably small memory footprint. 
138
139 \section{Design overview}
140
141 Messaging in Barrelfish is connection-oriented: messages are passed via an explicit binding object, which encapsulates one half of a connection, and such a binding must be established in advance. Therefore, we have decided to support only connection-oriented multi-hop messaging (for now).  The multi-hop interconnect driver is designed in such a way that channel set-up is collapsed into the binding phase. 
142
143 We use virtual circuit switching in order to multiplex multiple multi-hop channels over the available ICD links. Virtual circuit switching has several advantages over a packed-switched approach. It ensures that all messages take the same path and thereby FIFO delivery of messages (as long as the underlying ICD links provide FIFO delivery). Moreover, it allows to create per-circuit state on the nodes of a virtual circuit. 
144
145 Each monitor maintains a forwarding table. For each multi-hop channel, entries are created in the forwarding tables at all the nodes of that channel. Messages that are sent over the channel are forwarded at each node according to its forwarding table. Those entries in the forwarding tables can be seen as per-channel created \emph{hard} state: It is explicitly created at channel set-up and deleted at channel tear-down. Additionally to the entries in the forwarding table, per-channel created state includes bindings to the neighbouring nodes on the multi-hop channel.  
146
147 In addition to the forwarding table, each node maintains a routing table. The routing table is used for channel set-up: If a node receives a channel set-up request, it determines where to forward the request with the help of its routing table. 
148
149 The virtual circuit switching approach would also allow to reserve some resources on the nodes for each channel. Per-channel reserved resources could include buffer space to save received, but not yet forwarded messages, or bandwidth on the ICD links. This is potentially very useful for congestion and flow control. Note that we cannot simply drop messages in case of congested links, as we want to provide a reliable messaging service. As of now, we do not reserve resources on the nodes, but allocate required resources dynamically.
150
151 \begin{figure}[h]
152         \begin{center}
153         \includegraphics[scale=0.7]{overview_multihop_channel.pdf}
154         \caption{Basic set-up}\label{fig:multihop-chan}
155         \end{center}
156 \end{figure}
157
158 \section{Additional monitor bindings}
159 A multi-hop channel is multiplexed over the available ICD links. However, for each multi-hop channel, there will be two additional ICD links: Two additional LMP channels will be created between the client's dispatcher and the monitor running on its core and between the service's dispatcher and the monitor on its core. LMP channels are rather cheap - they do not require polling and require only a small amount of memory. Therefore, this does not compromise our goal of optimizing resource usage. Figure~\ref{fig:multihop-chan} shows an example set-up of a multi-hop channel with the two additional LMP channels. 
160
161 Those additional channels are needed to ensure that the default monitor binding is not congested or even blocked by multi-hop messages. For example, suppose that a client's dispatcher receives a lot of multi-hop messages within a short period of time. The client reacts to this by allocating more memory. If multi-hop messages are sent over the default monitor binding, the message coming from the memory server will be blocked, therefore this will result in a dead lock. By creating new monitor bindings and not using the default monitor binding, we can prevent such a scenario.
162
163
164 \section{Virtual circuit identifiers}
165 \label{section:vcis}
166 Multi-hop messages carry a virtual circuit identifier (VCI). Virtual circuit identifiers allow nodes to identify the particular multi-hop channel a message belongs to. Each node on a multi-hop channel maintains a forwarding table, which maps VCIs to the next hop on that particular channel. A node forwards multi-hop messages based on this forwarding table. At channel end-points, a VCI allows to identify the binding belonging to the multi-hop channel the message was sent over. Virtual circuit identifiers are not only local to a specific link, but also to a direction on that link. Figure~\ref{fig:vci} shows an example assignment of VCIs.
167
168 We assign virtual circuit identifiers at random. At each node, we use a hash table to map virtual circuit identifiers to a pointer to the channel state. The use of a hash table allows efficient message forwarding. When a message arrives, it can be determined where to forward this message by means of a simple look-up in the hash table. The complexity of this lookup is linear in the number of virtual circuit identifiers that map to the same hash bucket (the number of buckets in the hash table is a compile time constant).
169
170 An attacker sending messages with manipulated virtual circuit identifiers may be able to send messages on channels not belonging to him. By assigning virtual circuit identifiers at random, we make it very unlikely for an attacker to find valid virtual circuit identifiers of channels not belonging to him.
171
172 This design requires that each node on a multi-hop channel tells its neighbours what virtual circuit identifier they should use for messages sent over that particular channel. This happens in the set-up phase of a multi-hop channel (see section~\ref{section: set-up}).
173
174 \begin{figure}[h]
175         \begin{center}
176         \includegraphics[scale=0.68]{vcis.pdf}
177         \caption{Virtual circuit identifiers} \label{fig:vci}
178         \end{center}
179 \end{figure}
180
181
182 \section{Channel set-up}
183 \label{section: set-up}
184 If two dispatchers want to communicate with the help of the multi-hop interconnect driver, they have to create a multi-hop channel first. During channel-set up, one dispatcher must act as the client and the other as the server (however, once a channel is established, the communication process on both sides of the channel is indistinguishable). 
185
186 The channel set-up process can be initiated by invoking the \texttt{multihop\_chan\_bind} function of the multihop interconnect driver. It has to be remarked that normally a user does not interact directly with the multi-hop interconnect driver, but only over the flounder generated stubs (see chapter~\ref{chapter: flounder integration} ).
187
188
189 The channel set-up process works as follows:
190
191 \begin{enumerate}
192
193 \item A client dispatcher initiates the set-up process by calling the bind function of the multi-hop interconnect driver. This function forwards the bind request to the monitor running on the client dispatcher's core. The bind request includes various parameters, including the \emph{iref} of the service and the client's (ingoing) virtual circuit identifier.
194
195 \item The monitor running on the client dispatcher's core determines (from the iref) the core on which the service resides. It then forwards the bind request to another monitor, which is determined based on the routing table.
196
197 \item Monitors receiving the bind request check whether the service is running on the same core as they are. If so, they determine the local dispatcher which has exported this iref and forward the request to it. Otherwise, the bind request is forwarded to another monitor in the same way as in step two.
198
199 \item As soon as the service's dispatcher receives the bind request, it runs the user provided connection callback. Based on the return value of this callback, it either accepts the connection or rejects it. In any case, the bind reply is sent back to the monitor.
200
201 \item The monitor proxies the bind replay back to where it received the bind request from.
202
203 \item If the client dispatcher receives the bind reply, it will run the user provided bind callback.
204
205 \end{enumerate}
206
207 In order to support setting up connections between dispatchers, the existing messaging interfaces between dispatchers and their local monitor, and between monitors has been extended.
208
209 As described in section~\ref{section:vcis}, it is necessary that each node on the multi-hop channel tells its neighbouring nodes what virtual circuit identifier they should use for messages sent over that particular channel. Therefore, each message contains the virtual circuit identifier of the sender.  The two response-messages additionally contain the VCI of the receiver. This allows the receiver of a response-message to identify the multi-hop channel the message belongs to.
210
211
212 \section{Message forwarding}
213 \label{section: message forwarding}
214 Once the multi-hop channel is set-up, messages can be sent in both directions. A message can be sent by invoking the \texttt{multihop\_send\_message} function of the interconnect driver.  This function requires that the message payload is passed as one (char) array. If a user-defined message contains multiple arguments that are not stored in continuous memory locations, either the user-defined message must be split up in multiple multi-hop messages, or a new array must be allocated and all message arguments must be copied into the newly allocated array (see chapter~\ref{chapter: flounder integration} for a discussion).
215
216 In order to support sending messages, the existing messaging interfaces between dispatchers and their local monitor, and between monitors has been extended. Each multi-hop  message contains a VCI, a field encoding the direction of the message and the message payload (as a dynamic array). Furthermore, it contains one field encoding message flags and another field used to acknowledge received messages. Those two fields are used for flow control (see section~\ref{section: flow control}).
217
218 As a multi-hop channel allows to send messages in two directions, the direction field is needed to identify the direction of a particular message. Currently we assign direction ''1'' to all messages going from the dispatcher who initiated the multi-hop channel to the other dispatcher, and direction ''2'' for messages going the opposite way. 
219
220 This definition of a multi-hop is motivated by the fact that it must be possible to transport an arbitrary message within one (or more) multi-hop messages. By using a dynamic array argument for the message payload, we can transfer data of an arbitrary size in a multi-hop message.
221
222 Internally, multi-hop messages are forwarded at every node of a multi-hop channel until they reach the receiver. We make sure that multi-hop messages cannot overtake other multi-hop messages at the nodes by enqueuing messages in the order they arrive and forwarding them in a FIFO order.
223
224 \section{Capability forwarding}
225 \label{section: capabilities}
226 Because capabilities are maintained as references to per-core state in the CPU drivers, only the LMP interconnect driver which traverses kernel-mode code can directly deliver a capability along with message payload. In the multi-hop interconnect driver, capabilities travel out-of-band from other message payload. 
227
228 To send a capability, the monitor sends a \texttt{multihop\_cap\_send} message to its local monitor, containing the capability. The monitor determines whether the capability can be sent to the remote dispatcher. In gereral, capabilities referring to inherently local state (such as LMP endpoint) may not be sent, nor may capabilities that are currently being revoked. If the capability cannot be sent, a \texttt{multihop\_cap\_reply} message is sent back to the local dispatcher containing the error code. Otherwise, the capability is serialised and forwarded along the multi-hop channel. 
229
230 The monitor running on the receiver's core reconstructs the capability from its serialised representation and forwards it to the destination dispatcher. This dispatcher identifies the binding to which the capability belongs and invokes a callback on that binding. 
231
232 The capability sender only receives a reply message in case an error occurs. An error can occur if for example the capability cannot be sent or the receiver has no space left to accommodate an additional capability.
233
234 \section{Receiving messages}
235 In order to receive messages sent over a multi-hop channel, message handlers must be registered with that multi-hop channel. In particular, three message handlers must be registered: one message handler for ''normal'' messages, one handler for incoming capabilities and one handler for capability reply messages (that are sent in case an error occurred while sending a capability).
236
237 The flounder generated stubs for the multi-hop interconnect driver (see chapter~\ref{chapter: flounder integration}) register those message handlers, not the application itself (normally).
238
239 \section{Routing tables}
240 \label{sec: routing tables}
241 The routing tables are used to determine where to forward a connection set-up request. Each monitor needs its own routing table. We currently support the automatic generation of routing tables for three basic modes of routing:
242
243 \begin{enumerate}
244 \item \textbf{Direct}: All set-up requests are immediately forwarded to the end-receiver.
245
246 \item \textbf{Ring}: We route over all cores of a system. Core $i$ forwards a request to core $i+1$ mod num\_cores.
247
248 \item \textbf{Fat tree}: We route directly between the cores that are located on the same CPU socket. On each socket, we choose a ''leader'' and route directly between all leaders. A set-up request for a core on a different socket is always forwarded over the local leader to the leader on that socket.
249 \end{enumerate} 
250
251 For the routing modes ''ring'' and ''fat tree'' we need information from the system knowledge base: We need to know the number of cores in the system for the ''ring'' routing mode. For the ''fat tree'' mode, we additionally need to know the number of cores per CPU socket (note that we assume here that sockets are continuously numbered). 
252
253 We decided that there should be no direct communication between the monitor and the system knowledge base, because it is not always present. For some architectures, such as Microsoft's experimental Beehive architecture or to a certain extend the Intel Single Chip Cloud Computer, the system knowledge base is not available. Therefore, a dependency of the monitor on the system knowledge base should be avoided.
254
255 For this reason, we decided to create a separate module, called the \emph{routing table set-up dispatcher} (RTS) that talks to the system knowledge base and to the initial monitor (the monitor that is first booted). The routing table set-up dispatcher will retrieve the required information from the system knowledge base in order to construct the routing table. Once it has constructed the routing table, it will send it to the initial monitor. 
256
257 The initial monitor will forward the (relevant parts of the) routing table to the other monitors once they are booted. This is necessary  because we want to avoid having to create a channel between each monitor and the routing table set-up dispatcher.
258
259 It must be noted that the routing table set-up dispatcher can only generate the routing tables for the cores of a single system. It cannot handle set-ups like an Intel single chip cloud computer connected to a x86 machine over a PCIe-based channel.
260
261 \section{Flow control}
262 \label{section: flow control}
263 It is possible that one dispatcher on a multi-hop channel is sending at a faster rate than the receiving dispatcher can handle incoming messages and process them. Because we want to provide a reliable messaging service, we cannot just drop messages in such a case, but have to buffer them and deliver them eventually. To limit the space needed to buffer undelivered messages, we decided to implement a flow control mechanism within the multi-hop interconnect driver. The flow control mechanism allows the receiving dispatcher to control the transmission speed, so that it is not overwhelmed with messages.
264
265 We decided to use a credit-based flow control mechanism: The number of messages in flight at any given time is limited. Once a sender has reached this limit, he has to wait until he receives an acknowledgement that the receiver has processed previously sent messages. We call this limit the \emph{window size}.
266
267 The flow control mechanism is completely transparent to applications. It is entirely handled by the multi-hop interconnect driver. On each message sent by a dispatcher over a multi-hop channel an acknowledgement for all messages previously received over this channel is piggy-backed. 
268
269 If an application uses a one-way communication schema, i.e. one dispatcher is always sending while the other is only receiving, it is not possible to piggy-back acknowledgements on messages sent the other way. In such a case, the multi-hop interconnect driver sends a dummy message. A dummy message contains no message payload, but acknowledges all received messages. This approach ensures that acknowledgements are, whenever possible, piggy-backed on messages. Only if it is absolutely necessary, an acknowledgement is sent in its own message.
270
271
272
273 \chapter{Flounder support for multi-hop messaging}
274 \label{chapter: flounder integration}
275
276 Flounder is a stub compiler which generates stubs for defined interfaces. To support multi-hop messaging, we created a new back-end code generator for the flounder stub compiler that generates code to use the multi-hop interconnect driver.  Applications do not interact with the multi-hop interconnect driver directly, but only over the generated stubs. The stubs for the multi-hop interconnect driver have the exact same interface as stubs for other interconnect drivers. This makes application code independent of the interconnect driver used for communication.
277
278 The generated stubs can be seen as an ''adaptor'' to the multi-hop interconnect driver. They  translate calls to the common flounder interface to the interface of the multi-hop interconnect driver. Supported functionality mainly includes binding, sending and receiving of multi-hop messages and some control operations.
279
280 \section{Binding}
281 If two dispatchers want to communicate with the help of the multi-hop interconnect driver, they must acquire binding objects for each endpoint of the channel. In any binding attempt, one dispatcher must act as the client and the other as the service (however, once a binding is established, the communication process on both sides of the binding is indistinguishable). The binding phase is merged with channel set-up, i.e. a new multi-hop channel will be created during the binding process. 
282
283 In order to initiate a binding, a client dispatcher calls the bind function for a given interface. Because Barrelfish features multiple interconnect drivers, the interface's bind function will have to decide which interconnect driver to use in order to establish the binding. Currently, it ''asks'' the different interconnect drivers to establish a binding in a predefined order (for example, the LMP driver is always first). As soon as an interconnect driver manages to establish the binding, the binding process is finished. Should one interconnect driver fail, the next one in order is tried.
284
285 If an application wants to create a new multi-hop channel, it can pass the flag \texttt{IDC\_BIND\_FLAG\_MULTIHOP} as an argument to the interface's bind function. This changes the order of the interconnect drivers: The multi-hop interconnect driver will come in second place, directly after the LMP driver. The LMP driver is first, because it is preferable to the multi-hop interconnect driver if client and service are running on the same core. If the multi-hop interconnect driver fails to establish a binding for some reason, the binding process continues as normal with the other interconnect drivers.
286
287 The result of the binding process on the client's and service's side is a binding object which is the abstract interface to the multi-hop interconnect driver for a specific interface type.
288
289
290 \section{Sending messages}
291 \label{section: flounder sending messages}
292 A message may be sent on the binding by calling the appropriate transmit function. We distinguish between user-defined messages and multi-hop messages. User-defined messages are those messages defined by the user in the interface. Multi-hop messages are messages that are sent over a multi-hop channel. 
293
294 As pointed out in section \ref{section: message forwarding}, the multi-hop interconnect driver requires that the message payload is passed as one char array. If a user-defined message contains dynamic arguments (arguments whose size is only known at run-time), such as a string or a dynamic array, it is generally not possible to pass the message payload as one char array to the multi-hop interconnect driver. There are three possible approaches to send such a message:
295
296 \begin{enumerate}
297 \item Allocate a region of memory capable of holding all message arguments and copy the message arguments to this region. A pointer to it can then be passed to the multi-hop interconnect driver as message payload.
298
299 \item Split a user-defined message into multiple multi-hop messages. Each argument of the multi-hop message is transported in its own multi-hop message. 
300
301 \item Use a combination of the above approaches. For instance, all fixed size arguments could be sent in one message, and each dynamically sized argument could be sent in an extra multi-hop message.
302 \end{enumerate}
303
304 In comparison to approach 1, approach 2 saves the cost of allocating a region of memory and copying all the arguments of the message to that region. In exchange for that, it needs to split a user-defined message and transport it via multiple multi-hop messages. The preferable approach depends on the type of messages that are sent. However, we think that the performance penalty involved in sending each message argument in its own multi-hop message is not acceptable for most message types. Therefore, the flounder-generated stubs for the multi-hop interconnect driver use approach 1. Approach 3 might be a possible performance optimization, but is currently not in use.
305
306 \subsection{Implementation}
307 All message arguments are copied to continuous memory locations in order to send the whole user-defined message in one multi-hop message.
308 When sending a user-defined message, we first calculate the size of its payload. The size of a message's payload is only known at compile-time if the message definition does not contain any dynamic arguments. Otherwise, the size of the payload has to be computed each time such a message is sent. After having computed the payload size, we allocate a memory region of that size and copy the message arguments to that region of memory. Finally, we pass a pointer to this memory region to the multi-hop interconnect driver.
309
310 We include the size of every dynamically sized argument in the message payload. This tells the receiver about the size of those arguments and allows him to retrieve them from the received message payload. Currently, we use 8 bytes to transfer the size of a dynamic argument. This ensures that we do not get an overflow. We account for those size fields when calculating the size of the message payload.
311
312 Capabilities are never sent as message payload. They are always sent out-of-band from ''normal'' message payload. A discussion of this can be found in section~\ref{section: capabilities}.
313
314 There is one issue regarding communication in heterogeneous systems of our implementation: To be consistent  with the common flounder interface, we have to use a variable of type \texttt{size\_t} to represent the size of a dynamic array. The type \texttt{size\_t} is architecture dependent. On a 32-bit system it will likely be at least 32-bits wide. On a 64-bit system it will likely be at least 64-bit wide. If a dispatcher on a 64-bit system communicates with a dispatcher on a 32-bit system, this can lead to a problem: The dispatcher on the 64-bit system can potentially send dynamic arrays that are bigger than the dispatcher on the 32-bit system can receive. This is a problem of the current Barrelfish version and remains unsolved.
315
316
317 \subsection{Send continuation}
318 Each transmit function takes as an argument a pointer to a continuation closure. The closure will be executed after the message has successfully been sent. If another transmit function is called on the same binding before the continuation is executed, it will return the \texttt{FLOUNDER\_ERR\_TX\_BUSY} error code, indicating that the binding is currently unable to accept another message. In this case, the user must arrange to retry the send.
319
320 The send continuation is the only way to know when a message has been sent over the multi-hop channel and it is safe to send the next message. Note that even if an application uses a ping pong communication scheme, i.e. it sends a message back and forth between two dispatchers, it is not guaranteed to not get a \texttt{FLOUNDER\_ERR\_TX\_BUSY} error code, unless it serialises all sends with the continuation. This somewhat unintentional behaviour is caused by the fact that the multi-hop channel internally relies on other ICD-links to transport messages. The multi-hop channel itself uses send continuations on the underlying ICD-links to determine when it can accept another message. Those send continuations are always executed after a message is sent. Therefore it is possible (although unlikely) that a message is sent and the reply for that message is received, before the multi-hop channel can accept the next message.
321
322
323 \section{Receiving messages}
324 The flounder-generated stubs register a callback function with the multi-hop interconnect driver at channel set-up time in order to be notified when a message arrives. As we send a user-defined message within a single multi-hop message, we therefore also receive a user-defined message in one multi-hop message.
325
326 Upon receiving a multi-hop message, we have to extract the original user-defined message from it and pass it on to the user-provided receive handler. It is a fatal error if a message arrives on a multi-hop channel and the receive handler function for that message type is not set.
327
328 If the user-defined message contains dynamic arguments, we have to allocate space for each of those arguments separately and copy them from the received multi-hop message. This is necessary, because all dynamic message arguments are passed by reference to the user and become property of the user. The user must be able to free those arguments separately, therefore they must be copied to separately allocated memory. Fixed-size arguments are simply passed on the stack to the user.
329
330
331
332 \chapter{Group Communication}
333
334 \section{Terminology}
335
336 \textbf{Groups:}
337 The set of all nodes on the machine form a \emph{universe group}.
338 The set of nodes in the universe group that
339 wish to communicate with each other form an \emph{application group}.
340 An application group is a subset of the universe group.
341 A subset of nodes in the application group can form a \emph{multicast group}.
342
343 It is possible to join and leave any multicast and application group.
344
345 \textbf{IDs:}
346 Each application group is identified by a \emph{group ID}.
347 The group ID in turn identifies the instance of routing library to use.
348 The group ID is unique within the universe group.
349
350 Each multicast group is identified by \emph{multicast ID}.
351 The multicast ID is unique within the application group.
352
353 When nodes join an application group, they are assigned a \emph{node ID}.
354 The node ID is unique within the application group.
355
356 Each node is also given an \emph{application broadcast ID}.
357 These may or may not be unique and are drawn from a set that
358 may just have a single element.
359
360 The union of the set of node ID, multicast ID, and application broadcast ID is
361 called the \emph{destination ID}.
362 The set of node IDs, multicast IDs, and application broadcast IDs are disjoint.
363
364 \textbf{Messaging:}
365 It is not possible to communicate with nodes in the universe group that
366 are not in the application group.
367
368 A node can send a message to another node in the application group by
369 sending a message to the appropriate node ID.
370 A node can send a message to all nodes in the application group by
371 sending a message to the application broadcast provided to it.
372 A node can send a message to all nodes in an multicast group by
373 sending a message to the multicast ID provided to it
374 when it joined the multicast group.
375
376 \textbf{Types of messages:}
377 \emph{Unicast:} Send a message to a single node in the application group.
378 \emph{Broadcast:} Send a message to all nodes in the application group.
379 \emph{Multicast:} Send a message to all nodes in the multicast group.
380
381
382 \section{Semantics}\label{sec:semantics}
383
384 The routing layer will provide a uniform set of semantics to the
385 application layer regardless of the set of semantics the
386 IDC mechanisms below it provide.
387 It can provide different semantics to suit the
388 needs of different application scenarios.
389
390 Below, we discuss the different set of semantics it can provide.
391
392 \subsection{Set 1: Single source FIFO}
393 The set of semantics provided are as follows:
394
395 \begin{itemize}
396 \item Reliability:
397   A message is delivered only once and only if it was sent earlier.
398   Each message is eventually delivered and the contents are not corrupted.
399 \item Single source FIFO ordering:
400   If a sender sends $m$ before $m'$ then $m$ is delivered before $m'$
401   at all receivers.
402 \item Failure:
403   The routing library will not fail.
404 \item Payload:
405   The IDC can deliver an arbitrarily sized message.
406 \end{itemize}
407
408 \subsection{Set 2: Causal order}
409 The set of semantics provided are as follows:
410
411 \begin{itemize}
412 \item Reliability:
413   A message is delivered only once and only if it was sent earlier.
414   Each message is eventually delivered and the contents are not corrupted.
415 \item Causal ordering:
416   If the delivery of message $m$ depends upon the delivery of message $m'$ as
417   per the \emph{happened before} relationship \cite{events-time},
418   then $m$ is not delivered till $m'$ has been delivered.
419 \item Failure:
420   The routing library will not fail.
421 \item Payload:
422   The IDC can deliver an arbitrarily sized message.
423 \end{itemize}
424
425 \subsection{Set 3: Total order}
426 The set of semantics provided are as follows:
427
428 \begin{itemize}
429 \item Reliability:
430   A message is delivered only once and only if it was sent earlier.
431   Each message is eventually delivered and the contents are not corrupted.
432 \item Total order:
433   All messages are delivered to all nodes in the same order.
434 \item Failure:
435   The routing library will not fail.
436 \item Payload:
437   The IDC can deliver an arbitrarily sized message.
438 \end{itemize}
439
440 It is possible to order messages using various types of ordering mechanisms.
441 Investigation of this remains future work.
442
443 \subsection{Additional sets}
444 In future, if we choose to provide additional set of semantics,
445 they will be listed here.
446 They could include weaker semantics than above if the underlying IDC mechanism
447 are too expensive.
448 Some example are just reliability, or not even providing reliability.
449
450 \section{Interface}
451 We discuss the interface for group management and sending/receiving of messages.
452
453 \subsection{Group management}
454
455 \textbf{Creating groups:}
456 Before nodes can join a group, they need to be created.
457 Any dispatcher in the system can create a new application group
458 and any node in an application group can create a new multicast group
459 within the application group.
460
461 The library will return to application a group ID or
462 multicast ID of the created group.
463
464 \textbf{Updating a group:}
465 A dispatcher can join any application group by calling join on
466 the application group ID.
467 A node can join any multicast group within the application group it is part of.
468 When the join has finished, the node gets the join callback from the library.
469 When a dispatcher is done joining an application group,
470 it can query the library for its node ID and application broadcast ID.
471
472 Similarly a node can leave a group at anytime by calling leave on the group ID.
473 When the leave is done, the application will get a leave callback.
474 A dispatcher should call leave before it exits the system.
475
476 The behavior of the group is undefined while membership is in flux.
477 New links are being created and old links are being torn down.
478 Messages may not reach their proper destination.
479 If such guarantees are required at all times in the application,
480 the application must refrain from sending messages while
481 group member is in flux.
482
483 %\section{Flow control}
484 %The IDC mechanisms that the routing library operates over are asynchronous.
485 %When a message is sent over them,
486 %it will eventually be delivered to the receiver.
487 %Undelivered messages are maintained in a queue of fixed length.
488 %If the sender tries to send messages too quickly the queue can fill up.
489 %If the queue is full, the sender must wait
490 %till the queue has room for more messages.
491 %IDC mechanisms allow senders to register callbacks in such situations.
492 %When a send fails with the transient error that
493 %the queue is full, the sender can register
494 %a callback which will be called when the next send should not fail.
495 %While the sender waits for the callback, it has to handle the unsent message.
496
497 %We discuss the simple scenario of two nodes and
498 %then a more complex scenario of many nodes.
499
500 %\subsection{Client-server model}
501
502 %\begin{figure}[t]
503 % \includegraphics[width=\columnwidth]{client-server.pdf}
504 % \caption{Client-server model}\label{fig:client-server}
505 %\end{figure}
506
507 %Figure \ref{fig:client-server} shows a simple client-server model
508 %of two nodes that are directly connected.
509 %The weights on the edges is the length of the queue.
510 %The client sends messages to the server, the server processes them
511 %and sends replies to the client.
512 %It is possible that link1 becomes full maybe because
513 %the client has not been handling replies on it.
514 %At this point the server has some options:%
515
516 %\begin{itemize}
517 %\item Drop the message.
518 %  The server can simply drop the message if the queue is full.
519 %  This will result in an unreliable channel.
520 %\item Allocate some resources and queue the message up.
521 %  This implies unbounded resource requirement.
522 %\item Apply back pressure on the client.
523 %  The server at this point can stop processing messages
524 %  from the client till it is able to send messages to it again.
525 %\end{itemize}
526
527 %In this model the last option works well as it will force the client
528 %to slow down and process replies before sending more requests.
529
530 %\subsection{Multihop route}
531
532 \begin{figure}[t]
533  \includegraphics[width=\columnwidth]{many-to-many.pdf}
534  \caption{Example multihop route}\label{fig:many-to-many}
535 \end{figure}
536
537 %In this scenario the problem is more complex.
538 %Figure \ref{fig:many-to-many} shows a group of 5 nodes,
539 %the link weights specifies the queue length of the link.
540 %If node1 and node2 are sending messages to node4,
541 %link34 will fill up before link13 or link23 does.
542 %Node3 cannot send additional messages to node4.
543 %At this point, node3 has the following options:
544
545 %\begin{itemize}
546 %\item Continue to process incoming messages on link13 and link23.
547 %  If they are destined for node4, drop them.
548 %  This will result in an unreliable channel.
549 %\item Continue to process incoming messages and if they are destined for node4,
550 %  queue them up locally.
551 %  This implies unbounded resource requirement.
552 %\item Stop processing messages on link13 and link23.
553 %  This will delay messages on those links that were not destined to node4.
554 %  In literature, this is called \emph{Head of line blocking} \cite{cite}.
555 %\end{itemize}
556
557 %None of these solutions are particularly desirable.
558 %Flow control in the context different types of networks has
559 %been studied previously.
560 %We should study the related work before we come up with our own designs.
561
562 %I summarize some existing work I am aware of here that we should look into:
563 %\begin{itemize}
564 %\item Credit based flow control:
565 %  The endpoints dictate maximum number of messages in flight.
566 %\item TCP flow control
567 %\item Ethernet flow control
568 %\item Datacenter ethernet flow control
569 %\item Related work in routing between sockets on a machine
570 %\item QoS (DiffServ and IntServ).
571 %\end{itemize}
572
573 %Some applications may not be willing to pay the cost of flow control.
574 %Further, a flow control mechanism that guarantees reliability
575 %may not scale well with  number of nodes.
576 %This can be an interesting research topic for us.
577
578 %We discuss some abstract ideas we have for flow control below.
579
580
581
582 \section{Open questions}
583 Some open questions
584
585 \subsection{Reservation of resources with end-to-end flow control}
586 The essential idea is that when a route is established,
587 reservations for some number of in flight messages are made for the route.
588 Even though the links might be shared,
589 no other routing path is allowed to use the reserved resources.
590 The endpoints must then limit the number of in flight messages.
591 If they exceed it, the library can deliver an error at the endpoint or try to
592 optimistically deliver the message and drop the message if it is unable to.
593
594 For example, in figure \ref{fig:many-to-many},
595 if reservations for two messages is made for the routing path
596 from node1 to node4, node1 and node3 each will maintain a queue of size 2.
597 Whenever they receive a message from the application in node1 destined to node4
598 and they are not able to send it on the link,
599 they can locally store the message.
600 Eventually, when the link has space in it,
601 they can try to send the message again.
602
603 It remains to be seen if the approach can work and scale well.
604 \note{Cite work on switching networks and other works that make reservations and
605   give guarantees.}
606
607 This approach works when the nodes that are sharing the links
608 cooperate with one another.
609 However, if the link is shared between distrustful
610 nodes then additional guarantees of fairness and no starvation maybe required.
611
612 \begin{figure}[t]
613  \includegraphics[width=\columnwidth]{client-monitor.pdf}
614  \caption{A network of monitor with clients}\label{fig:client-monitor}
615 \end{figure}
616
617 Figure \ref{fig:client-monitor} shows a network of two monitors.
618 Each monitor is connected to two clients.
619 Clients A1 and A2 are cooperating and client B1 and B2 are cooperating.
620 The clients want to send some messages that must go through the monitors such as
621 transferring capabilities.
622 If one pair of client is aggressive in sending messages,
623 it may fill up the link between the monitors and impact the performance
624 of the other pair of clients.
625 In this scenario, the link between the monitor can be seen
626 as a common system resource that is being multiplexed between the users.
627 The monitors should guarantee some fairness to the users in using this link.
628
629 \subsection{Discovering node IDs}
630 When a set of dispatchers join an application group,
631 each of them is assigned a node ID.
632 The nodes need some mechanism of discovering the IDs of each other
633 so that they can message each other.
634
635 The discovery service will be built on top of the routing library
636 and can be designed in multiple ways.
637 Nodes can send broadcasts to each other informing each other of their node IDs,
638 they can use the name service, etc.
639
640 \chapter{Interesting benchmarks}\label{chap:benchmarks}
641
642 Some benchmarks that validate the claims of above and show the performance of the library.
643
644 \note{Costs of one-to-many channels. One sender, multiple readers.}
645
646 \note{Comparison of routes with no forwarding and routes with forwarding.}
647
648 \note{Resource requirements for channels, memory and cpu time.}
649
650 \note{Cost of the discussion group membership update mechanism.}
651
652 \chapter{Fun research questions}
653
654 \begin{itemize}
655 \item Flow control
656 \item Link state vs. distance vector routing
657 \end{itemize}
658
659 \bibliographystyle{abbrvnat}
660 \bibliography{defs,barrelfish}
661
662 \end{document}