【正文】 et 91 Jim Binkley LSA header details ? key for LSA is (type, LS ID, advert router) ? types are 15 for basic LSAS (router/work, area summary, etc) – 5 for extended LSAs ? advert router, who originated LSA, note may or may not be same as Link State ID ? sequence number inc if LSA fresh ? LSA csum, fletcher (ISO), not IP ? length, includes LSA hdr, must fit in IP pkt ? age, 0 when 1st sent 92 Jim Binkley LSA link state ID ?associated with type ?type 1, originating router ID ?type 2, IP of i/f of work DR ?type 3, destination IP addr ?type 4, router ID of ASBR ?type 5, destination IP address 93 Jim Binkley routerLSA summary info ?router X – has separate links for interfaces – ., 3 links – each of which mentions a work – and metric on that work – all router interfaces must be mentioned 94 Jim Binkley ty。we do need equal cost multi path – a rooted tree of best paths from you to everybody else 187。these events can drive LSA generation ?note that interfaces have a state machine associated with them – plicated by DR election, adjacencies, hw knowledge events (link is down) 32 Jim Binkley flooding algorithm basics ? flooding is reliable per link ? if A/C fails, A will notify other two links ?B ., will tell D but will NOT tell A (don’t send it back thru input i/f) ? B will add message to its DB and repute routing table iff ? LSA is more recent, not corrupt, known type ? updates would cross from B to/from D, but D would not in turn then forward the pkt to A 33 Jim Binkley flooding mechanics ?protocol includes per link ACK – resend until ACK heard therefore reliable – ACK is optimized in several ways and ., not sent when updates cross – recv may delay in hopes that ACK (may be unicast or multicast) may include multiple ACKs ?we need checksum/sequence pair as well – sequence number must have “overflow” technique 34 Jim Binkley checksum/sequence ? all OSPF packets include checksum and other robustness features in face of errors, hdr has IP csum, LSA has csum too ? OSPF does not use spanning tree, but floods which is inherently redundant ? router might accidentally delete LSA, therefore originator must refresh LSA on 30 minute basis ? pkt discarded if csum fails, checksum not altered by others, (LSA csum excludes age field) ? 3 tuple for freshness (csum, sequence number, age ) ? every router increments age, hence like IP TTL – discard at MaxAge 35 Jim Binkley freshness, robustness, etc. ? rate limit LSA origination, at most 1 per 5 secs ? router periodically verifies LSA csums in DB. guards against internal memory failures ? originator sends (checksum, seq+1, age=0) ? if stored in other R db, age is incremented as it passes through, and over time by timeout function ? if 1 hour passes, and no resend, then LSA is tossed (why wait 30 minutes?) ? sequence space WRAP is velly tricky ... 36 Jim Binkley sequence space wrap ?in ARPANET, LS protocol had famous sequence failure – in theory Sn+1 Sn, but unfortunately S1 S2 S3 S1 happened – entire work had to be powercycled ?v1 had lollipop algorithm – calculation still felt to be problematic ?therefore v2 does not wrap ... 37 Jim Binkley v2 sequence idea ?we have reliable flooding, therefore originator reliably REMOVES LSA from domain, and regenerates it at wrap time ?S0 is InitialSequenceNumber, max negative, in hex 0x800000001, ?increment by one until 0x7fffffff, but 1st ?flood deletion with S(max), then send S0 ?in theory, 600 years of time ... but errors could occur 38 Jim Binkley hello/bringing up adjacencies ? hello is neighbor discovery packet ? therefore has these functions – link operational (peers exist) – elect Designated R and BDR on broadcast links ? hello sent at default 10 seconds ? on write sent to (allSPFrouters) ? list of neighbors are included (i can hear you) – basically this is an ACK, link must be bidirectional ? routerDeadInterval, 40 seconds must hear from neighbor within this time, else route around 39 Jim Binkley hello, cont. ? decide link is operational iff – other guy has you in its hello – if pt/pt, that is enough – if broadcast, must wait for DR election ? election algorithm ideas: – priority field and IP address used as discriminators – highest priority wins, if 1 with same priority, highest IP wins – always keep DR and BDR, if DR fails, BDR is DR 40 Jim Binkley election algorithm roughly ?if more than one BDR, choose based on 1. priority/2. high IP address is tiebreaker ?if no backup, choose based on priority/IP ?if 1 DR, choose based on priority/IP ?if no DRs, and BDR, promote BDR ?key idea: DRs and BDRs must do database exchange with all other routers on sub – non DR is adjacent to DR 41 Jim Binkley how many relationships on this bcast ? 6 routers, N * (N1) / 2 N = 6 42 Jim Binkley DR points/are these ?non DR routers keep LSA databases in sync with DR using – database exchange (I booted, give me all you got) – reliable flooding – single point of failure, therefore BDR is hot standby – routers must sync with BDR too – this makes plexity linear 43 Jim Binkley flooding with DRs then DR BDR R 1. flooded LSA 2. R floods to , all DRs 3. DR floods to , all OSPFs 44 Jim Binkley database sync ?could e from LSA flooding alone ?we MUST keep routers in sync with LSA maps ?else we risk routing loops, black holes ?optimization: at boot, exchange map with adjacent router, or do this at partition fixup ?call this database exchange 45 Jim Binkley aka ?bringing up adjacencies ... ?one of 3 subprotocols in OSPF ?1. hello ?2. bringing up adjacencies (db exchange) ?3. reliable flooding (fun with LSAs) 46 Jim Binkley database exchange ?basica