blob: eece4c40d9fa2e605cfa8231f8262558bc114621 [file] [log] [blame]
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -07001/* -*- 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
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070021#ifndef _NDN_PIT_IMPL_H_
22#define _NDN_PIT_IMPL_H_
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070023
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070024#include "ndn-pit.h"
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -070025
Alexander Afanasyev26719e22013-03-26 12:43:28 -070026#include "ns3/log.h"
27#include "ns3/simulator.h"
Alexander Afanasyev413c7f12012-07-10 17:35:16 -070028
Alexander Afanasyev26719e22013-03-26 12:43:28 -070029#include "../../utils/trie/trie-with-policy.h"
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070030#include "ndn-pit-entry-impl.h"
Alexander Afanasyev413c7f12012-07-10 17:35:16 -070031
Alexander Afanasyev26719e22013-03-26 12:43:28 -070032#include "ns3/ndn-interest.h"
Alexander Afanasyev6eba36f2013-08-07 17:42:54 -070033#include "ns3/ndn-data.h"
Alexander Afanasyev26719e22013-03-26 12:43:28 -070034#include "ns3/ndn-forwarding-strategy.h"
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -070035#include "ns3/ndn-name.h"
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070036
Alexander Afanasyev26719e22013-03-26 12:43:28 -070037
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070038namespace ns3 {
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070039namespace ndn {
40
41class ForwardingStrategy;
42
43namespace pit {
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070044
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070045/**
Alexander Afanasyev79206512013-07-27 16:49:12 -070046 * @ingroup ndn-pit
47 * @brief Class implementing Pending Interests Table
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070048 */
Alexander Afanasyevbd6f3f42012-07-26 17:50:17 -070049template<class Policy>
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070050class PitImpl : public Pit
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -070051 , protected ndnSIM::trie_with_policy<Name,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070052 ndnSIM::smart_pointer_payload_traits< EntryImpl< PitImpl< Policy > > >,
53 // ndnSIM::persistent_policy_traits
54 Policy
55 >
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070056{
57public:
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -070058 typedef ndnSIM::trie_with_policy<Name,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070059 ndnSIM::smart_pointer_payload_traits< EntryImpl< PitImpl< Policy > > >,
Alexander Afanasyevbd6f3f42012-07-26 17:50:17 -070060 // ndnSIM::persistent_policy_traits
61 Policy
Alexander Afanasyev36b45772012-07-10 16:57:42 -070062 > super;
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070063 typedef EntryImpl< PitImpl< Policy > > entry;
Alexander Afanasyev36b45772012-07-10 16:57:42 -070064
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070065 /**
66 * \brief Interface ID
67 *
68 * \return interface ID
69 */
70 static TypeId GetTypeId ();
71
72 /**
73 * \brief PIT constructor
74 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070075 PitImpl ();
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070076
77 /**
78 * \brief Destructor
79 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070080 virtual ~PitImpl ();
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070081
Alexander Afanasyev7456b702013-02-01 22:41:48 -080082 // inherited from Pit
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070083 virtual Ptr<Entry>
Alexander Afanasyev772f51b2013-08-01 18:53:25 -070084 Lookup (const Data &header);
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070085
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070086 virtual Ptr<Entry>
Alexander Afanasyeveae83ee2013-03-15 15:01:10 -070087 Lookup (const Interest &header);
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070088
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070089 virtual Ptr<Entry>
Alexander Afanasyeve5a8b5a2013-03-15 15:15:26 -070090 Find (const Name &prefix);
Alexander Afanasyev4ebe07e2013-03-26 13:27:55 -070091
Alexander Afanasyeve5a8b5a2013-03-15 15:15:26 -070092 virtual Ptr<Entry>
Alexander Afanasyeveae83ee2013-03-15 15:01:10 -070093 Create (Ptr<const Interest> header);
Alexander Afanasyev7456b702013-02-01 22:41:48 -080094
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070095 virtual void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070096 MarkErased (Ptr<Entry> entry);
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -070097
98 virtual void
99 Print (std::ostream &os) const;
Alexander Afanasyev1aa4bbc2012-07-09 17:17:25 -0700100
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700101 virtual uint32_t
102 GetSize () const;
103
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700104 virtual Ptr<Entry>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700105 Begin ();
106
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700107 virtual Ptr<Entry>
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700108 End ();
109
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700110 virtual Ptr<Entry>
111 Next (Ptr<Entry>);
Alexander Afanasyev7456b702013-02-01 22:41:48 -0800112
Alexander Afanasyev26719e22013-03-26 12:43:28 -0700113 const typename super::policy_container &
114 GetPolicy () const { return super::getPolicy (); }
115
Alexander Afanasyev4ebe07e2013-03-26 13:27:55 -0700116 typename super::policy_container &
117 GetPolicy () { return super::getPolicy (); }
118
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -0700119protected:
Alexander Afanasyev413c7f12012-07-10 17:35:16 -0700120 void RescheduleCleaning ();
121 void CleanExpired ();
Alexander Afanasyev7456b702013-02-01 22:41:48 -0800122
123 // inherited from Object class
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -0700124 virtual void NotifyNewAggregate (); ///< @brief Even when object is aggregated to another Object
125 virtual void DoDispose (); ///< @brief Do cleanup
126
127private:
128 uint32_t
129 GetMaxSize () const;
130
131 void
132 SetMaxSize (uint32_t maxSize);
Alexander Afanasyev7456b702013-02-01 22:41:48 -0800133
134 uint32_t
135 GetCurrentSize () const;
136
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -0700137private:
Alexander Afanasyev413c7f12012-07-10 17:35:16 -0700138 EventId m_cleanEvent;
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700139 Ptr<Fib> m_fib; ///< \brief Link to FIB table
140 Ptr<ForwardingStrategy> m_forwardingStrategy;
Alexander Afanasyev36b45772012-07-10 16:57:42 -0700141
Alexander Afanasyev26719e22013-03-26 12:43:28 -0700142 static LogComponent g_log; ///< @brief Logging variable
Alexander Afanasyev4ebe07e2013-03-26 13:27:55 -0700143
Alexander Afanasyev36b45772012-07-10 16:57:42 -0700144 // indexes
145 typedef
Alexander Afanasyev6b51b082012-07-27 16:28:34 -0700146 boost::intrusive::multiset<entry,
Alexander Afanasyev36b45772012-07-10 16:57:42 -0700147 boost::intrusive::compare < TimestampIndex< entry > >,
148 boost::intrusive::member_hook< entry,
149 boost::intrusive::set_member_hook<>,
150 &entry::time_hook_>
Alexander Afanasyev413c7f12012-07-10 17:35:16 -0700151 > time_index;
Alexander Afanasyev7456b702013-02-01 22:41:48 -0800152 time_index i_time;
153
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700154 friend class EntryImpl< PitImpl >;
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -0700155};
156
Alexander Afanasyev26719e22013-03-26 12:43:28 -0700157//////////////////////////////////////////
158////////// Implementation ////////////////
159//////////////////////////////////////////
160
161template<class Policy>
162LogComponent PitImpl< Policy >::g_log = LogComponent (("ndn.pit." + Policy::GetName ()).c_str ());
163
164
165template<class Policy>
166TypeId
167PitImpl< Policy >::GetTypeId ()
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,
177 &PitImpl< Policy >::SetMaxSize),
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
190template<class Policy>
191uint32_t
192PitImpl<Policy>::GetCurrentSize () const
193{
194 return super::getPolicy ().size ();
195}
196
197template<class Policy>
198PitImpl<Policy>::PitImpl ()
199{
200}
201
202template<class Policy>
203PitImpl<Policy>::~PitImpl ()
204{
205}
206
207template<class Policy>
208uint32_t
209PitImpl<Policy>::GetMaxSize () const
210{
211 return super::getPolicy ().get_max_size ();
212}
213
214template<class Policy>
215void
216PitImpl<Policy>::SetMaxSize (uint32_t maxSize)
217{
218 super::getPolicy ().set_max_size (maxSize);
219}
220
221template<class Policy>
222void
223PitImpl<Policy>::NotifyNewAggregate ()
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
237template<class Policy>
238void
239PitImpl<Policy>::DoDispose ()
240{
241 super::clear ();
242
243 m_forwardingStrategy = 0;
244 m_fib = 0;
245
246 Pit::DoDispose ();
247}
248
249template<class Policy>
250void
251PitImpl<Policy>::RescheduleCleaning ()
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
272template<class Policy>
273void
274PitImpl<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
301template<class Policy>
302Ptr<Entry>
Alexander Afanasyev772f51b2013-08-01 18:53:25 -0700303PitImpl<Policy>::Lookup (const Data &header)
Alexander Afanasyev26719e22013-03-26 12:43:28 -0700304{
305 /// @todo use predicate to search with exclude filters
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
314template<class Policy>
315Ptr<Entry>
316PitImpl<Policy>::Lookup (const Interest &header)
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
332template<class Policy>
333Ptr<Entry>
334PitImpl<Policy>::Find (const Name &prefix)
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
345template<class Policy>
346Ptr<Entry>
347PitImpl<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
379template<class Policy>
380void
381PitImpl<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
394template<class Policy>
395void
396PitImpl<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
408template<class Policy>
409uint32_t
410PitImpl<Policy>::GetSize () const
411{
412 return super::getPolicy ().size ();
413}
414
415template<class Policy>
416Ptr<Entry>
417PitImpl<Policy>::Begin ()
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
432template<class Policy>
433Ptr<Entry>
434PitImpl<Policy>::End ()
435{
436 return 0;
437}
438
439template<class Policy>
440Ptr<Entry>
441PitImpl<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
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700462} // namespace pit
463} // namespace ndn
Alexander Afanasyev11f7bb42012-07-09 17:06:30 -0700464} // namespace ns3
465
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700466#endif /* NDN_PIT_IMPL_H */