From owner-rmt@listserv.lbl.gov Thu Aug 3 10:09:03 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA11072 for ; Thu, 3 Aug 2000 10:09:02 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id FAA07057; Thu, 3 Aug 2000 05:36:08 -0700 (PDT) Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id FAA07053 for ; Thu, 3 Aug 2000 05:36:06 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id FAA12497 for ; Thu, 3 Aug 2000 05:36:05 -0700 (PDT) Received: from violin.dcs.uky.edu (violin.dcs.uky.edu [204.198.75.11]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id FAA12494 for ; Thu, 3 Aug 2000 05:36:04 -0700 (PDT) Received: from gladstone.dcs.uky.edu (gladstone.dcs.uky.edu [204.198.75.142]) by violin.dcs.uky.edu (8.9.1a/8.9.1) with ESMTP id IAA00659; Thu, 3 Aug 2000 08:36:02 -0400 (EDT) Received: from localhost (calvert@localhost) by gladstone.dcs.uky.edu (8.9.1a/8.9.1) with ESMTP id IAA16386; Thu, 3 Aug 2000 08:36:02 -0400 (EDT) X-Authentication-Warning: gladstone.dcs.uky.edu: calvert owned process doing -bs Date: Thu, 3 Aug 2000 08:36:02 -0400 (EDT) From: Ken Calvert To: rmt@lbl.gov cc: griff@dcs.uky.edu Subject: concast Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-rmt@lbl.gov Precedence: bulk [I sent a similar message to the rm list earlier in the week, but it appears not to have made it out.] Folks, We'd like to call your attention to draft-calvert-concast-svc-00.txt, which describes the concast many-to-one service. After looking over the current drafts and hearing the presentations earlier this week, it appears that Concast would make a good RM building block. It is useful for aggregation of feedback, both ack/nack and congestion-related. We'd appreciate any comments. The draft describes the service independent of RM, because it is also useful outside the context of multicast. Cheers, KC -- Ken Calvert calvert@dcs.uky.edu Associate Professor ***************NOTE NEW AREA CODE = 859 Computer Science, 773 Anderson Hall +1.859.257.6745 University of Kentucky Fax: +1.859.323.1971 Lexington, KY 40506-0046 http://www.cs.uky.edu/~calvert/ From owner-rmt@listserv.lbl.gov Thu Aug 3 12:04:07 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA00635 for ; Thu, 3 Aug 2000 12:04:06 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id HAA08106; Thu, 3 Aug 2000 07:40:59 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA08102 for ; Thu, 3 Aug 2000 07:40:57 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA27850 for ; Thu, 3 Aug 2000 07:40:56 -0700 (PDT) Received: from nilla.aciri.org (wireless-132-79.ietf.marconi.com [147.73.132.79]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA27835 for ; Thu, 3 Aug 2000 07:40:55 -0700 (PDT) Received: from nilla.aciri.org (localhost [127.0.0.1]) by nilla.aciri.org (8.9.3/8.9.3) with ESMTP id IAA01451; Thu, 3 Aug 2000 08:10:40 -0700 (PDT) (envelope-from mjh@nilla.aciri.org) Message-Id: <200008031510.IAA01451@nilla.aciri.org> From: Mark Handley X-Organisation: ACIRI To: Ken Calvert cc: rmt@lbl.gov Subject: Re: concast In-reply-to: Your message of "Thu, 03 Aug 2000 08:36:02 EDT." Date: Thu, 03 Aug 2000 08:10:40 -0700 Sender: owner-rmt@lbl.gov Precedence: bulk >[I sent a similar message to the rm list earlier in the week, but it >appears not to have made it out.] I received it. If anyone is on both lists, and didn't get both copies, please let me know, so I can figure out if there's a problem with the mail server that handles the rm list. Cheers, Mark From owner-rmt@listserv.lbl.gov Thu Aug 3 13:41:25 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA06221 for ; Thu, 3 Aug 2000 13:41:24 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id JAA08936; Thu, 3 Aug 2000 09:34:49 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA08932 for ; Thu, 3 Aug 2000 09:34:47 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA28496 for ; Thu, 3 Aug 2000 09:34:46 -0700 (PDT) Received: from omega.cisco.com (omega.cisco.com [171.69.63.141]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA28491 for ; Thu, 3 Aug 2000 09:34:46 -0700 (PDT) Received: from localhost (lorenzo@localhost) by omega.cisco.com (8.8.8-Cisco List Logging/8.8.8) with ESMTP id JAA26174; Thu, 3 Aug 2000 09:33:46 -0700 (PDT) Message-Id: <200008031633.JAA26174@omega.cisco.com> To: Ken Calvert cc: rmt@lbl.gov Subject: Re: concast In-Reply-To: Your message of "Thu, 03 Aug 2000 08:36:02 EDT." Date: Thu, 03 Aug 2000 09:33:46 -0700 From: Lorenzo Vicisano Sender: owner-rmt@lbl.gov Precedence: bulk Ken, Your work seems to be very relevant to the chater of this WG in the context of GRA (see draft-ietf-rmt-gra-arch-01.txt). You might want to contact the authors of this draft and see if you can coordinate your effort with theirs. cheers, Lorenzo > We'd like to call your attention to draft-calvert-concast-svc-00.txt, > which describes the concast many-to-one service. After looking over the > current drafts and hearing the presentations earlier this week, it appears > that Concast would make a good RM building block. It is useful for > aggregation of feedback, both ack/nack and congestion-related. > > We'd appreciate any comments. The draft describes the service independent > of RM, because it is also useful outside the context of multicast. > > Cheers, > > KC > -- > Ken Calvert calvert@dcs.uky.edu > Associate Professor ***************NOTE NEW AREA CODE = 859 > Computer Science, 773 Anderson Hall +1.859.257.6745 > University of Kentucky Fax: +1.859.323.1971 > Lexington, KY 40506-0046 http://www.cs.uky.edu/~calvert/ > > From owner-rmt@listserv.lbl.gov Fri Aug 11 07:55:37 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA10448 for ; Fri, 11 Aug 2000 07:55:37 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id EAA02848; Fri, 11 Aug 2000 04:02:05 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA02840 for ; Fri, 11 Aug 2000 04:02:02 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA23092 for ; Fri, 11 Aug 2000 04:02:01 -0700 (PDT) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA23087 for ; Fri, 11 Aug 2000 04:02:00 -0700 (PDT) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA08886; Fri, 11 Aug 2000 07:01:59 -0400 (EDT) Message-Id: <200008111101.HAA08886@ietf.org> Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; Cc: rmt@lbl.gov From: Internet-Drafts@ietf.org Reply-to: Internet-Drafts@ietf.org Subject: I-D ACTION:draft-ietf-rmt-norm-bb-00.txt Date: Fri, 11 Aug 2000 07:01:58 -0400 Sender: owner-rmt@lbl.gov Precedence: bulk --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the Reliable Multicast Transport Working Group of the IETF. Title : NACK-Oriented Reliable Multicast (NORM) Protocol Building Blocks Author(s) : B. Adamson, C. Bormann, S. Floyd, M. Handley, J. Macker Filename : draft-ietf-rmt-norm-bb-00.txt Pages : 25 Date : 10-Aug-00 This memo describes issues related to the creation of negative- acknowledgment (NACK) oriented reliable multicast (NORM) protocols. The general goals and assumptions for NORM are defined. The tech- nical challenges related to NACK-oriented (and in some cases gen- eral) reliable multicast protocol design are identified. These challenges are resolved into a set of applicable 'building blocks' which are described in further detail. It is anticipated that these building blocks (as they are further refined and defined in future revisions of this document) will be useful in generating different instantiations of reliable multicast protocols. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-norm-bb-00.txt Internet-Drafts are also available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-rmt-norm-bb-00.txt". A list of Internet-Drafts directories can be found in http://www.ietf.org/shadow.html or ftp://ftp.ietf.org/ietf/1shadow-sites.txt Internet-Drafts can also be obtained by e-mail. Send a message to: mailserv@ietf.org. In the body type: "FILE /internet-drafts/draft-ietf-rmt-norm-bb-00.txt". NOTE: The mail server at ietf.org can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e. documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ietf.org" Content-Type: text/plain Content-ID: <20000810140221.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-norm-bb-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-norm-bb-00.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000810140221.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Fri Aug 11 11:03:07 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA21328 for ; Fri, 11 Aug 2000 11:03:05 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id HAA29896; Fri, 11 Aug 2000 07:05:28 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA29842 for ; Fri, 11 Aug 2000 07:05:24 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA07501 for ; Fri, 11 Aug 2000 07:05:23 -0700 (PDT) Received: from picard.noroff.no ([212.20.204.3]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA07491 for ; Fri, 11 Aug 2000 07:05:22 -0700 (PDT) Received: by picard.noroff.no (Postfix, from userid 815) id 1376122002; Fri, 11 Aug 2000 16:49:40 +0200 (CEST) Received: from loki.ietf.org (loki.ietf.org [132.151.1.177]) by picard.noroff.no (Postfix) with ESMTP id BCECAB3802 for ; Fri, 11 Aug 2000 16:49:37 +0200 (CEST) Received: (from adm@localhost) by loki.ietf.org (8.9.1b+Sun/8.9.1) id JAA11482 for ietf-123-outbound.09@ietf.org; Fri, 11 Aug 2000 09:25:01 -0400 (EDT) Received: from ietf.org (odin.ietf.org [10.27.2.28]) by loki.ietf.org (8.9.1b+Sun/8.9.1) with ESMTP id HAA10105 for ; Fri, 11 Aug 2000 07:01:59 -0400 (EDT) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA08886; Fri, 11 Aug 2000 07:01:59 -0400 (EDT) Message-Id: <200008111101.HAA08886@ietf.org> Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; Cc: rmt@lbl.gov From: Internet-Drafts@ietf.org Reply-To: Internet-Drafts@ietf.org Subject: I-D ACTION:draft-ietf-rmt-norm-bb-00.txt Date: Fri, 11 Aug 2000 07:01:58 -0400 X-AntiVirus: scanned for viruses by Amavis 0.2.1-pre2 Sender: owner-rmt@lbl.gov Precedence: bulk --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the Reliable Multicast Transport Working Group of the IETF. Title : NACK-Oriented Reliable Multicast (NORM) Protocol Building Blocks Author(s) : B. Adamson, C. Bormann, S. Floyd, M. Handley, J. Macker Filename : draft-ietf-rmt-norm-bb-00.txt Pages : 25 Date : 10-Aug-00 This memo describes issues related to the creation of negative- acknowledgment (NACK) oriented reliable multicast (NORM) protocols. The general goals and assumptions for NORM are defined. The tech- nical challenges related to NACK-oriented (and in some cases gen- eral) reliable multicast protocol design are identified. These challenges are resolved into a set of applicable 'building blocks' which are described in further detail. It is anticipated that these building blocks (as they are further refined and defined in future revisions of this document) will be useful in generating different instantiations of reliable multicast protocols. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-norm-bb-00.txt Internet-Drafts are also available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-rmt-norm-bb-00.txt". A list of Internet-Drafts directories can be found in http://www.ietf.org/shadow.html or ftp://ftp.ietf.org/ietf/1shadow-sites.txt Internet-Drafts can also be obtained by e-mail. Send a message to: mailserv@ietf.org. In the body type: "FILE /internet-drafts/draft-ietf-rmt-norm-bb-00.txt". NOTE: The mail server at ietf.org can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e. documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ietf.org" Content-Type: text/plain Content-ID: <20000810140221.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-norm-bb-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-norm-bb-00.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000810140221.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Tue Aug 15 22:06:53 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id WAA03739 for ; Tue, 15 Aug 2000 22:06:53 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id RAA24015; Tue, 15 Aug 2000 17:42:34 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA24011 for ; Tue, 15 Aug 2000 17:42:28 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA09591 for ; Tue, 15 Aug 2000 17:42:27 -0700 (PDT) Received: from tech.cisco.com (tech.cisco.com [161.44.224.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA09588 for ; Tue, 15 Aug 2000 17:42:27 -0700 (PDT) Received: from ORANLT ([171.71.147.155]) by tech.cisco.com (Netscape Messaging Server 3.61) with SMTP id AAA5CAB for ; Tue, 15 Aug 2000 20:42:42 -0400 From: "Dave Oran" To: Subject: FW: Adding reliable transport layer above sgm/xcsat Date: Tue, 15 Aug 2000 20:41:54 -0400 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit -----Original Message----- From: owner-xcast@public.alcatel.com [mailto:owner-xcast@public.alcatel.com]On Behalf Of Tal Anker Sent: Tuesday, August 15, 2000 7:27 AM To: xcast@public.alcatel.com Cc: dolev@cs.huji.ac.il Subject: Adding reliable transport layer above sgm/xcsat Hi, We would like to share some thoughts on the benefit from the xcast model (or sgm) to small group multicast applications. In particular, we have been playing with reliable multicast transport layers in the last few years. A reliable transport for small group multicast may not be important for video conference application, but for other collaborative application such as shared editor or shared drawing board (whiteboard) it may be very usefull. Since the reliable multicast working group concentrate (for now) on one-to-many within the SSM architecture, this issue may fit to this working group. To trigger a discussion, we have comprised a list of issues that come up when implementing reliale transport layer for multicast: 1) Fault detection - in xcast this is pretty simple to handle. In large groups, the need to probe for liveness of every member is a problem for the scalability proporty. In xcast, it becomes much simple to handle. For instance every source can "ping" the liveness of all the receivers in the members list, which leads us to the next item: 2) Dynamic Group Membership - In xcast every source is requested to know the members list apriori. In general, learning the potential group of members is a chalange. Special challange is the aggreement on the "view" of the group - i.e., aggreement on the active members list. In xcast, leader based or token based algorithms can be easily used. 3) Messages ordering - This is a problem that was discussed in various forums and communities. Ordering is an important property for various applications, such as distributed database applications or shared whiteboards, etc. Typicall applications in xcast may not require a full fledge database consistency requirements, but will certainly benefit from various ordering properties. In particular, consider a shared editor or whiteboard that a small group of participants use. Consider scenarios where someone deletes an object fron the drawing board, and another is moving the object around. An ordering property (such as Total ordering) can resolve these conflicts relatiely easily. We think that the xcast model alleviates the deployments of ordering algorithms. For instance, logical "token based" algorithms or leader based algorithms are very feasible for implementation in the xcast model. 4) Buffering messages for retransmissions: When the group is small, there is no real prolem in "saving" messages for later retransmissions. This may not be nessary for video conferencing, but wheh the conference is coupled with shared text editor or shared drawing board, the two latter applications are sure to benefit from this kind of reliability. 5) Flow control for small group multicast: We think that flow control for small groups is a much easier problem to solve. For instance, one can even think on maintaining a sliding window per receiver (from the source point of view). 6) Handling leave/join of members: When a new member joins the group, the fact that the group is of small size makes it easier to build a "digest" of the group state and transferring this digest to the newcomer. The convergence of the group membership changes is much faster. 7) handling network partitions/merges: In case there is a link that has failed, some of the group members may be temporary partitioned. This calls for the reliability layer to adapt to such cases, and do not try and attempt recovering/retransmitting messages that were sent within each partition. This is a sort of a "can of worms" and is heavily discusses within the area of Group Communication Systems. We suggest to put it away at this time. In any case, in small groups there is a high chance that a sort of temporary "relays" can be constructed within the period of partition. These relays are point-to-point communication channels that can bridge accross partiotions (given that logical transitivity exist). Comments? opinions? anything :) ? Danny & Tal ===================================== Institute of Computer Science The Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904 Israel From owner-rmt@listserv.lbl.gov Tue Aug 15 22:15:51 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id WAA03896 for ; Tue, 15 Aug 2000 22:15:51 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id SAA24053; Tue, 15 Aug 2000 18:13:47 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id SAA24049 for ; Tue, 15 Aug 2000 18:13:45 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id SAA14098 for ; Tue, 15 Aug 2000 18:13:45 -0700 (PDT) Received: from aardvark.aciri.org (aardvark.aciri.org [192.150.187.20]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id SAA14095 for ; Tue, 15 Aug 2000 18:13:45 -0700 (PDT) Received: from aardvark.aciri.org (localhost [127.0.0.1]) by aardvark.aciri.org (8.9.3/8.9.3) with ESMTP id SAA46797; Tue, 15 Aug 2000 18:13:38 -0700 (PDT) (envelope-from mjh@aardvark.aciri.org) From: Mark Handley X-Organisation: ACIRI To: "Dave Oran" cc: rmt@lbl.gov Subject: Re: FW: Adding reliable transport layer above sgm/xcsat In-reply-to: Your message of "Tue, 15 Aug 2000 20:41:54 EDT." Date: Tue, 15 Aug 2000 18:13:38 -0700 Message-ID: <46795.966388418@aardvark.aciri.org> Sender: owner-rmt@lbl.gov Precedence: bulk The advantages they state seem to apply to any small group, whether based on SGM, Internet Standard multicast or SSM. I don't see how SGM helps. Also not all RM protocols need to know who the receivers are. (e.g. digital fountain approaches don't care who the receivers are) Requiring the sender to know who the receivers are is therefore an impediment, not an advantage. The advantages of SGM (if any) do not seem to be at the transport/application layer to me. The one exception might be the very limited security gain you get by having slightly more control over who receives the traffic. However IMHO such security gain is a poor substitute for decent encryption. Cheers, Mark >-----Original Message----- >From: owner-xcast@public.alcatel.com >[mailto:owner-xcast@public.alcatel.com]On Behalf Of Tal Anker >Sent: Tuesday, August 15, 2000 7:27 AM >To: xcast@public.alcatel.com >Cc: dolev@cs.huji.ac.il >Subject: Adding reliable transport layer above sgm/xcsat > > > >Hi, > >We would like to share some thoughts on the benefit from the xcast >model (or sgm) to small group multicast applications. In particular, >we have been playing with reliable multicast transport layers in the >last few years. A reliable transport for small group multicast may not >be important for video conference application, but for other >collaborative application such as shared editor or shared drawing >board (whiteboard) it may be very usefull. Since the reliable >multicast working group concentrate (for now) on one-to-many within >the SSM architecture, this issue may fit to this >working group. > >To trigger a discussion, we have comprised a list of issues that come up >when implementing reliale transport layer for multicast: > >1) Fault detection - in xcast this is pretty simple to handle. In >large groups, the need to probe for liveness of every member is a >problem for the scalability proporty. In xcast, it becomes much simple >to handle. For instance every source can "ping" the liveness of all >the receivers in the members list, which leads us to the next item: > >2) Dynamic Group Membership - In xcast every source is requested to >know the members list apriori. In general, learning the potential >group of members is a chalange. Special challange is the aggreement on >the "view" of the group - i.e., aggreement on the active members list. >In xcast, leader based or token based algorithms can be easily used. > >3) Messages ordering - This is a problem that was discussed in various >forums and communities. Ordering is an important property for various >applications, such as distributed database applications or shared >whiteboards, etc. Typicall applications in xcast may not require a >full fledge database consistency requirements, but will certainly >benefit from various ordering properties. In particular, consider a >shared editor or whiteboard that a small group of participants >use. Consider scenarios where someone deletes an object fron the >drawing board, and another is moving the object around. An ordering >property (such as Total ordering) can resolve these conflicts >relatiely easily. We think that the xcast model alleviates the >deployments of ordering algorithms. For instance, logical "token based" >algorithms or leader based algorithms are very feasible for >implementation in the xcast model. > >4) Buffering messages for retransmissions: When the group is small, >there is no real prolem in "saving" messages for later >retransmissions. This may not be nessary for video conferencing, but >wheh the conference is coupled with shared text editor or shared >drawing board, the two latter applications are sure to benefit from >this kind of reliability. > >5) Flow control for small group multicast: We think that flow control >for small groups is a much easier problem to solve. For instance, one >can even think on maintaining a sliding window per receiver (from the >source point of view). > >6) Handling leave/join of members: When a new member joins the group, >the fact that the group is of small size makes it easier to build a >"digest" of the group state and transferring this digest to the >newcomer. The convergence of the group membership changes is much >faster. > >7) handling network partitions/merges: In case there is a link that >has failed, some of the group members may be temporary >partitioned. This calls for the reliability layer to adapt to such >cases, and do not try and attempt recovering/retransmitting messages >that were sent within each partition. This is a sort of a "can of >worms" and is heavily discusses within the area of Group Communication >Systems. We suggest to put it away at this time. In any case, in small >groups there is a high chance that a sort of temporary "relays" can be >constructed within the period of partition. These relays are >point-to-point communication channels that can bridge accross >partiotions (given that logical transitivity exist). > >Comments? opinions? anything :) ? > >Danny & Tal > >===================================== >Institute of Computer Science >The Hebrew University of Jerusalem, >Givat Ram, Jerusalem 91904 >Israel > > From owner-rmt@listserv.lbl.gov Wed Aug 16 05:24:29 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA20482 for ; Wed, 16 Aug 2000 05:24:29 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id BAA24726; Wed, 16 Aug 2000 01:18:15 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA24722 for ; Wed, 16 Aug 2000 01:18:14 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA16839 for ; Wed, 16 Aug 2000 01:18:13 -0700 (PDT) Received: from cs.huji.ac.il (cs.huji.ac.il [132.65.16.10]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA16831 for ; Wed, 16 Aug 2000 01:18:07 -0700 (PDT) Received: from haserver.cs.huji.ac.il ([132.65.200.200] ident=exim) by cs.huji.ac.il with esmtp (Exim 3.15 #1) id 13OyOY-0004ME-00; Wed, 16 Aug 2000 11:17:54 +0300 Received: from anker by haserver.cs.huji.ac.il with local (Exim 3.15 #1) id 13OyOX-0001fM-00; Wed, 16 Aug 2000 11:17:53 +0300 Date: Wed, 16 Aug 2000 11:17:53 +0300 (IDT) From: Tal Anker To: Mark Handley cc: Dave Oran , rmt@lbl.gov, xcast@public.alcatel.com, dolev@cs.huji.ac.il Subject: Re: FW: Adding reliable transport layer above sgm/xcsat In-Reply-To: <46795.966388418@aardvark.aciri.org> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-rmt@lbl.gov Precedence: bulk On Tue, 15 Aug 2000, Mark Handley wrote: > > The advantages they state seem to apply to any small group, whether > based on SGM, Internet Standard multicast or SSM.I don't see how SGM > helps. That is almost correct with one thing different (you already said it bellow): there is more control on who are the receivers that receives the traffic. There are many reliable multicast "flavors", and to some of them the membership (of receivers and sources) is important. When the membership is known, it is much easier to give stronger semantics to the user application, e.g., to guarantee that ALL the messages will be delivered to ALL the alive receivers. This is obviously requires failure detector (in the transport layer) in order to declare a receiver "faulty" and thus enable the progression within the group (otherwise, the source might get stuck and wait for acks from a faulty receiver). These kind of protocols make it easier to build shared whiteboard/editor, where the consistency of the object that is shared is important. - Tal. > > Also not all RM protocols need to know who the receivers are. > (e.g. digital fountain approaches don't care who the receivers are) > Requiring the sender to know who the receivers are is therefore an > impediment, not an advantage. > > The advantages of SGM (if any) do not seem to be at the > transport/application layer to me.The one exception might be the > very limited security gain you get by having slightly more control > over who receives the traffic.However IMHO such security gain is a > poor substitute for decent encryption. > > Cheers, > Mark > > > From owner-rmt@listserv.lbl.gov Thu Aug 17 14:33:45 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA02302 for ; Thu, 17 Aug 2000 14:33:44 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id KAA03017; Thu, 17 Aug 2000 10:14:58 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA03013 for ; Thu, 17 Aug 2000 10:14:56 -0700 (PDT) From: announce@leisurewebcams.com Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA12493 for ; Thu, 17 Aug 2000 10:14:54 -0700 (PDT) Received: from mail.yourdomain.com (m319-mp1-cvx1a.man.ntl.com [62.252.197.63]) by SpamWall.lbl.gov (8.9.3/8.9.3) with SMTP id KAA12468 for ; Thu, 17 Aug 2000 10:14:51 -0700 (PDT) Message-Id: <200008171714.KAA12468@SpamWall.lbl.gov> Date: Thu, 17 Aug 2000 14:39:06 To: Subject: LeisureWebcams.com - See the World Sender: owner-rmt@lbl.gov Precedence: bulk LeisureWebcams.com is a recently launched website specialising in providing free LIVE access to over 1,500 webcams and 2,000 Tourist Offices world wide. Check it out:- http://www.leisurewebcams.com/ This offers you the chance to check out live and frequently updated images of your chosen location through the webcams and get detailed local knowledge through the Tourist Offices. Along with booking holidays direct through our travel partner, there is the opportunity to sell your unwanted clothes and equipment through our free Swap Shop. There is a lot to see, so if you have enjoyed your trip through our site, do tell your friends and let us know through 'Your Views'. If you have any suggestions for the site, or queries, please feel free to contact me at cy@LeisureWebcams.com. I look forward to hearing from you. Kind regards, Charlie Yates MARKETING DIRECTOR LeisureWebcams.com From owner-rmt@listserv.lbl.gov Fri Aug 18 13:40:44 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA03359 for ; Fri, 18 Aug 2000 13:40:44 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id JAA18194; Fri, 18 Aug 2000 09:37:14 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA18190 for ; Fri, 18 Aug 2000 09:37:12 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA25942 for ; Fri, 18 Aug 2000 09:37:11 -0700 (PDT) Received: from boreas.isi.edu (boreas.isi.edu [128.9.160.161]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id JAA25937 for ; Fri, 18 Aug 2000 09:37:11 -0700 (PDT) Received: from ISI.EDU (jet.isi.edu [128.9.160.87]) by boreas.isi.edu (8.9.3/8.9.3) with ESMTP id JAA25974; Fri, 18 Aug 2000 09:37:07 -0700 (PDT) Message-Id: <200008181637.JAA25974@boreas.isi.edu> To: IETF-Announce: ; Subject: RFC 2887 on Multicast Design Space for Bulk Data Transfer Cc: rfc-ed@ISI.EDU, rmt@lbl.gov Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary=NextPart Date: Fri, 18 Aug 2000 09:37:07 -0700 From: RFC Editor Sender: owner-rmt@lbl.gov Precedence: bulk --NextPart A new Request for Comments is now available in online RFC libraries. RFC 2887 Title: The Reliable Multicast Design Space for Bulk Data Transfer Author(s): M. Handley, S. Floyd, B. Whetten, R. Kermode, L. Vicisano, M. Luby Status: Informational Date: August 2000 Mailbox: mjh@aciri.org, floyd@aciri.org, whetten@talarian.com, Roger.Kermode@motorola.com, lorenzo@cisco.com, luby@digitalfountain.com Pages: 22 Characters: 51135 Updates/Obsoletes/SeeAlso: None I-D Tag: draft-ietf-rmt-design-space-01.txt URL: ftp://ftp.isi.edu/in-notes/rfc2887.txt The design space for reliable multicast is rich, with many possible solutions having been devised. However, application requirements serve to constrain this design space to a relatively small solution space. This document provides an overview of the design space and the ways in which application constraints affect possible solutions. This document is a product of the Reliable Multicast Transport Working Group of the IETF. This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. This announcement is sent to the IETF list and the RFC-DIST list. Requests to be added to or deleted from the IETF distribution list should be sent to IETF-REQUEST@IETF.ORG. Requests to be added to or deleted from the RFC-DIST distribution list should be sent to RFC-DIST-REQUEST@RFC-EDITOR.ORG. Details on obtaining RFCs via FTP or EMAIL may be obtained by sending an EMAIL message to rfc-info@RFC-EDITOR.ORG with the message body help: ways_to_get_rfcs. For example: To: rfc-info@RFC-EDITOR.ORG Subject: getting rfcs help: ways_to_get_rfcs Requests for special distribution should be addressed to either the author of the RFC in question, or to RFC-Manager@RFC-EDITOR.ORG. Unless specifically noted otherwise on the RFC itself, all RFCs are for unlimited distribution.echo Submissions for Requests for Comments should be sent to RFC-EDITOR@RFC-EDITOR.ORG. Please consult RFC 2223, Instructions to RFC Authors, for further information. Joyce K. Reynolds and Sandy Ginoza USC/Information Sciences Institute ... Below is the data which will enable a MIME compliant Mail Reader implementation to automatically retrieve the ASCII version of the RFCs. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="RFC-INFO@RFC-EDITOR.ORG" Content-Type: text/plain Content-ID: <000818093455.RFC@RFC-EDITOR.ORG> RETRIEVE: rfc DOC-ID: rfc2887 --OtherAccess Content-Type: Message/External-body; name="rfc2887.txt"; site="ftp.isi.edu"; access-type="anon-ftp"; directory="in-notes" Content-Type: text/plain Content-ID: <000818093455.RFC@RFC-EDITOR.ORG> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Tue Aug 22 08:34:13 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id IAA03395 for ; Tue, 22 Aug 2000 08:34:12 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id EAA04811; Tue, 22 Aug 2000 04:31:17 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA04807 for ; Tue, 22 Aug 2000 04:31:15 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA29513 for ; Tue, 22 Aug 2000 04:31:14 -0700 (PDT) Received: from motgate2.mot.com (motgate2.mot.com [136.182.1.10]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA29510 for ; Tue, 22 Aug 2000 04:31:13 -0700 (PDT) Received: [from pobox3.mot.com ([10.64.251.242]) by motgate2.mot.com (motgate2 2.1) with ESMTP id EAA15759 for ; Tue, 22 Aug 2000 04:31:12 -0700 (MST)] Received: [from homer.arc.corp.mot.com (homer.arc.corp.mot.com [217.1.10.38]) by pobox3.mot.com (MOT-pobox3 2.0) with ESMTP id EAA03759 for ; Tue, 22 Aug 2000 04:30:18 -0700 (MST)] Received: from arc.corp.mot.com ([217.2.31.199]) by homer.arc.corp.mot.com (8.10.2/8.10.2) with ESMTP id e7MBV8s23311 for ; Tue, 22 Aug 2000 21:31:09 +1000 (EST) Message-ID: <39A26474.7623C9D2@arc.corp.mot.com> Date: Tue, 22 Aug 2000 21:31:00 +1000 From: Roger Kermode Reply-To: Roger.Kermode@motorola.com Organization: Motorola X-Mailer: Mozilla 4.73 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 To: rmt-list Subject: RMT Slides... Content-Type: multipart/mixed; boundary="------------DCD90943EAD0A24B08893E73" Sender: owner-rmt@lbl.gov Precedence: bulk This is a multi-part message in MIME format. --------------DCD90943EAD0A24B08893E73 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dear RMT Pittsburgh Presenters, if you have not yet submitted your slides for inclusion in the IETF proceedings please do so by sending them to minutes@ietf.org. thanks! Roger --------------DCD90943EAD0A24B08893E73 Content-Type: text/x-vcard; charset=us-ascii; name="rkermode.vcf" Content-Description: Card for Roger Kermode Content-Disposition: attachment; filename="rkermode.vcf" Content-Transfer-Encoding: 7bit begin:vcard n:Kermode;Roger tel;cell:+61-408-212-284 tel;fax:+61-2-9666-0501 tel;home:+61-2-9664-8335 tel;work:+61-2-9666-0558 x-mozilla-html:FALSE url:www.mot.com.au org:Motorola Australian Research Centre;Communications and Networking Lab version:2.1 email;internet:Roger.Kermode@motorola.com title:Principal Research Engineer, Manager adr;quoted-printable:;;Level 3,=0D=0A12 Lord St.;Botany;NSW;2019;Australia fn:Roger Kermode end:vcard --------------DCD90943EAD0A24B08893E73-- From owner-rmt@listserv.lbl.gov Sun Aug 27 15:00:35 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA11303 for ; Sun, 27 Aug 2000 15:00:34 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id LAA24975; Sun, 27 Aug 2000 11:00:58 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA24971 for ; Sun, 27 Aug 2000 11:00:56 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA22971 for ; Sun, 27 Aug 2000 11:00:55 -0700 (PDT) Received: from tech.cisco.com (tech.cisco.com [161.44.224.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA22963 for ; Sun, 27 Aug 2000 11:00:54 -0700 (PDT) Received: from ORANLT ([171.69.210.12]) by tech.cisco.com (Netscape Messaging Server 3.61) with SMTP id AAA2C0F; Sun, 27 Aug 2000 14:01:14 -0400 From: "Dave Oran" To: Cc: , Subject: RE: Adding reliable transport layer above sgm/xcsat Date: Sun, 27 Aug 2000 14:00:20 -0400 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 In-Reply-To: <85256944.0065FD30.00@d54mta04.raleigh.ibm.com> Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit My knowledge of reliable multicast is spotty at best, so I wade in here with some trepidation. Since this is a side issue wrt SGM, feel free to drop this thread at any point. I just want to make sure that any claims are supportable with analysis or hard facts. See below. > -----Original Message----- > From: rhboivie@us.ibm.com [mailto:rhboivie@us.ibm.com] > Sent: Wednesday, August 23, 2000 2:34 PM > To: Dave Oran > Cc: xcast@public.alcatel.com > Subject: RE: FW: FW: Adding reliable transport layer above sgm/xcsat > > > > > >> > > >> > The advantages they state seem to apply to any small group, whether > >> > based on SGM, Internet Standard multicast or SSM. I don't > see how SGM > >> > helps. > >> > >> It is not true that the advantages apply to any small group. The > >> distinguishing characteristic of SGM is that it can easily send to a > >> subset of the destinations, which makes things like reliability and > >> congestion control easier. > >> > >I'm not sure this dicussion is getting us anywhere, but I don't follow > >Dirk's contention that having explicitly-addressed subsets of the group > >helps in any substantial way for congestion control or reliability. An > >explanation might help. > > The explicit list of addresses helps with respect to reliability in > a couple of ways. > - you know the address(es) at the other end which is helpful if > you want to implement "end-to-end" reliability In order to have any sort of end-to-end reliability, you either use FEC or feedback to the transmitter. In the case of FEC the transmitter never finds out (or needs to find out) who the receiver(s) is/are. In the case of feedback, the feedback contains the (unicast) source address of the receiver and hence you can target retransmissions via unicast if need be. > - it's easy with SGM to send "appropriate" retransmissions when > retransmissions are needed. ie you can send an SGM packet to > the subset of destinations that have not acked, say, or to the > subset that have nacked, say, and the retransmission is "optimal" > in terms of the network bandwidth consumed. Well, if you use ACKs/NAKs then the main problem is the number of ACKs/NAKs, right? That's why nearly all rmt schemes use some form of ACK/NAK elimination to avoid implosion. There may be some savings if you use explicit multicast addressing for the retransmissions, but that savings depends sensitively on where the losses occur (the closer to the source, the better you do, I suppose). There is also the problem with estimating the RTT, and hence tuning the retransmission scheme, which I don't think explicit multicast doesn't helps with at all. If you don't have the timers tuned you will wind up with multiple retransmissions to different subsets and hence may have even less gain over multi-unicast, or pure multicast. > - the routers don't have to do much to support reliable SGM (ie > they don't have to do anything other than support unreliable SGM) Well, that's true of some of the RMT schemes as well. For schemes that do have router state, the difference is that with RMT the router state is viewed as optimizations and the sources don't have to get involved in figuring out the optimal strategy. > - i.e. they don't have to keep track of multicast group > state and they don't have to do retransmissions > (since reliability would be end-to-end) Some schemes have routers only holding protocol state and not data state and hence the routers don't actually do any retransmissions. Note that reliability is still end-to-end because the router state is used only as an optimization. > - the routers don't have to build special multicast trees > when a source needs to send a retransmission to a subset > of the destinations. (The tree for the retransmission > is built (as is always the case in SGM) "on the fly" as > the packet flows from the source to the destinations.) > I do not believe I know of schemes which build special trees. Some schemes are smart and prune the existing tree to the subtree needed to cover the receivers which need the retransmission, but this is not a tree computation. > Of course the fact that the groups are "small" is also helpful. > Right. The question again is whether there is any gain compared to "rmt classic" *for groups of identical size*. Has anyone actually done any analysis or simulation? Some of these properties are anti-intuitive and need hard justification. > re: congestion control, if you have end-to-end awareness (as you have > in SGM) you can implement end-to-end congestion control. And the > fact that you can easily send to a subset helps too as Dirk mentioned. > I think I disagree with this, but I'm on REALLY shaky ground here so please correct me as needed. The reason congestion control is hard for multicast in general (and RMT in particular) is because you don't know where the bottlenecks are relative to the delivery tree and because each receiver is seeing a potentially different congestion environment. As long as the source is going to try to get one packet to multiple destinations, no matter how it does so, this fact doesn't change. > You said you're "not sure this discussion is getting us anywhere". > Well it has brought out certain points such as the fact that if one > is using "conference bridges", it seems more appropriate to use > SGM than "classical multicast" as Yuji has explained in his note. > I don't know at all how you got there. I didn't respond to Yuji's note because I assumed he was just pointing out that if you did (audio) conference bridges with SGM, that would win over multi-unicast. If you factor out the group-state-in-the-routers, the optimal strategy is each source unicasting to the bridge, and the bridge unicasting back to the active sources (since each sees a unique mix), and multicasting to the non-active sources. Since any even half-way rational conference only has multiple simultaneous talkers for a brief back-off period, I don't see how you can do better than normal multicast from the bridge to the receivers. There are also hybrid techniques which I won't go into that optimize the multicast case further. > On the larger point of making progress, I'm ok with either of the > problem statements that you proposed for the working group in a note > a little while back. (If I had to choose I mightly lean slightly > toward the first one.) > And I haven't heard any feedback to the contrary so perhaps we should > formally kick off an effort to address one or both of those problem > statements. > I'm going to call the question at the end of the coming week. > Is there any reason why we shouldn't? > Yes. I think the jury is still out. I'd really like to hear from a wider audience than we've been hearing from. Dave. > > > From owner-rmt@listserv.lbl.gov Mon Aug 28 16:29:05 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA20033 for ; Mon, 28 Aug 2000 16:29:05 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id MAA28697; Mon, 28 Aug 2000 12:31:01 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA28693 for ; Mon, 28 Aug 2000 12:30:59 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA08248 for ; Mon, 28 Aug 2000 12:30:58 -0700 (PDT) Received: from computer (209-128-164-153.dial-up.ipa.net [209.128.164.153]) by SpamWall.lbl.gov (8.9.3/8.9.3) with SMTP id MAA08103 for ; Mon, 28 Aug 2000 12:30:39 -0700 (PDT) Message-Id: <200008281930.MAA08103@SpamWall.lbl.gov> From: "Lloyd Gibson" To: Subject: Secrets of New Millonaires Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Mon, 28 Aug 2000 14:31:14 Sender: owner-rmt@lbl.gov Precedence: bulk Secrets of New Millonaires > > > > > > ----- Original Message ----- > > From: "Tom Anderson" > > To: > > Sent: Thursday, June 22, 2000 2:19 PM > > Subject: Fwd: Secrets of New Millionaires > > > > > > > > > > > > > > > > >From: "Lloyd Gibson" > > > >To: billa30@hotmail.com > > > >Subject: Fwd: Secrets of New Millionaires > > > >Date: Wed, 14 Jun 2000 13:04:28 CDT > > > > > > > > > > > > > > > > > > > >>From: > > > >>Subject: Secrets of New Millionaires > > > >>Date: Wed, 26 Apr 2000 02:47:02 > > > >>Received: from [4.3.96.183] by hotmail.com (3.2) with ESMTP id > > > >>MHotMailBAD01C76007BD82197D4040360B709610; Wed Apr 26 04:22:35 2000 > > > >>From webfinderz00@Yahoo.com Wed Apr 26 04:26:05 2000 > > > >>Message-Id: <331.824584.698332@server> > > > >> > > > >>Dear Friend, > > > >> > > > >>You can earn $50,000 or more in the next 90 days > > > >>sending e-mail. > > > >> > > > >> Seem impossible? Read on for details. > > > >> > > > >> "AS SEEN ON NATIONAL TV" > > > >> > > > >> Thank you for your time and interest. This is the > > > >>letter you've been reading about in the news lately. > > > >>Due to the popularity of this letter on the Internet, > > > >>a major nightly news program recently devoted an > > > >>entire show to the investigation of the program > > > >>described below to see if it really can make people > > > >>money. > > > >> > > > >> The show also investigated whether or not the > > > >>program was legal. Their findings proved once and for > > > >>all that there are absolutely no laws prohibiting the > > > >>participation in the program. This has helped to show > > > >>people that this is a simple, harmless and fun way to > > > >>make some extra money at home. > > > >> > > > >> The results of this show have been truly > > > >>remarkable. So many people are participating that > > > >>those involved are doing much better than ever before. > > > >>Since everyone makes more as more people try it out, > > > >>it's been very exciting to be a part of lately. You > > > >>will understand once you experience it. > > > >> > > > >> I did and so far it's going great! HERE IT IS BELOW: > > > >> > > > >> *** Print This Now For Future Reference *** > > > >> > > > >> The following income opportunity is one you may be > > > >>interested in taking a look at. It can be started with > > > >>VERY LITTLE investment and the income return is > > > >>TREMENDOUS!!! > > > >> > > > >> $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ > > > >> > > > >> If you would like to make at least $50,000 in less > > > >>than 90 days! Please read the enclosed program...THEN > > > >>READ IT AGAIN!!! > > > >> > > > >> $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ > > > >> > > > >> THIS IS A LEGITIMATE, LEGAL, MONEY MAKING > > > >>OPPORTUNITY. It does not require you to come into > > > >>contact with people, do any hard work, and best of > > > >>all, you never have to leave the house except to get > > > >>the mail. > > > >> > > > >> If you believe that someday you'll get that big > > > >>break that you've been waiting for, THIS IS IT! > > > >> > > > >> Simply follow the instructions, and your dreams > > > >>will come true. > > > >> > > > >> This multi-level e-mail order marketing program > > > >>works perfectly...100% EVERYTIME. > > > >> > > > >> E-mail is the sales tool of the future. Take > > > >>advantage of this non-commercialized method of > > > >>advertising NOW!!! The longer you wait, the more > > > >>people will be doing business using e-mail. Get your > > > >>piece of this action!!! > > > >> > > > >> MULTI-LEVEL MARKETING (MLM) has finally gained > > > >>respectability. It is being taught in the Harvard > > > >>Business School, and both Stanford Research and the > > > >>Wall Street Journal have stated that between 50% and > > > >>65% of all goods and services will be sold through > > > >>multi-level methods by the mid to late 1990's. > > > >> > > > >> This is a Multi-Billion Dollar industry and of the > > > >>500,000 millionaires in the U.S., 20% (100,000) made > > > >>their fortune in the last several years in MLM. > > > >> Moreover, statistics show 45 people become > > > >>millionaire's everyday through Multi-Level Marketing. > > > >> > > > >> You may have heard this story before, but over the > > > >>summer Donald Trump made an appearance on the David > > > >>Letterman show. Dave asked him what he would do if he > > > >>lost everything and had to start over from scratch. > > > >>Without hesitating, Trump said he would find a good > > > >>network marketing company and get to work. The > > > >>audience started to hoot and boo him. He looked out at > > > >>the audience and deadpanned his response: > > > >> > > > >> "That's why I'm sitting up here and you are all > > > >>sitting out there!" > > > >> > > > >> The enclosed information is something I almost let > > > >>slip through my fingers. > > > >> > > > >> Fortunately, sometime later I re-read everything > > > >>and gave some thought and study to it. My name is > > > >>Johnathon Rourke. Two years ago, the corporation I > > > >>worked at for the past twelve years downsized and my > > > >>position was eliminated. After unproductive job interviews, I > > > >>decided to open my own business. Over the past year, I > > > >>incurred many unforeseen financial problems. > > > >> > > > >> I owed my family, friends and creditors over > > > >>$35,000. The economy was taking a toll on my business > > > >>and I just couldn't seem to make ends meet. I had to > > > >>refinance and borrow against my home to support my > > > >>family and struggling business. > > > >> > > > >> AT THAT MOMENT something significant happened in my > > > >>life and I am writing to share the experience in hopes > > > >>that this will change your life FOREVER FINANCIALLY!!! > > > >> > > > >> In mid December, I received this program via > > > >>e-mail. Six month's prior to receiving this program I > > > >>had been sending away for information on various > > > >>business opportunities. All of the programs I > > > >>received, in my opinion, were not cost effective. They were > > > >>either too difficult for me to comprehend or the initial > > > >>investment was too much for me to risk to see if they > > > >>would work or not. One claimed that I would make a > > > >>million dollars in one year...it didn't tell me I'd > > > >>have to write a book to make it! > > > >> > > > >> But like I was saying, in December of 1999 I > > > >>received this program. I didn't send for it, or ask > > > >>for it, they just got my name off a mailing list. > > > >>THANK GOODNESS FOR THAT!!! After reading it several > > > >>times, to make sure I was reading it correctly, I couldn't > > > >>believe my eyes. Here was a MONEY MAKING PHENOMENON. > > > >>I could invest as much as I wanted to start, without > > > >>putting me further into debt. After I got a pencil and > > > >>paper and figured it out, I would at least get my > > > >>money back. But like most of you I was still a little > > > >>skeptical and a little worried about the legal aspects > > > >>of it all. So I checked it out with the U.S. Post > > > >>Office (1-800-725-2161 24-hrs) and they confirmed that > > > >>it is indeed legal! After determining the program was > > > >>LEGAL and NOT A CHAIN LETTER, I decided WHY NOT." > > > >> > > > >> Initially I sent out 10,000 e-mails. It cost me > > > >>about $15 for my time on-line. The great thing about > > > >>e-mail is that I don't need any money for printing to > > > >>send out the program, and because all of my orders are > > > >>fulfilled via e-mail, my only expense is my time. I am > > > >>telling you like it is I hope it don't turn you off, > > > >>but I promised myself that I would not "rip-off" > > > >>anyone, no matter how much money it made me. > > > >> > > > >> In less than one week, I was starting to receive > > > >>orders for REPORT # 1 By January 13; I had received 26 > > > >>orders for REPORT # 1. Your goal is to "RECEIVE at > > > >>least 20 ORDERS FOR REPORT # 1 WITHIN 2 WEEKS. IF YOU > > > >>DON'T, SEND OUT MORE PROGRAMS UNTIL YOU DO!" > > > >> > > > >> My first step in making $50,000 in 90 days was done. By January > > > >>30, I > > > >>had received 196 orders for REPORT # 2. Your goal is to > > > >>"RECEIVE AT LEAST 100+ ORDERS FOR REPORT # 2 WITHIN 2 > > > >>WEEKS. IF NOT, SEND OUT MORE PROGRAMS UNTIL YOU DO. > > > >>ONCE YOU HAVE 100 ORDERS, THE REST IS EASY, RELAX, YOU > > > >>WILL MAKE YOUR $50,000 GOAL." Well, I had 196 orders > > > >>for REPORT # 296 more than I needed. So I sat back and > > > >>relaxed. By March 1, of my e-mailing of 10,000, I > > > >>received $58,000 with more coming in every day. > > > >> > > > >> I paid off ALL my debts and bought a much needed > > > >>new car. Please take your time to read the attached > > > >>program, IT WILL CHANGE YOUR LIFE FOREVER!!! > > > >> > > > >> Remember, it won't work if you don't try it. This > > > >>program does work, but you must follow it EXACTLY! > > > >>Especially the rules of not trying to place your name > > > >>in a different place. It won't work and you'll lose > > > >>out on a lot of money! > > > >> > > > >> In order for this program to work, you must meet > > > >>your goal of 20 + orders for REPORT # 1, and 100 + orders > > > >>for REPORT # 2 and you will make $50,000 or more in 90 > > > >>days. I AM LIVING PROOF THAT IT WORKS!!! > > > >> > > > >> If you choose not to participate in this program, I > > > >>am sorry. It really is a great opportunity with little > > > >>cost or risk to you. If you choose to participate, > > > >>follow the program and you will be on your way to > > > >>financial security. If you are a fellow business owner > > > >>and are in financial trouble like I was, or you want > > > >>to start your own business, consider this a sign. > > > >> > > > >> I DID! > > > >> > > > >> Sincerely, > > > >> Johnathon Rourke > > > >> > > > >> > > > >>~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~ > > > >>~~ > > > >> > > > >> A PERSONAL NOTE FROM THE ORIGINATOR OF THIS > > > >>PROGRAM: > > > >> > > > >> By the time you have read the enclosed program and > > > >>reports, you should have concluded that such a > > > >>program, and one that is legal, could not have been > > > >>created by an amateur. > > > >> > > > >> Let me tell you a little about myself. I had a > > > >>profitable business for 10 years. Then in 1979 my > > > >>business began falling off. I was doing the same > > > >>things that were previously successful for me, but it > > > >>wasn't working. Finally, I figured it out. It wasn't me, it > > > >>was the economy. Inflation and recession had replaced > > > >>the stable economy that had been with us since 1945. > > > >> > > > >> I don't have to tell you what happened to the > > > >>unemployment rate... because many of you know from > > > >>first hand experience. There were more failures and > > > >>bankruptcies than ever before. The middle class was > > > >>vanishing. Those who knew what they were doing > > > >>invested wisely and moved up. Those who did not, > > > >>including those who never had anything to save or > > > >>invest, were moving down into the ranks of the poor. > > > >> > > > >> As the saying goes, "THE RICH GET RICHER AND THE POOR > > > >>GET POORER." The traditional methods of making money > > > >>will never allow you to "move up" or "get rich", inflation will > > > >>see to that. > > > >> > > > >> You have just received information that can give > > > >>you financial freedom for the rest of your life, with > > > >>"NO RISK" and "JUST A LITTLE BIT OF EFFORT." You can > > > >>make more money in the next few months than you have > > > >>ever imagined. I should also point out that I will not see > > > >>a penny of this money, nor anyone else who has > > > >>provided a testimonial for this program. I have > > > >>already made over 4 MILLION DOLLARS! I have retired > > > >>from the program after sending thousands and thousands > > > >>of programs. > > > >> > > > >>Follow the program EXACTLY AS INSTRUCTED. > > > >>Do not change it in any way. It works exceedingly well > > > >>as it is now. Remember to e-mail a copy of this > > > >>exciting report to everyone you can think of. One of the people > > > >>you > > > >>send this to may send out 50,000...and your name will be on > > > >>every one of them! > > > >> > > > >> Remember though, the more you send out the more > > > >>potential customers you will reach. > > > >> > > > >> So my friend, I have given you the ideas, > > > >>information, materials and opportunity to become > > > >>financially independent. IT IS UP TO YOU NOW! > > > >> > > > >> "THINK ABOUT IT" > > > >> > > > >> Before you delete this program from your mailbox, > > > >>as I almost did, take a little time to read it and > > > >>REALLY THINK ABOUT IT. Get a pencil and figure out > > > >>what could happen when YOU participate. Figure out the > > > >>worst possible response and no matter how you > > > >>calculate it, you will still make a lot of money! You > > > >>will definitely get back what you invested. Any doubts > > > >>you have will vanish when your first orders come in. > > > >>IT WORKS! > > > >> > > > >> Jody Jacobs > > > >> Richmond, VA > > > >> > > > >> HERE'S HOW THIS AMAZING PROGRAM WILL MAKE YOU > > > >>THOUSANDS OF DOLLAR$ > > > >> > > > >> INSTRUCTIONS: > > > >> > > > >> This method of raising capital REALLY WORKS 100% > > > >>EVERY TIME. I am sure that you could use up to $50,000 > > > >>or more in the next 90 days. Before you say "BULL... > > > >>", please read this program carefully. > > > >> > > > >> This is not a chain letter, but a perfectly legal > > > >>money making opportunity. Basically, this is what you > > > >>do: As with all multi-level businesses, we build our > > > >>business by recruiting new partners and selling our > > > >>products. Every state in the USA allows you to recruit > > > >>new multi-level business partners, and we offer a > > > >>product for EVERY dollar sent. > > > >> > > > >> YOUR ORDERS COME BY MAIL AND ARE FILLED BY E-MAIL, > > > >>so you are not involved in personal selling. You do it > > > >>privately in your own home, store or office. This is > > > >>the GREATEST Multi-Level Mail Order Marketing > > > >>anywhere. > > > >> > > > >> This is what you MUST do: > > > >> > > > >> 1. Order all 4 reports shown on the list below (you > > > >>can't sell them if you don't order them). > > > >> > > > >> -- For each report, send $5.00 CASH, the NAME & > > > >>NUMBER OF THE REPORT YOU ARE ORDERING, YOUR E-MAIL > > > >>ADDRESS, and YOUR NAME & RETURN ADDRESS (in case of a > > > >>problem) to the person whose name appears on the list > > > >>next to the report. > > > >> > > > >> MAKE SURE YOUR RETURN ADDRESS IS ON YOUR ENVELOPE > > > >>IN CASE OF ANY MAIL PROBLEMS! > > > >> > > > >> -- When you place your order, make sure you order > > > >>each of the four reports. You will need all four > > > >>reports so that you can save them on your computer and > > > >>resell them. > > > >> > > > >> -- Within a few days you will receive, via e-mail, > > > >>each of the four reports. Save them on your computer > > > >>so they will be accessible for you to send to the > > > >>1,000's of people who will order them from you. > > > >> > > > >> 2. IMPORTANT DO NOT alter the names of the people > > > >>who are listed next to each report, or their sequence > > > >>on the list, in any way other than is instructed below > > > >>in steps "a" through "f" or you will lose out on the > > > >>majority of your profits. Once you understand the > > > >>way this works, you'll also see how it doesn't work if > > > >>you change it. Remember, this method has been tested, > > > >>and if you alter it, it will not work. > > > >> > > > >> a. Look below for the listing of available reports. > > > >> > > > >> b. After you've ordered the four reports, take this > > > >>advertisement and remove the name and address under > > > >>REPORT # 4. This person has made it through the cycle > > > >>and is no doubt counting their $50,000! > > > >> > > > >> c. Move the name and address under REPORT # 3 down > > > >>to REPORT # 4. > > > >> > > > >> d. Move the name and address under REPORT # 2 down > > > >>to REPORT # 3. > > > >> > > > >> e. Move the name and address under REPORT # 1 down > > > >>to REPORT # 2. > > > >> > > > >> f. Insert your name/address in the REPORT # 1 > > > >>position. > > > >> > > > >> Please make sure you COPY ALL INFORMATION, every > > > >>name and address, ACCURATELY! > > > >> > > > >> 3. Take this entire letter, including the modified > > > >>list of names, and save it to your computer. Make NO > > > >>changes to the instruction portion of this letter. > > > >> > > > >> Your cost to participate in this is practically > > > >>nothing (surely you can afford $20). You obviously > > > >>already have an Internet connection and > > > >>e-mail is FREE! > > > >> > > > >> There are two primary methods of building your > > > >>downline: > > > >> > > > >> METHOD # 1: SENDING BULK E-MAIL > > > >> > > > >> Let's say that you decide to start small, just to > > > >>see how it goes, and we'll assume you and all those > > > >>involved send out only 2,000 programs each. Let's > > > >>also assume that the mailing receives a 0.5% response. > > > >>Using a good list the response could be much better. > > > >>Also, many people will send out hundreds of thousands > > > >>of programs instead of 2,000. But continuing with this > > > >>example, you send out only 2,000 programs. With a 0.5% > > > >>response, that is only 10 orders for REPORT # 1. Those > > > >>10 people respond by sending out 2,000 programs each > > > >>for a total of 20,000. Out of those 0.5%, 100 people > > > >>respond and order REPORT # 2. Those 100 mail out 2,000 > > > >>programs each for a total of 200,000. The 0.5% > > > >>response to that are 1,000 orders for REPORT # 3. Those > > > >>1,000 send out 2,000 programs each for a 2,000,000 > > > >>total. > > > >> > > > >>The 0.5% response to that are 10,000 orders for REPORT # 4. > > > >>That's 10,000 $5 bills for you. CASH!!! Your total > > > >>income in this example is $50 + $500 + $5,000 + $50,000 > > > >>for a total of $55,550!!! REMEMBER FRIEND, THIS IS > > > >>ASSUMING 1,990 OUT OF THE 2,000 PEOPLE YOU MAIL TO > > > >>WILL DO ABSOLUTELY NOTHING AND TRASH THIS PROGRAM! > > > >>DARE TO THINK FOR A MOMENT WHAT WOULD HAPPEN IF > > > >>EVERYONE, OR HALF SENT OUT 100,000 PROGRAMS INSTEAD OF > > > >>2,000. Believe me, many people will do just that, and > > > >>more! By the way, your cost to participate in this is > > > >>practically nothing. You obviously already have an > > > >>Internet connection and e-mail is FREE!!! > > > >> > > > >> REPORT # 2 will show you the best methods for bulk > > > >>e-mailing; tell you where to obtain free bulk e-mail > > > >>software and where to obtain e-mail lists. > > > >> > > > >> METHOD # 2 - PLACING FREE ADS ON THE INTERNET > > > >> > > > >> Advertising on the Internet is very, very > > > >>inexpensive, and there are HUNDREDS of FREE places to > > > >>advertise. Let's say you decide to start small just to > > > >>see how well it works. Assume your goal is to get ONLY > > > >>10 people to participate on your first level. (Placing > > > >>a lot of FREE ads on the Internet will EASILY get a > > > >>larger response.) Also assume that everyone else in > > > >>YOUR ORGANIZATION gets ONLY 10 downline members. > > > >>Follow this example to achieve the STAGGERING results > > > >>below: > > > >> > > > >> 1st level--your 10 members with > > > >> $5.......................................$50 > > > >> > > > >> 2nd level--10 members from those 10 > > > >> ($5 x 100)..................$500 > > > >> > > > >> 3rd level--10 members from those 100 > > > >> ($5 x 1,000)...........$5,000 > > > >> > > > >> 4th level--10 members from those 1,000 > > > >> ($5 x 10,000).....$50,000 > > > >> > > > >> THIS TOTALS ----------$55,550 > > > >> > > > >> Remember friends, this assumes that the people who > > > >>participate only recruit 10 people each. Think for a > > > >>moment what would happen if they got 20 people to > > > >>participate! Most people get 100's of participants! > > > >> > > > >> THINK ABOUT IT! For every $5.00 you receive, all > > > >>you must do is e-mail them the report they ordered. > > > >>THAT'S IT! ALWAYS PROVIDE SAME-DAY SERVICE ON ALL > > > >>ORDERS! This will guarantee that the e-mail THEY send > > > >>out with YOUR name and address on it will be prompt > > > >>because they can't advertise until they receive the > > > >>report! > > > >> > > > >> AVAILABLE REPORTS > > > >> > > > >> *** Order Each REPORT by NUMBER and NAME *** > > > >> Notes: > > > >> > > > >> -- ALWAYS SEND $5 CASH (U.S. CURRENCY) FOR EACH > > > >>REPORT. CHECKS NOT > > > >>ACCEPTED. > > > >> > > > >> -- ALWAYS SEND YOUR ORDER VIA FIRST CLASS MAIL. > > > >> > > > >> Make sure the cash is concealed by wrapping it in at least two > > > >>sheets of paper. > > > >>On one of those sheets of paper, include: > > > >> > > > >> (a) the number & name of the report you are ordering, > > > >> > > > >> (b) your e-mail address, and > > > >> > > > >> (c) your name & postal address. > > > >> > > > >> > > > >> ## PLACE YOUR ORDER FOR THESE REPORTS NOW: > > > >> > > > >> REPORT # 1 "The Insider's Guide to Advertising for > > > >>Free on the Internet" > > > >> > > > >> ORDER REPORT FROM: # 1 FROM: > > > >>Jerry G Enterprisess > > > >> 19007 CopperMine RD. Rogers AR. 72756 > > > >> REPORT # 2 "The Insider's Guide to Sending Bulk > > > >>E-mail on the Internet" > > > >> > > > >> ORDER REPORT # 2 FROM: > > > >>Nitro Marketing > > > >> 29250 Hwy. HH > > > >> Sedalia, MO 65301 > > > >>> > > >> > > > >> REPORT # 3 "The Secrets to Multilevel Marketing on > > > >>the Internet" > > > >>Jerry Bradford > > > >> P.O. Box 366 > > > >> Cole Camp, MO 65235 > > > >> > > > >>> > > >> > > > >> REPORT # 4 "How to become a Millionaire utilizing > > > >>the Power of Multilevel Marketing and the Internet" > > > >>> > > >>> ORDER REport # 4 From> > > >> > > > > > > >> > > > >> > > >> Derald Ewing > > > >> 4000 Hyde Park Ave. Apt. # 83 > > > >> Columbia, MO 65201 > > > >> > > > >> > > > >> About 50,000 new people get online every month! > > > >> > > > >> ******* TIPS FOR SUCCESS ******* > > > >> > > > >> -- TREAT THIS AS YOUR BUSINESS! Be prompt, > > > >>professional, and follow the directions accurately. > > > >> > > > >> -- Send for the four reports IMMEDIATELY so you > > > >>will have them when the orders start coming in > > > >>because: When you receive a $5 order, you MUST send > > > >>out the requested product/report. > > > >> > > > >> -- ALWAYS PROVIDE SAME-DAY SERVICE ON THE ORDERS > > > >>YOU RECEIVE. > > > >> > > > >> -- Be patient and persistent with this program. If > > > >>you follow the instructions exactly, your results WILL > > > >>BE SUCCESSFUL! > > > >> > > > >> -- ABOVE ALL, HAVE FAITH IN YOURSELF AND KNOW YOU > > > >>WILL SUCCEED! > > > >> > > > >> ******* YOUR SUCCESS GUIDELINES ******* > > > >> > > > >> Follow these guidelines to guarantee your success: > > > >> > > > >> If you don't receive 20 orders for REPORT # 1 within > > > >>two weeks, continue advertising or sending e-mails > > > >>until you do. Then, a couple of weeks later you should > > > >>receive at least 100 orders for REPORT # 2. If you > > > >>don't, continue advertising or sending e-mails until you do. > > > >>Once you have received 100 or more orders for REPORT > > > >># 2, YOU CAN RELAX, because the system is already > > > >>working for you, and the cash will continue to roll in! > > > >> > > > >> THIS IS IMPORTANT TO REMEMBER: > > > >> > > > >> Every time your name is moved down on the list, you > > > >>are placed in front of a DIFFERENT report. You can > > > >>KEEP TRACK of your PROGRESS by watching which report > > > >>people are ordering from you. If you want to generate > > > >>more income, send another batch of e-mails or continue > > > >>placing ads and start the whole process again! There > > > >>is no limit to the income you will generate from this > > > >>business! Before you make your decision as to whether > > > >>or not you participate in this program. Please answer > > > >>one question. DO YOU WANT TO CHANGE YOUR LIFE? If the > > > >>answer is yes, please look at the following facts > > > >>about this program: > > > >> > > > >> 1. You are selling a product which does not Cost > > > >>anything to PRODUCE, SHIP OR ADVERTISE. > > > >> > > > >> 2. All of your customers pay you in CASH! > > > >> > > > >> 3. E-mail is without question the most powerful > > > >>method of distributing information on earth. This > > > >>program combines the distribution power of e-mail > > > >>together with the revenue generating power of > > > >>multi-level marketing. > > > >> > > > >> 4. Your only expense--other than your initial $20 > > > >>investment--is your time! > > > >> > > > >> 5. Virtually all of the income you generate from > > > >>this program is PURE PROFIT! > > > >> > > > >> 6. This program will change your LIFE FOREVER. > > > >> ACT NOW! Take your first step toward achieving > > > >>financial independence. Order the reports and follow > > > >>the program outlined above--SUCCESS will be > > > >>your reward. > > > >> > > > >> Thank you for your time and consideration. > > > >> > > > >> PLEASE NOTE: If you need help with starting a > > > >>business, registering a business name, learning how > > > >>income tax is handled, etc., contact your local > > > >>office of the Small Business Administration (a > > > >>Federal Agency)1-800-827-5722 for free help and > > > >>answers to questions. > > > >> > > > >>Also, the Internal Revenue Service > > > >>offers free help via telephone and free seminars about > > > >>business tax requirements. Your earnings are highly > > > >>dependant on your activities and advertising. The information > > > >>contained on this site and in the report constitutes > > > >>no guarantees neither stated nor implied. In the event that it > > > >>is determined that this site or report constitutes a > > > >>guarantee of any kind, that guarantee is now void. The > > > >>earnings amounts listed on this site and in the > > > >>report are estimates only. If you have any questions > > > >>of the legality of this program, contact the Office of > > > >>Associate Director for Marketing Practices, Federal > > > >>Trade Commission, and Bureau of > > > >>Consumer Protection in Washington, DC. > > > >> > > > >> > > > >>///////////////////////////////////////////////////////////////// > > > >> ONE TIME MAILING, NO NEED TO REMOVE > > > >> > > > >>///////////////////////////////////////////////////////////////// > > > >> > > > >> > > > >>******************************************************** > > > >> This message is sent in compliance of the proposed > > > >>bill:SECTION 301. > > > >> Per Section 301, Paragraph (a)(2)(C) of S. 1618, > > > >> further transmissions to you by the sender of this > > > >>email may be stopped at no cost to you by sending a > > > >>reply to this email address with the word remove in > > > >>the > > > >>subject line. This message is not intended for > > > >>residents in the State of Washington, screening of > > > >>addresses has been done to the best of our technical > > > >>ability. If you are a Washington, Virginia, or > > > >>California resident or otherwise wish to be removed > > > >>from this list, further transmissions to you by the > > > >>sender of this email may be stopped at no cost to you > > > >>by sending a reply to this email address with the word > > > >>remove in the subject line. > > > >> > > > >>********************************************************* > > > >> > > > >> > > > >> > > > >> > > > >> > > > >> > > > >> > > > >> > > > > > > > > > > _______________________________________________________________________ _ > > > Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com > > > > > > Error: Timeout , Sent From: tMTIAppUnlock.OnfTimer , Var: Error: Timeout , Sent From: tMTIAppUnlock.OnfTimer , Var: Error: Timeout , Sent From: tMTIAppUnlock.OnfTimer , Var: From owner-rmt@listserv.lbl.gov Mon Aug 28 19:30:05 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA22079 for ; Mon, 28 Aug 2000 19:30:04 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id PAA29501; Mon, 28 Aug 2000 15:18:01 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id PAA29496 for ; Mon, 28 Aug 2000 15:17:59 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id PAA01132 for ; Mon, 28 Aug 2000 15:17:58 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id PAA01122 for ; Mon, 28 Aug 2000 15:17:56 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id PAA28945 for ; Mon, 28 Aug 2000 15:17:30 -0700 (PDT) Message-Id: <4.1.20000828143653.01ba80e0@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Mon, 28 Aug 2000 15:17:24 -0700 To: rmt@lbl.gov From: Brian Whetten Subject: Choices for TRACK/NACK report encoding Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk Hi there, A question just came up for me on how we should best do NACK (and TRACK) encoding for the information that is sent up. I think there are two primary ways that have been used so far: List NACKs (i.e. PGM) and bitmaps (i.e. RMTP-II & TRAM). The other option, which hasn't been used yet but has been discussed, is run length encoded bitmaps. I'd ideally like to see us use the same encoding format (as part of the common data headers BB) for each. I ran a quick comparison of the overhead of encoding a window of N packets, with a uniform loss rate of P. The overhead for each option is: List NACK=32*N*P Bitmap=N RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is reasonably accurate for low values of P) Note that as P approaches 1 (worst case, which we need to plan for), we get: List=32*N Bitmap=N RLE Bitmap=Actually goes down (because we encode successes rather than losses), with a worst case always less than either of the other two (but approaching the bitmap case). Here are numeric results for these formulas, in bits, assuming N=1000. p List NACK Bitmap RLE Bitmap 0.001 32 1000 10 0.0031 101 1000 28.5 0.01 320 1000 70 0.031 1012 1000 158.1 0.1 3200 1000 400 0.31 10119 1000 632 0.66 21120 1000 660 0.9 28800 1000 400 As you can see, List NACKs are better than a bitmap for P<3%, and worse otherwise. A RLE bitmap is the most complicated to implement, but is also the most efficient for all cases. A related topic to this is the idea of reliable NACKs. Taking PGM as an example, it uses reliable NACKs, which make a lot of sense if none of these encoding mechanisms are used, since there is no built in redundancy across successive NACKs in that case. I think that NORM/PGM's biggest advantage is being able to work without needing reliability mechanisms, which gives these protocols better scalability in the face of failures. The reliable NACKs actually go directly in the face of this, and increase the amount of NACK implosion traffic that would occur when a network partition occurs. I believe that the need for reliable NACKs could be removed in NACK-only protocols (as it is in TRACK oriented protocols) by reporting a full status of all the non-stable packets. With a RLE mechanism, this scales very nicely, and I think the overhead of adding the RLE mechanism would be less than the complexity of reliable NACKs. Conclusion: I think we should standardize on non-reliable NACKs/TRACKs (they are basically the same thing, just generated at different times), which use the same encoding format for their retransmission request reports. I think that RLE encoded bitmaps should be used for this, since the system needs to be stable even in the face of very high loss rates and high data rates. Comments? Brian From owner-rmt@listserv.lbl.gov Mon Aug 28 19:56:37 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA22341 for ; Mon, 28 Aug 2000 19:56:36 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id QAA29611; Mon, 28 Aug 2000 16:06:58 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA29607 for ; Mon, 28 Aug 2000 16:06:56 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA15343 for ; Mon, 28 Aug 2000 16:06:55 -0700 (PDT) Received: from prv-mail20.provo.novell.com (prv-mail20.provo.novell.com [137.65.81.122]) by SpamWall.lbl.gov (8.9.3/8.9.3) with SMTP id QAA15338 for ; Mon, 28 Aug 2000 16:06:54 -0700 (PDT) Received: from INET-PRV-Message_Server by prv-mail20.provo.novell.com with Novell_GroupWise; Mon, 28 Aug 2000 17:06:20 -0600 Message-Id: X-Mailer: Novell GroupWise Internet Agent 5.5.3.1 Date: Mon, 28 Aug 2000 17:06:16 -0600 From: "Sukanta Ganguly" To: , Subject: Re: Choices for TRACK/NACK report encoding Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="=_772FE97C.87E68BD3" Sender: owner-rmt@lbl.gov Precedence: bulk This is a MIME message. If you are reading this text, you may want to consider changing to a mail reader or gateway that understands how to properly handle MIME multipart messages. --=_772FE97C.87E68BD3 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable Brian, Reliable NACK should not be the fact based on which the design should be = done. Scalability is the obvious probelm with it. So most of your = assumptions are correct. I don't quite understand how you came up with the = overheads. I also could not quite understand where did you get the 32 in = the calculation.=20 However, what do you mean by full status of the non-stable packets? = Where is this full status generated? Are we assumming that the RLE data = reaches the target without any loss? SG >>> Brian Whetten 08/28/00 04:17PM >>> Hi there, A question just came up for me on how we should best do NACK (and TRACK) encoding for the information that is sent up. I think there are two primary ways that have been used so far: List NACKs (i.e. PGM) and = bitmaps (i.e. RMTP-II & TRAM). The other option, which hasn't been used yet but has been discussed, is run length encoded bitmaps. =20 I'd ideally like to see us use the same encoding format (as part of the common data headers BB) for each. I ran a quick comparison of the = overhead of encoding a window of N packets, with a uniform loss rate of P. The overhead for each option is: List NACK=3D32*N*P Bitmap=3DN RLE Bitmap=3Dapproximately Ceiling(Log2(1/P))*N*P (I think this is reasonably accurate for low values of P) Note that as P approaches 1 (worst case, which we need to plan for), we = get: List=3D32*N Bitmap=3DN RLE Bitmap=3DActually goes down (because we encode successes rather than losses), with a worst case always less than either of the other two (but approaching the bitmap case). Here are numeric results for these formulas, in bits, assuming N=3D1000. p List NACK Bitmap RLE Bitmap 0.001 32 1000 10 0.0031 101 1000 28.5 0.01 320 1000 70 0.031 1012 1000 158.1 0.1 3200 1000 400 0.31 10119 1000 632 0.66 21120 1000 660 0.9 28800 1000 400 As you can see, List NACKs are better than a bitmap for P<3%, and worse otherwise. A RLE bitmap is the most complicated to implement, but is also the most efficient for all cases. A related topic to this is the idea of reliable NACKs. Taking PGM as an example, it uses reliable NACKs, which make a lot of sense if none of = these encoding mechanisms are used, since there is no built in redundancy across successive NACKs in that case. I think that NORM/PGM's biggest advantage is being able to work without needing reliability mechanisms, which gives these protocols better scalability in the face of failures. The reliable NACKs actually go directly in the face of this, and increase the amount of NACK implosion traffic that would occur when a network partition occurs. = =20 I believe that the need for reliable NACKs could be removed in NACK-only protocols (as it is in TRACK oriented protocols) by reporting a full = status of all the non-stable packets. With a RLE mechanism, this scales very nicely, and I think the overhead of adding the RLE mechanism would be less than the complexity of reliable NACKs. Conclusion: I think we should standardize on non-reliable NACKs/TRACKs (they are basically the same thing, just generated at different times), which use the same encoding format for their retransmission request reports. I think that RLE encoded bitmaps should be used for this, since the system needs to be stable even in the face of very high loss rates and high data rates. =20 Comments? Brian --=_772FE97C.87E68BD3 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Brian,
  Reliable NACK should not be the fact based on which the = design=20 should be done. Scalability is the obvious probelm with it. So most = of your=20 assumptions are correct. I don't quite understand how you came up with = the=20 overheads. I also could not quite understand where did you get the 32 in = the=20 calculation.
  However, what do you mean by full status of the non-s= table=20 packets? Where is this full status generated? Are we assumming that the = RLE data=20 reaches the target without any loss?
 
SG

>>> Brian Whetten <whetten@talarian.com> = 08/28/00=20 04:17PM >>>
Hi there,
A question just came up for me on how = we=20 should best do NACK (and TRACK)
encoding for the information that is = sent=20 up.  I think there are two
primary ways that have been used so=20 far:  List NACKs (i.e. PGM) and bitmaps
(i.e. RMTP-II & = TRAM). =20 The other option, which hasn't been used yet but
has been discussed, is = run=20 length encoded bitmaps. 

I'd ideally like to see us use the = same=20 encoding format (as part of the
common data headers BB) for each.  = I ran=20 a quick comparison of the overhead
of encoding a window of N packets, = with a=20 uniform loss rate of P.  The
overhead for each option is:

