org.jgroups.stack

Class NakReceiverWindow

public class NakReceiverWindow extends 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, May 2004 John Georgiadis May 8 2001

Nested Class Summary
interfaceNakReceiverWindow.Listener
Field Summary
protected static Loglog
Constructor Summary
NakReceiverWindow(Address sender, Retransmitter.RetransmitCommand cmd, long start_seqno, TimeScheduler sched)
Creates a new instance with the given retransmit command
NakReceiverWindow(Address sender, Retransmitter.RetransmitCommand cmd, long start_seqno)
Creates a new instance with the given retransmit command
NakReceiverWindow(Address sender, long start_seqno)
Creates a new instance without a retransmission thread
Method Summary
voidadd(long seqno, Message msg)
Adds a message according to its sequence number (ordered).
voiddestroy()
Stop the retransmitter and reset the nak window
Messageget(long sequence_num)
Returns the message from received_msgs or delivered_msgs.
longgetHighestDelivered()
longgetHighestReceived()
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.
longgetHighestSeen()
Returns the highest deliverable seqno; e.g., for 1,2,3,5,6 it would be 3.
longgetLowestSeen()
intgetMaxXmitBufSize()
ListgetMessagesHigherThan(long seqno)
Return messages that are higher than seqno (excluding seqno).
ListgetMessagesInList(List missing_msgs)
Return a list of all messages for which there is a seqno in missing_msgs.
ListgetMessagesInRange(long lower, long upper)
Return all messages m for which the following holds: m > lower && m <= upper (excluding lower, including upper).
ListgetMissingMessages(long low, long high)
Find all messages between 'low' and 'high' (including 'low' and 'high') that have a null msg.
Messageremove()
voidreset()
Reset the retransmitter and the nak window
voidsetDiscardDeliveredMessages(boolean flag)
voidsetListener(NakReceiverWindow.Listener l)
voidsetMaxXmitBufSize(int max_xmit_buf_size)
voidsetRetransmitTimeouts(long[] timeouts)
intsize()
voidstable(long seqno)
Delete all messages <= seqno (they are stable, that is, have been received at all members).
StringtoString()

Field Detail

log

protected static final Log log

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

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.

See Also: NakReceiverWindow

getHighestSeen

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

See Also: NakReceiverWindow

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 ? 1998-2005 Bela Ban. All Rights Reserved.