Subject: ACK Building Block

From: Dah Ming Chiu - Sun Microsystems <[email-masked]>
Date: Wed, 12 Jan 2000 15:49:57 -0500 (EST)

Over a month ago, I wrote a short proposal to develop an ACK building
block, and circulated it to a small set of people in RMT for comment.
So far, only Brian Whetten and I have been discussing it; and we have
some different opinions. Since there may be others on the RMT list who
are interested in the (Tree-based) ACK approach, I would like to move
the discussion here.

Attached is a sketch of an ACK BB (Building Block). I have not updated
it since I wrote it a month ago.  It describes the relationship
between a receiver and its repair head (repair node), and some basic
session management functions of the sender, all in terms of an abstract
API.  I have also sketched out some algorithms that need to be specified
(such as deciding when to ack and request ack), and some hooks to other
BB's (e.g. congestion control, tree-building). Most importantly, this
is all quite simple.

I hope this is useful for helping us build the TRACK protocol standards
as we move ahead.  Comments are welcome.

Dah Ming Chiu
      ACK-based reliable multicast service building block (ACK BB)
      ------------------------------------------------------------

The ACK-based reliable multicast building block abstracts out the basic
interface and algorithms used by an ACK-based reliable multicast transport,
and described how it interacts with other building blocks such as the
use (and building) of a repair tree, congestion/flow control, security
and group management.

The following is a rough sketch of the ACK BB, including definitions of
an abstract API, a number of algorithms, and descriptions of "hooks" used
for integrating with other building blocks.

1) Abstract API

1.1) Definition of some primitive datatypes used to describe the abstract API.
 
     session: 
	This is possibly identified by the following -
	        session id
	        multicast address
	        [sender address]	
	
     member: 
	This identifies a receiver using its address and port

     head:   
	This identifies a repair head using its address and port

1.2) APIs for member to repair head interaction: 

    BindToRepairHead(session, head, scope, [role], [subtree])

      This function is used by a member to request repair service from a
      repair head.  The parameter scope includes ttl and/or administrative
      scoping information, used by a repair head to perform localized repair.
      The optional parameters [role] and [subtree] provide other information
      about the receiver.  Role says if the receiver can or cannot become
      head; subtree indicates if the receiver is itself a repair head,
      and information about its dependents.
    
    Ack(session, head, ack_info)

      This function is used to send an acknowledgement to a repair head.
      The parameter ack_info is a suitable data structure - for example 
      can contain an ascending list of sequence numbers; the first
      element  of the list signifying the highest sequence number of 
      consecutively received packets, etc.
    
    Unbind(session, head, reason)

      This function is used to tell the current repair head that its services
      are no longer needed.

1.3) APIs for repair head to member interaction:

    AcceptMember(session, member, available_packets, [repair_addr], [level])

      This function is used to respond to a BindToRepairHead request.
      The parameter available_packets a suitable data structure for example
      containing a descending list of sequence numbers; the first element of
      the list signifying the beginning of a consecutive packet stream this
      repair head is prepared to repair.  Optionally, a separate multicast
      address can be suggested for members to listen for (multicast) repairs.
      The optional parameter [level] is used (when there is a repair tree) to
      indicate the number of other repair heads this repair head depends on.
    
    RejectMember(session, member, reason)

      This function is used to reject a membership request via 
      BindToRepairHead.
    
    RequestAck(session, memberlist, seqno)

      This function is used to request the members in memberlist to ack.
      The parameter seqno contains the newest sequence number the repair
      head has seen.
      
    RequestFinalAck(session, memberlist, seqno)

      This function is used to request the members in memberlist to ack
      the receipt of all packets up to seqno (inclusive), which is the
      last packet of the session.  The repair head cannot exit until it
      has fulfilled it obligation to see all members have received the last
      packet of the session.
    
    SendRepair(session, [member], seqno)

      This function is used to send a repair message.  If a member parameter
      is included, then the repair head sends a unicast repair message (seqno)
      to this member; else the repair message (seqno) is sent to all members
      served by this repair head.

    Terminate(session, member, reason)

      This function is used by the head to terminate a member.  Reasons
      for termination could be the member is not able to following the
      minimum data rate configured for the session, and/or causing the
      repair head to fill up its cache.

    Resign(session, reason)
    
      This function is used by the head to resign.  It provides a way
      for its members to gracefully find other repair heads more
      quickly (than if the repair head crashed).
    
1.4) APIs for sender to group interaction:

    SessionStart(session)

      This function is used by the sender to send a multicast message to the
      whole group to indicate a multicast session is about to begin.
    
    SenderStatus(session, status)

      This function is used by the sender to tell the whole multicast group
      that it is still alive and optionally the sequence number of messages
      it has sent thus far.  This is typically done when there is a (time)
      gap in the data packet stream.
    
    SessionEnd(session, seqno)

      This function is used by the sender to tell the whole multicast group
      that it has sent out the last packet (seqno).  This is an optimization
      to help the whole group to recognize the end of the session.