Li= st=20 NACK=3D32*N*P
Bitmap=3DN
RLE Bitmap=3Dapproximately Ceiling(Log2(1/P)= )*N*P =20 (I think this is
reasonably accurate for low values of P)

Note = that as=20 P approaches 1 (worst case, which we need to plan for), we=20 get:
List=3D32*N
Bitmap=3DN
RLE Bitmap=3DActually goes down = (because we=20 encode successes rather than
losses), with a worst case always less = than=20 either of the other two (but
approaching the bitmap case).

Here = are=20 numeric results for these formulas, in bits, assuming=20 N=3D1000.

p        List=20 NACK    Bitmap        RLE=20 Bitmap
0.001        32   = =20     1000       =20 10
0.0031    101       =20 1000        28.5
0.01   =20=     320       =20 1000        70
0.031   =20     1012       =20 1000        158.1
0.1   =20=     3200       =20 1000        400
0.31   =20     10119       =20 1000        632
0.66   =20     21120       =20 1000        660
0.9   =20     28800       =20 1000        400

As you can see, List = NACKs=20 are better than a bitmap for P<3%, and worse
otherwise.  A RLE = bitmap=20 is the most complicated to implement, but is also
the most efficient = for all=20 cases.

A related topic to this is the idea of reliable NACKs. = =20 Taking PGM as an
example, it uses reliable NACKs, which make a lot of = sense=20 if none of these
encoding mechanisms are used, since there is no built = in=20 redundancy across
successive NACKs in that case.  I think that=20 NORM/PGM's biggest advantage
is being able to work without needing=20 reliability mechanisms, which gives
these protocols better scalability = in the=20 face of failures.  The reliable
NACKs actually go directly in the = face=20 of this, and increase the amount of
NACK implosion traffic that would = occur=20 when a network partition occurs. 

