CS 536 ParkImplementationMajor Internet routing protocols:• RIP (v1 and v2): intra-domain, Bellman-Ford→ also called “distance vector”→ metric: hop count→ UDP→ nearest neighbor advertisement→ popular in small intra-domain networks• OSPF (v1 and v2): intra-domain, Dijkstra→ also called “link state”→ metric: average delay→ directly over IP: protocol number 89→ broadcasting via flooding→ popular in larger intra-domain networksCS 536 Park• IS-IS: intra-domain, Dijkstra→ “link state”→ directly over link layer (e.g., Ethernet)→ more recently: also available over IP→ flooding→ popular in larger intra-domain networks• Source routing: packet specifies path→ implemented in various link layer protocols→ ATM call set-up: circuit-switching→ IPv4/v6: option field→ mostly disabled→ large ISPs: sometimes used internally for diagnosisCS 536 ParkBGP (Border Gateway Protocol):• Inter-domain routing→ border routers vs. backbone routersPeeringBorder RoutersAutonomous System BAutonomous System A−→ “peering” between two AS’s−→ includes customer-provider relationship−→ exchanges: peering between multiple AS’sCS 536 Park• CIDR addressing→ i.e., a.b.c.d/x→ Purdue: 128.10.0.0/16, 128.210.0.0/16, 204.52.32.0/20→ check at www.iana.org (e.g., ARIN for US)• Route table look-up: maximum prefix matching→ e.g., entries: 128.10.0.0/16 and 128.10.27.0/24→ destination address 128.10.27.20 matches 128.10.27.0/24best• Metric: policy→ e.g., shortest-path, trust, pricing→ meaning of “shortest”: delay, router hop, AS hop→ route amplification: shortest AS path 6= shortestrouter path→ mechanism: path vector routing→ BPG update messageCS 536 ParkBGP route update:−→ BGP update message propagationBGP update message:ASNAk→···→ASNA2→ ASNA1; a.b.c.d/xMeaning: ASN A1(with CIDR address a.b.c.d/x) can bereached through indicated path−→ “path vector”−→ called AS-PATHSome AS numbers:• Purdue: 17• BBN: 1• UUNET: 701• Level3: 3356• Abilene (aka “Internet2”): 11537CS 536 ParkPurdue’s backbone network (Fall 2004): ITaPCS 536 ParkLevel3 backbone network: www.level3.com−→ 10 Gbps backbone (same as Purdue)−→ part of backbone: OC-48 (2.488 Gbps)CS 536 ParkAbilene/Internet2 backbone: www.internet2.eduCS 536 ParkPolicy:• if multiple AS-PATHs to target AS are known, chooseone based on policy→ e.g., shortest AS path length, cheapest, least wor-risome• advertise to neighbors target AS’s reachability→ also subject to policy→ no obligation to advertise→ specifics depend on bilateral contract (SLA)SLA (service level agreement):−→ bandwidth (e.g., 1 Gbps, OC-3, DS3−→ delay (e.g., avrg. 25ms US), loss (e.g., 0.05%)−→ pricing (e.g., 1 Mbps: below $100)−→ availability (e.g., 99.999%)−→ etc.CS 536 ParkEx.:AS AAS HAS FAS GAS EAS DAS CAS BStubProviderA; a.b.c.d/xAS HAS AF −> C −> B −> A; a.b.c.d/xB −> A; a.b.c.d/xB −> A; a.b.c.d/xD −> B −> A; a.b.c.d/xG −> D −> B −> A; a.b.c.d/xC −> B −> A; a.b.c.d/xAS FAS CAS BAS DAS GAS EPurdue: ASN 17; 128.10.0.0/16CS 536 ParkBGP-update procedure:Upon receiving BGP update message from neighbor totarget AS A1. Store AS-PATH reachability info for target A→ AdjIn table (one per neighbor)2. Determine if new path to A should be adopted→ policy→ path should be unique→ BPG table (locRIB) & IP routing table update→ inter-domain: IP table update from BGP3. Determine who to advertise reachability for target A→ selective advertisementNote: if shortest-path then same as Dijkstra in-reverseCS 536 ParkBGP-withdrawal:1. Use BGP keep-alive message to sense neighbor→ timeout2. If keep-alive does not arrive within timeout, assumenode is down3. Send BGP withdraw message for neighbor who is deemeddown if no alternative path exists; else send BGP up-date message→ may trigger further updatesOther BGP features:• BGP runs over TCP→ port number 179→ i.e., “application layer” protocol• BPG-4 (1995); secure BGP→ S-BGP: not implemented yet (“BBN vs. Cisco”)CS 536 ParkPerformanceRoute update frequency:−→ routing table stability vs. responsiveness−→ rule: not too frequently−→ 30 seconds−→ stability wins−→ hard lesson learned from the past (sub-second)−→ legacy: TTLOther factors for route instability:−→ selfishness (e.g., fluttering)−→ BGP’s vector path routing: inherently unstable−→ more common: slow convergence−→ target of denial-of-service (DoS) attackCS 536 ParkRoute amplification:−→ shortest AS path 6= shortest router path−→ e.g., may be several router hops longer−→ AS graph vs. router graph−→ inter- vs. intra-domain routing: separate subsystems−→ policy: company in DenmarkRoute asymmetry:−→ routes are not symmetric−→ estimate: > 50%−→ mainly artifact of inter-domain policy routing−→ various performance implications−→ source tracebackCS 536 ParkBlack holes:−→ persistent unreachable destination prefixes−→ BGP routing problems−→ further aggrevated by DNS−→ purely application layer: end system problemCS 536 ParkTopology:−→ who is connected to whom−→ Internet AS graph (segment of Jan. 2002)CS 536 ParkContrast with random graph: same number of nodes andedges−→ random graph: choose each link with prob. p−→ independently: prob. of k neighbors is pkCS 536 ParkPhenomenon:−→ Pr{u has k neighbors}∝k−α(2 <α<3)−→ called power-law graphIn contrast to random graph:−→ Pr{u has k neighbors}∝pk−→ probability is exponentially small in k−→ UUNET (AS 701) has > 2500 neighbors!−→ > 12500 domains in 2002−→ probabilistically UUNET should not exist−→ so things are not randomWhat’s going on ...−→ connection to airlines?CS 536 ParkEx.: Delta Airlines route map−→ by design: hub and backbone architecture−→ mixture of centralized/decentralized design−→ small system: centralized is good−→ large system: decentralization necessaryCS 536 ParkSmall system with centralized design:−→ star topology−→ e.g., Southwest Airlines−→ essentially two conjoined star topologies−→ a matter of load balancing−→ backbone topology: trivialCS 536 ParkSimple backbone topologies comprised of stars:tree (hierarchy) of starsrandom/planar backbone of starsring of starsmesh of stars−→ different star sizes: Pr{deg(u)=k}∝k−α−→ cliques: peering at