blob: b068954ed881ef646d16a81a343d488580c7950a [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 Afanasyeva46844b2011-11-21 19:13:26 -080036#include <boost/lambda/lambda.hpp>
Alexander Afanasyev19426ef2011-11-23 20:55:28 -080037#include <boost/lambda/bind.hpp>
38namespace ll = boost::lambda;
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080039
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070040namespace ns3 {
41
42
43//////////////////////////////////////////////////////////////////////
44// Helpers
45//////////////////////////////////////////////////////////////////////
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070046namespace __ccnx_private {
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070047
48struct CcnxFibFaceMetricByFace
49{
50 typedef CcnxFibFaceMetricContainer::type::index<i_face>::type
51 type;
52};
53
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070054}
55//////////////////////////////////////////////////////////////////////
56//////////////////////////////////////////////////////////////////////
Ilya Moiseenko00b30482011-11-15 17:58:00 -080057NS_LOG_COMPONENT_DEFINE ("CcnxFib");
58
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070059using namespace __ccnx_private;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070060
Alexander Afanasyevcf133f02011-09-06 12:13:48 -070061TypeId
62CcnxFib::GetTypeId (void)
63{
64 static TypeId tid = TypeId ("ns3::CcnxFib")
65 .SetParent<Object> ()
66 .SetGroupName ("Ccnx")
67 .AddConstructor<CcnxFib> ()
68
69 ;
70 return tid;
71}
72
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080073/////////////////////////////////////////////////////////////////////
74
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070075void
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080076CcnxFibFaceMetric::UpdateRtt (const Time &rttSample)
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070077{
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070078 // const Time & this->m_rttSample
79
80 //update srtt and rttvar (RFC 2988)
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080081 if (m_sRtt.IsZero ())
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070082 {
83 //first RTT measurement
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080084 NS_ASSERT_MSG (m_rttVar.IsZero (), "SRTT is zero, but variation is not");
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070085
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080086 m_sRtt = rttSample;
87 m_rttVar = Time (m_sRtt / 2.0);
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070088 }
89 else
90 {
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080091 m_rttVar = Time ((1 - NDN_RTO_BETA) * m_rttVar + NDN_RTO_BETA * Abs(m_sRtt - rttSample));
92 m_sRtt = Time ((1 - NDN_RTO_ALPHA) * m_sRtt + NDN_RTO_ALPHA * rttSample);
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070093 }
94}
95
Alexander Afanasyeva46844b2011-11-21 19:13:26 -080096/////////////////////////////////////////////////////////////////////
97
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070098void
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -080099CcnxFibEntry::UpdateFaceRtt (Ptr<CcnxFace> face, const Time &sample)
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700100{
Alexander Afanasyeva46844b2011-11-21 19:13:26 -0800101 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
102 NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700103 "Update status can be performed only on existing faces of CcxnFibEntry");
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700104
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800105 m_faces.modify (record,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800106 ll::bind (&CcnxFibFaceMetric::UpdateRtt, ll::_1, sample));
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700107
108 // reordering random access index same way as by metric index
Alexander Afanasyeva46844b2011-11-21 19:13:26 -0800109 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700110}
111
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800112void
113CcnxFibEntry::UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status)
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700114{
Alexander Afanasyev23d2b542011-12-07 18:54:46 -0800115 NS_LOG_FUNCTION (this << boost::cref(*face) << status);
116
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800117 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
118 NS_ASSERT_MSG (record != m_faces.get<i_face> ().end (),
119 "Update status can be performed only on existing faces of CcxnFibEntry");
120
121 m_faces.modify (record,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800122 (&ll::_1)->*&CcnxFibFaceMetric::m_status = status);
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800123
124 // reordering random access index same way as by metric index
125 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
126}
127
128void
129CcnxFibEntry::AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric)
130{
131 NS_LOG_FUNCTION (this);
132 NS_ASSERT_MSG (face != NULL, "Trying to Add or Update NULL face");
133
134 CcnxFibFaceMetricByFace::type::iterator record = m_faces.get<i_face> ().find (face);
135 if (record == m_faces.get<i_face> ().end ())
136 {
137 m_faces.insert (CcnxFibFaceMetric (face, metric));
138 }
139 else
140 {
141 m_faces.modify (record,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800142 (&ll::_1)->*&CcnxFibFaceMetric::m_routingCost = metric);
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800143 }
144
145 // reordering random access index same way as by metric index
146 m_faces.get<i_nth> ().rearrange (m_faces.get<i_metric> ().begin ());
147}
148
149const CcnxFibFaceMetric &
150CcnxFibEntry::FindBestCandidate (uint32_t skip/* = 0*/) const
151{
152 if (m_faces.size () == 0) throw CcnxFibEntry::NoFaces ();
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700153 skip = skip % m_faces.size();
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800154 return m_faces.get<i_nth> () [skip];
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700155}
156
157
Alexander Afanasyeva67e28c2011-08-31 21:16:25 -0700158CcnxFib::CcnxFib ()
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700159{
160}
161
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700162void
163CcnxFib::NotifyNewAggregate ()
164{
165 if (m_node == 0)
166 m_node = this->GetObject<Node>();
167 Object::NotifyNewAggregate ();
168}
169
170void
171CcnxFib::DoDispose (void)
172{
Alexander Afanasyev07827182011-12-13 01:07:32 -0800173 m_fib.clear ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700174 m_node = 0;
175 Object::DoDispose ();
176}
177
178
179CcnxFibEntryContainer::type::iterator
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700180CcnxFib::LongestPrefixMatch (const CcnxInterestHeader &interest) const
181{
182 const CcnxNameComponents &name = interest.GetName ();
Alexander Afanasyeva174aa52011-12-13 01:30:32 -0800183 for (size_t componentsCount = name.GetComponents ().size ()+1;
184 componentsCount > 0;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700185 componentsCount--)
186 {
Alexander Afanasyeva174aa52011-12-13 01:30:32 -0800187 CcnxNameComponents subPrefix (name.GetSubComponents (componentsCount-1));
Alexander Afanasyev07827182011-12-13 01:07:32 -0800188 CcnxFibEntryContainer::type::iterator match = m_fib.find (subPrefix);
189 if (match != m_fib.end())
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700190 return match;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700191 }
192
Alexander Afanasyev07827182011-12-13 01:07:32 -0800193 return m_fib.end ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700194}
195
196
197CcnxFibEntryContainer::type::iterator
198CcnxFib::Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric)
199{
200// CcnxFibFaceMetric
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800201 NS_LOG_FUNCTION(this << prefix << face << metric);
Alexander Afanasyev07827182011-12-13 01:07:32 -0800202 CcnxFibEntryContainer::type::iterator entry = m_fib.find (prefix);
203 if (entry == m_fib.end ())
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700204 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800205 entry = m_fib.insert (m_fib.end (), CcnxFibEntry (prefix));
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700206 // insert new
207 }
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700208
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800209 NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
Alexander Afanasyev07827182011-12-13 01:07:32 -0800210 m_fib.modify (entry,
211 ll::bind (&CcnxFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800212
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700213 return entry;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700214}
Ilya Moiseenko4e473482011-10-31 17:58:14 -0700215
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800216void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800217CcnxFib::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800218{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800219 NS_LOG_FUNCTION (this);
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800220
Alexander Afanasyev07827182011-12-13 01:07:32 -0800221 m_fib.modify (m_fib.iterator_to (entry),
222 ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800223 if (entry.m_faces.size () == 0)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800224 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800225 m_fib.erase (m_fib.iterator_to (entry));
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800226 }
227}
228
229void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800230CcnxFib::RemoveFromAll (Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800231{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800232 NS_LOG_FUNCTION (this);
233
Alexander Afanasyev07827182011-12-13 01:07:32 -0800234 for_each (m_fib.begin (), m_fib.end (),
235 ll::bind (&CcnxFib::Remove, this, ll::_1, face));
236}
237
238/**
239 * \brief Get number of FIB entry (for python bindings)
240 */
241uint32_t
242CcnxFib::GetCcnxFibEntryCount () const
243{
244 return m_fib.size ();
245}
246
247/**
248 * \brief Get FIB entry by index (for python bindings)
249 */
250const CcnxFibEntry &
251CcnxFib::GetCcnxFibEntry (uint32_t index)
252{
253 NS_ASSERT (0 <= index && index < m_fib.size ());
254 return m_fib.get <i_nth> () [index];
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800255}
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700256
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800257
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700258std::ostream& operator<< (std::ostream& os, const CcnxFib &fib)
259{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700260 os << "Node " << Names::FindName (fib.m_node) << "\n";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700261 os << " Dest prefix Interfaces(Costs) \n";
262 os << "+-------------+--------------------------------------+\n";
263
Alexander Afanasyev07827182011-12-13 01:07:32 -0800264 for (CcnxFibEntryContainer::type::iterator entry = fib.m_fib.begin ();
265 entry != fib.m_fib.end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700266 entry++)
267 {
Alexander Afanasyev07827182011-12-13 01:07:32 -0800268 os << entry->GetPrefix () << "\t" << *entry << "\n";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700269 }
270 return os;
271}
272
273std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry)
274{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700275 for (CcnxFibFaceMetricContainer::type::index<i_nth>::type::iterator metric =
276 entry.m_faces.get<i_nth> ().begin ();
277 metric != entry.m_faces.get<i_nth> ().end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700278 metric++)
279 {
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700280 if (metric != entry.m_faces.get<i_nth> ().begin ())
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700281 os << ", ";
282
283 os << *metric;
284 }
285 return os;
286}
287
288std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric)
289{
290 static const std::string statusString[] = {"","g","y","r"};
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700291
Alexander Afanasyev3661e232012-01-20 17:36:15 -0800292 os << *metric.m_face << "(" << metric.m_routingCost << ","<< statusString [metric.m_status] << "," << metric.m_face->GetMetric () << ")";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700293 return os;
294}
295
296// void CcnxFib::resetProbing()
297// {
298// for(FibRangeIterator fib = _fib.begin(); fib != _fib.end(); fib++)
299// VALUE(fib).needsProbing = true;
300// }
301
302// void CcnxFib::updateInterfaceStatus( int interface, int status )
303// {
304// for( FibRangeIterator fib = _fib.begin(); fib!=_fib.end(); fib++ )
305// {
306// VALUE(fib).updateStatus( interface, status );
307// }
308// }
309
310} // namespace ns3