I believe that the need = for=20 reliable NACKs could be removed in NACK-only
protocols (as it is in = TRACK=20 oriented protocols) by reporting a full status
of all the non-stable=20 packets.  With a RLE mechanism, this scales very
nicely, and I = think the=20 overhead of adding the RLE mechanism would be less
than the complexity = of=20 reliable NACKs.

Conclusion:  I think we should standardize = on=20 non-reliable NACKs/TRACKs
(they are basically the same thing, just = generated=20 at different times),
which use the same encoding format for their=20 retransmission request
reports.  I think that RLE encoded bitmaps = should=20 be used for this, since
the system needs to be stable even in the face = of=20 very high loss rates and
high data rates. =20

Comments?
Brian

--=_772FE97C.87E68BD3-- From owner-rmt@listserv.lbl.gov Tue Aug 29 11:01:09 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA20666 for ; Tue, 29 Aug 2000 11:01:08 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id GAA02929; Tue, 29 Aug 2000 06:52:09 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id GAA02925 for ; Tue, 29 Aug 2000 06:52:07 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id GAA14299 for ; Tue, 29 Aug 2000 06:52:06 -0700 (PDT) Received: from info.iet.unipi.it (info.iet.unipi.it [131.114.9.184]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id GAA14296 for ; Tue, 29 Aug 2000 06:52:05 -0700 (PDT) Received: (from luigi@localhost) by info.iet.unipi.it (8.9.3/8.9.3) id PAA51220; Tue, 29 Aug 2000 15:52:06 +0200 (CEST) (envelope-from luigi) From: Luigi Rizzo Message-Id: <200008291352.PAA51220@info.iet.unipi.it> Subject: Re: Choices for TRACK/NACK report encoding In-Reply-To: <4.1.20000828143653.01ba80e0@mailhost.talarian.com> from Brian Whetten at "Aug 28, 2000 03:17:24 pm" To: Brian Whetten Date: Tue, 29 Aug 2000 15:52:06 +0200 (CEST) CC: rmt@lbl.gov X-Mailer: ELM [version 2.4ME+ PL61 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is > reasonably accurate for low values of P) mumble... wonder what did you use to compute the RLE bitmap size for p in the range 0.1 to 0.5 below... was that an actual encoding or just the result from the above formula (which might not apply given your comment above) note though that maybe it is not such a good idea to issue selective naks for >100 losses at once (or said it differently, gropus of 1000 pkts with a loss rate of 10% or more), so maybe we could limit our attention to a relatively small set of missing pkts irrespective of window size. cheers luigi > Note that as P approaches 1 (worst case, which we need to plan for), we get: > List=32*N > Bitmap=N > RLE Bitmap=Actually goes down (because we encode successes rather than > losses), with a worst case always less than either of the other two (but > approaching the bitmap case). > > Here are numeric results for these formulas, in bits, assuming N=1000. > > p List NACK Bitmap RLE Bitmap > 0.001 32 1000 10 > 0.0031 101 1000 28.5 > 0.01 320 1000 70 > 0.031 1012 1000 158.1 > 0.1 3200 1000 400 > 0.31 10119 1000 632 > 0.66 21120 1000 660 > 0.9 28800 1000 400 > > As you can see, List NACKs are better than a bitmap for P<3%, and worse > otherwise. A RLE bitmap is the most complicated to implement, but is also > the most efficient for all cases. > > A related topic to this is the idea of reliable NACKs. Taking PGM as an > example, it uses reliable NACKs, which make a lot of sense if none of these > encoding mechanisms are used, since there is no built in redundancy across > successive NACKs in that case. I think that NORM/PGM's biggest advantage > is being able to work without needing reliability mechanisms, which gives > these protocols better scalability in the face of failures. The reliable > NACKs actually go directly in the face of this, and increase the amount of > NACK implosion traffic that would occur when a network partition occurs. > > I believe that the need for reliable NACKs could be removed in NACK-only > protocols (as it is in TRACK oriented protocols) by reporting a full status > of all the non-stable packets. With a RLE mechanism, this scales very > nicely, and I think the overhead of adding the RLE mechanism would be less > than the complexity of reliable NACKs. > > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs > (they are basically the same thing, just generated at different times), > which use the same encoding format for their retransmission request > reports. I think that RLE encoded bitmaps should be used for this, since > the system needs to be stable even in the face of very high loss rates and > high data rates. > > Comments? > Brian > > From owner-rmt@listserv.lbl.gov Tue Aug 29 14:39:40 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA28285 for ; Tue, 29 Aug 2000 14:39:40 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id KAA03744; Tue, 29 Aug 2000 10:36:52 -0700 (PDT) Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA03740 for ; Tue, 29 Aug 2000 10:36:47 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA17422 for ; Tue, 29 Aug 2000 10:36:46 -0700 (PDT) Received: from mail.webfountain.com (mail.webfountain.com [63.161.54.5]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA17407 for ; Tue, 29 Aug 2000 10:36:45 -0700 (PDT) Received: from leningrad (gate.webfountain.com [63.161.54.3]) by mail.webfountain.com (8.9.3/8.9.3) with SMTP id KAA20092; Tue, 29 Aug 2000 10:23:15 -0700 X-Authentication-Warning: mail.webfountain.com: Host gate.webfountain.com [63.161.54.3] claimed to be leningrad From: "Mike Luby" To: "Luigi Rizzo" , "Brian Whetten" Cc: Subject: RE: Choices for TRACK/NACK report encoding Date: Tue, 29 Aug 2000 10:27:31 -0700 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 In-Reply-To: <200008291352.PAA51220@info.iet.unipi.it> Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit Is there an option to NACK based on FEC, i.e., to just give the number of missing packets (and which block they are from) instead of an explicit list of missing packets? Mike -----Original Message----- From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi Rizzo Sent: Tuesday, August 29, 2000 6:52 AM To: Brian Whetten Cc: rmt@lbl.gov Subject: Re: Choices for TRACK/NACK report encoding > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is > reasonably accurate for low values of P) mumble... wonder what did you use to compute the RLE bitmap size for p in the range 0.1 to 0.5 below... was that an actual encoding or just the result from the above formula (which might not apply given your comment above) note though that maybe it is not such a good idea to issue selective naks for >100 losses at once (or said it differently, gropus of 1000 pkts with a loss rate of 10% or more), so maybe we could limit our attention to a relatively small set of missing pkts irrespective of window size. cheers luigi > Note that as P approaches 1 (worst case, which we need to plan for), we get: > List=32*N > Bitmap=N > RLE Bitmap=Actually goes down (because we encode successes rather than > losses), with a worst case always less than either of the other two (but > approaching the bitmap case). > > Here are numeric results for these formulas, in bits, assuming N=1000. > > p List NACK Bitmap RLE Bitmap > 0.001 32 1000 10 > 0.0031 101 1000 28.5 > 0.01 320 1000 70 > 0.031 1012 1000 158.1 > 0.1 3200 1000 400 > 0.31 10119 1000 632 > 0.66 21120 1000 660 > 0.9 28800 1000 400 > > As you can see, List NACKs are better than a bitmap for P<3%, and worse > otherwise. A RLE bitmap is the most complicated to implement, but is also > the most efficient for all cases. > > A related topic to this is the idea of reliable NACKs. Taking PGM as an > example, it uses reliable NACKs, which make a lot of sense if none of these > encoding mechanisms are used, since there is no built in redundancy across > successive NACKs in that case. I think that NORM/PGM's biggest advantage > is being able to work without needing reliability mechanisms, which gives > these protocols better scalability in the face of failures. The reliable > NACKs actually go directly in the face of this, and increase the amount of > NACK implosion traffic that would occur when a network partition occurs. > > I believe that the need for reliable NACKs could be removed in NACK-only > protocols (as it is in TRACK oriented protocols) by reporting a full status > of all the non-stable packets. With a RLE mechanism, this scales very > nicely, and I think the overhead of adding the RLE mechanism would be less > than the complexity of reliable NACKs. > > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs > (they are basically the same thing, just generated at different times), > which use the same encoding format for their retransmission request > reports. I think that RLE encoded bitmaps should be used for this, since > the system needs to be stable even in the face of very high loss rates and > high data rates. > > Comments? > Brian > > From owner-rmt@listserv.lbl.gov Tue Aug 29 15:03:24 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA28780 for ; Tue, 29 Aug 2000 15:03:23 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id KAA03796; Tue, 29 Aug 2000 10:57:41 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA03792 for ; Tue, 29 Aug 2000 10:57:40 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA24824 for ; Tue, 29 Aug 2000 10:57:39 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id KAA24788 for ; Tue, 29 Aug 2000 10:57:33 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id KAA15504; Tue, 29 Aug 2000 10:57:05 -0700 (PDT) Message-Id: <4.1.20000829105244.01c0bb70@mailhost.talarian.com> Message-Id: <4.1.20000829105244.01c0bb70@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Tue, 29 Aug 2000 10:58:00 -0700 To: "Sukanta Ganguly" , From: Brian Whetten Subject: Re: Choices for TRACK/NACK report encoding In-Reply-To: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="=====================_260870902==_.ALT" Sender: owner-rmt@lbl.gov Precedence: bulk --=====================_260870902==_.ALT Content-Type: text/plain; charset="us-ascii" I'm glad you agree. 32 comes from the size of a sequence number. No, I'm not assuming that any sets of packets reach the sender without loss...that is part of the point of this. Most of the TRACK/NACK RMT protocols out there have the notion of a non-stable receiver window, which is the set of packets from the lost packet with lowest sequence packet that is still considered recoverable, up through the loss detected with the highest sequence number (or alternatively, up through the highest sequence number the receiver is aware of). The core idea is that if you only NACK individual packets, then there is no built in redundancy from NACK to NACK, and you have to build in a reliability mechanism for the NACKs. If you send up a compressed bitmap for the packets in the non-stable window, then you don't need to do this. This status is generated at the receivers, and passed up. (See TRAM or RMTP-II for details) Brian At 05:06 PM 8/28/2000 -0600, Sukanta Ganguly wrote: > > Brian, > Reliable NACK should not be the fact based on which the design should be > done. Scalability is the obvious probelm with it. So most of your assumptions > are correct. I don't quite understand how you came up with the overheads. I > also could not quite understand where did you get the 32 in the calculation. > However, what do you mean by full status of the non-stable packets? Where > is this full status generated? Are we assumming that the RLE data reaches the > target without any loss? > > SG > > >>> Brian Whetten 08/28/00 04:17PM >>> > Hi there, > A question just came up for me on how we should best do NACK (and TRACK) > encoding for the information that is sent up. I think there are two > primary ways that have been used so far: List NACKs (i.e. PGM) and bitmaps > (i.e. RMTP-II & TRAM). The other option, which hasn't been used yet but > has been discussed, is run length encoded bitmaps. > > I'd ideally like to see us use the same encoding format (as part of the > common data headers BB) for each. I ran a quick comparison of the overhead > of encoding a window of N packets, with a uniform loss rate of P. The > overhead for each option is: > > List NACK=32*N*P > Bitmap=N > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is > reasonably accurate for low values of P) > > Note that as P approaches 1 (worst case, which we need to plan for), we get: > List=32*N > Bitmap=N > RLE Bitmap=Actually goes down (because we encode successes rather than > losses), with a worst case always less than either of the other two (but > approaching the bitmap case). > > Here are numeric results for these formulas, in bits, assuming N=1000. > > p List NACK Bitmap RLE Bitmap > 0.001 32 1000 10 > 0.0031 101 1000 28.5 > 0.01 320 1000 70 > 0.031 1012 1000 158.1 > 0.1 3200 1000 400 > 0.31 10119 1000 632 > 0.66 21120 1000 660 > 0.9 28800 1000 400 > > As you can see, List NACKs are better than a bitmap for P<3%, and worse > otherwise. A RLE bitmap is the most complicated to implement, but is also > the most efficient for all cases. > > A related topic to this is the idea of reliable NACKs. Taking PGM as an > example, it uses reliable NACKs, which make a lot of sense if none of these > encoding mechanisms are used, since there is no built in redundancy across > successive NACKs in that case. I think that NORM/PGM's biggest advantage > is being able to work without needing reliability mechanisms, which gives > these protocols better scalability in the face of failures. The reliable > NACKs actually go directly in the face of this, and increase the amount of > NACK implosion traffic that would occur when a network partition occurs. > > I believe that the need for reliable NACKs could be removed in NACK-only > protocols (as it is in TRACK oriented protocols) by reporting a full status > of all the non-stable packets. With a RLE mechanism, this scales very > nicely, and I think the overhead of adding the RLE mechanism would be less > than the complexity of reliable NACKs. > > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs > (they are basically the same thing, just generated at different times), > which use the same encoding format for their retransmission request > reports. I think that RLE encoded bitmaps should be used for this, since > the system needs to be stable even in the face of very high loss rates and > high data rates. > > Comments? > Brian --=====================_260870902==_.ALT Content-Type: text/html; charset="us-ascii" I'm glad you agree.  32 comes from the size of a sequence number.  No, I'm not assuming that any sets of packets reach the sender without loss...that is part of the point of this.  Most of the TRACK/NACK RMT protocols out there have the notion of a non-stable receiver window, which is the set of packets from the lost packet with lowest sequence packet that is still considered recoverable, up through the loss detected with the highest sequence number (or alternatively, up through the highest sequence number the receiver is aware of). 

