- Generated on Thu Aug 30 2012 22:56:43 for INET Framework for OMNeT++/OMNEST by
1.7.6.1
|
INET Framework for OMNeT++/OMNEST
|
00001 // 00002 // Copyright (C) 2006 Andras Babos and Andras Varga 00003 // 00004 // This program is free software; you can redistribute it and/or 00005 // modify it under the terms of the GNU Lesser General Public License 00006 // as published by the Free Software Foundation; either version 2 00007 // of the License, or (at your option) any later version. 00008 // 00009 // This program is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 // GNU Lesser General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU Lesser General Public License 00015 // along with this program; if not, see <http://www.gnu.org/licenses/>. 00016 // 00017 00018 #include "OSPFArea.h" 00019 #include "OSPFRouter.h" 00020 #include <memory.h> 00021 00022 OSPF::Area::Area(OSPF::AreaID id) : 00023 areaID(id), 00024 transitCapability(false), 00025 externalRoutingCapability(true), 00026 stubDefaultCost(1), 00027 spfTreeRoot(NULL), 00028 parentRouter(NULL) 00029 { 00030 } 00031 00032 OSPF::Area::~Area(void) 00033 { 00034 int interfaceNum = associatedInterfaces.size(); 00035 for (int i = 0; i < interfaceNum; i++) { 00036 delete(associatedInterfaces[i]); 00037 } 00038 long lsaCount = routerLSAs.size(); 00039 for (long j = 0; j < lsaCount; j++) { 00040 delete routerLSAs[j]; 00041 } 00042 routerLSAs.clear(); 00043 lsaCount = networkLSAs.size(); 00044 for (long k = 0; k < lsaCount; k++) { 00045 delete networkLSAs[k]; 00046 } 00047 networkLSAs.clear(); 00048 lsaCount = summaryLSAs.size(); 00049 for (long m = 0; m < lsaCount; m++) { 00050 delete summaryLSAs[m]; 00051 } 00052 summaryLSAs.clear(); 00053 } 00054 00055 void OSPF::Area::AddInterface(OSPF::Interface* intf) 00056 { 00057 intf->SetArea(this); 00058 associatedInterfaces.push_back(intf); 00059 } 00060 00061 void OSPF::Area::info(char *buffer) 00062 { 00063 std::stringstream out; 00064 char areaString[16]; 00065 out << "areaID: " << AddressStringFromULong(areaString, 16, areaID); 00066 strcpy(buffer, out.str().c_str()); 00067 } 00068 00069 std::string OSPF::Area::detailedInfo(void) const 00070 { 00071 std::stringstream out; 00072 char addressString[16]; 00073 int i; 00074 out << "\n areaID: " << AddressStringFromULong(addressString, 16, areaID) << ", "; 00075 out << "transitCapability: " << (transitCapability ? "true" : "false") << ", "; 00076 out << "externalRoutingCapability: " << (externalRoutingCapability ? "true" : "false") << ", "; 00077 out << "stubDefaultCost: " << stubDefaultCost << "\n"; 00078 int addressRangeNum = areaAddressRanges.size(); 00079 for (i = 0; i < addressRangeNum; i++) { 00080 out << " addressRanges[" << i << "]: "; 00081 out << AddressStringFromIPv4Address(addressString, 16, areaAddressRanges[i].address); 00082 out << "/" << AddressStringFromIPv4Address(addressString, 16, areaAddressRanges[i].mask) << "\n"; 00083 } 00084 int interfaceNum = associatedInterfaces.size(); 00085 for (i = 0; i < interfaceNum; i++) { 00086 out << " interface[" << i << "]: addressRange: "; 00087 out << AddressStringFromIPv4Address(addressString, 16, associatedInterfaces[i]->GetAddressRange().address); 00088 out << "/" << AddressStringFromIPv4Address(addressString, 16, associatedInterfaces[i]->GetAddressRange().mask) << "\n"; 00089 } 00090 00091 out << "\n"; 00092 out << " Database:\n"; 00093 out << " RouterLSAs:\n"; 00094 long lsaCount = routerLSAs.size(); 00095 for (i = 0; i < lsaCount; i++) { 00096 out << " " << *routerLSAs[i] << "\n"; 00097 } 00098 out << " NetworkLSAs:\n"; 00099 lsaCount = networkLSAs.size(); 00100 for (i = 0; i < lsaCount; i++) { 00101 out << " " << *networkLSAs[i] << "\n"; 00102 } 00103 out << " SummaryLSAs:\n"; 00104 lsaCount = summaryLSAs.size(); 00105 for (i = 0; i < lsaCount; i++) { 00106 out << " " << *summaryLSAs[i] << "\n"; 00107 } 00108 00109 out << "--------------------------------------------------------------------------------"; 00110 00111 return out.str(); 00112 } 00113 00114 bool OSPF::Area::ContainsAddress(OSPF::IPv4Address address) const 00115 { 00116 int addressRangeNum = areaAddressRanges.size(); 00117 for (int i = 0; i < addressRangeNum; i++) { 00118 if ((areaAddressRanges[i].address & areaAddressRanges[i].mask) == (address & areaAddressRanges[i].mask)) { 00119 return true; 00120 } 00121 } 00122 return false; 00123 } 00124 00125 bool OSPF::Area::HasAddressRange(OSPF::IPv4AddressRange addressRange) const 00126 { 00127 int addressRangeNum = areaAddressRanges.size(); 00128 for (int i = 0; i < addressRangeNum; i++) { 00129 if ((areaAddressRanges[i].address == addressRange.address) && 00130 (areaAddressRanges[i].mask == addressRange.mask)) 00131 { 00132 return true; 00133 } 00134 } 00135 return false; 00136 } 00137 00138 OSPF::IPv4AddressRange OSPF::Area::GetContainingAddressRange(OSPF::IPv4AddressRange addressRange, bool* advertise /*= NULL*/) const 00139 { 00140 int addressRangeNum = areaAddressRanges.size(); 00141 for (int i = 0; i < addressRangeNum; i++) { 00142 if ((areaAddressRanges[i].address & areaAddressRanges[i].mask) == (addressRange.address & areaAddressRanges[i].mask)) { 00143 if (advertise != NULL) { 00144 std::map<OSPF::IPv4AddressRange, bool, OSPF::IPv4AddressRange_Less>::const_iterator rangeIt = advertiseAddressRanges.find(areaAddressRanges[i]); 00145 if (rangeIt != advertiseAddressRanges.end()) { 00146 *advertise = rangeIt->second; 00147 } else { 00148 *advertise = true; 00149 } 00150 } 00151 return areaAddressRanges[i]; 00152 } 00153 } 00154 if (advertise != NULL) { 00155 *advertise = false; 00156 } 00157 return NullIPv4AddressRange; 00158 } 00159 00160 OSPF::Interface* OSPF::Area::GetInterface(unsigned char ifIndex) 00161 { 00162 int interfaceNum = associatedInterfaces.size(); 00163 for (int i = 0; i < interfaceNum; i++) { 00164 if ((associatedInterfaces[i]->GetType() != OSPF::Interface::Virtual) && 00165 (associatedInterfaces[i]->GetIfIndex() == ifIndex)) 00166 { 00167 return associatedInterfaces[i]; 00168 } 00169 } 00170 return NULL; 00171 } 00172 00173 OSPF::Interface* OSPF::Area::GetInterface(OSPF::IPv4Address address) 00174 { 00175 int interfaceNum = associatedInterfaces.size(); 00176 for (int i = 0; i < interfaceNum; i++) { 00177 if ((associatedInterfaces[i]->GetType() != OSPF::Interface::Virtual) && 00178 (associatedInterfaces[i]->GetAddressRange().address == address)) 00179 { 00180 return associatedInterfaces[i]; 00181 } 00182 } 00183 return NULL; 00184 } 00185 00186 bool OSPF::Area::HasVirtualLink(OSPF::AreaID withTransitArea) const 00187 { 00188 if ((areaID != OSPF::BackboneAreaID) || (withTransitArea == OSPF::BackboneAreaID)) { 00189 return false; 00190 } 00191 00192 int interfaceNum = associatedInterfaces.size(); 00193 for (int i = 0; i < interfaceNum; i++) { 00194 if ((associatedInterfaces[i]->GetType() == OSPF::Interface::Virtual) && 00195 (associatedInterfaces[i]->GetTransitAreaID() == withTransitArea)) 00196 { 00197 return true; 00198 } 00199 } 00200 return false; 00201 } 00202 00203 00204 OSPF::Interface* OSPF::Area::FindVirtualLink(OSPF::RouterID routerID) 00205 { 00206 int interfaceNum = associatedInterfaces.size(); 00207 for (int i = 0; i < interfaceNum; i++) { 00208 if ((associatedInterfaces[i]->GetType() == OSPF::Interface::Virtual) && 00209 (associatedInterfaces[i]->GetNeighborByID(routerID) != NULL)) 00210 { 00211 return associatedInterfaces[i]; 00212 } 00213 } 00214 return NULL; 00215 } 00216 00217 bool OSPF::Area::InstallRouterLSA(OSPFRouterLSA* lsa) 00218 { 00219 OSPF::LinkStateID linkStateID = lsa->getHeader().getLinkStateID(); 00220 std::map<OSPF::LinkStateID, OSPF::RouterLSA*>::iterator lsaIt = routerLSAsByID.find(linkStateID); 00221 if (lsaIt != routerLSAsByID.end()) { 00222 OSPF::LSAKeyType lsaKey; 00223 00224 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00225 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00226 00227 RemoveFromAllRetransmissionLists(lsaKey); 00228 return lsaIt->second->Update(lsa); 00229 } else { 00230 OSPF::RouterLSA* lsaCopy = new OSPF::RouterLSA(*lsa); 00231 routerLSAsByID[linkStateID] = lsaCopy; 00232 routerLSAs.push_back(lsaCopy); 00233 return true; 00234 } 00235 } 00236 00237 bool OSPF::Area::InstallNetworkLSA(OSPFNetworkLSA* lsa) 00238 { 00239 OSPF::LinkStateID linkStateID = lsa->getHeader().getLinkStateID(); 00240 std::map<OSPF::LinkStateID, OSPF::NetworkLSA*>::iterator lsaIt = networkLSAsByID.find(linkStateID); 00241 if (lsaIt != networkLSAsByID.end()) { 00242 OSPF::LSAKeyType lsaKey; 00243 00244 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00245 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00246 00247 RemoveFromAllRetransmissionLists(lsaKey); 00248 return lsaIt->second->Update(lsa); 00249 } else { 00250 OSPF::NetworkLSA* lsaCopy = new OSPF::NetworkLSA(*lsa); 00251 networkLSAsByID[linkStateID] = lsaCopy; 00252 networkLSAs.push_back(lsaCopy); 00253 return true; 00254 } 00255 } 00256 00257 bool OSPF::Area::InstallSummaryLSA(OSPFSummaryLSA* lsa) 00258 { 00259 OSPF::LSAKeyType lsaKey; 00260 00261 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00262 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00263 00264 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::iterator lsaIt = summaryLSAsByID.find(lsaKey); 00265 if (lsaIt != summaryLSAsByID.end()) { 00266 OSPF::LSAKeyType lsaKey; 00267 00268 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00269 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00270 00271 RemoveFromAllRetransmissionLists(lsaKey); 00272 return lsaIt->second->Update(lsa); 00273 } else { 00274 OSPF::SummaryLSA* lsaCopy = new OSPF::SummaryLSA(*lsa); 00275 summaryLSAsByID[lsaKey] = lsaCopy; 00276 summaryLSAs.push_back(lsaCopy); 00277 return true; 00278 } 00279 } 00280 00281 OSPF::RouterLSA* OSPF::Area::FindRouterLSA(OSPF::LinkStateID linkStateID) 00282 { 00283 std::map<OSPF::LinkStateID, OSPF::RouterLSA*>::iterator lsaIt = routerLSAsByID.find(linkStateID); 00284 if (lsaIt != routerLSAsByID.end()) { 00285 return lsaIt->second; 00286 } else { 00287 return NULL; 00288 } 00289 } 00290 00291 const OSPF::RouterLSA* OSPF::Area::FindRouterLSA(OSPF::LinkStateID linkStateID) const 00292 { 00293 std::map<OSPF::LinkStateID, OSPF::RouterLSA*>::const_iterator lsaIt = routerLSAsByID.find(linkStateID); 00294 if (lsaIt != routerLSAsByID.end()) { 00295 return lsaIt->second; 00296 } else { 00297 return NULL; 00298 } 00299 } 00300 00301 OSPF::NetworkLSA* OSPF::Area::FindNetworkLSA(OSPF::LinkStateID linkStateID) 00302 { 00303 std::map<OSPF::LinkStateID, OSPF::NetworkLSA*>::iterator lsaIt = networkLSAsByID.find(linkStateID); 00304 if (lsaIt != networkLSAsByID.end()) { 00305 return lsaIt->second; 00306 } else { 00307 return NULL; 00308 } 00309 } 00310 00311 const OSPF::NetworkLSA* OSPF::Area::FindNetworkLSA(OSPF::LinkStateID linkStateID) const 00312 { 00313 std::map<OSPF::LinkStateID, OSPF::NetworkLSA*>::const_iterator lsaIt = networkLSAsByID.find(linkStateID); 00314 if (lsaIt != networkLSAsByID.end()) { 00315 return lsaIt->second; 00316 } else { 00317 return NULL; 00318 } 00319 } 00320 00321 OSPF::SummaryLSA* OSPF::Area::FindSummaryLSA(OSPF::LSAKeyType lsaKey) 00322 { 00323 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::iterator lsaIt = summaryLSAsByID.find(lsaKey); 00324 if (lsaIt != summaryLSAsByID.end()) { 00325 return lsaIt->second; 00326 } else { 00327 return NULL; 00328 } 00329 } 00330 00331 const OSPF::SummaryLSA* OSPF::Area::FindSummaryLSA(OSPF::LSAKeyType lsaKey) const 00332 { 00333 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::const_iterator lsaIt = summaryLSAsByID.find(lsaKey); 00334 if (lsaIt != summaryLSAsByID.end()) { 00335 return lsaIt->second; 00336 } else { 00337 return NULL; 00338 } 00339 } 00340 00341 void OSPF::Area::AgeDatabase(void) 00342 { 00343 long lsaCount = routerLSAs.size(); 00344 bool rebuildRoutingTable = false; 00345 long i; 00346 00347 for (i = 0; i < lsaCount; i++) { 00348 unsigned short lsAge = routerLSAs[i]->getHeader().getLsAge(); 00349 bool selfOriginated = (routerLSAs[i]->getHeader().getAdvertisingRouter().getInt() == parentRouter->GetRouterID()); 00350 bool unreachable = parentRouter->IsDestinationUnreachable(routerLSAs[i]); 00351 OSPF::RouterLSA* lsa = routerLSAs[i]; 00352 00353 if ((selfOriginated && (lsAge < (LS_REFRESH_TIME - 1))) || (!selfOriginated && (lsAge < (MAX_AGE - 1)))) { 00354 lsa->getHeader().setLsAge(lsAge + 1); 00355 if ((lsAge + 1) % CHECK_AGE == 0) { 00356 if (!lsa->ValidateLSChecksum()) { 00357 EV << "Invalid LS checksum. Memory error detected!\n"; 00358 } 00359 } 00360 lsa->IncrementInstallTime(); 00361 } 00362 if (selfOriginated && (lsAge == (LS_REFRESH_TIME - 1))) { 00363 if (unreachable) { 00364 lsa->getHeader().setLsAge(MAX_AGE); 00365 FloodLSA(lsa); 00366 lsa->IncrementInstallTime(); 00367 } else { 00368 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00369 if (sequenceNumber == MAX_SEQUENCE_NUMBER) { 00370 lsa->getHeader().setLsAge(MAX_AGE); 00371 FloodLSA(lsa); 00372 lsa->IncrementInstallTime(); 00373 } else { 00374 OSPF::RouterLSA* newLSA = OriginateRouterLSA(); 00375 00376 newLSA->getHeader().setLsSequenceNumber(sequenceNumber + 1); 00377 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00378 rebuildRoutingTable |= lsa->Update(newLSA); 00379 delete newLSA; 00380 00381 FloodLSA(lsa); 00382 } 00383 } 00384 } 00385 if (!selfOriginated && (lsAge == MAX_AGE - 1)) { 00386 lsa->getHeader().setLsAge(MAX_AGE); 00387 FloodLSA(lsa); 00388 lsa->IncrementInstallTime(); 00389 } 00390 if (lsAge == MAX_AGE) { 00391 OSPF::LSAKeyType lsaKey; 00392 00393 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00394 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00395 00396 if (!IsOnAnyRetransmissionList(lsaKey) && 00397 !HasAnyNeighborInStates(OSPF::Neighbor::ExchangeState | OSPF::Neighbor::LoadingState)) 00398 { 00399 if (!selfOriginated || unreachable) { 00400 routerLSAsByID.erase(lsa->getHeader().getLinkStateID()); 00401 delete lsa; 00402 routerLSAs[i] = NULL; 00403 rebuildRoutingTable = true; 00404 } else { 00405 OSPF::RouterLSA* newLSA = OriginateRouterLSA(); 00406 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00407 00408 newLSA->getHeader().setLsSequenceNumber((sequenceNumber == MAX_SEQUENCE_NUMBER) ? INITIAL_SEQUENCE_NUMBER : sequenceNumber + 1); 00409 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00410 rebuildRoutingTable |= lsa->Update(newLSA); 00411 delete newLSA; 00412 00413 FloodLSA(lsa); 00414 } 00415 } 00416 } 00417 } 00418 00419 std::vector<RouterLSA*>::iterator routerIt = routerLSAs.begin(); 00420 while (routerIt != routerLSAs.end()) { 00421 if ((*routerIt) == NULL) { 00422 routerIt = routerLSAs.erase(routerIt); 00423 } else { 00424 routerIt++; 00425 } 00426 } 00427 00428 lsaCount = networkLSAs.size(); 00429 for (i = 0; i < lsaCount; i++) { 00430 unsigned short lsAge = networkLSAs[i]->getHeader().getLsAge(); 00431 bool unreachable = parentRouter->IsDestinationUnreachable(networkLSAs[i]); 00432 OSPF::NetworkLSA* lsa = networkLSAs[i]; 00433 OSPF::Interface* localIntf = GetInterface(IPv4AddressFromULong(lsa->getHeader().getLinkStateID())); 00434 bool selfOriginated = false; 00435 00436 if ((localIntf != NULL) && 00437 (localIntf->GetState() == OSPF::Interface::DesignatedRouterState) && 00438 (localIntf->GetNeighborCount() > 0) && 00439 (localIntf->HasAnyNeighborInStates(OSPF::Neighbor::FullState))) 00440 { 00441 selfOriginated = true; 00442 } 00443 00444 if ((selfOriginated && (lsAge < (LS_REFRESH_TIME - 1))) || (!selfOriginated && (lsAge < (MAX_AGE - 1)))) { 00445 lsa->getHeader().setLsAge(lsAge + 1); 00446 if ((lsAge + 1) % CHECK_AGE == 0) { 00447 if (!lsa->ValidateLSChecksum()) { 00448 EV << "Invalid LS checksum. Memory error detected!\n"; 00449 } 00450 } 00451 lsa->IncrementInstallTime(); 00452 } 00453 if (selfOriginated && (lsAge == (LS_REFRESH_TIME - 1))) { 00454 if (unreachable) { 00455 lsa->getHeader().setLsAge(MAX_AGE); 00456 FloodLSA(lsa); 00457 lsa->IncrementInstallTime(); 00458 } else { 00459 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00460 if (sequenceNumber == MAX_SEQUENCE_NUMBER) { 00461 lsa->getHeader().setLsAge(MAX_AGE); 00462 FloodLSA(lsa); 00463 lsa->IncrementInstallTime(); 00464 } else { 00465 OSPF::NetworkLSA* newLSA = OriginateNetworkLSA(localIntf); 00466 00467 if (newLSA != NULL) { 00468 newLSA->getHeader().setLsSequenceNumber(sequenceNumber + 1); 00469 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00470 rebuildRoutingTable |= lsa->Update(newLSA); 00471 delete newLSA; 00472 } else { // no neighbors on the network -> old NetworkLSA must be flushed 00473 lsa->getHeader().setLsAge(MAX_AGE); 00474 lsa->IncrementInstallTime(); 00475 } 00476 00477 FloodLSA(lsa); 00478 } 00479 } 00480 } 00481 if (!selfOriginated && (lsAge == MAX_AGE - 1)) { 00482 lsa->getHeader().setLsAge(MAX_AGE); 00483 FloodLSA(lsa); 00484 lsa->IncrementInstallTime(); 00485 } 00486 if (lsAge == MAX_AGE) { 00487 OSPF::LSAKeyType lsaKey; 00488 00489 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00490 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00491 00492 if (!IsOnAnyRetransmissionList(lsaKey) && 00493 !HasAnyNeighborInStates(OSPF::Neighbor::ExchangeState | OSPF::Neighbor::LoadingState)) 00494 { 00495 if (!selfOriginated || unreachable) { 00496 networkLSAsByID.erase(lsa->getHeader().getLinkStateID()); 00497 delete lsa; 00498 networkLSAs[i] = NULL; 00499 rebuildRoutingTable = true; 00500 } else { 00501 OSPF::NetworkLSA* newLSA = OriginateNetworkLSA(localIntf); 00502 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00503 00504 if (newLSA != NULL) { 00505 newLSA->getHeader().setLsSequenceNumber((sequenceNumber == MAX_SEQUENCE_NUMBER) ? INITIAL_SEQUENCE_NUMBER : sequenceNumber + 1); 00506 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00507 rebuildRoutingTable |= lsa->Update(newLSA); 00508 delete newLSA; 00509 00510 FloodLSA(lsa); 00511 } else { // no neighbors on the network -> old NetworkLSA must be deleted 00512 delete networkLSAs[i]; 00513 } 00514 } 00515 } 00516 } 00517 } 00518 00519 std::vector<NetworkLSA*>::iterator networkIt = networkLSAs.begin(); 00520 while (networkIt != networkLSAs.end()) { 00521 if ((*networkIt) == NULL) { 00522 networkIt = networkLSAs.erase(networkIt); 00523 } else { 00524 networkIt++; 00525 } 00526 } 00527 00528 lsaCount = summaryLSAs.size(); 00529 for (i = 0; i < lsaCount; i++) { 00530 unsigned short lsAge = summaryLSAs[i]->getHeader().getLsAge(); 00531 bool selfOriginated = (summaryLSAs[i]->getHeader().getAdvertisingRouter().getInt() == parentRouter->GetRouterID()); 00532 bool unreachable = parentRouter->IsDestinationUnreachable(summaryLSAs[i]); 00533 OSPF::SummaryLSA* lsa = summaryLSAs[i]; 00534 00535 if ((selfOriginated && (lsAge < (LS_REFRESH_TIME - 1))) || (!selfOriginated && (lsAge < (MAX_AGE - 1)))) { 00536 lsa->getHeader().setLsAge(lsAge + 1); 00537 if ((lsAge + 1) % CHECK_AGE == 0) { 00538 if (!lsa->ValidateLSChecksum()) { 00539 EV << "Invalid LS checksum. Memory error detected!\n"; 00540 } 00541 } 00542 lsa->IncrementInstallTime(); 00543 } 00544 if (selfOriginated && (lsAge == (LS_REFRESH_TIME - 1))) { 00545 if (unreachable) { 00546 lsa->getHeader().setLsAge(MAX_AGE); 00547 FloodLSA(lsa); 00548 lsa->IncrementInstallTime(); 00549 } else { 00550 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00551 if (sequenceNumber == MAX_SEQUENCE_NUMBER) { 00552 lsa->getHeader().setLsAge(MAX_AGE); 00553 FloodLSA(lsa); 00554 lsa->IncrementInstallTime(); 00555 } else { 00556 OSPF::SummaryLSA* newLSA = OriginateSummaryLSA(lsa); 00557 00558 if (newLSA != NULL) { 00559 newLSA->getHeader().setLsSequenceNumber(sequenceNumber + 1); 00560 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00561 rebuildRoutingTable |= lsa->Update(newLSA); 00562 delete newLSA; 00563 00564 FloodLSA(lsa); 00565 } else { 00566 lsa->getHeader().setLsAge(MAX_AGE); 00567 FloodLSA(lsa); 00568 lsa->IncrementInstallTime(); 00569 } 00570 } 00571 } 00572 } 00573 if (!selfOriginated && (lsAge == MAX_AGE - 1)) { 00574 lsa->getHeader().setLsAge(MAX_AGE); 00575 FloodLSA(lsa); 00576 lsa->IncrementInstallTime(); 00577 } 00578 if (lsAge == MAX_AGE) { 00579 OSPF::LSAKeyType lsaKey; 00580 00581 lsaKey.linkStateID = lsa->getHeader().getLinkStateID(); 00582 lsaKey.advertisingRouter = lsa->getHeader().getAdvertisingRouter().getInt(); 00583 00584 if (!IsOnAnyRetransmissionList(lsaKey) && 00585 !HasAnyNeighborInStates(OSPF::Neighbor::ExchangeState | OSPF::Neighbor::LoadingState)) 00586 { 00587 if (!selfOriginated || unreachable) { 00588 summaryLSAsByID.erase(lsaKey); 00589 delete lsa; 00590 summaryLSAs[i] = NULL; 00591 rebuildRoutingTable = true; 00592 } else { 00593 OSPF::SummaryLSA* newLSA = OriginateSummaryLSA(lsa); 00594 if (newLSA != NULL) { 00595 long sequenceNumber = lsa->getHeader().getLsSequenceNumber(); 00596 00597 newLSA->getHeader().setLsSequenceNumber((sequenceNumber == MAX_SEQUENCE_NUMBER) ? INITIAL_SEQUENCE_NUMBER : sequenceNumber + 1); 00598 newLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 00599 rebuildRoutingTable |= lsa->Update(newLSA); 00600 delete newLSA; 00601 00602 FloodLSA(lsa); 00603 } else { 00604 summaryLSAsByID.erase(lsaKey); 00605 delete lsa; 00606 summaryLSAs[i] = NULL; 00607 rebuildRoutingTable = true; 00608 } 00609 } 00610 } 00611 } 00612 } 00613 00614 std::vector<SummaryLSA*>::iterator summaryIt = summaryLSAs.begin(); 00615 while (summaryIt != summaryLSAs.end()) { 00616 if ((*summaryIt) == NULL) { 00617 summaryIt = summaryLSAs.erase(summaryIt); 00618 } else { 00619 summaryIt++; 00620 } 00621 } 00622 00623 long interfaceCount = associatedInterfaces.size(); 00624 for (long m = 0; m < interfaceCount; m++) { 00625 associatedInterfaces[m]->AgeTransmittedLSALists(); 00626 } 00627 00628 if (rebuildRoutingTable) { 00629 parentRouter->RebuildRoutingTable(); 00630 } 00631 } 00632 00633 bool OSPF::Area::HasAnyNeighborInStates(int states) const 00634 { 00635 long interfaceCount = associatedInterfaces.size(); 00636 for (long i = 0; i < interfaceCount; i++) { 00637 if (associatedInterfaces[i]->HasAnyNeighborInStates(states)) { 00638 return true; 00639 } 00640 } 00641 return false; 00642 } 00643 00644 void OSPF::Area::RemoveFromAllRetransmissionLists(OSPF::LSAKeyType lsaKey) 00645 { 00646 long interfaceCount = associatedInterfaces.size(); 00647 for (long i = 0; i < interfaceCount; i++) { 00648 associatedInterfaces[i]->RemoveFromAllRetransmissionLists(lsaKey); 00649 } 00650 } 00651 00652 bool OSPF::Area::IsOnAnyRetransmissionList(OSPF::LSAKeyType lsaKey) const 00653 { 00654 long interfaceCount = associatedInterfaces.size(); 00655 for (long i = 0; i < interfaceCount; i++) { 00656 if (associatedInterfaces[i]->IsOnAnyRetransmissionList(lsaKey)) { 00657 return true; 00658 } 00659 } 00660 return false; 00661 } 00662 00663 bool OSPF::Area::FloodLSA(OSPFLSA* lsa, OSPF::Interface* intf, OSPF::Neighbor* neighbor) 00664 { 00665 bool floodedBackOut = false; 00666 long interfaceCount = associatedInterfaces.size(); 00667 00668 for (long i = 0; i < interfaceCount; i++) { 00669 if (associatedInterfaces[i]->FloodLSA(lsa, intf, neighbor)) { 00670 floodedBackOut = true; 00671 } 00672 } 00673 00674 return floodedBackOut; 00675 } 00676 00677 bool OSPF::Area::IsLocalAddress(OSPF::IPv4Address address) const 00678 { 00679 long interfaceCount = associatedInterfaces.size(); 00680 for (long i = 0; i < interfaceCount; i++) { 00681 if (associatedInterfaces[i]->GetAddressRange().address == address) { 00682 return true; 00683 } 00684 } 00685 return false; 00686 } 00687 00688 OSPF::RouterLSA* OSPF::Area::OriginateRouterLSA(void) 00689 { 00690 OSPF::RouterLSA* routerLSA = new OSPF::RouterLSA; 00691 OSPFLSAHeader& lsaHeader = routerLSA->getHeader(); 00692 long interfaceCount = associatedInterfaces.size(); 00693 OSPFOptions lsOptions; 00694 long i; 00695 00696 lsaHeader.setLsAge(0); 00697 memset(&lsOptions, 0, sizeof(OSPFOptions)); 00698 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 00699 lsaHeader.setLsOptions(lsOptions); 00700 lsaHeader.setLsType(RouterLSAType); 00701 lsaHeader.setLinkStateID(parentRouter->GetRouterID()); 00702 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 00703 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 00704 00705 routerLSA->setB_AreaBorderRouter(parentRouter->GetAreaCount() > 1); 00706 routerLSA->setE_ASBoundaryRouter((externalRoutingCapability && parentRouter->GetASBoundaryRouter()) ? true : false); 00707 OSPF::Area* backbone = parentRouter->GetArea(OSPF::BackboneAreaID); 00708 routerLSA->setV_VirtualLinkEndpoint((backbone == NULL) ? false : backbone->HasVirtualLink(areaID)); 00709 00710 routerLSA->setNumberOfLinks(0); 00711 routerLSA->setLinksArraySize(0); 00712 for (i = 0; i < interfaceCount; i++) { 00713 OSPF::Interface* intf = associatedInterfaces[i]; 00714 00715 if (intf->GetState() == OSPF::Interface::DownState) { 00716 continue; 00717 } 00718 if ((intf->GetState() == OSPF::Interface::LoopbackState) && 00719 ((intf->GetType() != OSPF::Interface::PointToPoint) || 00720 (intf->GetAddressRange().address != OSPF::NullIPv4Address))) 00721 { 00722 Link stubLink; 00723 stubLink.setType(StubLink); 00724 stubLink.setLinkID(ULongFromIPv4Address(intf->GetAddressRange().address)); 00725 stubLink.setLinkData(0xFFFFFFFF); 00726 stubLink.setLinkCost(0); 00727 stubLink.setNumberOfTOS(0); 00728 stubLink.setTosDataArraySize(0); 00729 00730 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00731 routerLSA->setLinksArraySize(linkIndex + 1); 00732 routerLSA->setNumberOfLinks(linkIndex + 1); 00733 routerLSA->setLinks(linkIndex, stubLink); 00734 } 00735 if (intf->GetState() > OSPF::Interface::LoopbackState) { 00736 switch (intf->GetType()) { 00737 case OSPF::Interface::PointToPoint: 00738 { 00739 OSPF::Neighbor* neighbor = (intf->GetNeighborCount() > 0) ? intf->GetNeighbor(0) : NULL; 00740 if (neighbor != NULL) { 00741 if (neighbor->GetState() == OSPF::Neighbor::FullState) { 00742 Link link; 00743 link.setType(PointToPointLink); 00744 link.setLinkID(neighbor->GetNeighborID()); 00745 if (intf->GetAddressRange().address != OSPF::NullIPv4Address) { 00746 link.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().address)); 00747 } else { 00748 link.setLinkData(intf->GetIfIndex()); 00749 } 00750 link.setLinkCost(intf->GetOutputCost()); 00751 link.setNumberOfTOS(0); 00752 link.setTosDataArraySize(0); 00753 00754 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00755 routerLSA->setLinksArraySize(linkIndex + 1); 00756 routerLSA->setNumberOfLinks(linkIndex + 1); 00757 routerLSA->setLinks(linkIndex, link); 00758 } 00759 if (intf->GetState() == OSPF::Interface::PointToPointState) { 00760 if (neighbor->GetAddress() != OSPF::NullIPv4Address) { 00761 Link stubLink; 00762 stubLink.setType(StubLink); 00763 stubLink.setLinkID(ULongFromIPv4Address(neighbor->GetAddress())); 00764 stubLink.setLinkData(0xFFFFFFFF); 00765 stubLink.setLinkCost(intf->GetOutputCost()); 00766 stubLink.setNumberOfTOS(0); 00767 stubLink.setTosDataArraySize(0); 00768 00769 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00770 routerLSA->setLinksArraySize(linkIndex + 1); 00771 routerLSA->setNumberOfLinks(linkIndex + 1); 00772 routerLSA->setLinks(linkIndex, stubLink); 00773 } else { 00774 if (ULongFromIPv4Address(intf->GetAddressRange().mask) != 0xFFFFFFFF) { 00775 Link stubLink; 00776 stubLink.setType(StubLink); 00777 stubLink.setLinkID(ULongFromIPv4Address(intf->GetAddressRange().address & 00778 intf->GetAddressRange().mask)); 00779 stubLink.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().mask)); 00780 stubLink.setLinkCost(intf->GetOutputCost()); 00781 stubLink.setNumberOfTOS(0); 00782 stubLink.setTosDataArraySize(0); 00783 00784 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00785 routerLSA->setLinksArraySize(linkIndex + 1); 00786 routerLSA->setNumberOfLinks(linkIndex + 1); 00787 routerLSA->setLinks(linkIndex, stubLink); 00788 } 00789 } 00790 } 00791 } 00792 } 00793 break; 00794 case OSPF::Interface::Broadcast: 00795 case OSPF::Interface::NBMA: 00796 { 00797 if (intf->GetState() == OSPF::Interface::WaitingState) { 00798 Link stubLink; 00799 stubLink.setType(StubLink); 00800 stubLink.setLinkID(ULongFromIPv4Address(intf->GetAddressRange().address & 00801 intf->GetAddressRange().mask)); 00802 stubLink.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().mask)); 00803 stubLink.setLinkCost(intf->GetOutputCost()); 00804 stubLink.setNumberOfTOS(0); 00805 stubLink.setTosDataArraySize(0); 00806 00807 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00808 routerLSA->setLinksArraySize(linkIndex + 1); 00809 routerLSA->setNumberOfLinks(linkIndex + 1); 00810 routerLSA->setLinks(linkIndex, stubLink); 00811 } else { 00812 OSPF::Neighbor* dRouter = intf->GetNeighborByAddress(intf->GetDesignatedRouter().ipInterfaceAddress); 00813 if (((dRouter != NULL) && (dRouter->GetState() == OSPF::Neighbor::FullState)) || 00814 ((intf->GetDesignatedRouter().routerID == parentRouter->GetRouterID()) && 00815 (intf->HasAnyNeighborInStates(OSPF::Neighbor::FullState)))) 00816 { 00817 Link link; 00818 link.setType(TransitLink); 00819 link.setLinkID(ULongFromIPv4Address(intf->GetDesignatedRouter().ipInterfaceAddress)); 00820 link.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().address)); 00821 link.setLinkCost(intf->GetOutputCost()); 00822 link.setNumberOfTOS(0); 00823 link.setTosDataArraySize(0); 00824 00825 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00826 routerLSA->setLinksArraySize(linkIndex + 1); 00827 routerLSA->setNumberOfLinks(linkIndex + 1); 00828 routerLSA->setLinks(linkIndex, link); 00829 } else { 00830 Link stubLink; 00831 stubLink.setType(StubLink); 00832 stubLink.setLinkID(ULongFromIPv4Address(intf->GetAddressRange().address & 00833 intf->GetAddressRange().mask)); 00834 stubLink.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().mask)); 00835 stubLink.setLinkCost(intf->GetOutputCost()); 00836 stubLink.setNumberOfTOS(0); 00837 stubLink.setTosDataArraySize(0); 00838 00839 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00840 routerLSA->setLinksArraySize(linkIndex + 1); 00841 routerLSA->setNumberOfLinks(linkIndex + 1); 00842 routerLSA->setLinks(linkIndex, stubLink); 00843 } 00844 } 00845 } 00846 break; 00847 case OSPF::Interface::Virtual: 00848 { 00849 OSPF::Neighbor* neighbor = (intf->GetNeighborCount() > 0) ? intf->GetNeighbor(0) : NULL; 00850 if ((neighbor != NULL) && (neighbor->GetState() == OSPF::Neighbor::FullState)) { 00851 Link link; 00852 link.setType(VirtualLink); 00853 link.setLinkID(neighbor->GetNeighborID()); 00854 link.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().address)); 00855 link.setLinkCost(intf->GetOutputCost()); 00856 link.setNumberOfTOS(0); 00857 link.setTosDataArraySize(0); 00858 00859 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00860 routerLSA->setLinksArraySize(linkIndex + 1); 00861 routerLSA->setNumberOfLinks(linkIndex + 1); 00862 routerLSA->setLinks(linkIndex, link); 00863 } 00864 } 00865 break; 00866 case OSPF::Interface::PointToMultiPoint: 00867 { 00868 Link stubLink; 00869 stubLink.setType(StubLink); 00870 stubLink.setLinkID(ULongFromIPv4Address(intf->GetAddressRange().address)); 00871 stubLink.setLinkData(0xFFFFFFFF); 00872 stubLink.setLinkCost(0); 00873 stubLink.setNumberOfTOS(0); 00874 stubLink.setTosDataArraySize(0); 00875 00876 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00877 routerLSA->setLinksArraySize(linkIndex + 1); 00878 routerLSA->setNumberOfLinks(linkIndex + 1); 00879 routerLSA->setLinks(linkIndex, stubLink); 00880 00881 long neighborCount = intf->GetNeighborCount(); 00882 for (long i = 0; i < neighborCount; i++) { 00883 OSPF::Neighbor* neighbor = intf->GetNeighbor(i); 00884 if (neighbor->GetState() == OSPF::Neighbor::FullState) { 00885 Link link; 00886 link.setType(PointToPointLink); 00887 link.setLinkID(neighbor->GetNeighborID()); 00888 link.setLinkData(ULongFromIPv4Address(intf->GetAddressRange().address)); 00889 link.setLinkCost(intf->GetOutputCost()); 00890 link.setNumberOfTOS(0); 00891 link.setTosDataArraySize(0); 00892 00893 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00894 routerLSA->setLinksArraySize(linkIndex + 1); 00895 routerLSA->setNumberOfLinks(linkIndex + 1); 00896 routerLSA->setLinks(linkIndex, stubLink); 00897 } 00898 } 00899 } 00900 break; 00901 default: break; 00902 } 00903 } 00904 } 00905 00906 long hostRouteCount = hostRoutes.size(); 00907 for (i = 0; i < hostRouteCount; i++) { 00908 Link stubLink; 00909 stubLink.setType(StubLink); 00910 stubLink.setLinkID(ULongFromIPv4Address(hostRoutes[i].address)); 00911 stubLink.setLinkData(0xFFFFFFFF); 00912 stubLink.setLinkCost(hostRoutes[i].linkCost); 00913 stubLink.setNumberOfTOS(0); 00914 stubLink.setTosDataArraySize(0); 00915 00916 unsigned short linkIndex = routerLSA->getLinksArraySize(); 00917 routerLSA->setLinksArraySize(linkIndex + 1); 00918 routerLSA->setNumberOfLinks(linkIndex + 1); 00919 routerLSA->setLinks(linkIndex, stubLink); 00920 } 00921 00922 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 00923 00924 routerLSA->SetSource(OSPF::LSATrackingInfo::Originated); 00925 00926 return routerLSA; 00927 } 00928 00929 OSPF::NetworkLSA* OSPF::Area::OriginateNetworkLSA(const OSPF::Interface* intf) 00930 { 00931 if (intf->HasAnyNeighborInStates(OSPF::Neighbor::FullState)) { 00932 OSPF::NetworkLSA* networkLSA = new OSPF::NetworkLSA; 00933 OSPFLSAHeader& lsaHeader = networkLSA->getHeader(); 00934 long neighborCount = intf->GetNeighborCount(); 00935 OSPFOptions lsOptions; 00936 00937 lsaHeader.setLsAge(0); 00938 memset(&lsOptions, 0, sizeof(OSPFOptions)); 00939 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 00940 lsaHeader.setLsOptions(lsOptions); 00941 lsaHeader.setLsType(NetworkLSAType); 00942 lsaHeader.setLinkStateID(ULongFromIPv4Address(intf->GetAddressRange().address)); 00943 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 00944 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 00945 00946 networkLSA->setNetworkMask(ULongFromIPv4Address(intf->GetAddressRange().mask)); 00947 00948 for (long j = 0; j < neighborCount; j++) { 00949 const OSPF::Neighbor* neighbor = intf->GetNeighbor(j); 00950 if (neighbor->GetState() == OSPF::Neighbor::FullState) { 00951 unsigned short netIndex = networkLSA->getAttachedRoutersArraySize(); 00952 networkLSA->setAttachedRoutersArraySize(netIndex + 1); 00953 networkLSA->setAttachedRouters(netIndex, neighbor->GetNeighborID()); 00954 } 00955 } 00956 unsigned short netIndex = networkLSA->getAttachedRoutersArraySize(); 00957 networkLSA->setAttachedRoutersArraySize(netIndex + 1); 00958 networkLSA->setAttachedRouters(netIndex, parentRouter->GetRouterID()); 00959 00960 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 00961 00962 return networkLSA; 00963 } else { 00964 return NULL; 00965 } 00966 } 00967 00989 OSPF::LinkStateID OSPF::Area::GetUniqueLinkStateID(OSPF::IPv4AddressRange destination, 00990 OSPF::Metric destinationCost, 00991 OSPF::SummaryLSA*& lsaToReoriginate) const 00992 { 00993 if (lsaToReoriginate != NULL) { 00994 delete lsaToReoriginate; 00995 lsaToReoriginate = NULL; 00996 } 00997 00998 OSPF::LSAKeyType lsaKey; 00999 01000 lsaKey.linkStateID = ULongFromIPv4Address(destination.address); 01001 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01002 01003 const OSPF::SummaryLSA* foundLSA = FindSummaryLSA(lsaKey); 01004 01005 if (foundLSA == NULL) { 01006 return lsaKey.linkStateID; 01007 } else { 01008 OSPF::IPv4Address existingMask = IPv4AddressFromULong(foundLSA->getNetworkMask().getInt()); 01009 01010 if (destination.mask == existingMask) { 01011 return lsaKey.linkStateID; 01012 } else { 01013 if (destination.mask >= existingMask) { 01014 return (lsaKey.linkStateID | (~(ULongFromIPv4Address(destination.mask)))); 01015 } else { 01016 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA(*foundLSA); 01017 01018 long sequenceNumber = summaryLSA->getHeader().getLsSequenceNumber(); 01019 01020 summaryLSA->getHeader().setLsAge(0); 01021 summaryLSA->getHeader().setLsSequenceNumber((sequenceNumber == MAX_SEQUENCE_NUMBER) ? INITIAL_SEQUENCE_NUMBER : sequenceNumber + 1); 01022 summaryLSA->setNetworkMask(ULongFromIPv4Address(destination.mask)); 01023 summaryLSA->setRouteCost(destinationCost); 01024 summaryLSA->getHeader().setLsChecksum(0); // TODO: calculate correct LS checksum 01025 01026 lsaToReoriginate = summaryLSA; 01027 01028 return (lsaKey.linkStateID | (~(ULongFromIPv4Address(existingMask)))); 01029 } 01030 } 01031 } 01032 } 01033 01034 OSPF::SummaryLSA* OSPF::Area::OriginateSummaryLSA(const OSPF::RoutingTableEntry* entry, 01035 const std::map<OSPF::LSAKeyType, bool, OSPF::LSAKeyType_Less>& originatedLSAs, 01036 OSPF::SummaryLSA*& lsaToReoriginate) 01037 { 01038 if (((entry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 01039 (entry->GetPathType() == OSPF::RoutingTableEntry::Type1External) || 01040 (entry->GetPathType() == OSPF::RoutingTableEntry::Type2External) || 01041 (entry->GetArea() == areaID)) 01042 { 01043 return NULL; 01044 } 01045 01046 bool allNextHopsInThisArea = true; 01047 unsigned int nextHopCount = entry->GetNextHopCount(); 01048 01049 for (unsigned int i = 0; i < nextHopCount; i++) { 01050 OSPF::Interface* nextHopInterface = parentRouter->GetNonVirtualInterface(entry->GetNextHop(i).ifIndex); 01051 if ((nextHopInterface != NULL) && (nextHopInterface->GetAreaID() != areaID)) { 01052 allNextHopsInThisArea = false; 01053 break; 01054 } 01055 } 01056 if ((allNextHopsInThisArea) || (entry->GetCost() >= LS_INFINITY)){ 01057 return NULL; 01058 } 01059 01060 if ((entry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0) { 01061 OSPF::RoutingTableEntry* preferredEntry = parentRouter->GetPreferredEntry(*(entry->GetLinkStateOrigin()), false); 01062 if ((preferredEntry != NULL) && (*preferredEntry == *entry) && (externalRoutingCapability)) { 01063 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA; 01064 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01065 OSPFOptions lsOptions; 01066 01067 lsaHeader.setLsAge(0); 01068 memset(&lsOptions, 0, sizeof(OSPFOptions)); 01069 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 01070 lsaHeader.setLsOptions(lsOptions); 01071 lsaHeader.setLsType(SummaryLSA_ASBoundaryRoutersType); 01072 lsaHeader.setLinkStateID(entry->GetDestinationID().getInt()); 01073 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 01074 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01075 01076 summaryLSA->setNetworkMask(entry->GetAddressMask()); 01077 summaryLSA->setRouteCost(entry->GetCost()); 01078 summaryLSA->setTosDataArraySize(0); 01079 01080 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01081 01082 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated); 01083 01084 return summaryLSA; 01085 } 01086 } else { // entry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination 01087 if (entry->GetPathType() == OSPF::RoutingTableEntry::InterArea) { 01088 OSPF::IPv4AddressRange destinationRange; 01089 01090 destinationRange.address = IPv4AddressFromULong(entry->GetDestinationID().getInt()); 01091 destinationRange.mask = IPv4AddressFromULong(entry->GetAddressMask().getInt()); 01092 01093 OSPF::LinkStateID newLinkStateID = GetUniqueLinkStateID(destinationRange, entry->GetCost(), lsaToReoriginate); 01094 01095 if (lsaToReoriginate != NULL) { 01096 OSPF::LSAKeyType lsaKey; 01097 01098 lsaKey.linkStateID = entry->GetDestinationID().getInt(); 01099 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01100 01101 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::iterator lsaIt = summaryLSAsByID.find(lsaKey); 01102 if (lsaIt == summaryLSAsByID.end()) { 01103 delete(lsaToReoriginate); 01104 lsaToReoriginate = NULL; 01105 return NULL; 01106 } else { 01107 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA(*(lsaIt->second)); 01108 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01109 01110 lsaHeader.setLsAge(0); 01111 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01112 lsaHeader.setLinkStateID(newLinkStateID); 01113 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01114 01115 return summaryLSA; 01116 } 01117 } else { 01118 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA; 01119 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01120 OSPFOptions lsOptions; 01121 01122 lsaHeader.setLsAge(0); 01123 memset(&lsOptions, 0, sizeof(OSPFOptions)); 01124 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 01125 lsaHeader.setLsOptions(lsOptions); 01126 lsaHeader.setLsType(SummaryLSA_NetworksType); 01127 lsaHeader.setLinkStateID(newLinkStateID); 01128 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 01129 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01130 01131 summaryLSA->setNetworkMask(entry->GetAddressMask()); 01132 summaryLSA->setRouteCost(entry->GetCost()); 01133 summaryLSA->setTosDataArraySize(0); 01134 01135 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01136 01137 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated); 01138 01139 return summaryLSA; 01140 } 01141 } else { // entry->GetPathType() == OSPF::RoutingTableEntry::IntraArea 01142 OSPF::IPv4AddressRange destinationAddressRange; 01143 01144 destinationAddressRange.address = IPv4AddressFromULong(entry->GetDestinationID().getInt()); 01145 destinationAddressRange.mask = IPv4AddressFromULong(entry->GetAddressMask().getInt()); 01146 01147 bool doAdvertise = false; 01148 OSPF::IPv4AddressRange containingAddressRange = parentRouter->GetContainingAddressRange(destinationAddressRange, &doAdvertise); 01149 if (((entry->GetArea() == OSPF::BackboneAreaID) && // the backbone's configured ranges should be ignored 01150 (transitCapability)) || // when originating Summary LSAs into transit areas 01151 (containingAddressRange == OSPF::NullIPv4AddressRange)) 01152 { 01153 OSPF::LinkStateID newLinkStateID = GetUniqueLinkStateID(destinationAddressRange, entry->GetCost(), lsaToReoriginate); 01154 01155 if (lsaToReoriginate != NULL) { 01156 OSPF::LSAKeyType lsaKey; 01157 01158 lsaKey.linkStateID = entry->GetDestinationID().getInt(); 01159 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01160 01161 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::iterator lsaIt = summaryLSAsByID.find(lsaKey); 01162 if (lsaIt == summaryLSAsByID.end()) { 01163 delete(lsaToReoriginate); 01164 lsaToReoriginate = NULL; 01165 return NULL; 01166 } else { 01167 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA(*(lsaIt->second)); 01168 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01169 01170 lsaHeader.setLsAge(0); 01171 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01172 lsaHeader.setLinkStateID(newLinkStateID); 01173 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01174 01175 return summaryLSA; 01176 } 01177 } else { 01178 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA; 01179 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01180 OSPFOptions lsOptions; 01181 01182 lsaHeader.setLsAge(0); 01183 memset(&lsOptions, 0, sizeof(OSPFOptions)); 01184 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 01185 lsaHeader.setLsOptions(lsOptions); 01186 lsaHeader.setLsType(SummaryLSA_NetworksType); 01187 lsaHeader.setLinkStateID(newLinkStateID); 01188 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 01189 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01190 01191 summaryLSA->setNetworkMask(entry->GetAddressMask()); 01192 summaryLSA->setRouteCost(entry->GetCost()); 01193 summaryLSA->setTosDataArraySize(0); 01194 01195 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01196 01197 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated); 01198 01199 return summaryLSA; 01200 } 01201 } else { 01202 if (doAdvertise) { 01203 Metric maxRangeCost = 0; 01204 unsigned long entryCount = parentRouter->GetRoutingTableEntryCount(); 01205 01206 for (unsigned long i = 0; i < entryCount; i++) { 01207 const OSPF::RoutingTableEntry* routingEntry = parentRouter->GetRoutingTableEntry(i); 01208 01209 if ((routingEntry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) && 01210 (routingEntry->GetPathType() == OSPF::RoutingTableEntry::IntraArea) && 01211 ((routingEntry->GetDestinationID().getInt() & routingEntry->GetAddressMask().getInt() & ULongFromIPv4Address(containingAddressRange.mask)) == 01212 ULongFromIPv4Address(containingAddressRange.address & containingAddressRange.mask)) && 01213 (routingEntry->GetCost() > maxRangeCost)) 01214 { 01215 maxRangeCost = routingEntry->GetCost(); 01216 } 01217 } 01218 01219 OSPF::LinkStateID newLinkStateID = GetUniqueLinkStateID(containingAddressRange, maxRangeCost, lsaToReoriginate); 01220 OSPF::LSAKeyType lsaKey; 01221 01222 if (lsaToReoriginate != NULL) { 01223 lsaKey.linkStateID = lsaToReoriginate->getHeader().getLinkStateID(); 01224 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01225 01226 std::map<OSPF::LSAKeyType, bool, OSPF::LSAKeyType_Less>::const_iterator originatedIt = originatedLSAs.find(lsaKey); 01227 if (originatedIt != originatedLSAs.end()) { 01228 delete(lsaToReoriginate); 01229 lsaToReoriginate = NULL; 01230 return NULL; 01231 } 01232 01233 lsaKey.linkStateID = entry->GetDestinationID().getInt(); 01234 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01235 01236 std::map<OSPF::LSAKeyType, OSPF::SummaryLSA*, OSPF::LSAKeyType_Less>::iterator lsaIt = summaryLSAsByID.find(lsaKey); 01237 if (lsaIt == summaryLSAsByID.end()) { 01238 delete(lsaToReoriginate); 01239 lsaToReoriginate = NULL; 01240 return NULL; 01241 } 01242 01243 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA(*(lsaIt->second)); 01244 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01245 01246 lsaHeader.setLsAge(0); 01247 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01248 lsaHeader.setLinkStateID(newLinkStateID); 01249 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01250 01251 return summaryLSA; 01252 } else { 01253 lsaKey.linkStateID = newLinkStateID; 01254 lsaKey.advertisingRouter = parentRouter->GetRouterID(); 01255 01256 std::map<OSPF::LSAKeyType, bool, OSPF::LSAKeyType_Less>::const_iterator originatedIt = originatedLSAs.find(lsaKey); 01257 if (originatedIt != originatedLSAs.end()) { 01258 return NULL; 01259 } 01260 01261 OSPF::SummaryLSA* summaryLSA = new OSPF::SummaryLSA; 01262 OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01263 OSPFOptions lsOptions; 01264 01265 lsaHeader.setLsAge(0); 01266 memset(&lsOptions, 0, sizeof(OSPFOptions)); 01267 lsOptions.E_ExternalRoutingCapability = externalRoutingCapability; 01268 lsaHeader.setLsOptions(lsOptions); 01269 lsaHeader.setLsType(SummaryLSA_NetworksType); 01270 lsaHeader.setLinkStateID(newLinkStateID); 01271 lsaHeader.setAdvertisingRouter(parentRouter->GetRouterID()); 01272 lsaHeader.setLsSequenceNumber(INITIAL_SEQUENCE_NUMBER); 01273 01274 summaryLSA->setNetworkMask(entry->GetAddressMask()); 01275 summaryLSA->setRouteCost(entry->GetCost()); 01276 summaryLSA->setTosDataArraySize(0); 01277 01278 lsaHeader.setLsChecksum(0); // TODO: calculate correct LS checksum 01279 01280 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated); 01281 01282 return summaryLSA; 01283 } 01284 } 01285 } 01286 } 01287 } 01288 01289 return NULL; 01290 } 01291 01292 OSPF::SummaryLSA* OSPF::Area::OriginateSummaryLSA(const OSPF::SummaryLSA* summaryLSA) 01293 { 01294 const std::map<OSPF::LSAKeyType, bool, OSPF::LSAKeyType_Less> emptyMap; 01295 OSPF::SummaryLSA* dontReoriginate = NULL; 01296 01297 const OSPFLSAHeader& lsaHeader = summaryLSA->getHeader(); 01298 unsigned long entryCount = parentRouter->GetRoutingTableEntryCount(); 01299 01300 for (unsigned long i = 0; i < entryCount; i++) { 01301 const OSPF::RoutingTableEntry* entry = parentRouter->GetRoutingTableEntry(i); 01302 01303 if ((lsaHeader.getLsType() == SummaryLSA_ASBoundaryRoutersType) && 01304 ((((entry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 01305 ((entry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0)) && 01306 ((entry->GetDestinationID().getInt() == lsaHeader.getLinkStateID()) && 01307 (entry->GetAddressMask() == summaryLSA->getNetworkMask())))) 01308 { 01309 OSPF::SummaryLSA* returnLSA = OriginateSummaryLSA(entry, emptyMap, dontReoriginate); 01310 if (dontReoriginate != NULL) { 01311 delete dontReoriginate; 01312 } 01313 return returnLSA; 01314 } 01315 01316 unsigned long lsaMask = summaryLSA->getNetworkMask().getInt(); 01317 01318 if ((lsaHeader.getLsType() == SummaryLSA_NetworksType) && 01319 (entry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) && 01320 (entry->GetAddressMask().getInt() == lsaMask) && 01321 ((entry->GetDestinationID().getInt() & lsaMask) == (lsaHeader.getLinkStateID() & lsaMask))) 01322 { 01323 OSPF::SummaryLSA* returnLSA = OriginateSummaryLSA(entry, emptyMap, dontReoriginate); 01324 if (dontReoriginate != NULL) { 01325 delete dontReoriginate; 01326 } 01327 return returnLSA; 01328 } 01329 } 01330 01331 return NULL; 01332 } 01333 01334 void OSPF::Area::CalculateShortestPathTree(std::vector<OSPF::RoutingTableEntry*>& newRoutingTable) 01335 { 01336 OSPF::RouterID routerID = parentRouter->GetRouterID(); 01337 bool finished = false; 01338 std::vector<OSPFLSA*> treeVertices; 01339 OSPFLSA* justAddedVertex; 01340 std::vector<OSPFLSA*> candidateVertices; 01341 unsigned long i, j, k; 01342 unsigned long lsaCount; 01343 01344 if (spfTreeRoot == NULL) { 01345 OSPF::RouterLSA* newLSA = OriginateRouterLSA(); 01346 01347 InstallRouterLSA(newLSA); 01348 01349 OSPF::RouterLSA* routerLSA = FindRouterLSA(routerID); 01350 01351 spfTreeRoot = routerLSA; 01352 FloodLSA(newLSA); 01353 delete newLSA; 01354 } 01355 if (spfTreeRoot == NULL) { 01356 return; 01357 } 01358 01359 lsaCount = routerLSAs.size(); 01360 for (i = 0; i < lsaCount; i++) { 01361 routerLSAs[i]->ClearNextHops(); 01362 } 01363 lsaCount = networkLSAs.size(); 01364 for (i = 0; i < lsaCount; i++) { 01365 networkLSAs[i]->ClearNextHops(); 01366 } 01367 spfTreeRoot->SetDistance(0); 01368 treeVertices.push_back(spfTreeRoot); 01369 justAddedVertex = spfTreeRoot; // (1) 01370 01371 do { 01372 LSAType vertexType = static_cast<LSAType> (justAddedVertex->getHeader().getLsType()); 01373 01374 if ((vertexType == RouterLSAType)) { 01375 OSPF::RouterLSA* routerVertex = check_and_cast<OSPF::RouterLSA*> (justAddedVertex); 01376 if (routerVertex->getV_VirtualLinkEndpoint()) { // (2) 01377 transitCapability = true; 01378 } 01379 01380 unsigned int linkCount = routerVertex->getLinksArraySize(); 01381 for (i = 0; i < linkCount; i++) { 01382 Link& link = routerVertex->getLinks(i); 01383 LinkType linkType = static_cast<LinkType> (link.getType()); 01384 OSPFLSA* joiningVertex; 01385 LSAType joiningVertexType; 01386 01387 if (linkType == StubLink) { // (2) (a) 01388 continue; 01389 } 01390 01391 if (linkType == TransitLink) { 01392 joiningVertex = FindNetworkLSA(link.getLinkID().getInt()); 01393 joiningVertexType = NetworkLSAType; 01394 } else { 01395 joiningVertex = FindRouterLSA(link.getLinkID().getInt()); 01396 joiningVertexType = RouterLSAType; 01397 } 01398 01399 if ((joiningVertex == NULL) || 01400 (joiningVertex->getHeader().getLsAge() == MAX_AGE) || 01401 (!HasLink(joiningVertex, justAddedVertex))) // (from, to) (2) (b) 01402 { 01403 continue; 01404 } 01405 01406 unsigned int treeSize = treeVertices.size(); 01407 bool alreadyOnTree = false; 01408 01409 for (j = 0; j < treeSize; j++) { 01410 if (treeVertices[j] == joiningVertex) { 01411 alreadyOnTree = true; 01412 break; 01413 } 01414 } 01415 if (alreadyOnTree) { // (2) (c) 01416 continue; 01417 } 01418 01419 unsigned long linkStateCost = routerVertex->GetDistance() + link.getLinkCost(); 01420 unsigned int candidateCount = candidateVertices.size(); 01421 OSPFLSA* candidate = NULL; 01422 01423 for (j = 0; j < candidateCount; j++) { 01424 if (candidateVertices[j] == joiningVertex) { 01425 candidate = candidateVertices[j]; 01426 } 01427 } 01428 if (candidate != NULL) { // (2) (d) 01429 OSPF::RoutingInfo* routingInfo = check_and_cast<OSPF::RoutingInfo*> (candidate); 01430 unsigned long candidateDistance = routingInfo->GetDistance(); 01431 01432 if (linkStateCost > candidateDistance) { 01433 continue; 01434 } 01435 if (linkStateCost < candidateDistance) { 01436 routingInfo->SetDistance(linkStateCost); 01437 routingInfo->ClearNextHops(); 01438 } 01439 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(joiningVertex, justAddedVertex); // (destination, parent) 01440 unsigned int nextHopCount = newNextHops->size(); 01441 for (k = 0; k < nextHopCount; k++) { 01442 routingInfo->AddNextHop((*newNextHops)[k]); 01443 } 01444 delete newNextHops; 01445 } else { 01446 if (joiningVertexType == RouterLSAType) { 01447 OSPF::RouterLSA* joiningRouterVertex = check_and_cast<OSPF::RouterLSA*> (joiningVertex); 01448 joiningRouterVertex->SetDistance(linkStateCost); 01449 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(joiningVertex, justAddedVertex); // (destination, parent) 01450 unsigned int nextHopCount = newNextHops->size(); 01451 for (k = 0; k < nextHopCount; k++) { 01452 joiningRouterVertex->AddNextHop((*newNextHops)[k]); 01453 } 01454 delete newNextHops; 01455 OSPF::RoutingInfo* vertexRoutingInfo = check_and_cast<OSPF::RoutingInfo*> (joiningRouterVertex); 01456 vertexRoutingInfo->SetParent(justAddedVertex); 01457 01458 candidateVertices.push_back(joiningRouterVertex); 01459 } else { 01460 OSPF::NetworkLSA* joiningNetworkVertex = check_and_cast<OSPF::NetworkLSA*> (joiningVertex); 01461 joiningNetworkVertex->SetDistance(linkStateCost); 01462 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(joiningVertex, justAddedVertex); // (destination, parent) 01463 unsigned int nextHopCount = newNextHops->size(); 01464 for (k = 0; k < nextHopCount; k++) { 01465 joiningNetworkVertex->AddNextHop((*newNextHops)[k]); 01466 } 01467 delete newNextHops; 01468 OSPF::RoutingInfo* vertexRoutingInfo = check_and_cast<OSPF::RoutingInfo*> (joiningNetworkVertex); 01469 vertexRoutingInfo->SetParent(justAddedVertex); 01470 01471 candidateVertices.push_back(joiningNetworkVertex); 01472 } 01473 } 01474 } 01475 } 01476 01477 if ((vertexType == NetworkLSAType)) { 01478 OSPF::NetworkLSA* networkVertex = check_and_cast<OSPF::NetworkLSA*> (justAddedVertex); 01479 unsigned int routerCount = networkVertex->getAttachedRoutersArraySize(); 01480 01481 for (i = 0; i < routerCount; i++) { // (2) 01482 OSPF::RouterLSA* joiningVertex = FindRouterLSA(networkVertex->getAttachedRouters(i).getInt()); 01483 if ((joiningVertex == NULL) || 01484 (joiningVertex->getHeader().getLsAge() == MAX_AGE) || 01485 (!HasLink(joiningVertex, justAddedVertex))) // (from, to) (2) (b) 01486 { 01487 continue; 01488 } 01489 01490 unsigned int treeSize = treeVertices.size(); 01491 bool alreadyOnTree = false; 01492 01493 for (j = 0; j < treeSize; j++) { 01494 if (treeVertices[j] == joiningVertex) { 01495 alreadyOnTree = true; 01496 break; 01497 } 01498 } 01499 if (alreadyOnTree) { // (2) (c) 01500 continue; 01501 } 01502 01503 unsigned long linkStateCost = networkVertex->GetDistance(); // link cost from network to router is always 0 01504 unsigned int candidateCount = candidateVertices.size(); 01505 OSPFLSA* candidate = NULL; 01506 01507 for (j = 0; j < candidateCount; j++) { 01508 if (candidateVertices[j] == joiningVertex) { 01509 candidate = candidateVertices[j]; 01510 } 01511 } 01512 if (candidate != NULL) { // (2) (d) 01513 OSPF::RoutingInfo* routingInfo = check_and_cast<OSPF::RoutingInfo*> (candidate); 01514 unsigned long candidateDistance = routingInfo->GetDistance(); 01515 01516 if (linkStateCost > candidateDistance) { 01517 continue; 01518 } 01519 if (linkStateCost < candidateDistance) { 01520 routingInfo->SetDistance(linkStateCost); 01521 routingInfo->ClearNextHops(); 01522 } 01523 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(joiningVertex, justAddedVertex); // (destination, parent) 01524 unsigned int nextHopCount = newNextHops->size(); 01525 for (k = 0; k < nextHopCount; k++) { 01526 routingInfo->AddNextHop((*newNextHops)[k]); 01527 } 01528 delete newNextHops; 01529 } else { 01530 joiningVertex->SetDistance(linkStateCost); 01531 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(joiningVertex, justAddedVertex); // (destination, parent) 01532 unsigned int nextHopCount = newNextHops->size(); 01533 for (k = 0; k < nextHopCount; k++) { 01534 joiningVertex->AddNextHop((*newNextHops)[k]); 01535 } 01536 delete newNextHops; 01537 OSPF::RoutingInfo* vertexRoutingInfo = check_and_cast<OSPF::RoutingInfo*> (joiningVertex); 01538 vertexRoutingInfo->SetParent(justAddedVertex); 01539 01540 candidateVertices.push_back(joiningVertex); 01541 } 01542 } 01543 } 01544 01545 if (candidateVertices.empty()) { // (3) 01546 finished = true; 01547 } else { 01548 unsigned int candidateCount = candidateVertices.size(); 01549 unsigned long minDistance = LS_INFINITY; 01550 OSPFLSA* closestVertex = candidateVertices[0]; 01551 01552 for (i = 0; i < candidateCount; i++) { 01553 OSPF::RoutingInfo* routingInfo = check_and_cast<OSPF::RoutingInfo*> (candidateVertices[i]); 01554 unsigned long currentDistance = routingInfo->GetDistance(); 01555 01556 if (currentDistance < minDistance) { 01557 closestVertex = candidateVertices[i]; 01558 minDistance = currentDistance; 01559 } else { 01560 if (currentDistance == minDistance) { 01561 if ((closestVertex->getHeader().getLsType() == RouterLSAType) && 01562 (candidateVertices[i]->getHeader().getLsType() == NetworkLSAType)) 01563 { 01564 closestVertex = candidateVertices[i]; 01565 } 01566 } 01567 } 01568 } 01569 01570 treeVertices.push_back(closestVertex); 01571 01572 for (std::vector<OSPFLSA*>::iterator it = candidateVertices.begin(); it != candidateVertices.end(); it++) { 01573 if ((*it) == closestVertex) { 01574 candidateVertices.erase(it); 01575 break; 01576 } 01577 } 01578 01579 if (closestVertex->getHeader().getLsType() == RouterLSAType) { 01580 OSPF::RouterLSA* routerLSA = check_and_cast<OSPF::RouterLSA*> (closestVertex); 01581 if (routerLSA->getB_AreaBorderRouter() || routerLSA->getE_ASBoundaryRouter()) { 01582 OSPF::RoutingTableEntry* entry = new OSPF::RoutingTableEntry; 01583 OSPF::RouterID destinationID = routerLSA->getHeader().getLinkStateID(); 01584 unsigned int nextHopCount = routerLSA->GetNextHopCount(); 01585 OSPF::RoutingTableEntry::RoutingDestinationType destinationType = OSPF::RoutingTableEntry::NetworkDestination; 01586 01587 entry->SetDestinationID(destinationID); 01588 entry->SetLinkStateOrigin(routerLSA); 01589 entry->SetArea(areaID); 01590 entry->SetPathType(OSPF::RoutingTableEntry::IntraArea); 01591 entry->SetCost(routerLSA->GetDistance()); 01592 if (routerLSA->getB_AreaBorderRouter()) { 01593 destinationType |= OSPF::RoutingTableEntry::AreaBorderRouterDestination; 01594 } 01595 if (routerLSA->getE_ASBoundaryRouter()) { 01596 destinationType |= OSPF::RoutingTableEntry::ASBoundaryRouterDestination; 01597 } 01598 entry->SetDestinationType(destinationType); 01599 entry->SetOptionalCapabilities(routerLSA->getHeader().getLsOptions()); 01600 for (i = 0; i < nextHopCount; i++) { 01601 entry->AddNextHop(routerLSA->GetNextHop(i)); 01602 } 01603 01604 newRoutingTable.push_back(entry); 01605 01606 OSPF::Area* backbone; 01607 if (areaID != OSPF::BackboneAreaID) { 01608 backbone = parentRouter->GetArea(OSPF::BackboneAreaID); 01609 } else { 01610 backbone = this; 01611 } 01612 if (backbone != NULL) { 01613 OSPF::Interface* virtualIntf = backbone->FindVirtualLink(destinationID); 01614 if ((virtualIntf != NULL) && (virtualIntf->GetTransitAreaID() == areaID)) { 01615 OSPF::IPv4AddressRange range; 01616 range.address = GetInterface(routerLSA->GetNextHop(0).ifIndex)->GetAddressRange().address; 01617 range.mask = IPv4AddressFromULong(0xFFFFFFFF); 01618 virtualIntf->SetAddressRange(range); 01619 virtualIntf->SetIfIndex(routerLSA->GetNextHop(0).ifIndex); 01620 virtualIntf->SetOutputCost(routerLSA->GetDistance()); 01621 OSPF::Neighbor* virtualNeighbor = virtualIntf->GetNeighbor(0); 01622 if (virtualNeighbor != NULL) { 01623 unsigned int linkCount = routerLSA->getLinksArraySize(); 01624 OSPF::RouterLSA* toRouterLSA = dynamic_cast<OSPF::RouterLSA*> (justAddedVertex); 01625 if (toRouterLSA != NULL) { 01626 for (i = 0; i < linkCount; i++) { 01627 Link& link = routerLSA->getLinks(i); 01628 01629 if ((link.getType() == PointToPointLink) && 01630 (link.getLinkID() == toRouterLSA->getHeader().getLinkStateID()) && 01631 (virtualIntf->GetState() < OSPF::Interface::WaitingState)) 01632 { 01633 virtualNeighbor->SetAddress(IPv4AddressFromULong(link.getLinkData())); 01634 virtualIntf->ProcessEvent(OSPF::Interface::InterfaceUp); 01635 break; 01636 } 01637 } 01638 } else { 01639 OSPF::NetworkLSA* toNetworkLSA = dynamic_cast<OSPF::NetworkLSA*> (justAddedVertex); 01640 if (toNetworkLSA != NULL) { 01641 for (i = 0; i < linkCount; i++) { 01642 Link& link = routerLSA->getLinks(i); 01643 01644 if ((link.getType() == TransitLink) && 01645 (link.getLinkID() == toNetworkLSA->getHeader().getLinkStateID()) && 01646 (virtualIntf->GetState() < OSPF::Interface::WaitingState)) 01647 { 01648 virtualNeighbor->SetAddress(IPv4AddressFromULong(link.getLinkData())); 01649 virtualIntf->ProcessEvent(OSPF::Interface::InterfaceUp); 01650 break; 01651 } 01652 } 01653 } 01654 } 01655 } 01656 } 01657 } 01658 } 01659 } 01660 01661 if (closestVertex->getHeader().getLsType() == NetworkLSAType) { 01662 OSPF::NetworkLSA* networkLSA = check_and_cast<OSPF::NetworkLSA*> (closestVertex); 01663 unsigned long destinationID = (networkLSA->getHeader().getLinkStateID() & networkLSA->getNetworkMask().getInt()); 01664 unsigned int nextHopCount = networkLSA->GetNextHopCount(); 01665 bool overWrite = false; 01666 OSPF::RoutingTableEntry* entry = NULL; 01667 unsigned long routeCount = newRoutingTable.size(); 01668 unsigned long longestMatch = 0; 01669 01670 for (i = 0; i < routeCount; i++) { 01671 if (newRoutingTable[i]->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) { 01672 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[i]; 01673 unsigned long entryAddress = routingEntry->GetDestinationID().getInt(); 01674 unsigned long entryMask = routingEntry->GetAddressMask().getInt(); 01675 01676 if ((entryAddress & entryMask) == (destinationID & entryMask)) { 01677 if ((destinationID & entryMask) > longestMatch) { 01678 longestMatch = (destinationID & entryMask); 01679 entry = routingEntry; 01680 } 01681 } 01682 } 01683 } 01684 if (entry != NULL) { 01685 const OSPFLSA* entryOrigin = entry->GetLinkStateOrigin(); 01686 if ((entry->GetCost() != networkLSA->GetDistance()) || 01687 (entryOrigin->getHeader().getLinkStateID() >= networkLSA->getHeader().getLinkStateID())) 01688 { 01689 overWrite = true; 01690 } 01691 } 01692 01693 if ((entry == NULL) || (overWrite)) { 01694 if (entry == NULL) { 01695 entry = new OSPF::RoutingTableEntry; 01696 } 01697 01698 entry->SetDestinationID(destinationID); 01699 entry->SetAddressMask(networkLSA->getNetworkMask()); 01700 entry->SetLinkStateOrigin(networkLSA); 01701 entry->SetArea(areaID); 01702 entry->SetPathType(OSPF::RoutingTableEntry::IntraArea); 01703 entry->SetCost(networkLSA->GetDistance()); 01704 entry->SetDestinationType(OSPF::RoutingTableEntry::NetworkDestination); 01705 entry->SetOptionalCapabilities(networkLSA->getHeader().getLsOptions()); 01706 for (i = 0; i < nextHopCount; i++) { 01707 entry->AddNextHop(networkLSA->GetNextHop(i)); 01708 } 01709 01710 if (!overWrite) { 01711 newRoutingTable.push_back(entry); 01712 } 01713 } 01714 } 01715 01716 justAddedVertex = closestVertex; 01717 } 01718 } while (!finished); 01719 01720 unsigned int treeSize = treeVertices.size(); 01721 for (i = 0; i < treeSize; i++) { 01722 OSPF::RouterLSA* routerVertex = dynamic_cast<OSPF::RouterLSA*> (treeVertices[i]); 01723 if (routerVertex == NULL) { 01724 continue; 01725 } 01726 01727 unsigned int linkCount = routerVertex->getLinksArraySize(); 01728 for (j = 0; j < linkCount; j++) { 01729 Link& link = routerVertex->getLinks(j); 01730 if (link.getType() != StubLink) { 01731 continue; 01732 } 01733 01734 unsigned long distance = routerVertex->GetDistance() + link.getLinkCost(); 01735 unsigned long destinationID = (link.getLinkID().getInt() & link.getLinkData()); 01736 OSPF::RoutingTableEntry* entry = NULL; 01737 unsigned long routeCount = newRoutingTable.size(); 01738 unsigned long longestMatch = 0; 01739 01740 for (k = 0; k < routeCount; k++) { 01741 if (newRoutingTable[k]->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) { 01742 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[k]; 01743 unsigned long entryAddress = routingEntry->GetDestinationID().getInt(); 01744 unsigned long entryMask = routingEntry->GetAddressMask().getInt(); 01745 01746 if ((entryAddress & entryMask) == (destinationID & entryMask)) { 01747 if ((destinationID & entryMask) > longestMatch) { 01748 longestMatch = (destinationID & entryMask); 01749 entry = routingEntry; 01750 } 01751 } 01752 } 01753 } 01754 01755 if (entry != NULL) { 01756 Metric entryCost = entry->GetCost(); 01757 01758 if (distance > entryCost) { 01759 continue; 01760 } 01761 if (distance < entryCost) { 01762 //FIXME remove 01763 //if(parentRouter->GetRouterID() == 0xC0A80302) { 01764 // EV << "CHEAPER STUB LINK FOUND TO " << IPAddress(destinationID).str() << "\n"; 01765 //} 01766 entry->SetCost(distance); 01767 entry->ClearNextHops(); 01768 entry->SetLinkStateOrigin(routerVertex); 01769 } 01770 if (distance == entryCost) { 01771 // no const version from check_and_cast 01772 OSPF::RouterLSA* routerOrigin = check_and_cast<OSPF::RouterLSA*> (const_cast<OSPFLSA*> (entry->GetLinkStateOrigin())); 01773 if (routerOrigin->getHeader().getLinkStateID() < routerVertex->getHeader().getLinkStateID()) { 01774 entry->SetLinkStateOrigin(routerVertex); 01775 } 01776 } 01777 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(link, routerVertex); // (destination, parent) 01778 unsigned int nextHopCount = newNextHops->size(); 01779 for (k = 0; k < nextHopCount; k++) { 01780 entry->AddNextHop((*newNextHops)[k]); 01781 } 01782 delete newNextHops; 01783 } else { 01784 //FIXME remove 01785 //if(parentRouter->GetRouterID() == 0xC0A80302) { 01786 // EV << "STUB LINK FOUND TO " << IPAddress(destinationID).str() << "\n"; 01787 //} 01788 entry = new OSPF::RoutingTableEntry; 01789 01790 entry->SetDestinationID(destinationID); 01791 entry->SetAddressMask(link.getLinkData()); 01792 entry->SetLinkStateOrigin(routerVertex); 01793 entry->SetArea(areaID); 01794 entry->SetPathType(OSPF::RoutingTableEntry::IntraArea); 01795 entry->SetCost(distance); 01796 entry->SetDestinationType(OSPF::RoutingTableEntry::NetworkDestination); 01797 entry->SetOptionalCapabilities(routerVertex->getHeader().getLsOptions()); 01798 std::vector<OSPF::NextHop>* newNextHops = CalculateNextHops(link, routerVertex); // (destination, parent) 01799 unsigned int nextHopCount = newNextHops->size(); 01800 for (k = 0; k < nextHopCount; k++) { 01801 entry->AddNextHop((*newNextHops)[k]); 01802 } 01803 delete newNextHops; 01804 01805 newRoutingTable.push_back(entry); 01806 } 01807 } 01808 } 01809 } 01810 01811 std::vector<OSPF::NextHop>* OSPF::Area::CalculateNextHops(OSPFLSA* destination, OSPFLSA* parent) const 01812 { 01813 std::vector<OSPF::NextHop>* hops = new std::vector<OSPF::NextHop>; 01814 unsigned long i, j; 01815 01816 OSPF::RouterLSA* routerLSA = dynamic_cast<OSPF::RouterLSA*> (parent); 01817 if (routerLSA != NULL) { 01818 if (routerLSA != spfTreeRoot) { 01819 unsigned int nextHopCount = routerLSA->GetNextHopCount(); 01820 for (i = 0; i < nextHopCount; i++) { 01821 hops->push_back(routerLSA->GetNextHop(i)); 01822 } 01823 return hops; 01824 } else { 01825 OSPF::RouterLSA* destinationRouterLSA = dynamic_cast<OSPF::RouterLSA*> (destination); 01826 if (destinationRouterLSA != NULL) { 01827 unsigned long interfaceNum = associatedInterfaces.size(); 01828 for (i = 0; i < interfaceNum; i++) { 01829 OSPF::Interface::OSPFInterfaceType intfType = associatedInterfaces[i]->GetType(); 01830 if ((intfType == OSPF::Interface::PointToPoint) || 01831 ((intfType == OSPF::Interface::Virtual) && 01832 (associatedInterfaces[i]->GetState() > OSPF::Interface::LoopbackState))) 01833 { 01834 OSPF::Neighbor* ptpNeighbor = associatedInterfaces[i]->GetNeighborCount() > 0 ? associatedInterfaces[i]->GetNeighbor(0) : NULL; 01835 if (ptpNeighbor != NULL) { 01836 if (ptpNeighbor->GetNeighborID() == destinationRouterLSA->getHeader().getLinkStateID()) { 01837 NextHop nextHop; 01838 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 01839 nextHop.hopAddress = ptpNeighbor->GetAddress(); 01840 nextHop.advertisingRouter = destinationRouterLSA->getHeader().getAdvertisingRouter().getInt(); 01841 hops->push_back(nextHop); 01842 break; 01843 } 01844 } 01845 } 01846 if (intfType == OSPF::Interface::PointToMultiPoint) { 01847 OSPF::Neighbor* ptmpNeighbor = associatedInterfaces[i]->GetNeighborByID(destinationRouterLSA->getHeader().getLinkStateID()); 01848 if (ptmpNeighbor != NULL) { 01849 unsigned int linkCount = destinationRouterLSA->getLinksArraySize(); 01850 OSPF::RouterID rootID = parentRouter->GetRouterID(); 01851 for (j = 0; j < linkCount; j++) { 01852 Link& link = destinationRouterLSA->getLinks(j); 01853 if (link.getLinkID() == rootID) { 01854 NextHop nextHop; 01855 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 01856 nextHop.hopAddress = IPv4AddressFromULong(link.getLinkData()); 01857 nextHop.advertisingRouter = destinationRouterLSA->getHeader().getAdvertisingRouter().getInt(); 01858 hops->push_back(nextHop); 01859 } 01860 } 01861 break; 01862 } 01863 } 01864 } 01865 } else { 01866 OSPF::NetworkLSA* destinationNetworkLSA = dynamic_cast<OSPF::NetworkLSA*> (destination); 01867 if (destinationNetworkLSA != NULL) { 01868 OSPF::IPv4Address networkDesignatedRouter = IPv4AddressFromULong(destinationNetworkLSA->getHeader().getLinkStateID()); 01869 unsigned long interfaceNum = associatedInterfaces.size(); 01870 for (i = 0; i < interfaceNum; i++) { 01871 OSPF::Interface::OSPFInterfaceType intfType = associatedInterfaces[i]->GetType(); 01872 if (((intfType == OSPF::Interface::Broadcast) || 01873 (intfType == OSPF::Interface::NBMA)) && 01874 (associatedInterfaces[i]->GetDesignatedRouter().ipInterfaceAddress == networkDesignatedRouter)) 01875 { 01876 OSPF::IPv4AddressRange range = associatedInterfaces[i]->GetAddressRange(); 01877 NextHop nextHop; 01878 01879 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 01880 nextHop.hopAddress = (range.address & range.mask); 01881 nextHop.advertisingRouter = destinationNetworkLSA->getHeader().getAdvertisingRouter().getInt(); 01882 hops->push_back(nextHop); 01883 } 01884 } 01885 } 01886 } 01887 } 01888 } else { 01889 OSPF::NetworkLSA* networkLSA = dynamic_cast<OSPF::NetworkLSA*> (parent); 01890 if (networkLSA != NULL) { 01891 if (networkLSA->GetParent() != spfTreeRoot) { 01892 unsigned int nextHopCount = networkLSA->GetNextHopCount(); 01893 for (i = 0; i < nextHopCount; i++) { 01894 hops->push_back(networkLSA->GetNextHop(i)); 01895 } 01896 return hops; 01897 } else { 01898 unsigned long parentLinkStateID = parent->getHeader().getLinkStateID(); 01899 01900 OSPF::RouterLSA* destinationRouterLSA = dynamic_cast<OSPF::RouterLSA*> (destination); 01901 if (destinationRouterLSA != NULL) { 01902 OSPF::RouterID destinationRouterID = destinationRouterLSA->getHeader().getLinkStateID(); 01903 unsigned int linkCount = destinationRouterLSA->getLinksArraySize(); 01904 for (i = 0; i < linkCount; i++) { 01905 Link& link = destinationRouterLSA->getLinks(i); 01906 NextHop nextHop; 01907 01908 if (((link.getType() == TransitLink) && 01909 (link.getLinkID().getInt() == parentLinkStateID)) || 01910 ((link.getType() == StubLink) && 01911 ((link.getLinkID().getInt() & link.getLinkData()) == (parentLinkStateID & networkLSA->getNetworkMask().getInt())))) 01912 { 01913 unsigned long interfaceNum = associatedInterfaces.size(); 01914 for (j = 0; j < interfaceNum; j++) { 01915 OSPF::Interface::OSPFInterfaceType intfType = associatedInterfaces[j]->GetType(); 01916 if (((intfType == OSPF::Interface::Broadcast) || 01917 (intfType == OSPF::Interface::NBMA)) && 01918 (associatedInterfaces[j]->GetDesignatedRouter().ipInterfaceAddress == IPv4AddressFromULong(parentLinkStateID))) 01919 { 01920 OSPF::Neighbor* nextHopNeighbor = associatedInterfaces[j]->GetNeighborByID(destinationRouterID); 01921 if (nextHopNeighbor != NULL) { 01922 nextHop.ifIndex = associatedInterfaces[j]->GetIfIndex(); 01923 nextHop.hopAddress = nextHopNeighbor->GetAddress(); 01924 nextHop.advertisingRouter = destinationRouterLSA->getHeader().getAdvertisingRouter().getInt(); 01925 hops->push_back(nextHop); 01926 } 01927 } 01928 } 01929 } 01930 } 01931 } 01932 } 01933 } 01934 } 01935 01936 return hops; 01937 } 01938 01939 std::vector<OSPF::NextHop>* OSPF::Area::CalculateNextHops(Link& destination, OSPFLSA* parent) const 01940 { 01941 std::vector<OSPF::NextHop>* hops = new std::vector<OSPF::NextHop>; 01942 unsigned long i; 01943 01944 OSPF::RouterLSA* routerLSA = check_and_cast<OSPF::RouterLSA*> (parent); 01945 if (routerLSA != spfTreeRoot) { 01946 unsigned int nextHopCount = routerLSA->GetNextHopCount(); 01947 for (i = 0; i < nextHopCount; i++) { 01948 hops->push_back(routerLSA->GetNextHop(i)); 01949 } 01950 return hops; 01951 } else { 01952 unsigned long interfaceNum = associatedInterfaces.size(); 01953 for (i = 0; i < interfaceNum; i++) { 01954 OSPF::Interface::OSPFInterfaceType intfType = associatedInterfaces[i]->GetType(); 01955 01956 if ((intfType == OSPF::Interface::PointToPoint) || 01957 ((intfType == OSPF::Interface::Virtual) && 01958 (associatedInterfaces[i]->GetState() > OSPF::Interface::LoopbackState))) 01959 { 01960 OSPF::Neighbor* neighbor = (associatedInterfaces[i]->GetNeighborCount() > 0) ? associatedInterfaces[i]->GetNeighbor(0) : NULL; 01961 if (neighbor != NULL) { 01962 OSPF::IPv4Address neighborAddress = neighbor->GetAddress(); 01963 if (((neighborAddress != OSPF::NullIPv4Address) && 01964 (ULongFromIPv4Address(neighborAddress) == destination.getLinkID().getInt())) || 01965 ((neighborAddress == OSPF::NullIPv4Address) && 01966 (ULongFromIPv4Address(associatedInterfaces[i]->GetAddressRange().address) == destination.getLinkID().getInt()) && 01967 (ULongFromIPv4Address(associatedInterfaces[i]->GetAddressRange().mask) == destination.getLinkData()))) 01968 { 01969 NextHop nextHop; 01970 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 01971 nextHop.hopAddress = neighborAddress; 01972 nextHop.advertisingRouter = parentRouter->GetRouterID(); 01973 hops->push_back(nextHop); 01974 break; 01975 } 01976 } 01977 } 01978 if ((intfType == OSPF::Interface::Broadcast) || 01979 (intfType == OSPF::Interface::NBMA)) 01980 { 01981 if ((destination.getLinkID().getInt() == ULongFromIPv4Address(associatedInterfaces[i]->GetAddressRange().address & associatedInterfaces[i]->GetAddressRange().mask)) && 01982 (destination.getLinkData() == ULongFromIPv4Address(associatedInterfaces[i]->GetAddressRange().mask))) 01983 { 01984 NextHop nextHop; 01985 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 01986 nextHop.hopAddress = IPv4AddressFromULong(destination.getLinkID().getInt()); 01987 nextHop.advertisingRouter = parentRouter->GetRouterID(); 01988 hops->push_back(nextHop); 01989 break; 01990 } 01991 } 01992 if (intfType == OSPF::Interface::PointToMultiPoint) { 01993 if (destination.getType() == StubLink) { 01994 if (destination.getLinkID().getInt() == ULongFromIPv4Address(associatedInterfaces[i]->GetAddressRange().address)) { 01995 // The link contains the router's own interface address and a full mask, 01996 // so we insert a next hop pointing to the interface itself. Kind of pointless, but 01997 // not much else we could do... 01998 // TODO: check what other OSPF implementations do in this situation 01999 NextHop nextHop; 02000 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 02001 nextHop.hopAddress = associatedInterfaces[i]->GetAddressRange().address; 02002 nextHop.advertisingRouter = parentRouter->GetRouterID(); 02003 hops->push_back(nextHop); 02004 break; 02005 } 02006 } 02007 if (destination.getType() == PointToPointLink) { 02008 OSPF::Neighbor* neighbor = associatedInterfaces[i]->GetNeighborByID(destination.getLinkID().getInt()); 02009 if (neighbor != NULL) { 02010 NextHop nextHop; 02011 nextHop.ifIndex = associatedInterfaces[i]->GetIfIndex(); 02012 nextHop.hopAddress = neighbor->GetAddress(); 02013 nextHop.advertisingRouter = parentRouter->GetRouterID(); 02014 hops->push_back(nextHop); 02015 break; 02016 } 02017 } 02018 } 02019 // next hops for virtual links are generated later, after examining transit areas' SummaryLSAs 02020 } 02021 02022 if (hops->size() == 0) { 02023 unsigned long hostRouteCount = hostRoutes.size(); 02024 for (i = 0; i < hostRouteCount; i++) { 02025 if ((destination.getLinkID().getInt() == ULongFromIPv4Address(hostRoutes[i].address)) && 02026 (destination.getLinkData() == 0xFFFFFFFF)) 02027 { 02028 NextHop nextHop; 02029 nextHop.ifIndex = hostRoutes[i].ifIndex; 02030 nextHop.hopAddress = hostRoutes[i].address; 02031 nextHop.advertisingRouter = parentRouter->GetRouterID(); 02032 hops->push_back(nextHop); 02033 break; 02034 } 02035 } 02036 } 02037 } 02038 02039 return hops; 02040 } 02041 02042 bool OSPF::Area::HasLink(OSPFLSA* fromLSA, OSPFLSA* toLSA) const 02043 { 02044 unsigned int i; 02045 02046 OSPF::RouterLSA* fromRouterLSA = dynamic_cast<OSPF::RouterLSA*> (fromLSA); 02047 if (fromRouterLSA != NULL) { 02048 unsigned int linkCount = fromRouterLSA->getLinksArraySize(); 02049 OSPF::RouterLSA* toRouterLSA = dynamic_cast<OSPF::RouterLSA*> (toLSA); 02050 if (toRouterLSA != NULL) { 02051 for (i = 0; i < linkCount; i++) { 02052 Link& link = fromRouterLSA->getLinks(i); 02053 LinkType linkType = static_cast<LinkType> (link.getType()); 02054 02055 if (((linkType == PointToPointLink) || 02056 (linkType == VirtualLink)) && 02057 (link.getLinkID().getInt() == toRouterLSA->getHeader().getLinkStateID())) 02058 { 02059 return true; 02060 } 02061 } 02062 } else { 02063 OSPF::NetworkLSA* toNetworkLSA = dynamic_cast<OSPF::NetworkLSA*> (toLSA); 02064 if (toNetworkLSA != NULL) { 02065 for (i = 0; i < linkCount; i++) { 02066 Link& link = fromRouterLSA->getLinks(i); 02067 02068 if ((link.getType() == TransitLink) && 02069 (link.getLinkID().getInt() == toNetworkLSA->getHeader().getLinkStateID())) 02070 { 02071 return true; 02072 } 02073 if ((link.getType() == StubLink) && 02074 ((link.getLinkID().getInt() & link.getLinkData()) == (toNetworkLSA->getHeader().getLinkStateID() & toNetworkLSA->getNetworkMask().getInt()))) 02075 { 02076 return true; 02077 } 02078 } 02079 } 02080 } 02081 } else { 02082 OSPF::NetworkLSA* fromNetworkLSA = dynamic_cast<OSPF::NetworkLSA*> (fromLSA); 02083 if (fromNetworkLSA != NULL) { 02084 unsigned int routerCount = fromNetworkLSA->getAttachedRoutersArraySize(); 02085 OSPF::RouterLSA* toRouterLSA = dynamic_cast<OSPF::RouterLSA*> (toLSA); 02086 if (toRouterLSA != NULL) { 02087 for (i = 0; i < routerCount; i++) { 02088 if (fromNetworkLSA->getAttachedRouters(i).getInt() == toRouterLSA->getHeader().getLinkStateID()) { 02089 return true; 02090 } 02091 } 02092 } 02093 } 02094 } 02095 02096 return false; 02097 } 02098 02104 bool OSPF::Area::FindSameOrWorseCostRoute(const std::vector<OSPF::RoutingTableEntry*>& newRoutingTable, 02105 const OSPF::SummaryLSA& summaryLSA, 02106 unsigned short currentCost, 02107 bool& destinationInRoutingTable, 02108 std::list<OSPF::RoutingTableEntry*>& sameOrWorseCost) const 02109 { 02110 destinationInRoutingTable = false; 02111 sameOrWorseCost.clear(); 02112 02113 long routeCount = newRoutingTable.size(); 02114 OSPF::IPv4AddressRange destination; 02115 02116 destination.address = IPv4AddressFromULong(summaryLSA.getHeader().getLinkStateID()); 02117 destination.mask = IPv4AddressFromULong(summaryLSA.getNetworkMask().getInt()); 02118 02119 for (long j = 0; j < routeCount; j++) { 02120 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[j]; 02121 bool foundMatching = false; 02122 02123 if (summaryLSA.getHeader().getLsType() == SummaryLSA_NetworksType) { 02124 if ((routingEntry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) && 02125 (ULongFromIPv4Address(destination.address & destination.mask) == routingEntry->GetDestinationID().getInt())) 02126 { 02127 foundMatching = true; 02128 } 02129 } else { 02130 if ((((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 02131 ((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0)) && 02132 (ULongFromIPv4Address(destination.address) == routingEntry->GetDestinationID().getInt())) 02133 { 02134 foundMatching = true; 02135 } 02136 } 02137 02138 if (foundMatching) { 02139 destinationInRoutingTable = true; 02140 02141 /* If the matching entry is an IntraArea getRoute(intra-area paths are 02142 * always preferred to other paths of any cost), or it's a cheaper InterArea 02143 * route, then skip this LSA. 02144 */ 02145 if ((routingEntry->GetPathType() == OSPF::RoutingTableEntry::IntraArea) || 02146 ((routingEntry->GetPathType() == OSPF::RoutingTableEntry::InterArea) && 02147 (routingEntry->GetCost() < currentCost))) 02148 { 02149 return true; 02150 } else { 02151 // if it's an other InterArea path 02152 if ((routingEntry->GetPathType() == OSPF::RoutingTableEntry::InterArea) && 02153 (routingEntry->GetCost() >= currentCost)) 02154 { 02155 sameOrWorseCost.push_back(routingEntry); 02156 } // else it's external -> same as if not in the table 02157 } 02158 } 02159 } 02160 return false; 02161 } 02162 02167 OSPF::RoutingTableEntry* OSPF::Area::CreateRoutingTableEntryFromSummaryLSA(const OSPF::SummaryLSA& summaryLSA, 02168 unsigned short entryCost, 02169 const OSPF::RoutingTableEntry& borderRouterEntry) const 02170 { 02171 OSPF::IPv4AddressRange destination; 02172 02173 destination.address = IPv4AddressFromULong(summaryLSA.getHeader().getLinkStateID()); 02174 destination.mask = IPv4AddressFromULong(summaryLSA.getNetworkMask().getInt()); 02175 02176 OSPF::RoutingTableEntry* newEntry = new OSPF::RoutingTableEntry; 02177 02178 if (summaryLSA.getHeader().getLsType() == SummaryLSA_NetworksType) { 02179 newEntry->SetDestinationID(ULongFromIPv4Address(destination.address & destination.mask)); 02180 newEntry->SetAddressMask(ULongFromIPv4Address(destination.mask)); 02181 newEntry->SetDestinationType(OSPF::RoutingTableEntry::NetworkDestination); 02182 } else { 02183 newEntry->SetDestinationID(ULongFromIPv4Address(destination.address)); 02184 newEntry->SetAddressMask(0xFFFFFFFF); 02185 newEntry->SetDestinationType(OSPF::RoutingTableEntry::ASBoundaryRouterDestination); 02186 } 02187 newEntry->SetArea(areaID); 02188 newEntry->SetPathType(OSPF::RoutingTableEntry::InterArea); 02189 newEntry->SetCost(entryCost); 02190 newEntry->SetOptionalCapabilities(summaryLSA.getHeader().getLsOptions()); 02191 newEntry->SetLinkStateOrigin(&summaryLSA); 02192 02193 unsigned int nextHopCount = borderRouterEntry.GetNextHopCount(); 02194 for (unsigned int j = 0; j < nextHopCount; j++) { 02195 newEntry->AddNextHop(borderRouterEntry.GetNextHop(j)); 02196 } 02197 02198 return newEntry; 02199 } 02200 02207 void OSPF::Area::CalculateInterAreaRoutes(std::vector<OSPF::RoutingTableEntry*>& newRoutingTable) 02208 { 02209 unsigned long i = 0; 02210 unsigned long j = 0; 02211 unsigned long lsaCount = summaryLSAs.size(); 02212 02213 for (i = 0; i < lsaCount; i++) { 02214 OSPF::SummaryLSA* currentLSA = summaryLSAs[i]; 02215 OSPFLSAHeader& currentHeader = currentLSA->getHeader(); 02216 02217 unsigned long routeCost = currentLSA->getRouteCost(); 02218 unsigned short lsAge = currentHeader.getLsAge(); 02219 RouterID originatingRouter = currentHeader.getAdvertisingRouter().getInt(); 02220 bool selfOriginated = (originatingRouter == parentRouter->GetRouterID()); 02221 02222 if ((routeCost == LS_INFINITY) || (lsAge == MAX_AGE) || (selfOriginated)) { // (1) and(2) 02223 continue; 02224 } 02225 02226 char lsType = currentHeader.getLsType(); 02227 unsigned long routeCount = newRoutingTable.size(); 02228 OSPF::IPv4AddressRange destination; 02229 02230 destination.address = IPv4AddressFromULong(currentHeader.getLinkStateID()); 02231 destination.mask = IPv4AddressFromULong(currentLSA->getNetworkMask().getInt()); 02232 02233 if ((lsType == SummaryLSA_NetworksType) && (parentRouter->HasAddressRange(destination))) { // (3) 02234 bool foundIntraAreaRoute = false; 02235 02236 // look for an "Active" IntraArea route 02237 for (j = 0; j < routeCount; j++) { 02238 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[j]; 02239 02240 if ((routingEntry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) && 02241 (routingEntry->GetPathType() == OSPF::RoutingTableEntry::IntraArea) && 02242 ((routingEntry->GetDestinationID().getInt() & 02243 routingEntry->GetAddressMask().getInt() & 02244 ULongFromIPv4Address(destination.mask) ) == ULongFromIPv4Address(destination.address & 02245 destination.mask))) 02246 { 02247 foundIntraAreaRoute = true; 02248 break; 02249 } 02250 } 02251 if (foundIntraAreaRoute) { 02252 continue; 02253 } 02254 } 02255 02256 OSPF::RoutingTableEntry* borderRouterEntry = NULL; 02257 02258 // The routingEntry describes a route to an other area -> look for the border router originating it 02259 for (j = 0; j < routeCount; j++) { // (4) N == destination, BR == borderRouterEntry 02260 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[j]; 02261 02262 if ((routingEntry->GetArea() == areaID) && 02263 (((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 02264 ((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0)) && 02265 (routingEntry->GetDestinationID().getInt() == originatingRouter)) 02266 { 02267 borderRouterEntry = routingEntry; 02268 break; 02269 } 02270 } 02271 if (borderRouterEntry == NULL) { 02272 continue; 02273 } else { // (5) 02274 /* "Else, this LSA describes an inter-area path to destination N, 02275 * whose cost is the distance to BR plus the cost specified in the LSA. 02276 * Call the cost of this inter-area path IAC." 02277 */ 02278 bool destinationInRoutingTable = true; 02279 unsigned short currentCost = routeCost + borderRouterEntry->GetCost(); 02280 std::list<OSPF::RoutingTableEntry*> sameOrWorseCost; 02281 02282 if (FindSameOrWorseCostRoute(newRoutingTable, 02283 *currentLSA, 02284 currentCost, 02285 destinationInRoutingTable, 02286 sameOrWorseCost)) 02287 { 02288 continue; 02289 } 02290 02291 if (destinationInRoutingTable && (sameOrWorseCost.size() > 0)) { 02292 OSPF::RoutingTableEntry* equalEntry = NULL; 02293 02294 /* Look for an equal cost entry in the sameOrWorseCost list, and 02295 * also clear the more expensive entries from the newRoutingTable. 02296 */ 02297 for (std::list<OSPF::RoutingTableEntry*>::iterator it = sameOrWorseCost.begin(); it != sameOrWorseCost.end(); it++) { 02298 OSPF::RoutingTableEntry* checkedEntry = (*it); 02299 02300 if (checkedEntry->GetCost() > currentCost) { 02301 for (std::vector<OSPF::RoutingTableEntry*>::iterator entryIt = newRoutingTable.begin(); entryIt != newRoutingTable.end(); entryIt++) { 02302 if (checkedEntry == (*entryIt)) { 02303 newRoutingTable.erase(entryIt); 02304 break; 02305 } 02306 } 02307 } else { // EntryCost == currentCost 02308 equalEntry = checkedEntry; // should be only one - if there are more they are ignored 02309 } 02310 } 02311 02312 unsigned long nextHopCount = borderRouterEntry->GetNextHopCount(); 02313 02314 if (equalEntry != NULL) { 02315 /* Add the next hops of the border router advertising this destination 02316 * to the equal entry. 02317 */ 02318 for (unsigned long j = 0; j < nextHopCount; j++) { 02319 equalEntry->AddNextHop(borderRouterEntry->GetNextHop(j)); 02320 } 02321 } else { 02322 OSPF::RoutingTableEntry* newEntry = CreateRoutingTableEntryFromSummaryLSA(*currentLSA, currentCost, *borderRouterEntry); 02323 ASSERT(newEntry != NULL); 02324 newRoutingTable.push_back(newEntry); 02325 } 02326 } else { 02327 OSPF::RoutingTableEntry* newEntry = CreateRoutingTableEntryFromSummaryLSA(*currentLSA, currentCost, *borderRouterEntry); 02328 ASSERT(newEntry != NULL); 02329 newRoutingTable.push_back(newEntry); 02330 } 02331 } 02332 } 02333 } 02334 02335 void OSPF::Area::ReCheckSummaryLSAs(std::vector<OSPF::RoutingTableEntry*>& newRoutingTable) 02336 { 02337 unsigned long i = 0; 02338 unsigned long j = 0; 02339 unsigned long lsaCount = summaryLSAs.size(); 02340 02341 for (i = 0; i < lsaCount; i++) { 02342 OSPF::SummaryLSA* currentLSA = summaryLSAs[i]; 02343 OSPFLSAHeader& currentHeader = currentLSA->getHeader(); 02344 02345 unsigned long routeCost = currentLSA->getRouteCost(); 02346 unsigned short lsAge = currentHeader.getLsAge(); 02347 RouterID originatingRouter = currentHeader.getAdvertisingRouter().getInt(); 02348 bool selfOriginated = (originatingRouter == parentRouter->GetRouterID()); 02349 02350 if ((routeCost == LS_INFINITY) || (lsAge == MAX_AGE) || (selfOriginated)) { // (1) and(2) 02351 continue; 02352 } 02353 02354 unsigned long routeCount = newRoutingTable.size(); 02355 char lsType = currentHeader.getLsType(); 02356 OSPF::RoutingTableEntry* destinationEntry = NULL; 02357 OSPF::IPv4AddressRange destination; 02358 02359 destination.address = IPv4AddressFromULong(currentHeader.getLinkStateID()); 02360 destination.mask = IPv4AddressFromULong(currentLSA->getNetworkMask().getInt()); 02361 02362 for (j = 0; j < routeCount; j++) { // (3) 02363 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[j]; 02364 bool foundMatching = false; 02365 02366 if (lsType == SummaryLSA_NetworksType) { 02367 if ((routingEntry->GetDestinationType() == OSPF::RoutingTableEntry::NetworkDestination) && 02368 (ULongFromIPv4Address(destination.address & destination.mask) == routingEntry->GetDestinationID().getInt())) 02369 { 02370 foundMatching = true; 02371 } 02372 } else { 02373 if ((((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 02374 ((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0)) && 02375 (ULongFromIPv4Address(destination.address) == routingEntry->GetDestinationID().getInt())) 02376 { 02377 foundMatching = true; 02378 } 02379 } 02380 02381 if (foundMatching) { 02382 OSPF::RoutingTableEntry::RoutingPathType pathType = routingEntry->GetPathType(); 02383 02384 if ((pathType == OSPF::RoutingTableEntry::Type1External) || 02385 (pathType == OSPF::RoutingTableEntry::Type2External) || 02386 (routingEntry->GetArea() != OSPF::BackboneAreaID)) 02387 { 02388 break; 02389 } else { 02390 destinationEntry = routingEntry; 02391 break; 02392 } 02393 } 02394 } 02395 if (destinationEntry == NULL) { 02396 continue; 02397 } 02398 02399 OSPF::RoutingTableEntry* borderRouterEntry = NULL; 02400 unsigned short currentCost = routeCost; 02401 02402 for (j = 0; j < routeCount; j++) { // (4) BR == borderRouterEntry 02403 OSPF::RoutingTableEntry* routingEntry = newRoutingTable[j]; 02404 02405 if ((routingEntry->GetArea() == areaID) && 02406 (((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::AreaBorderRouterDestination) != 0) || 02407 ((routingEntry->GetDestinationType() & OSPF::RoutingTableEntry::ASBoundaryRouterDestination) != 0)) && 02408 (routingEntry->GetDestinationID().getInt() == originatingRouter)) 02409 { 02410 borderRouterEntry = routingEntry; 02411 currentCost += borderRouterEntry->GetCost(); 02412 break; 02413 } 02414 } 02415 if (borderRouterEntry == NULL) { 02416 continue; 02417 } else { // (5) 02418 if (currentCost <= destinationEntry->GetCost()) { 02419 if (currentCost < destinationEntry->GetCost()) { 02420 destinationEntry->ClearNextHops(); 02421 } 02422 02423 unsigned long nextHopCount = borderRouterEntry->GetNextHopCount(); 02424 02425 for (j = 0; j < nextHopCount; j++) { 02426 destinationEntry->AddNextHop(borderRouterEntry->GetNextHop(j)); 02427 } 02428 } 02429 } 02430 } 02431 }
1.7.6.1