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-fib-impl.cc
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 #include "ndn-fib-impl.h"
22 
23 #include "ns3/ndn-face.h"
24 #include "ns3/ndn-interest.h"
25 #include "ns3/ndn-forwarding-strategy.h"
26 
27 #include "ns3/node.h"
28 #include "ns3/assert.h"
29 #include "ns3/names.h"
30 #include "ns3/log.h"
31 
32 #include <boost/ref.hpp>
33 #include <boost/lambda/lambda.hpp>
34 #include <boost/lambda/bind.hpp>
35 namespace ll = boost::lambda;
36 
37 NS_LOG_COMPONENT_DEFINE ("ndn.fib.FibImpl");
38 
39 namespace ns3 {
40 namespace ndn {
41 namespace fib {
42 
43 NS_OBJECT_ENSURE_REGISTERED (FibImpl);
44 
45 TypeId
47 {
48  static TypeId tid = TypeId ("ns3::ndn::fib::Default") // cheating ns3 object system
49  .SetParent<Fib> ()
50  .SetGroupName ("Ndn")
51  .AddConstructor<FibImpl> ()
52  ;
53  return tid;
54 }
55 
57 {
58 }
59 
60 void
62 {
63  Object::NotifyNewAggregate ();
64 }
65 
66 void
68 {
69  clear ();
70  Object::DoDispose ();
71 }
72 
73 
74 Ptr<Entry>
76 {
78  // @todo use predicate to search with exclude filters
79 
80  if (item == super::end ())
81  return 0;
82  else
83  return item->payload ();
84 }
85 
86 Ptr<fib::Entry>
87 FibImpl::Find (const Name &prefix)
88 {
89  super::iterator item = super::find_exact (prefix);
90 
91  if (item == super::end ())
92  return 0;
93  else
94  return item->payload ();
95 }
96 
97 
98 Ptr<Entry>
99 FibImpl::Add (const Name &prefix, Ptr<Face> face, int32_t metric)
100 {
101  return Add (Create<Name> (prefix), face, metric);
102 }
103 
104 Ptr<Entry>
105 FibImpl::Add (const Ptr<const Name> &prefix, Ptr<Face> face, int32_t metric)
106 {
107  NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
108 
109  // will add entry if doesn't exists, or just return an iterator to the existing entry
110  std::pair< super::iterator, bool > result = super::insert (*prefix, 0);
111  if (result.first != super::end ())
112  {
113  if (result.second)
114  {
115  Ptr<EntryImpl> newEntry = Create<EntryImpl> (this, prefix);
116  newEntry->SetTrie (result.first);
117  result.first->set_payload (newEntry);
118  }
119 
120  super::modify (result.first,
121  ll::bind (&Entry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
122 
123  if (result.second)
124  {
125  // notify forwarding strategy about new FIB entry
126  NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
127  this->GetObject<ForwardingStrategy> ()->DidAddFibEntry (result.first->payload ());
128  }
129 
130  return result.first->payload ();
131  }
132  else
133  return 0;
134 }
135 
136 void
137 FibImpl::Remove (const Ptr<const Name> &prefix)
138 {
139  NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
140 
141  super::iterator fibEntry = super::find_exact (*prefix);
142  if (fibEntry != super::end ())
143  {
144  // notify forwarding strategy about soon be removed FIB entry
145  NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
146  this->GetObject<ForwardingStrategy> ()->WillRemoveFibEntry (fibEntry->payload ());
147 
148  super::erase (fibEntry);
149  }
150  // else do nothing
151 }
152 
153 // void
154 // FibImpl::Invalidate (const Ptr<const Name> &prefix)
155 // {
156 // NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
157 
158 // super::iterator foundItem, lastItem;
159 // bool reachLast;
160 // boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
161 
162 // if (!reachLast || lastItem->payload () == 0)
163 // return; // nothing to invalidate
164 
165 // super::modify (lastItem,
166 // ll::bind (&Entry::Invalidate, ll::_1));
167 // }
168 
169 void
171 {
172  NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
173 
174  super::parent_trie::recursive_iterator item (super::getTrie ());
175  super::parent_trie::recursive_iterator end (0);
176  for (; item != end; item++)
177  {
178  if (item->payload () == 0) continue;
179 
180  super::modify (&(*item),
181  ll::bind (&Entry::Invalidate, ll::_1));
182  }
183 }
184 
185 void
186 FibImpl::RemoveFace (super::parent_trie &item, Ptr<Face> face)
187 {
188  if (item.payload () == 0) return;
189  NS_LOG_FUNCTION (this);
190 
191  super::modify (&item,
192  ll::bind (&Entry::RemoveFace, ll::_1, face));
193 }
194 
195 void
196 FibImpl::RemoveFromAll (Ptr<Face> face)
197 {
198  NS_LOG_FUNCTION (this);
199 
200  Ptr<Entry> entry = Begin ();
201  while (entry != End ())
202  {
203  entry->RemoveFace (face);
204  if (entry->m_faces.size () == 0)
205  {
206  Ptr<Entry> nextEntry = Next (entry);
207 
208  // notify forwarding strategy about soon be removed FIB entry
209  NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
210  this->GetObject<ForwardingStrategy> ()->WillRemoveFibEntry (entry);
211 
212  super::erase (StaticCast<EntryImpl> (entry)->to_iterator ());
213  entry = nextEntry;
214  }
215  else
216  {
217  entry = Next (entry);
218  }
219  }
220 }
221 
222 void
223 FibImpl::Print (std::ostream &os) const
224 {
225  // !!! unordered_set imposes "random" order of item in the same level !!!
226  super::parent_trie::const_recursive_iterator item (super::getTrie ());
227  super::parent_trie::const_recursive_iterator end (0);
228  for (; item != end; item++)
229  {
230  if (item->payload () == 0) continue;
231 
232  os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
233  }
234 }
235 
236 uint32_t
238 {
239  return super::getPolicy ().size ();
240 }
241 
242 Ptr<const Entry>
244 {
245  super::parent_trie::const_recursive_iterator item (super::getTrie ());
246  super::parent_trie::const_recursive_iterator end (0);
247  for (; item != end; item++)
248  {
249  if (item->payload () == 0) continue;
250  break;
251  }
252 
253  if (item == end)
254  return End ();
255  else
256  return item->payload ();
257 }
258 
259 Ptr<const Entry>
260 FibImpl::End () const
261 {
262  return 0;
263 }
264 
265 Ptr<const Entry>
266 FibImpl::Next (Ptr<const Entry> from) const
267 {
268  if (from == 0) return 0;
269 
270  super::parent_trie::const_recursive_iterator item (*StaticCast<const EntryImpl> (from)->to_iterator ());
271  super::parent_trie::const_recursive_iterator end (0);
272  for (item++; item != end; item++)
273  {
274  if (item->payload () == 0) continue;
275  break;
276  }
277 
278  if (item == end)
279  return End ();
280  else
281  return item->payload ();
282 }
283 
284 Ptr<Entry>
286 {
287  super::parent_trie::recursive_iterator item (super::getTrie ());
288  super::parent_trie::recursive_iterator end (0);
289  for (; item != end; item++)
290  {
291  if (item->payload () == 0) continue;
292  break;
293  }
294 
295  if (item == end)
296  return End ();
297  else
298  return item->payload ();
299 }
300 
301 Ptr<Entry>
303 {
304  return 0;
305 }
306 
307 Ptr<Entry>
308 FibImpl::Next (Ptr<Entry> from)
309 {
310  if (from == 0) return 0;
311 
312  super::parent_trie::recursive_iterator item (*StaticCast<EntryImpl> (from)->to_iterator ());
313  super::parent_trie::recursive_iterator end (0);
314  for (item++; item != end; item++)
315  {
316  if (item->payload () == 0) continue;
317  break;
318  }
319 
320  if (item == end)
321  return End ();
322  else
323  return item->payload ();
324 }
325 
326 
327 } // namespace fib
328 } // namespace ndn
329 } // namespace ns3
virtual void DoDispose()
Perform cleanup.
Definition: ndn-fib-impl.cc:67
Class for NDN Name.
Definition: name.h:29
virtual Ptr< Entry > LongestPrefixMatch(const Interest &interest)
Perform longest prefix match.
Definition: ndn-fib-impl.cc:75
Class implementing FIB functionality.
Definition: ndn-fib-impl.h:70
virtual Ptr< const Entry > Begin() const
Return first element of FIB (no order guaranteed)
virtual void InvalidateAll()
Invalidate all FIB entries.
virtual void NotifyNewAggregate()
Notify when object is aggregated.
Definition: ndn-fib-impl.cc:61
virtual Ptr< fib::Entry > Find(const Name &prefix)
Get FIB entry for the prefix (exact match)
Definition: ndn-fib-impl.cc:87
const Name & GetName() const
Get interest name.
Definition: ndn-interest.cc:76
FibImpl()
Constructor.
Definition: ndn-fib-impl.cc:56
iterator longest_prefix_match(const Name &key)
Find a node that has the longest common prefix with key (FIB/PIT lookup)
virtual Ptr< Entry > Add(const Name &prefix, Ptr< Face > face, int32_t metric)
Add or update FIB entry.
Definition: ndn-fib-impl.cc:99
virtual uint32_t GetSize() const
Get number of entries in FIB.
static TypeId GetTypeId()
Interface ID.
Definition: ndn-fib-impl.cc:46
void AddOrUpdateRoutingMetric(Ptr< Face > face, int32_t metric)
Add or update routing metric of FIB next hop.
void Invalidate()
Invalidate face.
virtual void Print(std::ostream &os) const
Print out entries in FIB.
Class implementing FIB functionality.
Definition: ndn-fib.h:44
virtual void RemoveFromAll(Ptr< Face > face)
Remove all references to a face from FIB.
NDN Interest (wire formats are defined in wire)
Definition: ndn-interest.h:43
virtual Ptr< const Entry > End() const
Return item next after last (no order guaranteed)
virtual void Remove(const Ptr< const Name > &prefix)
Remove FIB entry.
void RemoveFace(const Ptr< Face > &face)
Remove record associated with face