blob: 1c86b2895e9d8ee546cac335f71baa978d66a23f [file] [log] [blame]
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -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
21#include "ccnx-fib.h"
22
23#include "ccnx.h"
24#include "ccnx-face.h"
25#include "ccnx-interest-header.h"
26
27#include "ns3/node.h"
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070028#include "ns3/assert.h"
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -070029#include "ns3/names.h"
Ilya Moiseenko00b30482011-11-15 17:58:00 -080030#include "ns3/log.h"
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070031
32#define NDN_RTO_ALPHA 0.125
33#define NDN_RTO_BETA 0.25
34#define NDN_RTO_K 4
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070035
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -070036#include <boost/ref.hpp>
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080037#include <boost/lambda/lambda.hpp>
Alexander Afanasyev19426ef2011-11-23 20:55:28 -080038#include <boost/lambda/bind.hpp>
39namespace ll = boost::lambda;
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080040
Alexander Afanasyev3a4a0b32012-06-28 14:14:22 -070041NS_LOG_COMPONENT_DEFINE ("CcnxFib");
42
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070043namespace ns3 {
44
Alexander Afanasyev3a4a0b32012-06-28 14:14:22 -070045NS_OBJECT_ENSURE_REGISTERED (CcnxFib);
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070046
47//////////////////////////////////////////////////////////////////////
48// Helpers
49//////////////////////////////////////////////////////////////////////
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070050namespace __ccnx_private {
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070051
52struct CcnxFibFaceMetricByFace
53{
54 typedef CcnxFibFaceMetricContainer::type::index<i_face>::type
55 type;
56};
57
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070058}
59//////////////////////////////////////////////////////////////////////
60//////////////////////////////////////////////////////////////////////
Ilya Moiseenko00b30482011-11-15 17:58:00 -080061
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070062using namespace __ccnx_private;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070063
Alexander Afanasyevcf133f02011-09-06 12:13:48 -070064TypeId
65CcnxFib::GetTypeId (void)
66{
67 static TypeId tid = TypeId ("ns3::CcnxFib")
68 .SetParent<Object> ()
69 .SetGroupName ("Ccnx")
70 .AddConstructor<CcnxFib> ()
71
72 ;
73 return tid;
74}
75
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080076/////////////////////////////////////////////////////////////////////
77
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070078void
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080079CcnxFibFaceMetric::UpdateRtt (const Time &rttSample)
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070080{
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070081 // const Time & this->m_rttSample
82
83 //update srtt and rttvar (RFC 2988)
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080084 if (m_sRtt.IsZero ())
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070085 {
86 //first RTT measurement
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080087 NS_ASSERT_MSG (m_rttVar.IsZero (), "SRTT is zero, but variation is not");
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070088
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080089 m_sRtt = rttSample;
90 m_rttVar = Time (m_sRtt / 2.0);
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070091 }
92 else
93 {
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080094 m_rttVar = Time ((1 - NDN_RTO_BETA) * m_rttVar + NDN_RTO_BETA * Abs(m_sRtt - rttSample));
95 m_sRtt = Time ((1 - NDN_RTO_ALPHA) * m_sRtt + NDN_RTO_ALPHA * rttSample);
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070096 }
97}
98
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080099/////////////////////////////////////////////////////////////////////
100
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700101void
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800102CcnxFibEntry::UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample)
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700103{
Alexander Afanasyeva46844b2011-11-21 19:13:26 -0800104 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
105 NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700106 "Update status can be performed only on existing faces of CcxnFibEntry");
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700107
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800108 m_faces.modify (record,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800109 ll::bind (&CcnxFibFaceMetric::UpdateRtt, ll::_1, sample));
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700110
111 // reordering random access index same way as by metric index
Alexander Afanasyeva46844b2011-11-21 19:13:26 -0800112 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700113}
114
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800115void
116CcnxFibEntry::UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status)
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700117{
Alexander Afanasyev23d2b542011-12-07 18:54:46 -0800118 NS_LOG_FUNCTION (this << boost::cref(*face) << status);
119
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800120 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
121 NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
122 "Update status can be performed only on existing faces of CcxnFibEntry");
123
124 m_faces.modify (record,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800125 (&ll::_1)->*&CcnxFibFaceMetric::m_status = status);
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800126
127 // reordering random access index same way as by metric index
128 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
129}
130
131void
132CcnxFibEntry::AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric)
133{
134 NS_LOG_FUNCTION (this);
135 NS_ASSERT_MSG (face != NULL, "Trying to Add or Update NULL face");
136
137 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
138 if (record == m_faces.get<i_face> ().end ())
139 {
140 m_faces.insert (CcnxFibFaceMetric (face, metric));
141 }
142 else
143 {
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700144 // don't update metric to higher value
145 if (record->m_routingCost > metric || record->m_status == CcnxFibFaceMetric::NDN_FIB_RED)
146 {
147 m_faces.modify (record,
148 (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = metric);
149
150 m_faces.modify (record,
151 (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_YELLOW);
152 }
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800153 }
154
155 // reordering random access index same way as by metric index
156 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
157}
158
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700159void
160CcnxFibEntry::Invalidate ()
161{
162 for (CcnxFibFaceMetricByFace::type::iterator face = m_faces.begin ();
163 face != m_faces.end ();
164 face++)
165 {
166 m_faces.modify (face,
167 (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = std::numeric_limits<uint16_t>::max ());
168
169 m_faces.modify (face,
170 (&ll::_1)->*&CcnxFibFaceMetric::m_status = CcnxFibFaceMetric::NDN_FIB_RED);
171 }
172}
173
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800174const CcnxFibFaceMetric &
175CcnxFibEntry::FindBestCandidate (uint32_t skip/* = 0*/) const
176{
177 if (m_faces.size () == 0) throw CcnxFibEntry::NoFaces ();
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700178 skip = skip % m_faces.size();
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800179 return m_faces.get<i_nth> () [skip];
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700180}
181
182
Alexander Afanasyeva67e28c2011-08-31 21:16:25 -0700183CcnxFib::CcnxFib ()
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700184{
185}
186
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700187void
188CcnxFib::NotifyNewAggregate ()
189{
190 if (m_node == 0)
191 m_node = this->GetObject<Node>();
192 Object::NotifyNewAggregate ();
193}
194
195void
196CcnxFib::DoDispose (void)
197{
Alexander Afanasyev07827182011-12-13 01:07:32 -0800198 m_fib.clear ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700199 m_node = 0;
200 Object::DoDispose ();
201}
202
203
204CcnxFibEntryContainer::type::iterator
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700205CcnxFib::LongestPrefixMatch (const CcnxInterestHeader &interest) const
206{
207 const CcnxNameComponents &name = interest.GetName ();
Alexander Afanasyeva174aa52011-12-13 01:30:32 -0800208 for (size_t componentsCount = name.GetComponents ().size ()+1;
209 componentsCount > 0;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700210 componentsCount--)
211 {
Alexander Afanasyeva174aa52011-12-13 01:30:32 -0800212 CcnxNameComponents subPrefix (name.GetSubComponents (componentsCount-1));
Alexander Afanasyev07827182011-12-13 01:07:32 -0800213 CcnxFibEntryContainer::type::iterator match = m_fib.find (subPrefix);
214 if (match != m_fib.end())
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700215 return match;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700216 }
217
Alexander Afanasyev07827182011-12-13 01:07:32 -0800218 return m_fib.end ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700219}
220
221
222CcnxFibEntryContainer::type::iterator
223CcnxFib::Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric)
224{
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700225 return Add (Create<CcnxNameComponents> (prefix), face, metric);
226}
227
228CcnxFibEntryContainer::type::iterator
229CcnxFib::Add (const Ptr<const CcnxNameComponents> &prefix, Ptr<CcnxFace> face, int32_t metric)
230{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700231// CcnxFibFaceMetric
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700232 NS_LOG_FUNCTION(this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
233 CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
Alexander Afanasyev07827182011-12-13 01:07:32 -0800234 if (entry == m_fib.end ())
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700235 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800236 entry = m_fib.insert (m_fib.end (), CcnxFibEntry (prefix));
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700237 // insert new
238 }
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700239
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800240 NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
Alexander Afanasyev07827182011-12-13 01:07:32 -0800241 m_fib.modify (entry,
242 ll::bind (&CcnxFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800243
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700244 return entry;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700245}
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700246
247void
248CcnxFib::Remove (const Ptr<const CcnxNameComponents> &prefix)
249{
250 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
251 CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
252 if (entry != m_fib.end ())
253 m_fib.erase (entry);
254}
255
256void
257CcnxFib::Invalidate (const Ptr<const CcnxNameComponents> &prefix)
258{
259 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
260
261 CcnxFibEntryContainer::type::iterator entry = m_fib.find (*prefix);
262 if (entry == m_fib.end ())
263 return; // nothing to invalidate
264
265 m_fib.modify (entry,
266 ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
267}
268
269void
270CcnxFib::InvalidateAll ()
271{
272 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
273
274 for (CcnxFibEntryContainer::type::iterator entry = m_fib.begin ();
275 entry != m_fib.end ();
276 entry ++)
277 {
278 m_fib.modify (entry,
279 ll::bind (&CcnxFibEntry::Invalidate, ll::_1));
280 }
281}
282
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800283void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800284CcnxFib::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800285{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800286 NS_LOG_FUNCTION (this);
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800287
Alexander Afanasyev07827182011-12-13 01:07:32 -0800288 m_fib.modify (m_fib.iterator_to (entry),
289 ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800290 if (entry.m_faces.size () == 0)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800291 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800292 m_fib.erase (m_fib.iterator_to (entry));
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800293 }
294}
295
296void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800297CcnxFib::RemoveFromAll (Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800298{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800299 NS_LOG_FUNCTION (this);
300
Alexander Afanasyev07827182011-12-13 01:07:32 -0800301 for_each (m_fib.begin (), m_fib.end (),
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700302 ll::bind (static_cast< void (CcnxFib::*) (const CcnxFibEntry &, Ptr<CcnxFace>) > (&CcnxFib::Remove),
303 this, ll::_1, face));
Alexander Afanasyev07827182011-12-13 01:07:32 -0800304}
305
306/**
307 * \brief Get number of FIB entry (for python bindings)
308 */
309uint32_t
310CcnxFib::GetCcnxFibEntryCount () const
311{
312 return m_fib.size ();
313}
314
315/**
316 * \brief Get FIB entry by index (for python bindings)
317 */
318const CcnxFibEntry &
319CcnxFib::GetCcnxFibEntry (uint32_t index)
320{
321 NS_ASSERT (0 <= index && index < m_fib.size ());
322 return m_fib.get <i_nth> () [index];
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800323}
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700324
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800325
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700326std::ostream& operator<< (std::ostream& os, const CcnxFib &fib)
327{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700328 os << "Node " << Names::FindName (fib.m_node) << "\n";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700329 os << " Dest prefix Interfaces(Costs) \n";
330 os << "+-------------+--------------------------------------+\n";
331
Alexander Afanasyev07827182011-12-13 01:07:32 -0800332 for (CcnxFibEntryContainer::type::iterator entry = fib.m_fib.begin ();
333 entry != fib.m_fib.end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700334 entry++)
335 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800336 os << entry->GetPrefix () << "\t" << *entry << "\n";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700337 }
338 return os;
339}
340
341std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry)
342{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700343 for (CcnxFibFaceMetricContainer::type::index<i_nth>::type::iterator metric =
344 entry.m_faces.get<i_nth> ().begin ();
345 metric != entry.m_faces.get<i_nth> ().end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700346 metric++)
347 {
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700348 if (metric != entry.m_faces.get<i_nth> ().begin ())
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700349 os << ", ";
350
351 os << *metric;
352 }
353 return os;
354}
355
356std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric)
357{
358 static const std::string statusString[] = {"","g","y","r"};
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700359
Alexander Afanasyev3661e232012-01-20 17:36:15 -0800360 os << *metric.m_face << "(" << metric.m_routingCost << ","<< statusString [metric.m_status] << "," << metric.m_face->GetMetric () << ")";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700361 return os;
362}
363
364// void CcnxFib::resetProbing()
365// {
366// for(FibRangeIterator fib = _fib.begin(); fib != _fib.end(); fib++)
367// VALUE(fib).needsProbing = true;
368// }
369
370// void CcnxFib::updateInterfaceStatus( int interface, int status )
371// {
372// for( FibRangeIterator fib = _fib.begin(); fib!=_fib.end(); fib++ )
373// {
374// VALUE(fib).updateStatus( interface, status );
375// }
376// }
377
378} // namespace ns3