Unformatted text preview:

CS419: Computer NetworksLecture 4, Feb 14, 2004IP Forwarding TableCS419Routing and Forwarding Revisited| We separate notion of “routing” and “forwarding”| Routing algorithm is what a router does in the “background” to figure out where each prefix should be forwardedz Address prefixes, next hops, link costs, distances, etc.| Forwarding is what a router does when a packet arrivesz Address prefixes, next hops, interface, subnet addressCS419Routing and Forwarding RevisitedCS419A simple example(FIB)CS419Simple (naïve) forwarding rule| Step through table from top to bottom| At each step, apply mask to FIB address and packet address. If results match, then use FIB entry to forward packetz If (FIB-addr && FIB-mask) == z (PK-addr && FIB-mask) z then use entry| FIB = Forwarding Information Basez i.e. Forwarding Tablez Routing Table also called RIBCS419CS419Simple example with defaultCS419But default entry must be last!CS419A more complex example (a site with 500 hosts)| How do we assign prefixes (addr and mask) in this case???CS419One way to assign prefixes…20.1.1.0/2720.1.1.32/2720.1.1.0/2720.1.1.64/2720.1.1.96/2720.1.1.128/2720.1.1.128/27CS419My mistake last year…..CS419The view from the global Internet: 6 FIB entries!20.1.1.0/2720.1.1.32/2720.1.1.64/2720.1.1.96/2720.1.1.128/2720.1.1.128/27CS419We can shrink that to one FIB entry!20.1.1.0/2720.1.1.128/27CS4191024 addresses to address 500 hosts! What a waste…20.1.1.0/2720.1.1.128/27CS419What about this prefix assignment approach instead?20.1.1.0/2720.1.1.32/2720.1.1.64/2720.1.1.96/2720.1.1.128/2720.1.0.0/2720.1.0.32/2720.1.0.64/2720.1.0.96/2720.1.0.128/27CS419Now 500 addresses fit into a 512 address block!20.1.1.0/2720.1.1.128/27 20.1.0.0/2720.1.0.128/27CS419But now our forwarding rules fail (like with the default)20.1.0.0/2720.1.0.128/27CS419Longest-prefix match| Since multiple entries may match, we prefer the entry with the longest mask (prefix)| Two ways:1. Go through the whole FIB, remembering the matching entrieywith the longest prefix2. Sort FIB in order of longest prefix first, and select first matchCS419First-match Longest-prefix20.1.0.0/2720.1.0.128/2720.1.0.0/2720.1.0.128/27CS419Best-match rules revisited| Select matching FIB entry with longest prefix| If multiple matching FIB entries have the same prefix size, then any may be usedz Even simultaneously---path splitting for load balancingz But try to maintain source affinity (i.e. send different flows along different paths, but don’t split a given flow)CS419Paths to multi-homed site XISP AInternet (other ISPs)ISP BX20.1.2/2420.1/1620.2/1620.1.2/2420.1.1/2420.1.2/2420.1.1/24Y20.1/1620.1.1/24CS419Paths to Site X after X-B link failureISP AInternet (other ISPs)ISP BX20.1.2/2420.1/1620.2/1620.1.2/2420.1.1/2420.1.2/2420.1.1/24X20.1/1620.1.1/24YCS419Better load balance (without increasing FIB size)ISP AInternet (other ISPs)ISP BX20.1.2/2420.1/1620.1.2/2420.2/1620.1.2/2420.1.1/2420.1.2/2420.1.1/2420.1/1620.1.1/24YCS419Paths to Site YISP AInternet (other ISPs)ISP BX20.1.2/2420.1/1620.2/1620.1.2/2420.1.1/2420.1.2/2420.1.1/2420.1.1/2420.1/16YCS419Paths “to” Site Y after Y-B link failureISP AInternet (other ISPs)ISP BX20.1.2/2420.1/1620.2/1620.1.2/2420.1.1/2420.1.2/2420.1.1/24X20.1/1620.1.1/24YXCS419Implementing the forwarding table| First-match style ok for small forwarding tablesz Scales poorly with the number of entries| Hash structures work for flat addresses, but not hierarchical (masked) addressesz “Bridged Ethernets”| High-end routers implement forwarding table in hardwarez Combination of a fancy tree structure and CAMs(Content Addressable Memory)| Otherwise, some kind of tree-like data structure is typically usedz We’ll look at this later in the courseCS419Other types of forwarding| What we looked at so far is hop-by-hop forwarding with hierarchical addresses| Hop-by-hop means that every switch in the path makes an “independent” forwarding decision| But we can also have source routingz The entire path is listed in the packetz IP has a (never used) option for thisCS419Hop-by-hop versus source routing| Source routing is (kindof) what you do when you print out directions from mapquestz I.e., you carry you path with you| Hop-by-hop routing is often (kindof) how you find your way around Wal-Martz “where is kids clothing?”, “where are socks?”CS419Hop-by-hop versus source routing| Hop-by-hop is what is used in the Internetz Though many people have proposed source routing| With the exception of routing through a switch fabric within a routerz But we’ll look at router/switch architecture


View Full Document

CORNELL CS 419 - Computer Networks

Download Computer Networks
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 Computer Networks 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 Computer Networks 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?