From owner-rmt@listserv.lbl.gov Sun Mar 5 07:58: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 HAA08242 for ; Sun, 5 Mar 2000 07:58:54 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id DAA14487; Sun, 5 Mar 2000 03:58:00 -0800 (PST) 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 DAA14483 for ; Sun, 5 Mar 2000 03:57:57 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA02865 for ; Sun, 5 Mar 2000 03:57:56 -0800 (PST) Received: from motgate.mot.com (motgate.mot.com [129.188.136.100]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA02860 for ; Sun, 5 Mar 2000 03:57:55 -0800 (PST) Received: [from pobox.mot.com (pobox.mot.com [129.188.137.100]) by motgate.mot.com (motgate 2.1) with ESMTP id EAA21434 for ; Sun, 5 Mar 2000 04:57:54 -0700 (MST)] Received: [from homer.arc.corp.mot.com (homer.arc.corp.mot.com [217.1.10.38]) by pobox.mot.com (MOT-pobox 2.0) with ESMTP id EAA17112 for ; Sun, 5 Mar 2000 04:57:46 -0700 (MST)] Received: from motorola.com ([217.2.31.248]) by homer.arc.corp.mot.com (8.9.3/8.9.3) with ESMTP id WAA12101 for ; Sun, 5 Mar 2000 22:54:47 +1100 (EST) Message-ID: <38C24AE1.C9C83844@motorola.com> Date: Sun, 05 Mar 2000 22:54:11 +1100 From: Roger Kermode X-Mailer: Mozilla 4.7 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 To: rmt-list Subject: RMT Meeting Feb 10, minutes draft Content-Type: multipart/mixed; boundary="------------12DAB1FB4EB5F784B0A83607" Sender: owner-rmt@lbl.gov Precedence: bulk This is a multi-part message in MIME format. --------------12DAB1FB4EB5F784B0A83607 Content-Type: multipart/alternative; boundary="------------83EEF7F1661A5FD3901798F2" --------------83EEF7F1661A5FD3901798F2 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dear RMT'ers, First of all please accept my apologies for the tardiness in sending out these minutes/notes. Much thanks must go to Sally Floyd and Bob Quinn for taking them during the meeting Please take a moment to puruse them and point out any errors. thanks! Roger ------------------------------------------------------------ RMT Interim Working Group Meeting Feb 10, 2000 Minutes ----------------------------- Attendees Initials/Name/Interest MH Mark Handley CC, NACK SF Sally Floyd CC DC Dah Ming Chiu ACK, TREE, CC SK Shivkumar Kalyanaraman CC LR Lars Rasmussen ALC BQ Bob Quinn all aspects CB Carsten Borman NACK (and the rest) VO Volkan Ozdemir CC YY Yung Yi CC DA Deb Agarwal all aspects BL Brian Levine tree building, yoga (!) SB Supratek Bhattacharyya tree building IR Injong Rhee CC AC Adam Costello GRA, tree building ML Michael Luby ALC, FEC, CC BLu Bruce Lueckenhoff ALC CP Christos Papadolulos GRA, tree building JM Joe Macker NACK, ALC BA Brian Adamson NACK, ALC TH Thomas Hardjono Security HR Hayder Radha CC/ALC BW Brian Whetten track, CC JG Jim Gemmell ALC, FEC, NACK BC Brad Cain GRA, Tree building TO Tokuop Oishi GR Gursel Taskale all RK Roger Kermode all LV Lorenzo Vicisano all ---------------------------------------------------- Interim Reliable Multicast Transport Working Group Feb. 10 2000, ACIRI, Berkeley CA. [RK: thanks to Sally Floyd] Several people are late, because highway 880 was closed for a while. There is a SMUG (Secure Multicast Research Group) meeting here tomorrow. Intro by Roger: [Add a pointer to Roger's viewgraphs.] Goals of meeting, Overview of agenda. Call to Arms: Building-Block and Design Space drafts are waiting for review by Mark. Mike: Are we on-schedule with the goals listed in our charter? Roger: We are behind schedule. The group will standardize building block and protocol instantiation documents. The Guidelines draft: [Add a pointer to Roger's viewgraphs.] What is missing from here? Mike: What about revision control between the PI (Protocol Instantiation) and the BB (Building Blocks) documents? Do they cross-reference each other? This comes to the API issue: what parts of the BB documents are referenced by the PI documents? The BBs have, not an API, but a higher-level interface description. NACK: There is a BB and a PI. How does this work? Answer: The BB has the more general stuff. And a NACK PI might also use ACK-based stuff. Jim: Can we do an example, with PGM? BBs should discuss design tradeoffs. Building blocks might be more applicable than just bulk transfer, though that is our immediate focus. Mike: There is a danger of designing a BB without a PI in mind. Maybe each PI should write its BBs, and then come together. Mark, Sally: For NACK and TRACK, it is clear that there is a CC (Congestion Control) BB that can be broken out now, in parallel. For ALC, there might not be as many BBs that can be broken out now. FEC is a building block that can be taken out of ALC now. What will go in the NACK BB? Mike: Maybe the BB role can be more informational. >From SMUG: BBs are coarse-grained, and might need more fine-grained components within them. Mark: BBs should not include all possible options, but should narrow down the design space. A call for BBs and PIs to start with overviews first, not the nitty-gritty details. Out of today, perhaps we can end up with overviews of each of the BBs. ------------------------------------------------------ Congestion Control: Mark: TFRC, Unicast TCP-Friendly Rate Control [Add a pointer to Mark's viewgraphs.] Pointer to paper: "http://www.aciri.org/tfrc/". The talk shows results from experiments and simulations with TFRC. For unicast, the performance is very good. Question: Simulations with TFRC: in simulations, TFRC tends to drop to zero with many flows, very high bandwidth? Mark didn't see this, will look at it later. Oscillations from smoothing the roundtrip time, and sending at 1/RTT: For unicast TFRC, we added RTT-based Congestion Avoidance. This is needed more for Drop-Tail than for RED queues, or for high levels of statistical multiplexing. Issues for multicast: timely feedback, measuring RTT. Question: Does this apply to non-sender-based congestion control? Mike Luby: The work on CC for ALC is not finalized. It is interesting to see if sender-based TFRC schemes will apply to receiver-based ALC. VRC: [Viziano, Rizzo, Crowcroft], the RLC protocol. Receivers join a layer and all lower-bandwidth layers. Each layer has twice the bandwidth of the previous layer. Join times are quick, and leave times might now be quick also. In his opinion, the RLC approach has more power than the single-source approach. For TCP-friendly issues, how does the RTT get taken into account? Mark: In small levels of stat mux, increasing the sending rate can dramatically increase the packet drop rate. This is not the case with large-scale stat mux. Mike: There is a lot of interesting work to be done. Remark: Fine-grained video coding is the coming thing. Roger: Is the discussion leading to BBs? Are we going into too much detail? Brian: We have a TRACK architecture overview, that shows how BBs fit together. TEAR: Similar to a TFRC building block. Differs in how to measure a fair TCP throughput. TEAR differs from TFRC in the receiver. Instead of using the TCP-friendly equation, TEAR emulates TCP at the receiver. Takes a weighted average of eight TCP congestion control rounds. TEAR trys to give a more accurate model of TCP. Mark: TEAR is sensitive to the pattern of losses. And they differ in the modeling of retransmit timeouts. Shiv Kalyanaraman: Generic source-based multicast congestion control. [Get a pointer to viewgraphs.] This is sender-based congestion control. No measurement support from the receiver set, except for NACKS or ACKS that are already there. No aggregation support expected in the tree. Congestion periods are broken into congestion epochs, which is a period with a single rate reduction, with time for the rate-reduction to diffuse to the congested sub-tree. Mark: He is assuming a very low level of stat mux? He is assuming that if the sending rate is increased, the packet loss rate increases also? The protocol mimics TCP at every point. They have implemented this in NS, and they have a PGM implementation. ---------------------------------------------- ----------------------------------- RMT Interim Working Group Meeting -- Draft Minutes -- [ RK: thanks to Bob Quinn] Feb 10, /2000 - Hosted by Aciri at ICSI in Berkeley, CA ----------------------------------- Roger Kermode, RMT working group co-chair, started the meeting at AM with 18 people present (we had 28 by 11AM) with a review of the agenda. Tentative Agenda --------------------------------- 09:00 - 09:10 10 mins Agenda Bashing [Roger] 09:10 - 09:10 10 mins WG status update bb + ds drafts Recharter 09:10 - 09:20 10 mins Call to arms/editorship selection update [Roger] 09:20 - 09:40 40 mins Guidelines Draft Update/Discussion [Roger/Lorenzo/Allison] 10 mins draft outline 30 mins discussion 10:00 - 11:20 1hr20mins Congestion Control: [Handley/Flloyd?] 10 mins TFMCC update [Handley/Flloyd] 10 mins ALC implications for CC [Luby] 10 mins TEAR implications for CC [Rhee] 10 mins Generic source-based multicast CC [Kalyanaraman] 40 mins discussion 11:20 - 12:20 1hr NACK: [Bormann & Adamson?] 10 mins BB Update [Borman] 20 mins BB Discussion 10 mins PI Update [Adamson] 20 mins PI Discusion 12:20 - 13:00 1hr Lunch 13:00 - 14:00 1hr Asynchronous Layered Coding: [Luby] 10 mins BB update 10 mins Gemmell? 40 mins discussion 14:00 - 14:30 1hr Tree-Building: [??] 10 mins table of contents update [Chiu] 20 mins discussion 14:30 - 16:00 1hr TRACK progress [Whetten/Chiu] 10 mins [Whetten] 10 mins [Chiu] 40 mins Discussion 16:00 - 16:45 45 mins VACANT 16:45 - 17:00 15 mins Agenda bashing for Adelaide RMT has been rechartered and the new charter--now approved by IESG--is in place on the RMT working group webpage. http://www.ietf.org/html.charters/rmt-charter.html Mark Handley showed the new charter as it appears on the RMT working group webpage. Roger provided status for the existing documents. The charter is agressive and we are a bit behind at this point. Many of the documents are essentially done (though most are not issued as Internet Drafts (I-D). Generic Router Assist (GRA) is the only exception. The Multicast Congestion Control document is due for Apri--after Addelaide--and it is acknowledged as the most difficult problem, and the one that gates all others. Mike Luby asked whether we expect to be doing work on both the BBs or the instantiations, and Roger said, "Yes, both." The Building Block (BB) Guidelines draft has been stalled. That is likely a source of confusion, since many people may not know how to proceed with creating a BB I-D without it. The idea behind the BB is tp create some framework definitions for Reliable multicast transport (RMT) that exist for Real-Time Protocol (RTP) format. Goal: to help people write Building Block (BB) and Protocol Instantiation (PI) drafts - How BBs and PIs fit together - Sections to be included: + applicatiblity statement = where to use and where NOT to use = known failure modes + BB: = bunctional description = abstract API for use by other BBs + PI (protocol instantiation): = core functionality not in BBs = which BBs are used = how they fit together = packet formats Mark Handley and Sally Floyd (MH and SF): PI needs to be specific about the application targets - the PI *may* have some mechanisms that BB doesn't (but not all will) Joe Macker (JM): The BB should describe the trade-offs MH: Some BBs will be more generic as far as being applicable to bulk file transfer alone, and others will not. Mike Luby (ML): doing the BB first and the PI second seems backwards. It would be better to do the PI, then try to derive the commonalities that represent the BB. MH: We alread have a lot of existing protocols that we understand very well. ML: But are these written down? Roger Kermode (RK): Our hope is that people that have the experience with specific protocols need to exchange their experiences. ML: But again, it is written down? MH: We may well do some back-tracking after the fact, but we expect that. ML: I think it is important to do the PI first and write it down. MH: I think that ALC may be one where that is true ML: Why is that? SF: Because there are lots of TRACK and NACK based protocols for which we understand the commonalities so it makes a lot of sense to do the BBs in parallel with PIs. Jim Gemmel (JG): I'm fuzzy about what goes into a BB, is it going to simply say what NAK does or list many different ways it could work. MH: I think that NAK will have suppression mechanisms built into it. JG: Are you going to list the mechanisms/algorithms? MH: We need to pick one and describe it. JG: But there are so many ML: You pick one and it may not be appropriate in all cases. Thomas Hardjono (TH): In SMuG we have picked a number of them RK: We are obviously still struggling with what a BB is, so I tend to agree with Mike that we should concentrate on a PI first. ??: I thought that the BB was supposed to describe what we recommend with Interet health as the focus. SF: It is a good idea to have things that refer to Internet health, but we already have RFC 2357 (?) that describes the requirements for any RM transport. RK: I think we are approaching some concensus. JG: Go write one and lets take a look at it ??: Suggested that we have an overview and functionality description for each BB *first* then move into the other details --- TFRC - TCP-Freindly rate control Mark Handley (Equation based congestion control) - we thought we understood this (for unicast) a year ago, but we did not and we don't know multicast yet. Scripts and paper all available at http://www.aciri.org/tfrc It is fair to TCP in general, although we have seen TCP get beat up because it was too bursty Key measures are loss fraction and round trip time Measuring round trip time, there are oscillations in TCP and with multicast the delays between these is longer. To dampen oscillations but still gain RTT-based congestion avoideance behavior, need inverse dependence on RTT but lower gain. <> The result of this is a smoothing of the oscilllations. - If you fix the RTT time, you get the oscillations, but if you don't (as described above) then they are smoothed. - we've tried these things with a wide variety of Queuing congestion control mechmanisms, and it works well with all (though having RED reduces the need for this mechansism). Issues for Multicast - how to ensure timely feeback? Delay reporting loss event fraction may affect dynamics - How to measure RTT to all receivers quickly? Not a showstopper, but may affect how CCC fits together with other components - RTT-based Congestion Avoidance is difficult (referring to the algorithm described above): It is not clear that this is necessary, but the consequences of not doing it are not yet fully understood. ??: What is the traffic load for reporting congestion control? MH: You really want your NACK or ACK trafffic to report it, and with aggregation points (TRACK or other local/shared recovery points) you have additional delay. None of this applies to ALC though, of course (since it is one-way). ML: Yes, but reading through your paper I got the impression that a lot of it is based on the receiver, so it could well be applicable. ML: If you actually did an experiment with two TCPs then they would not be fair to each other. The one that has longer timeout (say 10 times) would be 100 times more loss. SF: I don't believe that loss rate would be 10 times more Brian Whetten (BW): I don't beleive it would be, either. JM: What about slow-start mechanism for multicast? MH: We may not need one for multicast since the advantage of having one is not clear yet. ---- Asynchronous Layered Coding (ALC) BB Mike Luby The work on ALC CC is not finalized yet, though there has been some great work done so far. - thing about ALC is that you can have different receivers receiving at different rates (determined by the number of groups they have joined, and streams they are receiving in parallel) and we need to take advantage of it. - VRC (authors Lorenzo V. , R. and Crowcroft mechanism is used for this (also referred to as RLC for author names also ...for some unknown reason). - Synchronization points happen more often at the lower layers than at the upper layers. Layers are cumulative. It is now a very course-grained CC, and we should make it more fine-grained (more fine-grained than the synch points can provide). Current one gives a linear increase. SF: A factor involved with whether you couild ramp up send rater slowly is whether you have either small or large-scale statistical multiplexing. Hayder Radha (HR): ALC sounds much like MPEg-4, which provides fine-grained scalability and uses many different multicast groups (roughly 10-20). -- Short talk on TEAR Rhee - TFRC uses equations looking at 8 loss events that have occurred and is based on what it finds from the sender, whereas TEAR emulates TCP within the receiver and how. MH: TEAR is sensitive to the pattern of losses (which may be good or bad) and sensitive to the timeouts. -- Generic Source-Based Mcast Congewstion Control Shivkumar Kalyanaraman (RPI) <> - implosion control needed - need timing info on Sender & Reciever (may need GPS at receivers) - Need to know the (S,G) state "Generic" means - completely implemented at the source - no measurement support from receivers - no extra contol traffic inserted - no extra fields - no aggregation support expected - should work with NAKs, HACKs, ACKs, bit maps or other reverse traffic which provides congestion and timing information Weak requirements on RTT & loss estimation: - suppress NAKs from long RTTs (partial timing info) Basic idea is that they devide congestion time periods into "epochs" where the source reduces the send rate exactly once and enough time is given for rate-reduction to diffuse throughout the congested sub-tree. They do not depend on the loss rate. They have implemented it in their version of PGM. MH: Seems like you are not depending on having large-scale statistical multiplexing rate and that assumes that the competing flows are doing the same thing, which is a flawed assumption. -- Brian Whetten said he has done a description of how the BBs fit together from the perspective of TRACK.* reliability ====== short break ====== RK: This is a new process we've been doing with the BB approach, so we need to describe it in more detail. Boorman: The BB needs to be normative, we need to have it as something that people can reference as opposed to something that is not BW: It should have exact algorithms and abstract APIs SF: BBs need to describe design tradeoffs required for Application- specific variations (e.g. optional feedback). Single Rate CC BB Team: Mark H (leader), Sally F., Injong, Brian W., Shiv, Supratek, Hursel, Joe Macker, Brian A. MultiRate CC BB Team: Mike L (leader), Lorenzo, Hayder, Injong, Jim Gemmel, Luigi Rizzo, Jon Crowcroft ??: I come from a satellite company and I'd like to see some satellite-specific considerations described. RK: We deal with the Big 'I' Internet and this includes the satellite media, so it is included implicitly. MH: It looks like Single Source multicast (e.g. PIM Source Only) will have an earlier deployment than others so it is likely that we will have one-way links as well as two-way, so in that context satellite is not that special despite the fact it has a long fat pipe (long delay and high bandwidth capacity). RK: Can we have a document by Adelaide on Single Rate, Mark? MH: Yes, we can have a *start* on a document. We need at least a first pass of *every* building block by that time. RK: The due date for drafts is March 10 and we should really strive to have something done by this time. MH: We should also submit the names to the RFC editor beforehand so it doesn't get delayed (we should do this on the mailing list). RK: Ok, will do. MH: Should we have discussions in sub-groups or on the main RMT mailing list. <> <> CC Building Block Guidelines ----------------------------- Must be normative - exact specific algorithms and abstract APIs Discussions of tradeoffs - application specific variations (e.g. optional feedback). Cover design space. Purpose: RFC 2357 and Sally Floyd's Congestion Control Principles draft, see http://www.aciri.org/floyd/papers/draft-floyd-cong-01.txt + 2 parts: = Mandatory to satisfy IESG reqs = Application specific Requirements for other BBs: - what messages can be piggy-backed (existing BB msgs and additional msgs) . - loss detection - RTT measurement Two Separate BBs: -> single source (e.g., PIM-SO) -> Others (single rate) - satellite, asymmetric, wireless, GRA Considerations target scale (in terms of number of receivers). <> --- How TRACK fits with other BBs Brian Whetten (( his view of what needs to go into BBs )) Goals - functional decomposition across other BBs - sees TRACK as a superset of NACK Exponential back-off on loss detection Unicast NACK generation - issue: NACK needs multicast NACKS? response to retransmission request GRA signaling Integration with TRACK hierarchy - how do you do this well SF: Why is this included here? BW: We repeat it in both places Question: Since it is a superset of NACK, why have a separate BB? BW: Interesting thought. MH: We need to do suppression so the question is how to do it. You can do it by a tree or not, so the discussion needs to talk about it with that focus MH: One thing missing here is how it interacts with and uses FEC. Lorenzo Vicanso (LV): Yes, FEC is very mixed with suppression. MH: FEC itself is not in there, but a description of its functionality is. ??: Why do you call it NACK when it should really be a generic feedback mechanism? BW: We have differentiated the feedback (for CC) and the NACK for data loss and the TRACK since it has to deal with hierarchy. Brad Cain: What do you think the biggest issue is? BW: The issue of how and when you deal with the NACKs. FEC BB: - input of a (sub) window of data packets + issue: packet nameing - creating parity packet + issue: exhaustion of parity packets + proactive parity (which block owns it)? - flush data stream with only a small sub-window - FEC decode - Bind to different codecs LV: It seems that some of these issues (like flush) belong in the protocol instantiation. BW: This is a highlight of the functions and not specifications of what they are doing ML: I would just talk about the protocol and not how it will work in all protocol instantiations. That cannot work. RK: The model to look at for this framework is RTP, where there is enough generality to allow a common, versatile framework. LV: You need an API for making state available ML: There is a way to describe FECs in general without going into detail with exactly how to use them. ??: This has actually been done in the AVT RFCs that deal with codecs (may still be I-Ds at this point). They may not be exact, but it is a good thing to start with. LV: You can define blocks and when you can reveal the blocks and deal with them. TFMCC BB: - Initialization - Receiver measuraments + issue: RTT measurements - Receiver feedback (on TRACK/NACK) + Issue: how to bias NACK timers? - hierarchical aggregation - sender rate control MH: There's no requirement for interoperability until you get into a PI. The packet formats are defined in terms of funcionatlity rather than generically as "feedback" to be efficient in terms of size used. GRA BB (draft-ietf-rmt-gra-arch-00.txt): - Core, simple router functionality + issue: how to instantiate this? - signaling guidelines - NACK Brad Cain (co-author): we will have a separate document that will include feedback mechanism defined and we will define packet format. It will be incrementally deployable (as spec already says). We will be dealing with server-to-server traffic, which is the auto-tree configuration. Auto-Tree Configuration BB: - Discover hierarchy that matches the multicast topology - works in all environments - provides children with an address list of candidates + if/when first fails you go to second one BC: You need to discover namers, create hierarchy (some sort of routing protocols where you abstract away who is closest to the root). JM: Is this going to be a routing-ish shared tree? BC: We are not doing that level of detail ...we are not creating PIM over a mesh. Once you abstract away what a possible root could be (source, RP, etc.), then there has to be a route from whatever it is. Then that has to be...??? I wouldn't touch that one with a ten-foot pole. There will be packets between servers, and there will need to be a way to measure distance between server to source and you can do that LOTS of different ways. You need to know what the metric means. BW: Yes, I agree that the problem is not yet well defined ====== lunch break ====== << Brian Whetten, on TRACK BB Requirements, continued >> Common Packet Headers - Data Naming + sequence number, FEC offset + issues: Add object ID? Need sequential packet numbering. Need to support application level multicast - Session naming + stream ID + TRACK may need a Tree ID - Also issues with Application Level Framing (Talarian, TIBCO and FastForward are three examples), since you are multiplexing at a different level MH: There seems to be three sequence spaces: - packets within FEC block - FEC blocks themselves - Object ID itself You might be able to build over to create frames over that, but it must be at the object level to get reliability. I think it might be worthwhile to go down this path to see what comes out, what meta-information we need. BW: The other consideration that is important is the number of bits we add to support this. MH: My view on bits is don't worry about it, since it is only on low-bandwidth links that it is a concern Security BB - Really SMuG's area and our area - Transports only job is to protect itself - Interface to key managerment is what we need - IPSec for lightweight version TRACK functions - hierarchy creation and maintenance + join, leave, falure recovery, keepalives + local multicast groups for control, retransmission - parameter initializeation/distribution + server and tree-wide - source ordered, unordered, time bounded (?) - network management JM: Is there a new security consideration for ACK Aggregation TH: At last IETF I talked about a mechanism whereby an intermediate point that received a NACK would have to forward them upstream for signing (so intermediate point does not need to be a trusted participant). Authentication and trust models are the issues. LV: The NACK authentication is an end-to-end issue TH: Yes, but NACKS are from routers BW: Routers don't issue NACKs, however. Routers create the tree (for TRACK). MH: Tree-based protocols help you to generate round trip times. TRACK Issues - Kill TN and Aggregators? + shared tree versus per-source tree? - Can we have dynamic DR/receivers - Multicast address sharing BW: Is top of the tree always co-located with the sender? MH: There are lots of different ways to build trees BW: You can have multiple data sources for a single tree BC: It would be good if anyone desiging NACKs talk to him and BL about how to define them for each of the BB type (e.g. NACK, TRACK, ALC), specifically in terms of application interface and packet formats. ====== We then had break-out meetings for separate sub-groups: "ALC", ""NACK," and "Tree Building" (in quotes since these are very loosely defined). Here are the topics discussed: "ALC": - FEC - PI for ALC - Congestion Control "NACK": - PI versus BB - NACK - Congestion Control "Tree Building" - Auto Tree config ========= Wrap Up ========= Roger Kermode on Auto-Tree Creation BB discussion: - Preconfigured solution + assumes the existence of a mesh of delivery servers (which may be statically configured or dynamically generated): + requires existing infrastructure on internal nodes - Ad hoc solution + does not require predeployment + assumes mesh discovery protocol + no GRA + no TTL scoping (needs to support PIM_SO) + no static config info in hosts MH: Do you have any reference implementations for these models? I'd like to see some running code. Mike Luby on ALC: - we had lots of concensus and progress - We also took on the FEC BB TRACK: - what identifies a source or a receiver? NACK: - We also discussed FEC a lot too since it is tied in Rather than having different mailing lists for each subgroup, Roger proposed that everything go to RMT and we preface subjects with what the topic is relevant to (and add "PI" as a suffix if that's the topic) FEC, TREE, ALC, NACK, CONG_{SR | MR}, TRACK, GRA, or GUIDE. He will send a message to the RMT mailing list describing this. <> ========================================= Notes from TRACK sub-group Discussions RMT Working Group Meeting 2/6/00 ========================================= blame bob quinn for any innaccuracies Motivation for creating a tree - Good for error control and congestion control - Distributed aggregation (caching hierarchies, e.g., for use in a Content Distribution Network (CDN)) - Anycast - Security, group key management - Distributed gaming/simulations All have similar requirements Why is it useful? 1) hierarchical construction assists with load balancing 2) topologically aware aggregation 3) topologically aware subcasting First is sufficient (2nd and 3rd are efficient). Why by aware of topography? - topologically based structures have dramatic performance benefits + localized aggregation + subcasts that are focused towards downstream logical descendants + allow use of subcast, period. + ensures reduced latency between pairs Applications - local aggregation + error, congestion control, CDN, security - focused subcasts + error, congestion, security - reduced latency between pairs + gaming, anycast BW: So is the goal topological congruency? Brian Levine (BL): Yes BW: Would anyone debate that? BL: yes. You can't do it now without difficulty, but that does not mean it is not something we should *try* to do. BC: That is something we should strive for. BW: There are some that would say it is better for error control BL: I don't agree with that BW: I just want to talk about it since it is relevant to asymmetric routing, among other thigns. BC: That is a really tricky issue and the other reason is inter-domain BW: Exactly, which is why single-AS is going to rule BC: Exactly. BW: Should we scope it to a single domain? "Easy" way to do topo-aware - use GRA!! - Source periodically multicast packets with GRA and router alert (MD5 Auth) + They go down the tree from a parent + I'm assuming we are doing Express mode stuff - GRA routers with their IP address in the payload of the packet (perhaps both in and out interfaces ...?) + Each hop adds as packet traverses + As there are more routers, you get a better idea - Receivers subcast from last revised router announcing their path strings - Receivers pick parents, send unicast to confirm - Or...new mtrace messages (added by Brad Cain) + This would trace down the tree (though we have not yet figured out the format ...though many don't like mtrace since it gathers statistics, has latency and adds overhead) ??: There was a guy at MCast2000 who said that the hyperqueue could build a tree very quickly BC: There is part of this that people can use to do other tricky things. For example how do you find out how close you are to a source or an intermediate routers and there are lots of ways to do it. Two problems with finding a metric that's good: congruency and how best to announce to the group Breaking Up the Problem: - Neighbor Discovery - routing-like protocol + who is closest to the "source" (for mcast) + who is closest to other point (e.g. server) - How to find distance to server or seoruce? - How to make it generic? + can we do it for others than reliable multicast, such as the content delivery people. - Fault tolerance BC: Looking at a graph or mesh of servers and over the top of that there is some sort of protocol that you use to build a hierarchy in the server to server protocol itself. To do so you need to have some sort of metric, such as who is closest to data source or RP. You discover a set of neighbors within a scope (that's how the mesh is built), then over that mesh you establish the tree. BW: That is basically what we are looking at but that could be a heavy weight protocol. BC: You can statically configure the mesh (which will most often be the case anyway ...that's the way these content distribution network guys are doing already). RK: We have to be able to exist where GRA doesn't already exist. BL: If we didn't bring up topological awareness then we woudln't have any issue with non-GRA implementations. We are being passed-by and need to do *something*: - companies can do non-topo aware without us, though standards are nice - eventually they *will* do topo-aware without us - As IETF'ers we should make recommendations BW: The barriers to getting GRA into all the routing infrastructure is so high that from a practical standpoint we should be able to use it without GRA. BL: I think it will take 3 years to get GRA widely available BW: I think that is really wishful, which is why we should think about new mtrace messages. BC: The mtrace command needs access control (password, maybe?) since it reveals the tree which can be very dangerous. RK: If you are going to use mtrace, think about a network with 10000 nodes BC: MTrace would not scale to that many receivers BC: you can try to match receivers with nearest server or make tree closest to source. The content delivery is focused on making caches close by to receivers. ??: Seems a question of how tall you want to make the tree with respect to how much fan-out there is (the optimality of the tree). BC: Yes, that all relates to how you build the tree Miriam Kadansky did a doc that relates to requirements BL referenced this and created slides from the TOC. Dah Ming (DM): How the the tree is formed and then used. This was a strawman for generating discussions. We have lots of information about tree optimization and maintenance as well as tree building and what I'd like to see is a discussion of how much of this belongs in the BB. BW: I think only the building of the tree is important. BC: I think there should be two layers: a base layer that can be useful for a lot of things and the second that is specific to reliable multicast. RK: Auto-Tree Requirements (RM specific) -------------------------- 1) Aggregation of things like ACKs, NACKS, congestion control 2) Subcasting - parent to child unicast (application level) - parent to all descendents local multicast group - parent to child (GRA) 3) Others (non-RM specific) - group membership - list of GRA-capable routers - billing RK: It has to be spelled-out in the draft what is RM-specific and what is not. TH: Some mechanisms used to design the tree are exactly the same that is needed to deliver some of the services that the tree is supposed to support. BW: So, for example, you could use subcast to do auto tree configuration. TH: Good examplee BW: Goals: - Perfect topology congruence - failing that, do something not stupid - list of parents BC: Where does the metric fit in? How do you determine a "perfect tree?" What does the API give you? BW: These are the list of parents and the metric(s). There are other interactions to prevent loops (for example). We may be able to pick one metric. BL: we should have one metric in mind. BC: There are a number of different possibilities. RK: You are building a tree to do what, connect sources with receivers or with end-points?? DM: The DR could be either the source or the distribution head. BW: The head of the tree is always the source BC: the problem is that if you are given just a list of neighbors and metrics, then you could construct a tree that has loops. BW: I was assuming it was at least an ordered list so there are no loops. BL: you can always override this, so we must assume that it has no loops. Congurence is the goal and besides, it is not even a tree if it has loops. DM: There are diffferent ways to make sure you don't have a loop, BW: Yes, but if you just know the depth of the tree then this is enough information to create a non-looped system. DH: That implies the tree is built top-down BW: The issue comes down to work BC: right. BW: Who has to do the job BC: The loop protection depends on what info is exchnaged between nodes. Requirements (according to BW) - Universally deployable + multi-AS + All multicast routing + GRA - Safe - Receiver auto-config + e.g. receivers can find their nearest server - Keep it Simple BC: I think the receiver auto-config is DONE: DNS (though Anycast or a web-page or other out-of-band mechanism could be used also) BW: I am just defining high-level requirements without considering solutions BC: We need to be able to "prune protocols" (to quote Steve Deering) to make it simple BC: Do we want to get into Policy metrics when considering inter-AS (inter-domain)? BW: I really don't think we want to go there. BC: All protocols are source based now BW: Huh? Applications don't have a way to specify the source. ??: the tree building protocol is running all the time? BW: Yes, so you can ask anytime for what parents are RK: It sounds like you are trying to punt things away, so if it does not get done here where does it get done? BW: In TRACK BC: We still need to determine the line between TRACK and here. BW: The issue is that keep-alives, HACK packets, get generated. It is control path versus data path issue. RK: I like that separation between control and data paths. This document should be sufficient to create a control path and that control path is used to deliver data. BW: There is realistic three peices here: all error packets are part of data. We want auto-tree config information. BC: I agree they are separate, but think there is anough commonality to keep them together. BW: I am abstracting out configuration information for control RK: Can we separate out like: - Ctrl path: tree creation and maintainenace - Data path: "repair" PI specific control << short diversion into discussing whether it is possible to create a generic BB or whether we have to start with a PI ...the challenge being whether we can have something generic without getting into protocol details >> BC: You can do something really simple, but if it is going to be that minimal, there is some question about whether it is useful. TH: It has to work, so it can't be that thin. The thing is that to be useful, we need to agree on some common elements. BW: I think the NACK BB is going to be very short (deal with retry timer and action) and I suspect that we can make this Tree Building BB just as small. BC: CDN people want all these things. I don't know where the line is between generic BB and PI. ??: There are two main things: discovery and maintenance. DM: Yes, but it is more complex since there are different scenarios (e.g. late joins). RK: Tree "functions" - Discovery: learning *possible* parents (manually or auto) - Construction: Joining the tree + BC: e.g. applying Dijkstra and creating link-state - Maintenance: Fail over, leaving - Service Hooks (sub-cast, aggregation, etc.) BW: Problem is you can't discover parents without considering where the source is. BC: What is the signal for generating a tree, is it that a receiver joined or that a source is there? BW: I would say when receiver joins BC: I would agree with that RK: Discovery: - who starts the process? + source: top-down tree generation + receiver: bottom up tree generation BW: The way the world actually works is you have a collection of Sources, a collection of potential DR's (intermediates) and receivers (he illustrated on board with three layers). BC: We are not dealing with the receivers to servers in this tree building (which is a server location problem ...and we can safely assume that DNS solves this). Most of the time the configuration of the mesh of intermediates is statically configured (99% of the time) ...call it "the Mesh." At this point there are NO TREES yet (an important point), so there's no concept of loops at this point since nothing is source specific. BW: Mesh: 1) neighbor disovery 2) senders announce 3) receivers initiate join BC: Alternately, the source finds a server DM: Yes, there may be many servers that are not relevant to a source BC: Ok, yes, so let's assume that the source does NOT announce to the servers. We already know how to do this and it's called multicast routing (using PIM). It requires that each server knows the metric distance to the source(s). BW: Ok, so we're done! We will just run another routing protocol (along with the one below us at the IP layer that we cannot access and the one that may be above at the application level). ??: Ok, this assumes that there is a mesh, but what if we don't assume this? BC: I disagree, since if you look at anything on the net it is formed as a mesh and there are a lot of administrative issues about who can talk to who. Lots of discussion/debate about whether we can assume that the mesh is avilable as preconfigured infrastructure. To do auto configuration we cannot assume many-to-many SRM-like discovery. Dah Ming and BL agreed that having the intermediate mesh assumed makes having the receivers going directly to senders impossible (e.g. so the receivers can organize into a tree without having an intermediate layer). BL: Could send from source with IP list, as I described earlier. DM: Yes. BC: Ok, if source sends magic packet then each receiver picks a receiving parent. DM: Yes. This should be allowed and the static intermediate layer could be optional. BL: Yes, and then any intermediate node can declare that they don't want to be part of the tree. -> Some disagreement about which of the two models should be the primary requirement. RK: My dream protocol that I want - Doesn't require GRA (but be compatible with GRA) - Doesn't use TTL scoping - Needs to work in PIM source only (PIM-SO) - Doesn't require config info in hosts - Doesn't require statically deployed mesh BC: You may want to determine your tree with metrics other than hops (e.g., server load, geographic location, etc.). BL (and others): the one where receivers can be DRs makes the static mesh possible, but the converse is NOT true. BC: I disagree. Since not all receivers can send, it becomes an access control issue that assumes many-to-many multicast is possible. Summary of differences between the two models: > Dynamic Discovery version sends a probe from the source and each *logical* hop adds its addres and the metric you end up using is a router-like distance metric that uses the number of hops. In that model also, any receiver can (potentially) be a repair node, which Brad and BW both say is not realistic since that assumes many-to-many (like SRM) and that is simply not available in the real world. In this model only the members in the mesh can be repair nodes. Brad pointed out that this is how all of the CDN folk do things. > Other version assumes the creation/existence of a mesh which can use *any* number of different metrics for distance (not just a router-like "number of hops", which would have to count virtual hops, since it counts servers rather than routers). The first model can co-exist with the second, but the first cannot exist if the existence of the mesh in the first is assumed. <> --------------83EEF7F1661A5FD3901798F2 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Dear RMT'ers,

