Warning:
JavaScript is turned OFF. None of the links on this page will work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: ch 12, Open and closed groups Closed groups only members can send to group, a member delivers to itself they are useful for coordination of groups of cooperating servers Open they are useful for notification of events to groups of interested processes also Reliability of one-to-one communication The term reliable 1-1 communication is defined in terms of validity and integrity as follows: validity: any message in the outgoing message buffer is eventually delivered to the incoming message buffer; integrity: the message received is identical to one sent, and no messages are delivered twice., Introduction to multicast Multicast communication requires coordination and agreement. The aim is for members of a group to receive copies of messages sent to the group Many different delivery guarantees are possible e.g. agree on the set of messages received or on delivery ordering A process can multicast by the use of a single operation instead of a send to each member For example in IP multicast aSocket.send(aMessage) The single operation allows for: efficiency I.e. send once on each link, using hardware multicast when available, e.g. multicast from a computer in London to two in Beijing delivery guarantees e.g. can’t make a guarantee if multicast is implemented as multiple sends and the sender fails. Can also do ordering System Model System model The system consists of a collection of processes which can communicate reliably over 1-1 channels Processes fail only by crashing (no arbitrary failures) Processes are members of groups - which are the destinations of multicast messages In general process p can belong to more than one group Operations multicast(g, m) sends message m to all members of process group g deliver (m) is called to get a multicast message delivered. It is different from receive as it may be delayed to allow for ordering or reliability. Multicast message m carries the id of the sending process sender(m) and the id of the destination group group(m) We assume there is no falsification of the origin and destination of messages, A correct process will eventually deliver the message provided the multicaster does not crash note that IP multicast does not give this guarantee The primitives are called B-multicast and B-deliver A straightforward but ineffective method of implementation: use a reliable 1-1 send (i.e. with integrity and validity as above) To B-multicast(g,m): for each process p e g, send(p, m); On receive (m) at p: B-deliver (m) at p Problem if the number of processes is large, the protocol will suffer from ack-implosion Implement Implementation of basic multicast over IP Each process p maintains: a sequence number, Spg for each group it belongs to and Rqg, the sequence number of the latest message it has delivered from process q For process p to B-multicast a message m to group g it piggybacks Sgp on the message m, using IP multicast to send it the piggybacked sequence numbers allow recipients to learn about messages they have not received On receive (g,m, S) at p: if S = Rqg +1 B-deliver (m) and increment Rqg by 1 if S < Rqg +1 reject the message because it has been delivered before if S > Rqg +1 note that a message is missing, request missing message from sender. (will use a hold-back queue to be discussed later on) If the sender crashes, then a message may be delivered to some members of the group but not others., System model The system consists of a collection of processes which can communicate reliably over 1-1 channels Processes fail only by crashing (no arbitrary failures) Processes are members of groups - which are the destinations of multicast messages In general process p can belong to more than one group Operations multicast(g, m) sends message m to all members of process group g deliver (m) is called to get a multicast message delivered. It is different from receive as it may be delayed to allow for ordering or reliability. Multicast message m carries the id of the sending process sender(m) and the id of the destination group group(m) We assume there is no falsification of the origin and destination of messages and Open and closed groups Closed groups only members can send to group, a member delivers to itself they are useful for coordination of groups of cooperating servers Open they are useful for notification of events to groups of interested processes, IP multicast – an implementation of group communication built on top of IP (note IP packets are addressed to computers) allows the sender to transmit a single IP packet to a set of computers that form a multicast group (a class D internet address with first 4 bits 1110) Dynamic membership of groups. Can send to a group with or without joining it To multicast, send a UDP datagram with a multicast address To join, make a socket join a group (s.joinGroup(group) - Fig 4.17) enabling it to receive messages from the group Multicast routers Local messages use local multicast capability. Routers make it efficient by choosing other routers on the way. Failure model Omission failures some but not all members may receive a message. e.g. a recipient may drop message, or a multicast router may fail IP packets may not arrive in sender order, group members can receive messages in different orders and Introduction to multicast Multicast communication requires coordination and agreement. The aim is for members of a group to receive copies of messages sent to the group Many different delivery guarantees are possible e.g. agree on the set of messages received or on delivery ordering A process can multicast by the use of a single operation instead of a send to each member For example in IP multicast aSocket.send(aMessage) The single operation allows for: efficiency I.e. send once on each link, using hardware multicast when available, e.g. multicast from a computer in London to two in Beijing delivery guarantees e.g. can’t make a guarantee if multicast is implemented as multiple sends and the sender fails. Can also do ordering, Reliability properties of reliable multicast over IP Integrity - duplicate messages detected and rejected. IP multicast uses checksums to reject corrupt messages Validity - due to IP multicast in which sender delivers to itself Agreement - processes can detect missing messages. They must keep copies of messages they have delivered so that they can re-transmit them to others. discarding of copies of messages that are no longer needed : when piggybacked acknowledgements arrive, note which processes have received messages. When all processes in g have the message, discard it. problem of a process that stops sending - use ‘heartbeat’ messages. This protocol has been implemented in a practical way in Psynch and Trans (refs. on p442) and Ordered multicast The basic multicast algorithm delivers messages to processes in an arbitrary order. A variety of orderings may be implemented: FIFO ordering If a correct process issues multicast(g, m) and then multicast(g,m’ ), then every correct process that delivers m’ will deliver m before m’ . Causal ordering If multicast(g, m) multicast(g,m’ ), where is the happened-before relation between messages in group g, then any correct process that delivers m’ will deliver m before m’ . Total ordering If a correct process delivers message m before it delivers m’, then any other correct process that delivers m’ will deliver m before m’. Ordering is expensive in delivery latency and bandwidth consumption, A correct process will eventually deliver the message provided the multicaster does not crash note that IP multicast does not give this guarantee The primitives are called B-multicast and B-deliver A straightforward but ineffective method of implementation: use a reliable 1-1 send (i.e. with integrity and validity as above) To B-multicast(g,m): for each process p e g, send(p, m); On receive (m) at p: B-deliver (m) at p Problem if the number of processes is large, the protocol will suffer from ack-implosion Implement The hold-back queue for arriving multicast messages The hold back queue is not necessary for reliability as in the implementation using IP muilticast, but it simplifies the protocol, allowing sequence numbers to represent sets of messages. Hold-back queues are also used for ordering protocols., Reliability of one-to-one communication The term reliable 1-1 communication is defined in terms of validity and integrity as follows: validity: any message in the outgoing message buffer is eventually delivered to the incoming message buffer; integrity: the message received is identical to one sent, and no messages are delivered twice. and A correct process will eventually deliver the message provided the multicaster does not crash note that IP multicast does not give this guarantee The primitives are called B-multicast and B-deliver A straightforward but ineffective method of implementation: use a reliable 1-1 send (i.e. with integrity and validity as above) To B-multicast(g,m): for each process p e g, send(p, m); On receive (m) at p: B-deliver (m) at p Problem if the number of processes is large, the protocol will suffer from ack-implosion