org.javagroups.stack
Class NakReceiverWindow

java.lang.Object
  extended byorg.javagroups.stack.NakReceiverWindow

public class NakReceiverWindow
extends java.lang.Object

Keeps track of messages according to their sequence numbers. Allows messages to be added out of order, and with gaps between sequence numbers. Method remove() removes the first message with a sequence number that is 1 higher than next_to_remove (this variable is then incremented), or it returns null if no message is present, or if no message's sequence number is 1 higher.

When there is a gap upon adding a message, its seqno will be added to the Retransmitter, which (using a timer) requests retransmissions of missing messages and keeps on trying until the message has been received, or the member who sent the message is suspected.

Started out as a copy of SlidingWindow. Main diff: RetransmitCommand is different, and retransmission thread is only created upon detection of a gap.

Change Nov 24 2000 (bela): for PBCAST, which has its own retransmission (via gossip), the retransmitter thread can be turned off

Change April 25 2001 (igeorg):
i. Restructuring: placed all nested class definitions at the top, then class static/non-static variables, then class private/public methods.
ii. Class and all nested classes are thread safe. Readers/writer lock added on NakReceiverWindow for finer grained locking.
iii. Internal or externally provided retransmission scheduler thread.
iv. Exponential backoff in time for retransmissions.

Author:
Bela Ban May 27 1999, John Georgiadis May 8 2001

Constructor Summary
NakReceiverWindow(Address sender, long start_seqno)
          Creates a new instance without a retransmission thread
NakReceiverWindow(Address sender, Retransmitter.RetransmitCommand cmd, long start_seqno)
          Creates a new instance with the given retransmit command
NakReceiverWindow(Address sender, Retransmitter.RetransmitCommand cmd, long start_seqno, TimeScheduler sched)
          Creates a new instance with the given retransmit command
 
Method Summary
 void add(long seqno, Message msg)
          Adds a message according to its sequence number (ordered).
 void destroy()
          Stop the retransmitter and reset the nak window
 long getHighestDelivered()
           
 long getHighestReceived()
          Returns the highest sequence number received so far (which may be higher than the highest seqno delivered so far, e.g.
 long getHighestSeen()
          Returns the highest deliverable seqno, e.g.
 long getLowestSeen()
           
 List getMessagesHigherThan(long seqno)
          Return messages that are higher than seqno (excluding seqno).
 List getMessagesInList(List missing_msgs)
          Return a list of all messages for which there is a seqno in missing_msgs.
 List getMessagesInRange(long lower, long upper)
          Return all messages m for which the following holds: m > lower && m <= upper (excluding lower, including upper).
 List getMissingMessages(long low, long high)
          Find all messages between 'low' and 'high' (including 'low' and 'high') that have a null msg.
 Message remove()
          Find the entry with seqno head.
 void reset()
          Reset the retransmitter and the nak window
 void setRetransmitTimeouts(long[] timeouts)
           
 int size()
           
 void stable(long seqno)
          Delete all messages <= seqno (they are stable, that is, have been received at all members).
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

NakReceiverWindow

public NakReceiverWindow(Address sender,
                         Retransmitter.RetransmitCommand cmd,
                         long start_seqno,
                         TimeScheduler sched)
Creates a new instance with the given retransmit command

Parameters:
sender - The sender associated with this instance
cmd - The command used to retransmit a missing message, will be invoked by the table. If null, the retransmit thread will not be started
start_seqno - The first sequence number to be received
sched - the external scheduler to use for retransmission requests of missing msgs. If it's not provided or is null, an internal one is created

NakReceiverWindow

public NakReceiverWindow(Address sender,
                         Retransmitter.RetransmitCommand cmd,
                         long start_seqno)
Creates a new instance with the given retransmit command

Parameters:
sender - The sender associated with this instance
cmd - The command used to retransmit a missing message, will be invoked by the table. If null, the retransmit thread will not be started
start_seqno - The first sequence number to be received

NakReceiverWindow

public NakReceiverWindow(Address sender,
                         long start_seqno)
Creates a new instance without a retransmission thread

Parameters:
sender - The sender associated with this instance
start_seqno - The first sequence number to be received
Method Detail

setRetransmitTimeouts

public void setRetransmitTimeouts(long[] timeouts)

add

public void add(long seqno,
                Message msg)
Adds a message according to its sequence number (ordered).

Variables head and tail mark the start and end of the messages received, but not delivered yet. When a message is received, if its seqno is smaller than head, it is discarded (already received). If it is bigger than tail, we advance tail and add empty elements. If it is between head and tail, we set the corresponding missing (or already present) element. If it is equal to tail, we advance the latter by 1 and add the message (default case).


remove

public Message remove()
Find the entry with seqno head. If e.msg is != null -> return it and increment head, else return null.

This method essentially shrinks the size of the sliding window by one


stable

public void stable(long seqno)
Delete all messages <= seqno (they are stable, that is, have been received at all members). Stop when a number > seqno is encountered (all messages are ordered on seqnos).


reset

public void reset()
Reset the retransmitter and the nak window


destroy

public void destroy()
Stop the retransmitter and reset the nak window


getHighestDelivered

public long getHighestDelivered()
Returns:
the highest sequence number of a message consumed by the application (by remove())

getLowestSeen

public long getLowestSeen()
Returns:
the lowest sequence number of a message that has been delivered or is a candidate for delivery (by the next call to remove())

getHighestSeen

public long getHighestSeen()
Returns the highest deliverable seqno, e.g. for 1,2,3,5,6 it would be 3.

See Also:
NakReceiverWindow#GetHighestReceived

getMissingMessages

public List getMissingMessages(long low,
                               long high)
Find all messages between 'low' and 'high' (including 'low' and 'high') that have a null msg. Return them as a list of integers

Returns:
List A list of integers, sorted in ascending order. E.g. [1, 4, 7, 8]

getHighestReceived

public long getHighestReceived()
Returns the highest sequence number received so far (which may be higher than the highest seqno delivered so far, e.g. for 1,2,3,5,6 it would be 6

See Also:
getHighestSeen()

getMessagesHigherThan

public List getMessagesHigherThan(long seqno)
Return messages that are higher than seqno (excluding seqno). Check both received and delivered messages.


getMessagesInRange

public List getMessagesInRange(long lower,
                               long upper)
Return all messages m for which the following holds: m > lower && m <= upper (excluding lower, including upper). Check both msgs and delivered_msgs.


getMessagesInList

public List getMessagesInList(List missing_msgs)
Return a list of all messages for which there is a seqno in missing_msgs. The seqnos of the argument list are supposed to be in ascending order


size

public int size()

toString

public java.lang.String toString()


Copyright © 2001,2002 www.javagroups.com . All Rights Reserved.