First of all please accept my apologies for the tardiness
in sending out these minutes/notes. Much thanks must go to
Sally Floyd and Bob Quinn for taking them during the meeting
Please take a moment to puruse them and point out any errors.

thanks!

Roger
 

------------------------------------------------------------

RMT Interim Working Group Meeting Feb 10, 2000
Minutes
-----------------------------

Attendees

Initials/Name/Interest
MH  Mark Handley            CC, NACK
SF  Sally Floyd             CC
DC  Dah Ming Chiu           ACK, TREE, CC
SK  Shivkumar Kalyanaraman  CC
LR  Lars Rasmussen          ALC
BQ  Bob Quinn               all aspects
CB  Carsten Borman          NACK (and the rest)
VO  Volkan Ozdemir          CC
YY  Yung Yi                 CC
DA  Deb Agarwal             all aspects
BL  Brian Levine            tree building, yoga (!)
SB  Supratek Bhattacharyya  tree building
IR  Injong Rhee             CC
AC  Adam Costello           GRA, tree building
ML  Michael Luby            ALC, FEC, CC
BLu Bruce Lueckenhoff       ALC
CP  Christos Papadolulos    GRA, tree building
JM  Joe Macker              NACK, ALC
BA  Brian Adamson           NACK, ALC
TH  Thomas Hardjono         Security
HR  Hayder Radha            CC/ALC
BW  Brian Whetten           track, CC
JG  Jim Gemmell             ALC, FEC, NACK
BC  Brad Cain               GRA, Tree building
TO  Tokuop Oishi
GR  Gursel Taskale          all

RK  Roger Kermode           all
LV  Lorenzo Vicisano        all
 

----------------------------------------------------

Interim Reliable Multicast Transport Working Group
Feb. 10 2000, ACIRI, Berkeley CA.
[RK: thanks to Sally Floyd]

Several people are late, because highway 880 was closed for a while.

There is a SMUG (Secure Multicast Research Group) meeting here
tomorrow.

Intro by Roger:
[Add a pointer to Roger's viewgraphs.]
Goals of meeting,
Overview of agenda.
Call to Arms:
Building-Block and Design Space drafts are waiting for review by Mark.
Mike: Are we on-schedule with the goals listed in our charter?
Roger: We are behind schedule.
The group will standardize building block and protocol instantiation
  documents.

The Guidelines draft:
[Add a pointer to Roger's viewgraphs.]
What is missing from here?
Mike: What about revision control between the PI (Protocol
  Instantiation) and the BB (Building Blocks) documents?  Do they
  cross-reference each other?
This comes to the API issue: what parts of the BB documents are
  referenced by the PI documents?  The BBs have, not an API, but
  a higher-level interface description.
NACK: There is a BB and a PI.  How does this work?
Answer: The BB has the more general stuff.  And a NACK PI
  might also use ACK-based stuff.
Jim: Can we do an example, with PGM?
BBs should discuss design tradeoffs.
Building blocks might be more applicable than just bulk transfer,
  though that is our immediate focus.
Mike: There is a danger of designing a BB without a PI in mind.
Maybe each PI should write its BBs, and then come together.
Mark, Sally: For NACK and TRACK, it is clear that there
  is a CC (Congestion Control) BB that can be broken out now, in
  parallel.  For ALC, there might not be as many BBs that can
  be broken out now.
FEC is a building block that can be taken out of ALC now.
What will go in the NACK BB?
Mike: Maybe the BB role can be more informational.
>From SMUG: BBs are coarse-grained, and might need more
  fine-grained components within them.
Mark: BBs should not include all possible options, but should
  narrow down the design space.
A call for BBs and PIs to start with overviews first, not the
  nitty-gritty details.  Out of today, perhaps we can end up
  with overviews of each of the BBs.

------------------------------------------------------

Congestion Control:

Mark:
TFRC, Unicast TCP-Friendly Rate Control
[Add a pointer to Mark's viewgraphs.]
Pointer to paper: "http://www.aciri.org/tfrc/".
The talk shows results from experiments and simulations with TFRC.
For unicast, the performance is very good.
Question: Simulations with TFRC: in simulations, TFRC tends to drop to
  zero with many flows, very high bandwidth?  Mark didn't see this, will
  look at it later.
Oscillations from smoothing the roundtrip time, and sending at 1/RTT:
  For unicast TFRC, we added RTT-based Congestion Avoidance.
  This is needed more for Drop-Tail than for RED queues, or for
  high levels of statistical multiplexing.
Issues for multicast:  timely feedback, measuring RTT.
Question: Does this apply to non-sender-based congestion control?

Mike Luby:
The work on CC for ALC is not finalized.
It is interesting to see if sender-based TFRC schemes will apply
  to receiver-based ALC.
VRC: [Viziano, Rizzo, Crowcroft], the RLC protocol.  Receivers join
  a layer and all lower-bandwidth layers.  Each layer has twice
  the bandwidth of the previous layer.
Join times are quick, and leave times might now be quick also.
In his opinion, the RLC approach has more power than the
  single-source approach.
For TCP-friendly issues, how does the RTT get taken into account?
Mark:  In small levels of stat mux, increasing the sending rate can
  dramatically increase the packet drop rate.  This is not the
  case with large-scale stat mux.
Mike: There is a lot of interesting work to be done.
Remark: Fine-grained video coding is the coming thing.

Roger:  Is the discussion leading to BBs?  Are we going into
  too much detail?
Brian:  We have a TRACK architecture overview, that shows how BBs
  fit together.

TEAR:
Similar to a TFRC building block.  Differs in how to measure a
  fair TCP throughput.
TEAR differs from TFRC in the receiver.  Instead of using the
  TCP-friendly equation, TEAR emulates TCP at the receiver.
  Takes a weighted average of eight TCP congestion control
  rounds.  TEAR trys to give a more accurate model of TCP.
Mark:  TEAR is sensitive to the pattern of losses.  And they
  differ in the modeling of retransmit timeouts.

Shiv Kalyanaraman:
Generic source-based multicast congestion control.
[Get a pointer to viewgraphs.]
This is sender-based congestion control.
No measurement support from the receiver set, except for NACKS or ACKS
  that are already there.
No aggregation support expected in the tree.
Congestion periods are broken into congestion epochs, which is
  a period with a single rate reduction, with time for the
  rate-reduction to diffuse to the congested sub-tree.
Mark: He is assuming a very low level of stat mux?  He is assuming that
  if the sending rate is increased, the packet loss rate increases also?
The protocol mimics TCP at every point.
They have implemented this in NS, and they have a PGM implementation.

----------------------------------------------
 

-----------------------------------
 RMT Interim Working Group Meeting

      -- Draft Minutes --
 [ RK: thanks to Bob Quinn]

    Feb 10, /2000 - Hosted by Aciri
     at ICSI in Berkeley, CA
-----------------------------------

Roger Kermode, RMT working group co-chair, started the meeting
at AM with 18 people present (we had 28 by 11AM) with a review
of the agenda.

Tentative Agenda
---------------------------------
09:00 - 09:10   10 mins   Agenda Bashing
                          [Roger]
09:10 - 09:10   10 mins   WG status update
                          bb + ds drafts
                          Recharter
09:10 - 09:20   10 mins   Call to arms/editorship selection update
                          [Roger]
09:20 - 09:40   40 mins   Guidelines Draft Update/Discussion
                         [Roger/Lorenzo/Allison]
                10 mins  draft outline
                30 mins  discussion
10:00 - 11:20   1hr20mins Congestion Control: [Handley/Flloyd?]
                10 mins  TFMCC update [Handley/Flloyd]
                10 mins  ALC implications for CC [Luby]
                10 mins  TEAR implications for CC [Rhee]
                10 mins  Generic source-based multicast CC
                         [Kalyanaraman]
                40 mins  discussion
11:20 - 12:20   1hr       NACK: [Bormann & Adamson?]
                10 mins  BB Update [Borman]
                20 mins  BB Discussion
                10 mins  PI Update [Adamson]
                20 mins  PI Discusion
12:20 - 13:00   1hr       Lunch
13:00 - 14:00   1hr       Asynchronous Layered Coding: [Luby]
                10 mins  BB update
                10 mins  Gemmell?
                40 mins  discussion
14:00 - 14:30   1hr       Tree-Building: [??]
                10 mins  table of contents update [Chiu]
                20 mins  discussion
14:30 - 16:00   1hr       TRACK progress [Whetten/Chiu]
                10 mins   [Whetten]
                10 mins   [Chiu]
                40 mins   Discussion
16:00 - 16:45   45 mins   VACANT
16:45 - 17:00   15 mins   Agenda bashing for Adelaide

RMT has been rechartered and the new charter--now approved
by IESG--is in place on the RMT working group webpage.
http://www.ietf.org/html.charters/rmt-charter.html
Mark Handley showed the new charter as it appears on
the RMT working group webpage.

Roger provided status for the existing documents.  The charter
is agressive and we are a bit behind at this point.  Many of
the documents are essentially done (though most are not issued
as Internet Drafts (I-D).  Generic Router Assist (GRA) is the
only exception.  The Multicast Congestion Control document is
due for Apri--after Addelaide--and it is acknowledged as the
most difficult problem, and the one that gates all others.

Mike Luby asked whether we expect to be doing work on both the
BBs or the instantiations, and Roger said, "Yes, both."

The Building Block (BB) Guidelines draft has been stalled.
That is likely a source of confusion, since many people may not
know how to proceed with creating a BB I-D without it.  The idea
behind the BB is tp create some framework definitions for Reliable
multicast transport (RMT) that exist for Real-Time Protocol (RTP)
format.

Goal: to help people write Building Block (BB)
and Protocol Instantiation (PI) drafts
- How BBs and PIs fit together
- Sections to be included:
 + applicatiblity statement
  = where to use and where NOT to use
  = known failure modes
 + BB:
  = bunctional description
  = abstract API for use by other BBs
 + PI (protocol instantiation):
  = core functionality not in BBs
  = which BBs are used
  = how they fit together
  = packet formats

Mark Handley and Sally Floyd (MH and SF): PI needs to be
specific about the application targets
- the PI *may* have some mechanisms that BB doesn't
  (but not all will)

Joe Macker (JM): The BB should describe the trade-offs

MH: Some BBs will be more generic as far as being applicable
to bulk file transfer alone, and others will not.

Mike Luby (ML): doing the BB first and the PI second seems
backwards. It would be better to do the PI, then try to
derive the commonalities that represent the BB.

MH: We alread have a lot of existing protocols that we
understand very well.

ML: But are these written down?

Roger Kermode (RK): Our hope is that people that have the
experience with specific protocols need to exchange their
experiences.

ML: But again, it is written down?

MH: We may well do some back-tracking after the fact, but
we expect that.

ML: I think it is important to do the PI first and write it
down.

MH: I think that ALC may be one where that is true

ML: Why is that?

SF: Because there are lots of TRACK and NACK based protocols
for which we understand the commonalities so it makes a lot
of sense to do the BBs in parallel with PIs.

Jim Gemmel (JG): I'm fuzzy about what goes into a BB, is it
going to simply say what NAK does or list many different
ways it could work.

MH: I think that NAK will have suppression mechanisms built
into it.

JG: Are you going to list the mechanisms/algorithms?

MH: We need to pick one and describe it.

JG: But there are so many

ML: You pick one and it may not be appropriate in all cases.

Thomas Hardjono (TH): In SMuG we have picked a number of them

RK: We are obviously still struggling with what a BB is, so
I tend to agree with Mike that we should concentrate on a PI
first.

??: I thought that the BB was supposed to describe what we
recommend with Interet health as the focus.

SF: It is a good idea to have things that refer to Internet
health, but we already have RFC 2357 (?) that describes the
requirements for any RM transport.

RK: I think we are approaching some concensus.

JG: Go write one and lets take a look at it

??: Suggested that we have an overview and functionality
description for each BB *first* then move into the  other
details

---
TFRC - TCP-Freindly rate control      Mark Handley
(Equation based congestion control)

- we thought we understood this (for unicast) a year ago,
but we did not and we don't know multicast yet.

Scripts and paper all available at http://www.aciri.org/tfrc

It is fair to TCP in general, although we have seen TCP
get beat up because it was too bursty

Key measures are loss fraction and round trip time

Measuring round trip time, there are oscillations in TCP
and with multicast the delays between these is longer.

To dampen oscillations but still gain RTT-based congestion
avoideance behavior, need inverse dependence on RTT but
lower gain.  <<see equation>>  The result of this is a
smoothing of the oscilllations.

- If you fix the RTT time, you get the oscillations, but
  if you don't (as described above) then they are smoothed.

- we've tried these things with a wide variety of Queuing
  congestion control mechmanisms, and it works well with
  all (though having RED reduces the need for this mechansism).

Issues for Multicast
- how to ensure timely feeback?  Delay reporting loss event
  fraction may affect dynamics
- How to measure RTT to all receivers quickly? Not a showstopper,
  but may affect how CCC fits together with other components
- RTT-based Congestion Avoidance is difficult (referring to
  the algorithm described above): It is not clear that this is
  necessary, but the consequences of not doing it are not yet
  fully understood.

??: What is the traffic load for reporting congestion control?

MH: You really want your NACK or ACK trafffic to report it,
and with aggregation points (TRACK or other local/shared
recovery points) you have additional delay.  None of this
applies to ALC though, of course (since it is one-way).

ML: Yes, but reading through your paper I got the impression
that a lot of it is based on the receiver, so it could well
be applicable.

ML: If you actually did an experiment with two TCPs then they
would not be fair to each other.  The one that has longer
timeout (say 10 times) would be 100 times more loss.

SF: I don't believe that loss rate would be 10 times more

Brian Whetten (BW): I don't beleive it would be, either.

JM: What about slow-start mechanism for multicast?

MH: We may not need one for multicast since the advantage
of having one is not clear yet.

----
Asynchronous Layered Coding (ALC) BB       Mike Luby

The work on ALC CC is not finalized yet, though there has
been some great work done so far.

- thing about ALC is that you can have different receivers
  receiving at different rates (determined by the number
  of groups they have joined, and streams they are receiving
  in parallel) and we need to take advantage of it.

- VRC (authors Lorenzo V. , R. and Crowcroft mechanism
  is used for this (also referred to as RLC for author names
  also ...for some unknown reason).

- Synchronization points happen more often at the lower
  layers than at the upper layers.  Layers are cumulative.

It is now a very course-grained CC, and we should make it
more fine-grained (more fine-grained than the synch points
can provide).  Current one gives a linear increase.

SF: A factor involved with whether you couild ramp up send
rater slowly is whether you have either small or large-scale
statistical multiplexing.

Hayder Radha (HR): ALC sounds much like MPEg-4, which provides
fine-grained scalability and uses many different multicast
groups (roughly 10-20).

--
Short talk on TEAR                      Rhee

- TFRC uses equations looking at 8 loss events that have
  occurred and is based on what it finds from the sender,
  whereas TEAR emulates TCP within the receiver and how.

MH: TEAR is sensitive to the pattern of losses (which
may be good or bad) and sensitive to the timeouts.

--
Generic Source-Based Mcast Congewstion Control
Shivkumar Kalyanaraman (RPI) <<missed the URL>>

- implosion control needed
- need timing info on Sender & Reciever (may need GPS at
  receivers)
- Need to know the (S,G) state

"Generic" means
- completely implemented at the source
- no measurement support from receivers
- no extra contol traffic inserted
- no extra fields
- no aggregation support expected
- should work with NAKs, HACKs, ACKs, bit maps or other
  reverse traffic which provides congestion and timing
  information

Weak requirements on RTT & loss estimation:
 - suppress NAKs from long RTTs (partial timing info)

Basic idea is that they devide congestion time periods
into "epochs" where the source reduces the send rate
exactly once and enough time is given for rate-reduction
to diffuse throughout the congested sub-tree.

They do not depend on the loss rate.

They have implemented it in their version of PGM.

MH: Seems like you are not depending on having large-scale
statistical multiplexing rate and that assumes that the
competing flows are doing the same thing, which is a flawed
assumption.

--
Brian Whetten said he has done a description of how the
BBs fit together from the perspective of TRACK.* reliability

======
short break
======

RK: This is a new process we've been doing with the BB approach,
so we need to describe it in more detail.

Boorman: The BB needs to be normative, we need to have it as
something that people can reference as opposed to something
that is not

BW: It should have exact algorithms and abstract APIs

SF: BBs need to describe design tradeoffs required for Application-
specific variations (e.g. optional feedback).

  Single Rate CC BB Team:
   Mark H (leader), Sally F., Injong, Brian W., Shiv, Supratek, Hursel,
   Joe Macker, Brian A.

  MultiRate CC BB Team:
   Mike L (leader), Lorenzo, Hayder, Injong, Jim Gemmel, Luigi Rizzo,
   Jon Crowcroft

??: I come from a satellite company and I'd like to see some
satellite-specific considerations described.

RK: We deal with the Big 'I' Internet and this includes the
satellite media, so it is included implicitly.

MH: It looks like Single Source multicast (e.g. PIM Source Only)
will have an earlier deployment than others so it is likely that
we will have one-way links as well as two-way, so in that context
satellite is not that special despite the fact it has a long fat
pipe (long delay and high bandwidth capacity).

RK: Can we have a document by Adelaide on Single Rate, Mark?

MH: Yes, we can have a *start* on a document.  We need at least
a first pass of *every* building block by that time.

RK: The due date for drafts is March 10 and we should really
strive to have something done by this time.

MH: We should also submit the names to the RFC editor beforehand
so it doesn't get delayed (we should do this on the mailing list).

RK: Ok, will do.

MH: Should we have discussions in sub-groups or on the main RMT
mailing list.  <<A number of people responded that they would
prefer having this traffic on the main RMT mailing list>>

<<begin from whiteboard>>
CC Building Block Guidelines
-----------------------------
Must be normative - exact specific algorithms and abstract APIs

Discussions of tradeoffs - application specific variations (e.g.
optional feedback).  Cover design space.

Purpose: RFC 2357 and Sally Floyd's Congestion Control Principles
draft, see http://www.aciri.org/floyd/papers/draft-floyd-cong-01.txt
  + 2 parts:
    = Mandatory to satisfy IESG reqs
    = Application specific

Requirements for other BBs:
 - what messages can be piggy-backed (existing BB msgs and
    additional msgs) .
 - loss detection
 - RTT measurement

Two Separate BBs:
 -> single source (e.g., PIM-SO)
 -> Others (single rate)
   - satellite, asymmetric, wireless,

GRA Considerations

target scale (in terms of number of receivers).
<<end from whiteboard>>

---
How TRACK fits with other BBs                 Brian Whetten
(( his view of what needs to go into BBs ))

Goals
- functional decomposition across other BBs
- sees TRACK as a superset of NACK

Exponential back-off on loss detection

Unicast NACK generation
 - issue: NACK needs multicast NACKS?

response to retransmission request
GRA signaling
Integration with TRACK hierarchy
 - how do you do this well

SF: Why is this included here?

BW: We repeat it in both places

Question: Since it is a superset of NACK, why have a separate BB?

BW: Interesting thought.

MH: We need to do suppression so the question is how to do it.
You can do it by a tree or not, so the discussion needs to talk
about it with that focus

MH: One thing missing here is how it interacts with and uses FEC.

Lorenzo Vicanso (LV): Yes, FEC is very mixed with suppression.

MH: FEC itself is not in there, but a description of its
functionality is.

??: Why do you call it NACK when it should really be a generic
feedback mechanism?

BW: We have differentiated the feedback (for CC) and the
NACK for data loss and the TRACK since it has to deal with
hierarchy.

Brad Cain: What do you think the biggest issue is?

BW: The issue of how and when you deal with the NACKs.

FEC BB:
- input of a (sub) window of data packets
 + issue: packet nameing
- creating parity packet
 + issue: exhaustion of parity packets
 + proactive parity (which block owns it)?
- flush data stream with only a small sub-window
- FEC decode
- Bind to different codecs

LV: It seems that some of these issues (like flush) belong
in the protocol instantiation.

BW: This is a highlight of the functions and not specifications
of what they are doing

ML: I would just talk about the protocol and not how it will
work in all protocol instantiations.  That cannot work.

RK: The model to look at for this framework is RTP, where
there is enough generality to allow a common, versatile
framework.

LV: You need an API for making state available

ML: There is a way to describe FECs in general without going
into detail with exactly how to use them.

??: This has actually been done in the AVT RFCs that deal
with codecs (may still be I-Ds at this point).  They may not
be exact, but it is a good thing to start with.

LV: You can define blocks and when you can reveal the blocks
and deal with them.

TFMCC BB:
- Initialization
- Receiver measuraments
 + issue: RTT measurements
- Receiver feedback (on TRACK/NACK)
 + Issue: how to bias NACK timers?
- hierarchical aggregation
- sender rate control

MH: There's no requirement for interoperability until you get
into a PI.  The packet formats are defined in terms of funcionatlity
rather than generically as "feedback" to be efficient in terms of
size used.

GRA BB (draft-ietf-rmt-gra-arch-00.txt):
- Core, simple router functionality
 + issue: how to instantiate this?
- signaling guidelines
- NACK

Brad Cain (co-author): we will have a separate document that will
include feedback mechanism defined and we will define packet
format.  It will be incrementally deployable (as spec already
says).  We will be dealing with server-to-server traffic, which
is the auto-tree configuration.

Auto-Tree Configuration BB:
- Discover hierarchy that matches the multicast topology
- works in all environments
- provides children with an address list of candidates
 + if/when first fails you go to second one

BC: You need to discover namers, create hierarchy (some sort
of routing protocols where you abstract away who is closest
to the root).

JM: Is this going to be a routing-ish shared tree?

BC: We are not doing that level of detail ...we are not creating
PIM over a mesh.  Once you abstract away what a possible root
could be (source, RP, etc.), then there has to be a route from
whatever it is.  Then that has to be...???  I wouldn't touch that
one with a ten-foot pole.  There will be packets between servers,
and there will need to be a way to measure distance between server
to source and you can do that LOTS of different ways.  You need
to know what the metric means.

BW: Yes, I agree that the problem is not yet well defined

======
lunch break
======

<< Brian Whetten, on TRACK BB Requirements, continued >>

Common Packet Headers
- Data Naming
 + sequence number, FEC offset
 + issues: Add object ID? Need sequential packet numbering.
   Need to support application level multicast
- Session naming
 + stream ID
 + TRACK may need a Tree ID
- Also issues with Application Level Framing (Talarian,
  TIBCO and FastForward are three examples), since you are
  multiplexing at a different level

MH: There seems to be three sequence spaces:
 - packets within FEC block
 - FEC blocks themselves
 - Object ID itself

 You might be able to build over to create frames over
 that, but it must be at the object level to get reliability.
 I think it might be worthwhile to go down this path to see
 what comes out, what meta-information we need.

BW: The other consideration that is important is the number
of bits we add to support this.

MH: My view on bits is don't worry about it, since it is only
on low-bandwidth links that it is a concern

Security BB
- Really SMuG's area and our area
- Transports only job is to protect itself
- Interface to key managerment is what we need
- IPSec for lightweight version

TRACK functions
- hierarchy creation and maintenance
 + join, leave, falure recovery, keepalives
 + local multicast groups for control, retransmission
- parameter initializeation/distribution
 + server and tree-wide
- source ordered, unordered, time bounded (?)
- network management

JM: Is there a new security consideration for ACK Aggregation

TH: At last IETF I talked about a mechanism whereby an intermediate
point that received a NACK would have to forward them upstream
for signing (so intermediate point does not need to be a trusted
participant).  Authentication and trust models are the issues.

LV: The NACK authentication is an end-to-end issue

TH: Yes, but NACKS are from routers

BW: Routers don't issue NACKs, however.  Routers create the tree
(for TRACK).

MH: Tree-based protocols help you to generate round trip times.

TRACK Issues
- Kill TN and Aggregators?
 + shared tree versus per-source tree?
- Can we have dynamic DR/receivers
- Multicast address sharing

BW: Is top of the tree always co-located with the sender?

MH: There are lots of different ways to build trees

BW: You can have multiple data sources for a single tree

BC: It would be good if anyone desiging NACKs talk to
him and BL about how to define them for each of the
BB type (e.g. NACK, TRACK, ALC), specifically in terms
of application interface and packet formats.

======
We then had break-out meetings for separate sub-groups:
"ALC", ""NACK," and "Tree Building" (in quotes since these
are very loosely defined).  Here are the topics discussed:

"ALC":
 - FEC
 - PI for ALC
 - Congestion Control

"NACK":
 - PI versus BB
 - NACK
 - Congestion Control

"Tree Building"
 - Auto Tree config

=========
 Wrap Up
=========
Roger Kermode on Auto-Tree Creation BB discussion:
- Preconfigured solution
 + assumes the existence of a mesh of delivery servers
    (which may be statically configured or dynamically
    generated):
 + requires existing infrastructure on internal nodes

- Ad hoc solution
 + does not require predeployment
 + assumes mesh discovery protocol
 + no GRA
 + no TTL scoping (needs to support PIM_SO)
 + no static config info in hosts

MH: Do you have any reference implementations for these models?
I'd like to see some running code.

Mike Luby on ALC:
 - we had lots of concensus and progress
 - We also took on the FEC BB

TRACK:
 - what identifies a source or a receiver?

NACK:
 - We also discussed FEC a lot too since it is tied in

Rather than having different mailing lists for each subgroup,
Roger proposed that everything go to RMT and we preface subjects
with what the topic is relevant to (and add "PI" as a suffix if
that's the topic) FEC, TREE, ALC, NACK, CONG_{SR | MR}, TRACK,
GRA, or GUIDE.  He will send a message to the RMT mailing list
describing this.

<<end>>
 
 
 

=========================================
 Notes from TRACK sub-group Discussions
 RMT Working Group Meeting 2/6/00
=========================================
blame bob quinn <rcq@stardust.com> for any innaccuracies

Motivation for creating a tree
- Good for error control and congestion control
- Distributed aggregation (caching hierarchies, e.g., for
  use in a Content Distribution Network (CDN))
- Anycast
- Security, group key management
- Distributed gaming/simulations

All have similar requirements

Why is it useful?
1) hierarchical construction assists with load balancing
2) topologically aware aggregation
3) topologically aware subcasting

First is sufficient (2nd and 3rd are efficient).

Why by aware of topography?
- topologically based structures have dramatic performance benefits
 + localized aggregation
 + subcasts that are focused towards downstream logical descendants
 + allow use of subcast, period.
 + ensures reduced latency between pairs

Applications
- local aggregation
 + error, congestion control, CDN, security
- focused subcasts
 + error, congestion, security
- reduced latency between pairs
 + gaming, anycast

BW: So is the goal topological congruency?
Brian Levine (BL): Yes
BW: Would anyone debate that?
BL: yes.  You can't do it now without difficulty, but that
  does not mean it is not something we should *try* to do.
BC: That is something we should strive for.
BW: There are some that would say it is better for error
  control
BL: I don't agree with that
BW: I just want to talk about it since it is relevant to
  asymmetric routing, among other thigns.
BC: That is a really tricky issue and the other reason
  is inter-domain
BW: Exactly, which is why single-AS is going to rule
BC: Exactly.
BW: Should we scope it to a single domain?
  <general disagreement>

"Easy" way to do topo-aware
- use GRA!!
- Source periodically multicast packets with GRA and
 router alert (MD5 Auth)
 + They go down the tree from a parent
 + I'm assuming we are doing Express mode stuff
- GRA routers with their IP address in the payload of
the packet (perhaps both in and out interfaces ...?)
 + Each hop adds as packet traverses
 + As there are more routers, you get a better idea
- Receivers subcast from last revised router announcing
  their path strings
- Receivers pick parents, send unicast to confirm
- Or...new mtrace messages (added by Brad Cain)
 + This would trace down the tree (though we have not
  yet figured out the format ...though many don't like
  mtrace since it gathers statistics, has latency and
  adds overhead)

??: There was a guy at MCast2000 who said that the hyperqueue
  could build a tree very quickly
BC: There is part of this that people can use to do other
  tricky things.  For example how do you find out how close
  you are to a source or an intermediate routers and there
  are lots of ways to do it.

Two problems with finding a metric that's good: congruency
and how best to announce to the group

Breaking Up the Problem:
- Neighbor Discovery
- routing-like protocol
 + who is closest to the "source" (for mcast)
 + who is closest to other point (e.g. server)
- How to find distance to server or seoruce?
- How to make it generic?
  + can we do it for others than reliable multicast, such
   as the content delivery people.
- Fault tolerance

BC: Looking at a graph or mesh of servers and over the top
  of that there is some sort of protocol that you use to build
  a hierarchy in the server to server protocol itself.  To do
  so you need to have some sort of metric, such as who is
  closest to data source or RP.

You discover a set of neighbors within a scope (that's how
the mesh is built), then over that mesh you establish the
tree.

BW: That is basically what we are looking at but that could
  be a heavy weight protocol.

BC: You can statically configure the mesh (which will most
  often be the case anyway ...that's the way these content
  distribution network guys are doing already).

RK: We have to be able to exist where GRA doesn't already
  exist.

BL: If we didn't bring up topological awareness then
  we woudln't have any issue with non-GRA implementations.

We are being passed-by and need to do *something*:
- companies can do non-topo aware without us, though
 standards are nice
- eventually they *will* do topo-aware without us
- As IETF'ers we should make recommendations

BW: The barriers to getting GRA into all the routing
  infrastructure is so high that from a practical standpoint
  we should be able to use it without GRA.

BL: I think it will take 3 years to get GRA widely available
BW: I think that is really wishful, which is why we should
  think about new mtrace messages.
BC: The mtrace command needs access control (password, maybe?)
  since it reveals the tree which can be very dangerous.
RK: If you are going to use mtrace, think about a network
  with 10000 nodes
BC: MTrace would not scale to that many receivers
BC: you can try to match receivers with nearest server
  or make tree closest to source.  The content delivery is
  focused on making caches close by to receivers.
??: Seems a question of how tall you want to make the tree
  with respect to how much fan-out there is (the optimality
  of the tree).
BC: Yes, that all relates to how you build the tree

  Miriam Kadansky did a doc that relates to requirements
   BL referenced this and created slides from the TOC.

Dah Ming (DM): How the the tree is formed and then used.
  This was a strawman for generating discussions.  We have
  lots of information about tree optimization and maintenance
  as well as tree building and what I'd like to see is a
  discussion of how much of this belongs in the BB.

BW: I think only the building of the tree is important.

BC: I think there should be two layers: a base layer that
  can be useful for a lot of things and the second that is
  specific to reliable multicast.

RK: Auto-Tree Requirements (RM specific)
--------------------------
1) Aggregation of things like ACKs, NACKS, congestion control
2) Subcasting
 - parent to child unicast (application level)
 - parent to all descendents local multicast group
 - parent to child (GRA)
