A Group Communication Protocol for CORBA
A Group Communication Protocol for CORBA
L.E.Moser,P.M.Melliar-Smith,R.Koch,K.Berket
Department of Electrical and Computer Engineering
University of California,Santa Barbara93106
Abstract
Group communication protocols are used in fault-tolerant
systems to maintain strong replica consistency.The Fault-
Tolerant Multicast Protocol(FTMP)described here is a
group communication protocol specifically designed for the
Common Object Request Broker Architecture(CORBA).
FTMP operates over IP Multicast,and consists of the
Reliable Multicast Protocol(RMP)that provides reliable
source-ordered message delivery,the Reliable Ordered
Multicast Protocol(ROMP)that provides reliable totally-
ordered message delivery,and the Processor Group Mem-
bership Protocol(PGMP)that provides processor group
membership services.
1Introduction
Fault tolerance and high availability can be provided for the
Common Object Request Broker Architecture(CORBA)
[18]by means of object replication,where the replicas of an
object form an object group.However,object replication is
of little value unless the states of the replicas of the objects
remain consistent when methods are invoked on the object
group and when faults occur.
Group communication protocols[14]can facilitate the
maintenance of strong replica consistency for CORBA
applications by multicasting request and reply messages
containing method invocations and responses,and by de-
livering the messages reliably in the same order to all of
the members of a group.Such protocols also maintain the
membership of the group.
In this paper we provide a concrete mapping of
CORBA’s Generalized Inter-ORB Protocol(GIOP)specifi-
cation onto the Fault-Tolerant Multicast Protocol(FTMP),
a multicast group communication protocol that provides
reliable totally-ordered message delivery and group mem-
bership services.
Figure2:The encapsulation of a GIOP message.
its header.RMP uses the message sequence numbers to detect missing messages from a source.If RMP detects a missing message due to a gap in the sequence numbers, it negatively acknowledges the message.The missing message can be retransmitted by any processor that has the message.
ROMP uses the message timestamps to maintain the causal and total order of messages;the message times-tamps are derived from logical Lamport clocks.Synchro-nized clocks can be used to achieve better performance. ROMP uses the acknowledgment timestamps for buffer management.The acknowledgment timestamp indicates that the sender has received all messages with lower times-tamps from all members of the processor group to which the message is addressed.
To maintain liveness of ROMP and to keep the message delivery latency low,processors must transmit messages on a regular basis.If a processor has no application message to transmit,it transmits a Heartbeat(null)message. The Heartbeat messages also monitor the liveness of the processors and serve as a processor fault detector.
Each processor can be a member of several processor groups at the same time.PGMP adds(removes)a processor to(from)a processor group,as the fault tolerance infras-tructure adds(removes)objects to(from)the object groups. The protocol removes a processor that has been convicted of being faulty from all processor groups of which it is a member.
3FTMP Messages
3.1Encapsulation of GIOP Messages CORBA’s Generalized Inter-ORB Protocol(GIOP)spec-ification defines eight message types:Request,Reply, CancelRequest,LocateRequest,LocateReply,CloseCon-nection,MessageError and Fragment.Each such message is encapsulated in a FTMP header which,in turn,is encap-sulated in an IP Multicast header,as shown in Figure2. 3.2FTMP Message Header
The format of the FTMP message header is:
magic message message source
order type processor
group number timestamp
magic is set to FTMP
FTMP
order is true for little endian and false for big endian
retransmission is false for the first transmission of a message and true for all subsequent retransmissions
message
type is one of the types defined below source id is the identifier of the processor that originated the message
destination group
number is incremented each time a mes-sage that must be reliably delivered is transmitted
message
timestamp is a positive acknowledgment time-stamp that is used for buffer management.
4FTMP Logical Connections
Just as CORBA’s Internet Inter-ORB Protocol(IIOP)main-tains a physical connection between a client object and a server object with reliable source-ordered delivery of mes-sages using TCP/IP,FTMP maintains a logical connection between a client object group and a server object group with reliable ordered delivery of messages.At most one connection is open between a client object group and a server object group at any time.Each message sent by a client(server)object group to a server(client)object group is delivered to both groups,which enables duplicate detection and suppression.
Each logical connection has an identifier that consists of the fault tolerance domain identifier and the object group identifier of the client object group,and the fault tolerance domain identifier and the object group identifier of the server object group.
The connection identifier is used in conjunction with a request number for detection of duplicate requests and duplicate replies.They are also used to match a request with its corresponding reply which is necessary,for example, when replaying messages from a log.
All of the client replicas use the same request number for a given request and all of the server replicas use the same request number for the corresponding reply. The request numbers are monotonically increasing over all connections between the two groups;therefore,each connection identifier,request number pair is unique.
Totally Message Type Ordered
Yes
No
No
No
Yes except
to client
group
Yes except
to new
member
Yes
Yes
Yes
connection request GIOP
header id message
The sequence
processor
processor id.RMP uses the sequence
timestamp in the header of a Regular mes-sage,supplied by the ROMP layer,is derived from the Lam-port clock of the source with the given source id.
The ack
processor
timestamp.
The connection num in the body of a Reg-ular message are used to detect duplicate requests,duplicate replys,etc from the different replicas of an object.The re-quest
id,and is different from the standard CORBA request
id and request
processor start stop
header id seq
The header of the RetransmitRequest message contains the same sequence number as the previous message orig-inated by the sender of the RetransmitRequest message. The message timestamp are derived from the current values provided by the ROMP layer.
The processor
retransmission of,a block of messages with consecutive
sequence numbers from that processor.Start
seq holds the largest sequence number
of that block.If only one message is missing,start
seq are equal.
Heartbeat Message.A Heartbeat message is multicast
by a processor to a destination processor group if the
processor has not multicast a Regular message to that
group within a specified period of time.The choice of
the heartbeat interval is a compromise between message
latency and network traffic.A shorter heartbeat interval
results in lower message latency but higher network traffic.
Heartbeat messages are delivered unreliably and in
source order to the ROMP layer.The purpose of a Heartbeat
message is to provide the other members of the processor
group with the sender’s current sequence number,message
timestamp and acknowledgment timestamp.Heartbeat
messages are not retransmitted,because that information
would have become obsolete by the time a Heartbeat mes-
sage could be retransmitted and that retransmitted message
could reach a receiver.
The format of the Heartbeat message is:
FTMP
header
The sequence
timestamp and ack
connection processor
header id
processor id,sequence
timestamp in the header of the ConnectRe-
quest message all have the value0,whereas the other fields
have their usual meanings and values.
The body of the ConnectRequest message contains the
connection identifier and the sequence of identifiers of the
processors that support the client object group.
Connect Message.The Connect message is used by the fault tolerance infrastructure at a server to establish a new connection between a client object group and a server object group.It can also be used to change the IP Multicast address or processor group used by an existing connection.When used to establish a new connection,the Connect message is transmitted using the IP Multicast address of the server object group’s fault tolerance domain,to which the client is listening.When used to change the IP Multicast address or processor group for an existing connection,the Con-nect message is transmitted using the current IP Multicast address and the current processor group for that connection.
The Connect message is delivered reliably and in total order.However,the client processor group cannot be guaranteed reliable delivery because the members of that group are not members of the server processor group to which the Connect message is addressed.Consequently, the server processor group retransmits the Connect message periodically using the new IP Multicast address until it receives messages over the new connection.
After transmitting or receiving a Connect message,a member of the processor group is not allowed to transmit to the group any message that must be ordered,until it
has received from every member of the processor group a message with a higher timestamp than the timestamp of the Connect message,such as a Heartbeat message.
If a Connect message is used to change the IP Multicast address or processor group of an existing connection,then a receiver ignores any message for the connection,that uses the current IP Multicast address and current processor group and that has a larger timestamp than that of the Connect message.The sender of such a message must retransmit the message using the new IP Multicast address and the new processor group.
The format of the Connect message is:
FTMP group
header id
multicast timestamp current
address membership
of membership is the times-tamp of the most recent message delivered by the processor sending the Connect message,and the cur-rent
of membership and current
timestamp
header current membership
current new
sequence member The fields of the header of the AddProcessor message are determined as for a Regular message.
The body of the AddProcessor message contains the timestamp of the current membership and the current mem-bership.It also contains the sequence number of the most recent message from each member of the current mem-bership that has been ordered by the processor originating the message.This information allows the new member to construct the message order for messages with sequence numbers higher than those cited in the message. RemoveProcessor Message.The RemoveProcessor message is used to remove a non-faulty processor from a processor group.The RemoveProcessor message is de-livered reliably and in total order.
The format of the RemoveProcessor message is: FTMP to
message
7.2Group Membership Changes for
Faulty Processors
The Suspect and Membership messages are used for pro-cessor group membership changes due to faulty processors. When the ROMP layer at a processor determines that an-other processor has crashed(because it has not received a message from that processor),it invokes PGMP to remove that processor from the processor group membership so that ROMP can order and deliver messages.The protocol then issues a fault report for the faulty processor which is conveyed to the fault tolerance infrastructure.The fault tolerance infrastructure removes the affected replicas from their object groups,and activates new or backup replicas for the object groups.
Suspect Message.The Suspect message is used to re-move a faulty processor from a processor group.Suspect messages are used in conjunction with heuristic algorithms to increase the accuracy of the processor fault detectors. The Suspect message is delivered reliably and in source order,but not in total order.
The format of the Suspect message is:
FTMP of suspects
message membership
timestamp
header current membership
current new
sequence membership The fields of the FTMP header of the Membership message are determined as for a Regular message.
The body of the Membership message contains the current processor group membership and the timestamp of the current membership.It also contains,for each processor in the current membership,the highest sequence number of any message addressed to the group,such that the processor sending the Membership message has received that message and all messages with smaller sequence numbers.In addition,it contains the proposed new membership.
The current sequence numbers allow a processor that sur-vives from the current membership to the new membership to request retransmission of any message from the current membership that it has not received,but that some other processor of that membership has received.The aim is to ensure that all of the processors in the group,that survived from the current membership to the new membership,have received exactly the same messages in the current member-ship,which is necessary to maintain virtual synchrony.
8Related Work
Over the past15years,a number of multicast group communication systems have been developed.
The Isis,Horus and Ensemble systems[3,21]provide the services of multicast,causal multicast and atomic(total order)multicast.Those systems provide increasing flex-ibility in allowing the user to choose the protocol most appropriate for the application.
The Amoeba system[10]transmits messages point-to-point to a centralized sequencer,which determines the message order and then broadcasts the messages.In other sequencer-based protocols[4,5,9],the originators of the messages broadcast their messages.
The Trans/Total system[13]comprises the Trans pro-tocol which provides a causal order on messages,and the Total algorithm which converts this causal order into a total order.The Transis system[1]is based on the Trans protocol and on the Isis application programmer interface. The Totem system[15]uses a logical token-passing ring to achieve robust operation and high performance.
While the above systems are oriented primarily towards local-area networks,more recent work has focused on the development of group communication systems that are scalable and oriented towards wide-area networks[19,20].
The Atomic Group system[11]is intended for ATM networks,and is designed to support large numbers of small groups.In contrast,the InterGroup system[2]is intended for the Internet,and is designed to support large groups.The Newtop system[7]is similar in its objectives to the InterGroup system,and supports both symmetric and asymmetric ordering protocols.
Several systems have been developed that use multicast group communication protocols to augment CORBA ap-plication objects with fault tolerance and high availability.
These systems include the Electra toolkit,implemented on top of Horus,and Orbix+Isis,implemented on top of the Isis[12].Both Electra and Orbix+Isis integrate the replication and group communication mechanisms into the ORB and require modification of the ORB.
The Eternal system[16,17]provides fault tolerance for CORBA,using the Totem system to maintain replica consistency in a manner that is transparent to the ORB. In addition to transparency to the ORB,Eternal has the objectives of transparency to the application and ease of application programming.
The Object Group Service(OGS)[8]provides object replication through a set of services implemented on top of a ORB,including a group service,a consensus service,a monitoring service and a messaging service.
The Maestro toolkit[22]adds reliability and high avail-ability to CORBA applications,particularly for unrepli-cated clients and replicated servers.The AQuA framework [6]uses the Ensemble/Maestro toolkits,as well as the Qual-ity Objects(QuO)runtime and the Proteus dependability property manager,to provide fault tolerance for CORBA. 9Conclusion
We have described the Fault-Tolerant Multicast Protocol (FTMP),a group communication protocol specifically de-signed for CORBA.The protocol consists of the Reliable Multicast Protocol(RMP)that provides reliable source-ordered multicasts,the Reliable Ordered Multicast Protocol (ROMP)that provides reliable totally-ordered multicasts, and the Processor Group Membership Protocol(PGMP) that provides processor group membership services. References
[1]Y.Amir,D.Dolev,S.Kramer and D.Malki,‘‘Transis:A
communication sub-system for high availability,’’Proceed-ings of the IEEE22nd Annual International Symposium on Fault-Tolerant Computing,Boston,MA(July1992),pp.
76-84.
[2]K.Berket,L.E.Moser and P.M.Melliar-Smith,‘‘The
InterGroup protocols:Scalable group communication for the Internet,’’Proceedings of IEEE GLOBECOM,Global Internet’98Mini-Conference Record,Sydney,Australia (November1998),pp.100-105.
[3]K.P.Birman and R.van Renesse,Reliable Distributed
Computing with the Isis Toolkit,IEEE Computer Society Press,Los Alamitos,CA,1994.
[4]J.M.Chang and N.F.Maxemchuk,‘‘Reliable broadcast
protocols,’’ACM Transactions on Computer Systems,vol.
2,no.3(August1984),pp.251-273.
[5] F.Cristian and S.Mishra,‘‘The pinwheel asynchronous
atomic broadcast protocols,’’Proceedings of the2nd Inter-national Symposium on Autonomous Decentralized Systems, Phoenix,AZ(April1995),pp.215-221.
[6]M.Cukier,J.Ren,C.Sabnis,W.H.Sanders,D.E.Bakken,
M.E.Berman,D.A.Karr and R.E.Schantz,‘‘AQuA:An adaptive architecture that provides dependable distributed objects,’’Proceedings of the IEEE17th Symposium on Reliable Distributed Systems,West Lafayette,IN(October 1998),pp.245-253.
[7]P.Ezhilchelvan,R.Macedo and S.Shrivastava,‘‘New-
top:A fault-tolerant group communication system,’’Pro-ceedings of the IEEE15th International Conference on Distributed Computer Systems,Vancouver,Canada(May 1995),pp.296-306.
[8]P.Felber,B.Garbinato and R.Guerraoui,‘‘The design of
a CORBA group communication service,’’Proceedings of
the IEEE15th Symposium on Reliable Distributed Systems, Niagra-on-the-Lake,Ontario,Canada(October1996),pp.
150-159.
[9]W.Jia,J.Kaiser and https://www.wendangku.net/doc/2b4290372.html,t,‘‘RMP:Fault-tolerant group
communication,’’IEEE Micro,vol.16,no.2(April1996), pp.59-67.
[10]M. F.Kaashoek and A.S.Tanenbaum,‘‘Group com-
munication in the Amoeba distributed operating system,’’Proceedings of the IEEE11th International Conference on Distributed Computing Systems,Arlington,TX(May 1991),pp.222-230.
[11]R.R.Koch,L.E.Moser and P.M.Melliar-Smith,‘‘The
Atomic Group protocols:Group communication protocols for ATM networks,’’in preparation.
[12]https://www.wendangku.net/doc/2b4290372.html,ndis and S.Maffeis,‘‘Building reliable distributed
systems with CORBA,’’Theory and Practice of Object Systems,vol.3,no.1(April1997),pp.31-43.
[13]P.M.Melliar-Smith,L.E.Moser and V.Agrawala,‘‘Broad-
cast protocols for distributed systems,’’IEEE Transactions on Parallel and Distributed Systems,vol.1,no.1(January 1990),pp.17-25.
[14]P.M.Melliar-Smith and L.E.Moser,‘‘Group communi-
cation,’’Encyclopedia of Electrical and Electronics En-gineering,vol.8,ed.J.G.Webster,John Wiley&Sons (February1999),pp.500-512.
[15]L.E.Moser,P.M.Melliar-Smith,D.A.Agarwal,R.K.
Budhia and C.A.Lingley-Papadopoulos,‘‘Totem:A fault-tolerant multicast group communication system,’’Commu-nications of the ACM,vol.39,no.4(April1996),pp.
54-63.
[16]L.E.Moser,P.M.Melliar-Smith and P.Narasimhan,‘‘Con-
sistent object replication in the Eternal system,’’Theory and Practice of Object Systems,vol.4,no.2(1998),pp.81-92.
[17]P.Narasimhan,L.E.Moser and P.M.Melliar-Smith,
‘‘Replica consistency of CORBA objects in partitionable distributed systems,’’Distributed Systems Engineering,vol.
4,no.3(September1997),pp.139-150.
[18]Object Management Group,The Common Object Request
Broker:Architecture and Specification,Revision2.2,OMG Technical Document formal/98-07-01(February1998). [19]L.E.T.Rodrigues,H.Fonseca and P.Verissimo,‘‘Totally
ordered multicast in large-scale systems,’’Proceedings of the IEEE16th International Conference on Distributed Computing Systems,Hong Kong(May1996),pp.500-510.
[20]T.Tachikawa,H.Higaki,M.Takizawa,M.Gerla et al,
‘‘Flexible wide-area group communication protocols--in-ternational experiments,’’Proceedings of the1998ICPP Workshop on Architectural and OS Support for Multime-dia Applications,Minneapolis,MN(August1998),pp.
105-112.
[21]R.van Renesse,K.P.Birman,M.Hayden,A.Vaysburd et
al,‘‘Building adaptive systems using Ensemble,’’Software -Practice and Experience,vol.28,no.9(July1998),pp.
963-979.
[22] A.Vaysburd and K.Birman,‘‘The Maestro approach to
building reliable interoperable distributed applications with multiple execution styles,’’Theory and Practice of Object Systems,vol.4,no.2(1998),pp.73-80.