00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
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 ) 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);
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);
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);
00470 rebuildRoutingTable |= lsa->Update(newLSA);
00471 delete newLSA;
00472 } else {
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);
00507 rebuildRoutingTable |= lsa->Update(newLSA);
00508 delete newLSA;
00509
00510 FloodLSA(lsa);
00511 } else {
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);
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);
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);
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);
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);
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);
01081
01082 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated);
01083
01084 return summaryLSA;
01085 }
01086 } else {
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);
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);
01136
01137 summaryLSA->SetSource(OSPF::LSATrackingInfo::Originated);
01138
01139 return summaryLSA;
01140 }
01141 } else {
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) &&
01150 (transitCapability)) ||
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);
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);
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);
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);
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;
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()) {
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) {
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)))
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) {
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) {
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);
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);
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);
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++) {
01482 OSPF::RouterLSA* joiningVertex = FindRouterLSA(networkVertex->getAttachedRouters(i).getInt());
01483 if ((joiningVertex == NULL) ||
01484 (joiningVertex->getHeader().getLsAge() == MAX_AGE) ||
01485 (!HasLink(joiningVertex, justAddedVertex)))
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) {
01500 continue;
01501 }
01502
01503 unsigned long linkStateCost = networkVertex->GetDistance();
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) {
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);
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);
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()) {
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
01763
01764
01765
01766 entry->SetCost(distance);
01767 entry->ClearNextHops();
01768 entry->SetLinkStateOrigin(routerVertex);
01769 }
01770 if (distance == entryCost) {
01771
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);
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
01785
01786
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);
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
01996
01997
01998
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
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
02142
02143
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
02152 if ((routingEntry->GetPathType() == OSPF::RoutingTableEntry::InterArea) &&
02153 (routingEntry->GetCost() >= currentCost))
02154 {
02155 sameOrWorseCost.push_back(routingEntry);
02156 }
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)) {
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))) {
02234 bool foundIntraAreaRoute = false;
02235
02236
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
02259 for (j = 0; j < routeCount; j++) {
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 {
02274
02275
02276
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
02295
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 {
02308 equalEntry = checkedEntry;
02309 }
02310 }
02311
02312 unsigned long nextHopCount = borderRouterEntry->GetNextHopCount();
02313
02314 if (equalEntry != NULL) {
02315
02316
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)) {
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++) {
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++) {
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 {
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 }