3) Others (non-RM specific)
 - group membership
 - list of GRA-capable routers
 - billing

RK: It has to be spelled-out in the draft what is RM-specific
  and what is not.

TH: Some mechanisms used to design the tree are exactly the
  same that is needed to deliver some of the services that the
  tree is supposed to support.
BW: So, for example, you could use subcast to do auto tree
  configuration.
TH: Good examplee

BW: Goals:
 - Perfect topology congruence
 - failing that, do something not stupid
 - list of parents

BC: Where does the metric fit in?  How do you determine a
  "perfect tree?"  What does the API give you?
BW: These are the list of parents and the metric(s). There
  are other interactions to prevent loops (for example).  We
  may be able to pick one metric.
BL: we should have one metric in mind.
BC: There are a number of different possibilities.
RK: You are building a tree to do what, connect sources with
  receivers or with end-points??
DM: The DR could be either the source or the distribution head.
BW: The head of the tree is always the source

BC: the problem is that if you are given just a list of neighbors
  and metrics, then you could construct a tree that has loops.
BW: I was assuming it was at least an ordered list so there are
  no loops.
BL: you can always override this, so we must assume that it
  has no loops.  Congurence is the goal and besides, it is not even
  a tree if it has loops.
DM: There are diffferent ways to make sure you don't have a loop,
BW: Yes, but if you just know the depth of the tree then this is
  enough information to create a non-looped system.
DH: That implies the tree is built top-down
BW: The issue comes down to work
BC: right.
BW: Who has to do the job
BC: The loop protection depends on what info is exchnaged between
  nodes.

Requirements (according to BW)
- Universally deployable
 + multi-AS
 + All multicast routing
 + GRA
- Safe
- Receiver auto-config
 + e.g. receivers can find their nearest server
- Keep it Simple

BC: I think the receiver auto-config is DONE: DNS
  (though Anycast or a web-page or other out-of-band
  mechanism could be used also)
BW: I am just defining high-level requirements without
  considering solutions

BC: We need to be able to "prune protocols" (to quote
  Steve Deering) to make it simple

BC: Do we want to get into Policy metrics when considering
  inter-AS (inter-domain)?
BW: I really don't think we want to go there.

BC: All protocols are source based now
BW: Huh?  Applications don't have a way to specify the
  source.

??: the tree building protocol is running all the time?
BW: Yes, so you can ask anytime for what parents are

RK: It sounds like you are trying to punt things away, so
  if it does not get done here where does it get done?
BW: In TRACK
BC: We still need to determine the line between TRACK and
  here.
BW: The issue is that keep-alives, HACK packets, get generated.
  It is control path versus data path issue.
RK: I like that separation between control and data paths.
  This document should be sufficient to create a control path
  and that control path is used to deliver data.
BW: There is realistic three peices here: all error packets
  are part of data.  We want auto-tree config information.
BC: I agree they are separate, but think there is anough
  commonality to keep them together.
BW: I am abstracting out configuration information for control

RK: Can we separate out like:
 - Ctrl path: tree creation and maintainenace
 - Data path: "repair" PI specific control

<< short diversion into discussing whether it is possible to
create a generic BB or whether we have to start with a PI
...the challenge being whether we can have something generic
without getting into protocol details >>

BC: You can do something really simple, but if it is going
  to be that minimal, there is some question about whether
  it is useful.
TH: It has to work, so it can't be that thin.  The thing is
  that to be useful, we need to agree on some common elements.
BW: I think the NACK BB is going to be very short (deal with
  retry timer and action) and I suspect that we can make this
  Tree Building BB just as small.
BC: CDN people want all these things.  I don't know where
  the line is between generic BB and PI.

??: There are two main things: discovery and maintenance.
DM: Yes, but it is more complex since there are different
 scenarios (e.g. late joins).

RK: Tree "functions"
- Discovery: learning *possible* parents (manually or auto)
- Construction: Joining the tree
 + BC: e.g. applying Dijkstra and creating link-state
- Maintenance: Fail over, leaving
- Service Hooks (sub-cast, aggregation, etc.)

BW: Problem is you can't discover parents without considering
  where the source is.
BC: What is the signal for generating a tree, is it that a
receiver joined or that a source is there?
BW: I would say when receiver joins
BC: I would agree with that

RK: Discovery:
- who starts the process?
 + source: top-down tree generation
 + receiver: bottom up tree generation

BW: The way the world actually works is you have a collection
  of Sources, a collection of potential DR's (intermediates)
  and receivers (he illustrated on board with three layers).
BC: We are not dealing with the receivers to servers in this
  tree building (which is a server location problem ...and we
  can safely assume that DNS solves this).  Most of the time
  the configuration of the mesh of intermediates is statically
  configured (99% of the time) ...call it "the Mesh."  At this
  point there are NO TREES yet (an important point), so there's
  no concept of loops at this point since nothing is source
  specific.

BW: Mesh:
1) neighbor disovery
2) senders announce
3) receivers initiate join

BC: Alternately, the source finds a server
DM: Yes, there may be many servers that are not relevant
  to a source
BC: Ok, yes, so let's assume that the source does NOT
  announce to the servers.  We already know how to do this
  and it's called multicast routing (using PIM).  It requires
  that each server knows the metric distance to the source(s).
BW: Ok, so we're done!  We will just run another routing
  protocol (along with the one below us at the IP layer that
  we cannot access and the one that may be above at the
  application level).

??: Ok, this assumes that there is a mesh, but what if
  we don't assume this?
BC: I disagree, since if you look at anything on the net
  it is formed as a mesh and there are a lot of administrative
  issues about who can talk to who.

Lots of discussion/debate about whether we can assume that
the mesh is avilable as preconfigured infrastructure.  To do
auto configuration we cannot assume many-to-many SRM-like
discovery.

Dah Ming and BL agreed that having the intermediate mesh
assumed makes having the receivers going directly to senders
impossible (e.g. so the receivers can organize into a tree
without having an intermediate layer).

BL: Could send from source with IP list, as I described earlier.
DM: Yes.
BC: Ok, if source sends magic packet then each receiver
  picks a receiving parent.
DM: Yes.  This should be allowed and the static intermediate
  layer could be optional.
BL: Yes, and then any intermediate node can declare that
  they don't want to be part of the tree.

-> Some disagreement about which of the two models should be
   the primary requirement.

RK: My dream protocol that I want
- Doesn't require GRA (but be compatible with GRA)
- Doesn't use TTL scoping
- Needs to work in PIM source only (PIM-SO)
- Doesn't require config info in hosts
- Doesn't require statically deployed mesh

BC: You may want to determine your tree with metrics other
  than hops (e.g., server load, geographic location, etc.).

BL (and others): the one where receivers can be DRs makes
  the static mesh possible, but the converse is NOT true.
BC: I disagree.  Since not all receivers can send, it becomes
  an access control issue that assumes many-to-many multicast
  is possible.

Summary of differences between the two models:

> Dynamic Discovery version sends a probe from the source and
  each *logical* hop adds its addres and the metric you end up
  using is a router-like distance metric that uses the number
  of hops.  In that model also, any receiver can (potentially)
  be a repair node, which Brad and BW both say is not realistic
  since that assumes many-to-many (like SRM) and that is simply
  not available in the real world.  In this model only the members
  in the mesh can be repair nodes.  Brad pointed out that this
  is how all of the CDN folk do things.

> Other version assumes the creation/existence of a mesh
  which can use *any* number of different metrics for distance
  (not just a router-like "number of hops", which would have
  to count virtual hops, since it counts servers rather than
  routers).

The first model can co-exist with the second, but the first
cannot exist if the existence of the mesh in the first is
assumed.

