blob: 908937e16e56602de03006cac9c94239300d836e [file] [log] [blame]
Alexander Afanasyevad3757f2012-04-17 10:27:59 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
2/*
3 * Copyright (c) 2011 UCLA
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#include "ccnx-global-routing-helper.h"
22
23#include "ns3/ccnx.h"
24#include "../model/ccnx-net-device-face.h"
25#include "../model/ccnx-global-router.h"
26#include "ns3/ccnx-name-components.h"
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -070027#include "ns3/ccnx-fib.h"
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070028
29#include "ns3/node.h"
Alexander Afanasyevce810142012-04-17 15:50:36 -070030#include "ns3/node-container.h"
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070031#include "ns3/net-device.h"
32#include "ns3/channel.h"
33#include "ns3/log.h"
34#include "ns3/assert.h"
35#include "ns3/names.h"
36#include "ns3/node-list.h"
37#include "ns3/channel-list.h"
38
39#include <boost/lexical_cast.hpp>
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -070040#include <boost/foreach.hpp>
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -070041#include <boost/concept/assert.hpp>
42// #include <boost/graph/graph_concepts.hpp>
43// #include <boost/graph/adjacency_list.hpp>
44#include <boost/graph/dijkstra_shortest_paths.hpp>
45
Alexander Afanasyevad3757f2012-04-17 10:27:59 -070046#include "boost-graph-ccnx-global-routing-helper.h"
47
48NS_LOG_COMPONENT_DEFINE ("CcnxGlobalRoutingHelper");
49
50using namespace std;
51using namespace boost;
52
53namespace ns3 {
54
55void
56CcnxGlobalRoutingHelper::Install (Ptr<Node> node)
57{
58 NS_LOG_LOGIC ("Node: " << node->GetId ());
59
60 Ptr<Ccnx> ccnx = node->GetObject<Ccnx> ();
61 NS_ASSERT_MSG (ccnx != 0, "Cannot install CcnxGlobalRoutingHelper before Ccnx is installed on a node");
62
63 Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
64 if (gr != 0)
65 {
66 NS_LOG_DEBUG ("CcnxGlobalRouter is already installed: " << gr);
67 return; // already installed
68 }
69
70 gr = CreateObject<CcnxGlobalRouter> ();
71 node->AggregateObject (gr);
72
73 for (uint32_t faceId = 0; faceId < ccnx->GetNFaces (); faceId++)
74 {
75 Ptr<CcnxNetDeviceFace> face = DynamicCast<CcnxNetDeviceFace> (ccnx->GetFace (faceId));
76 if (face == 0)
77 {
78 NS_LOG_DEBUG ("Skipping non-netdevice face");
79 continue;
80 }
81
82 Ptr<NetDevice> nd = face->GetNetDevice ();
83 if (nd == 0)
84 {
85 NS_LOG_DEBUG ("Not a NetDevice associated with CcnxNetDeviceFace");
86 continue;
87 }
88
89 Ptr<Channel> ch = nd->GetChannel ();
90
91 if (ch == 0)
92 {
93 NS_LOG_DEBUG ("Channel is not associated with NetDevice");
94 continue;
95 }
96
97 if (ch->GetNDevices () == 2) // e.g., point-to-point channel
98 {
99 for (uint32_t deviceId = 0; deviceId < ch->GetNDevices (); deviceId ++)
100 {
101 Ptr<NetDevice> otherSide = ch->GetDevice (deviceId);
102 if (nd == otherSide) continue;
103
104 Ptr<Node> otherNode = otherSide->GetNode ();
105 NS_ASSERT (otherNode != 0);
106
107 Ptr<CcnxGlobalRouter> otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
108 if (otherGr == 0)
109 {
110 Install (otherNode);
111 }
112 otherGr = otherNode->GetObject<CcnxGlobalRouter> ();
113 NS_ASSERT (otherGr != 0);
114 gr->AddIncidency (face, otherGr);
115 }
116 }
117 else
118 {
119 Ptr<CcnxGlobalRouter> grChannel = ch->GetObject<CcnxGlobalRouter> ();
120 if (grChannel == 0)
121 {
122 Install (ch);
123 }
124 grChannel = ch->GetObject<CcnxGlobalRouter> ();
125
126 gr->AddIncidency (0, grChannel);
127 }
128 }
129}
130
131void
132CcnxGlobalRoutingHelper::Install (Ptr<Channel> channel)
133{
134 NS_LOG_LOGIC ("Channel: " << channel->GetId ());
135
136 Ptr<CcnxGlobalRouter> gr = channel->GetObject<CcnxGlobalRouter> ();
137 if (gr != 0)
138 return;
139
140 gr = CreateObject<CcnxGlobalRouter> ();
141 channel->AggregateObject (gr);
142
143 for (uint32_t deviceId = 0; deviceId < channel->GetNDevices (); deviceId ++)
144 {
145 Ptr<NetDevice> dev = channel->GetDevice (deviceId);
146
147 Ptr<Node> node = dev->GetNode ();
148 NS_ASSERT (node != 0);
149
150 Ptr<CcnxGlobalRouter> grOther = node->GetObject<CcnxGlobalRouter> ();
151 if (grOther == 0)
152 {
153 Install (node);
154 }
155 grOther = node->GetObject<CcnxGlobalRouter> ();
156 NS_ASSERT (grOther != 0);
157
158 gr->AddIncidency (0, grOther);
159 }
160}
161
162void
Alexander Afanasyevce810142012-04-17 15:50:36 -0700163CcnxGlobalRoutingHelper::Install (const NodeContainer &nodes)
164{
165 for (NodeContainer::Iterator node = nodes.Begin ();
166 node != nodes.End ();
167 node ++)
168 {
169 Install (*node);
170 }
171}
172
173void
174CcnxGlobalRoutingHelper::InstallAll ()
175{
176 Install (NodeContainer::GetGlobal ());
177}
178
179
180void
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700181CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, Ptr<Node> node)
182{
183 Ptr<CcnxGlobalRouter> gr = node->GetObject<CcnxGlobalRouter> ();
184 NS_ASSERT_MSG (gr != 0,
185 "CcnxGlobalRouter is not installed on the node");
186
187 Ptr<CcnxNameComponents> name = Create<CcnxNameComponents> (boost::lexical_cast<CcnxNameComponents> (prefix));
188 gr->AddLocalPrefix (name);
189}
190
191void
Alexander Afanasyev06d3a612012-04-17 22:25:40 -0700192CcnxGlobalRoutingHelper::AddOrigins (const std::string &prefix, const NodeContainer &nodes)
193{
194 for (NodeContainer::Iterator node = nodes.Begin ();
195 node != nodes.End ();
196 node++)
197 {
198 AddOrigin (prefix, *node);
199 }
200}
201
202void
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700203CcnxGlobalRoutingHelper::AddOrigin (const std::string &prefix, const std::string &nodeName)
204{
205 Ptr<Node> node = Names::Find<Node> (nodeName);
206 NS_ASSERT_MSG (node != 0, nodeName << "is not a Node");
207
208 AddOrigin (prefix, node);
209}
210
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700211void
212CcnxGlobalRoutingHelper::CalculateRoutes ()
213{
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700214 /**
215 * Implementation of route calculation is heavily based on Boost Graph Library
216 * See http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/table_of_contents.html for more details
217 */
218
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700219 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept< CcnxGlobalRouterGraph > ));
220 BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept< CcnxGlobalRouterGraph > ));
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700221
222 CcnxGlobalRouterGraph graph;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700223 typedef graph_traits < CcnxGlobalRouterGraph >::vertex_descriptor vertex_descriptor;
224
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700225 // For now we doing Dijkstra for every node. Can be replaced with Bellman-Ford or Floyd-Warshall.
226 // Other algorithms should be faster, but they need additional EdgeListGraph concept provided by the graph, which
227 // is not obviously how implement in an efficient manner
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700228 for (NodeList::Iterator node = NodeList::Begin (); node != NodeList::End (); node++)
229 {
230 Ptr<CcnxGlobalRouter> source = (*node)->GetObject<CcnxGlobalRouter> ();
231 if (source == 0)
232 {
233 NS_LOG_DEBUG ("Node " << (*node)->GetId () << " does not export CcnxGlobalRouter interface");
234 continue;
235 }
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700236
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700237 DistancesMap distances;
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700238
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700239 dijkstra_shortest_paths (graph, source,
240 // predecessor_map (boost::ref(predecessors))
241 // .
242 distance_map (boost::ref(distances))
243 .
244 distance_inf (WeightInf)
245 .
246 distance_zero (WeightZero)
247 .
248 distance_compare (boost::WeightCompare ())
249 .
250 distance_combine (boost::WeightCombine ())
251 );
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700252
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700253 // NS_LOG_DEBUG (predecessors.size () << ", " << distances.size ());
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700254
255 Ptr<CcnxFib> fib = source->GetObject<CcnxFib> ();
256 fib->InvalidateAll ();
257 NS_ASSERT (fib != 0);
258
259 // cout << "Reachability from Node: " << source->GetObject<Node> ()->GetId () << endl;
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700260 for (DistancesMap::iterator i = distances.begin ();
261 i != distances.end ();
262 i++)
263 {
264 if (i->first == source)
265 continue;
266 else
267 {
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700268 // cout << " Node " << i->first->GetObject<Node> ()->GetId ();
269 if (i->second.get<0> () == 0)
270 {
271 // cout << " is unreachable" << endl;
272 }
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700273 else
Alexander Afanasyev8e2f1122012-04-17 15:01:11 -0700274 {
275 // cout << " reachable via face " << *i->second.get<0> ()
276 // << " with distance " << i->second.get<1> () << endl;
277
278 BOOST_FOREACH (const Ptr<const CcnxNameComponents> &prefix, i->first->GetLocalPrefixes ())
279 {
280 fib->Add (prefix, i->second.get<0> (), i->second.get<1> ());
281 }
282 }
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700283 }
284 }
Alexander Afanasyeva5abcd92012-04-17 13:34:43 -0700285 }
Alexander Afanasyevad3757f2012-04-17 10:27:59 -0700286}
287
288
289}