What is routing?• forwarding – moving packetsbetween ports- Look up destination address inforwarding table- Find out-port or hout-port, MACaddri pair• Routing is process of populat-ing forwarding table- Routers exchange messages aboutnets they can reach- Goal: Find optimal route for ev-ery destination- . . . or maybe good route, or justany route (depending on scale)Routing algorithm properties• Static vs. dynamic- Static: routes change slowly over time- Dynamic: automatically adjust to quickly changingnetwork conditions• Global vs. decentralized- Global: All routers have complete topology- Decentralized: Only know neighbors & what they tell you• Intra-domain vs. Inter-domain routing- Intra-: All routers under same administrative control- Intra-: Scale to ∼100 networks (e.g., campus like Stanford)- Inter-: Decentralized, scale to InternetOptimality43621911DAFEBC• View network as a graph• Assign cost to each edge- Can be based on latency, b/w, utilization, queue length, . . .• Problem: Find lowest cost path between two nodes- Must be computed in distributed wayDistance Vector• Local routing algorithm• Each node maintains a set of triples- (Destination, Cost, NextHop)• Exchange updates w. directly connected neighbors- periodically (on the order of several seconds to minutes)- whenever table changes (called triggered update)• Each update is a list of pairs:- (Destination, Cost)• Update local table if receive a “better” route- smaller cost- from newly connected/available neighbor• Refresh existing routes; delete if they time outDV ExampleDGAFEBC• B’s routing table:Destination Cost NextHopA 1 AC1 CD 2 CE 2 AF 2 AG 3 AAdapting to failuresDGAFEBC- F detects that link to G has failed- F sets distance to G to infinity and sends update to A- A sets distance to G to infinity since it uses F to reach G- A receives periodic update from C with 2-hop path to G- A sets distance to G to 3 and sends update to F- F decides it can reach G in 4 hops via ADanger: LoopsDGAFEBC- link from A to E fails- A advertises distance of infinity to E- B and C advertise a distance of 2 to E- B decides it can reach E in 3 hops; advertises this to A- A decides it can reach E in 4 hops; advertises this to C- C decides that it can reach E in 5 hops. . .How to avoid loops• Consider small value (e.g., 16) to be infinity- Will quickly decite node is unavailable• Split horizon- When sending updates to node A, don’t includedestinations you route to through A• Split horizon with poison reverse- When sending updates to node A, explictly include veryhigh cost (“poison”) for destinations you route to through A• Note: Latter two only help between two nodes- Can still get loop with three nodes involved- Might need to delay advertising routes after changes, butwill affect convergence timeLink State• Strategy- Send to all nodes (not just neighbors)- Send only information about directly connected links (notentire routing table)• Link State Packet (LSP)- ID of the node that created the LSP- Cost of link to each directly connected neighbor- Sequence number (SEQNO)- Time-to-live (TTL) for this packetReliable flooding• Store most recent LSP from each node• Forward LSP to all nodes but one that sent it• Generate new LSP periodically- Increment SEQNO• Start SEQNO at 0 when reboot- If you hear your own packet w. SEQNO= n, set your nextSEQNO to n + 1• Decrement TTL of each stored LSP- discard when TTL= 0Calculating best path• Dijkstra’s shortest path algorithm• Let:- N denote set of nodes in the graph- l(i, j ) denotes non-negative cost (weight) for edge (i, j )- s denotes yourself (node computing paths)• Initialize variables- M ← {s} (set of nodes “incorporated” so far)- Cn← l(s, n) (cost of the path from s to n)- Rn← ⊥ (next hop on path to n)Dijkstra’s algorithm• While N 6= M- Let w ∈ (N − M ) be node with lowest Cw- M ← M ∪ {w}- Foreach n ∈ (N − M ), if Cw+ l(w , n) < Cnthen Cn← Cw+ l(w , n), Rn← w• Example: D (D, 0, ⊥)(C , 2, C )(B, 5, C )(A, 10, C )DABC5321110Distance Vector vs. Link State• # of messages- DV: convergence time varies, but Ω(d) where d is # ofneighbors of node- LS: O(n · d) for n nodes in system• Computation- DV: Could count all the way to ∞ if loop- LS: O(n2)• Robustness – what happens with malfunctioningrouter?- DV: Node can advertise incorrect path cost- DV: Costs used by others, errors propagate through net- LS: Node can advertise incorrect link costMetrics• Original ARPANET metric- measures number of packets enqueued on each link- took neither latency nor bandwidth into consideration• New ARPANET metric- stamp each incoming packet with its arrival time (AT)- record departure time (DT)- when link-level ACK arrives, computeDelay = (DT − AT ) + Transmit + Latency- if timeout, reset DT to departure time for retransmission- link cost = average delay over some time period• Fine Tuning- compressed dynamic range- replaced Delay with link utilization• Today: policy often trumps performance [more later]Intradomain routing protocols• RIP (routing information protocol)- Fairly simple implementation of DV• OSPF (open shortest path first)- LS-based protocol- Adds notion of areas for scalability- Area 0 is “backbone” area (includes all boundary routers)- Traffic between two areas must always go through area 0- Only need to know how to route exactly within area- Else, just route to appropriate area- (Virtual links can allow distant routers to be in area 0)OSPF areasScaling issues• Every router must be able to forward based on anydestination IP address- Given address, it needs to know ”next hop” (table)- Na¨ıve: Have an entry for each address- There would be 108entries!• Solution: Entry covers range of addresses- Can’t do this if addresses are assigned randomly! (e.g.,Ethernet addresses)- This is why address aggregation is important- Addresses allocation should be based on network structure• What is structure of the Internet?The Internet, 1990NSFNET backboneStanfordBARRNETregionalBerkeleyPARCNCARUAUNMWestnetregionalUNLKUISUMidNetregional…• Hierarchical structure w. single backboneAddress allocation, 1990Network number Host numberClass B addressSubnet mask (255.255.255.0)Subnetted address111111111111111111111111 00000000Network number Host IDSubnet ID• Hierarchical IP addresses- Class A (8-bit prefix), B (16-bit), C (24-bit)• Subnetting adds another level within
View Full Document