OLD | NEW |
(Empty) | |
| 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 /* |
| 3 * Copyright (c) 2010 Telum (www.telum.ru) |
| 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 * Authors: Denis Fakhriev <fakhriev@telum.ru> |
| 19 */ |
| 20 |
| 21 #include "lrr-routing-topology.h" |
| 22 |
| 23 namespace ns3 { |
| 24 namespace lrr { |
| 25 |
| 26 const uint32_t GlobalTopology::Infty = (uint32_t)(-1); |
| 27 |
| 28 GlobalTopology::GlobalTopology () |
| 29 { |
| 30 } |
| 31 GlobalTopology::~GlobalTopology () |
| 32 { |
| 33 Clear (); |
| 34 } |
| 35 |
| 36 void |
| 37 GlobalTopology::AddVertex (Ipv4Address vertexAddr) |
| 38 { |
| 39 NS_ASSERT (m_addressToIndexMap.find (vertexAddr) == m_addressToIndexMap.end ()
); |
| 40 NS_ASSERT (m_connectivityMatrix.size () == m_intexToAddressVector.size ()); |
| 41 NS_ASSERT (m_connectivityMatrix.size () == m_addressToIndexMap.size ()); |
| 42 |
| 43 m_addressToIndexMap.insert (std::pair<Ipv4Address, uint32_t> (vertexAddr, m_ad
dressToIndexMap.size ())); |
| 44 m_intexToAddressVector.push_back (vertexAddr); |
| 45 InitConnectivityMatrix (); |
| 46 } |
| 47 |
| 48 void |
| 49 GlobalTopology::InitConnectivityMatrix () |
| 50 { |
| 51 m_connectivityMatrix.clear (); |
| 52 for (uint32_t i = 0; i < m_intexToAddressVector.size (); ++i) |
| 53 { |
| 54 m_connectivityMatrix.push_back (std::vector<uint32_t> (m_intexToAddressVec
tor.size (), Infty)); |
| 55 } |
| 56 for (unsigned int i = 0; i < m_connectivityMatrix.size (); i++) |
| 57 { |
| 58 m_connectivityMatrix[i][i] = 0; |
| 59 } |
| 60 uint32_t nn = m_connectivityMatrix.size (); |
| 61 m_shortestPathVector.clear (); |
| 62 m_predecessorVector.clear (); |
| 63 m_shortestPathVector = std::vector<uint32_t> (nn * nn, Infty); |
| 64 m_predecessorVector = std::vector<uint32_t> (nn * nn, Infty); |
| 65 } |
| 66 |
| 67 bool |
| 68 GlobalTopology::SetEdges (Ipv4Address srcAddr, std::map<Ipv4Address, uint16_t> &
dstAddrVect) |
| 69 { |
| 70 for (std::map<Ipv4Address, uint16_t>::const_iterator it = dstAddrVect.begin ()
; it != dstAddrVect.end (); ++it) |
| 71 { |
| 72 NS_ASSERT (m_addressToIndexMap.find (it->first) != m_addressToIndexMap.end
()); |
| 73 } |
| 74 bool updated (false); |
| 75 |
| 76 // find srcNumber with srcAddr in addr_map |
| 77 uint32_t srcNumber = m_addressToIndexMap[srcAddr]; |
| 78 NS_ASSERT (srcNumber < m_connectivityMatrix.size ()); |
| 79 |
| 80 std::vector<uint32_t> newEdges (m_connectivityMatrix.size (), Infty); |
| 81 newEdges[srcNumber] = 0; |
| 82 for (std::map<Ipv4Address, uint16_t>::const_iterator it = dstAddrVect.begin ()
; it != dstAddrVect.end (); ++it) |
| 83 { |
| 84 newEdges[m_addressToIndexMap[it->first]] = it->second; |
| 85 } |
| 86 |
| 87 if (m_connectivityMatrix[srcNumber] != newEdges) |
| 88 { |
| 89 m_connectivityMatrix[srcNumber] = newEdges; |
| 90 updated = true; |
| 91 } |
| 92 |
| 93 return updated; |
| 94 } |
| 95 |
| 96 void |
| 97 GlobalTopology::Clear (void) |
| 98 { |
| 99 m_connectivityMatrix.clear (); |
| 100 m_intexToAddressVector.clear (); |
| 101 m_addressToIndexMap.clear (); |
| 102 m_shortestPathVector.clear (); |
| 103 m_predecessorVector.clear (); |
| 104 } |
| 105 |
| 106 void |
| 107 GlobalTopology::FloydWarshal (void) |
| 108 { |
| 109 // Print out the results table of connectivity matrix |
| 110 uint32_t nn = m_connectivityMatrix.size (); |
| 111 uint32_t i, j, k; // loop counters |
| 112 |
| 113 // Initialize data structures |
| 114 m_shortestPathVector.clear (); |
| 115 m_predecessorVector.clear (); |
| 116 m_shortestPathVector = std::vector<uint32_t> (nn * nn, 0); |
| 117 m_predecessorVector = std::vector<uint32_t> (nn * nn, 0); |
| 118 |
| 119 // Algorithm initialization |
| 120 for (i = 0; i < nn; i++) |
| 121 { |
| 122 for (j = 0; j < nn; j++) |
| 123 { |
| 124 if (m_connectivityMatrix[i][j] != Infty) |
| 125 { |
| 126 m_shortestPathVector[i * nn + j] = m_connectivityMatrix[i][j]; |
| 127 } |
| 128 else |
| 129 { |
| 130 m_shortestPathVector[i * nn + j] = Infty; // disconnected |
| 131 } |
| 132 |
| 133 if (i == j) // diagonal case |
| 134 { |
| 135 m_shortestPathVector[i * nn + j] = 0; |
| 136 } |
| 137 |
| 138 if ((m_shortestPathVector[ i * nn + j] > 0) && (m_shortestPathVector[
i * nn + j] < Infty)) |
| 139 { |
| 140 m_predecessorVector[i * nn + j] = i; |
| 141 } |
| 142 } |
| 143 } |
| 144 |
| 145 // Main loop of the algorithm |
| 146 for (k = 0; k < nn; k++) |
| 147 { |
| 148 for (i = 0; i < nn; i++) |
| 149 { |
| 150 for (j = 0; j < nn; j++) |
| 151 { |
| 152 uint32_t newdist = ((m_shortestPathVector[i * nn + k] == Infty) ||
(m_shortestPathVector[k * nn + j] == Infty)) ? Infty : (m_shortestPathVector[i
* nn + k] + m_shortestPathVector[k * nn + j]); |
| 153 if (m_shortestPathVector[i * nn + j] > newdist) |
| 154 { |
| 155 m_shortestPathVector[i * nn + j] = newdist; |
| 156 m_predecessorVector[i * nn + j] = k; |
| 157 } |
| 158 } |
| 159 } |
| 160 } |
| 161 for (i = 0; i < nn; i++) |
| 162 { |
| 163 for (j = 0; j < nn; j++) |
| 164 { |
| 165 if (i == j) continue; |
| 166 if (m_shortestPathVector[i * nn + j] == Infty) continue; |
| 167 uint32_t next = m_predecessorVector[i * nn + j]; |
| 168 if (next == i) continue; |
| 169 while (m_predecessorVector[i * nn + next] != i) |
| 170 { |
| 171 next = m_predecessorVector[i * nn + next]; |
| 172 } |
| 173 m_predecessorVector[i * nn + j] = next; |
| 174 } |
| 175 } |
| 176 } |
| 177 |
| 178 void |
| 179 GlobalTopology::Print (std::ostream & os) |
| 180 { |
| 181 Ipv4Address m_origin = m_intexToAddressVector[0]; |
| 182 |
| 183 os << "# Network topology as seen by vertex " << m_origin << "\n"; |
| 184 os << "digraph G {\n"; |
| 185 |
| 186 uint32_t nn = m_connectivityMatrix.size (); |
| 187 for (uint32_t i = 0; i < nn; ++i) |
| 188 { |
| 189 // For all vertices print address and distance to origin |
| 190 Ipv4Address addr = m_intexToAddressVector[i]; |
| 191 |
| 192 os << "\t\"" << addr << "\" [label=\"" << addr << "\""; |
| 193 |
| 194 if (addr == m_origin) os << ", shape=box"; |
| 195 |
| 196 os << "];\n"; |
| 197 |
| 198 // For all edges print metrics |
| 199 for (uint32_t j = 0; j < nn; ++j) |
| 200 { |
| 201 if ((m_connectivityMatrix[i][j] != Infty) && (i != j)) |
| 202 { |
| 203 os << "\t\"" << addr << "\" -> \"" << m_intexToAddressVector[j] <<
"\" [label=\"" << (unsigned) m_connectivityMatrix[i][j] << "\"];\n"; |
| 204 } |
| 205 } |
| 206 |
| 207 } |
| 208 os << "};\n"; |
| 209 } |
| 210 |
| 211 bool |
| 212 GlobalTopology::HavePath (Ipv4Address from, Ipv4Address to) |
| 213 { |
| 214 NS_ASSERT (m_addressToIndexMap.find (from) != m_addressToIndexMap.end ()); |
| 215 NS_ASSERT (m_addressToIndexMap.find (to) != m_addressToIndexMap.end ()); |
| 216 uint32_t index = m_addressToIndexMap[from] * m_addressToIndexMap.size () + m_a
ddressToIndexMap[to]; |
| 217 NS_ASSERT (m_shortestPathVector.size () > index); |
| 218 if (m_shortestPathVector[index] < Infty) |
| 219 { |
| 220 return true; |
| 221 } |
| 222 return false; |
| 223 } |
| 224 |
| 225 uint32_t |
| 226 GlobalTopology::PathDistance (Ipv4Address from, Ipv4Address to) |
| 227 { |
| 228 NS_ASSERT (m_addressToIndexMap.find (from) != m_addressToIndexMap.end ()); |
| 229 NS_ASSERT (m_addressToIndexMap.find (to) != m_addressToIndexMap.end ()); |
| 230 uint32_t index = m_addressToIndexMap[from] * m_addressToIndexMap.size () + m_a
ddressToIndexMap[to]; |
| 231 NS_ASSERT (m_shortestPathVector.size () > index); |
| 232 return m_shortestPathVector[index]; |
| 233 } |
| 234 |
| 235 Ipv4Address |
| 236 GlobalTopology::GetNextHop (Ipv4Address from, Ipv4Address to) |
| 237 { |
| 238 NS_ASSERT (m_addressToIndexMap.find (from) != m_addressToIndexMap.end ()); |
| 239 NS_ASSERT (m_addressToIndexMap.find (to) != m_addressToIndexMap.end ()); |
| 240 uint32_t index = m_addressToIndexMap[from] * m_addressToIndexMap.size () + m_a
ddressToIndexMap[to]; |
| 241 NS_ASSERT (m_shortestPathVector.size () > index); |
| 242 if (!HavePath (from, to)) |
| 243 { |
| 244 return Ipv4Address (); |
| 245 } |
| 246 if (from == to) |
| 247 { |
| 248 return from; |
| 249 } |
| 250 Ipv4Address predHop = m_intexToAddressVector[m_predecessorVector[index]]; |
| 251 if (predHop == from) |
| 252 { |
| 253 return to; |
| 254 } |
| 255 return predHop; |
| 256 } |
| 257 |
| 258 } // namespace lrr |
| 259 } // namespace ns3 |
| 260 |
OLD | NEW |