1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
// Define classes for routing table representation and lookup
// George F. Riley, Georgia Tech, Winter 2000
// Defines several variations on routing table representations
// and a method to determine the most memory efficient.
#ifndef __RLOOKUP_H__
#define __RLOOKUP_H__
#include "routealgo/rnode.h"
#include "routealgo/rbitmap.h"
#include <iostream>
#ifdef USE_HASH_MAP
#include <hash_map>
#include <hash_set>
#else
#include <map>
#include <set>
#endif
typedef enum {
RL_NULL, RL_FIXED, RL_BITMAP, RL_HASH, RL_NEXTHOP, RL_LAST}
RLookup_Types;
typedef pair<nodeid_t, nodeid_t> LookupPair_t; // Node/NextHop Pair
// Define an abstract base class that specifies functionality needed
class RLookup {
public :
RLookup();
virtual ~RLookup();
virtual RLookup_Types WhatType() const = 0; // Identifies the type of lookup
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE) // Last non-default
= 0;
virtual void Populate(istream& is); // Populate from log
virtual nodeid_t Lookup(nodeid_t) = 0; // Return next hop given target
virtual size_t Size() = 0; // Estimate size
virtual size_t NumberEntries(){return 0;} // Number of entries in table
virtual void Log( ostream&); // Log to ostream
static void Analyze(RoutingVec_t&,
RoutingVec_t&, // Population counts
nodeid_t&, nodeid_t&, nodeid_t, nodeid_t&,nodeid_t&);
// friend ostream& operator<<(ostream&, const RLookup& ); // Output a routing table
};
// The "Null" lookup is used when there is no routing table.
// Handles the pathological case for a node with no neighbors
class NOLookup : public RLookup {
public :
NOLookup();
virtual ~NOLookup();
virtual RLookup_Types WhatType() const;
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE);// Last non-default
virtual nodeid_t Lookup(nodeid_t);
virtual size_t Size();
virtual void Log( ostream&); // Log to ostream
};
// The "Fixed" lookup is used when all routes are the same
// Will always be the case for "leaf" nodes with only one neighbor
class FRLookup : public RLookup {
public :
FRLookup();
virtual ~FRLookup();
nodeid_t Default() const { return m_Default;}
virtual RLookup_Types WhatType() const;
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE);// Last non-default
virtual nodeid_t Lookup(nodeid_t);
virtual size_t Size();
virtual void Log( ostream&); // Log to ostream
static size_t EstimateSize(
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d, // Default route
nodeid_t n, // Number default
nodeid_t o, // Routing table owner
nodeid_t f, // First non-default
nodeid_t l); // Last non-default
// friend ostream& operator<<(ostream&, const FRLookup& ); // Output a routing table
private:
nodeid_t m_Default;
};
// The "Bitmap" lookup is used when there are many "default" entries
// and a few non-defaults clustered in a small range
class BMLookup : public RLookup {
public :
BMLookup();
virtual ~BMLookup();
virtual RLookup_Types WhatType() const; // Identifies the type of lookup
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE);// Last non-default
virtual nodeid_t Lookup(nodeid_t);
virtual size_t Size();
virtual size_t NumberEntries(); // Number of entries in table
virtual void Log( ostream&); // Log to ostream
static size_t EstimateSize(
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d, // Default route
nodeid_t n, // Number default
nodeid_t o, // Routing table owner
nodeid_t f, // First non-default
nodeid_t l); // Last non-default
// friend ostream& operator<<(ostream&, const BMLookup& ); // Output a bitmap routing table
private:
nodeid_t m_Default;
nodeid_t m_FirstNonDefault;
nodeid_t m_LastNonDefault;
RoutingVec_t m_NVec; // Neighbor vector
BitMap* m_pBitMap; // Bitmap of non-default entries
};
// The "HashMap" lookup is used when the previous two methods do not work.
// Uses the STL "hash_map" associative container to store non-default routes.
// By default, this is OFF because hash_map is an SGI extension to STL,
// not part of standard STL.
#ifdef USE_HASH_MAP
typedef hash_map<nodeid_t, nodeid_t,
hash<nodeid_t>, equal_to<nodeid_t> > RouteMap_t;
#else
typedef map<nodeid_t, nodeid_t, equal_to<nodeid_t> > RouteMap_t;
#endif
typedef RouteMap_t::iterator RouteMap_it;
typedef RouteMap_t::value_type RoutePair_t;
class HMLookup : public RLookup {
public :
HMLookup();
virtual ~HMLookup();
virtual RLookup_Types WhatType() const; // Identifies the type of lookup
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE);// Last non-default
virtual nodeid_t Lookup(nodeid_t);
virtual size_t Size();
virtual size_t NumberEntries(); // Number of entries in table
virtual void Log( ostream&); // Log to ostream
static size_t EstimateSize(
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d, // Default route
nodeid_t n, // Number default
nodeid_t o, // Routing table owner
nodeid_t f, // First non-default
nodeid_t l); // Last non-default
// friend ostream& operator<<(ostream&, const HMLookup& ); // Output a routing table
private:
nodeid_t m_Default;
RouteMap_t m_RouteMap;
};
// Also included is the "inefficient" version for memory usage comparisons
// NHLookup (NextHop) lookup just stores the next hop in a lookup array
class NHLookup : public RLookup {
public :
NHLookup();
virtual ~NHLookup();
virtual RLookup_Types WhatType() const; // Identifies the type of lookup
virtual void Populate( // Popluate the table
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d = NODE_NONE, // Default route
nodeid_t o = NODE_NONE, // Routing table owner
nodeid_t f = NODE_NONE, // First non-default
nodeid_t l = NODE_NONE);// Last non-default
virtual void Populate(istream& is); // Populate from log
virtual nodeid_t Lookup(nodeid_t);
virtual size_t Size();
virtual size_t NumberEntries(); // Number of entries in table
virtual void Log( ostream&); // Log to ostream
static size_t EstimateSize(
RoutingVec_t& r, // NextHop table
RoutingVec_t& p, // Population counts
nodeid_t d, // Default route
nodeid_t n, // Number default
nodeid_t o, // Routing table owner
nodeid_t f, // First non-default
nodeid_t l); // Last non-default
private:
RoutingVec_t m_RouteTable;
};
#endif
|
