blob: 93afbeb580b8a79f57c8b3344748a8c40c41a33b [file] [log] [blame]
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -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 * Ilya Moiseenko <iliamo@cs.ucla.edu>
20 */
21
22#include "ccnx-forwarding-strategy.h"
23
24#include "ns3/ccnx-pit.h"
25#include "ns3/ccnx-pit-entry.h"
26#include "ns3/ccnx-interest-header.h"
27#include "ns3/ccnx-content-object-header.h"
28#include "ns3/ccnx-pit.h"
29#include "ns3/ccnx-fib.h"
30#include "ns3/ccnx-content-store.h"
Alexander Afanasyevf249a192012-07-18 16:52:51 -070031#include "ns3/ccnx-face.h"
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -070032
33#include "ns3/assert.h"
34#include "ns3/ptr.h"
35#include "ns3/log.h"
36#include "ns3/simulator.h"
37#include "ns3/boolean.h"
38#include "ns3/string.h"
39
40#include <boost/ref.hpp>
41#include <boost/foreach.hpp>
42#include <boost/lambda/lambda.hpp>
43#include <boost/lambda/bind.hpp>
44#include <boost/tuple/tuple.hpp>
45namespace ll = boost::lambda;
46
47NS_LOG_COMPONENT_DEFINE ("CcnxForwardingStrategy");
48
49namespace ns3 {
50
51using namespace __ccnx_private;
52
53NS_OBJECT_ENSURE_REGISTERED (CcnxForwardingStrategy);
54
55TypeId CcnxForwardingStrategy::GetTypeId (void)
56{
57 static TypeId tid = TypeId ("ns3::CcnxForwardingStrategy")
58 .SetGroupName ("Ccnx")
59 .SetParent<Object> ()
60
61 ////////////////////////////////////////////////////////////////////
62 ////////////////////////////////////////////////////////////////////
63
64 .AddTraceSource ("OutInterests", "OutInterests", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_outInterests))
65 .AddTraceSource ("InInterests", "InInterests", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_inInterests))
66 .AddTraceSource ("DropInterests", "DropInterests", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_dropInterests))
67
68 ////////////////////////////////////////////////////////////////////
69 ////////////////////////////////////////////////////////////////////
70
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -070071 .AddTraceSource ("OutData", "OutData", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_outData))
72 .AddTraceSource ("InData", "InData", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_inData))
73 .AddTraceSource ("DropData", "DropData", MakeTraceSourceAccessor (&CcnxForwardingStrategy::m_dropData))
74
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -070075 .AddAttribute ("CacheUnsolicitedData", "Cache overheard data that have not been requested",
76 BooleanValue (false),
77 MakeBooleanAccessor (&CcnxForwardingStrategy::m_cacheUnsolicitedData),
78 MakeBooleanChecker ())
79
Alexander Afanasyev996b4872012-07-17 17:07:56 -070080 .AddAttribute ("DetectRetransmissions", "If non-duplicate interest is received on the same face more than once, "
81 "it is considered a retransmission",
82 BooleanValue (true),
83 MakeBooleanAccessor (&CcnxForwardingStrategy::m_detectRetransmissions),
84 MakeBooleanChecker ())
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -070085 ;
86 return tid;
87}
88
89CcnxForwardingStrategy::CcnxForwardingStrategy ()
90{
91}
92
93CcnxForwardingStrategy::~CcnxForwardingStrategy ()
94{
95}
96
97void
98CcnxForwardingStrategy::NotifyNewAggregate ()
99{
100 if (m_pit == 0)
101 {
102 m_pit = GetObject<CcnxPit> ();
103 }
104 if (m_fib == 0)
105 {
106 m_fib = GetObject<CcnxFib> ();
107 }
108 if (m_contentStore == 0)
109 {
110 m_contentStore = GetObject<CcnxContentStore> ();
111 }
112
113 Object::NotifyNewAggregate ();
114}
115
116void
117CcnxForwardingStrategy::DoDispose ()
118{
119 m_pit = 0;
120 m_contentStore = 0;
121 m_fib = 0;
122
123 Object::DoDispose ();
124}
125
126void
127CcnxForwardingStrategy::OnInterest (const Ptr<CcnxFace> &incomingFace,
128 Ptr<CcnxInterestHeader> &header,
129 const Ptr<const Packet> &packet)
130{
131 m_inInterests (header, incomingFace);
132
133 Ptr<CcnxPitEntry> pitEntry = m_pit->Lookup (*header);
134 if (pitEntry == 0)
135 {
136 pitEntry = m_pit->Create (header);
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700137 if (pitEntry != 0)
138 {
139 DidCreatePitEntry (incomingFace, header, packet, pitEntry);
140 }
141 else
142 {
143 FailedToCreatePitEntry (incomingFace, header, packet);
144 return;
145 }
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700146 }
147
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700148 bool isDuplicated = true;
149 if (!pitEntry->IsNonceSeen (header->GetNonce ()))
150 {
151 pitEntry->AddSeenNonce (header->GetNonce ());
152 isDuplicated = false;
153 }
154
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700155 if (isDuplicated)
156 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700157 DidReceiveDuplicateInterest (incomingFace, header, packet, pitEntry);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700158 return;
159 }
160
161 Ptr<Packet> contentObject;
162 Ptr<const CcnxContentObjectHeader> contentObjectHeader; // used for tracing
163 Ptr<const Packet> payload; // used for tracing
164 boost::tie (contentObject, contentObjectHeader, payload) = m_contentStore->Lookup (header);
165 if (contentObject != 0)
166 {
167 NS_ASSERT (contentObjectHeader != 0);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700168
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700169 pitEntry->AddIncoming (incomingFace/*, Seconds (1.0)*/);
Alexander Afanasyevf249a192012-07-18 16:52:51 -0700170
171 // Do data plane performance measurements
172 WillSatisfyPendingInterest (0, pitEntry);
173
174 // Actually satisfy pending interest
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700175 SatisfyPendingInterest (0, contentObjectHeader, payload, contentObject, pitEntry);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700176 return;
177 }
178
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700179 if (ShouldSuppressIncomingInterest (incomingFace, pitEntry))
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700180 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700181 pitEntry->AddIncoming (incomingFace/*, header->GetInterestLifetime ()*/);
182 // update PIT entry lifetime
183 pitEntry->UpdateLifetime (header->GetInterestLifetime ());
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700184
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700185 // Suppress this interest if we're still expecting data from some other face
186 NS_LOG_DEBUG ("Suppress interests");
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700187 m_dropInterests (header, incomingFace);
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700188 return;
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700189 }
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700190
191 PropagateInterest (incomingFace, header, packet, pitEntry);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700192}
193
194void
195CcnxForwardingStrategy::OnData (const Ptr<CcnxFace> &incomingFace,
196 Ptr<CcnxContentObjectHeader> &header,
197 Ptr<Packet> &payload,
198 const Ptr<const Packet> &packet)
199{
200 NS_LOG_FUNCTION (incomingFace << header->GetName () << payload << packet);
201 m_inData (header, payload, incomingFace);
202
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700203 // Lookup PIT entry
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700204 Ptr<CcnxPitEntry> pitEntry = m_pit->Lookup (*header);
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700205 if (pitEntry == 0)
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700206 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700207 DidReceiveUnsolicitedData (incomingFace, header, payload);
208 return;
209 }
210 else
211 {
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700212 // Add or update entry in the content store
213 m_contentStore->Add (header, payload);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700214 }
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700215
216 while (pitEntry != 0)
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700217 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700218 // Do data plane performance measurements
219 WillSatisfyPendingInterest (incomingFace, pitEntry);
220
221 // Actually satisfy pending interest
222 SatisfyPendingInterest (incomingFace, header, payload, packet, pitEntry);
223
224 // Lookup another PIT entry
225 pitEntry = m_pit->Lookup (*header);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700226 }
227}
228
229
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700230void
231CcnxForwardingStrategy::DidReceiveDuplicateInterest (const Ptr<CcnxFace> &incomingFace,
232 Ptr<CcnxInterestHeader> &header,
233 const Ptr<const Packet> &packet,
234 Ptr<CcnxPitEntry> pitEntry)
235{
Alexander Afanasyeve288d8b2012-07-20 15:35:17 -0700236 NS_LOG_FUNCTION (this << boost::cref (*incomingFace));
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700237 /////////////////////////////////////////////////////////////////////////////////////////
238 // //
239 // !!!! IMPORTANT CHANGE !!!! Duplicate interests will create incoming face entry !!!! //
240 // //
241 /////////////////////////////////////////////////////////////////////////////////////////
242 pitEntry->AddIncoming (incomingFace);
243 m_dropInterests (header, incomingFace);
244}
245
246void
247CcnxForwardingStrategy::DidExhaustForwardingOptions (const Ptr<CcnxFace> &incomingFace,
248 Ptr<CcnxInterestHeader> header,
249 const Ptr<const Packet> &packet,
250 Ptr<CcnxPitEntry> pitEntry)
251{
Alexander Afanasyeve288d8b2012-07-20 15:35:17 -0700252 NS_LOG_FUNCTION (this << boost::cref (*incomingFace));
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700253 m_dropInterests (header, incomingFace);
254}
255
256void
257CcnxForwardingStrategy::FailedToCreatePitEntry (const Ptr<CcnxFace> &incomingFace,
258 Ptr<CcnxInterestHeader> header,
259 const Ptr<const Packet> &packet)
260{
261 NS_LOG_FUNCTION (this);
262 m_dropInterests (header, incomingFace);
263}
264
265void
266CcnxForwardingStrategy::DidCreatePitEntry (const Ptr<CcnxFace> &incomingFace,
267 Ptr<CcnxInterestHeader> header,
268 const Ptr<const Packet> &packet,
269 Ptr<CcnxPitEntry> pitEntrypitEntry)
270{
271}
272
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700273bool
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700274CcnxForwardingStrategy::DetectRetransmittedInterest (const Ptr<CcnxFace> &incomingFace,
275 Ptr<CcnxPitEntry> pitEntry)
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700276{
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700277 CcnxPitEntry::in_iterator inFace = pitEntry->GetIncoming ().find (incomingFace);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700278
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700279 bool isRetransmitted = false;
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700280
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700281 if (inFace != pitEntry->GetIncoming ().end ())
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700282 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700283 // this is almost definitely a retransmission. But should we trust the user on that?
284 isRetransmitted = true;
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700285 }
286
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700287 return isRetransmitted;
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700288}
289
290void
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700291CcnxForwardingStrategy::SatisfyPendingInterest (const Ptr<CcnxFace> &incomingFace,
292 Ptr<const CcnxContentObjectHeader> header,
293 Ptr<const Packet> payload,
294 const Ptr<const Packet> &packet,
295 Ptr<CcnxPitEntry> pitEntry)
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700296{
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700297 if (incomingFace != 0)
298 pitEntry->RemoveIncoming (incomingFace);
299
300 //satisfy all pending incoming Interests
301 BOOST_FOREACH (const CcnxPitEntryIncomingFace &incoming, pitEntry->GetIncoming ())
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700302 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700303 incoming.m_face->Send (packet->Copy ());
304 m_outData (header, payload, false, incoming.m_face);
305 NS_LOG_DEBUG ("Satisfy " << *incoming.m_face);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700306
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700307 // successfull forwarded data trace
308 }
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700309
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700310 // All incoming interests are satisfied. Remove them
311 pitEntry->ClearIncoming ();
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700312
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700313 // Remove all outgoing faces
314 pitEntry->ClearOutgoing ();
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700315
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700316 // Set pruning timout on PIT entry (instead of deleting the record)
317 m_pit->MarkErased (pitEntry);
318}
319
320void
321CcnxForwardingStrategy::DidReceiveUnsolicitedData (const Ptr<CcnxFace> &incomingFace,
322 Ptr<const CcnxContentObjectHeader> header,
323 Ptr<const Packet> payload)
324{
325 if (m_cacheUnsolicitedData)
326 {
327 // Optimistically add or update entry in the content store
328 m_contentStore->Add (header, payload);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700329 }
330 else
331 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700332 // Drop data packet if PIT entry is not found
333 // (unsolicited data packets should not "poison" content store)
334
335 //drop dulicated or not requested data packet
336 m_dropData (header, payload, incomingFace);
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700337 }
338}
339
340void
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700341CcnxForwardingStrategy::WillSatisfyPendingInterest (const Ptr<CcnxFace> &incomingFace,
342 Ptr<CcnxPitEntry> pitEntry)
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700343{
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700344 CcnxPitEntry::out_iterator out = pitEntry->GetOutgoing ().find (incomingFace);
345
346 // If we have sent interest for this data via this face, then update stats.
347 if (out != pitEntry->GetOutgoing ().end ())
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700348 {
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700349 pitEntry->GetFibEntry ()->UpdateFaceRtt (incomingFace, Simulator::Now () - out->m_sendTime);
350 }
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700351}
352
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700353bool
354CcnxForwardingStrategy::ShouldSuppressIncomingInterest (const Ptr<CcnxFace> &incomingFace,
355 Ptr<CcnxPitEntry> pitEntry)
356{
357 bool isNew = pitEntry->GetIncoming ().size () == 0 && pitEntry->GetOutgoing ().size () == 0;
358
359 if (isNew) return false; // never suppress new interests
360
361 bool isRetransmitted = m_detectRetransmissions && // a small guard
362 DetectRetransmittedInterest (incomingFace, pitEntry);
363
364 if (pitEntry->GetOutgoing ().find (incomingFace) != pitEntry->GetOutgoing ().end ())
365 {
366 NS_LOG_DEBUG ("Non duplicate interests from the face we have sent interest to. Don't suppress");
367 // got a non-duplicate interest from the face we have sent interest to
368 // Probably, there is no point in waiting data from that face... Not sure yet
369
370 // If we're expecting data from the interface we got the interest from ("producer" asks us for "his own" data)
371 // Mark interface YELLOW, but keep a small hope that data will come eventually.
372
373 // ?? not sure if we need to do that ?? ...
374
375 // pitEntry->GetFibEntry ()->UpdateStatus (incomingFace, CcnxFibFaceMetric::NDN_FIB_YELLOW);
376 }
377 else
378 if (!isNew && !isRetransmitted)
379 {
380 return true;
381 }
382
383 return false;
384}
385
386void
387CcnxForwardingStrategy::PropagateInterest (const Ptr<CcnxFace> &incomingFace,
Alexander Afanasyevf249a192012-07-18 16:52:51 -0700388 Ptr<CcnxInterestHeader> header,
Alexander Afanasyev996b4872012-07-17 17:07:56 -0700389 const Ptr<const Packet> &packet,
390 Ptr<CcnxPitEntry> pitEntry)
391{
392 bool isRetransmitted = m_detectRetransmissions && // a small guard
393 DetectRetransmittedInterest (incomingFace, pitEntry);
394
395 pitEntry->AddIncoming (incomingFace/*, header->GetInterestLifetime ()*/);
396 /// @todo Make lifetime per incoming interface
397 pitEntry->UpdateLifetime (header->GetInterestLifetime ());
398
399 bool propagated = DoPropagateInterest (incomingFace, header, packet, pitEntry);
400
401 if (!propagated && isRetransmitted) //give another chance if retransmitted
402 {
403 // increase max number of allowed retransmissions
404 pitEntry->IncreaseAllowedRetxCount ();
405
406 // try again
407 propagated = DoPropagateInterest (incomingFace, header, packet, pitEntry);
408 }
409
410 // ForwardingStrategy will try its best to forward packet to at least one interface.
411 // If no interests was propagated, then there is not other option for forwarding or
412 // ForwardingStrategy failed to find it.
413 if (!propagated && pitEntry->GetOutgoing ().size () == 0)
414 {
415 DidExhaustForwardingOptions (incomingFace, header, packet, pitEntry);
416 }
417}
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700418
Alexander Afanasyevf249a192012-07-18 16:52:51 -0700419bool
420CcnxForwardingStrategy::WillSendOutInterest (const Ptr<CcnxFace> &outgoingFace,
421 Ptr<CcnxInterestHeader> header,
422 Ptr<CcnxPitEntry> pitEntry)
423{
424 CcnxPitEntryOutgoingFaceContainer::type::iterator outgoing =
425 pitEntry->GetOutgoing ().find (outgoingFace);
426
427 if (outgoing != pitEntry->GetOutgoing ().end () &&
428 outgoing->m_retxCount >= pitEntry->GetMaxRetxCount ())
429 {
430 NS_LOG_ERROR (outgoing->m_retxCount << " >= " << pitEntry->GetMaxRetxCount ());
431 return false; // already forwarded before during this retransmission cycle
432 }
433
434
435 bool ok = outgoingFace->IsBelowLimit ();
436 if (!ok)
437 return false;
438
439 pitEntry->AddOutgoing (outgoingFace);
440 return true;
441}
442
443void
444CcnxForwardingStrategy::DidSendOutInterest (const Ptr<CcnxFace> &outgoingFace,
445 Ptr<CcnxInterestHeader> header,
446 Ptr<CcnxPitEntry> pitEntry)
447{
448 m_outInterests (header, outgoingFace);
449}
450
451void
452CcnxForwardingStrategy::WillErasePendingInterest (Ptr<CcnxPitEntry> pitEntry)
453{
454 // do nothing for now. may be need to do some logging
455}
456
Alexander Afanasyeve3d126f2012-07-16 17:07:31 -0700457} //namespace ns3