<<end>> --------------83EEF7F1661A5FD3901798F2-- --------------12DAB1FB4EB5F784B0A83607 Content-Type: text/x-vcard; charset=us-ascii; name="Roger.Kermode.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Roger Kermode Content-Disposition: attachment; filename="Roger.Kermode.vcf" Content-Transfer-Encoding: 7bit begin:vcard n:Kermode;Roger tel;cell:+61-408-212-284 tel;fax:+61-2-966-0501 tel;work:+61-2-9666-0558 x-mozilla-html:FALSE url:www.motorola.com.au/arc/ org:Communications And Networking Lab;Motorola Australian Research Centre adr:;;Locked Bag 5028;Botany;NSW;1455;Australia version:2.1 email;internet:Roger.Kermode@motorola.com title:Principal Research Engineer/Lab Manager fn:Roger Kermode end:vcard --------------12DAB1FB4EB5F784B0A83607-- From owner-rmt@listserv.lbl.gov Sun Mar 5 08:03:46 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 IAA08322 for ; Sun, 5 Mar 2000 08:03:46 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id EAA14554; Sun, 5 Mar 2000 04:26:25 -0800 (PST) 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 EAA14550 for ; Sun, 5 Mar 2000 04:26:23 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA04788 for ; Sun, 5 Mar 2000 04:26:23 -0800 (PST) Received: from motgate.mot.com (motgate.mot.com [129.188.136.100]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA04784 for ; Sun, 5 Mar 2000 04:26:22 -0800 (PST) Received: [from pobox.mot.com (pobox.mot.com [129.188.137.100]) by motgate.mot.com (motgate 2.1) with ESMTP id FAA25363 for ; Sun, 5 Mar 2000 05:26:21 -0700 (MST)] Received: [from homer.arc.corp.mot.com (homer.arc.corp.mot.com [217.1.10.38]) by pobox.mot.com (MOT-pobox 2.0) with ESMTP id FAA21864 for ; Sun, 5 Mar 2000 05:26:19 -0700 (MST)] Received: from motorola.com ([217.2.31.248]) by homer.arc.corp.mot.com (8.9.3/8.9.3) with ESMTP id XAA12338 for ; Sun, 5 Mar 2000 23:23:23 +1100 (EST) Message-ID: <38C25197.2B860A5D@motorola.com> Date: Sun, 05 Mar 2000 23:22:47 +1100 From: Roger Kermode X-Mailer: Mozilla 4.7 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 To: rmt-list Subject: RMT Call for agenda items for Adelaide Content-Type: multipart/mixed; boundary="------------372261E48FE8926E5CBF5D96" Sender: owner-rmt@lbl.gov Precedence: bulk This is a multi-part message in MIME format. --------------372261E48FE8926E5CBF5D96 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dear RMTers, The draft ietf-draft deadline is rapdily approaching...so it's time that we start to put together an agenda for Adelaide. Let's keep the momemtum going from the interim meeting, please send items for disucssion to the chairs as soon as you can cheers, Roger FYI ...We have two chunks of time booked, so there should be plenty of time for discussion: Tuesday 1545-1645, 1700-1800 Wednesday 0900-1130 --------------372261E48FE8926E5CBF5D96 Content-Type: text/x-vcard; charset=us-ascii; name="Roger.Kermode.vcf" Content-Description: Card for Roger Kermode Content-Disposition: attachment; filename="Roger.Kermode.vcf" Content-Transfer-Encoding: 7bit begin:vcard n:Kermode;Roger tel;cell:+61-408-212-284 tel;fax:+61-2-966-0501 tel;work:+61-2-9666-0558 x-mozilla-html:FALSE url:www.motorola.com.au/arc/ org:Communications And Networking Lab;Motorola Australian Research Centre adr:;;Locked Bag 5028;Botany;NSW;1455;Australia version:2.1 email;internet:Roger.Kermode@motorola.com title:Principal Research Engineer/Lab Manager fn:Roger Kermode end:vcard --------------372261E48FE8926E5CBF5D96-- From owner-rmt@listserv.lbl.gov Mon Mar 6 05:27:38 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 FAA01680 for ; Mon, 6 Mar 2000 05:27:37 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id BAA16647; Mon, 6 Mar 2000 01:43:23 -0800 (PST) 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 BAA16642 for ; Mon, 6 Mar 2000 01:43:19 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA04675 for ; Mon, 6 Mar 2000 01:43:19 -0800 (PST) Received: from smtp2.cluster.oleane.net (smtp2.cluster.oleane.net [195.25.12.17]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA04668 for ; Mon, 6 Mar 2000 01:43:17 -0800 (PST) Received: from oleane (dyn-1-1-132.Vin.dialup.oleane.fr [195.25.4.132]) by smtp2.cluster.oleane.net with SMTP id KAA78930; Mon, 6 Mar 2000 10:42:56 +0100 (CET) Message-ID: <00f401bf874f$be56f800$0401a8c0@oleane.com> From: "Peter Lewis" To: Subject: SIP 2000 International Conference Date: Mon, 6 Mar 2000 10:38:24 +0100 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_00F1_01BF8758.19B928A0" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2314.1300 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Sender: owner-rmt@lbl.gov Precedence: bulk This is a multi-part message in MIME format. ------=_NextPart_000_00F1_01BF8758.19B928A0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Unknown and even rejected by many vendors and operators only a few = months ago, SIP is on the brink of making a definitive name for itself.=20 Visit the SIP 2000 International Conference programme: http://www.upperside.fr/basip.htm =20 ------=_NextPart_000_00F1_01BF8758.19B928A0 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Unknown and even rejected by many vendors and operators only a few = months=20 ago, SIP is on the brink of making a definitive name for itself.
Visit the SIP 2000 International Conference programme:
http://www.upperside.fr/basip.= htm
 
 
------=_NextPart_000_00F1_01BF8758.19B928A0-- From owner-rmt@listserv.lbl.gov Wed Mar 8 20:23:55 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 UAA19188 for ; Wed, 8 Mar 2000 20:23:54 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id QAA01920; Wed, 8 Mar 2000 16:35:05 -0800 (PST) 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 QAA01916 for ; Wed, 8 Mar 2000 16:35:03 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA21004 for ; Wed, 8 Mar 2000 16:35:03 -0800 (PST) Received: from sj-msg-core-2.cisco.com (sj-msg-core-2.cisco.com [171.69.43.88]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id QAA21000 for ; Wed, 8 Mar 2000 16:35:02 -0800 (PST) Received: from lorenzo-u10.cisco.com (lorenzo-u10.cisco.com [171.69.65.85]) by sj-msg-core-2.cisco.com (8.9.3/8.9.1) with ESMTP id QAA11874 for ; Wed, 8 Mar 2000 16:34:31 -0800 (PST) Received: from localhost (lorenzo@localhost) by lorenzo-u10.cisco.com (8.8.8-Cisco List Logging/CISCO.WS.1.2) with ESMTP id QAA29554 for ; Wed, 8 Mar 2000 16:35:09 -0800 (PST) Message-Id: <200003090035.QAA29554@lorenzo-u10.cisco.com> X-Authentication-Warning: lorenzo-u10.cisco.com: lorenzo owned process doing -bs X-Mailer: exmh version 2.0.2 2/24/98 To: rmt@lbl.gov Subject: FEC BB draft Mime-Version: 1.0 Content-Type: multipart/mixed ; boundary="==_Exmh_-17452598970" Date: Wed, 08 Mar 2000 16:35:09 -0800 From: Lorenzo Vicisano Sender: owner-rmt@lbl.gov Precedence: bulk This is a multipart MIME message. --==_Exmh_-17452598970 Content-Type: text/plain; charset=us-ascii Dear RTM-ers, As established, the ALC subgroup has worked on the attached FEC BB draft. We intend to submit it by Friday. As this BB also interests other subgroups, we are circulating it to collect comments. This draft addresses the following: - gives a general description/classification of the FEC codes pertinent to RMT. - discusses FEC-related information needed in packet fields. - addresses security issues. Please note that this is only the 1-st draft. Things can be changed later. In particular my guess is that section 3, that describes packets fields, will be expanded and detailed in the next revision of this spec. cheers, Lorenzo Vicisano --==_Exmh_-17452598970 Content-Type: text/plain ; name="draft-ietf-rmt-bb-fec-00.txt"; charset=us-ascii Content-Description: draft-ietf-rmt-bb-fec-00.txt Content-Disposition: attachment; filename="draft-ietf-rmt-bb-fec-00.txt" RMT Working Group M. Luby INTERNET DRAFT L. Vicisano Expires 8 September 2000 L. Rizzo J. Gemmell J. Crowcroft B. Lueckenhoff 8 March 2000 Reliable Multicast Transport Building Block: Forward Error Correction Codes Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved. Abstract This memo describes the use of Forward Error Correction (FEC) codes within the context of reliable IP multicast transport and provides an introduction to some commonly-used FEC codes. 1. Rationale and Overview Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 1] Internet Draft RMT BB, Forward Error Correction Codes March 2000 There are many ways to provide reliability for transmission proto- cols. A common method is to use ARQ, automatic request for retransmission. With ARQ, receivers use a back channel to the sender to send requests for retransmission of lost packets. ARQ works well for one-to-one reliable protocols, as evidenced by the pervasive suc- cess of TCP/IP. ARQ has also been an effective reliability tool for one-to-many reliability protocols, and in particular for some reli- able IP multicast protocols. However, for one-to-very many reliabil- ity protocols, ARQ has limitations, including the feedback implosion problem because many receivers are transmitting back to the sender, and the need for a back channel to send these requests from the receiver. Another limitation is that receivers may experience dif- ferent loss patterns of packets, and thus receivers may be delayed by retransmission of packets that other receivers have lost that but they have already received. This may also cause wasteful use of bandwidth used to retransmit packets that have already been received by many of the receivers. In environments where ARQ is either costly or impossible because there is either a very limited capacity back channel or no back chan- nel at all, such as satellite transmission, a Data Carousel approach to reliability is sometimes used [AFZ95]. With a Data Carousel, the sender partitions the object into equal length source symbols, places them into packets, and then continually cycles through and sends these packets. Receivers continually receive packets until they have received a copy of each packet. Data Carousel has the advantage that it requires no back channel because there is no data that flows from receivers to the sender. However, Data Carousel also has limita- tions. For example, if a receiver loses a packet in one round of transmission it must wait an entire round before it has a chance to receive that packet again. This may also cause wasteful use of bandwidth, as the sender continually cycles through and transmits the packets until no receiver is missing a packet. FEC codes provide a reliability method that can be used to augment or replace other reliability methods, especially for one-to-many relia- bility protocols such as reliable IP multicast. Ideally, FEC codes in the context of IP multicast can be used to encode an object into packets in such a way that each received packet is fully useful to a receiver to reassemble the object regardless of previous packet reception patterns. Thus, if some packets are lost in transit between the sender and the receiver, instead of asking for retransmission using ARQ or waiting till the packets are resent using Data Carousel, the receiver can use any other subsequent equal number of packets that arrive to reassemble the object. This implies that the same packet is fully useful to all receivers to reassemble the object, even though the receivers may have previously experienced different packet loss patterns. This property can reduce or even eliminate the Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 2] Internet Draft RMT BB, Forward Error Correction Codes March 2000 problems mentioned above associated with ARQ and Data Carousel and thereby dramatically increase the scalability of the protocol to ord- ers of magnitude more receivers. For some reliable IP multicast protocols, FEC codes are used in con- junction with ARQ to provide reliability. For example, in a first round all of the source symbols could be transmitted, and then receivers could report back to the sender the number of symbols they are missing from each block. Then, the sender could compute the max- imum number of missing symbols from each block among all receivers, and then transmit that number of redundant symbols for each block. In this case, even if different receivers are missing different sym- bols in different blocks, transmitted redundant symbols for a given block are useful to all receivers missing symbols from that block. For others, FEC codes are used in a Data Carousel fashion to provide reliability, by cycling through and transmitting the encoding symbols instead of the source symbols. For example, suppose an FEC code is applied to the entire object consisting of k source symbols to gen- erate n encoding symbols with the property that the entire object can be reassembled from any k encoding symbols, and the sender cycles through and transmits the n encoding symbols in the same order in each round. Then, a receiver can join the transmission at any point in time, and as long as the receiver receives at least k encoding symbols during the transmission of n encoding symbols then the receiver can completely recover the object. This is true even if the receiver joins the data carousel in the middle of a round. For yet other reliable IP multicast protocols the sole method to obtain reliability is to use FEC codes. For example, the sender can decide a priori how many encoding symbols it will transmit, use an FEC code to generate that number of encoding symbols from the object, and then transmit the encoding symbols to all receivers. This method is for example applicable to streaming protocols, where the stream is partitioned into objects, each object is encoded into encoding sym- bols using an FEC code, and then the sets of encoding symbols for each object are transmitted one after the other using IP multicast. The large on demand codes described below have the property that the FEC encoder can generate sequentially as many encoding symbols as are desired on demand. Thus, reliable IP multicast protocols that use large on demand codes generally rely solely on these codes for relia- bility. In the general literature, FEC refers to the ability to overcome both erasures (losses) and bit-level corruption. However, in the case of IP multicast, lower network layers will detect corrupted packets and discard them. Therefore, an IP multicast protocol need not be con- cerned with corruption; the focus is solely on erasure codes. The Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 3] Internet Draft RMT BB, Forward Error Correction Codes March 2000 payloads are generated and processed using an FEC erasure encoder and objects are reassembled from reception of packets using the corresponding FEC erasure decoder. The primary purpose of using FEC codes is to ensure that minimal number of packets need be received in order for a receiver to reassemble an object. Reception overhead is used to measure how close a protocol comes to achieving this minimum. Reception overhead is the aggregate length of packets needed to recover the object beyond the object length, measured as a percentage of the object length. For example, if it takes 15 MB of packets in order to recover a 10 MB object, then the reception overhead is (15 10)/10 times 100, or 50%. The minimal reception overhead possible is 0%. 2. FEC Codes 2.1. Simple codes There are some very simple codes that are effective for repairing packet loss under very low loss conditions. For example, one simple way to provide protection from a single loss is to partition the object into fixed size source symbols and then add a redundant symbol that is the parity (XOR) of all the source symbols. The size of a source symbol is chosen so that it fits perfectly into the payload of a packet, i.e. if the packet payload is 512 bytes then each source symbol is 512 bytes. The header of each packet contains enough information to identify the payload. In this case, this includes a symbol ID. The symbol IDs are numbered consecutively starting from zero independently for the source symbols and for the redundant sym- bol. Thus, the packet header also contains an encoding flag that indicates whether they symbol in the payload is a source symbol or a redundant symbol, where 1 indicates source symbol and 0 indicates redundant symbol. For example, if the object consists of four source symbols that have values a, b, c and d, then the value of the redun- dant symbol is e = a XOR b XOR c XOR d. Then, the packets carrying these symbols look like (0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d), (0, 0: e). In this example, the first two fields are in the header of the packet, where the first field is the symbol ID and the second field is the encoding flag. The portion of the packet after the colon is the payload. Any single symbol of the object can be recovered as the parity of all the other symbols. For example, if packets (0, 1: a), (1, 1: b), (3, 1: d), (0, 0: e) are received then the symbol value for the missing source symbol with ID 2 can be recovered by computing a XOR b XOR d XOR e = c. When the number of source symbols in the object is large, a simple block code variant of the above can be used. In this case, the source symbols are grouped together into source blocks of k Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 4] Internet Draft RMT BB, Forward Error Correction Codes March 2000 consecutive symbols each, and then for each block of source symbols a redundant symbol is added to form encoding blocks of k+1 symbols each. Then, a source block can be recovered from any k of the k+1 symbols from the associated encoding block. Slightly more sophisticated ways of adding redundant symbols using parity can also be used. For example, one can group the k source sym- bols in the object into a p x p square matrix, where p = sqrt(k). Then, for each row a redundant symbol is added that is the parity of all the source symbols in the row. Similarly, for each column a redundant symbol is added that is the parity of all the source sym- bols in the column. Then, Any row of the matrix can be recovered from any p of the p+1 symbols in the row, and similarly for any column. Higher dimensional product codes using this technique can also be used. However, one must be wary of using these constructions without some thought towards the possible loss patterns of symbols. Ideally, the property that one would like to obtain is that if k source symbols are encoded into n encoding symbols (the encoding sym- bols consist of the source symbols and the redundant symbols) then the k source symbols can be recovered from any k of the n encoding symbols. Using the simple constructions described above does not yield codes that come close to obtaining this ideal behavior. 2.2. Small block codes Reliable IP multicast protocols may use a block (n, k) FEC erasure code [BLA94]. For such a code, k source symbols are encoded into n > k encoding symbols, such that any k of the encoding symbols can be used to reassemble the original k source symbols. Thus, these codes have 0% reception overhead when used to encode the entire object directly. Block codes are usually systematic, which means that the n encoding symbols consist of the k source symbols and n-k redundant symbols generated from these k source symbols, where the size of a redundant symbol is the same as that for a source symbol. For exam- ple, the first simple code (XOR) described in the previous subsection is a (k+1, k) code. In general, the freedom to choose n larger than k+1 is desirable, as this can provide much better protection against losses. Codes of this sort are often based on algebraic methods using finite fields. Some of the most popular such codes are based on linear block codes. Implementations of (n, k) FEC erasure codes are efficient enough to be used by personal computers [RIZ97c, NON97]. For example, [Riz97b] describes an implementation where the encoding and decoding speeds decay as C/j, where the constant C is on the order of 10 to 80 Mbytes/second for Pentium class machines of various vintages and j is upper bounded by min(k, n-k). In practice, the values of k and n must be small for these codes as large values make encoding and decoding prohibitively expensive. As Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 5] Internet Draft RMT BB, Forward Error Correction Codes March 2000 many objects are longer than k symbols for reasonable values of k and the symbol length (e.g. larger than 16 KB for k = 16 using 1 KB sym- bols), they are divided into m source blocks consisting of k source symbols each. An erasure code is used to encode each source block into an encoding block consisting of n encoding symbols. For a receiver to completely recover the object, k distinct encoding sym- bols (i.e., with different symbol IDs) must be received for each of the encoding blocks. For some encoding blocks, more than k encoding symbols may be received, in which case any additional encoding sym- bols are discarded. An example encoding structure is shown in Figure 1. | source symbols | source symbols | | of source block 0 | of source block 1 | | | v v +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | encode | v +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ^ ^ | | | encoding symbols | encoding symbols | | of encoding block 0 | of encoding block 1 | Figure 1. Encoding structure for object divided into m = 2 source blocks, k = 8 and n = 10 When using small block codes for objects that are larger than k source symbols in length, the source symbols in the object are assigned to blocks. Typically, each k contiguous source symbols of the object is assigned to a block, i.e., block c consists of the range of source symbols [ck, (c+1)k-1]. This ensures that memory reference are local when the sender reads source symbols to encode, and when the receiver reads encoding symbols to decode.Locality of reference is particularly important when the object is stored on disk, as it reduces the disk seeks required. The block number and the source symbol ID within that block can be used to uniquely specify a source symbol within the object. If the Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 6] Internet Draft RMT BB, Forward Error Correction Codes March 2000 size of the object is not a multiple of k source symbols, then the last source block will contain less than k symbols. Encoding symbols can be uniquely identified by block number and encoding symbol ID. The block numbers can be numbered consecutively starting from zero. One way of identifying encoding symbols within a block are to use symbol IDs and an encoding flag that is used to specify whether an encoding symbol is a source symbol or a redundant symbol, where for example 1 indicates source symbol and 0 indicate redundant symbol. The symbol IDs can be numbered consecutively starting from zero for each block independently for the source sym- bols and for the redundant symbols. Thus, an encoding symbol can be identified by its block number, the encoding flag, and the symbol ID. For example, if the object consists 10 source symbols with values a, b, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are two source blocks consisting of 5 symbols each, and there are two encoding blocks consisting of 8 symbols each. Let p, q and r be the values of the redundant symbols for the first encoding block, and let x, y and z be the values of the redundant symbols for the second encoding block. Then the encoding symbols together with their iden- tifiers are (0, 0, 1:a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 4, 1: e), (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r), (1, 0, 1: f), (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j), (1, 0, 0: x), (1, 1, 0: y) and (1, 2, 0: z). In this example, the first three fields identify the encoding symbol, where the first field is the block number, the second field is the symbol ID and the third field is the encoding flag. The value of the encoding symbol is written after the colon. Each block can be recovered from any 5 of the 8 encoding symbols associated with that block. For example, reception of (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0, 0: p) and (0, 1, 0: q) are sufficient to recover the first source block and reception of (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y) and (1, 2, 0: z) are sufficient to recover the second source block. 2.3. Large block codes Tornado codes [LUB97] are block FEC erasure codes that provide an alternative to small block codes. A (n, k) Tornado code requires slightly more than k out of n encoding symbols to reassemble k source symbols. However, the advantage is that the value of k may be on the order of tens of thousands and still run efficiently. Because of memory considerations, in practice the value of n is restricted to be a small multiple of k, e.g., n = 2k. For example, [BYE98] describes an implementation of Tornado codes where the encoding and decoding speeds are proportional to 10 Mbytes/second to 80 Mbytes/second for Pentium class machines of various vintages when k is in the tens of thousands and n = 2k. The reception overhead for such values of k and n is in the 5-10% range. Tornado codes require a large amount of Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 7] Internet Draft RMT BB, Forward Error Correction Codes March 2000 out of band information to be communicated to all senders and receivers for each different object length, and require an amount of memory on the encoder and decoder which is proportional to the object length times 2n/k. Tornado codes are designed to have low reception overhead on average with respect to reception of a random portion of the encoding pack- ets. Thus, to ensure that a receiver can reassemble the object with low reception overhead, the packets are permuted into a random order before transmission. 2.4. On demand codes All of the FEC erasure codes described up to this point are block codes. There is a different type of FEC erasure code that we call on demand codes. Like block codes, an on demand encoder operates on an object of known size that is partitioned into equal length source symbols. Unlike block codes, there is no predetermined number of encoding symbols that can be generated for on demand codes. Instead, an on demand encoder can generate as few or as many encoding symbols as required on demand. Also unlike block codes, optimal on demand codes have the additional attractive property that encoding symbols for the same object can be generated and transmitted from multiple servers and concurrently received by a receiver and yet the receiver incurs a 0% reception overhead. LT codes are an example of a large on demand FEC code. An LT encoder uses randomization to generate each encoding symbol randomly and independently of all other encoding symbols. An LT encoder satisfies the on demand property, as it can generate as few or as many encoding symbols as required on demand. Let k be the number of source symbols that the object is partitioned into. An LT decoder has the property that with very high probability the receipt of any set of slightly more than k encoding symbols is sufficient to reassemble the object. Like Tornado codes, the value of k may be very large, i.e., on the order of tens or hundreds of thousands, and the encoder and decoder run efficiently in software. For example the encoding and decoding speeds for LT codes are proportional to 3 Mbytes/second to 20 Mbytes/second for Pentium class machines of various vintages when k is in the high tens of thousands. The reception overhead for such values of k is in the 2-4% range. When a new encoding symbol is to be generated, it is based on a key that uniquely describes how the encoding symbol is to be generated. Because encoding symbols are randomly and independently generated, LT codes have the property that encoding symbols for the same object can be generated and transmitted from multiple servers and concurrently received by a receiver with no more reception overhead than if all Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 8] Internet Draft RMT BB, Forward Error Correction Codes March 2000 the encoding symbols were generated by a single sender. There is a tradeoff between the number of source symbols and the reception overhead, and the larger the number of source symbols the smaller the reception overhead. Thus, for shorter objects, it is sometimes advantageous to include multiple symbols in each packet. Normally, and in the discussion below, there is only one symbol per packet. Like small block codes, there is a point when the object is large enough that it makes sense to partition it into blocks when using LT codes. Generally the object is partitioned into blocks whenever the number of source symbols times the packet payload length is less than the size of the object. Thus, if the packet payload is 1024 bytes and the number of source symbols is 64,000 then any object over 64 MB will be partitioned into more than one block. One can choose the number of source symbols to partition the object into, depending on the desired encoding and decoding speed versus reception overhead tradeoff desired. Encoding symbols can be uniquely identified by a block number (when the object is large enough to be partitioned into more than one block) and an encoding symbol ID. The block numbers, if they are used, are generally numbered consecutively starting from zero within the object. The range of possible values for an encoding symbol ID is orders of magnitude larger than the number of source symbols in a block, i.e., on the range of possible values is gen- erally in the billions. The block number and the encoding symbol ID are both chosen uniformly and randomly from their range when an encoding symbol is to be generated and transmitted. For example, suppose the number of source symbols is 64,000 and the number of blocks is 2. Then, each packet generated by the LT encoder could be of the form (b, x: y). In this example, the first two fields iden- tify the encoding symbol, where the first field is the block number b = 0 or 1 and the second field is the randomly chosen encoding symbol ID x. The value y after the colon is the value of the encoding sym- bol. 3. Passing FEC coding information to receivers There are two basic methods for passing FEC coding information to receivers in order to decode an object: within the IP multicast packet headers or through out of band methods. A description of the variety of out of band methods is outside the scope of this document. The FEC coding information can be classified as three types. FEC ses- sion information is information needed by the FEC decoder that may remain fixed for the transmission of many objects. FEC object transmission information is information particular to the object transmission session needed by the FEC decoder. The FEC payload ID identifies the symbols in the payload of the ALC packet. Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 9] Internet Draft RMT BB, Forward Error Correction Codes March 2000 FEC coding information include the FEC codec type, the source block length, the symbol length, the object length, the encoding block number, the encoding symbol ID, and an encoding flag indicating whether the encoding symbol is a source symbol or a redundant symbol. The FEC codec type, the source block length and the symbol length are often FEC session information, although they may classified as FEC object transmission information for some protocols. Thus, sometimes this information is passed to the receiver out of band, although they can equally well be included in each IP multicast packet header as long as the amount of space they take within each packet is minimal. The object length is part of FEC object transmission information. Depending on the protocol, the object length is passed to the receiver out of band or included within each IP multicast packet header. The FEC payload ID consists of the encoding block number (if used), the encoding symbol ID and the encoding flag. The FEC payload ID must be contained within each IP multicast packet header. 4. Security Considerations The use of FEC, in and of itself, imposes no additional security con- siderations versus sending the same information without FEC. How- ever, just like for any transmission system, a malicious sender may intentionally transmit bad symbols. If a receiver accepts one or more bad symbols in place of authentic ones then such a receiver will have its entire object download corrupted by the bad symbol. Application-level transmission object authentication can detect the corrupted transfer, but the receiver must then discard the transferred object. Thus, transmitting false symbols is at least an effective denial of service attack. At worst, a malicious sender could add, delete, or replace arbitrary data within the transmitted object. In light of this possibility, FEC receivers may screen the source address of a received symbol against a list of authentic transmitter addresses. Since source addresses may be spoofed, FEC transport pro- tocols may provide mechanisms for robust source authentication of each encoded symbol. Multicast routers along the path of a FEC transfer may provide the capability of discarding multicast packets that originated on that subnet, and whose source IP address does not correspond with that subnet. 5. Intellectual Property Disclosure Both Tornado codes and LT codes have patents pending. 6. References [AFZ95] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 10] Internet Draft RMT BB, Forward Error Correction Codes March 2000 Based Data Delivery Using Broadcast Disks'', IEEE Personal Communications, pp.50-60, Dec 1995. [BLA94] Blahut, R.E., ``Theory and Practice of Error Control Codes'', Addison Wesley, MA 1984. [BYE98] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A Digital Fountain Approach to Reliable Distribution of Bulk Data'', Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. [DEE88] Deering, S., ``Host Extensions for IP Multicasting'', RFC 1058, Stanford University, Stanford, CA, 1988. [GEM99] Gemmell, J., Schooler, E., and Gray, J., ``ALC Scalable Multicast File Distribution: Caching and Parameters Optimizations'' Technical Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April, 1999. [HAN98] Handley, M., and Jacobson, V., ``SDP: Session Description Protocol'', RFC 2327, April 1998. [HAN96] Handley, M., ``SAP: Session Announcement Protocol'', Internet Draft, IETF MMUSIC Working Group, Nov 1996. [LUB97] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., Stemann, V., ``Practical Loss-Resilient Codes'' 29th STOC'97. [LUB99] Luby, M., Vicisano, L., Speakman, T. ``Heterogeneous multicast congestion control based on router packet filtering'', presented at RMT meeting in Pisa, March 1999. [R2068] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee, T., Hypertext Transfer Protocol HTTP/1.1 (IETF RFC2068) http://www.rfc-editor.org/rfc/rfc2068.txt [R2119] Bradner, S., Key words for use in RFCs to Indicate Requirement Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt [RIZ97a] Rizzo, L, and Vicisano, L., ``Reliable Multicast Data Distribution protocol based on software FEC techniques'', Proceedings of the Fourth IEEES Workshop on the Architecture and Implementation of High Performance Communication Systems, HPCS-97, Chalkidiki, Greece, June 1997. [RIZ97b] Rizzo, L., and Vicisano, L., ``Effective Erasure Codes for Reliable Computer Communication Protocols'', ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997. Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 11] Internet Draft RMT BB, Forward Error Correction Codes March 2000 [RIZ97c] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. [RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact of Multicast Layering on Network Fairness'', Proceedings of ACM SIGCOMM'99. [VIC98A] L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion Control for Layered Multicast Data Transfer'', IEEE Infocom '98, San Francisco, CA, Mar.28-Apr.1 1998. [VIC98B] Vicisano, L., ``Notes On a Cumulative Layered Organization of Data Packets Across Multiple Streams with Different Rates'', University College London Computer Science Research Note RN/98/25, Work in Progress (May 1998). 7. Authors' Addresses Michael Luby luby@dfountain.com Digital Fountain 600 Alabama Street San Francisco, CA, USA, 94110 Lorenzo Vicisano lorenzo@cisco.com cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134 Luigi Rizzo luigi@iet.unipi.it Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy Jim Gemmell jgemmell@microsoft.com Microsoft Research 301 Howard St., #830 San Francisco, CA, USA, 94105 Jon Crowcroft J.Crowcroft@cs.ucl.ac.uk Department of Computer Science University College London Gower Street, London WC1E 6BT, UK Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 12] Internet Draft RMT BB, Forward Error Correction Codes March 2000 Bruce Lueckenhoff brucelu@cadence.com [address here] Luby, Vicisano, Rizzo, Gemmell, Crowcroft, Lueckenhoff [Page 13] --==_Exmh_-17452598970-- From owner-rmt@listserv.lbl.gov Fri Mar 10 17:36: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 RAA19448 for ; Fri, 10 Mar 2000 17:36:27 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id MAA19330; Fri, 10 Mar 2000 12:59:30 -0800 (PST) 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 MAA19326 for ; Fri, 10 Mar 2000 12:59:28 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA13719 for ; Fri, 10 Mar 2000 12:59:27 -0800 (PST) Received: from sj-msg-core-1.cisco.com (sj-msg-core-1.cisco.com [171.71.163.11]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id MAA13716 for ; Fri, 10 Mar 2000 12:59:27 -0800 (PST) Received: from lorenzo-u10.cisco.com (lorenzo-u10.cisco.com [171.69.65.85]) by sj-msg-core-1.cisco.com (8.9.3/8.9.1) with ESMTP id MAA16103; Fri, 10 Mar 2000 12:58:55 -0800 (PST) Received: from localhost (lorenzo@localhost) by lorenzo-u10.cisco.com (8.8.8-Cisco List Logging/CISCO.WS.1.2) with ESMTP id MAA04438; Fri, 10 Mar 2000 12:59:35 -0800 (PST) Message-Id: <200003102059.MAA04438@lorenzo-u10.cisco.com> X-Authentication-Warning: lorenzo-u10.cisco.com: lorenzo owned process doing -bs X-Mailer: exmh version 2.0.2 2/24/98 To: Dah Ming Chiu - Sun Microsystems cc: sob@harvard.edu, vern@aciri.org, mankin@EAST.ISI.EDU, ark008@email.mot.com, rcoltun@siara.com, oran@cisco.com, brian@cs.umass.edu, bcain@nortelnetworks.com, mjh@aciri.org, whetten@talarian.com, Radia.Perlman@east.sun.com, Miriam.Kadansky@east.sun.com, rmt@lbl.gov Subject: Re: PIM-SO and RMT In-reply-to: Your message of "Fri, 10 Mar 2000 15:22:53 EST." <200003102022.PAA00543@bcn.East.Sun.COM> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 10 Mar 2000 12:59:35 -0800 From: Lorenzo Vicisano Sender: owner-rmt@lbl.gov Precedence: bulk Dah, The charter does not state that a "single source" model should be assumed, however it is very likely that the future multicast deployment will be largely based on single source. Moreover, the current heterogeneity of multicast deployment does not allow to assume the presence of multicast feedback (mainly because providers do not allow "normal" customers to source multicast). Nor it does allow to assume the presence of "dense mode" protocols only (and most of the techniques you mentioned only work with dense mode). For the above reasons, in the last meeting (at ACIRI) the group agreed (I think) to assume no multicast back-channel (protocols can still take advantage of it, if present, as an optimization). Note that this does not exactly mean "assume Single Source". I also have two personal remark: - establishing multicast distribution trees is much more expensive than using unicast, hence, I think, we should not abuse this --precious-- resource if possible. - most of the techniques you mentioned do not work well with multicast back-channel, unless you assume the presence of a dense mode protocol (and this is not the case). E.g. expanding ring search is broken (most of the times) in PIM-SM because, it common cases, packets have to reach the RP first. On the other side there are application level algorithms that make *all* these techniques work without multicast back channels. cheers, Lorenzo Vicisano > In the recent RMT Interim meeting in Berkeley, I learned from Brad Cain > that we have to assume the IP multicast infrastructure is PIM-SourceOnly > (or PIM-SO) and IGMPv3. In particular, this means we must assume that > only one host can multicast to a given group. This is confirmed by Mark > Handley and Roger Kermode (see the meeting minutes under "My dream protocol" > for example). > > Later in separate discussions in the TREE BB subgroup, some stated that > the PIM-SO (hence only one host can multicast per multicast address) > is part of the RMT working group charter. > > I am seeking a clear statement regarding this requirement. I don't see > "must assume PIM-SO" are part of the charter. If it is, can it be stated? > Is it mandated as a requirement for the RMT? Can someone succinctly > summarize what is the PIM-SO requirement on RMT, and justify it? > > I am pressing for this because the lack of many-to-many IP multicast > capability means a lot of techniques/algorithms reported in the literature > will not work any more. For example: > - A NACK protocol depends on the NACK be sent via multicast to suppress > redundant NACKs that cause implosion. > - Some tree building protocols use Expanding Ring Search (ERS) to nearby > servers. Although ERS is considered costly in terms of message overheads, > it can still be a useful autoconfiguration technique for many scenarios. > - In a tree-based ACK protocol (TRACK), the repair heads should be able to > share multicast addresses for sending out multicast repairs. This would > not be possible if only one host can send on a multicast address. > > I understand that in the current public Internet, limiting multicast to a > single sender fits certain business models of ISPs who can charge for > multicast. But this constraint is not needed in many intranet environments. > > I understand many people support the Simple Multicast model, under which > there is no single-source constraint. Is that proposal still being studied > by IETF? Also, what is happening to the BGMP model that allows dense mode > multicast in administrative domains? Is the PIM-SO requirement premature? > > Dah Ming Chiu > Sun Labs > > From owner-rmt@listserv.lbl.gov Fri Mar 10 21:07: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 VAA25243 for ; Fri, 10 Mar 2000 21:07:34 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id RAA21038; Fri, 10 Mar 2000 17:37:31 -0800 (PST) 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 RAA21034 for ; Fri, 10 Mar 2000 17:37:30 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA01804 for ; Fri, 10 Mar 2000 17:37:28 -0800 (PST) Received: from virtualworkshop.com (IDENT:root@dino.virtualworkshop.com [208.14.33.1]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id RAA01801 for ; Fri, 10 Mar 2000 17:37:27 -0800 (PST) Received: from virtualworkshop.com (barney.virtualworkshop.com [208.14.33.4]) by virtualworkshop.com (8.9.1/8.8.7) with ESMTP id UAA16595; Fri, 10 Mar 2000 20:33:06 -0500 Message-ID: <38C9A253.D6D46902@virtualworkshop.com> Date: Fri, 10 Mar 2000 20:33:07 -0500 From: "Michael D. Myjak" Reply-To: mmyjak@virtualworkshop.com Organization: The Virtual Workshop, Inc. X-Mailer: Mozilla 4.7 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 To: Lorenzo Vicisano CC: Dah Ming Chiu - Sun Microsystems , sob@harvard.edu, vern@aciri.org, mankin@EAST.ISI.EDU, ark008@email.mot.com, rcoltun@siara.com, oran@cisco.com, brian@cs.umass.edu, bcain@nortelnetworks.com, mjh@aciri.org, whetten@talarian.com, Radia.Perlman@east.sun.com, Miriam.Kadansky@east.sun.com, rmt@lbl.gov Subject: Re: PIM-SO and RMT References: <200003102059.MAA04438@lorenzo-u10.cisco.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit Lorenzo Vicisano wrote: > Dah, > > The charter does not state that a "single source" model should > be assumed, however it is very likely that the future multicast > deployment will be largely based on single source. I take issue with this statement; Its about as far-sighted as next week. How can you possibly say, with any assurance or credibility, that future multicast deployment will largely be based on single sources?? Are you not familiar with any of the on-going work in NASA's Integrated Synthetic Environments? DoEs Shared Collaboratories? or DoEd's Advanced Distributed Learning? Certainly to date, the predominate model has been point-to-multipoint. But this statement is as reassuring as "Certainly... 32-bits is more than enough address space." Oh Please... -- All the best - _ ___|0|_|___ Michael D. Myjak, Vice President R&D and CTO | N & W | The Virtual Workshop, Inc. = oo---oo = P.O. Box 98 Titusville Fl 32781 email: voice&fax: 321.264.0440 From owner-rmt@listserv.lbl.gov Fri Mar 10 21:37: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 VAA05211 for ; Fri, 10 Mar 2000 21:37:07 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id SAA21158; Fri, 10 Mar 2000 18:09:19 -0800 (PST) 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 SAA21154 for ; Fri, 10 Mar 2000 18:09:18 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id SAA05648 for ; Fri, 10 Mar 2000 18:09:17 -0800 (PST) Received: from kickme.cisco.com (kickme.cisco.com [198.92.30.42]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id SAA05642 for ; Fri, 10 Mar 2000 18:09:16 -0800 (PST) Received: from lorenzo-u10.cisco.com (lorenzo-u10.cisco.com [171.69.65.85]) by kickme.cisco.com (8.9.1a/8.9.1) with ESMTP id RAA20398; Fri, 10 Mar 2000 17:56:58 -0800 (PST) Received: from localhost (lorenzo@localhost) by lorenzo-u10.cisco.com (8.8.8-Cisco List Logging/CISCO.WS.1.2) with ESMTP id SAA05057; Fri, 10 Mar 2000 18:09:24 -0800 (PST) Message-Id: <200003110209.SAA05057@lorenzo-u10.cisco.com> X-Authentication-Warning: lorenzo-u10.cisco.com: lorenzo owned process doing -bs X-Mailer: exmh version 2.0.2 2/24/98 To: mmyjak@virtualworkshop.com cc: Dah Ming Chiu - Sun Microsystems , sob@harvard.edu, vern@aciri.org, mankin@EAST.ISI.EDU, ark008@email.mot.com, rcoltun@siara.com, oran@cisco.com, brian@cs.umass.edu, bcain@nortelnetworks.com, mjh@aciri.org, whetten@talarian.com, Radia.Perlman@east.sun.com, Miriam.Kadansky@east.sun.com, rmt@lbl.gov Subject: Re: PIM-SO and RMT In-reply-to: Your message of "Fri, 10 Mar 2000 20:33:07 EST." <38C9A253.D6D46902@virtualworkshop.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Fri, 10 Mar 2000 18:09:24 -0800 From: Lorenzo Vicisano Sender: owner-rmt@lbl.gov Precedence: bulk > > The charter does not state that a "single source" model should > > be assumed, however it is very likely that the future multicast > > deployment will be largely based on single source. > > I take issue with this statement; Its about as far-sighted as next week. How > can > you possibly say, with any assurance or credibility, that future multicast > deployment will largely be based on single sources?? Are you not familiar wit >h any > of the on-going work in NASA's Integrated Synthetic Environments? DoEs Shared > Collaboratories? or DoEd's Advanced Distributed Learning? Michael, the context of my statement was in the RMT framework, which is bulk-data transfer for IP multicast (as currently specified). Moreover there was more in my email beside the statement that you are quoting... I agree with you that interactive applications work much better with a symmetric Multicast service and that this is probably the main the reason why we should keep working on its deployment. However this is out of the scope of RMT (please check the WG charter). Lorenzo Vicisano > > Certainly to date, the predominate model has been point-to-multipoint. But t >his > statement is as reassuring as "Certainly... 32-bits is more than enough addre >ss > space." Oh Please... > > > -- > All the best - > _ > ___|0|_|___ Michael D. Myjak, Vice President R&D and CTO > | N & W | The Virtual Workshop, Inc. > = oo---oo = P.O. Box 98 Titusville Fl 32781 > email: voice&fax: 321.264.0440 > > > From owner-rmt@listserv.lbl.gov Fri Mar 10 22:41:41 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 WAA27375 for ; Fri, 10 Mar 2000 22:41:40 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id TAA21297; Fri, 10 Mar 2000 19:04:32 -0800 (PST) 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 TAA21293 for ; Fri, 10 Mar 2000 19:04:30 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id TAA10266 for ; Fri, 10 Mar 2000 19:04:29 -0800 (PST) Received: from virtualworkshop.com (IDENT:root@dino.virtualworkshop.com [208.14.33.1]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id TAA10258 for ; Fri, 10 Mar 2000 19:04:28 -0800 (PST) Received: from virtualworkshop.com (barney.virtualworkshop.com [208.14.33.4]) by virtualworkshop.com (8.9.1/8.8.7) with ESMTP id WAA16747; Fri, 10 Mar 2000 22:04:24 -0500 Message-ID: <38C9B7B9.4DD89566@virtualworkshop.com> Date: Fri, 10 Mar 2000 22:04:25 -0500 From: "Michael D. Myjak" Reply-To: mmyjak@virtualworkshop.com Organization: The Virtual Workshop, Inc. X-Mailer: Mozilla 4.7 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 To: Lorenzo Vicisano CC: RMT Subject: Re: PIM-SO and RMT References: <200003110209.SAA05057@lorenzo-u10.cisco.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit Lorenzo, I read what you wrote... I'm just trying to earmark what's on the horizon. And I do understand that the RMT charter is highly focused toward a narrow-cast solution space. Be that as it may, the issue in my mind irrespective of that, is that that the prevailing mind set in this arena seems to be just as you stated - it prefers a closed, unidirectional, asymmetrical point-to-multipoint communications path which has little to no regard for application(s) performance (i.e., real-time). (In fact, the preferred application may be little more than a file or web site mirror.) Further, applications which are sufficiently "different" or fall outside of this groups perceived "mainstream" scope may yet evolve and attempt to utilize the approach developed here, whether we perceive it as applicable or not. (Ex. Distributed Interactive Simulation [IEEE-1278] used subnet broadcasting to accomplish what it could not using IP Multicast. Clearly, subnet broadcasting was never designed with such a (multipoint-to-multipoint) application in mind.) In short, all I'm trying to say is that we cannot assume that this (or any) specific application will be the only one(s) to use RMT. -- All the best - _ ___|0|_|___ Michael D. Myjak, Vice President R&D and CTO | N & W | The Virtual Workshop, Inc. = oo---oo = P.O. Box 98 Titusville Fl 32781 email: voice&fax: 321.264.0440 Lorenzo Vicisano wrote: > > > The charter does not state that a "single source" model should > > > be assumed, however it is very likely that the future multicast > > > deployment will be largely based on single source. > > > > I take issue with this statement; Its about as far-sighted as next week. How > > can > > you possibly say, with any assurance or credibility, that future multicast > > deployment will largely be based on single sources?? Are you not familiar wit > >h any > > of the on-going work in NASA's Integrated Synthetic Environments? DoEs Shared > > Collaboratories? or DoEd's Advanced Distributed Learning? > > Michael, > > the context of my statement was in the RMT framework, which is > bulk-data transfer for IP multicast (as currently specified). > Moreover there was more in my email beside the statement that > you are quoting... > > I agree with you that interactive applications work much better > with a symmetric Multicast service and that this is probably the > main the reason why we should keep working on its deployment. However > this is out of the scope of RMT (please check the WG charter). > > Lorenzo Vicisano > > > > > Certainly to date, the predominate model has been point-to-multipoint. But t > >his > > statement is as reassuring as "Certainly... 32-bits is more than enough addre > >ss > > space." Oh Please... > > > > > > -- > > All the best - > > _ > > ___|0|_|___ Michael D. Myjak, Vice President R&D and CTO > > | N & W | The Virtual Workshop, Inc. > > = oo---oo = P.O. Box 98 Titusville Fl 32781 > > email: voice&fax: 321.264.0440 > > > > > > From owner-rmt@listserv.lbl.gov Mon Mar 13 03:04:39 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 DAA07188 for ; Mon, 13 Mar 2000 03:04:38 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id XAA03052; Sun, 12 Mar 2000 23:21:14 -0800 (PST) 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 XAA03048 for ; Sun, 12 Mar 2000 23:21:12 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id XAA21669 for ; Sun, 12 Mar 2000 23:21:10 -0800 (PST) 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 XAA21665 for ; Sun, 12 Mar 2000 23:21:10 -0800 (PST) Received: from tahoe (talarian32-66.talarian.com [207.5.32.66]) by phobos.talarian.com (8.9.0/8.9.0) with SMTP id XAA26353; Sun, 12 Mar 2000 23:17:53 -0800 (PST) Message-Id: <4.1.20000312131129.0a957aa0@mailhost.talarian.com> X-Sender: bwhetten@mailhost.talarian.com X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1 Date: Sun, 12 Mar 2000 15:51:34 -0800 To: mmyjak@virtualworkshop.com, Lorenzo Vicisano From: Brian Whetten Subject: Re: PIM-SO and RMT Cc: Dah Ming Chiu - Sun Microsystems , sob@harvard.edu, vern@aciri.org, mankin@EAST.ISI.EDU, ark008@email.mot.com, rcoltun@siara.com, oran@cisco.com, brian@cs.umass.edu, bcain@nortelnetworks.com, mjh@aciri.org, Radia.Perlman@east.sun.com, Miriam.Kadansky@east.sun.com, rmt@lbl.gov In-Reply-To: <38C9A253.D6D46902@virtualworkshop.com> References: <200003102059.MAA04438@lorenzo-u10.cisco.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-rmt@lbl.gov Precedence: bulk >I take issue with this statement; Its about as far-sighted as next week. >How can >you possibly say, with any assurance or credibility, that future multicast >deployment will largely be based on single sources?? Are you not familiar >with any >of the on-going work in NASA's Integrated Synthetic Environments? DoEs Shared >Collaboratories? or DoEd's Advanced Distributed Learning? > >Certainly to date, the predominate model has been point-to-multipoint. But >this >statement is as reassuring as "Certainly... 32-bits is more than enough address >space." Oh Please... Mike, Even if a significant piece of multicast deployment eventually support many-many, there will still be a big piece that does NOT. We have to design to the least common denominator. As a side note, we'd all love to see many-many worldwide multicast, but I think there is growing consensus that it is extremely difficult to justify it economically. The costs are too high (the inter-domain issue is just too much) and the benefits too low (there are much easier way to implement many-many apps on top of 1-many multicast...Talarian has customers deployed with 10K client many-many environments). This does NOT mean that there are no compelling, scaleable many-many apps...just that we don't necessarily need to support them with true many-many multicast. Brian From owner-rmt@listserv.lbl.gov Mon Mar 13 04:41:10 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 EAA12171 for ; Mon, 13 Mar 2000 04:41:10 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id BAA03223; Mon, 13 Mar 2000 01:02:03 -0800 (PST) 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 BAA03219 for ; Mon, 13 Mar 2000 01:02:01 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id BAA26984 for ; Mon, 13 Mar 2000 01:01:57 -0800 (PST) Received: from bells.cs.ucl.ac.uk (bells.cs.ucl.ac.uk [128.16.5.31]) by SpamWall.lbl.gov (8.9.3/8.9.3) with SMTP id BAA26981 for ; Mon, 13 Mar 2000 01:01:56 -0800 (PST) Received: from sonic.cs.ucl.ac.uk by bells.cs.ucl.ac.uk with local SMTP id ; Mon, 13 Mar 2000 08:57:11 +0000 To: Brian Whetten cc: mmyjak@virtualworkshop.com, Lorenzo Vicisano , Dah Ming Chiu - Sun Microsystems , sob@harvard.edu, vern@aciri.org, mankin@EAST.ISI.EDU, ark008@email.mot.com, rcoltun@siara.com, oran@cisco.com, brian@cs.umass.edu, bcain@nortelnetworks.com, mjh@aciri.org, Radia.Perlman@east.sun.com, Miriam.Kadansky@east.sun.com, rmt@lbl.gov Subject: Re: PIM-SO and RMT In-reply-to: Your message of "Sun, 12 Mar 2000 15:51:34 PST." <4.1.20000312131129.0a957aa0@mailhost.talarian.com> Date: Mon, 13 Mar 2000 08:57:09 +0000 Message-ID: <2208.952937829@cs.ucl.ac.uk> From: Jon Crowcroft Sender: owner-rmt@lbl.gov Precedence: bulk >>environments). This does NOT mean that there are no compelling, scaleable >>many-many apps...just that we don't necessarily need to support them with >>true many-many multicast. Brian yes... i think another argument can show that we have a deployment credibility problem with the internet standard multicast service model ....we're already having a lot of ISPs clamp down on source addresses for unicast traffic so that they can rapidly respond to Denial of Service attacks - whatever the pro many=-to=many multicast people say (and i am one of them, believe me), its at least n-fold harder to audit n sources than 1... in fact ,there is going to be at least a BOF in adelaide on this topic - i wonder if any multicast considerations are going to be represented there? cheers jon From owner-rmt@listserv.lbl.gov Mon Mar 13 07:02:20 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 HAA29393 for ; Mon, 13 Mar 2000 07:02:17 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id DAA03412; Mon, 13 Mar 2000 03:19:29 -0800 (PST) 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 DAA03408 for ; Mon, 13 Mar 2000 03:19:27 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA04064 for ; Mon, 13 Mar 2000 03:19:26 -0800 (PST) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA04061 for ; Mon, 13 Mar 2000 03:19:25 -0800 (PST) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA15271; Mon, 13 Mar 2000 06:19:22 -0500 (EST) Message-Id: <200003131119.GAA15271@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-pi-alc-00.txt Date: Mon, 13 Mar 2000 06:19:21 -0500 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 : Asynchronous Layered Coding A scalable reliable multicast protocol Author(s) : M. Luby, L. Vicisano et.al Filename : draft-ietf-rmt-pi-alc-00.txt Pages : 28 Date : 10-Mar-00 This document describes Asynchronous Layered Coding, a scalable reli- able multicast protocol, hereafter referred to as ALC. ALC can be used to reliably transmit objects to multiple receivers. An object can be any well-defined piece of data. Examples include any type of file such as a group of pictures in an MPEG stream, a MP3 music file, a JPEG image, and a collection of files that are zipped into one file. In addition, the ALC delivery model is fairly flexible, e.g., on demand or a push delivery. When using ALC, the payload of the packets that flow from senders to receivers in no way depend on net- work conditions or the reaction of receivers to these conditions, although the rate of flow of the packets in various parts of the net- work does depend on network conditions. Receivers may join or leave an existing packet stream in an asynchronous manner independent of other receivers. Congestion control is achieved by sending several packet streams ordered in a layered fashion and delivering only a subset of these to individual receivers. The number of streams received is dictated by the local bandwidth availability and network conditions. A possible way to achieve this is by using a distinct multicast address for each stream. Receivers join the lowest layer stream they are not currently joined to at coordinated points in time when there is more available bandwidth between those receivers and the sender. Similarly, receivers leave one or more highest layer streams they are currently joined to as soon as they feel congestion (typically as evidenced by packet loss). Another possibility to achieve this form of congestion control is through router-assisted schemes. Reliability is achieved via FEC coding only, i.e. there is no request for feedback for retransmission from receivers that miss packets for whatever reason. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-pi-alc-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-pi-alc-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-pi-alc-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: <20000310135058.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-pi-alc-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-pi-alc-00.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000310135058.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Mon Mar 13 07:06:34 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 HAA00958 for ; Mon, 13 Mar 2000 07:06:33 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id DAA03418; Mon, 13 Mar 2000 03:19:35 -0800 (PST) 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 DAA03414 for ; Mon, 13 Mar 2000 03:19:33 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA04080 for ; Mon, 13 Mar 2000 03:19:32 -0800 (PST) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA04076 for ; Mon, 13 Mar 2000 03:19:31 -0800 (PST) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA15339; Mon, 13 Mar 2000 06:19:28 -0500 (EST) Message-Id: <200003131119.GAA15339@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-bb-fec-00.txt Date: Mon, 13 Mar 2000 06:19:28 -0500 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 : Reliable Multicast Transport Building Block: Forward Error Correction Codes Author(s) : M. Luby, L. Vicisano et.al Filename : draft-ietf-rmt-bb-fec-00.txt Pages : 14 Date : 10-Mar-00 This memo describes the use of Forward Error Correction (FEC) codes within the context of reliable IP multicast transport and provides an introduction to some commonly-used FEC codes. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-bb-fec-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-bb-fec-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-bb-fec-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: <20000310135108.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-bb-fec-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-bb-fec-00.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000310135108.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Wed Mar 15 07:34: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 HAA25930 for ; Wed, 15 Mar 2000 07:34:16 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id DAA13025; Wed, 15 Mar 2000 03:25:32 -0800 (PST) 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 DAA13021 for ; Wed, 15 Mar 2000 03:25:29 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA27008 for ; Wed, 15 Mar 2000 03:25:29 -0800 (PST) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id DAA27000 for ; Wed, 15 Mar 2000 03:25:26 -0800 (PST) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA29694; Wed, 15 Mar 2000 06:25:25 -0500 (EST) Message-Id: <200003151125.GAA29694@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-gra-arch-01.txt Date: Wed, 15 Mar 2000 06:25:24 -0500 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 : Generic Router Assist (GRA) Building Block Motivation and Architecture Author(s) : B. Cain, T. Speakman, D. Towsley Filename : draft-ietf-rmt-gra-arch-01.txt Pages : 21 Date : 14-Mar-00 Generic Router Assist (GRA) is a network-based service that enables end-to-end multicast transport protocols to take advantage of infor- mation distributed across the network elements in a given multicast distribution tree. The service consists of a canonical set of simple functions which network elements may apply to selected packets in the transport session as they traverse the distribution tree. The choice of function and the packet parameters to which it is applied can be defined and customized for a given transport session in a highly con- trolled fashion that still permits enough flexibility for GRA to be used to address a wide range of multicast transport problems not amenable to end-to-end solution. This document provides the motiva- tion and an architecture for GRA. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-gra-arch-01.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-gra-arch-01.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-gra-arch-01.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: <20000314133149.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-gra-arch-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-gra-arch-01.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000314133149.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Thu Mar 16 17:07:00 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 RAA10828 for ; Thu, 16 Mar 2000 17:06:59 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id NAA24743; Thu, 16 Mar 2000 13:21:15 -0800 (PST) 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 NAA24739 for ; Thu, 16 Mar 2000 13:21:13 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id NAA08503 for ; Thu, 16 Mar 2000 13:21:13 -0800 (PST) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id NAA08496 for ; Thu, 16 Mar 2000 13:21:12 -0800 (PST) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA24145; Thu, 16 Mar 2000 16:21:08 -0500 (EST) Message-Id: <200003162121.QAA24145@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-design-space-01.txt Date: Thu, 16 Mar 2000 16:21:08 -0500 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 : The Reliable Multicast Design Space for Bulk Data Transfer Author(s) : M. Handley, S. Floyd, B. Whetten, R. Kermode, L. Vicisano Filename : draft-ietf-rmt-design-space-01.txt Pages : 21 Date : 15-Mar-00 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. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-design-space-01.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-design-space-01.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-design-space-01.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: <20000315133011.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-design-space-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-design-space-01.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000315133011.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Thu Mar 16 17:08:34 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 RAA11487 for ; Thu, 16 Mar 2000 17:08:33 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id NAA24737; Thu, 16 Mar 2000 13:21:10 -0800 (PST) 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 NAA24733 for ; Thu, 16 Mar 2000 13:21:08 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id NAA08479 for ; Thu, 16 Mar 2000 13:21:07 -0800 (PST) Received: from ietf.org (odin.ietf.org [132.151.1.176]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id NAA08472 for ; Thu, 16 Mar 2000 13:21:06 -0800 (PST) Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA24101; Thu, 16 Mar 2000 16:21:02 -0500 (EST) Message-Id: <200003162121.QAA24101@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-buildingblocks-02.txt Date: Thu, 16 Mar 2000 16:21:01 -0500 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 : Reliable Multicast Transport Building Blocks for One-to-Many Bulk-Data Transfer Author(s) : B. Whetten, M. Handley, S. Floyd, R. Kermode, L. Vicisano, M. Luby Filename : draft-ietf-rmt-buildingblocks-02.txt Pages : 21 Date : 15-Mar-00 This document describes a framework for the standardization of bulk-data reliable multicast transport. It builds upon the experience gained during the deployment of several classes of contemporary reliable multicast transport, and attempts to pull out the commonalities between these classes of protocols into a number of building blocks. To that end, this document recommends that certain components that are common to multiple protocol classes be standardized as 'building blocks.' The remaining parts of the protocols, consisting of highly protocol specific, tightly intertwined functions, shall be designated as 'protocol cores.' Thus, each protocol can then be constructed by merging a 'protocol core' with a number of 'building blocks' which can be re-used across multiple protocols. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-rmt-buildingblocks-02.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-buildingblocks-02.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-buildingblocks-02.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: <20000315132959.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-rmt-buildingblocks-02.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-rmt-buildingblocks-02.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <20000315132959.I-D@ietf.org> --OtherAccess-- --NextPart-- From owner-rmt@listserv.lbl.gov Fri Mar 17 17:07: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 RAA25599 for ; Fri, 17 Mar 2000 17:07:43 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id NAA29378; Fri, 17 Mar 2000 13:17:24 -0800 (PST) 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 NAA29374 for ; Fri, 17 Mar 2000 13:17:22 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id NAA19329 for ; Fri, 17 Mar 2000 13:17:21 -0800 (PST) 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 NAA19322 for ; Fri, 17 Mar 2000 13:17:20 -0800 (PST) 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 QAA23979 for ; Fri, 17 Mar 2000 16:17:17 -0500 (EST) Mime-Version: 1.0 X-Sender: adamson@pop.itd.nrl.navy.mil Message-Id: Date: Fri, 17 Mar 2000 16:17:15 -0500 To: RMT From: Brian Adamson Subject: Initial draft of NACK-Oriented Reliable Multicast Building Blocks Content-Type: multipart/mixed; boundary="============_-1258794657==_============" Sender: owner-rmt@lbl.gov Precedence: bulk --============_-1258794657==_============ Content-Type: text/plain; charset="us-ascii" ; format="flowed" RMT: We go bounced on the draft submission deadline, but since we will probably provide an update on it in Adeleide, attached is an initial cut at a Building Blocks document for NACK-oriented Reliable Multicast. best regards, --============_-1258794657==_============ Content-Id: Content-Type: text/plain; name="draft-ietf-rmt-norm-bb-00.txt"; charset="us-ascii" ; format="flowed" Content-Disposition: attachment; filename="draft-ietf-rmt-norm-bb-00.txt" ; modification-date="Fri, 17 Mar 2000 14:40:08 -0500" RMT Working Group B. Adamson INTERNET-DRAFT C. Borman draft-ietf-rmt-norm-bb-00.txt S. Floyd Expires: Jul 2000 M. Handley J. Macker 15 March 2000 NACK-Oriented Reliable Multicast (NORM) Protocol Building Blocks Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other docu- ments at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved. Abstract This memo describes issues related to the creation of NACK-oriented reliable multicast protocols (NORM). The general goals and assump- tions for NORM are defined. Some issues related to NACK-oriented (and in some cases general) reliable multicast protocol design are identified. These issues are resolved into a number of "building block" components which are described in further detail. It is anticipated that these building block components (as they are fur- ther refined and defined in future revisions of this document) will be useful in generating different instantiations of NACK-oriented reliable multicast protocols. Adamson, Borman, et al. Expires September 2000 [Page 1] Internet Draft NORM Building Blocks March 2000 1.0 Background Reliable multicast transport is a desirable technology for the efficient and reliable distribution of data to a group on the Internet. The complexity of group communication paradigms necessi- tates the creation of different protocol types and instantiations to meet the range of performance and scalability requirements of different potential reliable multicast applications and users [Mankin98]. Properly designed negative acknowledgement (NACK) based reliable multicast protocols offer scalability advantages for applications and/or network topologies where, for various reasons, it is prohibitive to construct a higher order delivery infrastruc- ture above the basic Layer 3 IP multicast service (e.g. unicast or hybrid unicast/multicast data distribution trees). Additionally, the scalability property of NACK-oriented protocols [Pingali93, Levine96] may be applicable where broad "fanout" is expected for a single network hop (e.g. cable-TV data delivery, satellite, or other broadcast communication communication services). Further- more, the simplicity of a protocol based on "flat" group-wide mul- ticast distribution may offer advantages for a broad range of dis- tributed services or dynamic networks and applications. While different protocol instantiations may be required to meet specific application and network architecture demands [Clark90], there are a number of fundamental components which may be common to these different instantiations. This document describes the frame- work and common "building block" components relevant to multicast protocols based primarily on NACK operation for reliable transport. 2.0 Goals and Assumptions Each potential protocol instantiation derived from the building blocks presented here (and other applicable building block docu- ments) will have specific criteria which will influence individual protocol design. To support the development of applicable building blocks, it is useful to define the categories of these driving pro- tocol design goals and assumptions. Some general categories which are likely to impact protocol instantiation design are described in the sections below. These are areas which each protocol instantia- tion will need to address. 2.1 Data content model The implicit goal of a reliable multicast protocol is the reliable delivery of "data" among a group of participants communicating through IP multicast datagram service. However, the nature of the data content and the service the application is attempting to pro- vide can impact design decisions. The service model may range from Adamson, Borman, et al. Expires September 2000 [Page 2] Internet Draft NORM Building Blocks March 2000 long-lived transfer sessions of bulk quantities of data (file broadcast) to more interactive exhanges of small messages (e.g. white-boarding, text chat). And within those different models there are other issues such as the sender's ability to cache trans- mitted data (or state referencing it) for retransmission or repair. The need for ordering and/or causality in the sequence of transmis- sions/receptions among participants in the group can be a function of the data content. The group communication paradigm differs sig- nificantly from the point-to-point model in that, depending upon the data content type, some receivers may complete reception of a portion of data content and be able to act upon it before other participants have received the content. This may be acceptable (or even desirable) for some applications but not for others. These varying requirements drives the need for a number of different pro- tocol instantiation designs. A significant challenge in developing generally useful building block mechanisms is accommodating even a limited range of these capabilities without defining specific application-level details. Note that this particular building block "guideline" may be gener- ally applicable beyond the realm of NACK-oriented reliable multi- cast. 2.2) Group membership dynamics Group communication can differ from point-to-point communications with respect to the fact that even if the composition of the group changes, the "thread" of communication can still exist. This con- trasts with the point-to-point communication model where, if either of the two parties leave, the communication process (exchange of data) is terminated (or at least paused). Depending upon applica- tion goals, senders and receivers participating in a reliable mul- ticast transport "session" may be able to join late, leave, and/or potentially rejoin while the ongoing group communication "thread" still remains functional and useful. Also note that this can impact protocol message content. If "late joiners" are supported, some amount of additional information may be placed in message headers to accommodate this functionality. Alternatively, the information may be sent in its own message (on demand or intermittently) if the impact to the overhead of typical message transmissions is deemed too great. Group dynamics can also impact other protocol mechanisms such as NACK or other timing, con- gestion control operation, etc. 2.3) Sender/receiver relationships The relationship of senders and receivers among group participants Adamson, Borman, et al. Expires September 2000 [Page 3] Internet Draft NORM Building Blocks March 2000 requires consideration. In some applications, there may be a sin- gle sender multicasting to a group of receivers. In other cases, there may be more than one sender or the potential for everyone in the group to be a sender _and_ receiver of data may exist. 2.4) Group size Native IP multicast [Deering89] may scale to extremely large group sizes. It may be desirable for some applications to be able to scale along with the multicast infrastructure's ability to scale. In its simplest form, there are limits to the group size to which a NACK-oriented protocol can apply without NACK implosion problems, but with the potential for router assistance or other non-linear NACK suppression mechanisms, these protocols may scale to very large group sizes. In large scale cases, it may be prohibitive for participants to maintain state on all other participants (in par- ticular, other receivers) in the group. The impact of group size needs to be considered in the development of generally applicable building blocks. 2.5) Data delivery performance There is a trade-off between scalability and data delivery latency when designing NACK-oriented protocols. If NACK suppression is to be used, there will be some delays built into the NACK generation and repair transmission process to allow suppression to occur and for the sender of data to identify appropriate content for effi- cient repair transmission. For example, backoff timeouts can be used to ensure efficient NACK suppression and repair transmission, but this comes at a cost of increased delivery latency and increased buffering requirements for both senders and receivers. The building blocks should allow applications to establish bounds for data delivery performance. Note that application designers must be aware of the scalabilty trade-off which is made when such bounds are applied. 2.6) Network topology The Internet Protocol has historically assumed a role of providing service across heterogeneous network topologies. It is desirable that a reliable multicast protocol be capable of effectively oper- ating across a wide range of the networks to which general purpose IP service applies. Recently, a number of asymmetric network ser- vices including 56K/ADSL modems, CATV Internet service, satellite and other wireless communication services have begun to prolifer- ate. Many of these are inherently broadcast media with potentially large "fanouts" to which IP multicast service is highly applicable. Adamson, Borman, et al. Expires September 2000 [Page 4] Internet Draft NORM Building Blocks March 2000 Additionally, policy and/or technical issues may result in topolo- gies where multicast connectivity is limited to a single logical direction from a specific source or set of sources to the group at large. Receivers in the group may be restricted to unicast feed- back for NACKs and other messages. Consideration must be given, in building block development and protocol design, to the nature of the underlying networks over which the protocols may be operating. 2.7) Router/Intermediate System Assistance While intermediate assistance from devices/systems with direct knowledge of the underlying network topology may used to leverage the performance and scalability of reliable multicast protocols, there will continue to be a number of instances where this is not available or practical. Any building block components for NACK- oriented reliable multicast should be capable of operating without such assistance but should also be capable of utilizing these fea- tures when available. 3.0 Building Block Areas (Aside: OK. We've presented in general what building blocks are intended to be and some of the critera which may affect building block identification/ design. So now let's list possible building blocks. Some of these may be unique to NACK-oriented protocols while some may be more generally applicable) This section describes different building block areas applicable to NACK-oriented reliable multicast protocols. Some of these areas are specific to NACK-oriented protocols. Detailed descriptions of such areas are provided below. In other cases, the areas (e.g. node identifiers, FEC, etc) may be generally applicable to other forms of reliable multicast. In those cases, the discussion below describes requirements placed on those other general building block areas from the standpoint of NACK-oriented reliable multicast. For the individual building blocks to be incorporated as part of a specific protocol instantiation, it expected that a description of some notional "interface" to the building blocks' functionality be provided. For example, a building block component may require some form of "input" from another building block component or other source in order to perform its function. Any "inputs" required by each building block component and/or any resultant "output" pro- vided by the building block will be defined and described as the building block component's interface definition. The following building block areas are described below: Adamson, Borman, et al. Expires September 2000 [Page 5] Internet Draft NORM Building Blocks March 2000 (NACK-Oriented Components) 1) Sender transmission 2) NACK-oriented Repair Process 3) "Late-joining" Receiver Policies and Mechanisms (Generally-applicable Conponents) 4) Participant Identification 5) Data Content Identification 6) Forward Error Correction 7) Round-trip Timing Collection 8) Group Size Determination/Estimation 9) Congestion Control Operation 10) Router/Intermediate System Assistance 11) Additional Protocol Mechanisms 3.1 Sender transmission Senders will transmit data content to the multicast session. The data content will be application dependent. The sender will trans- mit data content at a rate and with packet sizes determined by application and/or network architecture requirements. When conges- tion control mechanisms are used (recommended), the transmission rate will be controlled by the congestion control mechanism. It is recommended that all data transmissions from senders be subject to rate limitations determined by the application or congestion con- trol algorithm. The sender's transmissions should make good utl- ization of the available capacity (either application or congestion control specified). As a result, it is expected there will be overlap and multiplexing of new data content transmission with repair content. Other sender messages or commands may be employed as part of proto- col operation. For NACK-oriented operation, the reliability of any such commands may depend upon redundant transmission. Other fac- tors related to NACK-oriented operation may determine sender trans- mission formats and methods. Some consideration may need to be given to the sender's behavior during intermittent idle periods when it has no data to transmit. While many aspects may be proto- col-specific, there are techniques which may be generally applica- ble to NACK-oriented reliable multicast. For example, the period- icity of redundant transmission of command messages issued by a sender should be dependent upon the greatest round trip timing estimate and the resultant NACK operation. More specifically, a command message might be redundantly transmitted by a sender to indicate that it is temporarily (or permanently) halting transmis- sion. At this time, it may be appropriate for receivers to respond with NACKs for any outstanding repairs they require following the rules of the NACK process described below. For efficiency, the Adamson, Borman, et al. Expires September 2000 [Page 6] Internet Draft NORM Building Blocks March 2000 sender whould allow sufficient time between redundant transmissions to receive any NACK-oriented responses from the receiver set to this command. Other protocol components may benefit from a similar approach. Inputs: 1) Data content 2) Segmentation size 3) Transmission rate Outputs: 1) Rate-controlled stream of packets with headers uniquely identifying data or repair content within the context of the reliable multicast session. 3.2 NACK-oriented repair process The most critical component of the NACK-oriented reliable multicast protocol building block is the NACK repair process. There are four primary elements of a general NACK repair process: 1) Method for determining when receivers will initiate the NACK process in response to sender transmission for which they need repair. 2) NACK message content. 3) NACK suppression mechanisms to promote scalability of the protocol. 4) Sender NACK reception, aggregation, and repair response. 3.2.1 NACK Process Initiation The NACK process (cycle) will be initiated by receivers who detect they require repair transmissions from a specific sender at defined opportunities. When FEC is applied, a NACK cycle should only be initiated when it is known by the receiver that its repair require- ments exceed the amount of FEC pending transmission for a given coding block of packets. This may be determined by the receiver if the sender's transmission advertises the quantity of repair packets it is already planning to send for a block, and/or at the end of the current transmission block (if it is indicated) or at the start of subsequent coding block for packets transmitted within the con- text of a designed data content set (See object/stream data content identifier discussion below). Allowing receivers to initiate NACK cycles at any time they detect Adamson, Borman, et al. Expires September 2000 [Page 7] Internet Draft NORM Building Blocks March 2000 their repair needs have exceeded pending repair transmissions may result in slightly quicker repair cycles. However, it may be use- ful to limit the initiation opportunities to specific events such as at the end-of-transmission of an FEC coding block (or alterna- tively at detection of subsequent coding blocks). This can allow for a degree of synchronization among receivers requesting repair and may increase the effectiveness of timer-based NACK suppression mechanisms. In either case, the NACK cycle should begin with receivers observing backoff timeouts to facilitate NACK suppression as described below. Interface Description Inputs: 1) Object/stream data content and sequencing identifiers from sender transmissions. Outputs: 1) NACK Process Initiation Decision 3.2.2 NACK Content (TBD - Note this will be driven by the data content identification means used. Certainly, FEC repair counts will be needed, but encoding of more explicit repair information may be useful for other purposes (e.g. decorrelating loss clusters to help congestion control mechanism identify bottlenecks.) 3.2.3 NACK Suppression Mechanisms A primary NACK suppression mechanism is the use of initial backoff timeouts by receivers wishing to transmit NACK messages[Floyd95]. Upon expiration of the timeout, a receiver will transmit a NACK unless the content of his pending repair request is completely superseded by NACK messages heard from other receivers (when receivers are multicasting NACKs) or from some indicator from the sender . (Note: When receivers are unicasting NACK messages, the sender may facilitate NACK suppression by forwarding appropriate NACKs it has received to the group at large or provide some other indicator of repair information it will be subsequently transmit- ting). The backoff timeout periods used by receivers should be indepen- dently, randomly picked by receivers with an exponential distribu- tion [Nonnemacher98]. This results in the bulk of the receiver set holding off transmission of NACK messages under the assumption that Adamson, Borman, et al. Expires September 2000 [Page 8] Internet Draft NORM Building Blocks March 2000 the smaller number of "early NACKers" will supersede the repair needs of the remainder of the group. The mean of the distribution should be determined as a function of the current estimate of sender<->group greatest round trip time (GRTT) and a group size estimate which could be determined by other mechanisms within the protocol (See discussion below) or preset by the multicast applica- tion. (This function TBD) For small group sizes (and even for large group sizes) the tail of the distribution should be hard-limited so that repair requests are deterministically transmitted within some desirable interval. Additionally, the buffering limitations of sender and receiver applications may dictate some bound on the time limits for receiver NACK backoff timeouts (and sender repair aggre- gation holdoff timeouts). Note that these factors affect scalabil- ity of the protocol to large group sizes due to increased potential for NACK implosion. There are some secondary NACK suppression mechanisms which can be considered. For example, the sender's transmissions follow some ordinal sequence of transmission (observed through data/repair con- tent and/or ) which is "rewound" during repair transmissions. Receivers may wish to limit transmission of their NACKs only when the sender's current sequence of transmission passes the point at which the receiver has incomplete transmis- sions, thus reducing premature requests for repair of data the sender may be providing in response to other receiver requests. This mechanism can be very effective for protocol convergence in high loss conditions when transmissions of NACKs from other receivers (or indicators from the sender) are lost. Another mecha- nism (particularly applicable when FEC is used) is for the server to embed an indication of impending repair transmissions in current packets sent. For example, the indication may be as simple as an advertisment of the number of FEC packets to be sent for the cur- rent applicable coding block. Finally, some consideration might be given to using the NACKing history of receivers to weight their selection of NACK backoff timeout intervals. For example, if a receiver has historically been experiencing the greatest degree of loss, it may promote itself to statistically NACK sooner than other receivers. Note this assumes there is some degree of correlation over successive intervals of time in the loss experienced by receivers. This adjustment of backoff timeout selection may require the creation of an "early NACK" slot for these historical NACKers. This additional slot in the NACK backoff window will result in a longer repair cycle process which may not be desirable for some applications. The resolution of these trade-offs may be dependent upon the protocol's target application set or network. Interface Description Adamson, Borman, et al. Expires September 2000 [Page 9] Internet Draft NORM Building Blocks March 2000 Inputs: 1) Group greatest round trip time estimate (GRTT). 2) Group size estimate. 3) Application-defined bound on backoff timeout period. 4) NACKs from other receivers. 5) Pending repair indication from sender (may be forwarded NACKs). 6) Current sender transmission position. Outputs: 1) Yes/no decision to generate NACK message upon backoff timer expiration. 3.2.4 Sender NACK Processing and Repair Response Upon reception of a repair request from a receiver in the group, the sender will initiate a repair response procedure. The sender may wish to delay transmission of repair content until it has had sufficient time to accumulate potentially multiple NACKs from the receiver set. This allows the sender to determine the most effi- cient repair strategy for a given transport stream/object or FEC coding block. Depending upon the approach used, some protocols may find it beneficial for the sender to provide an indicator of pend- ing repair transmissions as part of the its current transmitted message content. This can aid some NACK suppression mechanisms. Alternatively, in the case of unicast feedback from the receiver set, it may be useful for the sender to forward (via multicast) superseding NACK messages to the group to allow for NACK suppres- sion when there is not multicast connectivity among the receiver set. When FEC is used, it is beneficial that the sender transmit previ- ously untransmitted parity content whenever possible. This maxi- mizes the receiving nodes' ability to reconstruct the entire trans- mitted content from their individual subsets of received messages. The transmitted he object and/or stream content will be marked with monotonically increasing sequence numbers (within a reasonably large ordinal space). If the sender observes the discipline of transmitting repair for the earliest content first, the receivers can use a strategy of witholding repair requests for later content until the sender once again returns to that point in the object/stream transmission sequence. This can increase overall message efficiency among the group and help work to keep repair cycles relatively synchronized without dependence upon strict tim- ing. This also helps minimize the buffering requirements of Adamson, Borman, et al. Expires September 2000 [Page 10] Internet Draft NORM Building Blocks March 2000 receivers and senders and reduces redundant transmission of data to the group at large. Interface Description Inputs: 1) Receiver NACKs 1) Group timing information Outputs: 1) Repair messages (FEC and/or Data content retransmission) 3.3 Group "Join" Policy/ Procedure (TBD - What does the protocol need to do accommodate group member- ship dynamics? For example, what policies do receivers need to abide by to join a group and begin NACKing? What information needs to be advertised in protocol message headers so that a receiver can efficiently join a session in progress? etc) Inputs: 1) Current object/stream data/repair content and sequencing identifiers from sender transmissions. Outputs: 1) Receiver yes/no decision to begin receiving and NACKing for reliable reception of data 3.4 Reliable multicast participant identification In a NACK-based reliable multicast protocol (or other multicast protocols) where there is the potential for multiple sources of data, it is necessary to provide some mechanism to uniquely iden- tify the sources (and possibly some or all receivers in some cases) within the group. Identity based on arriving packet source addresses is insufficient for several reasons. These reasons include routing changes for hosts with multiple interfaces which result different packet source addresses for a given host over time, network address translation (NAT) or firewall devices, or other transport/network bridging approaches. As a result, some type of unique source identifier (sourceId) field should be present in packets transmitted by reliable multicast session participants. 3.5 Data content identification Adamson, Borman, et al. Expires September 2000 [Page 11] Internet Draft NORM Building Blocks March 2000 The data content transmitted by the multicast sender requires some form of identification in the protocol header fields. This identi- fication is required to facilitate the reliable NACK-based repair process. These identifiers will be used in NACK messages gener- ated. There are two very general types of data which may comprise bulk transfer session content. These data types are static objects of finite size and continuous non-finite streams. A given application may wish to reliably multicast data content using either one or both of these data models. While it may be possible for some applications to further generalize this model and provide mecha- nisms to encapsulate static objects as content embedded within a stream, there are advantages to many applications to provide dis- tinct support for static bulk objects and messages with the context of a reliable multicast session. These applications may include content caching servers, file transfer or collaborative tools with bulk content. Applications with requirements for these static object types can then take advantage of transport layer mechanisms (i.e. segmentation/reassembly, caching, integrated forward error correction coding, etc) rather than being required to provide their own mechanisms for these functions at the application layer. As noted, some applications may alternatively desire to transmit bulk content in the form of one or more streams of non-finite size. Example streams include continuous quasi-realtime message broad- casts (e.g. stock ticker) or some content types which are part of collaborative tools or other more complex applications. And, as indicated above, some applications may wish to encapsulate other bulk content (e.g. files) into one more streams within a multicast session. Additionally, multiple streams can allow for parallized transmission within the context of a single multicast session. The components described within this building block draft document are envisioned to be applicable to both of these models with the potential for a mix of both types within a single multicast ses- sion. To support this requirement, the normal data content identi- fication should include a field to uniquely identify the object or stream within some reasonable temporal or ordinal interval. Note that it is _not_ expected that this data content identification will be globally unique. It is expected that the object/stream identifier will be unique with respect to a given sender within the reliable multicast session. Since the "bulk" object/stream content will generally require seg- mentation, some form of segment identification must also be pro- vided. This segment identifier will be relative to any object or stream identifier which has been provided. Thus, in some cases, Adamson, Borman, et al. Expires September 2000 [Page 12] Internet Draft NORM Building Blocks March 2000 NACK-based protocol instantiations may be able to receive transmis- sions of and NACK for repair of multiple streams and one (or possi- bly more) sets of static objects in parallel. Additionally, flags to determine the usage of the content identi- fier fields (e.g. stream vs. object) may be applicable. Flags may also serve other purposes in data content identification. It is expected that any flags defined will be dependent upon individual protocol instantiations. In summary, the following data content identifiers may be required to NACK-based protocols: 1) Object/Stream identifier () 2) Segment identifier () 3) Flags to differentiate interpretation of identifier fields or identifier structure which implicitly indicates usage. These fields have been identified since any generated NACK messages will use these identifiers in requesting repair or retransmission of data. NACK-based protocols are expected to greatly benefit from interaction with other reliable multicast building blocks (Generic Router Assist(GRA), in particular) and those other building blocks will need to appropriately consider these anticipated requirements. 3.6 Forward Error Correction Multiple forward error correction (FEC)approaches have be identi- fied which can provide great performance enhancements to the repair process of NACK-based and other reliable multicast protocols [Met- zner84, Macker97]. NACK-based protocols can reap additional bene- fits since FEC-based repair does not _generally_ require explicit knowledge of repair content within the bounds of its coding block size (in packets). Generally, repair packets generated using FEC algorithms with good erasure filling properties (e.g. Reed-Solomon) will be transmitted only in response to NACK repair requests from receiving nodes. However, there are benefits in some network environments for trans- mitting some predetermined quantity of FEC repair packets multi- plexed with the regular data segment transmissions [Gossink98]. This can reduce the amount of NACK traffic generated with rela- tively little overhead cost when group sizes are very large or the network connectivity has a large delay*bandwidth product with some nominal level of expected packet loss. While the application of FEC is not unique to NACK-based protocols, these cumulative requirements may dictate the types of algorithms and protocol approaches applicable to NACK-based protocols. Adamson, Borman, et al. Expires September 2000 [Page 13] Internet Draft NORM Building Blocks March 2000 A specific issue related to the use of FEC with NACK-based proto- cols is the mechanism used to identify which portion(s) of trans- mitted data content to which specific FEC packet are applicable. It is expected that FEC algorithms will be based on generating a set of parity repair packets for a corresponding block of transmit- ted data packets. Since data content packets are uniquely identi- fied by the concatenation of during transport, it is expected that FEC packets will be identified in a similar manner. It may be sufficient to identify FEC packets using the of the first segment of the block of data content packets for which the FEC repair packet is applica- ble and add an additional FEC identifier field to its posi- tion within the set of FEC packets for the block. The size of the field can potentially be small (8 or 16 bits) relative to other identifier fields since its size is limited by the FEC coding algorithm used. 3.7 Round-trip Timing Collection (TBD - There are tradeoffs here ... one-to-many vs. many-to-many protocol operation, etc) 3.8 Group Size Determination/Estimation (TBD) 3.9 Congestion Control Operation (TBD - A NACK-oriented protocol may place limitations/requirements on collection of information to facilitate congestion control of senders. There are a number of specific issues of TCP-Friendly Multicast Congestion Control (TFMCC)which must be addressed.) 3.10 Router/Intermediate System assistance (TBD - NACK-oriented protocols can potentially benefit greatly from router assistance. In particular, additional NACK suppression would be beneficial (This may impact how synchronized receiver NACK cycles are, sender advertisement of NACK-cycle parameters (i.e. GRTT, group size, etc), NACK content, others) 3.11 Additional protocol mechanisms (TBD- e.g. positive acknowledgement collection, performance statis- tics collection, session management, etc) 4.0 Security Considerations (TBD) Adamson, Borman, et al. Expires September 2000 [Page 14] Internet Draft NORM Building Blocks March 2000 5.0 References [Mankin98] A. Mankin, A. Romanow, S. Bradner, V. Paxson, "IETF Cri- teria for Evaluating Reliable Multicast Transport and Application Protocols", RFC 2357, June 1998. [Pingali93] S. Pingali, D. Towsley, J. Kurose. "A Comparison of Sender-Initiated and Receiver-Initiated Reliable Multicast Proto- cols". In Proc. INFOCOM, San Francisco, CA, October 1993. [Levine96] B.N. Levine, J.J. Garcia-Luna-Aceves. "A Comparison of Known Classes of Reliable Multicast Protocols", Proc. International Conference on Network Protocols (ICNP-96), Columbus, Ohio, Oct 29--Nov 1, 1996. [Clark90] D. Clark, D. Tennenhouse, "Architectural Considerations for a New Generation of Protocols". In Proc. ACM SIGCOMM, pages 201--208, September 1990. [Deering89] S. Deering. "Host Extensions for IP Multicasting". Internet RFC1112, August 1989. [Floyd95] S. Floyd, V. Jacobson, S. McCanne, C. Liu, and L. Zhang. "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", Proc. ACM SIGCOMM, August 1995. [Nonnenmacher98] J. Nonnenmacher and E. W. Biersack, "Optimal mul- ticast feedback," in IEEE Infocom , (San Francisco, California), p. 964, March/April 1998. [Gossink98] D. Gossink, J. Macker, "Reliable Multicast and Inte- grated Parity Retransmission with Channel Estimation", IEEE GLOBE- COM 98'. [Metzner84] J. Metzner, "An Improved Broadcast Retransmission Pro- tocol", IEEE Transactions on Communications, Vol. Com-32, No.6, June 1984. [Macker97a] J. Macker, "Integrated Erasure-Based Coding for Reli- able Multicast Transmission", IRTF Meeting presentation, March 1997. [Macker97b] J. Macker, "Reliable Multicast Transport and Integrated Erasure-based Forward Error Correction", Proc. IEEE MILCOM 97, Oct 1997. Adamson, Borman, et al. Expires September 2000 [Page 15] Internet Draft NORM Building Blocks March 2000 6.0 Authors' Addresses Brian Adamson adamson@itd.nrl.navy.mil Newlink Global Engineering Corporation 8580 Cinder Bed Road, Suite 1000 Newington, VA, USA, 22122 Dr. Carsten Borman cabo@tzi.org Universit"at Bremen Postfach 330 440 D - 28334 Bremen, Germany Sally Floyd floyd@aciri.org 1947 Center Street, Suite 600 Berkeley, CA 94704 Mark Handley mjh@aciri.org 1947 Center Street, Suite 600 Berkeley, CA 94704 Joe Macker macker@itd.nrl.navy.mil Naval Research Laboratory Washington, DC, USA, 20375 Adamson, Borman, et al. Expires September 2000 [Page 16] --============_-1258794657==_============ Content-Type: text/plain; charset="us-ascii" ; format="flowed" Brian __________________________________ Brian Adamson --============_-1258794657==_============-- From owner-rmt@listserv.lbl.gov Mon Mar 20 08:32:10 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 IAA28258 for ; Mon, 20 Mar 2000 08:32:10 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id EAA05155; Mon, 20 Mar 2000 04:41:36 -0800 (PST) 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 EAA05151 for ; Mon, 20 Mar 2000 04:41:34 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA11834 for ; Mon, 20 Mar 2000 04:41:34 -0800 (PST) Received: from motgate.mot.com (motgate.mot.com [129.188.136.100]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id EAA11831 for ; Mon, 20 Mar 2000 04:41:33 -0800 (PST) Received: [from pobox.mot.com (pobox.mot.com [129.188.137.100]) by motgate.mot.com (motgate 2.1) with ESMTP id FAA07320; Mon, 20 Mar 2000 05:41:32 -0700 (MST)] Received: [from homer.arc.corp.mot.com (homer.arc.corp.mot.com [217.1.10.38]) by pobox.mot.com (MOT-pobox 2.0) with ESMTP id FAA08893; Mon, 20 Mar 2000 05:41:29 -0700 (MST)] Received: from motorola.com ([217.2.31.112]) by homer.arc.corp.mot.com (8.9.3/8.9.3) with ESMTP id XAA21291; Mon, 20 Mar 2000 23:41:26 +1100 (EST) Message-ID: <38D61C51.36C0EDA@motorola.com> Date: Mon, 20 Mar 2000 23:40:49 +1100 From: Roger Kermode X-Mailer: Mozilla 4.7 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 To: rmt-list CC: Allison Mankin , Lorenzo Vicisano Subject: Draft RMT agenda: PLS send comments Content-Type: multipart/mixed; boundary="------------FA190BEEAD9367C8B094B307" Sender: owner-rmt@lbl.gov Precedence: bulk This is a multi-part message in MIME format. --------------FA190BEEAD9367C8B094B307 Content-Type: multipart/alternative; boundary="------------406FE68B19589A6083E9D5C9" --------------406FE68B19589A6083E9D5C9 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dear Everyone, below is a first pass at the Agenda for Adelaide. If we just do presentations with minimal discussions, we'll just about fill one of our two sessions. If there are additional items please let me know ASAP. We will adjust the agenda to include the additional items and to allow for more discussions in a couple of days time. cheers, Roger ---------------------------------------------------------------- Reliable Multicast Transport WG (rmt) Tuesday, March 28 at 0900-1130 Wednesday, March 29 at 0900- 1130 ================================= CHAIRS: Roger Kermode Lorenzo Vicisano Allison Mankin AGENDA: Tuesday 28th March 2000, 09:00-11:30 - Introduction and Agenda Bashing Kermode (5 mins) - Design Space/Building Blocks draft progress Vicisano (5 mins) draft-ietf-rmt-design-space-01.txt draft-ietf-rmt-buildingblocks-02.txt - Guidelines Draft progress Kermode (15 mins) draft-ietf-rmt-author-guidelines-xx.txt - FEC Building Block Luby (20 mins) draft-ietf-rmt-bb-fec-00.txt - ALC Protocol Instantiation Luby (20 mins) draft-ietf-rmt-pi-alc-00.txt - Track Archictecure Whetten (20 mins) draft-ietf-rmt-track-arch-xx.txt - Tree Building Levine ?? (20 mins) - NACK-Oriented Reliable multicast Buoilding Block Adamson (20 mins) draft-ietf-rmt-norm-bb-00.tx Wednesday 29th March 2000, 09:00-11:30 --------------406FE68B19589A6083E9D5C9 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Dear Everyone,

