1Network Layer IEECS 122: Lecture 11Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeleyFebruary 21, 2006EECS122 Lecture 11 (AKP)2What is the network layer? So far we have been treating the network “as a cloud” that “routes packets”applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicallogical end-end transport2February 21, 2006EECS122 Lecture 11 (AKP)3What is the network layer? So far we have been treating the network “as a cloud” that “routes packets” The Network Layer1. Chops transport layer messages into IP packets2. Delivers them to the correct destination(s)3. Reconstitutes packets into transport layer messagesapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalFebruary 21, 2006EECS122 Lecture 11 (AKP)4Network layer Network layer protocols must run in every host, router In the internet, they all understand IP Routers do not examine the transport layer headers of the packets they forward But routers must establish routes, and so have to run their own applications e.g. OSPF, BGP etc.networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical3February 21, 2006EECS122 Lecture 11 (AKP)5Network Layer Functions Control Functions: Ensure that routers are configured to deliver packets correctly to the destination Path Selection (called routing in the book) Connection Setup: required in virtual circuit routing. Data Functions: Ensure that arriving packets are forwarded correctly within a router with minimum delay ForwardingFebruary 21, 2006EECS122 Lecture 11 (AKP)6Interplay between path selection and forwarding1230111value in arrivingpacket’s headerpath sel. algorithmlocal forwarding tableheader value output link01000101011110013221path selection algorithms runas application protocolsforwarding is a function mostly Implemented hardwareRouting = Fwding + Path Selection4February 21, 2006EECS122 Lecture 11 (AKP)7Network Level Connections Important function in some network architectures: ATM, frame relay, X.25 Before data packets flow, two hosts and intervening routers establish virtual connection Routers get involved Network and transport layer cnctn service: Network: between two hosts Transport: between two processes Note that connection setup is a control function but it is real-time. This makes it difficult to implement in the network layerFebruary 21, 2006EECS122 Lecture 11 (AKP)8Outline of next few lectures1. Path Selection: Next two lectures2. Forwarding: One lecture3. Network Connection Setup (QoS): Two lectures5February 21, 2006EECS122 Lecture 11 (AKP)9A Graph Model6785431212101311 Nodes are Routers/Hosts Edges are links Edge (2,6) is the edgefrom node 2 to node 6February 21, 2006EECS122 Lecture 11 (AKP)10Walks6785431212101311A Walk from 1 to 11Cycle 4-8-7-5-46February 21, 2006EECS122 Lecture 11 (AKP)11Paths6785431212101311Routes are PathsA Path is a Walkwith no cyclesThere are 24 paths from1 to 11February 21, 2006EECS122 Lecture 11 (AKP)12Routes678543121210131112232128111512212122722Routes are PathsA Path is a Walkwith no cyclesThere are 24 paths from1 to 11Edges have weights: c(i,j)Note: It is possible for edge(i,j) to have a different weightthan edge (j,i).7February 21, 2006EECS122 Lecture 11 (AKP)13Routing678543121210131112232128111512212122722Routes are PathsA Path is a Walkwith no cyclesThere are 24 paths from1 to 11Edges have weightsSelect the shortest path routeMany ways to do this: Path Selection AlgorithmsFebruary 21, 2006EECS122 Lecture 11 (AKP)14Routing Algorithm classificationGlobal or decentralized information?Global: all routers have complete topology, link cost info “link state” algorithms E.g. OSPFDecentralized: router knows physically-connected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors “distance vector” algorithms E.g. RIPStatic or dynamic?Static: routes change slowly over timeDynamic: routes change more quickly periodic update in response to link cost changes8February 21, 2006EECS122 Lecture 11 (AKP)15The internet has many Administrative Domains6785431212101311February 21, 2006EECS122 Lecture 11 (AKP)16The internet has many Administrative DomainsABC31212101311678549February 21, 2006EECS122 Lecture 11 (AKP)17Border Routers643213ABC2436137851121011OSPFRIPIGRPBGPFebruary 21, 2006EECS122 Lecture 11 (AKP)18Hierarchical RoutingABC6785431212101311643213B243613OSPFRIPIGRPBGPInterDomainInterDomainIntraDomainIntraDomainIntraDomain10February 21, 2006EECS122 Lecture 11 (AKP)19Link State Protocols1. Every node learns the topology of the network Flooding of Link State Packets (LSP)2. An efficient shortest path algorithm computes routes to every other node3. Node updates Forwarding TableFebruary 21, 2006EECS122 Lecture 11 (AKP)20Flooding678543121210131111February 21, 2006EECS122 Lecture 11 (AKP)21Flooding6785431212101311February 21, 2006EECS122 Lecture 11 (AKP)22Flooding678543121210131112February 21, 2006EECS122 Lecture 11 (AKP)23Flooding6785431212101311February 21, 2006EECS122 Lecture 11 (AKP)24Flooding is trickier than it looks… Suppose node i is to flood a list of neighbors. Rule at each of the nodes: upon receiving the packet send to all neighbors except the one you got the packet from… FAILS if there are cycles in the graph Don’t send the same packet out twice… But what if link states change? Use sequence numbers… Better but not perfect13February 21, 2006EECS122 Lecture 11 (AKP)25Some Issues What happens if sequence numbers wrap? Hardware errors could cause arbitrary behavior What happens when a partitioned network is reconstituted? What about security? Etc., etc. Many lines of codeFebruary 21, 2006EECS122 Lecture 11 (AKP)26Learning the topology Every router sends Link State Packets (LSPs) to all of its neighbors LSPs arrive and wait in buffers to be “accepted”
View Full Document
Unlocking...