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