blob: 89e5231d049acbef838830e60a36b57d5345dece [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 Afanasyev4fa5e842011-11-21 13:38:39 -0800173 clear ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700174 m_node = 0;
Alexander Afanasyev18252852011-11-21 13:35:31 -0800175 clear ();
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700176 Object::DoDispose ();
177}
178
179
180CcnxFibEntryContainer::type::iterator
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700181CcnxFib::LongestPrefixMatch (const CcnxInterestHeader &interest) const
182{
183 const CcnxNameComponents &name = interest.GetName ();
184 for (size_t componentsCount = name.GetComponents ().size ();
Alexander Afanasyev4a5c2c12011-12-12 18:50:57 -0800185 componentsCount >= 0;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700186 componentsCount--)
187 {
188 CcnxNameComponents subPrefix (name.GetSubComponents (componentsCount));
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700189 CcnxFibEntryContainer::type::iterator match = find (subPrefix);
190 if (match != end())
191 return match;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700192 }
193
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700194 return end ();
195}
196
197
198CcnxFibEntryContainer::type::iterator
199CcnxFib::Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric)
200{
201// CcnxFibFaceMetric
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800202 NS_LOG_FUNCTION(this << prefix << face << metric);
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700203 CcnxFibEntryContainer::type::iterator entry = find (prefix);
204 if (entry == end ())
205 {
206 entry = insert (end (), CcnxFibEntry (prefix));
207 // insert new
208 }
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700209
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800210 NS_ASSERT_MSG (face != NULL, "Trying to modify NULL face");
Alexander Afanasyeva5bbe0e2011-11-22 17:28:39 -0800211 modify (entry,
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800212 ll::bind (&CcnxFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Ilya Moiseenko00b30482011-11-15 17:58:00 -0800213
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700214 return entry;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700215}
Ilya Moiseenko4e473482011-10-31 17:58:14 -0700216
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800217void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800218CcnxFib::Remove (const CcnxFibEntry &entry, Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800219{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800220 NS_LOG_FUNCTION (this);
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800221
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800222 modify (iterator_to (entry),
223 ll::bind (&CcnxFibEntry::RemoveFace, ll::_1, face));
224 if (entry.m_faces.size () == 0)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800225 {
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800226 erase (iterator_to (entry));
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800227 }
228}
229
230void
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800231CcnxFib::RemoveFromAll (Ptr<CcnxFace> face)
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800232{
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800233 NS_LOG_FUNCTION (this);
234
235 for_each (begin (), end (), ll::bind (&CcnxFib::Remove, this, ll::_1, face));
236 // BOOST_FOREACH (const CcnxFibEntry &entry, *this)
237 // {
238 // Remove (entry, face);
239 // }
Alexander Afanasyev09c7deb2011-11-23 14:50:10 -0800240}
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700241
Alexander Afanasyev19426ef2011-11-23 20:55:28 -0800242
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700243std::ostream& operator<< (std::ostream& os, const CcnxFib &fib)
244{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700245 os << "Node " << Names::FindName (fib.m_node) << "\n";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700246 os << " Dest prefix Interfaces(Costs) \n";
247 os << "+-------------+--------------------------------------+\n";
248
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700249 for (CcnxFibEntryContainer::type::iterator entry = fib.begin ();
250 entry != fib.end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700251 entry++)
252 {
253 os << *entry << "\n";
254 }
255 return os;
256}
257
258std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry)
259{
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700260 os << *entry.m_prefix << "\t";
261
262 for (CcnxFibFaceMetricContainer::type::index<i_nth>::type::iterator metric =
263 entry.m_faces.get<i_nth> ().begin ();
264 metric != entry.m_faces.get<i_nth> ().end ();
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700265 metric++)
266 {
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700267 if (metric != entry.m_faces.get<i_nth> ().begin ())
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700268 os << ", ";
269
270 os << *metric;
271 }
272 return os;
273}
274
275std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric)
276{
277 static const std::string statusString[] = {"","g","y","r"};
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700278
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700279 os << *metric.m_face << "(" << metric.m_routingCost << ","<< statusString [metric.m_status] << ")";
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700280 return os;
281}
282
283// void CcnxFib::resetProbing()
284// {
285// for(FibRangeIterator fib = _fib.begin(); fib != _fib.end(); fib++)
286// VALUE(fib).needsProbing = true;
287// }
288
289// void CcnxFib::updateInterfaceStatus( int interface, int status )
290// {
291// for( FibRangeIterator fib = _fib.begin(); fib!=_fib.end(); fib++ )
292// {
293// VALUE(fib).updateStatus( interface, status );
294// }
295// }
296
297} // namespace ns3