below is a first pass at the Agenda for Adelaide.
If we just do presentations with minimal discussions,
we'll just about fill one of our two sessions. If there
are additional items please let me know ASAP. We will
adjust the agenda to include the additional items and
to allow for more discussions in a couple of days time.

cheers,

Roger
 
 
 

----------------------------------------------------------------
Reliable Multicast Transport WG (rmt)

Tuesday, March 28 at 0900-1130
Wednesday, March 29 at 0900- 1130
=================================

CHAIRS: Roger Kermode <Roger.Kermode@motorola.com>
        Lorenzo Vicisano <lorenzo@cisco.com>
        Allison Mankin <mankin@ isi.edu>

AGENDA:

Tuesday 28th March 2000, 09:00-11:30

- Introduction and Agenda Bashing
  Kermode (5 mins)

- Design Space/Building Blocks draft progress
  Vicisano (5 mins)
  draft-ietf-rmt-design-space-01.txt
  draft-ietf-rmt-buildingblocks-02.txt

- Guidelines Draft progress
  Kermode (15 mins)
  draft-ietf-rmt-author-guidelines-xx.txt

- FEC Building Block
  Luby (20 mins)
  draft-ietf-rmt-bb-fec-00.txt

- ALC Protocol Instantiation
  Luby (20 mins)
  draft-ietf-rmt-pi-alc-00.txt

