blob: 23e5323c86ed54435b9f1fb284b5d9d9c040b2c6 [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#ifndef _CCNX_FIB_H_
22#define _CCNX_FIB_H_
23
24#include "hash-helper.h"
25#include "ccnx-face.h"
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070026#include "ccnx.h"
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070027#include "ns3/nstime.h"
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -070028#include "ns3/simple-ref-count.h"
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -070029#include "ns3/node.h"
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070030
31#include <boost/multi_index_container.hpp>
32#include <boost/multi_index/tag.hpp>
33#include <boost/multi_index/ordered_index.hpp>
34#include <boost/multi_index/composite_key.hpp>
35#include <boost/multi_index/hashed_index.hpp>
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -070036#include <boost/multi_index/random_access_index.hpp>
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070037#include <boost/multi_index/member.hpp>
38#include <boost/multi_index/mem_fun.hpp>
39
40#include <iostream>
41
42namespace ns3 {
43
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070044class CcnxInterestHeader;
45
46/**
47 * \ingroup ccnx
48 * \brief Structure holding various parameters associated with a (FibEntry, Face) tuple
49 */
50class CcnxFibFaceMetric
51{
52public:
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070053 enum Status { NDN_FIB_GREEN = 1,
54 NDN_FIB_YELLOW = 2,
55 NDN_FIB_RED = 3 };
56public:
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070057 /**
58 * \brief Metric constructor
59 *
60 * \param face Face for which metric
61 * \param cost Initial value for routing cost
62 */
63 CcnxFibFaceMetric (Ptr<CcnxFace> face, int cost)
64 : m_face (face)
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070065 , m_status (NDN_FIB_YELLOW)
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070066 , m_routingCost (cost)
67 , m_sRtt (Seconds (0))
68 , m_rttVar (Seconds (0))
69 { }
70
71 /**
72 * \brief Comparison operator used by boost::multi_index::identity<>
73 */
74 bool
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070075 operator< (const CcnxFibFaceMetric &fm) const { return *m_face < *fm.m_face; } // return identity of the face
76
77 bool
78 operator< (const Ptr<CcnxFace> &face) const { return *m_face < *face; }
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070079
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -070080 Ptr<CcnxFace>
81 GetFace () const { return m_face; }
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -070082
83 /**
84 * \brief Unary function to recalculate smoothed RTT and RTT variation
85 * \param rttSample RTT sample
86 */
87 struct UpdateRtt
88 {
89 UpdateRtt (const Time &rttSample) : m_rttSample (rttSample) {};
90 void operator() (CcnxFibFaceMetric &entry);
91 private:
92 const Time &m_rttSample;
93 };
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -070094
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -070095private:
96 friend std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
97public:
98 Ptr<CcnxFace> m_face; ///< Face
99
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700100 Status m_status; ///< \brief Status of the next hop:
101 ///< - NDN_FIB_GREEN
102 ///< - NDN_FIB_YELLOW
103 ///< - NDN_FIB_RED
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700104
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700105 int32_t m_routingCost; ///< \brief routing protocol cost (interpretation of the value depends on the underlying routing protocol)
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700106
107 Time m_sRtt; ///< \brief smoothed round-trip time
108 Time m_rttVar; ///< \brief round-trip time variation
109};
110
111/**
112 * \ingroup ccnx
113 * \brief Typedef for indexed face container of CcnxFibEntry
114 *
115 * Currently, there are 2 indexes:
116 * - by face (used to find record and update metric)
117 * - by metric (face ranking)
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700118 * - random access index (for fast lookup on nth face). Order is
119 * maintained manually to be equal to the 'by metric' order
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700120 */
121struct CcnxFibFaceMetricContainer
122{
123 typedef boost::multi_index::multi_index_container<
124 CcnxFibFaceMetric,
125 boost::multi_index::indexed_by<
126 // For fast access to elements using CcnxFace
127 boost::multi_index::ordered_unique<
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700128 boost::multi_index::tag<__ccnx_private::i_face>,
129 boost::multi_index::member<CcnxFibFaceMetric,Ptr<CcnxFace>,&CcnxFibFaceMetric::m_face>
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700130 >,
131
132 // List of available faces ordered by (status, m_routingCost)
133 boost::multi_index::ordered_non_unique<
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700134 boost::multi_index::tag<__ccnx_private::i_metric>,
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700135 boost::multi_index::composite_key<
136 CcnxFibFaceMetric,
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700137 boost::multi_index::member<CcnxFibFaceMetric,CcnxFibFaceMetric::Status,&CcnxFibFaceMetric::m_status>,
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700138 boost::multi_index::member<CcnxFibFaceMetric,int32_t,&CcnxFibFaceMetric::m_routingCost>
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700139 >
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700140 >,
141
142 // To optimize nth candidate selection (sacrifice a little bit space to gain speed)
143 boost::multi_index::random_access<
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700144 boost::multi_index::tag<__ccnx_private::i_nth>
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700145 >
146 >
147 > type;
148};
149
150/**
151 * \ingroup ccnx
152 * \brief Structure for FIB table entry, holding indexed list of
153 * available faces and their respective metrics
154 */
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700155class CcnxFibEntry : public SimpleRefCount<CcnxFibEntry>
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700156{
157public:
158 /**
159 * \brief Constructor
160 * \param prefix Prefix for the FIB entry
161 */
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700162 CcnxFibEntry (const CcnxNameComponents &prefix)
163 : m_prefix (Create<CcnxNameComponents> (prefix))
164 , m_needsProbing (false)
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700165 { }
166
167 /**
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700168 * \brief Unary function to update status of FIB next hop
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700169 */
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700170 struct UpdateStatus
171 {
172 UpdateStatus (Ptr<CcnxFace> face, CcnxFibFaceMetric::Status status)
173 : m_face (face), m_status (status) {}
174 void operator () (CcnxFibEntry &entry);
175 private:
176 Ptr<CcnxFace> m_face;
177 CcnxFibFaceMetric::Status m_status;
178 };
179
180 /**
181 * \brief Unary function to add or update routing metric of FIB next hop
182 *
183 * Initial status of the next hop is set to YELLOW
184 */
185 struct AddOrUpdateRoutingMetric
186 {
187 AddOrUpdateRoutingMetric (Ptr<CcnxFace> face, int32_t metric)
188 : m_face (face), m_metric (metric) {}
189 void operator () (CcnxFibEntry &entry);
190 private:
191 Ptr<CcnxFace> m_face;
192 int32_t m_metric;
193 };
194
195 /**
196 * \brief Unary function to recalculate smoothed RTT and RTT variation
197 * \param rttSample RTT sample
198 */
199 struct UpdateFaceRtt
200 {
201 UpdateFaceRtt (Ptr<CcnxFace> face, const Time &rttSample)
202 : m_face (face), m_rttSample (rttSample) {};
203 void operator() (CcnxFibEntry &entry);
204 private:
205 Ptr<CcnxFace> m_face;
206 const Time &m_rttSample;
207 };
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700208
209 /**
210 * \brief Get prefix for the FIB entry
211 */
212 const CcnxNameComponents&
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700213 GetPrefix () const { return *m_prefix; }
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700214
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700215 /**
216 * \brief Find "best route" candidate, skipping `skip' first candidates (modulo # of faces)
217 */
218 Ptr<CcnxFace>
219 FindBestCandidate (int skip = 0);
220
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700221private:
222 friend std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
223
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700224public:
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700225 Ptr<CcnxNameComponents> m_prefix; ///< \brief Prefix of the FIB entry
226 CcnxFibFaceMetricContainer::type m_faces; ///< \brief Indexed list of faces
227
228 bool m_needsProbing; ///< \brief flag indicating that probing should be performed
229};
230
231///////////////////////////////////////////////////////////////////////////////
232///////////////////////////////////////////////////////////////////////////////
233
234/**
235 * \ingroup ccnx
236 * \brief Typedef for indexed container for FIB entries
237 *
238 * Currently, there is only one index
239 * - by prefix hash, which is used to perform prefix match
240 */
Alexander Afanasyeva67e28c2011-08-31 21:16:25 -0700241struct CcnxFibEntryContainer
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700242{
243 typedef boost::multi_index::multi_index_container<
244 CcnxFibEntry,
245 boost::multi_index::indexed_by<
246 // For fast access to elements using CcnxFace
247 boost::multi_index::hashed_unique<
Alexander Afanasyev78cf0c92011-09-01 19:57:14 -0700248 boost::multi_index::tag<__ccnx_private::i_prefix>,
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700249 boost::multi_index::const_mem_fun<CcnxFibEntry,
250 const CcnxNameComponents&,
Alexander Afanasyeva98cdd22011-08-29 17:32:37 -0700251 &CcnxFibEntry::GetPrefix>,
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700252 CcnxPrefixHash>
253
254 // other indexes?
255 >
256 > type;
257};
258
259/**
260 * \ingroup ccnx
261 * \brief Class implementing FIB functionality
262 */
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700263class CcnxFib : public Object, public CcnxFibEntryContainer::type
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700264{
265public:
266 /**
Alexander Afanasyevcf133f02011-09-06 12:13:48 -0700267 * \brief Interface ID
268 *
269 * \return interface ID
270 */
271 static TypeId GetTypeId ();
272
273 /**
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700274 * \brief Constructor
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700275 */
Alexander Afanasyeva67e28c2011-08-31 21:16:25 -0700276 CcnxFib ();
277 // * \param node smart pointer to Ccnx stack associated with particular node
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700278
279 // // Invalidate entries in FIB
280 // // Will leave FIB records in hash, but assign metric=NETWORK_UNREACHABLE
281 // void invalidate( );
282
283 // //Find corresponding FIB entry for the given content name
284 // //Longest match is performed
285 // FibIterator lookup( const string &name );
286 // bool isValid( const FibIterator &it ) { return it!=_fib.end(); }
287
288 /**
289 * \brief Perform longest prefix match
290 *
291 * \todo Implement exclude filters
292 *
293 * \param interest Interest packet header
Alexander Afanasyev8accdf62011-09-20 11:33:59 -0700294 * \returns If entry found a valid iterator will be returned, otherwise end ()
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700295 */
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700296 CcnxFibEntryContainer::type::iterator
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700297 LongestPrefixMatch (const CcnxInterestHeader &interest) const;
298
299 /**
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700300 * \brief Add or update FIB entry
301 *
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700302 * If the entry exists, metric will be updated. Otherwise, new entry will be created
303 *
304 * Entries in FIB never deleted. They can be invalidated with metric==NETWORK_UNREACHABLE
305 *
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700306 * @param name Prefix
307 * @param face Forwarding face
308 * @param metric Routing metric
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700309 */
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700310 CcnxFibEntryContainer::type::iterator
311 Add (const CcnxNameComponents &prefix, Ptr<CcnxFace> face, int32_t metric);
312 // bool update( const string &name, int interfaceIndex, int metric);
313 // bool update( NodeAddress nodeId, int interfaceIndex, int metric);
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700314 // Bool update( NodeAddress nodeId, int metric, NodeAddress nextHop );
315
316 // // Update Fib from OSPF routing table (through a hack in OSPF algorithm)
317 // void updateFibFromOSPFv2( int interface );
318
319 // // Update Fib from BGP routing table (using info from RibIn)
320 // void updateFibFromBGP( );
321
322 // // Update Fib from IP routing table
323 // void updateFibFromIpRouting( );
324
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700325 // void dump( );
326 // void dump( const FibIterator &fib );
327
328 // void resetProbing(); //reset needsProbing field for every FibEntry
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700329
330protected:
331 // inherited from Object class
332 virtual void NotifyNewAggregate ();
333 virtual void DoDispose ();
334
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700335private:
336 friend std::ostream& operator<< (std::ostream& os, const CcnxFib &fib);
Alexander Afanasyeva67e28c2011-08-31 21:16:25 -0700337 CcnxFib(const CcnxFib&) {} ; ///< \brief copy constructor is disabled
338
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700339private:
Alexander Afanasyevc5a23e22011-09-07 00:37:36 -0700340 Ptr<Node> m_node;
Alexander Afanasyev7fd74f92011-08-25 19:40:17 -0700341};
342
343///////////////////////////////////////////////////////////////////////////////
344///////////////////////////////////////////////////////////////////////////////
345
346std::ostream& operator<< (std::ostream& os, const CcnxFib &fib);
347std::ostream& operator<< (std::ostream& os, const CcnxFibEntry &entry);
348std::ostream& operator<< (std::ostream& os, const CcnxFibFaceMetric &metric);
349
350} // namespace ns3
351
352#endif /* NDN_FIB_H */