NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
ndn-pit-impl.h
1 /* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
2 /*
3  * Copyright (c) 2011 University of California, Los Angeles
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: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19  */
20 
21 #ifndef _NDN_PIT_IMPL_H_
22 #define _NDN_PIT_IMPL_H_
23 
24 #include "ndn-pit.h"
25 
26 #include "ns3/log.h"
27 #include "ns3/simulator.h"
28 
29 #include "../../utils/trie/trie-with-policy.h"
30 #include "ndn-pit-entry-impl.h"
31 
32 #include "ns3/ndn-interest.h"
33 #include "ns3/ndn-data.h"
34 #include "ns3/ndn-forwarding-strategy.h"
35 #include "ns3/ndn-name.h"
36 
37 
38 namespace ns3 {
39 namespace ndn {
40 
41 class ForwardingStrategy;
42 
43 namespace pit {
44 
49 template<class Policy>
50 class PitImpl : public Pit
51  , protected ndnSIM::trie_with_policy<Name,
52  ndnSIM::smart_pointer_payload_traits< EntryImpl< PitImpl< Policy > > >,
53  // ndnSIM::persistent_policy_traits
54  Policy
55  >
56 {
57 public:
60  // ndnSIM::persistent_policy_traits
61  Policy
62  > super;
64 
70  static TypeId GetTypeId ();
71 
75  PitImpl ();
76 
80  virtual ~PitImpl ();
81 
82  // inherited from Pit
83  virtual Ptr<Entry>
84  Lookup (const Data &header);
85 
86  virtual Ptr<Entry>
87  Lookup (const Interest &header);
88 
89  virtual Ptr<Entry>
90  Find (const Name &prefix);
91 
92  virtual Ptr<Entry>
93  Create (Ptr<const Interest> header);
94 
95  virtual void
96  MarkErased (Ptr<Entry> entry);
97 
98  virtual void
99  Print (std::ostream &os) const;
100 
101  virtual uint32_t
102  GetSize () const;
103 
104  virtual Ptr<Entry>
105  Begin ();
106 
107  virtual Ptr<Entry>
108  End ();
109 
110  virtual Ptr<Entry>
111  Next (Ptr<Entry>);
112 
113  const typename super::policy_container &
114  GetPolicy () const { return super::getPolicy (); }
115 
116  typename super::policy_container &
117  GetPolicy () { return super::getPolicy (); }
118 
119 protected:
120  void RescheduleCleaning ();
121  void CleanExpired ();
122 
123  // inherited from Object class
124  virtual void NotifyNewAggregate ();
125  virtual void DoDispose ();
126 
127 private:
128  uint32_t
129  GetMaxSize () const;
130 
131  void
132  SetMaxSize (uint32_t maxSize);
133 
134  uint32_t
135  GetCurrentSize () const;
136 
137 private:
138  EventId m_cleanEvent;
139  Ptr<Fib> m_fib;
140  Ptr<ForwardingStrategy> m_forwardingStrategy;
141 
142  static LogComponent g_log;
143 
144  // indexes
145  typedef
146  boost::intrusive::multiset<entry,
147  boost::intrusive::compare < TimestampIndex< entry > >,
148  boost::intrusive::member_hook< entry,
149  boost::intrusive::set_member_hook<>,
150  &entry::time_hook_>
151  > time_index;
152  time_index i_time;
153 
154  friend class EntryImpl< PitImpl >;
155 };
156 
160 
161 template<class Policy>
162 LogComponent PitImpl< Policy >::g_log = LogComponent (("ndn.pit." + Policy::GetName ()).c_str ());
163 
164 
165 template<class Policy>
166 TypeId
168 {
169  static TypeId tid = TypeId (("ns3::ndn::pit::"+Policy::GetName ()).c_str ())
170  .SetGroupName ("Ndn")
171  .SetParent<Pit> ()
172  .AddConstructor< PitImpl< Policy > > ()
173  .AddAttribute ("MaxSize",
174  "Set maximum size of PIT in bytes. If 0, limit is not enforced",
175  UintegerValue (0),
176  MakeUintegerAccessor (&PitImpl< Policy >::GetMaxSize,
178  MakeUintegerChecker<uint32_t> ())
179 
180  .AddAttribute ("CurrentSize", "Get current size of PIT in bytes",
181  TypeId::ATTR_GET,
182  UintegerValue (0),
183  MakeUintegerAccessor (&PitImpl< Policy >::GetCurrentSize),
184  MakeUintegerChecker<uint32_t> ())
185  ;
186 
187  return tid;
188 }
189 
190 template<class Policy>
191 uint32_t
193 {
194  return super::getPolicy ().size ();
195 }
196 
197 template<class Policy>
199 {
200 }
201 
202 template<class Policy>
204 {
205 }
206 
207 template<class Policy>
208 uint32_t
210 {
211  return super::getPolicy ().get_max_size ();
212 }
213 
214 template<class Policy>
215 void
216 PitImpl<Policy>::SetMaxSize (uint32_t maxSize)
217 {
218  super::getPolicy ().set_max_size (maxSize);
219 }
220 
221 template<class Policy>
222 void
224 {
225  if (m_fib == 0)
226  {
227  m_fib = GetObject<Fib> ();
228  }
229  if (m_forwardingStrategy == 0)
230  {
231  m_forwardingStrategy = GetObject<ForwardingStrategy> ();
232  }
233 
234  Pit::NotifyNewAggregate ();
235 }
236 
237 template<class Policy>
238 void
240 {
241  super::clear ();
242 
243  m_forwardingStrategy = 0;
244  m_fib = 0;
245 
246  Pit::DoDispose ();
247 }
248 
249 template<class Policy>
250 void
252 {
253  // m_cleanEvent.Cancel ();
254  Simulator::Remove (m_cleanEvent); // slower, but better for memory
255  if (i_time.empty ())
256  {
257  // NS_LOG_DEBUG ("No items in PIT");
258  return;
259  }
260 
261  Time nextEvent = i_time.begin ()->GetExpireTime () - Simulator::Now ();
262  if (nextEvent <= 0) nextEvent = Seconds (0);
263 
264  NS_LOG_DEBUG ("Schedule next cleaning in " <<
265  nextEvent.ToDouble (Time::S) << "s (at " <<
266  i_time.begin ()->GetExpireTime () << "s abs time");
267 
268  m_cleanEvent = Simulator::Schedule (nextEvent,
269  &PitImpl<Policy>::CleanExpired, this);
270 }
271 
272 template<class Policy>
273 void
274 PitImpl<Policy>::CleanExpired ()
275 {
276  NS_LOG_LOGIC ("Cleaning PIT. Total: " << i_time.size ());
277  Time now = Simulator::Now ();
278 
279  // uint32_t count = 0;
280  while (!i_time.empty ())
281  {
282  typename time_index::iterator entry = i_time.begin ();
283  if (entry->GetExpireTime () <= now) // is the record stale?
284  {
285  m_forwardingStrategy->WillEraseTimedOutPendingInterest (entry->to_iterator ()->payload ());
286  super::erase (entry->to_iterator ());
287  // count ++;
288  }
289  else
290  break; // nothing else to do. All later records will not be stale
291  }
292 
293  if (super::getPolicy ().size ())
294  {
295  NS_LOG_DEBUG ("Size: " << super::getPolicy ().size ());
296  NS_LOG_DEBUG ("i_time size: " << i_time.size ());
297  }
298  RescheduleCleaning ();
299 }
300 
301 template<class Policy>
302 Ptr<Entry>
304 {
306  typename super::iterator item = super::longest_prefix_match_if (header.GetName (), EntryIsNotEmpty ());
307 
308  if (item == super::end ())
309  return 0;
310  else
311  return item->payload (); // which could also be 0
312 }
313 
314 template<class Policy>
315 Ptr<Entry>
317 {
318  // NS_LOG_FUNCTION (header.GetName ());
319  NS_ASSERT_MSG (m_fib != 0, "FIB should be set");
320  NS_ASSERT_MSG (m_forwardingStrategy != 0, "Forwarding strategy should be set");
321 
322  typename super::iterator foundItem, lastItem;
323  bool reachLast;
324  boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (header.GetName ());
325 
326  if (!reachLast || lastItem == super::end ())
327  return 0;
328  else
329  return lastItem->payload (); // which could also be 0
330 }
331 
332 template<class Policy>
333 Ptr<Entry>
335 {
336  typename super::iterator item = super::find_exact (prefix);
337 
338  if (item == super::end ())
339  return 0;
340  else
341  return item->payload ();
342 }
343 
344 
345 template<class Policy>
346 Ptr<Entry>
347 PitImpl<Policy>::Create (Ptr<const Interest> header)
348 {
349  NS_LOG_DEBUG (header->GetName ());
350  Ptr<fib::Entry> fibEntry = m_fib->LongestPrefixMatch (*header);
351  if (fibEntry == 0)
352  return 0;
353 
354  // NS_ASSERT_MSG (fibEntry != 0,
355  // "There should be at least default route set" <<
356  // " Prefix = "<< header->GetName() << ", NodeID == " << m_fib->GetObject<Node>()->GetId() << "\n" << *m_fib);
357 
358  Ptr< entry > newEntry = ns3::Create< entry > (boost::ref (*this), header, fibEntry);
359  std::pair< typename super::iterator, bool > result = super::insert (header->GetName (), newEntry);
360  if (result.first != super::end ())
361  {
362  if (result.second)
363  {
364  newEntry->SetTrie (result.first);
365  return newEntry;
366  }
367  else
368  {
369  // should we do anything?
370  // update payload? add new payload?
371  return result.first->payload ();
372  }
373  }
374  else
375  return 0;
376 }
377 
378 
379 template<class Policy>
380 void
381 PitImpl<Policy>::MarkErased (Ptr<Entry> item)
382 {
383  if (this->m_PitEntryPruningTimout.IsZero ())
384  {
385  super::erase (StaticCast< entry > (item)->to_iterator ());
386  }
387  else
388  {
389  item->OffsetLifetime (this->m_PitEntryPruningTimout - item->GetExpireTime () + Simulator::Now ());
390  }
391 }
392 
393 
394 template<class Policy>
395 void
396 PitImpl<Policy>::Print (std::ostream& os) const
397 {
398  // !!! unordered_set imposes "random" order of item in the same level !!!
399  typename super::parent_trie::const_recursive_iterator item (super::getTrie ()), end (0);
400  for (; item != end; item++)
401  {
402  if (item->payload () == 0) continue;
403 
404  os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
405  }
406 }
407 
408 template<class Policy>
409 uint32_t
411 {
412  return super::getPolicy ().size ();
413 }
414 
415 template<class Policy>
416 Ptr<Entry>
418 {
419  typename super::parent_trie::recursive_iterator item (super::getTrie ()), end (0);
420  for (; item != end; item++)
421  {
422  if (item->payload () == 0) continue;
423  break;
424  }
425 
426  if (item == end)
427  return End ();
428  else
429  return item->payload ();
430 }
431 
432 template<class Policy>
433 Ptr<Entry>
435 {
436  return 0;
437 }
438 
439 template<class Policy>
440 Ptr<Entry>
441 PitImpl<Policy>::Next (Ptr<Entry> from)
442 {
443  if (from == 0) return 0;
444 
445  typename super::parent_trie::recursive_iterator
446  item (*StaticCast< entry > (from)->to_iterator ()),
447  end (0);
448 
449  for (item++; item != end; item++)
450  {
451  if (item->payload () == 0) continue;
452  break;
453  }
454 
455  if (item == end)
456  return End ();
457  else
458  return item->payload ();
459 }
460 
461 
462 } // namespace pit
463 } // namespace ndn
464 } // namespace ns3
465 
466 #endif /* NDN_PIT_IMPL_H */
boost::tuple< iterator, bool, iterator > find(const FullKey &key)
Perform the longest prefix match.
Definition: trie.h:305
virtual void NotifyNewAggregate()
Even when object is aggregated to another Object.
Definition: ndn-pit-impl.h:223
Class for NDN Name.
Definition: name.h:29
virtual Ptr< Entry > Find(const Name &prefix)
Get PIT entry for the prefix (exact match)
Definition: ndn-pit-impl.h:334
Class implementing Pending Interests Table.
Definition: ndn-pit.h:60
virtual Ptr< Entry > Lookup(const Data &header)
Find corresponding PIT entry for the given content name.
Definition: ndn-pit-impl.h:303
const Name & GetName() const
Get interest name.
Definition: ndn-interest.cc:76
Class implementing Pending Interests Table.
Definition: ndn-pit-impl.h:50
Data header.
Definition: ndn-data.h:39
const Name & GetName() const
Get name of the content object.
Definition: ndn-data.cc:75
virtual void DoDispose()
Do cleanup.
Definition: ndn-pit-impl.h:239
virtual uint32_t GetSize() const
Get number of entries in PIT.
Definition: ndn-pit-impl.h:410
PIT entry implementation with additional pointers to the underlying container.
virtual void Print(std::ostream &os) const
Print out PIT contents for debugging purposes.
Definition: ndn-pit-impl.h:396
static TypeId GetTypeId()
Interface ID.
Definition: ndn-pit-impl.h:167
NDN Interest (wire formats are defined in wire)
Definition: ndn-interest.h:43
virtual Ptr< Entry > End()
Return item next after last (no order guaranteed)
Definition: ndn-pit-impl.h:434
virtual Ptr< Entry > Create(Ptr< const Interest > header)
Creates a PIT entry for the given interest.
Definition: ndn-pit-impl.h:347
virtual Ptr< Entry > Begin()
Return first element of FIB (no order guaranteed)
Definition: ndn-pit-impl.h:417
virtual ~PitImpl()
Destructor.
Definition: ndn-pit-impl.h:203
PitImpl()
PIT constructor.
Definition: ndn-pit-impl.h:198