blob: 93fa2aa1134e4e6b8e6f29b01753e9c8f830e5ca [file] [log] [blame]
Alexander Afanasyev78057c32012-07-06 15:18:46 -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
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070021#ifndef _NDN_FIB_ENTRY_H_
22#define _NDN_FIB_ENTRY_H_
Alexander Afanasyev78057c32012-07-06 15:18:46 -070023
24#include "ns3/ptr.h"
25#include "ns3/nstime.h"
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070026#include "ns3/ndn-face.h"
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070027#include "ns3/ndn-name-components.h"
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -070028#include "ns3/ndn-limits.h"
Alexander Afanasyeve6dc0ac2013-02-21 14:00:48 -080029#include "ns3/traced-value.h"
Alexander Afanasyev78057c32012-07-06 15:18:46 -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>
36#include <boost/multi_index/random_access_index.hpp>
37#include <boost/multi_index/member.hpp>
38#include <boost/multi_index/mem_fun.hpp>
39
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070040namespace ns3 {
41namespace ndn {
Alexander Afanasyev78057c32012-07-06 15:18:46 -070042
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070043class NameComponents;
44
45namespace fib {
Alexander Afanasyev78057c32012-07-06 15:18:46 -070046
47/**
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070048 * \ingroup ndn
Alexander Afanasyev78057c32012-07-06 15:18:46 -070049 * \brief Structure holding various parameters associated with a (FibEntry, Face) tuple
50 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070051class FaceMetric
Alexander Afanasyev78057c32012-07-06 15:18:46 -070052{
53public:
54 /**
55 * @brief Color codes for FIB face status
56 */
57 enum Status { NDN_FIB_GREEN = 1,
58 NDN_FIB_YELLOW = 2,
59 NDN_FIB_RED = 3 };
60public:
61 /**
62 * \brief Metric constructor
63 *
64 * \param face Face for which metric
65 * \param cost Initial value for routing cost
66 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070067 FaceMetric (Ptr<Face> face, int32_t cost)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070068 : m_face (face)
69 , m_status (NDN_FIB_YELLOW)
70 , m_routingCost (cost)
71 , m_sRtt (Seconds (0))
72 , m_rttVar (Seconds (0))
Alexander Afanasyev6b0c88f2012-12-01 12:24:27 -080073 , m_realDelay (Seconds (0))
Alexander Afanasyev78057c32012-07-06 15:18:46 -070074 { }
75
76 /**
77 * \brief Comparison operator used by boost::multi_index::identity<>
78 */
79 bool
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070080 operator< (const FaceMetric &fm) const { return *m_face < *fm.m_face; } // return identity of the face
Alexander Afanasyev78057c32012-07-06 15:18:46 -070081
82 /**
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070083 * @brief Comparison between FaceMetric and Face
Alexander Afanasyev78057c32012-07-06 15:18:46 -070084 */
85 bool
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -080086 operator< (const Ptr<Face> &face) const { return *m_face < *face; }
Alexander Afanasyev78057c32012-07-06 15:18:46 -070087
88 /**
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070089 * @brief Return Face associated with FaceMetric
Alexander Afanasyev78057c32012-07-06 15:18:46 -070090 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070091 Ptr<Face>
Alexander Afanasyev78057c32012-07-06 15:18:46 -070092 GetFace () const { return m_face; }
93
94 /**
95 * \brief Recalculate smoothed RTT and RTT variation
96 * \param rttSample RTT sample
97 */
98 void
99 UpdateRtt (const Time &rttSample);
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800100
101 /**
102 * @brief Get current status of FIB entry
103 */
104 Status
105 GetStatus () const
106 {
107 return m_status;
108 }
109
110 /**
111 * @brief Set current status of FIB entry
112 */
113 void
114 SetStatus (Status status)
115 {
Alexander Afanasyeve6dc0ac2013-02-21 14:00:48 -0800116 m_status.Set (status);
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800117 }
118
119 /**
120 * @brief Get current routing cost
121 */
122 int32_t
123 GetRoutingCost () const
124 {
125 return m_routingCost;
126 }
127
128 /**
129 * @brief Set routing cost
130 */
131 void
132 SetRoutingCost (int32_t routingCost)
133 {
134 m_routingCost = routingCost;
135 }
136
137 /**
138 * @brief Get real propagation delay to the producer, calculated based on NS-3 p2p link delays
139 */
140 Time
141 GetRealDelay () const
142 {
143 return m_realDelay;
144 }
145
146 /**
147 * @brief Set real propagation delay to the producer, calculated based on NS-3 p2p link delays
148 */
149 void
150 SetRealDelay (Time realDelay)
151 {
152 m_realDelay = realDelay;
153 }
154
Alexander Afanasyeve6dc0ac2013-02-21 14:00:48 -0800155 /**
156 * @brief Get direct access to status trace
157 */
158 TracedValue<Status> &
159 GetStatusTrace ()
160 {
161 return m_status;
162 }
163
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700164private:
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700165 friend std::ostream& operator<< (std::ostream& os, const FaceMetric &metric);
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800166
167private:
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700168 Ptr<Face> m_face; ///< Face
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800169
Alexander Afanasyeve6dc0ac2013-02-21 14:00:48 -0800170 TracedValue<Status> m_status; ///< \brief Status of the next hop:
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700171 ///< - NDN_FIB_GREEN
172 ///< - NDN_FIB_YELLOW
173 ///< - NDN_FIB_RED
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800174
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700175 int32_t m_routingCost; ///< \brief routing protocol cost (interpretation of the value depends on the underlying routing protocol)
176
177 Time m_sRtt; ///< \brief smoothed round-trip time
178 Time m_rttVar; ///< \brief round-trip time variation
Alexander Afanasyev6b0c88f2012-12-01 12:24:27 -0800179
180 Time m_realDelay; ///< \brief real propagation delay to the producer, calculated based on NS-3 p2p link delays
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700181};
182
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700183/// @cond include_hidden
184class i_face {};
185class i_metric {};
186class i_nth {};
187/// @endcond
188
189
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700190/**
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700191 * \ingroup ndn
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700192 * \brief Typedef for indexed face container of Entry
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700193 *
194 * Currently, there are 2 indexes:
195 * - by face (used to find record and update metric)
196 * - by metric (face ranking)
197 * - random access index (for fast lookup on nth face). Order is
198 * maintained manually to be equal to the 'by metric' order
199 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700200struct FaceMetricContainer
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700201{
202 /// @cond include_hidden
203 typedef boost::multi_index::multi_index_container<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700204 FaceMetric,
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700205 boost::multi_index::indexed_by<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700206 // For fast access to elements using Face
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700207 boost::multi_index::ordered_unique<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700208 boost::multi_index::tag<i_face>,
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800209 boost::multi_index::const_mem_fun<FaceMetric,Ptr<Face>,&FaceMetric::GetFace>
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700210 >,
211
212 // List of available faces ordered by (status, m_routingCost)
213 boost::multi_index::ordered_non_unique<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700214 boost::multi_index::tag<i_metric>,
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700215 boost::multi_index::composite_key<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700216 FaceMetric,
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800217 boost::multi_index::const_mem_fun<FaceMetric,FaceMetric::Status,&FaceMetric::GetStatus>,
218 boost::multi_index::const_mem_fun<FaceMetric,int32_t,&FaceMetric::GetRoutingCost>
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700219 >
220 >,
221
222 // To optimize nth candidate selection (sacrifice a little bit space to gain speed)
223 boost::multi_index::random_access<
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700224 boost::multi_index::tag<i_nth>
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700225 >
226 >
227 > type;
228 /// @endcond
229};
230
231/**
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700232 * \ingroup ndn
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700233 * \brief Structure for FIB table entry, holding indexed list of
234 * available faces and their respective metrics
235 */
Alexander Afanasyevf5c07742012-10-31 13:13:05 -0700236class Entry : public Object
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700237{
238public:
Alexander Afanasyev8566f452012-12-10 15:21:51 -0800239 typedef Entry base_type;
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800240
Alexander Afanasyev8566f452012-12-10 15:21:51 -0800241public:
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700242 class NoFaces {}; ///< @brief Exception class for the case when FIB entry is not found
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800243
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700244 /**
245 * \brief Constructor
246 * \param prefix smart pointer to the prefix for the FIB entry
247 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700248 Entry (const Ptr<const NameComponents> &prefix)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700249 : m_prefix (prefix)
250 , m_needsProbing (false)
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700251 {
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700252 }
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800253
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700254 /**
255 * \brief Update status of FIB next hop
256 * \param status Status to set on the FIB entry
257 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700258 void UpdateStatus (Ptr<Face> face, FaceMetric::Status status);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700259
260 /**
261 * \brief Add or update routing metric of FIB next hop
262 *
263 * Initial status of the next hop is set to YELLOW
264 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700265 void AddOrUpdateRoutingMetric (Ptr<Face> face, int32_t metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700266
267 /**
Alexander Afanasyev6b0c88f2012-12-01 12:24:27 -0800268 * \brief Set real delay to the producer
269 */
270 void
271 SetRealDelayToProducer (Ptr<Face> face, Time delay);
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800272
Alexander Afanasyev6b0c88f2012-12-01 12:24:27 -0800273 /**
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700274 * @brief Invalidate face
275 *
276 * Set routing metric on all faces to max and status to RED
277 */
278 void
279 Invalidate ();
280
281 /**
282 * @brief Update RTT averages for the face
283 */
284 void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700285 UpdateFaceRtt (Ptr<Face> face, const Time &sample);
Alexander Afanasyev06dba7c2013-02-21 11:36:26 -0800286
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700287 /**
288 * \brief Get prefix for the FIB entry
289 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700290 const NameComponents&
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700291 GetPrefix () const { return *m_prefix; }
292
293 /**
294 * \brief Find "best route" candidate, skipping `skip' first candidates (modulo # of faces)
295 *
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700296 * throws Entry::NoFaces if m_faces.size()==0
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700297 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700298 const FaceMetric &
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700299 FindBestCandidate (uint32_t skip = 0) const;
300
301 /**
302 * @brief Remove record associated with `face`
303 */
304 void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700305 RemoveFace (const Ptr<Face> &face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700306 {
307 m_faces.erase (face);
308 }
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700309
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700310private:
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700311 friend std::ostream& operator<< (std::ostream& os, const Entry &entry);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700312
313public:
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700314 Ptr<const NameComponents> m_prefix; ///< \brief Prefix of the FIB entry
315 FaceMetricContainer::type m_faces; ///< \brief Indexed list of faces
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700316
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700317 bool m_needsProbing; ///< \brief flag indicating that probing should be performed
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700318};
319
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700320std::ostream& operator<< (std::ostream& os, const Entry &entry);
321std::ostream& operator<< (std::ostream& os, const FaceMetric &metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700322
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700323} // namespace fib
324} // namespace ndn
325} // namespace ns3
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700326
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700327#endif // _NDN_FIB_ENTRY_H_