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.
NakReceiverWindow
public NakReceiverWindow(Address sender,
long start_seqno)
Creates a new instance without a retransmission thread
sender
- The sender associated with this instancestart_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
sender
- The sender associated with this instancecmd
- The command used to retransmit a missing message, will
be invoked by the table. If null, the retransmit thread will not be
startedstart_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
sender
- The sender associated with this instancecmd
- The command used to retransmit a missing message, will
be invoked by the table. If null, the retransmit thread will not be
startedstart_seqno
- The first sequence number to be receivedsched
- the external scheduler to use for retransmission
requests of missing msgs. If it's not provided or is null, an internal
one is created
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.
- Message from received_msgs or delivered_msgs.
getHighestDelivered
public long getHighestDelivered()
- 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()
- 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.
- 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
missing_msgs
- A List of seqnos
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
- List. A list of seqnos, sorted in ascending order.
E.g. [1, 4, 7, 8]
reset
public void reset()
Reset the retransmitter and the nak window
setDiscardDeliveredMessages
public void setDiscardDeliveredMessages(boolean flag)
setMaxXmitBufSize
public void setMaxXmitBufSize(int max_xmit_buf_size)
setRetransmitTimeouts
public void setRetransmitTimeouts(long[] timeouts)
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()