- Track Archictecure
  Whetten (20 mins)
  draft-ietf-rmt-track-arch-xx.txt

- Tree Building
  Levine ?? (20 mins)

- NACK-Oriented Reliable multicast Buoilding Block
  Adamson (20 mins)
  draft-ietf-rmt-norm-bb-00.tx
 

Wednesday 29th March 2000, 09:00-11:30 --------------406FE68B19589A6083E9D5C9-- --------------FA190BEEAD9367C8B094B307 Content-Type: text/x-vcard; charset=us-ascii; name="Roger.Kermode.vcf" Content-Transfer-Encoding: 7bit Content-Description: Card for Roger Kermode Content-Disposition: attachment; filename="Roger.Kermode.vcf" Content-Transfer-Encoding: 7bit begin:vcard n:Kermode;Roger tel;cell:+61-408-212-284 tel;fax:+61-2-966-0501 tel;work:+61-2-9666-0558 x-mozilla-html:FALSE url:www.motorola.com.au/arc/ org:Communications And Networking Lab;Motorola Australian Research Centre adr:;;Locked Bag 5028;Botany;NSW;1455;Australia version:2.1 email;internet:Roger.Kermode@motorola.com title:Principal Research Engineer/Lab Manager fn:Roger Kermode end:vcard --------------FA190BEEAD9367C8B094B307-- From owner-rmt@listserv.lbl.gov Mon Mar 20 11:03: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 LAA02074 for ; Mon, 20 Mar 2000 11:03:07 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id GAA06205; Mon, 20 Mar 2000 06:57:03 -0800 (PST) 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 GAA06201 for ; Mon, 20 Mar 2000 06:57:01 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id GAA22991 for ; Mon, 20 Mar 2000 06:57:00 -0800 (PST) Received: from motgate.mot.com (motgate.mot.com [129.188.136.100]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id GAA22985 for ; Mon, 20 Mar 2000 06:57:00 -0800 (PST) Received: [from pobox.mot.com (pobox.mot.com [129.188.137.100]) by motgate.mot.com (motgate 2.1) with ESMTP id HAA07710 for ; Mon, 20 Mar 2000 07:56:58 -0700 (MST)] Received: [from s-il02-e.comm.mot.com (s-il02-e.comm.mot.com [145.1.204.15]) by pobox.mot.com (MOT-pobox 2.0) with ESMTP id HAA24003 for ; Mon, 20 Mar 2000 07:56:56 -0700 (MST)] Received: by s-il02-e.comm.mot.com with Internet Mail Service (5.5.2650.21) id ; Mon, 20 Mar 2000 08:44:33 -0600 Message-ID: <57B7E404C641D211A39A0008C7A4FBA701C05045@s-il02-q.comm.mot.com> From: Avasthi Pradeep-CCOF59 To: rmt-list Subject: remove Date: Mon, 20 Mar 2000 08:44:30 -0600 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2650.21) Content-Type: text/plain; charset="iso-8859-1" Sender: owner-rmt@lbl.gov Precedence: bulk -----Original Message----- From: Roger Kermode [mailto:Roger.Kermode@motorola.com] Sent: Monday, March 20, 2000 6:41 AM To: rmt-list Cc: Allison Mankin; Lorenzo Vicisano Subject: Draft RMT agenda: PLS send comments Dear Everyone, below is a first pass at the Agenda for Adelaide. If we just do presentations with minimal discussions, we'll just about fill one of our two sessions. If there are additional items please let me know ASAP. We will adjust the agenda to include the additional items and to allow for more discussions in a couple of days time. cheers, Roger ---------------------------------------------------------------- Reliable Multicast Transport WG (rmt) Tuesday, March 28 at 0900-1130 Wednesday, March 29 at 0900- 1130 ================================= CHAIRS: Roger Kermode Lorenzo Vicisano Allison Mankin AGENDA: Tuesday 28th March 2000, 09:00-11:30 - Introduction and Agenda Bashing Kermode (5 mins) - Design Space/Building Blocks draft progress Vicisano (5 mins) draft-ietf-rmt-design-space-01.txt draft-ietf-rmt-buildingblocks-02.txt - Guidelines Draft progress Kermode (15 mins) draft-ietf-rmt-author-guidelines-xx.txt - FEC Building Block Luby (20 mins) draft-ietf-rmt-bb-fec-00.txt - ALC Protocol Instantiation Luby (20 mins) draft-ietf-rmt-pi-alc-00.txt - Track Archictecure Whetten (20 mins) draft-ietf-rmt-track-arch-xx.txt - Tree Building Levine ?? (20 mins) - NACK-Oriented Reliable multicast Buoilding Block Adamson (20 mins) draft-ietf-rmt-norm-bb-00.tx Wednesday 29th March 2000, 09:00-11:30 From owner-rmt@listserv.lbl.gov Mon Mar 20 16:06: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 QAA03208 for ; Mon, 20 Mar 2000 16:06:28 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id LAA07263; Mon, 20 Mar 2000 11:58:28 -0800 (PST) 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 LAA07259 for ; Mon, 20 Mar 2000 11:58:26 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA26846 for ; Mon, 20 Mar 2000 11:58:26 -0800 (PST) Received: from pi4.informatik.uni-mannheim.de (root@pi4.informatik.uni-mannheim.de [134.155.48.96]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id LAA26836 for ; Mon, 20 Mar 2000 11:58:25 -0800 (PST) Received: from pi4.informatik.uni-mannheim.de (mauve@pi4 [134.155.48.96]) by pi4.informatik.uni-mannheim.de (8.9.3/8.9.3) with ESMTP id UAA06905; Mon, 20 Mar 2000 20:58:16 +0100 (MET) Message-ID: <38D682D8.39604EE8@pi4.informatik.uni-mannheim.de> Date: Mon, 20 Mar 2000 20:58:16 +0100 From: Martin Mauve Organization: University of Mannheim X-Mailer: Mozilla 4.08 [en] (X11; U; SunOS 5.6 sun4u) MIME-Version: 1.0 To: Brian Adamson CC: RMT Subject: Re: Initial draft of NACK-Oriented Reliable Multicast Building Blocks References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-rmt@lbl.gov Precedence: bulk Content-Transfer-Encoding: 7bit Hi Brian, hi all, I have read the NORM draft and I like it. There are two minor questions I would like to ask: 1. How is the unique source ID supposed to be determined? I assume that a collision would be unacceptable and that the ID should be small? 2. How long does the sender have to be prepared to retransmit any given packet? I do understand that these two questions might be out of scope for the draft. However, I assume that a building block implementation would have to worry about these things? thanks, Martin -- --------------------------------------------------------------------------- Martin Mauve University of Mannheim Praktische Informatik IV Phone: +49-621-181-2616 L 15,16 Fax : +49-621-181-2601 68131 Mannheim mauve@pi4.informatik.uni-mannheim.de Germany --------------------------------------------------------------------------- From owner-rmt@listserv.lbl.gov Wed Mar 22 18:14:14 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 SAA16741 for ; Wed, 22 Mar 2000 18:14:13 -0500 (EST) Received: (from majordom@localhost) by listserv.lbl.gov (8.9.3/8.9.3) id OAA18141; Wed, 22 Mar 2000 14:28:40 -0800 (PST) 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 OAA18137 for ; Wed, 22 Mar 2000 14:28:38 -0800 (PST) Received: from SpamWall.lbl.gov (localhost [127.0.0.1]) by postal1.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA24981 for ; Wed, 22 Mar 2000 14:28:37 -0800 (PST) Received: from mercury.Sun.COM (mercury.Sun.COM [192.9.25.1]) by SpamWall.lbl.gov (8.9.3/8.9.3) with ESMTP id OAA24968 for ; Wed, 22 Mar 2000 14:28:35 -0800 (PST) Received: from eastmail1.East.Sun.COM ([129.148.1.240]) by mercury.Sun.COM (8.9.3+Sun/8.9.3) with ESMTP id OAA06818 for ; Wed, 22 Mar 2000 14:28:33 -0800 (PST) Received: from bcn.East.Sun.COM (bcn.East.Sun.COM [129.148.75.4]) by eastmail1.East.Sun.COM (8.9.3+Sun/8.9.3/ENSMAIL,v1.7) with ESMTP id RAA01645; Wed, 22 Mar 2000 17:28:30 -0500 (EST) Received: from bridge (bridge [129.148.75.125]) by bcn.East.Sun.COM (8.9.1b+Sun/8.9.1) with SMTP id RAA09211; Wed, 22 Mar 2000 17:28:26 -0500 (EST) Message-Id: <200003222228.RAA09211@bcn.East.Sun.COM> Date: Wed, 22 Mar 2000 17:28:20 -0500 (EST) From: Dah Ming Chiu - Sun Microsystems Reply-To: Dah Ming Chiu - Sun Microsystems Subject: TRACK: Draft of TRACK architecture To: rmt@lbl.gov Cc: whetten@talarian.com, sanjoy@edgix.com, Miriam.Kadansky@east.sun.com MIME-Version: 1.0 Content-Type: MULTIPART/mixed; BOUNDARY=Brace_of_Greyhounds_614_000 X-Mailer: dtmail 1.3.0 CDE Version 1.3 SunOS 5.7 sun4u sparc Sender: owner-rmt@lbl.gov Precedence: bulk --Brace_of_Greyhounds_614_000 Content-Type: TEXT/plain; charset=us-ascii Content-MD5: 6kPLopFrZC4PeG3SsrmZcA== Hi, Attached is a draft of the TRACK architecture document. We ran out of time to resolve all the issues. The remaining issues are listed in an "open issues" section at the end of the document. This is published for discussion at the Adelaide meeting. Hopefully shortly after that we will be able to put together a draft ID. I apologize for not having managed to get the document in the correct ID format. I think it is more important for me to send this out now so that people going to adelaide can get a chance to look at it, rather and delaying it. I'd like to thank all for working hard on this, specially Brian Whetten for putting the initial draft together, and Miriam for helping me get the attached document ready. Regards Dah Ming --Brace_of_Greyhounds_614_000 Content-Type: TEXT/plain; name="draft-whetten-track-architecture-xxrev06.txt"; charset=ISO-8859-1; x-unix-mode=0644 Content-Description: draft-whetten-track-architecture-xxrev06.txt Content-MD5: rlWTzw5/bnx7WCJaB7+dYg== Content-Transfer-Encoding: QUOTED-PRINTABLE Reliable Multicast Transport (RMT) WG B. Whetten Internet Draft Talarian Document: draft-ietf-rmt-track-arch-xx.txt D.Chiu Sun Microsystems S.Paul Edgix March 22, 2000 TRACK ARCHITECTURE A SCALEABLE REAL-TIME RELIABLE MULTICAST PROTOCOL Status of this Memo This document is an Internet-Draft and is in full conformance with=20 all provisions of Section 10 of RFC2026 [1].=20 Internet-Drafts are working documents of the Internet Engineering=20 Task Force (IETF), its areas, and its working groups. Note that=20 other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of=20 six months and may be updated, replaced, or obsoleted by other=20 documents at any time. It is inappropriate to use Internet- Drafts=20 as reference material or to cite them other than as "work in=20 progress."=20 The list of current Internet-Drafts can be accessed at=20 http://www.ietf.org/ietf/1id-abstracts.txt=20 The list of Internet-Draft Shadow Directories can be accessed at=20 http://www.ietf.org/shadow.html. 1. Abstract One of the protocol instantiations the RMT WG is chartered to create=20 is a TRee-based ACKnowledgement protocol (TRACK). Rather than=20 create a set of monolithic protocol specifications, the RMT WG has=20 chosen to break the reliable multicast protocols in to Building=20 Blocks (BB) and Protocol Instantiations (PI). A Building Block is a=20 specification of the algorithms of a single component, with an=20 abstract interface to other BBs and PIs. A PI combines a set of=20 BBs, adds in the additional required functionality not specified in=20 any BB, and specifies the specific instantiation of the protocol.=20 For more information, see the Reliable Multicast Transport Building=20 Blocks and Reliable Multicast Design Space documents [2][3]. The TRACK protocol instantiation (TRACK for short) is designed to=20 reliably and efficiently send data from a single sender to large=20 groups of simultaneous recipients. It provides functions similar to=20 the NACK PI, and adds in support for a tree-based hierarchy (in its=20 simplest form may consist of only the sender as the Repair Head) of=20 Repair Heads, which increases scalability by providing aggregation=20 of control traffic and local retransmission of lost packets. In=20 addition to using negative acknowledgements (NACKs) and forward=20 error correction (FEC) for efficient reporting and retransmission of=20 lost packets, it also provides tree-based ACKnowledgements (ACKs). =20 ACKs provide the Sender with confirmation of delivery of data=20 packets to the Receivers. Like the NACK PI, it may also take=20 advantage of Generic Router Assist where available. This document proposes a design rationale for the TRACK PI, an=20 architecture for TRACK, and a set of functional requirements TRACK=20 has of other Building Blocks. =20 2. Conventions Used in this Document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",=20 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in=20 this document are to be interpreted as described in RFC-2119 [4]. 3. Design Rationale and Protocol Requirements This section discusses many of the requirements imposed on the=20 design of the TRACK PI, as well as a design rationale which guides=20 the aspects where there is flexibility in selecting from different=20 potential design decisions. 3.1 Private and Public Networks TRACK is designed to work in both private, controlled networks and=20 in the public Internet. A controlled network typically has a single=20 administrative domain, has more homogenous network bandwidth, and is=20 more easily managed and controlled. These networks have the fewest=20 barriers to IP multicast deployment and the most immediate need for=20 reliable multicast services. Deployment in the Internet requires a=20 protocol to span multiple administrative domains, over vastly=20 heterogeneous networks. The IETF is specifically chartered with=20 producing standards for the Internet, so this must be the primary=20 target network type. However, robust transport protocols are grown,=20 not created, and most of the short term deployment experience will=20 likely come from controlled networks. Therefore, TRACK is designed=20 to support both. 3.2 Manual vs. Automatic Controls Some networks can take advantage of manual or centralized tools for=20 configuring and controlling the usage of a reliable multicast group. =20 In the public Internet, these tools have to fully distributed, and=20 preferably automatic, because they have to deal with the need to=20 span multiple AS=92s, each with their own policies. To address these=20 requirements, TRACK supports both manual and automatic algorithms=20 for monitoring, management, and configuration. 3.3 Heterogeneous Networks While the majority of controlled networks are symmetrical and=20 support many-to-many multicast, in designing a protocol for the=20 Internet, it must deal with virtually all major network types. =20 These include asymmetrical networks, satellite networks, networks=20 where only a single node may send to a multicast group, and wireless=20 networks. TRACK takes this into account by not requiring any many- to-many multicast services. In addition, the congestion control=20 component used in TRACK will specifically deal with the high=20 bandwidth-delay product faced in many satellite networks and the=20 high link level loss rate faced by some wireless networks. Finally,=20 TRACK does not assume that the topology used for sending control=20 packets has any congruence to the topology of the multicast address=20 used for sending data packets. 3.4 Use of Network Infrastructure=20 There is wide consensus that in order to scale a real-time reliable=20 multicast protocol, there must be some use made of the network=20 infrastructure (the routers and servers inside the network). New=20 software that supports the transport layer typically would run in=20 either the routers or the servers in the network, or both. =20 Deployment of router software (such as that in the Generic Router=20 Assist BB) is a powerful solution, but typically requires very long=20 time cycles, is of necessity limited in functionality, and requires=20 a graceful upgrade path. Server software (such as the Repair Head=20 control tree) is much easier to deploy, but may require new hardware=20 to be added to the network. =20 In controlled networks, particularly during the first deployment=20 phases of reliable multicast, it is reasonable to deploy servers=20 that only support a single application, or even to use selected end=20 clients themselves to perform the functions necessary for=20 scalability. For widely deployed Internet infrastructure=20 components, the server infrastructure is usually dedicated to just=20 the single protocol, but supports all instances of that protocol=20 running across that piece of the network. Examples of this usage=20 model include DNS, DHCP, NNTP, and HTTP. Therefore, the control=20 nodes used in TRACK are primarily designed to be run on dedicated=20 network servers, and support hundreds or thousands of simultaneous=20 data sessions over each server. Optionally, these components MAY=20 run on an end user computer. =20 A number of extensions to IP multicast, such as subtree multicast,=20 NACK suppression, ACK aggregation, tree configuration discovery, and=20 higher fidelity congestion control reports, have been proposed which=20 can run in the routers. If deployed widely, these would make=20 reliable multicast protocols easier to configure and to scale more=20 readily. Some or all of these features are being standardized as=20 part of the Generic Router Assist (GRA) component. TRACK is=20 designed to take advantage of GRA as it becomes available, but not=20 to require it. Ubiquitous deployment of GRA would likely reduce the=20 number of dedicated TRACK servers needed for large scale (i.e. more=20 than 1000 Receiver) deployments, and improve the performance of the=20 protocol. 3.5 Targeted Application Types Multicast applications can be divided into two classes, few-to-many =20 and many-to-many. Many-to-many applications include server=20 replication, multi-user games, small group conferencing, and=20 computer supported collaborative work. These applications typically=20 treat all members in a group as peers, require special semantics=20 such as total ordering of messages from multiple Senders, and often=20 have moderate scalability requirements. Other protocols, such as=20 RMP [WMK94], have been designed to support these many-many=20 applications. In line with the charter for RMT, TRACK focuses on one to many bulk=20 data distribution applications, such as multicast file transfer,=20 electronic software distribution, real time news and financial=20 market data distribution, "push" applications, audio/video/data=20 streaming, distance learning, and some types of server replication. =20 In order to meet these requirements, TRACK treats each Sender as an=20 independent entity, and provides no ordering or other shared state=20 across data sessions, although multiple data sessions can share the=20 same control infrastructure. The protocol is designed to scale to=20 at least many thousands of simultaneous Receivers. TRACK provides a=20 strong, but fully distributed membership protocol, which supports=20 scaling to many thousands of simultaneous Receivers while providing=20 confirmed delivery on messages. Similar to TCP, TRACK continuously=20 streams data to receivers, performing acknowledgement and=20 retransmission of older data packets at the same time that new data=20 packets are being sent. It also provides some special support for=20 real-time applications such as audio/video/data streaming and live=20 financial market data distribution. TRACK meets a requirement of synchronous streaming applications with=20 a new reliability level called Time Bounded Reliability. Time=20 Bounded Reliability restricts recovery of packets to a limited time=20 interval. This keeps dropped packets from blocking the rest of a=20 synchronous data stream and helps prevent a failed Receiver from=20 affecting other Receivers. 3.6 IETF Mandated Criteria In addition to the requirements imposed by the targeted network and=20 application types, TRACK is designed to meet all of the requirements=20 proposed by the IETF in RFC2357. - Congestion Control. TRACK includes provably safe and TCP-friendly=20 congestion control algorithms that also scale to large groups.=20 - Well-controlled, Scaleable Behavior. TRACK includes carefully=20 analyzed algorithms that manage and smooth the control traffic and=20 retransmissions. These are key to avoiding NACK implosion, ACK=20 implosion, and retransmission implosion (the local recovery=20 pathology). - Security. TRACK supports protection of the transport=20 infrastructure, through the use of lightweight authentication of=20 control and data packets. 3.7 Graceful Evolution Creating robust, universally applicable standard protocols takes a=20 great deal of time and protocol evolution. While TRACK is being=20 written as a standard, it will have to continue to evolve as real=20 world experience is gained with the protocol, similar to how TCP has=20 been tuned over almost 20 years of research and development. TRACK=20 addresses this through its use of Building Blocks, which allow=20 particular algorithms to be broken out in to separate components=20 with well defined interfaces. This allows evolution of these=20 components, hopefully with little or no changes required to the rest=20 of the protocol. =20 TRACK also addresses this through its use of session parameters. =20 TRACK is presently dependent on a number of parameters which MUST be=20 configured throughout the tree for optimal operation. TRACK=20 provides mechanisms to automatically distribute these parameters to=20 all members of the group, and OPTIONALLY provides mechanisms to=20 dynamically change some of these parameters during group operation. It also provides SNMP management and monitoring tools. Over time,=20 deployment experiences will provide input on which values work best=20 for most deployments, leading to further refinements of the=20 standard.=20 3.8 Algorithm Selection The above design criteria applies to the general architecture of the=20 protocol. Additional criteria were used for selecting the optimal=20 algorithms for different sets of functions. These rationales are=20 described below, along with the individual functions they apply to. 4. Architectural Overview 4.1 TRACK Entities=20 4.1.1 Node Types TRACK divides the operation of the protocol in to three major=20 entities: Sender, Receiver, and Repair Head. It is assumed that=20 Senders and Receivers typically run as part of an application on an=20 end host client. It is assumed that Repair Heads are components in=20 the network infrastructure, managed by different network managers as=20 part of different administrative domains. A Repair Head MAY be run=20 on an end host client, in which case it functions as both a Receiver=20 and a Repair Head. Absent of any automatic tree configuration, it=20 is assumed that the Repair Heads have relatively static=20 configurations, which consist of a list of nearby possible Repair=20 Heads. Senders and Receivers, on the other hand, are transient=20 entities, which typically only exist for the duration of a single=20 data session. Again, these entities MAY be used in other ways than=20 this, but this is the primary design rationale for TRACK. In=20 addition to these core components, applications that use TRACK are=20 expected to interface with other services that reside in other=20 network entities, such as multicast address allocation, session=20 advertisement, network management consoles, DHCP, DNS, server level=20 multicast, and multicast key management. 4.1.2 Multicast Group Address A multicast group address is a pair consisting of an IP multicast=20 address and a UDP port number. It may optionally have a Time To=20 Live (TTL) value, although this value MUST only be used for=20 providing a global scope to a Data Session.=20 4.1.3 Data Session A Data Session is the unit of reliable delivery of TRACK. It=20 consists of a sequence of sequentially numbered Data packets, which=20 are sent by a single Sender over a single Data Multicast Address. =20 They are delivered reliably, with acknowledgements and=20 retransmissions occurring over the Control Tree. It is uniquely=20 identified by a combination of a Session ID, senders address and=20 port, and the multicast address and port.=20 A given Data Session is received by a set of zero or more Receivers,=20 and a set of zero or more of Repair Heads. One or more Data=20 Sessions MAY share the same Data Multicast Address (although this is=20 not recommended). Each TRACK node can simultaneously participate in=20 multiple Data Sessions. A receiver MUST join all the Data Multicast=20 Addresses and Control Trees corresponding to the Data Streams it=20 wishes to receive. 4.1.4 Control Tree A Control Tree is a hierarchical communication path used to send=20 control information from a set of Receivers, through zero or more=20 Repair Heads (RHs), to a Sender. It forms a tree, allowing the=20 interior nodes to aggregate this control information as it moves up=20 the tree. Each Data Session uses a Control Tree. Each RH in the control tree uses a separate multicast address for=20 communicating with its children. Optionally, these RH multicast=20 addresses may be the same as the multicast address of the Data=20 Channel. 4.1.5 Session ID A Session ID is a 32-bit number (to be formally defined in the=20 Common Packet Header BB) chosen either by the application that=20 creates the session or selected by TRACK. Senders and Receivers use=20 the Session ID to distinguish Data Streams. A Sender may specify a=20 Session ID in the range from (2^31) to (2^32)-1. Numbers in the=20 range from 0 to (2^31)-1 are reserved. If a sender specifies 0 as=20 the Stream ID, then TRACK randomly assigns a Stream ID in the range=20 from 1 to (2^31)-1. If a Session ID is selected that is already in=20 use on a Control Tree, the new stream will fail, and will need to=20 select a new Session ID. A session is uniquely identified by its Session ID, its sender=92s=20 address/port, and its Data Multicast Address and port. 4.1.6 Packet Sequence Numbers A packet sequence number is a 32 bit number in the range from 1=20 through 2^32 =96 1, which is used to specify the sequential order of a=20 Data packet in a Data Stream. A sender node assigns consecutive=20 sequence numbers to the Data packets provided by the Sender=20 application. Zero is reserved to indicate that the data session has=20 not yet started. =20 4.1.7 Data Queue A Data Queue is a buffer, maintained by a Sender or a Repair Head,=20 for transmission and retransmission of the Data packets provided by=20 the Sender application. New Data packets are added to the data=20 queue as they arrive from the sending application, up to a specified=20 buffer limit. The admission rate of packets to the network is=20 controlled by flow and congestion control algorithms. Once a packet=20 has been received by the Receivers of a Data Stream, it may be=20 deleted from the buffer. 4.1.8 Packet Types TRACK defines a set of packets, which can be implemented either on=20 top of UDP or directly on top of IP. All TRACK packets will conform=20 to the Common Packet Headers BB. Each TRACK packet definition=20 consists of a fixed header, zero or more option headers, followed by=20 data or control information. Data is carried in Data packets. The same packet type is used both=20 to transmit Data the first time and for retransmissions of lost=20 packets (see open issue). Each Data packet has a Session ID and a=20 sequence number, which identify the packet and allow a receiver=20 application to reconstruct the data stream from the Data packets. =20 When a Data packet has been received by all Receivers, it is said to=20 have gone stable. Receivers and Repair Heads unicast periodic status packets to their=20 parents. An ACK is sent regularly to indicate the status of the=20 Data packets which have arrived and to furnish congestion control=20 statistics about the state of data reception at the node. An ACK=20 requests retransmission of Data packets that have not been received. =20 An ACK also acknowledges packets that have become stable. A packet=20 becomes stable when it has been received by enough Repair Heads and=20 Receivers that the sender is no longer required to hold the packet=20 for retransmission. A NACK is an ACK that is used to request=20 immediate recovery of lost Data packets. ACKs and NACKs have the=20 same format, but ACKs are passed all the way up the tree, while=20 NACKs are only sent as far as needed to find a node which can=20 provide all the requested retransmissions. A child will also send=20 an ACK in response to a NullData or Heartbeat packet if it has not=20 sent an ACK within a certain time interval. When a Receiver or Repair Head wishes to establish a repair service=20 relationship, it uses a Bind packet to bind to a parent Repair Head.=20 A parent sends an Accept or Reject after it processes a Bind packet. The Reject message comes with a reason code that explains the reason=20 for rejection. The reason may indicate that the parent is not=20 connected into the tree yet, so that the receiver can try again=20 later (see open issue). When a Receiver or Repair Head wishes to leave a session, it sends a=20 Leave request to its parent. The parent replies with a LeaveConfirm=20 packet, at which time the child is allowed to leave. A Repair Head or Sender periodically sends Heartbeat packets to=20 notify its child nodes that it is alive.=20 If a Sender has no data to send for a session, it periodically multicasts a NullData packet on the Data Multicast Address. =20 NullData packets inform receivers about the state of the Data Stream=20 and the Sender. =20 If a child node is not operating normally, or a parent node restarts after a failure and receives a packet from a child not in its child=20 list, then the parent node sends an Eject packet to the child node. =20 4.2 Basic Operation of the Protocol For each Data Session, TRACK provides sequenced, reliable delivery=20 of data from a single Sender to up to tens of thousands of=20 Receivers. A TRACK Data Session consists of a network that has=20 exactly one Sender node, zero or more Receiver nodes and zero or=20 more Repair Heads. The figure below illustrates a TRACK Data Session with multiple=20 Repair Heads. =20 A Sender joins the TRACK tree and multicasts data packets on the=20 Data Multicast Address. All of the nodes in the session subscribe=20 to the class D IP multicast address and UDP port associated with the=20 Data Multicast Address.=20 There is no assumption of congruence between the topology of the=20 Data Multicast Address and the topology of the Control Tree. -------> SD (Sender node)----->| ^^^ | ACKs / | \ Control | and / | \ Tree | NACKs / | \ | / | \ (Repair | / | \ Head | / | \ nodes) v RH RH RH <------------| ^^ ^^^ ^^ | Data / | / | \ | \ |=20 Channel / | / | \ | \ | / | / | \ | \ v R R R R R R R <--------- (Receiver Nodes) A Receiver joins a Data Multicast Address to receive data. A=20 Receiver periodically informs its parent about the packets that it=20 has or has not received by unicasting an ACK packet to the parent. =20 Each parent node aggregates the ACKs from its child nodes and (if it=20 is not the Sender) unicasts a single aggregated ACK to its parent. =20 For lower latency recovery in low loss networks, Receivers can also=20 generate NACKs upon detection of losses. These have the same format=20 as a ACK, but are only passed up the tree as far as necessary in=20 order to find a Repair Head that can retransmit the packet. The=20 Repair Heads provide NACK suppression, which provides traffic=20 minimization benefits similar to ACK aggregation. The Sender and each Repair Head have a multicast Local Control=20 Channel to their children. This is used for transmitting Heartbeat=20 packets that inform their child nodes that the parent node is still=20 functioning. This channel is also used to perform local=20 retransmission of lost data packets to just these children. TRACK=20 will still provide correct operation even if multicast addresses are=20 reused across multiple Data Sessions or multiple Local Control=20 Channels. It is NOT RECOMMENDED to use the same multicast address=20 for multiple Local Control Channels serving any given Data Session. A tree forms a loop from the Sender to the Receivers, to the Repair=20 Heads, and back to the Sender. Data and NullData packets regularly=20 exercise the downward data direction. Heartbeat packets exercise=20 the downward control direction. ACKs, NACKs, and HeartbeatResponse=20 packets regularly exercise the control tree in the upward direction. =20 This combination constantly checks that all of the nodes in the tree=20 are still functioning correctly, and initiates fault recovery when=20 required. In addition to using ACKs, NACKs, and Repair Heads for scaleable=20 loss notification and retransmission, TRACK also supports the=20 optional use of Generic Router Assist (GRA) and integrated Forward=20 Error Correction (FEC). Two of the major functions of GRA are NACK=20 suppression and dynamically scoped local retransmission. These=20 functions, if enabled, are independently deployed between each=20 parent and its children. For the purpose of GRA NACK functions,=20 each parent is considered to be a Sender and the children of that=20 parent are considered as the Receivers. Retransmission requests, both NACKs and ACKs, contain selective=20 bitmaps indicating which packets need to be retransmitted. If FEC=20 is enabled, these bitmaps provide enough information to determine=20 the number of parity packets to be sent rather than sending=20 individual retransmissions. 4.3 Session Creation Before a data session starts delivering data, the tree for the Data=20 Session needs to be created. This process binds each Receiver to=20 either a Repair Head or the Sender, and binds the participating=20 Repair Heads in to a loop-free tree structure with the Sender as the=20 root of the tree. This process requires tree configuration=20 knowledge, which can be provided with some combination of manual=20 and/or automatic configuration. The actual algorithms for tree=20 configuration will be part of the Automatic Tree Configuration BB,=20 and are discussed in the next section. To start a data session, a Sender communicates to the Receivers, via=20 either an external service or through the application itself, the=20 Data Multicast Address that will be used for the Data Session. It=20 may advertise other relevant session information such as whether or=20 not Repair Heads should be used, whether manual or automatic tree=20 configuration should be used, and the time at which the session will=20 start. It may also advertise certain hints for the tree=20 configuration algorithms.=20 After receiving this out of band communication, the Receivers join=20 the Data Multicast Address, and attempt to bind to either the Sender=20 or a local Repair Head. The tree configuration algorithms are=20 responsible for providing the Receiver with a list of one or more=20 nodes which it will attempt to bind to. It will attempt to bind to=20 the first node in the list, and if this fails, it will move to the=20 next one. A Receiver only binds to a single Repair Head or Sender,=20 at a time, for each Data Session.=20 When a Repair Head has a Receiver bind to it for a given Data=20 Session, it then also binds to another Repair Head or to the Sender,=20 depending on the list given to it by the tree configuration=20 algorithms. The tree configuration algorithms are responsible for=20 ensuring that the tree is formed without loops.=20 Once the bind process has traversed from the Receivers up to the=20 Sender, it then repeats the process in the reverse direction. In=20 this confirmation phase, the Sender enforces a set of uniform=20 Session Configuration Parameters on all members of the session, and=20 verifies that no loops have formed in the tree. The Session=20 Configuration Parameters include values for certain protocol=20 constants, and indicate the set of optional algorithms which will be=20 used for this Data Session, and which each member must support in=20 order to be a member of the tree. Any failures to create a loop=20 free tree, or among members unable to support all the required=20 features, are handled as failures of those particular members. At the same time as the Sender initiates the second half of the tree=20 binding, it is also free to start sending Data packets on the Data=20 Multicast Address. Repair Heads and Receivers may start receiving=20 these packets, but may not request retransmission or deliver data to=20 the application until they receive confirmation that they have=20 successfully bound to the group. Some of the Session Configuration Parameters MAY be changed=20 dynamically by the Sender by advertising the changed values as part=20 of the keep-alive control packets periodically sent through the=20 tree. If a given Session Configuration Parameter must be the same=20 at all nodes in order to provide safe operation, it MUST NOT be=20 dynamically changed once the Data Session has started.=20 4.4 Tree Configuration TRACK is designed to work either with manual configuration of the=20 tree, or with optional automatic tree configuration. Tree=20 configuration is responsible for providing each Receiver and Repair=20 Head with a list of one or more appropriate parents to attempt to=20 bind to. =20 The goals of automatic tree configuration are: ? allow Receivers to automatically locate their best Repair Head(s). ? provide automatic configuration of the Repair Head with the=20 assumption that Repair Heads are servers operating in the network. ? dynamically select which receivers become repair heads. These algorithms are specified in the Tree Configuration BB. In=20 order to make sure that TRACK can be standardized in a timely=20 fashion, the automatic tree configuration algorithms need to be=20 separate from the rest of the TRACK protocol, so that TRACK can be=20 deployed even without these algorithms. When these algorithms from=20 the Tree Configuration BB are not available, TRACK will use static=20 configuration. 4.5 Data Transmission and Retransmission Data is multicast by a Sender on the Data Multicast Address. =20 Retransmissions of data packets may be multicast by the Sender on=20 the Data Multicast Address or be multicast on a Local Control=20 Channel by a Repair Head. In order to provide NACK suppression and=20 to work with proactive FEC, retransmissions are always multicast. =20 If Generic Router Assist is enabled, the routers may provide NACK=20 suppression and allow dynamically scoped retransmission to just the=20 subset of Receivers and Repair Heads that have missed a packet. =20 A Repair Head joins all of the Data Multicast Addresses that any of=20 its descendants have joined. A Repair Head is responsible for=20 receiving and buffering all data packets using the reliability=20 semantics configured for a stream. As a simple to implement option,=20 a Repair Head MAY also function as a Receiver, and pass these data=20 packets to an attached application. For additional fault tolerance, a Receiver MAY subscribe to the=20 multicast address associated with the Local Control Channel of one=20 or more Repair Heads in addition to the multicast address of its=20 parent. In this case it does not bind to this Repair Head or=20 Sender, but will process Retransmission packets sent to this=20 address. If the Receiver=92s Repair Head fails and it transfers to=20 another Repair Head, this minimizes the number of data packets it=20 needs to recover after binding to the new Repair Head.=20 There are three types of retransmissions: local retransmission,=20 global retransmission, and dynamically scoped retransmission. 4.5.1 Local Retransmission If a Repair Head determines from its child node's ACKs or NACKs that=20 a Data packet was missed, the Repair Head retransmits the Data=20 packet or, if FEC is enabled, an FEC parity packet. The Repair Head=20 multicasts the Retransmission packet on its multicast Local Control=20 Channel. In the event that a Repair Head receives a retransmission=20 and knows that its children need this repair, it re-multicasts the=20 retransmission to its children. The scope of retransmission is considered part of the Control=20 Channel=92s multicast address, and is derived during tree=20 configuration. 4.5.2 Global Retransmission If a Sender node receives an ACK or NACK that indicates missing=20 packets, the Sender MAY support an option for global retransmission. (Note: the Sender is always a Repair Head for its own Control=20 Channel, which is irrespective of whether Global Retransmission is=20 selected). In this case, the Sender multicasts the requested=20 packets on the Data Multicast Address. Again, if FEC is enabled,=20 the Sender will transmit one or more parity packets instead of the=20 actual data packets. This is an optional feature, used as an=20 optimization for some environments such as asymmetrical networks. =20 It MUST NOT be enabled if Generic Router Assist is being used. 4.5.3 Dynamically Scoped Retransmission On a network whose routers support dynamically scoped=20 retransmissions through Generic Router Assist, then this may be=20 used. Dynamically Scoped Retransmissions use soft state kept in the=20 routers to constrain the Retransmission to only the children that=20 have requested them through a NACK. Dynamically Scoped=20 Retransmissions are known to be susceptible to router topology=20 changes. Therefore, only the first retransmission of a packet is=20 sent via this mechanism. Thereafter, only the above two mechanisms=20 should be used. This will allow the protocol to provide=20 connectivity even during router topology changes, albeit with less=20 efficiency. 4.6 Control Traffic Management One of the largest challenges for scaleable reliable multicast=20 protocols has been that of controlling the potential explosion of=20 control traffic. There is a fundamental tradeoff between the=20 latency with which losses can be detected and repaired, and the=20 amount of control traffic generated by the protocol. In conjunction=20 with the dynamic global tree parameters, TRACK provides a set of=20 algorithms that carefully control and manage this traffic,=20 preventing control traffic explosion. Despite their different names, ACKs and NACKs both function as=20 selective acknowledgements of the window of contiguous sequence=20 numbers that have not yet been fully acknowledged. The only=20 difference between the packet headers is a single flag. ACKs are controlled by setting a number of tree wide parameters=20 controlling their maximum rate of generation. The primary parameter=20 is the ratio parameter, R, for the maximum number of ACK packets to=20 be generated per data packet sent. The higher R is, the faster=20 positive acknowledgements will be generated all the way back to the=20 sender, but the more traffic that is generated. =20 ACKs MUST be enabled for any Data Session. NACKs SHOULD be=20 implemented as part of any implementation, and MAY be enabled for=20 any given Data Session. If enabled, then on detection of a lost=20 packet, a Receiver waits a random interval before sending a NACK. =20 If the Receiver receives the retransmitted data before the NACK=20 timer expires, the Receiver cancels the NACK. This reduces the=20 chance that multiple Receivers generate a NACK for the same packet. A Repair Head node multicasts a Data packet to its children as soon=20 as it gets a NACK request for that packet, unless it recently=20 retransmitted that packet. If it does not have the missing packet,=20 it forwards the NACK to its parent, and multicasts a control packet=20 to its children to suppress any further NACKs for that packet from=20 them. The Repair Head forwards only one NACK for a missing Data=20 packet within a specified period of time. If more than one packet=20 has been detected as missing before the NACK is sent, the NACK will=20 request all of the missing packets. NACKs are particularly good for providing real-time data=20 distribution in networks with low loss rates and short to moderate=20 RTT times. See [5] for comparisons on the tradeoffs between ACKs=20 and NACKs for low latency recovery of lost packets. 4.7 Integrated Forward Error Correction Work [6][7][8] has shown the benefits of incorporating reactive=20 forward error correction (FEC) into reliable multicast protocols. =20 This feature encodes data packets with FEC algorithms, but does not=20 transmit the parity packets until a loss is detected. The parity=20 packets are then transmitted and are able to repair different lost=20 packets at different Receivers. This is a powerful tool for=20 providing scalability in the face of independent loss. When=20 implemented, it is a simple matter to also provide proactive FEC=20 which automatically transmits a certain percentage of parity packets=20 along with the data. This is particularly useful when a high=20 minimum error rate is expected, or when low latency is particularly=20 important. Both of these are optionally supported in TRACK. FEC is organized around windows of packets. TRACK Data packets=20 include an FEC offset window field, which identifies the offset of a=20 given packet within an FEC window. Combined with the FEC session=20 configuration parameters, this allows receivers to decode a=20 combination of Data and parity packets, to generate each window of=20 Data packets. Proactive FEC packets are parity packets sent as=20 global retransmissions at the same time a window of Data packets are=20 sent. Reactive FEC packets are sent either from a Repair Head or a=20 Sender, in response to requests for retransmissions. If using=20 reactive FEC, a Repair Head must first have all the packets in a=20 window before it can respond to any request for retransmission. The=20 ACK and NACK bitmaps, combined with the information in the headers=20 of the Data packets, provides each Repair Head with enough=20 information to determine which parity packets the RH must compute=20 and send in response to requests for retransmission. 4.8 Flow and Congestion Control Flow and congestion control algorithms act to prevent the Senders=20 from overflowing the Receivers=92 buffers and to force them to share=20 the network fairly and safely with other TCP and RM connections. =20 TRACK uses a combination of a transmission window for flow control,=20 and the dynamic rate control algorithms specified in the Congestion=20 Control (CC) BB for congestion control. These algorithms have been=20 proven to meet all the requirements for flow and congestion control,=20 including being safe for use in a general Internet environment, and=20 provably fair with TCP. The Sender application provides the minimum and maximum rate limits=20 as part of the global parameters. A Sender will not transmit at=20 lower than the minimum rate (except possibly during short periods of=20 time when certain slow receivers are being ejected), or higher than=20 the maximum rate. If a Receiver is not able to keep up with the=20 minimum rate for a period of time, the CC BB algorithms will cause=20 it to leave the group. Receivers that leave the group MAY attempt to=20 rejoin the group at a later time, but SHOULD NOT attempt an=20 immediate reconnection. 4.9 Membership TRACK provides a simple counted membership for each session,=20 available at the Sender node. This counted membership is a simple=20 count of the Receiver nodes that have joined a session as well as=20 any Repair Heads that are also acting as Receivers. A failure=20 report is also provided, which will notify a Sender of any Receivers=20 or Repair Heads that have been detected as having failed or being=20 forced to leave the group. Both the counted membership and failure=20 reports are piggybacked on ACK and NACK packets that are sent=20 towards the Sender, and aggregated together at each Repair Head. A=20 failure report is bounded in size, and so may not be able to report=20 all failures if many occur at once. =20 Each Repair Head and Sender also keeps track of the list of=20 currently attached children, and makes this information available to=20 authorized entities through an SNMP interface. An external=20 membership server could be used to periodically poll the full per=20 session membership from all the Repair Heads and Senders. Combined=20 with the real-time counted membership and failure reports, this=20 enables an application to keep accurate track of global group=20 membership. 4.10 Fault Detection and Recovery 4.10.1 Sender node failure detection A Sender node that has no data to send will periodically send=20 NullData packets on the Data Multicast Address. If a Receiver or a=20 Repair Head fails to receive Data packets or NullData packets for a=20 session sent by the Sender, the Receiver detects a Sender failure. 4.10.2 Receiver node failure detection A Receiver node sends ACKs and (optionally) NACKs for each of the=20 active sessions that it has joined. If none of the sessions are=20 active, then the Receiver sends HeartbeatResponse packets to its=20 parent. If a Receiver's parent node does not receive a ACK, NACK or a=20 HeartbeatResponse within a specified time interval, the parent=20 detects the failure of the Receiver and removes the child from its=20 child list. 4.10.3 Repair Head failure detection Each Repair Head node sends Heartbeat packets to its child nodes on=20 its multicast Control Tree. If the child nodes do not receive any=20 Heartbeats from their parent Repair Head, they detect failure of the=20 parent. 4.10.4 Repair Head discovery TRACK supports an option which allows the nodes in the TRACK tree to=20 acquire the addresses and location of its ancestors in the control=20 tree and the addresses of its parent's siblings. If a TRACK node's=20 parent fails, then the node can use the acquired information to join=20 an alternate control node. 4.10.5 Message Stability Semantics To successfully recover from a failed Repair Head, the children of=20 that Repair Head need to be able to recover the packets they missed=20 while transferring over to a new parent. TRACK provides two levels=20 of message stability, pessimistic and optimistic, to assist in this. =20 With pessimistic stability, a parent may only release a packet from=20 its Data Queue when it has been acknowledged by all of its=20 descendants. With optimistic stability, a parent may release a=20 packet from its Data Queue when each of its direct children have=20 acknowledged it. Pessimistic stability allows a child to recover by=20 switching to any node in the tree, since the Sender will still have=20 a copy of all that child=92s missing packets. Optimistic stability=20 requires less buffer space and may provide higher throughput, but=20 does not provide strong assurances that children will be able to=20 always recover from a failure of their parent. 4.10.6 Recovery When a child node detects failure of its parent node, it can try to=20 reconnect to an alternate Repair Head of the TRACK tree, or it can=20 try to reconnect directly to the Sender. The failure detection=20 timeouts, coupled with the use of pessimistic stability semantics=20 (if enabled), provide reasonable assurances that a single node=20 failure can be handled without any Receivers losing any of the data=20 packets in a session. 4.11 Ordering Semantics TRACK offers three levels of delivery ordering semantics: Unordered=20 Reliable, Time Bounded Reliable, and Source Ordered Reliable. These=20 are selected on a per session basis as part of the Session=20 Configuration Parameters. =20 Unordered Reliable provides a reliable stream of packets, without=20 duplicates, and delivers them in the order received. This allows=20 the lowest latency delivery for extremely time sensitive=20 applications. If a packet in the session can not be delivered for=20 some reason, a failure is declared for the session. Source Ordered Reliable provides TCP semantics on delivery. All=20 packets are delivered in the order sent, without duplicates, and=20 without losses. If a loss occurs, a failure is declared for the=20 session. Time Bounded Reliable provides bounded TCP semantics on delivery. A=20 specific time period is associated with the session, and this is the=20 maximum time allowed for recovery of a packet at the Receiver after=20 it is detected as lost. If recovery of all lost packets happen=20 within this time bound, then the session will have Source Ordered=20 Reliable semantics. For any packets that take longer than the time=20 bound to recover, the Receiver declares them as lost, notifies the=20 application of this, and then will deliver any packets that have=20 been pending due to the packets now declared as lost. =20 4.12 SNMP Support The Repair Heads and the Sender are designed to interact with SNMP=20 management tools. This allows network managers to easily monitor=20 and control the sessions being transmitted. All TRACK nodes have=20 SNMP MIBs defined. SNMP support is optional for Receiver nodes, but=20 is required for all other nodes. 5. Functional Specification for TRACK Requirements of Building Blocks=20 Work [2] provides a rationale for decomposing the RMT protocols in=20 to Building Blocks and Protocol Instantiations. This section=20 provides a simple specification of the functions that TRACK requires=20 from each of the Building Blocks. It also provides some basic=20 description of the interfaces between these components. Since the following overlaps with what is done in the BBs, all of=20 section 5 is for discussion purposes only, and is not meant to=20 replace what is specified in the supporting BBs. The BBs will=20 define the actual algorithms. 5.1 NACK-based Reliability This building block defines NACK-based loss detection/notification=20 and recovery. The major issues it addresses are implosion=20 prevention (suppression) and NACK semantics (i.e. how packets to be=20 retransmitted should be specified, both in the case of selective and=20 FEC loss repair). The NACK suppression mechanisms used by TRACK are unicast NACKs with=20 multicast confirmation and exponentially distributed timers. These=20 suppression mechanisms primarily need to both minimize delay while=20 also minimizing redundant messages. They may also need to have=20 special weighting to work with Congestion Feedback. 5.1.1 NACK BB Algorithms Exponential Back Off. When a packet is detected as lost, an=20 exponentially distributed timer is set, based on the algorithms in=20 [9]. This timer is biased based on the input congestion weighting=20 factor. If either a packet or an explicit suppression message with=20 the same sequence number is detected before the timer goes off, the=20 timer is cancelled. NACK Generation. When a timer goes off, the protocol instantiation=20 is notified to generate a NACK for that sequence number. The=20 protocol instantiation may, at its discretion, group multiple NACK=20 notifications in to a single NACK packet. For TRACK, NACKs are=20 implemented as a unicast packet with a multicast confirmation=20 response. Response to a Retransmission Request. When a Repair Head or other=20 possible retransmission agent receives the first NACK from another=20 group member for a given packet, it notifies the protocol=20 instantiation to send either a data retransmission or, if it doesn=92t=20 have the packet for retransmission, an optional suppression message. =20 It then sets an embargo timeout, tied to the RTT to the furthest=20 Receiver, during which other requests for the same packet will be=20 ignored. The length of this embargo doubles each time that a=20 retransmission is sent. This algorithm should also work with=20 requests for retransmissions that come in the form of ACKs, as the=20 algorithms and packet formats for both are identical, with the=20 exception of the suppression mechanisms used. GRA Signaling. A primary function of GRA is to do NACK=20 elimination/suppression and subcasting of repairs. In order to do=20 this, the transport need to signal the GRA-enabled routers to turn=20 on the appropriate algorithms. This algorithm has to deal with=20 issues such as router topology changes. While not dealt with in=20 detail here, this is a very subtle issue, which will have to be=20 dealt with carefully. 5.1.2 NACK BB Parameters Congestion Weighting. From Congestion Control BB. This is a=20 weighting parameter for NACK suppression timers. The exact=20 algorithms for this are still to be determined. Loss Notification. From TRACK protocol instantiation. Notification=20 at a Sender that a packet has been detected as lost, and the=20 sequence number of that packet. Retransmission Request. From TRACK protocol instantiation. When a=20 NACK or ACK with a request for retransmission is received, this=20 needs to be passed to the BB for handling retransmission requests. =20 GRA Enabled. From PI. Is GRA enabled in the network? 5.2 FEC Repair BB This building block is concerned with packet level FEC repair. It=20 specifies the FEC codec selection and the FEC packet naming=20 (indexing) for both reactive FEC and proactive FEC. 5.2.1 FEC BB Algorithms FEC Input. Receive a window of packets (not necessarily all at=20 once), and store pointers to them for use in the FEC Create Parity=20 algorithm. FEC Create Parity. Given a window of packets, create and return a=20 parity packet. If a window is not yet full, first call the FEC=20 Flush function. If there are no more parity packets that can be=20 generated for this window, then return an error or else return a=20 parity packet that has already been generated. This uses one of a=20 set of codecs, specified through the use of codepoints. For TRACK,=20 it is expected that the codecs will operate over relatively small=20 windows, to work with real-time applications and congestion control. FEC Flush. For a window that needs a parity packet, but is not yet=20 full, FEC flush creates all-zero packets for the rest of the packets=20 in the window. No more calls to FEC input can be made for this=20 window after FEC flush has been called. FEC Decode. Given a set of received data and/or parity packets,=20 decode the window using the specified FEC codec. 5.2.2 FEC BB Parameters Codec Code Point Index. What is the codec being used for encoding=20 and decoding? This is a fixed parameter per data stream. FEC Window Size. What is the number of packets in an FEC window? =20 This is a fixed parameter per data stream. FEC Maximum Parity. This is the maximum number of parity packets=20 that can be generated over a given window size. This is a fixed=20 parameter per data stream. Data Packet Sequence Number. This is the sequence number of a data=20 packet. This is input to FEC Input from the PI. =20 FEC Window Offset. For a given packet, what is the offset in to an=20 FEC window? This is associated with each Data packet that uses FEC. =20 It is a header field on each Data packet sent. It is sequential=20 over each packet in a window, unless a Flush occurs on a partially=20 full window. In that case, the window offset of this last packet is=20 set to FEC Window Size=961. For parity packets, the FEC Window Offset=20 starts at FEC Window Size, and goes up to FEC Window Size + FEC=20 Maximum Parity=961. This is returned from FEC Input and from FEC=20 Create Parity. 5.3 Congestion Control BB TRACK uses a source-based rate regulation algorithm, with a single=20 rate provided to all the Receivers in the session. The following set of algorithms and parameters is a subset of those=20 needed for a full implementation, but give an idea of what is=20 required.=20 5.3.1 Congestion Control BB Algorithms Initialization. A number of transport-wide parameters must be fed=20 to each of the nodes in the group, such as minimum rate, maximum=20 rate, data segment size, etc. Receiver Measurements. The Receiver must keep track of its average=20 loss rate, and RTT to the Sender. We will call these measures=20 =93congestion reports=94. Receiver Feedback. The Receivers must feed these congestion back=20 to the Sender, piggybacked on both NACKs and ACKs. =20 Hierarchical Aggregation. Restricted worst edge aggregation should=20 be used to aggregate the congestion reports in the ACKs and/or NACKs=20 being fed up the tree [10]. Every time that an ACK or NACK is=20 generated, this algorithm should be called to fill in the=20 appropriate fields. Every time an ACK or NACK is received, this=20 algorithm should be called to process the congestion control fields=20 in the packet. This algorithm must also be notified every time a=20 new child joins or leaves at a Repair Head or Sender. Sender Rate Control. Based on the congestion reports received, the=20 Sender must change its sending rate. TCP Friendly Equation. Given values for RTT, DataSize, and=20 LossRate, this generates a target throughput rate according to a=20 modified version of the complex TCP model given in [11]. 5.3.2 Congestion Control BB Parameters Initialization Parameters. A set of different options, some of=20 which can be permanent constants, but others are selected by either=20 the Sender or a network manager. =20 Lost Packet. Every time a packet is detected as lost, the Senders=20 must be notified of this. RTT Measurement. Every time a RTT measurement is generated, either=20 between Sender and Receiver(s), or between one level of the tree and=20 another, the CC BB must be notified. Highest Allowed Sequence Number (HASN). This is used to implement=20 =93receiver-driven=94 window control [13]. Each receiver can keep track=20 of a congestion window and compute the HASN to be included in each=20 ACK. A Repair Head aggregates the HASNs by computing the minimum=20 value from all its children and forwards that as its own HASN up the=20 tree. 5.4 Generic Router Assist BB The task of designing scaleable RM protocols can be made easier by=20 the presence of some specific support in routers. In some=20 application- specific cases, the increased benefits afforded by the=20 addition of special router support can justify the resulting=20 additional complexity and expense. Functional components which can take advantage of router support=20 include feedback aggregation/suppression (both for loss notification=20 and congestion control) and constrained retransmission of repair=20 packets. =20 The process of designing and deploying these mechanisms inside=20 routers can be much slower than the one required for end-host=20 protocol mechanisms. Therefore, it would be highly advantageous to=20 define these mechanisms in a generic way that multiple protocols can=20 use if it is available, but do not necessarily need to depend on. This component has two halves, a signaling protocol and actual=20 router algorithms. The signaling protocol allows the transport=20 protocol to request from the router the functions that it wishes to=20 perform, and the router algorithms actually perform these functions.=20 An important component of the signaling protocol is some level of=20 commonality between the packet headers of multiple protocols, which=20 allows the router to recognize and interpret the headers. This is=20 covered in the section on common packet headers, below. 5.4.1 GRA BB Algorithms NACK Suppression. NACKs are sent towards the parent Repair Head or=20 Sender, with a Router Alert option on. GRA enabled routers detect=20 these packets and suppress redundant NACKs. It then updates a soft=20 state table so that it knows to retransmit the requested packet to=20 the requesting children, using Dynamic Selective Retransmission. The=20 NACK suppression algorithm needs to work with both ACKs and NACKs,=20 in order for Dynamic Selective Retransmission to work with TRACK. =20 This means that GRA can not suppress ACKs but must still use them to=20 update its state for retransmissions. It also means that GRA must=20 work with ACK and NACK selective bitmaps, not just NACKs that=20 request a single packet. Dynamic Selective Retransmission. When a retransmission occurs, it=20 is only forwarded to the interfaces of each router that have=20 signaled through the use of NACKs that they need to see that packet. Nearest Repair Head Hint. The router is made aware of the nearest=20 Repair Heads, and is able to tell a child which is the best=20 candidate for it to use. This must only be used as a hint to=20 children. Fine Grained Loss Reports. A major limitation of TFMCC is its=20 limitation of only getting 1-bit loss reports (i.e. a packet is=20 lost, or it is not) from the routers. A 8 or 16 bit report,=20 piggybacked on to data packets, with the cumulative loss detected=20 across all interfaces of GRA enabled routers the data packet=20 crossed, would allow TRACK to become much more responsive to changes=20 in network conditions. These reports can only be used as hints. Signaling Protocol. The functions for GRA need to be requested by=20 the protocol ahead of time, and then the run time packet headers=20 need to be decipherable by the router. =20 5.4.2 GRA BB Parameters GRA Enabled. Is GRA enabled in any of the routers in the network? =20 Which functions do the deployed version of GRA support? Packet Format. Which type of packet format is GRA to operate over? =20 It is likely that different protocol instantiations will require=20 differences in the packet headers they send to the router. This is=20 tied to the common packet header BB, below. 5.5 Automatic Tree Configuration BB TRACK takes advantage of hierarchical Repair Heads, to greatly=20 increase the theoretical scalability of the protocol. These Repair=20 Heads are used to form a tree with the source at the root, the=20 Receivers at the leaves of the tree, and the Repair Heads in the=20 middle. The Repair Heads can either be dedicated server software=20 for this task, or they may be application nodes that are performing=20 dual duty. The effectiveness of these agents to assist in the delivery of data=20 is highly dependent upon how well the logical tree they use to=20 communicate matches the underlying routing topology. The purpose of=20 this building block is to construct and manage the logical tree=20 connecting the agents. Ideally, this building block will perform=20 these functions in a manner that adapts to changes in session=20 membership, routing topology, and network availability. 5.5.1 Auto Tree BB Algorithms These are discussed in section 3.3. They are not yet mature enough=20 to break down in to component parts. 5.5.2 Auto Tree BB Parameters These are discussed in section 3.3. The algorithms are not yet=20 mature enough to break down in to the parameters needed. 5.6 Security As specified in [12], the primary security requirement for a TRACK=20 protocol is protection of the transport infrastructure. This is=20 accomplished through the use of lightweight group authentication of=20 the control and, optionally, the data packets sent to the group. =20 These algorithms use IPsec and shared symmetric keys. For TRACK,=20 [12] recommends that there be one shared key for the Data Session=20 and one for each Local Control Channel. These keys are distributed=20 through a separate key manager component, which may be either=20 centralized or distributed. Each member of the group is responsible=20 for contacting the key manager, establishing a pair-wise security=20 association with the key manager, and obtaining the appropriate=20 keys. The TRACK protocol then provides options for piggy-backing=20 key update messages on the Data Session and each Local Control=20 Channel of the protocol. These can either include a new shared=20 group key (encrypted with the old group key) or a notification that=20 the group key(s) are being changed and that the group members should=20 contact the key manager to get the new key(s). The former typically=20 occurs on a periodic basis, while the latter may occur when a group=20 member leaves. The exact algorithms for this BB is presently the subject of=20 research within the IRTF Secure Multicast Group (SMuG). Solutions=20 for these requirements will be standardized within the IETF when=20 ready. 5.7 Common Headers BB As pointed out in the generic router support section, it is=20 important to have some level of commonality across packet headers. =20 It may also be useful to have common data header formats for other=20 reasons. This building block consists of recommendations on fields=20 in their packet headers that protocols should make common across=20 themselves. TRACK needs to implement these recommendations in the=20 TRACK PI. 5.7.1 Common Header BB Fields GRA Signaling. The Retransmission, NACK and ACK packet headers need=20 to provide a means for signaling their existence to GRA. For NACK=20 and ACK headers, the selective bitmap needs to be specified in a=20 common way across all protocols so that the GRA component can=20 interpret these fields and determine the sequence numbers of the=20 packets that are being requested. For the Retransmission packets,=20 the sequence number of the packet needs to be in a standard position=20 so that GRA can interpret it. For both NACK, ACK and Retransmission=20 packets, the Session ID needs to be specified in a standard way=20 across protocols. Data Packets. The identification of data packets within a stream=20 should be common across all protocols, both to aid in commonality of=20 application semantics across protocols and to aid in GRA signaling.=20 A Data Packet is identified by three fields: the Session ID, the=20 Sequence Number, and the FEC Window Offset. The Session ID may=20 include the multicast address and/or a unique ID. The sequence=20 number starts at 1 and increments with each Data packet sent in the=20 Session. Sequence numbers are always sequentially generated,=20 without gaps. The FEC Window Offset specifies the offset of a Data=20 packet in to an FEC window. For a window of W generated packets, a=20 maximum window size of M, and a maximum parity size of P, the=20 packets are numbered as follows. The first W-1 packets are numbered=20 as 0 through W-2, with W never to exceed M. Packet W is always=20 numbered as M-1, so that Receivers and Repair Heads can detect a=20 partially filled window. The P parity packets are numbered M=20 through M+P-1. IP and UDP. It is easiest to implement protocols in the application=20 space using UDP packets, but eventual kernel implementations will=20 have TRACK implemented directly on top of IP. Other protocols share=20 this requirement, and the way that this transition is done should be=20 specified across all protocols. 6. Security Considerations 7. Open Issues 1. At various places in the document (e.g. Section 1, 3.5), different=20 flavors of reliability services are described. We need to define=20 them and describe how they are selected/configured. It seems=20 there are at least three flavors of reliability: ? ACK-to-sender (also known as pessimistic) ? ACK-to-RH (also known as optimistic) ? Time-bounded (useful for supporting real-time applications) It is argued that the pessimistic flavor should be optional (for=20 implementation) as it is less useful. Currently, Time-bounded is included in 4.11 as a kind of ordering=20 semantics, which does not seem appropriate. 2. Receivers talk to their parents with three kinds of messages:=20 ACKs, NACKs and heartbeatResponse. They can all be the same=20 message. The recipient of the message can always tell from the=20 packet content and recipient=92s local state the message=92s intent. 3. Control Tree. TreeId has been removed. It is not clear how to=20 refer to a subset of a control tree (a set of RHs bind with each=20 other, without a sender as a root) to be re-used/shared. Since=20 half of the Session Id is not controlled by TRACK, it seems that=20 they can be used to identify such sharable control (sub)trees when=20 appropriate. 4. It is suggested that a different type be used to distinguish=20 retransmission Data Packets from original Data Packets. The=20 ability to distinguish retransmission from the original packet=20 helps quickly determine if the packet came from the sender or a=20 Repair Head. 5. Section 4.1.8. Originally, there was a AcceptPending packet, used=20 to indicate that the Bind is successful pending further=20 confirmation. This has been removed in favor of using a Reject=20 with a reason code. The reason for this change is that the=20 AcceptPending approach leaves state at the RH that becomes=20 difficult to clean up. If not careful, it may be open to Denial- of-service attack. The simple reject and retry approach is=20 considered more robust. The change, however, has not been agreed=20 to by all authors, and becomes an open issue. 6. Section 4.1.8 and 4.10.2. The descriptions of how heartbeat and=20 heartbeatResponses are generated are lacking. There is a proposal=20 to allow heartbeat to contain mechanism to prompt for=20 heartbeatResponse. Such prompting can reduce the need for regular=20 heartbeatResponses from receivers. These algorithms need further=20 agreements. 7. Section 4.3 describes a 2-pass =93bottom-up=94 tree construction=20 algorithm. It has been suggested that if the Binding is done=20 =93top-down=94 there is no need for a 2-pass process and hence the=20 whole algorithm can be simpler. Furthermore, these algorithms=20 should be debated and worked out in the Tree Configuration BB. 8. TRACK depends on being able to configure a Control Tree. The Tree=20 Configuration BB must deliver some standard base-level mechanism,=20 even if completely static. Otherwise, some static configuration=20 mechanisms need to be specified in the TRACK PI. 9. Section 4.10.4 describes a mechanism for a receiver to find RH=20 information from its current RH, to serve as backup RHs. This is=20 really a requirement for the Tree Configuration BB to supply such=20 a mechanism. If one is not available from the Tree BB, then the=20 described mechanism would be used. 10. Need to add discussion of Late Join support 11. Need to add discussion of how session can gracefully close 12. In section 4.6, a number of other tactics for controlling ACK=20 and NACK traffic are possible, for instance, having receivers=20 stagger NACK production on different window boundaries. 13. Need to specify how RH determines the retransmission rate. 8. References 1 Bradner, S., "The Internet Standards Process -- Revision 3", BCP=20 9, RFC 2026, October 1996. 2 Whetten, B., et. al. =93Reliable Multicast Transport Building=20 Blocks for One-to-Many Bulk-Data Transfer.=94 Internet Draft,=20 draft-ietf-rmt-buildingblocks-02.txt, Work in Progress. 3 Handley, M., et. al. =93The Reliable Multicast Design Space for=20 Bulk Data Transfer.=94 Internet Draft, draft-ietf-rmt-design- space-01.txt, Work in Progress.=20 4 Bradner, S., "Key words for use in RFCs to Indicate Requirement=20 Levels", BCP 14, RFC 2119, March 1997 5 Whetten, B., Taskale, G. =93Overview of the Reliable Multicast=20 Transport Protocol II (RMTP-II).=94 IEEE Networking, Special Issue=20 on Multicast, February 2000. 6 Nonnenmacher, J., Biersack, E. "Reliable Multicast: Where to use Forward Error Correction", Proc. 5th. Workshop on=20 Protocols for High Speed Networks, Sophia Antipolis, France, Oct.=20 1996. 7 Nonnenmacher, J., et. al. "Parity-Based Loss Recovery for=20 Reliable Multicast Transmission", In Proc. of ACM SIGCOMM '97,=20 Cannes, France, September 1997. 8 Rizzo, L. "Effective erasure codes for reliable computer communications protocols", DEIT Technical Report LR-970115. 9 Nonnenmacher, J., Biersack, E. "Optimal Multicast Feedback",=20 Proc. IEEE INFOCOM 1998, March 1998. 10 Whetten, B., Conlan, J. =93A Rate Based Congestion Control Scheme=20 for Reliable Multicast=94, GlobalCast Communications Technical=20 White Paper, November 1998. http://www.talarian.com/rmtp-ii 11 Padhye, J., et. al. =93Modeling TCP Throughput: A Simple Model=20 and its Empirical Validation=94. University of Massachusetts=20 Technical Report CMPSCI TR 98-008. 12 Hardjorno, T., Whetten, B. =93Security Requirements for TRACK=20 Protocols.=94 Work in Progress. 13 Golestani, J., =93Fundamental Observations on Multicast Congestion=20 Control in the Internet=94, Bell Labs, Lucent Technology, paper=20 presented at the July 1998 RMRG meeting. 14 Kadansky, M., D. Chiu, J. Wesley, J. Provino, =93Tree-based=20 Reliable Multicast (TRAM)=94, draft-kadansky-tram-02.txt, Work in=20 Progress. 15 Whetten, B., M. Basavaiah, S. Paul, T. Montgomery, =93RMTP-II=20 Specification=94, draft-whetten-rmtp-ii-00.txt, April 8, 1998. Work=20 in Progress. 8. Acknowledgments Special thanks goes to the following individuals, who have=20 contributed to the design and review of this document. Supratik Bhattacharyya, Sprint Labs Miriam Kadansky, Sun Microsystems Seok Koh, ETRI Korea Joseph Wesley, Sun Microsystems 9. Author's Addresses Brian Whetten Talarian Corporation 333 Distel Circle Los Altos CA 94022 whetten@talarian.com Dah Ming Chiu Sun Microsystems Laboratories 1 Network Drive Burlington, MA 01803 dahming.chiu@sun.com Sanjoy Paul Edgix Corporation 130 W. 42nd Street, Suite 850 New York, NY 10036 sanjoy@edgix.com Full Copyright Statement Copyright (C) The Internet Society, 2000. All Rights Reserved. This=20 document and translations of it may be copied and furnished to=20 others, and derivative works that comment on or otherwise explain it=20 or assist in its implementation may be prepared, copied, published=20 and distributed, in whole or in part, without restriction of any=20 kind, provided that the above copyright notice and this paragraph=20 are included on all such copies and derivative works. However, this=20 document itself may not be modified in any way, such as by removing=20 the copyright notice or references to the Internet Society or other=20 Internet organizations, except as needed for the purpose of=20 developing Internet standards in which case the procedures for=20 copyrights defined in the Internet Standards process must be=20 followed, or as required to translate it into other languages. =09TRACK ARCHITECTURE=09March 2000 =20 B. Whetten=09Internet Draft =96 Expires September 2000=0925 =20 B. Whetten=09Internet Draft =96 Expires September 2000=091 --Brace_of_Greyhounds_614_000--