Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!elroy.jpl.nasa.gov!decwrl!sgi!rpw3@rigden.wpd.sgi.com From: rpw3@rigden.wpd.sgi.com (Rob Warnock) Newsgroups: comp.protocols.tcp-ip Subject: Re: Reliable Broadcasts? (was Re: Reliable Datagram ??? Protocols) Message-ID: <73099@sgi.sgi.com> Date: 24 Oct 90 08:33:26 GMT References: <9010221418.AA03839@ftp.com> <60282@bbn.BBN.COM> Sender: guest@sgi.sgi.com Reply-To: rpw3@sgi.com (Rob Warnock) Organization: Silicon Graphics, Inc., Mountain View, CA Lines: 50 In article <60282@bbn.BBN.COM> craig@ws6.nnsc.nsf.net.BBN.COM (Craig Partridge) writes: +--------------- | So if you could open a TCP connection to an IP multicast address, and | figure out how to handle the remote ends cleanly at the sender, you'd be | pretty far along. (And 1 sending workstation gets, at worst, 100 | acks from 100 receivers -- less if receivers ack every 2nd segment). +--------------- XTP multicast receivers send the ACKs to the multicast address too, which allows for something the XTP spec calls "damping" (which I prefer to call "stifling"). If receiver "A" hears another receiver "B" emit an ACK with "worse" news than what "A" was going to ACK, then "A" "damps" its ACK (stifles itself, stays quiet). A helpful related feature is "slotting", wherein a receiver delays a random amount of time before sending an ACK, in the hopes that someone else will send "worse" news and it can stifle itself. Damping/slotting are optional features in XTP; with a small number of receivers, they have some negative throughput implication due to the increased delay on the ACKs and the (slightly) increased overhead of running the damping algorithm. But with very large numbers of receivers they can save a good bit of network bandwidth. What would otherwise be a large burst of ACKs (one from every station) is replaced by a much smaller flurry of ACKs, each one bearing "worse news" than its predecessor. The sender retransmits based on the "worst news" (lowest ACK number) heard during each epoch of ACK-gathering (called "buckets", in the XTP spec.) And all this works in the absence of a reliable group-membership protocol. However, in order to avoid "leaving a receiver behind", you have to extend your retransmission buffers and ensure that you get "enough" epochs of ACK-gathering (enough "buckets") so that the probability of losing "too many" consecutive ACKs from the receiver with the worst news is "as low as you like". But increasing the number of epochs per unit time increases the number of ACKs, and thus the network overhead. (*sigh*) [The tradeoffs between retransmission buffer size, ACKs per RTT, and probability of losing a receiver are discussed in detail in "Appendix B" of the "XTP Protocol Definition, Revision 3.5".] Anyway, as Vernon Schryver mentioned, it certainly *ought* to be be possible to graft the XTP/multicast "bucket algorithm" onto TCP + IP/multicast... -Rob ----- Rob Warnock, MS-9U/510 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311