The core idea is that if you only NACK individual packets, then there is no built in redundancy from NACK to NACK, and you have to build in a reliability mechanism for the NACKs.  If you send up a compressed bitmap for the packets in the non-stable window, then you don't need to do this.  This status is generated at the receivers, and passed up.  (See TRAM or RMTP-II for details)

Brian

At 05:06 PM 8/28/2000 -0600, Sukanta Ganguly wrote:
Brian,
  Reliable NACK should not be the fact based on which the design should be done. Scalability is the obvious probelm with it. So most of your assumptions are correct. I don't quite understand how you came up with the overheads. I also could not quite understand where did you get the 32 in the calculation.
  However, what do you mean by full status of the non-stable packets? Where is this full status generated? Are we assumming that the RLE data reaches the target without any loss?
 
SG

>>> Brian Whetten <whetten@talarian.com> 08/28/00 04:17PM >>>
Hi there,
A question just came up for me on how we should best do NACK (and TRACK)
encoding for the information that is sent up.  I think there are two
primary ways that have been used so far:  List NACKs (i.e. PGM) and bitmaps
(i.e. RMTP-II & TRAM).  The other option, which hasn't been used yet but
has been discussed, is run length encoded bitmaps. 

I'd ideally like to see us use the same encoding format (as part of the
common data headers BB) for each.  I ran a quick comparison of the overhead
of encoding a window of N packets, with a uniform loss rate of P.  The
overhead for each option is:

