DOC PREVIEW
A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOL

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOLBrian Whetten, University of California at Berkeley ([email protected])Todd Montgomery, West Virginia University ([email protected])Simon Kaplan, University of Illinois at Champaign-Urbana ([email protected])AbstractThis paper presents the Reliable Multicast Protocol (RMP). RMP provides a totally ordered, reliable, atomicmulticast service on top of an unreliable multicast datagram service such as IP Multicasting. RMP is fully andsymmetrically distributed so that no site bears an undue portion of the communication load. RMP provides awide range of guarantees, from unreliable delivery to totally ordered delivery, to K-resilient, majority resilient,and totally resilient atomic delivery. These QoS guarantees are selectable on a per packet basis. RMP providesmany communication options, including virtual synchrony, a publisher/subscriber model of message delivery, aclient/server model of delivery, an implicit naming service, mutually exclusive handlers for messages, andmutually exclusive locks.It has commonly been held that a large performance penalty must be paid in order to implement total ordering--RMP discounts this. On SparcStation5's on a 1250 KB/sec Ethernet, RMP provides totally ordered packetdelivery to one destination at 1070 KB/sec throughput and with 4.0 ms packet latency. The performance staysroughly constant independent of the number of destinations. For two or more destinations on a LAN, RMPprovides higher throughput than any protocol that does not use multicast or broadcast.Keywords: Congestion control, internetworking, distributed network algorithms, reliable multicast1 IntroductionTotally ordered, reliable broadcast and multicast protocols have existed for quite some time [ChMa84], andprovide a powerful tool for programming distributed systems and distributed databases [Chang84]. Newapplications such as Computer Supported Cooperative Work (CSCW) programs, groupware systems and sharedtools can also benefit greatly from this service. In the past, these protocols have had problems with performance,efficiency, and/or scalability. It has become a widespread belief that these are inherent problems with a totallyordered reliable multicast protocol [RaLi93]. In part, this concept resulted from the fact that in the pastmulticasts had to be implemented as a series of unicasts to each destination. Recent developments such as the IPMulticasting standard [Deering89] now allow a multicast datagram to be sent to multiple destinations over aninternetwork. In the case where all destinations are on the same LAN, one multicast packet to all of them coststhe same as a unicast packet to just one.This paper presents the architecture of the Reliable Multicast Protocol (RMP). RMP provides a reliablemulticast service on top of unreliable datagram services such as IP and IP Multicasting. RMP is based on thetoken ring technique originally proposed by J. M. Chang and N. F. Maxemchuk in [ChMa83] and [ChMa84].This CM protocol provides totally ordered atomic broadcast to a single group of broadcast clients on a LAN.While RMP uses an algorithm similar to this CM protocol for its basic delivery, it differs in the followingways:1) RMP provides multiple multicast groups, as opposed to a single broadcast group.2) RMP provides an implicit naming service that maps textual group names into communication groups. 3) Instead of only providing totally ordered, K-resilient packet delivery, RMP allows the user to select from awide range of guarantees, including agreed and safe delivery, selectable on a per-packet basis.4) For increased scalability, RMP allows processes that are not members of a group to send messages to it,and receive replys to messages, through its multi-RPC mechanism.25) The CM membership algorithm handles all cases, and takes an extended period of time to run. RMPoptimizes for the common membership change case with the addition of a new membership algorithm that allowsnon-failure membership changes to be made at the cost of only a single group message.6) RMP uses a new membership algorithm that handles faults. It is faster, less likely to mistakenly removeprocesses from a group, and supports virtual synchrony and extended virtual synchrony.7) To facilitate replicated services, RMP provides a set of mutually exclusive handlers for messages. Amessage can request that it be handled, and at most one process will reply to the message. 8) RMP provides a windowed flow and congestion control mechanism that allows RMP to provide highperformance over both LANs and WANs, even in the face of congestion.9) RMP shows how to seamlessly extend reliable multicast to hosts that do not support multicast.10) The implementation of RMP has demonstrated exceptional performance. For a single destination, itsperformance rivals or exceeds that of most TCP/IP implementations. The performance stays almost constantirregardless of the number of group members per LAN. For totally ordered messages to groups of three or moreprocesses, RMP provides performance equal to or better than any protocol we know of.The basic RMP protocol provides what can be thought of as N-way virtual circuits, called groups, betweensets of processes connected by a multicast medium. It is fully distributed, so that all processes play the same rolein communication. While primarily using NACKs for error detection and retransmission, RMP provides truereliability and limits the necessary buffer space by passing a token around the members of a group.RMP provides a wide range of reliability and ordering guarantees on packet delivery, selectable on a perpacket basis. In addition to unreliable and reliable but unordered quality of service (QoS) levels, RMP canprovide atomic, reliably delivery of packets ordered with respect to each source. It can also efficiently providedelivery of packets in both total and causal order, using causal ordering as defined in [Lamp78]. Totally ordereddelivery also provides virtual synchrony, as first defined by the ISIS project [BSS91]. Virtual synchronyguarantees that when new members join or leave a group these operations appear to be atomic, so that the sets ofmessages delivered before and after each membership change are consistent across all sites. Using K-resilientfault tolerance, RMP can provide total


A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOL

Download A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOL
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOL and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A HIGH PERFORMANCE TOTALLY ORDERED MULTICAST PROTOCOL 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?