org.jgroups.stack

Class 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.

Authors:
Bela Ban May 27 1999, May 2004
John Georgiadis May 8 2001

Nested Class Summary

static interface
NakReceiverWindow.Listener

Field Summary

protected static Log
log

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
Message
get(long sequence_num)
Returns the message from received_msgs or delivered_msgs.
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., for 1,2,3,5,6 it would be 6.
long
getHighestSeen()
Returns the highest deliverable seqno; e.g., for 1,2,3,5,6 it would be 3.
long
getLowestSeen()
int
getMaxXmitBufSize()
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()
void
reset()
Reset the retransmitter and the nak window
void
setDiscardDeliveredMessages(boolean flag)
void
setListener(NakReceiverWindow.Listener l)
void
setMaxXmitBufSize(int max_xmit_buf_size)
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).
String
toString()

Field Details

log

protected static final Log log

Constructor Details

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

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,
                         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

Method Details

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).


destroy

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

get

public Message get(long sequence_num)
Returns the message from received_msgs or delivered_msgs.
Parameters:
sequence_num -
Returns:
Message from received_msgs or delivered_msgs.

getHighestDelivered

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

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.

getHighestSeen

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

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())

getMaxXmitBufSize

public int getMaxXmitBufSize()

getMessagesHigherThan

public List getMessagesHigherThan(long seqno)
Return messages that are higher than seqno (excluding seqno). Check both received and delivered messages.
Returns:
List. All messages that have a seqno greater than seqno

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
Parameters:
missing_msgs - A List of seqnos
Returns:
List

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 received_msgs and delivered_msgs.

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 longs
Returns:
List. A list of seqnos, sorted in ascending order. E.g. [1, 4, 7, 8]

remove

public Message remove()

reset

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

setDiscardDeliveredMessages

public void setDiscardDeliveredMessages(boolean flag)

setListener

public void setListener(NakReceiverWindow.Listener l)

setMaxXmitBufSize

public void setMaxXmitBufSize(int max_xmit_buf_size)

setRetransmitTimeouts

public void setRetransmitTimeouts(long[] timeouts)

size

public int size()

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).

toString

public String toString()

Copyright B) 1998-2005 Bela Ban. All Rights Reserved.