DOC PREVIEW
Stanford CS 144 - What is routing

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Stanford CS 144 - What is routing

Documents in this Course
IP Review

IP Review

22 pages

Load more
Download What is routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view What is routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view What is routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?