A Discrete-Event Network Simulator
API
tcp-rx-buffer.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2010 Adrian Sai-wah Tam
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Adrian Sai-wah Tam <adrian.sw.tam@gmail.com>
19  */
20 
21 #include "ns3/packet.h"
22 #include "ns3/log.h"
23 #include "tcp-rx-buffer.h"
24 
25 namespace ns3 {
26 
27 NS_LOG_COMPONENT_DEFINE ("TcpRxBuffer");
28 
29 NS_OBJECT_ENSURE_REGISTERED (TcpRxBuffer);
30 
31 TypeId
33 {
34  static TypeId tid = TypeId ("ns3::TcpRxBuffer")
35  .SetParent<Object> ()
36  .SetGroupName ("Internet")
37  .AddConstructor<TcpRxBuffer> ()
38  .AddTraceSource ("NextRxSequence",
39  "Next sequence number expected (RCV.NXT)",
41  "ns3::SequenceNumber32TracedValueCallback")
42  ;
43  return tid;
44 }
45 
46 /* A user is supposed to create a TcpSocket through a factory. In TcpSocket,
47  * there are attributes SndBufSize and RcvBufSize to control the default Tx and
48  * Rx window sizes respectively, with default of 128 KiByte. The attribute
49  * RcvBufSize is passed to TcpRxBuffer by TcpSocketBase::SetRcvBufSize() and in
50  * turn, TcpRxBuffer:SetMaxBufferSize(). Therefore, the m_maxBuffer value
51  * initialized below is insignificant.
52  */
54  : m_nextRxSeq (n), m_gotFin (false), m_size (0), m_maxBuffer (32768), m_availBytes (0)
55 {
56 }
57 
59 {
60 }
61 
64 {
65  return m_nextRxSeq;
66 }
67 
68 void
70 {
71  m_nextRxSeq = s;
72 }
73 
76 {
77  return m_maxBuffer;
78 }
79 
80 void
82 {
83  m_maxBuffer = s;
84 }
85 
87 TcpRxBuffer::Size (void) const
88 {
89  return m_size;
90 }
91 
94 {
95  return m_availBytes;
96 }
97 
98 void
100 {
101  NS_LOG_FUNCTION (this);
102  // Increment nextRxSeq is valid only if we don't have any data buffered,
103  // this is supposed to be called only during the three-way handshake
104  NS_ASSERT (m_size == 0);
105  m_nextRxSeq++;
106 }
107 
108 // Return the lowest sequence number that this TcpRxBuffer cannot accept
111 {
112  if (m_gotFin)
113  { // No data allowed beyond FIN
114  return m_finSeq;
115  }
116  else if (m_data.size () && m_nextRxSeq > m_data.begin ()->first)
117  { // No data allowed beyond Rx window allowed
118  return m_data.begin ()->first + SequenceNumber32 (m_maxBuffer);
119  }
121 }
122 
123 void
125 {
126  NS_LOG_FUNCTION (this);
127 
128  m_gotFin = true;
129  m_finSeq = s;
130  if (m_nextRxSeq == m_finSeq) ++m_nextRxSeq;
131 }
132 
133 bool
135 {
136  return (m_gotFin && m_finSeq < m_nextRxSeq);
137 }
138 
139 bool
141 {
142  NS_LOG_FUNCTION (this << p << tcph);
143 
144  uint32_t pktSize = p->GetSize ();
145  SequenceNumber32 headSeq = tcph.GetSequenceNumber ();
146  SequenceNumber32 tailSeq = headSeq + SequenceNumber32 (pktSize);
147  NS_LOG_LOGIC ("Add pkt " << p << " len=" << pktSize << " seq=" << headSeq
148  << ", when NextRxSeq=" << m_nextRxSeq << ", buffsize=" << m_size);
149 
150  // Trim packet to fit Rx window specification
151  if (headSeq < m_nextRxSeq) headSeq = m_nextRxSeq;
152  if (m_data.size ())
153  {
154  SequenceNumber32 maxSeq = m_data.begin ()->first + SequenceNumber32 (m_maxBuffer);
155  if (maxSeq < tailSeq) tailSeq = maxSeq;
156  if (tailSeq < headSeq) headSeq = tailSeq;
157  }
158  // Remove overlapped bytes from packet
159  BufIterator i = m_data.begin ();
160  while (i != m_data.end () && i->first <= tailSeq)
161  {
162  SequenceNumber32 lastByteSeq = i->first + SequenceNumber32 (i->second->GetSize ());
163  if (lastByteSeq > headSeq)
164  {
165  if (i->first > headSeq && lastByteSeq < tailSeq)
166  { // Rare case: Existing packet is embedded fully in the new packet
167  m_size -= i->second->GetSize ();
168  m_data.erase (i++);
169  continue;
170  }
171  if (i->first <= headSeq)
172  { // Incoming head is overlapped
173  headSeq = lastByteSeq;
174  }
175  if (lastByteSeq >= tailSeq)
176  { // Incoming tail is overlapped
177  tailSeq = i->first;
178  }
179  }
180  ++i;
181  }
182  // We now know how much we are going to store, trim the packet
183  if (headSeq >= tailSeq)
184  {
185  NS_LOG_LOGIC ("Nothing to buffer");
186  return false; // Nothing to buffer anyway
187  }
188  else
189  {
190  uint32_t start = static_cast<uint32_t> (headSeq - tcph.GetSequenceNumber ());
191  uint32_t length = static_cast<uint32_t> (tailSeq - headSeq);
192  p = p->CreateFragment (start, length);
193  NS_ASSERT (length == p->GetSize ());
194  }
195  // Insert packet into buffer
196  NS_ASSERT (m_data.find (headSeq) == m_data.end ()); // Shouldn't be there yet
197  m_data [ headSeq ] = p;
198 
199  if (headSeq > m_nextRxSeq)
200  {
201  // Generate a new SACK block
202  UpdateSackList (headSeq, tailSeq);
203  }
204 
205  NS_LOG_LOGIC ("Buffered packet of seqno=" << headSeq << " len=" << p->GetSize ());
206  // Update variables
207  m_size += p->GetSize (); // Occupancy
208  for (i = m_data.begin (); i != m_data.end (); ++i)
209  {
210  if (i->first < m_nextRxSeq)
211  {
212  continue;
213  }
214  else if (i->first > m_nextRxSeq)
215  {
216  break;
217  };
218  m_nextRxSeq = i->first + SequenceNumber32 (i->second->GetSize ());
219  m_availBytes += i->second->GetSize ();
221  }
222  NS_LOG_LOGIC ("Updated buffer occupancy=" << m_size << " nextRxSeq=" << m_nextRxSeq);
223  if (m_gotFin && m_nextRxSeq == m_finSeq)
224  { // Account for the FIN packet
225  ++m_nextRxSeq;
226  };
227  return true;
228 }
229 
230 uint32_t
232 {
233  NS_LOG_FUNCTION (this);
234 
235  return static_cast<uint32_t> (m_sackList.size ());
236 }
237 
238 void
240 {
241  NS_LOG_FUNCTION (this << head << tail);
242  NS_ASSERT (head > m_nextRxSeq);
243 
244  TcpOptionSack::SackBlock current;
245  current.first = head;
246  current.second = tail;
247 
248  // The block "current" has been safely stored. Now we need to build the SACK
249  // list, to be advertised. From RFC 2018:
250  // (a) The first SACK block (i.e., the one immediately following the
251  // kind and length fields in the option) MUST specify the contiguous
252  // block of data containing the segment which triggered this ACK,
253  // unless that segment advanced the Acknowledgment Number field in
254  // the header. This assures that the ACK with the SACK option
255  // reflects the most recent change in the data receiver's buffer
256  // queue.
257  //
258  // (b) The data receiver SHOULD include as many distinct SACK blocks as
259  // possible in the SACK option. Note that the maximum available
260  // option space may not be sufficient to report all blocks present in
261  // the receiver's queue.
262  //
263  // (c) The SACK option SHOULD be filled out by repeating the most
264  // recently reported SACK blocks (based on first SACK blocks in
265  // previous SACK options) that are not subsets of a SACK block
266  // already included in the SACK option being constructed. This
267  // assures that in normal operation, any segment remaining part of a
268  // non-contiguous block of data held by the data receiver is reported
269  // in at least three successive SACK options, even for large-window
270  // TCP implementations [RFC1323]). After the first SACK block, the
271  // following SACK blocks in the SACK option may be listed in
272  // arbitrary order.
273 
274  m_sackList.push_front (current);
275 
276  // We have inserted the block at the beginning of the list. Now, we should
277  // check if any existing blocks overlap with that.
278  bool updated = false;
279  TcpOptionSack::SackList::iterator it = m_sackList.begin ();
280  TcpOptionSack::SackBlock begin = *it;
282  ++it;
283 
284  // Iterates until we examined all blocks in the list (maximum 4)
285  while (it != m_sackList.end ())
286  {
287  current = *it;
288 
289  // This is a left merge:
290  // [current_first; current_second] [beg_first; beg_second]
291  if (begin.first == current.second)
292  {
293  NS_ASSERT (current.first < begin.second);
294  merged = TcpOptionSack::SackBlock (current.first, begin.second);
295  updated = true;
296  }
297  // while this is a right merge
298  // [begin_first; begin_second] [current_first; current_second]
299  else if (begin.second == current.first)
300  {
301  NS_ASSERT (begin.first < current.second);
302  merged = TcpOptionSack::SackBlock (begin.first, current.second);
303  updated = true;
304  }
305 
306  // If we have merged the blocks (and the result is in merged) we should
307  // delete the current block (it), the first block, and insert the merged
308  // one at the beginning.
309  if (updated)
310  {
311  m_sackList.erase (it);
312  m_sackList.pop_front ();
313  m_sackList.push_front (merged);
314  it = m_sackList.begin ();
315  begin = *it;
316  updated = false;
317  }
318 
319  ++it;
320  }
321 
322  // Since the maximum blocks that fits into a TCP header are 4, there's no
323  // point on maintaining the others.
324  if (m_sackList.size () > 4)
325  {
326  m_sackList.pop_back ();
327  }
328 
329  // Please note that, if a block b is discarded and then a block contiguous
330  // to b is received, only that new block (without the b part) is reported.
331  // This is perfectly fine for the RFC point (a), given that we do not report any
332  // overlapping blocks shortly after.
333 }
334 
335 void
337 {
338  NS_LOG_FUNCTION (this << seq);
339 
340  TcpOptionSack::SackList::iterator it;
341  for (it = m_sackList.begin (); it != m_sackList.end (); )
342  {
343  TcpOptionSack::SackBlock block = *it;
344  NS_ASSERT (block.first < block.second);
345 
346  if (block.second <= seq)
347  {
348  it = m_sackList.erase (it);
349  }
350  else
351  {
352  it++;
353  }
354  }
355 }
356 
359 {
360  return m_sackList;
361 }
362 
365 {
366  NS_LOG_FUNCTION (this << maxSize);
367 
368  uint32_t extractSize = std::min (maxSize, m_availBytes);
369  NS_LOG_LOGIC ("Requested to extract " << extractSize << " bytes from TcpRxBuffer of size=" << m_size);
370  if (extractSize == 0) return nullptr; // No contiguous block to return
371  NS_ASSERT (m_data.size ()); // At least we have something to extract
372  Ptr<Packet> outPkt = Create<Packet> (); // The packet that contains all the data to return
373  BufIterator i;
374  while (extractSize)
375  { // Check the buffered data for delivery
376  i = m_data.begin ();
377  NS_ASSERT (i->first <= m_nextRxSeq); // in-sequence data expected
378  // Check if we send the whole pkt or just a partial
379  uint32_t pktSize = i->second->GetSize ();
380  if (pktSize <= extractSize)
381  { // Whole packet is extracted
382  outPkt->AddAtEnd (i->second);
383  m_data.erase (i);
384  m_size -= pktSize;
386  extractSize -= pktSize;
387  }
388  else
389  { // Partial is extracted and done
390  outPkt->AddAtEnd (i->second->CreateFragment (0, extractSize));
391  m_data[i->first + SequenceNumber32 (extractSize)] = i->second->CreateFragment (extractSize, pktSize - extractSize);
392  m_data.erase (i);
393  m_size -= extractSize;
394  m_availBytes -= extractSize;
395  extractSize = 0;
396  }
397  }
398  if (outPkt->GetSize () == 0)
399  {
400  NS_LOG_LOGIC ("Nothing extracted.");
401  return nullptr;
402  }
403  NS_LOG_LOGIC ("Extracted " << outPkt->GetSize ( ) << " bytes, bufsize=" << m_size
404  << ", num pkts in buffer=" << m_data.size ());
405  return outPkt;
406 }
407 
408 } //namespace ns3
ns3::TypeId
a unique identifier for an interface.
Definition: type-id.h:59
NS_LOG_COMPONENT_DEFINE
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
NS_OBJECT_ENSURE_REGISTERED
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
NS_ASSERT
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:67
ns3::TcpRxBuffer::IncNextRxSequence
void IncNextRxSequence(void)
Increment the Next Sequence number.
Definition: tcp-rx-buffer.cc:99
ns3::TcpRxBuffer::ClearSackList
void ClearSackList(const SequenceNumber32 &seq)
Remove old blocks from the sack list.
Definition: tcp-rx-buffer.cc:336
min
#define min(a, b)
Definition: 80211b.c:42
ns3::TcpRxBuffer::m_gotFin
bool m_gotFin
Did I received FIN packet?
Definition: tcp-rx-buffer.h:224
ns3::TcpRxBuffer::UpdateSackList
void UpdateSackList(const SequenceNumber32 &head, const SequenceNumber32 &tail)
Update the sack list, with the block seq starting at the beginning.
Definition: tcp-rx-buffer.cc:239
ns3::Packet::GetSize
uint32_t GetSize(void) const
Returns the the size in bytes of the packet (including the zero-filled initial payload).
Definition: packet.h:852
ns3::Packet::CreateFragment
Ptr< Packet > CreateFragment(uint32_t start, uint32_t length) const
Create a new packet which contains a fragment of the original packet.
Definition: packet.cc:227
ns3::TcpRxBuffer::Size
uint32_t Size(void) const
Get the actual buffer occupancy.
Definition: tcp-rx-buffer.cc:87
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::TcpRxBuffer::MaxRxSequence
SequenceNumber32 MaxRxSequence(void) const
Get the lowest sequence number that this TcpRxBuffer cannot accept.
Definition: tcp-rx-buffer.cc:110
ns3::TcpRxBuffer::GetSackListSize
uint32_t GetSackListSize() const
Get the size of Sack list.
Definition: tcp-rx-buffer.cc:231
ns3::TcpRxBuffer::m_finSeq
SequenceNumber32 m_finSeq
Seqnum of the FIN packet.
Definition: tcp-rx-buffer.h:223
ns3::TcpRxBuffer::NextRxSequence
SequenceNumber32 NextRxSequence(void) const
Get Next Rx Sequence number.
Definition: tcp-rx-buffer.cc:63
ns3::TcpRxBuffer::GetTypeId
static TypeId GetTypeId(void)
Get the type ID.
Definition: tcp-rx-buffer.cc:32
ns3::TcpRxBuffer::Add
bool Add(Ptr< Packet > p, TcpHeader const &tcph)
Insert a packet into the buffer and update the availBytes counter to reflect the number of bytes read...
Definition: tcp-rx-buffer.cc:140
ns3::TcpRxBuffer
Rx reordering buffer for TCP.
Definition: tcp-rx-buffer.h:74
ns3::TypeId::SetParent
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
ns3::SequenceNumber32
SequenceNumber< uint32_t, int32_t > SequenceNumber32
32 bit Sequence number.
Definition: sequence-number.h:479
ns3::MakeTraceSourceAccessor
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Definition: trace-source-accessor.h:202
ns3::TcpRxBuffer::~TcpRxBuffer
virtual ~TcpRxBuffer()
Definition: tcp-rx-buffer.cc:58
ns3::TcpRxBuffer::SetMaxBufferSize
void SetMaxBufferSize(uint32_t s)
Set the Maximum buffer size.
Definition: tcp-rx-buffer.cc:81
ns3::TcpRxBuffer::MaxBufferSize
uint32_t MaxBufferSize(void) const
Get the Maximum buffer size.
Definition: tcp-rx-buffer.cc:75
ns3::Ptr< Packet >
visualizer.core.start
def start()
Definition: core.py:1853
ns3::TcpRxBuffer::m_sackList
TcpOptionSack::SackList m_sackList
Sack list (updated constantly)
Definition: tcp-rx-buffer.h:218
tcp-rx-buffer.h
ns3::Object
A base class which provides memory management and object aggregation.
Definition: object.h:88
ns3::TcpRxBuffer::Available
uint32_t Available() const
Get the actual number of bytes available to be read.
Definition: tcp-rx-buffer.cc:93
ns3::TcpRxBuffer::m_nextRxSeq
TracedValue< SequenceNumber32 > m_nextRxSeq
Seqnum of the first missing byte in data (RCV.NXT)
Definition: tcp-rx-buffer.h:222
ns3::TcpHeader
Header for the Transmission Control Protocol.
Definition: tcp-header.h:45
ns3::TcpRxBuffer::SetFinSequence
void SetFinSequence(const SequenceNumber32 &s)
Set the FIN Sequence number (i.e., the one closing the connection)
Definition: tcp-rx-buffer.cc:124
ns3::TcpRxBuffer::GetSackList
TcpOptionSack::SackList GetSackList() const
Get the sack list.
Definition: tcp-rx-buffer.cc:358
ns3::TcpOptionSack::SackBlock
std::pair< SequenceNumber32, SequenceNumber32 > SackBlock
SACK block definition.
Definition: tcp-option-sack.h:59
NS_LOG_LOGIC
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
ns3::TcpRxBuffer::BufIterator
std::map< SequenceNumber32, Ptr< Packet > >::iterator BufIterator
container for data stored in the buffer
Definition: tcp-rx-buffer.h:221
ns3::TcpRxBuffer::m_availBytes
uint32_t m_availBytes
Number of bytes available to read, i.e.
Definition: tcp-rx-buffer.h:227
ns3::TcpRxBuffer::m_maxBuffer
uint32_t m_maxBuffer
Upper bound of the number of data bytes in buffer (RCV.WND)
Definition: tcp-rx-buffer.h:226
uint32_t
ns3::Packet::AddAtEnd
void AddAtEnd(Ptr< const Packet > packet)
Concatenate the input packet at the end of the current packet.
Definition: packet.cc:335
ns3::TcpRxBuffer::m_data
std::map< SequenceNumber32, Ptr< Packet > > m_data
Corresponding data (may be null)
Definition: tcp-rx-buffer.h:228
pktSize
uint32_t pktSize
packet size used for the simulation (in bytes)
Definition: wifi-bianchi.cc:86
NS_LOG_FUNCTION
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Definition: log-macros-enabled.h:244
ns3::TcpRxBuffer::Finished
bool Finished(void)
Check if the buffer did receive all the data (and the connection is closed)
Definition: tcp-rx-buffer.cc:134
ns3::TcpRxBuffer::SetNextRxSequence
void SetNextRxSequence(const SequenceNumber32 &s)
Set the Next Sequence number.
Definition: tcp-rx-buffer.cc:69
ns3::TcpRxBuffer::TcpRxBuffer
TcpRxBuffer(uint32_t n=0)
Constructor.
Definition: tcp-rx-buffer.cc:53
ns3::SequenceNumber< uint32_t, int32_t >
ns3::TcpRxBuffer::m_size
uint32_t m_size
Number of total data bytes in the buffer, not necessarily contiguous.
Definition: tcp-rx-buffer.h:225
ns3::TcpRxBuffer::Extract
Ptr< Packet > Extract(uint32_t maxSize)
Extract data from the head of the buffer as indicated by nextRxSeq.
Definition: tcp-rx-buffer.cc:364
sample-rng-plot.n
n
Definition: sample-rng-plot.py:37
ns3::TcpOptionSack::SackList
std::list< SackBlock > SackList
SACK list definition.
Definition: tcp-option-sack.h:60
ns3::TcpHeader::GetSequenceNumber
SequenceNumber32 GetSequenceNumber() const
Get the sequence number.
Definition: tcp-header.cc:143