2) Algorithms

   The following algorithms describe when the above functions are used (only
   the cases where it is s not obvious).  In the process, we discuss a 
   number of (configurable) parameters and some internal states of the receiver 
   and repair heads.

2.1) When to ack

   Three events may trigger a receiver to send an ack:
      ack window
      ack timer
      probe

   The normal event is the ack window.  Ack window is a configured parameter.
   (Note, in some implementations, this may be a dynamic parameter tied to
   the congestion window).  For example, a receiver may be configured to send 
   an ack once every 32 packets.  If the packet stream is continuous and under
   normal operation conditions, this may be the only mechanism used to 
   schedule sending of acks.

   The ack timer is also a configured parameter.  (Note again, in some
   implementations this may be a dynamically adjusted parameter based on
   prediction of expected inter-packet arrival times).  This mechanism is
   typically triggered when losses occur, or when application data has a
   (time) gap in it.

   The receiver also sends an ack in response to various probes from the repair
   head or the sender.  For example, the RequestAck, RequestFinalAck, 
   SessionEnd and RTT computation functions may all trigger a receiver to 
   send an ack. 

2.2) When to request ack

   When a repair head detects that a member has not sent an ack for some
   interval of time, it requests those members to respond with an ack. This
   time is similar to the ack timer discussed above. Request for ack can be 
   a unicast message (when only one member is being polled) or a multicast 
   message when multiple members are being polled. The addresses of the 
   multiple members can be listed in the request message. This enables the 
   repair heads to disown unresponsive members and reclaim buffers. 
   Request for ack can also be used to compute RTT between a repair head
   and its member. 

2.3) Cache management
   
   Depends on the type of late join support and the type of reliability
   being supported.
 
2.4) Repair algorithm

   When some member indicates missing packets, the repair head calls the 
   SendRepair function to queue repairs to the retransmission queue.  It is 
   often the case that multiple members request the same repair.  The 
   implementation of SendRepair must carefully avoid queueing a repair packet
   that is already in the queue, or sending a repair that has very recently 
   been sent.
   
   The repair head also decides when to send an ack via unicast and when
   to use multicast to minimize bandwidth usage.
   
2.5) Session close

   The algorithm to close the session is for the sender to call sessionEnd().
   This results in a multicast message being transmitted to the whole group
   indicating end of session.  Each repair head, separately requests all
   members in its repair group to send an ack of the final packet.  In
   case the session end message from the sender is not received by a
   repair head, it may be sent multiple times.  Failing that, the session
   end signal still would propagate down the tree via each repair head
   requesting the final ack.

3) Other Hooks

   The hooks describe additional ways (other than the abstract API) this
   building block interacts with other building blocks and a protocol
   instantiation.

3.1) Hooks exported

3.1.1) Missing packet info

   Other BB's may need to query this BB for the total number of lost packet 
   seen and repaired up to now.  This information may prove useful for
   congestion control, for example in calculating the suitable rate for
   transmission; or in determining which member is keeping the group
   transmission rate below the minimum data rate.  

   Similarly, there should be a hook for zeroing the above states to
   accommodate the need to restart certain calculations (for example - 
   when the sender resumes data transmission after a pause).

3.1.2) Cache info

   Other BB may be interested in the cache occupancy, or available packets
   in the cache.

3.1.3) ackWindow

3.2) Hooks expected from other BB's

3.2.1) Current Data rate

   This information probably comes from the congestion control BB.  It
   may be useful for dynamically setting some timers used to send (or
   request) acks.

3.2.2) Keep alive function

   The repair head and its member need a keep-alive function which runs in the
   absence of repairs.  If this is covered in the tree-building BB, then the
   hooks are needed by this BB to access it.

3.2.3) Repair scope

   The TREE BB may provide a repair scope for controlling the locality of
   repairs.  The repair scope infomation is needed by this BB too.

3.2.4) Security hook

   Security hooks are needed to perform signature/authentication operations
   on all BB(protocol) control messages. 

4) Issues

   Some functions in this BB overlap with functions in the tree configuration
   BB.  For example, the Bind/Unbind, Accept/Reject would be used during tree
   building as well.  On the other hand, a receiver and head need some
   keep-alive function that we did not specify here now (perhaps we should
   have), and expected it be part of the tree maintenance function in the
   tree BB.

---

From: "Seok J. Koh" <[email-masked]>
Date: Fri, 28 Jan 2000 17:48:57 +0900

Hi, there,

The proposal seems to be one of reasonable inputs for initial draft of ACK building block,
even though some addings or modifications are required.
For examples, the scope of ACK building block can be explictly described, and 
some assumptions, including that the tree is given by automatic configurations
or can be obtained from external software, may be made.

Anyway, I cannot find the item of ACK building block as the drafting work,
in the plan of this Mid-Feb RMT meeting.
I would like to know why the drafting work of ACK building block has not
been inlcuded as a drafting item at the meeting,
in spite that NACK and GRA BBs were included. 

Is that item pre-mature yet ? 
or overlapped by the other BBs such as tree building or TRACK ?

cheers,

Seok-Joo, Koh