List NACK=32*N*P
Bitmap=N
RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P  (I think this is
reasonably accurate for low values of P)

Note that as P approaches 1 (worst case, which we need to plan for), we get:
List=32*N
Bitmap=N
RLE Bitmap=Actually goes down (because we encode successes rather than
losses), with a worst case always less than either of the other two (but
approaching the bitmap case).

Here are numeric results for these formulas, in bits, assuming N=1000.

p        List NACK    Bitmap        RLE Bitmap
0.001        32        1000        10
0.0031    101        1000        28.5
0.01        320        1000        70
0.031        1012        1000        158.1
0.1        3200        1000        400
0.31        10119        1000        632
0.66        21120        1000        660
0.9        28800        1000        400

As you can see, List NACKs are better than a bitmap for P<3%, and worse
otherwise.  A RLE bitmap is the most complicated to implement, but is also
the most efficient for all cases.

A related topic to this is the idea of reliable NACKs.  Taking PGM as an
example, it uses reliable NACKs, which make a lot of sense if none of these
encoding mechanisms are used, since there is no built in redundancy across
successive NACKs in that case.  I think that NORM/PGM's biggest advantage
is being able to work without needing reliability mechanisms, which gives
these protocols better scalability in the face of failures.  The reliable
NACKs actually go directly in the face of this, and increase the amount of
NACK implosion traffic that would occur when a network partition occurs. 

