OverSim
NeighborCache.h
Go to the documentation of this file.
1 //
2 // Copyright (C) 2006 Institut fuer Telematik, Universitaet Karlsruhe (TH)
3 //
4 // This program is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU General Public License
6 // as published by the Free Software Foundation; either version 2
7 // of the License, or (at your option) any later version.
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 
26 #ifndef __NEIGHBORCACHE_H_
27 #define __NEIGHBORCACHE_H_
28 
29 #include <omnetpp.h>
30 
31 #include <map>
32 #include <cfloat>
33 #include <deque>
34 
35 #include <BaseApp.h>
36 #include <NodeHandle.h>
37 #include <CoordinateSystem.h>
38 
39 #include <Nps.h>
40 
41 #include <TreeManagement.h>
43 #include <SimpleUnderlayNCS.h>
44 
45 #include <Vivaldi.h>
46 #include <SVivaldi.h>
47 #include <SimpleNcs.h>
48 #include <ProxNodeHandle.h>
49 #include <HashFunc.h>
50 
51 
52 class GlobalStatistics;
53 class TransportAddress;
54 class RpcListener;
55 class TreeManagement;
56 class GlobalViewBuilder;
57 class DiscoveryMode;
58 
59 // Prox stuff
61  NEIGHBORCACHE_AVAILABLE, //< RTT, timeout, or unknown (no query)
62  NEIGHBORCACHE_EXACT, //< RTT or query
63  NEIGHBORCACHE_EXACT_TIMEOUT, //< RTT, timeout, or query
64  NEIGHBORCACHE_ESTIMATED, //< RTT or estimated
65  NEIGHBORCACHE_QUERY, //< only query, return unknown
66  // default
67  NEIGHBORCACHE_DEFAULT, //< available, exact, exact_timeout or estimated
68  NEIGHBORCACHE_DEFAULT_IMMEDIATELY, //< return a result immediately (available or estimated)
69  NEIGHBORCACHE_DEFAULT_QUERY //< do a query if needed (exact, exact_timeout, or query)
70 };
71 
72 class ProxListener {
73 public:
74  virtual void proxCallback(const TransportAddress& node, int rpcId,
75  cPolymorphic *contextPointer, Prox prox) = 0;
76 };
77 
78 class NeighborCache : public BaseApp
79 {
80  friend class Nps;
81  friend class SimpleUnderlayNCS;
82  friend class TreeManagement;
83  friend class GlobalViewBuilder;
84  friend class DiscoveryMode;
85 
86 private:
87  // parameters
89  //bool doDiscovery;
91  simtime_t rttExpirationTime;
92  uint32_t maxSize;
94 
95  uint32_t misses;
96  uint32_t hits;
97 
98  bool cleanupCache();
99 
100  void updateEntry(const TransportAddress& address,
101  simtime_t insertTime);
102 
107 
109 
111 
113 
116 
120 
122 
123  cMessage* landmarkTimer;
124  cMessage* cbrTimer;
125 
126  static const std::vector<double> coordsDummy;
127 
128  //Stuff needed to calculate a mean RTT to a specific node
129  void recordNcsEstimationError(const NodeHandle &handle, simtime_t rtt);
130  std::map<TransportAddress, std::vector<double> > lastAbsoluteErrorPerNode;
131  uint32_t numMsg;
136  uint32_t rttHistory;
138 
139 
141  {
142  WaitingContext() { proxListener = NULL; proxContext = NULL; };
144  cPolymorphic* context,
145  uint32_t id)
146 
147  : proxListener(listener), proxContext(context), id(id) { };
149  cPolymorphic* proxContext;
150  uint32_t id;
151  };
152  typedef std::vector<WaitingContext> WaitingContexts;
153 
154  // ping context stuff
155  bool insertNodeContext(const TransportAddress& handle,
156  cPolymorphic* context,
157  ProxListener* rpcListener,
158  int rpcId);
159 
161 
167  };
168 
169  typedef std::pair<simtime_t, NeighborCacheRttState> Rtt;
170 
171  Rtt getNodeRtt(const TransportAddress& add);
172 
173  void pingResponse(PingResponse* response, cPolymorphic* context,
174  int rpcId, simtime_t rtt);
175 
176  void pingTimeout(PingCall* call, const TransportAddress& dest,
177  cPolymorphic* context, int rpcId);
178 
179  static const double RTT_TIMEOUT_ADJUSTMENT = 1.3;
180  static const double NCS_TIMEOUT_CONSTANT = 0.350;
181 
182  void prepareOverlay();
183  void setCbrNodeId();
184 
185 protected:
187 
191  coordsInfo = NULL; };
192 
193 
195  delete coordsInfo;
196  for (uint16_t i = 0; i < waitingContexts.size(); ++i) {
197  delete waitingContexts[i].proxContext;
198  }
199  };
200 
201  simtime_t insertTime;
202  simtime_t rtt;
204  std::deque<simtime_t> lastRtts;
208 
210  };
211 
212  UNORDERED_MAP<TransportAddress, NeighborCacheEntry> neighborCache;
213  typedef UNORDERED_MAP<TransportAddress, NeighborCacheEntry>::iterator NeighborCacheIterator;
214  typedef UNORDERED_MAP<TransportAddress, NeighborCacheEntry>::const_iterator NeighborCacheConstIterator;
215 
216  std::multimap<simtime_t, TransportAddress> neighborCacheExpireMap;
217  typedef std::multimap<simtime_t, TransportAddress>::iterator neighborCacheExpireMapIterator;
218 
220 
221  void initializeApp(int stage);
222 
223  void finishApp();
224 
226 
227  void handleTimerEvent(cMessage* msg);
228 
235  void queryProx(const TransportAddress &node,
236  int rpcId,
237  ProxListener *listener,
238  cPolymorphic *contextPointer);
239 
243  bool handleRpcCall(BaseCallMessage* msg);
244 
249 
250  simtime_t getRttBasedTimeout(const NodeHandle &node);
251  simtime_t getNcsBasedTimeout(const NodeHandle &node);
252 
253  void callbackDiscoveryFinished(const TransportAddress& nearNode);
254 
255 public:
256  ~NeighborCache();
257 
258  inline bool isEnabled() { return enableNeighborCache; };
259 
261 
262  bool piggybackOwnCoords() { return (ncsPiggybackOwnCoords && ncs != NULL); };
263 
264  const AbstractNcs& getNcsAccess() const {
265  if (!ncs) throw cRuntimeError("No NCS activated");
266  else return *ncs;
267  };
268 
270 
271  uint16_t getNeighborCacheSize() { return neighborCache.size(); };
272 
273  // getter for specific node information
274  bool isEntry(const TransportAddress& node);
275  simtime_t getNodeAge(const TransportAddress& handle);
276  const NodeHandle& getNodeHandle(const TransportAddress &add);
277 
284  simtime_t getNodeTimeout(const NodeHandle &node);
285 
286  // getter for general node information
287  TransportAddress getNearestNode(uint8_t maxLayer);
288  double getAvgAbsPredictionError();
289 
290  std::vector<TransportAddress>* getClosestNodes(uint8_t number);
291  std::vector<TransportAddress>* getSpreadedNodes(uint8_t number);
292 
293  // setter for specific node information
294  void updateNode(const NodeHandle &add, simtime_t rtt,
295  const NodeHandle& srcRoute = NodeHandle::UNSPECIFIED_NODE,
296  AbstractNcsNodeInfo* ncsInfo = NULL);
297  void updateNcsInfo(const TransportAddress& node,
298  AbstractNcsNodeInfo* ncsInfo);
299  void setNodeTimeout(const TransportAddress& handle);
300 
322  Prox getProx(const TransportAddress &node,
324  int rpcId = -1,
325  ProxListener *listener = NULL,
326  cPolymorphic *contextPointer = NULL);
327 
335  Prox estimateProx(const TransportAddress &node);
336 
344 
351 
352  std::pair<simtime_t, simtime_t> getMeanVarRtt(const TransportAddress &node,
353  bool returnVar);
354 
355  friend std::ostream& operator<<(std::ostream& os,
356  const NeighborCacheEntry& entry);
357 };
358 
359 #endif
360