The Reimplementation of theRRDP Transport ProtocolC.McAvaney, J.Rough, G.Wickham,D.De Paoli{chrismc,ruffy,gjw,ddp}@.auSchool of Computing and MathematicsDeakin UniversityGeelong, Victoria, 3217AbstractThe RHODOS Reliable Datagram Protocol (RRDP) is an integral part of the RHODOS distributed operating system. The existing implementation of RRDP, after years of development, has begun to show inadequacies that are hindering the whole RHODOS system. This document describes what was the existing implementation of RRDP, the problems that existed, and reports on the reimplementation of the RRDP protocol. Minor modifications made to the actual protocol and the supporting infrastructure in the operating system are also described within.The Reimplementation of the RRDP Transport Protocol1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12 Overview of RHODOS Interprocess Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.1 Message Delivery. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12.2 The RHODOS System Name (SName) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.3 Berkeley Memory Buffers (MBufs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22.4 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.4.1 The send() primitive. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.4.2 The recv() primitive. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.4.3 The call() primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.5 Remote Interprocess Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.6 The Roles of RHODOS Components in Remote Interprocess Communication . . . .62.6.1 The Microkernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.6.2 IPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.6.3 RRDP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.6.4 IP/Eth. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 The RRDP Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83.1 RRDP Packet Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83.2 Packet Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .103.3 Sending Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .113.4 Receiving Messages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123.5 Resolution of Network Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133.6 Unreliable RRDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133.7 Protocol Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .134 Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144.1 Message Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144.2 Optimum Timeout Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144.3 Removal of RRDP/IP header dependency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155 Performance Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .167 Acknowledgements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17Page iiThe Reimplementation of the RRDP Transport Protocol 1 IntroductionDistributed operating systems aim to provide a transparent interface to a cluster of workstations connected together by a local area network. Crucial to this objective is the provision of a high-performance interprocess communications facility. The two components of this facility are the interprocess communication primitives and the supporting transport protocol for remote communication [Goscinski1991]. The reimplementation of the supporting transport protocol (RRDP) is the subject of this report.The previous implementation of RRDP lacked timeouts and hence full reliability. The delivery of messages would fail if the last packet of a group (Section 3.2) was lost or corrupted. Additionally, the resources used by the message would not be freed due to an impasse where the sender was waiting for an acknowledgement (where it would free the resources), and the receiver was waiting for the final packet to arrive before it would send the acknowledgement. Although implementing timeouts in RRDP should have been a trivial exercise, several race conditions existed that complicated the task somewhat. These race conditions had caused modifications to RRDP to be abandoned in the past, thus one of the objectives of this project was to eliminate these race conditions.The goals of this project were to introduce timeouts reliably to the protocol, minimising any changes to servers that interact with the RRDP server. Once completed, all race conditions were to have been eliminated in the RRDP server, allowing future improvements and fixes to be applied to the protocol without unnecessary complication.Section2 provides an overview of interprocess communication in RHODOS including the roles of RHODOS components in providing the interprocess communication service. Section3 describes the RRDP protocol including packet structures, the procedures used for transmitting and receiving messages, and handling of network failures. Important issues that were raised during the implementation of this project are presented in Section4. A comparison of the performance of the old and new implementations of RRDP is in Section5. Finally Section6 concludes this report and indicates future work to be done on RHODOS interprocess communication.2 Overview of RHODOS Interprocess CommunicationThis section describes the implementation of interprocess communication in the RHODOS operating system. The roles and responsibilities of the Microkernel, IPCM, RRDP and IP/Eth servers are discussed. Additionally, the structure and semantics of communication between these components is described.2.1 Message DeliveryAll messages in RHODOS are sent to a “port”, with any process allowed to have any number of ports to receive messages on. A port is a logical entity maintained by the Microkernel and has associated with it an “operation queue”. Messages are delivered to a port by being referenced by an operation structure (oper), which is stored in the operation queue. The oper contains the details about the message, such as the return port, a pointer to the message (stored in MBufs), and pointers to the Process Control Blocks (PCBs) of any processes with blocked operations on that port.Page 1The Reimplementation of the RRDP Transport Protocol Page 2Two models are used for message delivery. In the first model, the message is copiedinto buffers maintained by the Microkernel, in this case Berkeley MBufs [Leffler et al 1989].The message is then added to the destination port’s operation queue for retrieval by a matchingreceive. When a matching receive is invoked the message is copied from the MBufs into thedestination process’ memory, and the MBufs are freed. In cases where a matching receive hasalready been invoked on the destination port, a second model is used where the message iscopied directly from the sending process’ buffer to the destination process’ buffer, thuseliminating a copy operation. These mechanisms are discussed extensively in[Goscinski et al 1994a].2.2 The RHODOS System Name (SName)In order to differentiate between the different active ports across the whole distributedsystem, some form of identification (naming) is necessary. RHODOS’ naming structureconsists of three levels: user level, system level, and low level (physical) naming[Goscinski et al 1994b]. System names (SNames) are used to identify objects used at thesystem level, hence ports are identified by an SName. The structure of the SName is shown inBlock 1. The fields that uniquely describe a port are the origin (sn_origin), which identifies theworkstation where the port was created; and the object number (sn_object ) which differentiatesbetween ports created on the same workstation.2.3 Berkeley Memory Buffers (MBufs)The demands placed on memory management for interprocess communication arevery different to the demands from other parts of an operating system. The MBuf data structure(shown in Block 2) was designed to provide an efficient allocation and reclamation scheme forinterprocess communication systems [Leffler et al 1989].The advantage of MBufs is that data can be inserted or removed at the beginning of anMBuf by manipulating the value of the m_off variable, and can be appended or removed at theend of an MBuf by manipulating the value of the m_len variable. This is extremely usefulwhen used in network protocols, where manipulation of packet headers (and trailers) occursfrequently. MBufs are shared in RHODOS, used for the storage and passing of messagesbetween: the Microkernel; IPCM; RRDP; and IP/Eth.If the data structure that is to be stored in MBufs is larger than the data region in asingle MBuf, then several MBufs can be linked via the m_next field to hold the data structure.Block 1: The RHODOS System Name (SName)The Reimplementation of the RRDP Transport Protocol Page 3This is known as a “chain” of MBufs. Several chains can also be linked together using them_act field, form a linked list.The implementation of MBufs in RHODOS is not identical to that of Berkeley. Themost obvious change is the addition of the m_flags field, which used to indicate to the IP/Ethserver (Section 2.6.4) whether the MBufs holding a packet can be deleted once the packet istransmitted.2.4 PrimitivesThe first point of contact for all interprocess communication primitives in RHODOSis the Microkernel (Section 2.6.1), invoked by using the primitives described in this section.RHODOS provides two models of interprocess communication: message passing (send() andrecv()); and remote procedure calls (call(),recv(), and send()).2.4.1 The send() primitiveThe send() primitive (Block 3) is used to send a message from one process to another.It requires four arguments:•dest_port - the SName of the receiving (destination) port for the message;•return_port - the SName of a port where return messages can be sent;•send_args - a data structure holding the parameters of the send operation, such as thelocation of the user’s buffer, the length of that buffer, etc. Several of these structures can belinked together to issue a send operation using several buffers (termed a multibufferedsend);•send_results - a data structure that is populated with the results of the send operation such asthe total amount of data transmitted.2.4.2 The recv() primitiveThe recv() primitive (Block 4) is used to receive a message that has been delivered.The recv() primitive waits for a matching message to be delivered if necessary. It requires fourarguments:•dest_port- the SName of the destination port where the message is attached or will arrive;Block 2: The MBuf Data StructureThe Reimplementation of the RRDP Transport ProtocolBlock 3: The RHODOS send() Primitive•return_port - an SName structure that can optionally be used to place restrictions on the return port;•recv_args - a data structure holding the parameters of the receive operation, such as the location of the user’s buffer, the length of that buffer, etc. Several of these structures can be linked together to issue a receive operation using several buffers (termed a multibuffered receive);•recv_results - a data structure that is populated with the result of the receive operation such as the total amount of data received.Block 4: The RHODOS recv() Primitive2.4.3 The call() primitiveThe call() primitive (Block 5) is used to provide remote procedure calls. Although the call() primitive is an atomic system call, it is logically composed of a call to the send() primitive, followed by a call to the recv() primitive. The call() primitive requires four arguments:•dest_port - the SName of the destination port for the RPC (the process providing the service);•call_args - a data structure holding the parameters of the call operation, such as the location of the user’s buffers for both the request and response, the length of each of those buffers, etc. Several of these structures can be linked together to issue a multi-buffer request;•call_results - a data structure that is populated with the results of the call operation such as the total amount of data transmitted and received.2.5 Remote Interprocess CommunicationTwo paths are used for remote interprocess communication in RHODOS. In the default path, messages are transmitted reliably using the RRDP protocol. RRDP also provides an unreliable service (see Section 3.6) if the use of a reliable protocol is deemed to be too expensive. The second delivery mechanism involves the use of the “Fast Eth” protocol. Fast Page 4The Reimplementation of the RRDP Transport ProtocolBlock 5: The RHODOS call() PrimitiveEth is an extremely light weight (unreliable) protocol, located directly over the Ethernet layer. Due to its placement, the Fast Eth protocol can only be used for communications within a subnet. The Fast Eth protocol is not relevant to this report and will not be discussed any further.A process sends a message in RHODOS by invoking the send() primitive (Section2.4.1). If the destination port for a message is local, the message is delivered as described in Section 2.1. If the destination port is not local, then the message is forwarded to the IPCM for resolution. The IPCM first determines the destination for the message (see Section2.6.2), and then forwards the message to the RRDP server, along with the address of the workstation for the message to be sent to. The RRDP server transmits the message by splitting the message into packets, and forwarding the MBufs (Section2.3) holding the packets to the IP/Eth server. Finally the IP/Eth server transmits the packets on the network.Any RRDP packets arriving from the network (received by IP/Eth), are passed up to the RRDP server, which reconstructs the incoming message and forwards it to the local IPCM for delivery to the destination port. These mechanisms are depicted in Figure1. It is important to realise that the message is only copied once, either from the user’s buffer into MBufs during a send operation, or from MBufs into the user’s buffer during a receive operation. A message or packet is forwarded between servers by passing a pointer to the MBufs that hold the message/packet.Figure 1: Structure of Remote Interprocess Communication in RHODOSPage 5The Reimplementation of the RRDP Transport Protocol2.6 The Roles of RHODOS Components in Remote Interprocess CommunicationThe servers involved in providing remote IPC are described in this section. In particular, the roles of the Microkernel, IPCM and IP/Eth servers are presented. Communication between the RRDP server and other servers are also described. An overview of interactions with the RRDP server can be seen in Figure 2.2.6.1 The MicrokernelThe first point of contact for all RHODOS interprocess communication is the Microkernel (Section 2.4). When a new message is received, the Microkernel checks that the return port is valid (checks that it exists locally), and then determines whether or not the destination port exists locally. If the destination port is local, then the message is attached using the oper structure described in Section 2.1. If the destination port it is not local, the message is packed into MBufs (Section 2.3) and forwarded to the IPCM for resolution.Messages are packed into MBufs by the Microkernel in sequences such that they can be easily divided into separate chains equal to the length of the data part of an RRDP packet. This means that the Ethernet, IP, and RRDP packet headers (see Section 3.1) can be attached to the data without needing to move any data between MBufs to fully utilise a packet.When a message arrives at a destination workstation, the IPCM delivers the message by using the send() primitive. The IPCM’s call to send() is different to usual, in that the return port is not checked to see if it exists locally, and the message is stored in MBufs. This allows the IPCM to deliver messages from remote hosts, specifying a remote SName as the return port if necessary. The message is attached to the destination port using the oper structure described in Section 2.1. The Microkernel then attempts to pair the new message with any blocked receive operations.2.6.2 IPCMThe IPCM is responsible for the delivery of messages destined for ports that do not exist locally. The IPCM always receives messages in MBufs, either from the Microkernel for outgoing messages, or from the RRDP server for incoming messages. When a message arrives for remote delivery, the IPCM first sends the message to the workstation where the destination port was created (the port’s origin). If the port has not been migrated, then the port will exist on that workstation and the message is delivered.If the port has been migrated, the remote IPCM returns the message to the source IPCM, along with the workstation where the port currently exists. The source IPCM stores a mapping for the port for future messages, and the message is sent to the new workstation [De Paoli1996].To transmit an outgoing message, the IPCM forwards the message to the RRDP server, along with additional information identifying the source workstation of the message, the return (source) port and destination port origin and object numbers, and the quality of service required for delivery of the message. The RRDP server later returns an acknowledgement to the IPCM to indicate the success or failure of delivery of the message to the remote workstation.Page 6The Reimplementation of the RRDP Transport ProtocolPage 7The sending process invokes send() for a message destined to a remote port. The message is forwarded to the IPCM for resolution.The IPCM forwards the message to RRDP with the address where the message is to be sent.The RRDP server splits the message into packets and forwards the packets to IP/Eth for resolution.The IP/Eth server on the sending workstation sends the packets to the remote workstation, received by the remote IP/Eth server .The first group is forwarded to the remote RRDP , which returns an acknowledgement to the sending RRDP server.The second (and last) group of packets is sent to the remote workstation.The last group is forwarded to the remote RRDP server.The RRDP server returns an acknowledgement to the sending RRDP server and then forwards the reconstructed message to the IPCM.The message is forwarded to the receiving process.Sender IPCM RRDP IP/Eth IP/Eth RRDP IPCM Receiver Figure 2: Overview of Remote Interprocess Communication with RRDP in RHODOSThe Reimplementation of the RRDP Transport ProtocolPage 8The IPCM receives incoming messages from the RRDP server, along with theadditional information provided to RRDP by the source IPCM. The IPCM checks for the existence of the destination port on the local workstation, and if the port exists it forwards the message to the destination process using the send() primitive as discussed in Section 2.6.1. If the port does not exist locally, and has not existed locally and then been migrated to another workstation, the IPCM notifies the source IPCM that the destination port was invalid.2.6.3 RRDPThe RRDP server is responsible for delivering messages between workstations. This includes the division of messages into packets (although this is helped by the Microkernel as discussed in Section 2.6.1), reliable delivery of the packets to the remote workstation, and reconstruction of the original message on the remote workstation. RRDP is discussed in depth in Section 3.2.6.4 IP/EthThe IP/Eth server receives packets for transmission from the RRDP server, stored in chains of MBufs. The data in the first MBuf of each chain begins with the IP header for the outgoing packet, with the protocol number and destination address fields filled in by the RRDP server. The IP/Eth server populates the remaining fields of the IP address, attaches an Ethernet header, and queues the packet for transmission by the Ethernet device driver.Any RRDP packets that arrive from the network are packed into MBufs and forwarded to the RRDP server. The RRDP packets are identified by the protocol number field in the IP header (see Figure 3). The ICMP [Postel1981] and IGMP [Deering1989] protocols are also partially supported. All other packets addressed to the workstation are ignored.3 The RRDP ProtocolThe RRDP Protocol is a reliable datagram based transport protocol developed using the concept of a multidatagram protocol. RRDP was initially built upon UDP [Goscinski et al1990], but UDP has since been removed from the model. A datagram based, connectionless protocol was selected for its high performance and low setup overheads. This section presents a description of the implementation of the RRDP protocol.3.1 RRDP Packet StructureThe structure of RRDP packets, as with other network protocols, involves a header part and a data part. The header is shown in Figure 3. The Ethernet and IP protocols are well documented by other literature and will not be addressed here. The value of the protocol field in the IP header is given a value that is recognised by RHODOS workstations as the RRDP protocol. The value used in this field is unimportant, except it cannot be a protocol number used by any other workstations on the network.The RRDP header is composed of 13 fields (see Figure 3). The message number, source location,destination origin,destination object,source origin, and source object fields are supplied by the RHODOS Interprocess Communications Manager (IPCM). The DCM Message Number and DCM Origin fields are set by the Data Collection Manager [Wickham1997].The message number field uniquely identifies every outgoing message from a particular workstation. The message number is generated by a simple counter mechanism maintained by the IPCM. The source location field identifies the workstation that is currently transmitting a message. The destination origin and object fields are used to identify the destination port SName. The source origin andobject fields are used to identify the SName of the return port provided by the sending process.1The group number field is initially given the value of 0 and incremented before the transmission of a new group, hence the first group transmitted is group 1. The sequence bit field is initially set at the least significant bit, and left shifted once to identify each packet in the group. Each of these identifiers are then combined to form a “bitmap” of the packets that have arrived at the destination workstation. This bitmap is returned in the sequence bit field as part of the acknowledgement. The version field is reserved for future use. The quality of service field indicates whether a message is being transmitted reliably or not (see Section 3.6). The1.the format used for representing the IP header in this diagram was adapted from [T anenbaum 1996].Figure 3: RRDP Packet Header 1type of packetfield indicates whether a packet is a data packet, or acknowledgement packet. Finally, the padding field is used to align the data section to a 32-bit boundary.3.2 Packet GroupsThe original proposal for the RRDP protocol [Goscinski et al1989] was a stop-and-wait protocol where an acknowledgement was required for each packet transmitted. In an effort to reduce the number of acknowledgments in RRDP, a multidatagram approach was introduced, where several packets are transmitted before an acknowledgement is required (Figure 4).Figure 4: Multidatagram protocol with group size 4The number of packets transmitted in a group can be any value between 1 (which causes RRDP to revert to a stop-and-wait protocol) and 32. These limits are imposed by size of the sequence bit field of the RRDP header which is 32-bits. Figure 5 demonstrates the relation between group size and message turnaround time for message sizes varying from 10k to 100k, increasing by 10k increments.It can be seen that as group sizes are increased, minimal turn around times are reached for larger messages. Once the optimal value for a message size is reached, it remains much the same for the remaining group sizes. For example, a message size of 10k reaches an optimal reading at a group size of 9, whereas a message of 100k reaches its minimum value at a group size of approximately 29 packets.However, it was also found that the larger the group size, the higher the number of buffer overruns (missed packets) in the Ethernet handler. This problem can be attributed to the network congestion that is caused by releasing such a large number of packets in quick succession, and a lack of support for flow control to prevent this problem. There are two alternatives that can be used to reduce this problem: the size of the Ethernet handler’s receive buffer can be increased, or the group size can be reduced. However these alternatives do not resolve the lack of flow control that causes this problem, thus they are not solutions. Support for flow control is the subject of future research in RRDP.An arbitrary group size of 29 has been selected for its optimal time values up to a 100k message size, but no true optimal value will be able to be found until flow control is introduced to the protocol.3.3 Sending MessagesNew messages are received by the RRDP server from the IPCM in a single chain of MBufs. This chain is immediately separated into several smaller chains, each no longer than the maximum data payload length of an RRDP packet. This procedure is assisted by the way that the Microkernel packs a message into MBufs (discussed in Section 2.6.1).An entry is added into RRDP’s internal state tables, and the first group of packets is transmitted by passing chains of MBufs containing the packets to IP/Eth (see Section 2.6.4). The send state table entry (STE) is marked as waiting for an acknowledgement and RRDP continues to accept messages. If no acknowledgement arrives within a specified period, a timeout occurs and the packets of that group are retransmitted. The value of the timeout is currently set to an arbitrary value of 200ms, and is the subject of future research.Whenever a timeout occurs and packets are retransmitted, the timeout is reset to twice the value of previous setting, and after five timeouts it is decided that the message is undeliverable. If an acknowledgement does arrive, the timeout value is reset to the initial 200ms, and the process repeats.When an acknowledgement arrives and there are packets that haven’t been acknowledged as having arrived safely, those missing packets are immediately retransmitted。