I believe that the need for reliable NACKs could be removed in NACK-only
protocols (as it is in TRACK oriented protocols) by reporting a full status
of all the non-stable packets.  With a RLE mechanism, this scales very
nicely, and I think the overhead of adding the RLE mechanism would be less
than the complexity of reliable NACKs.

Conclusion:  I think we should standardize on non-reliable NACKs/TRACKs
(they are basically the same thing, just generated at different times),
which use the same encoding format for their retransmission request
reports.  I think that RLE encoded bitmaps should be used for this, since
the system needs to be stable even in the face of very high loss rates and
high data rates. 

Comments?
Brian


--=====================_260870902==_.ALT-- From owner-rmt@listserv.lbl.gov Tue Aug 29 15:17:28 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA29130 for ; Tue, 29 Aug 2000 15:17:28 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id LAA03872; Tue, 29 Aug 2000 11:13:05 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA03868 for ; Tue, 29 Aug 2000 11:13:03 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA00963 for ; Tue, 29 Aug 2000 11:13:02 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA00952 for ; Tue, 29 Aug 2000 11:13:01 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id LAA15999; Tue, 29 Aug 2000 11:12:03 -0700 (PDT) Message-Id: <4.1.20000829105816.01c12740@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Tue, 29 Aug 2000 11:10:35 -0700 To: Luigi Rizzo From: Brian Whetten Subject: Re: Choices for TRACK/NACK report encoding Cc: rmt@lbl.gov In-Reply-To: <200008291352.PAA51220@info.iet.unipi.it> References: <4.1.20000828143653.01ba80e0@mailhost.talarian.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk I just used the formula, which is only a quick and dirty approximation. I need to go back and freshen up on encoding/compression algorithms (Mike, I'm sure this is trivial for you...do you have a more accurate formula?). I think the issue of the # of packets you NACK is orthogonal to how you respond to the NACKs. It strikes me that we should always (within the bounds of efficiency) be striving to get as much information as possible to the sender, and then it is a different issue as to how those NACKs are dealt with. The rate of retransmissions needs to be explicitly considered by the congestion control BB. Also, in very high bandwidth-delay product networks, I think you may want to be NACKing 100 or more packets at a time in some cases...but again, this should be dealt with by congestion control. Brian At 03:52 PM 8/29/2000 +0200, Luigi Rizzo wrote: >> RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is >> reasonably accurate for low values of P) > >mumble... wonder what did you use to compute the RLE bitmap size >for p in the range 0.1 to 0.5 below... was that an actual >encoding or just the result from the above formula (which might >not apply given your comment above) > >note though that maybe it is not such a good idea to issue selective >naks for >100 losses at once (or said it differently, gropus of >1000 pkts with a loss rate of 10% or more), so maybe we could >limit our attention to a relatively small set of missing pkts >irrespective of window size. > > cheers > luigi > >> Note that as P approaches 1 (worst case, which we need to plan for), we get: >> List=32*N >> Bitmap=N >> RLE Bitmap=Actually goes down (because we encode successes rather than >> losses), with a worst case always less than either of the other two (but >> approaching the bitmap case). >> >> Here are numeric results for these formulas, in bits, assuming N=1000. >> >> p List NACK Bitmap RLE Bitmap >> 0.001 32 1000 10 >> 0.0031 101 1000 28.5 >> 0.01 320 1000 70 >> 0.031 1012 1000 158.1 >> 0.1 3200 1000 400 >> 0.31 10119 1000 632 >> 0.66 21120 1000 660 >> 0.9 28800 1000 400 >> >> As you can see, List NACKs are better than a bitmap for P<3%, and worse >> otherwise. A RLE bitmap is the most complicated to implement, but is also >> the most efficient for all cases. >> >> A related topic to this is the idea of reliable NACKs. Taking PGM as an >> example, it uses reliable NACKs, which make a lot of sense if none of these >> encoding mechanisms are used, since there is no built in redundancy across >> successive NACKs in that case. I think that NORM/PGM's biggest advantage >> is being able to work without needing reliability mechanisms, which gives >> these protocols better scalability in the face of failures. The reliable >> NACKs actually go directly in the face of this, and increase the amount of >> NACK implosion traffic that would occur when a network partition occurs. >> >> I believe that the need for reliable NACKs could be removed in NACK-only >> protocols (as it is in TRACK oriented protocols) by reporting a full status >> of all the non-stable packets. With a RLE mechanism, this scales very >> nicely, and I think the overhead of adding the RLE mechanism would be less >> than the complexity of reliable NACKs. >> >> Conclusion: I think we should standardize on non-reliable NACKs/TRACKs >> (they are basically the same thing, just generated at different times), >> which use the same encoding format for their retransmission request >> reports. I think that RLE encoded bitmaps should be used for this, since >> the system needs to be stable even in the face of very high loss rates and >> high data rates. >> >> Comments? >> Brian >> >> > From owner-rmt@listserv.lbl.gov Tue Aug 29 15:27:28 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA29389 for ; Tue, 29 Aug 2000 15:27:28 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id LAA03878; Tue, 29 Aug 2000 11:13:37 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA03874 for ; Tue, 29 Aug 2000 11:13:35 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA01156 for ; Tue, 29 Aug 2000 11:13:35 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA01153 for ; Tue, 29 Aug 2000 11:13:34 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id LAA16003; Tue, 29 Aug 2000 11:12:04 -0700 (PDT) Message-Id: <4.1.20000829111049.01c18920@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Tue, 29 Aug 2000 11:14:45 -0700 To: "Mike Luby" , "Luigi Rizzo" From: Brian Whetten Subject: RE: Choices for TRACK/NACK report encoding Cc: In-Reply-To: References: <200008291352.PAA51220@info.iet.unipi.it> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk Hi there, We certainly need to be able to send this information up. If the sender knows the FEC window boundaries, then I believe the FEC information can be extracted from the bitmap (another reason to use a compressed bitmap). So unless the FEC coding windows were as a common case quite large, I'm not sure that the added complexity of offering an explicit count per window option would be worth it, at least for NACK/TRACK protocols. Brain At 10:27 AM 8/29/2000 -0700, Mike Luby wrote: >Is there an option to NACK based on FEC, i.e., to just give the number of >missing packets (and which block they are from) instead of an explicit list >of missing packets? >Mike > >-----Original Message----- >From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi >Rizzo >Sent: Tuesday, August 29, 2000 6:52 AM >To: Brian Whetten >Cc: rmt@lbl.gov >Subject: Re: Choices for TRACK/NACK report encoding > > >> RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is >> reasonably accurate for low values of P) > >mumble... wonder what did you use to compute the RLE bitmap size >for p in the range 0.1 to 0.5 below... was that an actual >encoding or just the result from the above formula (which might >not apply given your comment above) > >note though that maybe it is not such a good idea to issue selective >naks for >100 losses at once (or said it differently, gropus of >1000 pkts with a loss rate of 10% or more), so maybe we could >limit our attention to a relatively small set of missing pkts >irrespective of window size. > > cheers > luigi > >> Note that as P approaches 1 (worst case, which we need to plan for), we >get: >> List=32*N >> Bitmap=N >> RLE Bitmap=Actually goes down (because we encode successes rather than >> losses), with a worst case always less than either of the other two (but >> approaching the bitmap case). >> >> Here are numeric results for these formulas, in bits, assuming N=1000. >> >> p List NACK Bitmap RLE Bitmap >> 0.001 32 1000 10 >> 0.0031 101 1000 28.5 >> 0.01 320 1000 70 >> 0.031 1012 1000 158.1 >> 0.1 3200 1000 400 >> 0.31 10119 1000 632 >> 0.66 21120 1000 660 >> 0.9 28800 1000 400 >> >> As you can see, List NACKs are better than a bitmap for P<3%, and worse >> otherwise. A RLE bitmap is the most complicated to implement, but is also >> the most efficient for all cases. >> >> A related topic to this is the idea of reliable NACKs. Taking PGM as an >> example, it uses reliable NACKs, which make a lot of sense if none of >these >> encoding mechanisms are used, since there is no built in redundancy across >> successive NACKs in that case. I think that NORM/PGM's biggest advantage >> is being able to work without needing reliability mechanisms, which gives >> these protocols better scalability in the face of failures. The reliable >> NACKs actually go directly in the face of this, and increase the amount of >> NACK implosion traffic that would occur when a network partition occurs. >> >> I believe that the need for reliable NACKs could be removed in NACK-only >> protocols (as it is in TRACK oriented protocols) by reporting a full >status >> of all the non-stable packets. With a RLE mechanism, this scales very >> nicely, and I think the overhead of adding the RLE mechanism would be less >> than the complexity of reliable NACKs. >> >> Conclusion: I think we should standardize on non-reliable NACKs/TRACKs >> (they are basically the same thing, just generated at different times), >> which use the same encoding format for their retransmission request >> reports. I think that RLE encoded bitmaps should be used for this, since >> the system needs to be stable even in the face of very high loss rates and >> high data rates. >> >> Comments? >> Brian >> >> > > From owner-rmt@listserv.lbl.gov Tue Aug 29 16:02:22 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA00126 for ; Tue, 29 Aug 2000 16:02:21 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id LAA04066; Tue, 29 Aug 2000 11:57:25 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA04062 for ; Tue, 29 Aug 2000 11:57:23 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA15929 for ; Tue, 29 Aug 2000 11:57:22 -0700 (PDT) Received: from nard.net (nard.net [63.66.160.50]) by SpamWall.lbl.gov (8.9.3/8.9.3) with SMTP id LAA15915 for ; Tue, 29 Aug 2000 11:57:21 -0700 (PDT) Received: (qmail 2754 invoked by uid 500); 29 Aug 2000 18:59:56 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 29 Aug 2000 18:59:56 -0000 Date: Tue, 29 Aug 2000 14:59:56 -0400 (EDT) From: "Todd L. Montgomery" X-Sender: tmont@cartman.nard.net To: Mike Luby cc: Luigi Rizzo , Brian Whetten , rmt@lbl.gov Subject: RE: Choices for TRACK/NACK report encoding In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-rmt@lbl.gov Precedence: bulk I hope there is. PGMs FEC adds a nice feature that allows a block to report it's loss count and pack that into a 32-bit number no matter how big the block. That is a LOT smaller with List NAKs than a bitmap can be. To do this, the block size (in packets) must be a power of 2, but that is not very restrictive. On Tue, 29 Aug 2000, Mike Luby wrote: > Is there an option to NACK based on FEC, i.e., to just give the number of > missing packets (and which block they are from) instead of an explicit list > of missing packets? > Mike > > -----Original Message----- > From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi > Rizzo > Sent: Tuesday, August 29, 2000 6:52 AM > To: Brian Whetten > Cc: rmt@lbl.gov > Subject: Re: Choices for TRACK/NACK report encoding > > > > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is > > reasonably accurate for low values of P) > > mumble... wonder what did you use to compute the RLE bitmap size > for p in the range 0.1 to 0.5 below... was that an actual > encoding or just the result from the above formula (which might > not apply given your comment above) > > note though that maybe it is not such a good idea to issue selective > naks for >100 losses at once (or said it differently, gropus of > 1000 pkts with a loss rate of 10% or more), so maybe we could > limit our attention to a relatively small set of missing pkts > irrespective of window size. > > cheers > luigi > > > Note that as P approaches 1 (worst case, which we need to plan for), we > get: > > List=32*N > > Bitmap=N > > RLE Bitmap=Actually goes down (because we encode successes rather than > > losses), with a worst case always less than either of the other two (but > > approaching the bitmap case). > > > > Here are numeric results for these formulas, in bits, assuming N=1000. > > > > p List NACK Bitmap RLE Bitmap > > 0.001 32 1000 10 > > 0.0031 101 1000 28.5 > > 0.01 320 1000 70 > > 0.031 1012 1000 158.1 > > 0.1 3200 1000 400 > > 0.31 10119 1000 632 > > 0.66 21120 1000 660 > > 0.9 28800 1000 400 > > > > As you can see, List NACKs are better than a bitmap for P<3%, and worse > > otherwise. A RLE bitmap is the most complicated to implement, but is also > > the most efficient for all cases. > > > > A related topic to this is the idea of reliable NACKs. Taking PGM as an > > example, it uses reliable NACKs, which make a lot of sense if none of > these > > encoding mechanisms are used, since there is no built in redundancy across > > successive NACKs in that case. I think that NORM/PGM's biggest advantage > > is being able to work without needing reliability mechanisms, which gives > > these protocols better scalability in the face of failures. The reliable > > NACKs actually go directly in the face of this, and increase the amount of > > NACK implosion traffic that would occur when a network partition occurs. > > > > I believe that the need for reliable NACKs could be removed in NACK-only > > protocols (as it is in TRACK oriented protocols) by reporting a full > status > > of all the non-stable packets. With a RLE mechanism, this scales very > > nicely, and I think the overhead of adding the RLE mechanism would be less > > than the complexity of reliable NACKs. > > > > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs > > (they are basically the same thing, just generated at different times), > > which use the same encoding format for their retransmission request > > reports. I think that RLE encoded bitmaps should be used for this, since > > the system needs to be stable even in the face of very high loss rates and > > high data rates. > > > > Comments? > > Brian > > > > > > -- Todd L. Montgomery Talarian Corporation 304-291-5972 todd@talarian.com From owner-rmt@listserv.lbl.gov Tue Aug 29 16:46:17 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA00725 for ; Tue, 29 Aug 2000 16:46:16 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id MAA04295; Tue, 29 Aug 2000 12:45:29 -0700 (PDT) Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA04291 for ; Tue, 29 Aug 2000 12:45:28 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA29190 for ; Tue, 29 Aug 2000 12:45:27 -0700 (PDT) Received: from mail.webfountain.com (mail.webfountain.com [63.161.54.5]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA29180 for ; Tue, 29 Aug 2000 12:45:26 -0700 (PDT) Received: from leningrad (gate.webfountain.com [63.161.54.3]) by mail.webfountain.com (8.9.3/8.9.3) with SMTP id MAA26186; Tue, 29 Aug 2000 12:32:13 -0700 X-Authentication-Warning: mail.webfountain.com: Host gate.webfountain.com [63.161.54.3] claimed to be leningrad From: "Mike Luby" To: "Todd L. Montgomery" Cc: "Luigi Rizzo" , "Brian Whetten" , Subject: RE: Choices for TRACK/NACK report encoding Date: Tue, 29 Aug 2000 12:36:29 -0700 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 In-Reply-To: Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit As design goals, it would seem to be desirable: (1) That explicit packets can be NACKed per block. (2) That a count of packets can be NACKed per block. (3) That the mechanisms that achieve (1) and (2) are compatible with each other. (4) That the mechanisms would work relatively efficiently independent of the loss per block or the size of the block. (a) Would be desirable to work with small as well as large blocks (in terms of number of packets per block). (b) Would be desirable that the block size in packets doesn't have to fit any special requirements, e.g., be a power of 2. (c) Would be desirable that the scheme would scale with the number of losses per block, in particular when the report is a count then one should report any number between 0 and the size of the block in packets. Do these goals make sense, and how would people prioritize these goals, and are there other goals that are even more important that are missing? Once the goals and their relative priority are clear, then the design may just fall out as a natural consequence. Mike -----Original Message----- From: Todd L. Montgomery [mailto:todd@talarian.com] Sent: Tuesday, August 29, 2000 12:00 PM To: Mike Luby Cc: Luigi Rizzo; Brian Whetten; rmt@lbl.gov Subject: RE: Choices for TRACK/NACK report encoding I hope there is. PGMs FEC adds a nice feature that allows a block to report it's loss count and pack that into a 32-bit number no matter how big the block. That is a LOT smaller with List NAKs than a bitmap can be. To do this, the block size (in packets) must be a power of 2, but that is not very restrictive. On Tue, 29 Aug 2000, Mike Luby wrote: > Is there an option to NACK based on FEC, i.e., to just give the number of > missing packets (and which block they are from) instead of an explicit list > of missing packets? > Mike > > -----Original Message----- > From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi > Rizzo > Sent: Tuesday, August 29, 2000 6:52 AM > To: Brian Whetten > Cc: rmt@lbl.gov > Subject: Re: Choices for TRACK/NACK report encoding > > > > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is > > reasonably accurate for low values of P) > > mumble... wonder what did you use to compute the RLE bitmap size > for p in the range 0.1 to 0.5 below... was that an actual > encoding or just the result from the above formula (which might > not apply given your comment above) > > note though that maybe it is not such a good idea to issue selective > naks for >100 losses at once (or said it differently, gropus of > 1000 pkts with a loss rate of 10% or more), so maybe we could > limit our attention to a relatively small set of missing pkts > irrespective of window size. > > cheers > luigi > > > Note that as P approaches 1 (worst case, which we need to plan for), we > get: > > List=32*N > > Bitmap=N > > RLE Bitmap=Actually goes down (because we encode successes rather than > > losses), with a worst case always less than either of the other two (but > > approaching the bitmap case). > > > > Here are numeric results for these formulas, in bits, assuming N=1000. > > > > p List NACK Bitmap RLE Bitmap > > 0.001 32 1000 10 > > 0.0031 101 1000 28.5 > > 0.01 320 1000 70 > > 0.031 1012 1000 158.1 > > 0.1 3200 1000 400 > > 0.31 10119 1000 632 > > 0.66 21120 1000 660 > > 0.9 28800 1000 400 > > > > As you can see, List NACKs are better than a bitmap for P<3%, and worse > > otherwise. A RLE bitmap is the most complicated to implement, but is also > > the most efficient for all cases. > > > > A related topic to this is the idea of reliable NACKs. Taking PGM as an > > example, it uses reliable NACKs, which make a lot of sense if none of > these > > encoding mechanisms are used, since there is no built in redundancy across > > successive NACKs in that case. I think that NORM/PGM's biggest advantage > > is being able to work without needing reliability mechanisms, which gives > > these protocols better scalability in the face of failures. The reliable > > NACKs actually go directly in the face of this, and increase the amount of > > NACK implosion traffic that would occur when a network partition occurs. > > > > I believe that the need for reliable NACKs could be removed in NACK-only > > protocols (as it is in TRACK oriented protocols) by reporting a full > status > > of all the non-stable packets. With a RLE mechanism, this scales very > > nicely, and I think the overhead of adding the RLE mechanism would be less > > than the complexity of reliable NACKs. > > > > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs > > (they are basically the same thing, just generated at different times), > > which use the same encoding format for their retransmission request > > reports. I think that RLE encoded bitmaps should be used for this, since > > the system needs to be stable even in the face of very high loss rates and > > high data rates. > > > > Comments? > > Brian > > > > > > -- Todd L. Montgomery Talarian Corporation 304-291-5972 todd@talarian.com From owner-rmt@listserv.lbl.gov Tue Aug 29 19:00:32 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id TAA02363 for ; Tue, 29 Aug 2000 19:00:32 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id OAA04851; Tue, 29 Aug 2000 14:58:51 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA04847 for ; Tue, 29 Aug 2000 14:58:49 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA12656 for ; Tue, 29 Aug 2000 14:58:49 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA12643 for ; Tue, 29 Aug 2000 14:58:47 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id OAA22617; Tue, 29 Aug 2000 14:57:14 -0700 (PDT) Message-Id: <4.1.20000829143701.01ba2b70@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Tue, 29 Aug 2000 14:46:10 -0700 To: "Mike Luby" , "Todd L. Montgomery" From: Brian Whetten Subject: RE: Choices for TRACK/NACK report encoding Cc: "Luigi Rizzo" , In-Reply-To: References: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk I would add: (5) Being able to efficiently encode as many losses across as many blocks as possible. i.e. being able to report a history of outstanding lost packets, rather than just the most recent ones. (6) Simplicity (7) Being stable in the face of very high loss rates, either of data packets and/or NACK packets. I would prioritize 1,2,6,7 as having the highest importance. Brian At 12:36 PM 8/29/2000 -0700, Mike Luby wrote: >As design goals, it would seem to be desirable: > >(1) That explicit packets can be NACKed per block. >(2) That a count of packets can be NACKed per block. >(3) That the mechanisms that achieve (1) and (2) are compatible with each >other. >(4) That the mechanisms would work relatively efficiently independent of the >loss per block or the size of the block. > (a) Would be desirable to work with small as well as large blocks (in >terms of number of packets per block). > (b) Would be desirable that the block size in packets doesn't have to >fit any special requirements, e.g., be a power of 2. > (c) Would be desirable that the scheme would scale with the number of >losses per block, in particular when the report is a count then one should >report any number between 0 and the size of the block in packets. > >Do these goals make sense, and how would people prioritize these goals, and >are there other goals that are even more important that are missing? Once >the goals and their relative priority are clear, then the design may just >fall out as a natural consequence. >Mike > >-----Original Message----- >From: Todd L. Montgomery [mailto:todd@talarian.com] >Sent: Tuesday, August 29, 2000 12:00 PM >To: Mike Luby >Cc: Luigi Rizzo; Brian Whetten; rmt@lbl.gov >Subject: RE: Choices for TRACK/NACK report encoding > > > >I hope there is. PGMs FEC adds a nice feature that allows a block >to report it's loss count and pack that into a 32-bit number >no matter how big the block. That is a LOT smaller with List NAKs >than a bitmap can be. > >To do this, the block size (in packets) must be a power of 2, but that is >not very restrictive. > >On Tue, 29 Aug 2000, Mike Luby wrote: > >> Is there an option to NACK based on FEC, i.e., to just give the number of >> missing packets (and which block they are from) instead of an explicit >list >> of missing packets? >> Mike >> >> -----Original Message----- >> From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi >> Rizzo >> Sent: Tuesday, August 29, 2000 6:52 AM >> To: Brian Whetten >> Cc: rmt@lbl.gov >> Subject: Re: Choices for TRACK/NACK report encoding >> >> >> > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is >> > reasonably accurate for low values of P) >> >> mumble... wonder what did you use to compute the RLE bitmap size >> for p in the range 0.1 to 0.5 below... was that an actual >> encoding or just the result from the above formula (which might >> not apply given your comment above) >> >> note though that maybe it is not such a good idea to issue selective >> naks for >100 losses at once (or said it differently, gropus of >> 1000 pkts with a loss rate of 10% or more), so maybe we could >> limit our attention to a relatively small set of missing pkts >> irrespective of window size. >> >> cheers >> luigi >> >> > Note that as P approaches 1 (worst case, which we need to plan for), we >> get: >> > List=32*N >> > Bitmap=N >> > RLE Bitmap=Actually goes down (because we encode successes rather than >> > losses), with a worst case always less than either of the other two (but >> > approaching the bitmap case). >> > >> > Here are numeric results for these formulas, in bits, assuming N=1000. >> > >> > p List NACK Bitmap RLE Bitmap >> > 0.001 32 1000 10 >> > 0.0031 101 1000 28.5 >> > 0.01 320 1000 70 >> > 0.031 1012 1000 158.1 >> > 0.1 3200 1000 400 >> > 0.31 10119 1000 632 >> > 0.66 21120 1000 660 >> > 0.9 28800 1000 400 >> > >> > As you can see, List NACKs are better than a bitmap for P<3%, and worse >> > otherwise. A RLE bitmap is the most complicated to implement, but is >also >> > the most efficient for all cases. >> > >> > A related topic to this is the idea of reliable NACKs. Taking PGM as an >> > example, it uses reliable NACKs, which make a lot of sense if none of >> these >> > encoding mechanisms are used, since there is no built in redundancy >across >> > successive NACKs in that case. I think that NORM/PGM's biggest >advantage >> > is being able to work without needing reliability mechanisms, which >gives >> > these protocols better scalability in the face of failures. The >reliable >> > NACKs actually go directly in the face of this, and increase the amount >of >> > NACK implosion traffic that would occur when a network partition occurs. >> > >> > I believe that the need for reliable NACKs could be removed in NACK-only >> > protocols (as it is in TRACK oriented protocols) by reporting a full >> status >> > of all the non-stable packets. With a RLE mechanism, this scales very >> > nicely, and I think the overhead of adding the RLE mechanism would be >less >> > than the complexity of reliable NACKs. >> > >> > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs >> > (they are basically the same thing, just generated at different times), >> > which use the same encoding format for their retransmission request >> > reports. I think that RLE encoded bitmaps should be used for this, >since >> > the system needs to be stable even in the face of very high loss rates >and >> > high data rates. >> > >> > Comments? >> > Brian >> > >> > >> >> > >-- >Todd L. Montgomery >Talarian Corporation >304-291-5972 >todd@talarian.com > > From owner-rmt@listserv.lbl.gov Tue Aug 29 20:03:47 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA03151 for ; Tue, 29 Aug 2000 20:03:46 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id QAA05190; Tue, 29 Aug 2000 16:09:21 -0700 (PDT) Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA05186 for ; Tue, 29 Aug 2000 16:09:19 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA04329 for ; Tue, 29 Aug 2000 16:09:19 -0700 (PDT) Received: from mail.webfountain.com (mail.webfountain.com [63.161.54.5]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA04325 for ; Tue, 29 Aug 2000 16:09:18 -0700 (PDT) Received: from leningrad (gate.webfountain.com [63.161.54.3]) by mail.webfountain.com (8.9.3/8.9.3) with SMTP id PAA01934; Tue, 29 Aug 2000 15:55:58 -0700 X-Authentication-Warning: mail.webfountain.com: Host gate.webfountain.com [63.161.54.3] claimed to be leningrad From: "Mike Luby" To: "Brian Whetten" , "Todd L. Montgomery" Cc: "Luigi Rizzo" , Subject: RE: Choices for TRACK/NACK report encoding Date: Tue, 29 Aug 2000 16:00:14 -0700 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0) Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 In-Reply-To: <4.1.20000829143701.01ba2b70@mailhost.talarian.com> Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit The additional design goals make sense. I would prioritize almost the same: (1,2),6,(4,7),5,3. (Parenthesis enclose goals of similar priority). Given this, the question then is: does a NACK scheme that meets these goals in this priority order jump out? (My only goal was to drive the design process starting from the goals, not from the mechanisms. This may be where I stop contributing.) Mike -----Original Message----- From: Brian Whetten [mailto:whetten@talarian.com] Sent: Tuesday, August 29, 2000 2:46 PM To: Mike Luby; Todd L. Montgomery Cc: Luigi Rizzo; rmt@lbl.gov Subject: RE: Choices for TRACK/NACK report encoding I would add: (5) Being able to efficiently encode as many losses across as many blocks as possible. i.e. being able to report a history of outstanding lost packets, rather than just the most recent ones. (6) Simplicity (7) Being stable in the face of very high loss rates, either of data packets and/or NACK packets. I would prioritize 1,2,6,7 as having the highest importance. Brian At 12:36 PM 8/29/2000 -0700, Mike Luby wrote: >As design goals, it would seem to be desirable: > >(1) That explicit packets can be NACKed per block. >(2) That a count of packets can be NACKed per block. >(3) That the mechanisms that achieve (1) and (2) are compatible with each >other. >(4) That the mechanisms would work relatively efficiently independent of the >loss per block or the size of the block. > (a) Would be desirable to work with small as well as large blocks (in >terms of number of packets per block). > (b) Would be desirable that the block size in packets doesn't have to >fit any special requirements, e.g., be a power of 2. > (c) Would be desirable that the scheme would scale with the number of >losses per block, in particular when the report is a count then one should >report any number between 0 and the size of the block in packets. > >Do these goals make sense, and how would people prioritize these goals, and >are there other goals that are even more important that are missing? Once >the goals and their relative priority are clear, then the design may just >fall out as a natural consequence. >Mike > >-----Original Message----- >From: Todd L. Montgomery [mailto:todd@talarian.com] >Sent: Tuesday, August 29, 2000 12:00 PM >To: Mike Luby >Cc: Luigi Rizzo; Brian Whetten; rmt@lbl.gov >Subject: RE: Choices for TRACK/NACK report encoding > > > >I hope there is. PGMs FEC adds a nice feature that allows a block >to report it's loss count and pack that into a 32-bit number >no matter how big the block. That is a LOT smaller with List NAKs >than a bitmap can be. > >To do this, the block size (in packets) must be a power of 2, but that is >not very restrictive. > >On Tue, 29 Aug 2000, Mike Luby wrote: > >> Is there an option to NACK based on FEC, i.e., to just give the number of >> missing packets (and which block they are from) instead of an explicit >list >> of missing packets? >> Mike >> >> -----Original Message----- >> From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi >> Rizzo >> Sent: Tuesday, August 29, 2000 6:52 AM >> To: Brian Whetten >> Cc: rmt@lbl.gov >> Subject: Re: Choices for TRACK/NACK report encoding >> >> >> > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is >> > reasonably accurate for low values of P) >> >> mumble... wonder what did you use to compute the RLE bitmap size >> for p in the range 0.1 to 0.5 below... was that an actual >> encoding or just the result from the above formula (which might >> not apply given your comment above) >> >> note though that maybe it is not such a good idea to issue selective >> naks for >100 losses at once (or said it differently, gropus of >> 1000 pkts with a loss rate of 10% or more), so maybe we could >> limit our attention to a relatively small set of missing pkts >> irrespective of window size. >> >> cheers >> luigi >> >> > Note that as P approaches 1 (worst case, which we need to plan for), we >> get: >> > List=32*N >> > Bitmap=N >> > RLE Bitmap=Actually goes down (because we encode successes rather than >> > losses), with a worst case always less than either of the other two (but >> > approaching the bitmap case). >> > >> > Here are numeric results for these formulas, in bits, assuming N=1000. >> > >> > p List NACK Bitmap RLE Bitmap >> > 0.001 32 1000 10 >> > 0.0031 101 1000 28.5 >> > 0.01 320 1000 70 >> > 0.031 1012 1000 158.1 >> > 0.1 3200 1000 400 >> > 0.31 10119 1000 632 >> > 0.66 21120 1000 660 >> > 0.9 28800 1000 400 >> > >> > As you can see, List NACKs are better than a bitmap for P<3%, and worse >> > otherwise. A RLE bitmap is the most complicated to implement, but is >also >> > the most efficient for all cases. >> > >> > A related topic to this is the idea of reliable NACKs. Taking PGM as an >> > example, it uses reliable NACKs, which make a lot of sense if none of >> these >> > encoding mechanisms are used, since there is no built in redundancy >across >> > successive NACKs in that case. I think that NORM/PGM's biggest >advantage >> > is being able to work without needing reliability mechanisms, which >gives >> > these protocols better scalability in the face of failures. The >reliable >> > NACKs actually go directly in the face of this, and increase the amount >of >> > NACK implosion traffic that would occur when a network partition occurs. >> > >> > I believe that the need for reliable NACKs could be removed in NACK-only >> > protocols (as it is in TRACK oriented protocols) by reporting a full >> status >> > of all the non-stable packets. With a RLE mechanism, this scales very >> > nicely, and I think the overhead of adding the RLE mechanism would be >less >> > than the complexity of reliable NACKs. >> > >> > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs >> > (they are basically the same thing, just generated at different times), >> > which use the same encoding format for their retransmission request >> > reports. I think that RLE encoded bitmaps should be used for this, >since >> > the system needs to be stable even in the face of very high loss rates >and >> > high data rates. >> > >> > Comments? >> > Brian >> > >> > >> >> > >-- >Todd L. Montgomery >Talarian Corporation >304-291-5972 >todd@talarian.com > > From owner-rmt@listserv.lbl.gov Tue Aug 29 21:26:37 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id VAA04011 for ; Tue, 29 Aug 2000 21:26:36 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id RAA05454; Tue, 29 Aug 2000 17:28:55 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA05450 for ; Tue, 29 Aug 2000 17:28:53 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA23564 for ; Tue, 29 Aug 2000 17:28:53 -0700 (PDT) Received: from phobos.talarian.com (mailhost.talarian.com [207.5.32.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA23560 for ; Tue, 29 Aug 2000 17:28:52 -0700 (PDT) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id RAA25891; Tue, 29 Aug 2000 17:27:13 -0700 (PDT) Message-Id: <4.1.20000829163742.01c18540@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Tue, 29 Aug 2000 17:21:36 -0700 To: "Mike Luby" , "Todd L. Montgomery" From: Brian Whetten Subject: RE: Choices for TRACK/NACK report encoding Cc: "Luigi Rizzo" , In-Reply-To: References: <4.1.20000829143701.01ba2b70@mailhost.talarian.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk This was a good contribution. Thanks, Mike. As always, I was assuming everyone already agreed on the design principles and was just throwing out potential solutions. :) Todd had a good point about being able to encode the number of lost packets in a block very efficiently. I've added another column for this, which I'll title block count. I model its overhead as: Block Count=32*n/b*(1-(1-p)^b), where n=number of packets in the encoded window, b is the size of the FEC block, and p is the probability for loss. I ran three cases, for b=8, 32, and 128. I actually think that smaller block sizes will most often be used for NACK/TRACK based protocols, since otherwise you would likely use the ALC scheme instead. Again, for RLE it is probably off by up to a factor of 2 for the middle cases due to my rough model used. For b=8, the block count is only marginally better than a straight list NACK until the loss rate gets above 10%, and is still worse than bitmap at that point. For b=32, the block count method is approximatley equal to the list for low loss rates, and equal to bitmap for high loss rates, which is a desireable combination. For b=128, Block Count is the most efficient. For B=8 or B=32, RLE still appears to be the most efficient. Going by your prioritization list: - I believe that all of these EXCEPT for List NACKs can easily meet #1 and #2, and therefore also #3. List NACKs has to be combined with one of the others to meet these requirements. Again, this assumes that the sender can derive block counts from a complete bitmap list. - In terms of #6 (simplicity), I believe that RLE is the most complex of the four, and that any single one is less complex than having to specify and implement any two of the others. I think that List NACKs bring higher reliance on reliable NACK mechanisms, which (in terms relative to the complexity of these mechanisms) are very complex. - In terms of #4 and #7 (efficiency in all/worst cases), I think that RLE best meets these requirements, because it works efficiently with b=1 (no FEC, which is a common case we need to be concerned with), b=8, and b=128. The only scenario where it is not the best (again, given my rough model for RLE) is when both p and b are large (p>=10% and b>=64). - For #5, Bitmap and RLE satisfy this, the others don't. So, I think that RLE is the best of the mechanisms proposed, given this analysis and set of requirements. The complexity of having to do two encoding schemes and/or reliable NACKs, combined with its efficiency, is what recommends it to me. Comments? Any mistakes I've made? Brian Tables: b p List Bitmap RLE Block Count 8 0.001 32 1000 10 32 8 0.003 101 1000 28 100 8 0.010 320 1000 70 309 8 0.032 1012 1000 158 907 8 0.100 3200 1000 400 2278 8 0.316 10119 1000 632 3809 8 0.500 16000 1000 500 3984 8 0.660 21120 1000 660 3999 8 0.900 28800 1000 400 4000 b p List Bitmap RLE Block Count 32 0.001 32 1000 10 32 32 0.003 101 1000 28 96 32 0.010 320 1000 70 275 32 0.032 1012 1000 158 642 32 0.100 3200 1000 400 966 32 0.316 10119 1000 632 1000 32 0.500 16000 1000 500 1000 32 0.660 21120 1000 660 1000 32 0.900 28800 1000 400 1000 b p List Bitmap RLE Block Count 128 0.001 32 1000 10 30 128 0.003 101 1000 28 83 128 0.010 320 1000 70 181 128 0.032 1012 1000 158 246 128 0.100 3200 1000 400 250 128 0.316 10119 1000 632 250 128 0.500 16000 1000 500 250 128 0.660 21120 1000 660 250 128 0.900 28800 1000 400 250 At 04:00 PM 8/29/2000 -0700, Mike Luby wrote: >The additional design goals make sense. I would prioritize almost the same: > >(1,2),6,(4,7),5,3. > >(Parenthesis enclose goals of similar priority). Given this, the question >then is: does a NACK scheme that meets these goals in this priority order >jump out? (My only goal was to drive the design process starting from the >goals, not from the mechanisms. This may be where I stop contributing.) > >Mike > >-----Original Message----- >From: Brian Whetten [mailto:whetten@talarian.com] >Sent: Tuesday, August 29, 2000 2:46 PM >To: Mike Luby; Todd L. Montgomery >Cc: Luigi Rizzo; rmt@lbl.gov >Subject: RE: Choices for TRACK/NACK report encoding > > >I would add: >(5) Being able to efficiently encode as many losses across as many blocks >as possible. i.e. being able to report a history of outstanding lost >packets, rather than just the most recent ones. >(6) Simplicity >(7) Being stable in the face of very high loss rates, either of data >packets and/or NACK packets. > >I would prioritize 1,2,6,7 as having the highest importance. > >Brian > >At 12:36 PM 8/29/2000 -0700, Mike Luby wrote: >>As design goals, it would seem to be desirable: >> >>(1) That explicit packets can be NACKed per block. >>(2) That a count of packets can be NACKed per block. >>(3) That the mechanisms that achieve (1) and (2) are compatible with each >>other. >>(4) That the mechanisms would work relatively efficiently independent of >the >>loss per block or the size of the block. >> (a) Would be desirable to work with small as well as large blocks (in >>terms of number of packets per block). >> (b) Would be desirable that the block size in packets doesn't have to >>fit any special requirements, e.g., be a power of 2. >> (c) Would be desirable that the scheme would scale with the number of >>losses per block, in particular when the report is a count then one should >>report any number between 0 and the size of the block in packets. >> >>Do these goals make sense, and how would people prioritize these goals, and >>are there other goals that are even more important that are missing? Once >>the goals and their relative priority are clear, then the design may just >>fall out as a natural consequence. >>Mike >> >>-----Original Message----- >>From: Todd L. Montgomery [mailto:todd@talarian.com] >>Sent: Tuesday, August 29, 2000 12:00 PM >>To: Mike Luby >>Cc: Luigi Rizzo; Brian Whetten; rmt@lbl.gov >>Subject: RE: Choices for TRACK/NACK report encoding >> >> >> >>I hope there is. PGMs FEC adds a nice feature that allows a block >>to report it's loss count and pack that into a 32-bit number >>no matter how big the block. That is a LOT smaller with List NAKs >>than a bitmap can be. >> >>To do this, the block size (in packets) must be a power of 2, but that is >>not very restrictive. >> >>On Tue, 29 Aug 2000, Mike Luby wrote: >> >>> Is there an option to NACK based on FEC, i.e., to just give the number of >>> missing packets (and which block they are from) instead of an explicit >>list >>> of missing packets? >>> Mike >>> >>> -----Original Message----- >>> From: owner-rmt@lbl.gov [mailto:owner-rmt@lbl.gov]On Behalf Of Luigi >>> Rizzo >>> Sent: Tuesday, August 29, 2000 6:52 AM >>> To: Brian Whetten >>> Cc: rmt@lbl.gov >>> Subject: Re: Choices for TRACK/NACK report encoding >>> >>> >>> > RLE Bitmap=approximately Ceiling(Log2(1/P))*N*P (I think this is >>> > reasonably accurate for low values of P) >>> >>> mumble... wonder what did you use to compute the RLE bitmap size >>> for p in the range 0.1 to 0.5 below... was that an actual >>> encoding or just the result from the above formula (which might >>> not apply given your comment above) >>> >>> note though that maybe it is not such a good idea to issue selective >>> naks for >100 losses at once (or said it differently, gropus of >>> 1000 pkts with a loss rate of 10% or more), so maybe we could >>> limit our attention to a relatively small set of missing pkts >>> irrespective of window size. >>> >>> cheers >>> luigi >>> >>> > Note that as P approaches 1 (worst case, which we need to plan for), we >>> get: >>> > List=32*N >>> > Bitmap=N >>> > RLE Bitmap=Actually goes down (because we encode successes rather than >>> > losses), with a worst case always less than either of the other two >(but >>> > approaching the bitmap case). >>> > >>> > Here are numeric results for these formulas, in bits, assuming N=1000. >>> > >>> > p List NACK Bitmap RLE Bitmap >>> > 0.001 32 1000 10 >>> > 0.0031 101 1000 28.5 >>> > 0.01 320 1000 70 >>> > 0.031 1012 1000 158.1 >>> > 0.1 3200 1000 400 >>> > 0.31 10119 1000 632 >>> > 0.66 21120 1000 660 >>> > 0.9 28800 1000 400 >>> > >>> > As you can see, List NACKs are better than a bitmap for P<3%, and worse >>> > otherwise. A RLE bitmap is the most complicated to implement, but is >>also >>> > the most efficient for all cases. >>> > >>> > A related topic to this is the idea of reliable NACKs. Taking PGM as >an >>> > example, it uses reliable NACKs, which make a lot of sense if none of >>> these >>> > encoding mechanisms are used, since there is no built in redundancy >>across >>> > successive NACKs in that case. I think that NORM/PGM's biggest >>advantage >>> > is being able to work without needing reliability mechanisms, which >>gives >>> > these protocols better scalability in the face of failures. The >>reliable >>> > NACKs actually go directly in the face of this, and increase the amount >>of >>> > NACK implosion traffic that would occur when a network partition >occurs. >>> > >>> > I believe that the need for reliable NACKs could be removed in >NACK-only >>> > protocols (as it is in TRACK oriented protocols) by reporting a full >>> status >>> > of all the non-stable packets. With a RLE mechanism, this scales very >>> > nicely, and I think the overhead of adding the RLE mechanism would be >>less >>> > than the complexity of reliable NACKs. >>> > >>> > Conclusion: I think we should standardize on non-reliable NACKs/TRACKs >>> > (they are basically the same thing, just generated at different times), >>> > which use the same encoding format for their retransmission request >>> > reports. I think that RLE encoded bitmaps should be used for this, >>since >>> > the system needs to be stable even in the face of very high loss rates >>and >>> > high data rates. >>> > >>> > Comments? >>> > Brian >>> > >>> > >>> >>> >> >>-- >>Todd L. Montgomery >>Talarian Corporation >>304-291-5972 >>todd@talarian.com >> >> > > > From owner-rmt@listserv.lbl.gov Wed Aug 30 05:06:56 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA22626 for ; Wed, 30 Aug 2000 05:06:55 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id BAA06118; Wed, 30 Aug 2000 01:07:44 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA06114 for ; Wed, 30 Aug 2000 01:07:43 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA01884 for ; Wed, 30 Aug 2000 01:07:42 -0700 (PDT) Received: from daffy.ee.lbl.gov (daffy.ee.lbl.gov [131.243.1.31]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA01881 for ; Wed, 30 Aug 2000 01:07:41 -0700 (PDT) Received: (from vern@localhost) by daffy.ee.lbl.gov (8.10.0/8.10.0) id e7U87fX11665; Wed, 30 Aug 2000 01:07:41 -0700 (PDT) Message-Id: <200008300807.e7U87fX11665@daffy.ee.lbl.gov> To: rmt@lbl.gov Subject: Round 2 - you may be deleted from rmt@lbl.gov - please read! Date: Wed, 30 Aug 2000 01:07:41 PDT From: Vern Paxson Sender: owner-rmt@lbl.gov Precedence: bulk I have been getting repeated bounces from the following addresses for the RMT mailing list rmt@lbl.gov: erwan.humez@detexis.thomson-csf.com ietflist.rmt@icn.siemens.de rmontgom@cabletron.com sangli@cse.iitk.ac.in I plan to delete these addresses in a week or so unless I hear back that particular addresses should be kept or changed. Your RMT list maintainer, Vern From owner-rmt@listserv.lbl.gov Wed Aug 30 11:07:54 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA01335 for ; Wed, 30 Aug 2000 11:07:53 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id HAA07512; Wed, 30 Aug 2000 07:11:42 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA07508 for ; Wed, 30 Aug 2000 07:11:40 -0700 (PDT) From: rhboivie@us.ibm.com Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA02763 for ; Wed, 30 Aug 2000 07:11:39 -0700 (PDT) Received: from e21.nc.us.ibm.com (e21.nc.us.ibm.com [32.97.136.227]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA02758 for ; Wed, 30 Aug 2000 07:11:38 -0700 (PDT) Received: from southrelay02.raleigh.ibm.com (southrelay02.raleigh.ibm.com [9.37.3.209]) by e21.nc.us.ibm.com (8.9.3/8.9.3) with ESMTP id KAA36276; Wed, 30 Aug 2000 10:00:06 -0500 Received: from d54mta04.raleigh.ibm.com (d54mta04.raleigh.ibm.com [9.67.228.36]) by southrelay02.raleigh.ibm.com (8.8.8m3/NCO v4.93) with SMTP id KAA20680; Wed, 30 Aug 2000 10:11:37 -0400 Received: by d54mta04.raleigh.ibm.com(Lotus SMTP MTA v4.6.5 (863.2 5-20-1999)) id 8525694B.004DF6F9 ; Wed, 30 Aug 2000 10:11:34 -0400 X-Lotus-FromDomain: IBMUS To: "Dave Oran" cc: xcast@public.alcatel.com, rmt@lbl.gov Message-ID: <8525694B.004D959F.00@d54mta04.raleigh.ibm.com> Date: Wed, 30 Aug 2000 10:07:09 -0400 Subject: RE: Adding reliable transport layer above sgm/xcsat Mime-Version: 1.0 Content-type: text/plain; charset=us-ascii Content-Disposition: inline Sender: owner-rmt@lbl.gov Precedence: bulk >My knowledge of reliable multicast is spotty at best, so I wade in here with >some trepidation. Since this is a side issue wrt SGM, feel free to drop this >thread at any point. I just want to make sure that any claims are >supportable with analysis or hard facts. See below. Dave, I'm also ok with dropping this thread since this is, as you say, a side issue wrt SGM. I'm just saying that the the ability to selectively specify a subset of the destinations and the ability to efficiently deliver data to a subset of destinations lend themselves to reliable multicast since you can do the re-transmissions efficiently if you want to. But as I said, I agree that we can drop this thread since this is kind of a side issue. Rick re: >I don't know at all how you got there. I didn't respond to Yuji's note >because I assumed he was just pointing out that if you did (audio) >conference bridges with SGM, that would win over multi-unicast. If you >factor out the group-state-in-the-routers, the optimal strategy is each >source unicasting to the bridge, and the bridge unicasting back to the >active sources (since each sees a unique mix), and multicasting to the >non-active sources. Yuji's point was that when you multicast to the non-active sources, you may need a number of different class-D addresses, one for each combination of non-active sources ie. in a 5-party conference consisting of parties 1, 2, 3, 4 and 5, you need one multicast group for 2,3,4,5, and one for 1,3,4,5 and one for 1,2,4,5 ... And you need one class D address for each of the various combinations of 3 members, the combinations of 2 members etc. From owner-rmt@listserv.lbl.gov Wed Aug 30 11:20:16 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA01813 for ; Wed, 30 Aug 2000 11:20:16 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id HAA07518; Wed, 30 Aug 2000 07:13:14 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA07514 for ; Wed, 30 Aug 2000 07:13:12 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA03029 for ; Wed, 30 Aug 2000 07:13:11 -0700 (PDT) Received: from info.iet.unipi.it (info.iet.unipi.it [131.114.9.184]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id HAA03020 for ; Wed, 30 Aug 2000 07:13:10 -0700 (PDT) Received: (from luigi@localhost) by info.iet.unipi.it (8.9.3/8.9.3) id QAA55310; Wed, 30 Aug 2000 16:13:00 +0200 (CEST) (envelope-from luigi) From: Luigi Rizzo Message-Id: <200008301413.QAA55310@info.iet.unipi.it> Subject: Re: Choices for TRACK/NACK report encoding In-Reply-To: <4.1.20000829111049.01c18920@mailhost.talarian.com> from Brian Whetten at "Aug 29, 2000 11:14:45 am" To: Brian Whetten Date: Wed, 30 Aug 2000 16:13:00 +0200 (CEST) CC: Mike Luby , rmt@lbl.gov X-Mailer: ELM [version 2.4ME+ PL61 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit > Hi there, ... > Brain interesting typo... does not look so nice for my name! lugii From owner-rmt@listserv.lbl.gov Wed Aug 30 18:32:08 2000 Received: from listserv.lbl.gov (listserv.lbl.gov [128.3.7.140]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA10366 for ; Wed, 30 Aug 2000 18:32:08 -0400 (EDT) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id OAA08855; Wed, 30 Aug 2000 14:34:04 -0700 (PDT) X-Authentication-Warning: listserv.lbl.gov: majordom set sender to owner-rmt@listserv.lbl.gov using -f Received: from postal1.lbl.gov (postal1.lbl.gov [128.3.7.82]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA08851 for ; Wed, 30 Aug 2000 14:34:02 -0700 (PDT) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA16576 for ; Wed, 30 Aug 2000 14:34:01 -0700 (PDT) Received: from itd.nrl.navy.mil (s2.itd.nrl.navy.mil [132.250.83.3]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA16573 for ; Wed, 30 Aug 2000 14:34:00 -0700 (PDT) Received: from [132.250.92.151] (manimac.itd.nrl.navy.mil [132.250.92.151]) by itd.nrl.navy.mil (8.8.8/8.8.8) with ESMTP id RAA01911; Wed, 30 Aug 2000 17:30:49 -0400 (EDT) Mime-Version: 1.0 X-Sender: adamson@pop.itd.nrl.navy.mil Message-Id: In-Reply-To: <4.1.20000829143701.01ba2b70@mailhost.talarian.com> References: <4.1.20000829143701.01ba2b70@mailhost.talarian.com> Date: Wed, 30 Aug 2000 17:30:16 -0400 To: Brian Whetten From: Brian Adamson Subject: RE: Choices for TRACK/NACK report encoding Cc: "Mike Luby" , "Todd L. Montgomery" , "Luigi Rizzo" , , adamson@itd.nrl.navy.mil, macker@itd.nrl.navy.mil Content-Type: text/plain; charset="us-ascii" ; format="flowed" Sender: owner-rmt@lbl.gov Precedence: bulk I agree with these goals for NACKs as well ... The NACK Content discussion in the current NORM building block draft (but I probably should have put more on "goals" in the draft than just the "solutions" presented) tries to meet these sorts of goals: 1) Explicit packets per block 2) Count of packets NACKed per block 3) Simplicity 4) Independent of block size (within constraints of messaging size ... if a coding blocks are so large that a bit mask (even compressed) representing it can't be fit into a single NACK message some additional fields to support fragmentation might be needed ... but does not necessarily break the protocol given other aspects of the sender<->receiver NACK/repair process) I think the other important goals (stability in high loss, _working_ at all) are also dependent upon the entire NACK process ... i.e. how the NACK messages are used and of course not just the format of the messages themselves. I think it's worthwhile to consider creating a a general NACK format ... particularly to get to a goal of generic router assist in NACK aggregation. I think a general format can be created which satisfies the stated goals and provides the functionality needed for different protocols using NACKs ... The goals outlined make sense for what I hope NORM turns out to be These are also in line with the goals we had for the MDP protocol (some of the current NORM ideas are of course pulled from my experience here) ... In MDP, a NACK message can contain a concatenation of repair requests for coding blocks missed in entirety (if any, which can happen for various reasons) as well as an explicit indication of missing packets within specific partially received coding blocks _and_ a count of the number of erasures for each of those coding blocks. So an individual Repair Request has the following fields: ObjectId - Identifier of transport object or stream requiring repair RepairRequestType - SEGMENT, BLOCK, OBJECT, or INFO NumErasures - count of missing packets (segments) for SEGMENT repair request Offset - starting point of bit mask which follows (coding block identifier) MaskLen - length of bit mask which follows Mask - Bit mask which marks specific blocks or segments needing repair depending upon the RepairRequestType Multiple of these "Repair Requests" are concatenated as needed to form a NACK message. We limit the growth of the size of an individual NACK message to the current multicast session MTU. At most, a single NACK message is sent per repair cycle by a given receiver with respect to a given sender. There is no need for reliability of NACKs given that subsequent transmissions (or lack thereof) by the sender provide an implicit indication of whether the receiver needs to NACK again or not. As Brian Whetten points out, run-length encoding of the bit masks would improve the efficiency of NACK packing in _some_ cases. We have found the above scheme to work well in a variety of situations, but haven't studied NACK size explicitly. (BTW, this could be easily studied with some ns simulations) The above hierarchical NACK lets us NACK for either an entire object (or stream), or some set missing blocks, and/or missing segments efficiently. The receivers' NACKs aren't allowed to grow beyond one session MTU in size The NACK process is self-limited in that all receivers always NACK for the _oldest_ missing data ... the sender follows the rule that it will repair oldest data first (This allows the packing of NACK content be limited to what will fit in one packet)... Thus, receivers constrain themselves from NACKing again until they see the sender's sequence of transmission exceed the point at which they have missing data (This is how the receiver is implicitly aware that the sender has failed to fulfill his repair needs whether from lost repair transmissions or that the receiver's NACK was lost)... The receiver is also constrained by GRTT timing rules to allow the sender sufficient time to receive NACKs, aggregate them, and begin transmitting repairs, etc The above fields may need some additional generalization ... For example, in MDP the "NumErasures" field is an 8-bit value assuming Reed Solomon FEC with 8-bit words ... The erasure count simplifies sender-side processing ... The explicit content is important so that there doesn't need to be synchronization among clients and the sender with respect to multiple repair cycles ... An erasure count alone isn't sufficient to tell the sender to which repair round (1st, 2nd, 3rd, etc) the NACK is applicable ... We found it simplest to have the receivers provide an indication of explicit repair needs even though FEC is usually used for repair ... And the bit masks are easy for the server to process for repair aggregation and receivers (and hopefully eventually routers) to process for NACK suppression purposes ... At 2:46 PM -0700 8/29/00, Brian Whetten wrote: >I would add: >(5) Being able to efficiently encode as many losses across as many blocks >as possible. i.e. being able to report a history of outstanding lost >packets, rather than just the most recent ones. >(6) Simplicity >(7) Being stable in the face of very high loss rates, either of data >packets and/or NACK packets. > >I would prioritize 1,2,6,7 as having the highest importance. > >Brian > >At 12:36 PM 8/29/2000 -0700, Mike Luby wrote: > >As design goals, it would seem to be desirable: > > > >(1) That explicit packets can be NACKed per block. > >(2) That a count of packets can be NACKed per block. > >(3) That the mechanisms that achieve (1) and (2) are compatible with each > >other. > >(4) That the mechanisms would work relatively efficiently independent of the > >loss per block or the size of the block. > > (a) Would be desirable to work with small as well as large blocks (in > >terms of number of packets per block). > > (b) Would be desirable that the block size in packets doesn't have to > >fit any special requirements, e.g., be a power of 2. > > (c) Would be desirable that the scheme would scale with the number of > >losses per block, in particular when the report is a count then one should > >report any number between 0 and the size of the block in packets. > > > >Do these goals make sense, and how would people prioritize these goals, and > >are there other goals that are even more important that are missing? Once > >the goals and their relative priority are clear, then the design may just > >fall out as a natural consequence. > >Mike > > Brian __________________________________ Brian Adamson