|
1 |
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 |
/* |
3 |
* This program is free software; you can redistribute it and/or modify |
4 |
* it under the terms of the GNU General Public License version 2 as |
5 |
* published by the Free Software Foundation; |
6 |
* |
7 |
* This program is distributed in the hope that it will be useful, |
8 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
9 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
10 |
* GNU General Public License for more details. |
11 |
* |
12 |
* You should have received a copy of the GNU General Public License |
13 |
* along with this program; if not, write to the Free Software |
14 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
15 |
*/ |
16 |
|
17 |
|
18 |
#include "ns3/point-to-point-tree.h" |
19 |
#include "ns3/ptr.h" |
20 |
#include "ns3/point-to-point-star.h" |
21 |
#include "ns3/node.h" |
22 |
#include "ns3/node-container.h" |
23 |
#include "ns3/log.h" |
24 |
#include "ns3/constant-position-mobility-model.h" |
25 |
#include <cmath> |
26 |
|
27 |
namespace ns3 { |
28 |
|
29 |
NS_LOG_COMPONENT_DEFINE("PointToPointTreeHelper"); |
30 |
NS_OBJECT_ENSURE_REGISTERED (PointToPointTreeHelper); |
31 |
|
32 |
TypeId |
33 |
PointToPointTreeHelper::GetTypeId (void) |
34 |
{ |
35 |
static TypeId tid = TypeId ("ns3::PointToPointTreeHelper") |
36 |
.SetParent<Object> () |
37 |
.AddConstructor<PointToPointTreeHelper> () |
38 |
; |
39 |
return tid; |
40 |
} |
41 |
|
42 |
|
43 |
|
44 |
PointToPointTreeHelper::PointToPointTreeHelper ( |
45 |
uint32_t num_levels, |
46 |
uint32_t fan_out, |
47 |
PointToPointHelper p2pHelper |
48 |
) :m_num_levels (num_levels),m_fan_out (ConstantVariable (fan_out)) |
49 |
{ |
50 |
CreateTopologyHelper (num_levels, p2pHelper); |
51 |
} |
52 |
|
53 |
PointToPointTreeHelper::PointToPointTreeHelper( |
54 |
uint32_t num_levels, |
55 |
RandomVariable rv, |
56 |
PointToPointHelper p2pHelper |
57 |
) :m_num_levels (num_levels),m_fan_out (rv) |
58 |
{ |
59 |
CreateTopologyHelper (num_levels, p2pHelper); |
60 |
} |
61 |
|
62 |
PointToPointTreeHelper::PointToPointTreeHelper () |
63 |
{ |
64 |
} |
65 |
|
66 |
void |
67 |
PointToPointTreeHelper::CreateTopologyHelper (uint32_t num_levels, PointToPointHelper p2pHelper) |
68 |
{ |
69 |
if (num_levels <= 0) |
70 |
{ |
71 |
NS_LOG_WARN ("Number of levels:"<<num_levels<<"<=0\nNo Topology created"); |
72 |
} |
73 |
|
74 |
m_root_node.Create (1); |
75 |
NS_LOG_INFO ("Root Node created"); |
76 |
|
77 |
for (uint32_t i = 0 ; i < num_levels ; i++) |
78 |
{ |
79 |
PerLevelNodeContainer.push_back (NodeContainer()); |
80 |
} |
81 |
PerLevelNodeContainer[0] = m_root_node; //level 0 container has root node |
82 |
NS_LOG_INFO ("Begin creating levels starting from level 1"); |
83 |
AddStarTopologyRecursively (m_root_node,1,p2pHelper); //Start from level 1, as root node is at level 0 |
84 |
|
85 |
} |
86 |
|
87 |
void |
88 |
PointToPointTreeHelper::AddStarTopologyRecursively (NodeContainer parent_node, uint32_t level, PointToPointHelper p2pHelper) |
89 |
{ |
90 |
uint32_t fan_out = m_fan_out.GetInteger (); |
91 |
Ptr<PointToPointStarHelper> star_helper ; |
92 |
if (level >= this->m_num_levels) |
93 |
{ |
94 |
NS_LOG_INFO ("Begin creating levels starting from level 1"); |
95 |
return; |
96 |
} |
97 |
|
98 |
star_helper = parent_node.Get (0)->GetObject<PointToPointStarHelper> (); |
99 |
if (star_helper == 0) |
100 |
{ |
101 |
star_helper = CreateObject<PointToPointStarHelper> (parent_node,fan_out,p2pHelper); |
102 |
PerLevelNodeContainer[level].Add (star_helper->GetSpokeNodes()); |
103 |
parent_node.Get (0)->AggregateObject (star_helper); |
104 |
NS_LOG_INFO ("After aggregating star to parent node Id:"<<parent_node.Get(0)->GetId()<<" with fan out="<<fan_out); |
105 |
} |
106 |
else |
107 |
{ |
108 |
NS_FATAL_ERROR ("Node Id:"<< parent_node.Get (0)->GetId ()<<" Already contains a star set"); |
109 |
} |
110 |
level++; |
111 |
for (uint32_t i = 0 ; i < fan_out ; i++) |
112 |
{ |
113 |
NS_LOG_INFO ("Before star for parent node Id:"<<parent_node.Get(0)->GetId()<<" with fan out="<<fan_out); |
114 |
AddStarTopologyRecursively (star_helper->GetSpokeNode (i),level,p2pHelper); |
115 |
} |
116 |
} |
117 |
|
118 |
PointToPointTreeHelper::~PointToPointTreeHelper () |
119 |
{ |
120 |
} |
121 |
|
122 |
Ptr<Node> |
123 |
PointToPointTreeHelper::GetNode (uint32_t level, uint32_t index) |
124 |
{ |
125 |
if (level >= m_num_levels) |
126 |
{ |
127 |
NS_LOG_WARN ("Requested level:"<<level<<" Does not exist"); |
128 |
return NULL; |
129 |
} |
130 |
if (index >= PerLevelNodeContainer[level].GetN ()) |
131 |
{ |
132 |
NS_LOG_WARN ("Requested index:"<<index<<" Does not exist"); |
133 |
return NULL; |
134 |
} |
135 |
return PerLevelNodeContainer[level].Get (index); |
136 |
} |
137 |
|
138 |
|
139 |
NodeContainer |
140 |
PointToPointTreeHelper::GetLeaves () |
141 |
{ |
142 |
return PerLevelNodeContainer[m_num_levels-1]; |
143 |
} |
144 |
|
145 |
void |
146 |
PointToPointTreeHelper::InstallStack (InternetStackHelper stack) |
147 |
{ |
148 |
for (uint32_t i = 0; i < m_num_levels ; i++) |
149 |
{ |
150 |
stack.Install(PerLevelNodeContainer[i]); |
151 |
} |
152 |
} |
153 |
|
154 |
|
155 |
Ipv4Address |
156 |
PointToPointTreeHelper::GetLeafIpv4Address (uint32_t leaf_index) |
157 |
{ |
158 |
//Get hub(parent) of the leaf node |
159 |
//Get The node container for penultimate level |
160 |
//The penultimate levels carries the leaves |
161 |
NodeContainer nc = PerLevelNodeContainer [m_num_levels-2]; |
162 |
Ptr<Node> n = NULL ; |
163 |
Ptr<PointToPointStarHelper> star_helper = NULL; |
164 |
|
165 |
// Go through each node on the penultimate level |
166 |
// Obtained the star topology aggregated with each node |
167 |
// Check if the leaf index falls within the spoke count of each star |
168 |
for (uint32_t i = 0 ; i < nc.GetN ();i++) |
169 |
{ |
170 |
n = nc.Get (i); |
171 |
NS_ASSERT (n); |
172 |
star_helper = n->GetObject<PointToPointStarHelper> (); |
173 |
if (star_helper == 0) |
174 |
{ |
175 |
NS_LOG_WARN ("This tree is perhaps has only one node."); |
176 |
// This can happen due to a bug, or if only one node exists |
177 |
// in tree (not really a tree in that case!!) |
178 |
// This can also happen if the user desired random fan out |
179 |
// which chose '0' as a fan out |
180 |
} |
181 |
else |
182 |
{ |
183 |
// The leaf index does not belong to this star |
184 |
if (leaf_index > star_helper->SpokeCount ()-1) |
185 |
{ |
186 |
n = NULL ; |
187 |
leaf_index -= star_helper->SpokeCount (); |
188 |
continue; |
189 |
} |
190 |
else |
191 |
{ |
192 |
// Found the star |
193 |
break; |
194 |
} |
195 |
} |
196 |
} //for loop |
197 |
NS_ASSERT (n); |
198 |
NS_ASSERT (star_helper); |
199 |
|
200 |
// Found the desired star |
201 |
return star_helper->GetSpokeIpv4Address (leaf_index); |
202 |
} |
203 |
|
204 |
// A helper function that extends a massk, based on the number of subnets required |
205 |
// Examples: given a mask such as /8, if 3 subnets are required, the mask has to be |
206 |
// extended to /10 |
207 |
|
208 |
Ipv4Mask |
209 |
PointToPointTreeHelper::ExtendMaskForSubnets (Ipv4Mask original_mask, uint32_t subnets_required) |
210 |
{ |
211 |
// If the original mask is already /31 and over we cannot allocate any more subnets |
212 |
if (subnets_required) |
213 |
NS_ASSERT (original_mask.GetPrefixLength () <=30); |
214 |
|
215 |
uint8_t num_additional_subnet_bits = 0;//number of additional subnet bits required |
216 |
for (uint32_t i = 0 ; i < 31 ; i++) //30 is maximum subnets |
217 |
{ |
218 |
if( pow (2.0,static_cast<int> (i)) >= subnets_required) |
219 |
{ |
220 |
num_additional_subnet_bits = i ; |
221 |
break; |
222 |
} |
223 |
} |
224 |
uint32_t tmp = 0x10000000 ; |
225 |
tmp >>= (original_mask.GetPrefixLength () - 1); //Position 1 at the last "1" bit in the mask |
226 |
uint32_t new_mask = original_mask.Get (); // Initialize new mask |
227 |
for (uint8_t i = 0 ; i < num_additional_subnet_bits ; i++) |
228 |
{ |
229 |
tmp >>= i ; // Move the 1 right for each additional subnet bit |
230 |
new_mask |= tmp; // Add the 1 to the original mask |
231 |
} |
232 |
return Ipv4Mask (new_mask); |
233 |
} |
234 |
|
235 |
/* |
236 |
The function starts with an allocated network address N and mask M |
237 |
The mask M is extended to allocate X subnets. where X is the |
238 |
number of fan out nodes/spokes nodes associated with a node |
239 |
Each allocated subnet above is further divided into 2 subnets A and B |
240 |
subnet A is used at the network between the hub and any spoke node |
241 |
subnet B will be the new network which is used by the spoke nodes |
242 |
as part of recursion |
243 |
For example: |
244 |
10.0.0.0/8 is allocated for the tree |
245 |
The Root Node [R] has 4 point-to-point links to 4 spoke nodes |
246 |
10.0.0.0/8 is divided into 4 subnets |
247 |
10.0.0.0/10, 10.64.0.0/10, 10.128.0.0/10, 10.192.0.0/10 |
248 |
|
249 |
10.0.0.0/10 is divided into 2 subnets |
250 |
10.0.0.0/11 and 10.32.0.0/11 |
251 |
|
252 |
|
253 |
o(10.32.0.1/11) |
254 |
[N1] |
255 |
o(10.0.0.2/11) |
256 |
[N3] / |
257 |
\ / |
258 |
\ / |
259 |
o o(10.0.0.1/11) |
260 |
(10.0.0.0/8) [R] |
261 |
o o(10.64.0.1/11) |
262 |
/ \ |
263 |
/ \ |
264 |
[N4] \ |
265 |
\ |
266 |
o(10.64.0.2/11) |
267 |
[N2] |
268 |
o(10.96.0.1/11) |
269 |
|
270 |
*/ |
271 |
|
272 |
void |
273 |
PointToPointTreeHelper::AssignIpv4AddressHierarchicalRecursiveHelper (Ptr<Node> n, Ipv4Address network, Ipv4Mask allocated_mask) |
274 |
{ |
275 |
Ptr<PointToPointStarHelper> star_helper ; |
276 |
star_helper = n->GetObject<PointToPointStarHelper> (); |
277 |
if (star_helper == 0) |
278 |
{ |
279 |
NS_LOG_INFO ("AssignIpv4AddressRecursiveHelper Node Id:"<<n->GetId ()); |
280 |
return ; |
281 |
} |
282 |
uint32_t fan_out = star_helper->SpokeCount (); |
283 |
|
284 |
// Prepare mask and address helper for X subnets |
285 |
// Where X is the number of fan out nodes |
286 |
Ipv4Mask outer_mask = ExtendMaskForSubnets (allocated_mask,fan_out); |
287 |
Ipv4AddressHelper outer_addrhelper (network,outer_mask); |
288 |
|
289 |
//Create Mask for Subnet A and Subnet B (2 subnets) |
290 |
Ipv4Mask inner_mask = ExtendMaskForSubnets (outer_mask,2); |
291 |
|
292 |
Ipv4Address inner_network = network; //Initialization |
293 |
for (uint32_t i = 0; i < fan_out; ++i) |
294 |
{ |
295 |
Ipv4AddressHelper inner_addrhelper (inner_network, inner_mask); |
296 |
star_helper->AssignIpv4AddressForSingleSpoke (inner_addrhelper, i); |
297 |
AssignIpv4AddressHierarchicalRecursiveHelper (star_helper->GetSpokeNode (i), inner_addrhelper.NewNetwork (), inner_mask); |
298 |
inner_network = outer_addrhelper.NewNetwork (); |
299 |
|
300 |
} |
301 |
} |
302 |
void |
303 |
PointToPointTreeHelper::AssignIpv4AddressesHierarchical (Ipv4Address networkaddress, Ipv4Mask mask) |
304 |
{ |
305 |
// Assign Ipv4 addresses recursively, starting at level 0 |
306 |
AssignIpv4AddressHierarchicalRecursiveHelper (PerLevelNodeContainer[0].Get (0),networkaddress,mask); |
307 |
} |
308 |
|
309 |
void |
310 |
PointToPointTreeHelper::BoundingBoxRecursiveHelper (double xDist, double inter_level_height,uint32_t current_level) |
311 |
{ |
312 |
double inter_node_x_distance = 0 ; |
313 |
uint32_t num_node_in_current_level = 0; |
314 |
NS_LOG_FUNCTION ("Current level:"<<current_level); |
315 |
if (current_level >= this->m_num_levels) |
316 |
{ |
317 |
NS_LOG_INFO ("Recursion complete"); |
318 |
return ; |
319 |
} |
320 |
num_node_in_current_level = PerLevelNodeContainer[current_level].GetN (); // number of nodes in the current level |
321 |
inter_node_x_distance = (xDist/num_node_in_current_level)/2; // /2 is required to position the nodes at center of each x block |
322 |
|
323 |
for (uint32_t i = 0 ; i <num_node_in_current_level; i++) |
324 |
{ |
325 |
Ptr<Node> n = PerLevelNodeContainer[current_level].Get (i); |
326 |
NS_ASSERT (n); |
327 |
Ptr<ConstantPositionMobilityModel> loc = n->GetObject<ConstantPositionMobilityModel> (); |
328 |
if (loc == 0) |
329 |
{ |
330 |
loc = CreateObject<ConstantPositionMobilityModel> (); |
331 |
} |
332 |
else |
333 |
{ |
334 |
NS_LOG_WARN ("ConstantPositionMobilityModel Aggregated object already exists.Will use this object"); |
335 |
} |
336 |
n->AggregateObject (loc); // visualizers can retrieve the aggregated mobility model from a node to position it |
337 |
Vector spokeVec (inter_node_x_distance+(i*(inter_node_x_distance*2)), |
338 |
inter_level_height*current_level, |
339 |
0); |
340 |
loc->SetPosition (spokeVec); |
341 |
} |
342 |
current_level++; |
343 |
BoundingBoxRecursiveHelper (xDist,inter_level_height,current_level); |
344 |
} |
345 |
|
346 |
void |
347 |
PointToPointTreeHelper::BoundingBox (double ulx, double uly, double lrx, double lry) |
348 |
{ |
349 |
double yDist; |
350 |
double xDist; |
351 |
if (lrx > ulx) |
352 |
{ |
353 |
xDist = lrx - ulx; |
354 |
} |
355 |
else |
356 |
{ |
357 |
xDist = ulx - lrx; |
358 |
} |
359 |
if (lry > uly) |
360 |
{ |
361 |
yDist = lry - uly; |
362 |
} |
363 |
else |
364 |
{ |
365 |
yDist = uly - lry; |
366 |
} |
367 |
double inter_level_height = yDist/(m_num_levels-1) ; |
368 |
BoundingBoxRecursiveHelper (xDist,inter_level_height,0); |
369 |
|
370 |
} |
371 |
|
372 |
} // namespace ns3 |
373 |
|