Network Layer I EECS 122 Lecture 11 Department of Electrical Engineering and Computer Sciences University of California Berkeley What is the network layer application transport network data link physical network data link physical gi lo network data link physical l ca So far we have been treating the network as a cloud that routes packets d en den network data link physical t or sp an tr network data link physical network data link physical application transport network data link physical February 21 2006 EECS122 Lecture 11 AKP 2 1 What is the network layer 1 2 3 So far we have been treating the network as a cloud that routes packets The Network Layer Chops transport layer messages into IP packets Delivers them to the correct destination s Reconstitutes packets into transport layer messages February 21 2006 application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical 3 EECS122 Lecture 11 AKP Network layer Network layer protocols must run in every host router application transport network data link physical network data link physical In the internet they all understand IP network data link physical 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 February 21 2006 network data link physical EECS122 Lecture 11 AKP network data link physical network data link physical network data link physical network data link physical network data link physical application transport network data link physical 4 2 Network 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 Forwarding February 21 2006 5 EECS122 Lecture 11 AKP Interplay between path selection and forwarding path sel algorithm path selection algorithms run as application protocols local forwarding table header value output link 0100 0101 0111 1001 forwarding is a function mostly Implemented hardware 3 2 2 1 Routing Fwding Path Selection value in arriving packet s header 0111 1 3 2 February 21 2006 EECS122 Lecture 11 AKP 6 3 Network Level Connections Important function in some network architectures Before data packets flow two hosts and intervening routers establish virtual connection Routers get involved Network and transport layer cnctn service ATM frame relay X 25 Network between two hosts Transport between two processes Note that connection setup is a control function but it is realtime This makes it difficult to implement in the network layer February 21 2006 EECS122 Lecture 11 AKP 7 Outline of next few lectures 1 2 3 Path Selection Next two lectures Forwarding One lecture Network Connection Setup QoS Two lectures February 21 2006 EECS122 Lecture 11 AKP 8 4 A Graph Model Nodes are Routers Hosts Edges are links Edge 2 6 is the edge from node 2 to node 6 5 7 4 8 6 11 2 10 3 1 13 February 21 2006 12 9 EECS122 Lecture 11 AKP Walks A Walk from 1 to 11 5 7 Cycle 4 8 7 5 4 4 8 6 11 2 1 February 21 2006 10 3 13 EECS122 Lecture 11 AKP 12 10 5 Paths A Path is a Walk with no cycles Routes are Paths 5 7 4 There are 24 paths from 1 to 11 8 6 11 2 10 3 1 13 February 21 2006 12 11 EECS122 Lecture 11 AKP Routes A Path is a Walk with no cycles Routes are Paths 2 8 5 4 There are 24 paths from 1 to 11 1 7 2 8 Edges have weights c i j Note It is possible for edge i j to have a different weight than edge j i 2 12 6 15 2 3 2 2 2 3 1 13 12 February 21 2006 12 7 11 1 11 10 2 12 2 EECS122 Lecture 11 AKP 12 6 Routing A Path is a Walk with no cycles Routes are Paths 2 8 5 4 There are 24 paths from 1 to 11 1 7 2 8 Edges have weights 2 12 6 15 2 3 2 2 2 3 1 13 12 Select the shortest path route Many ways to do this Path Selection Algorithms February 21 2006 12 7 11 1 11 10 2 12 2 EECS122 Lecture 11 AKP 13 Routing Algorithm classification Global or decentralized information Static or dynamic Global all routers have complete topology link cost info link state algorithms E g OSPF Decentralized router knows physicallyconnected neighbors link costs to neighbors iterative process of computation exchange of info with neighbors distance vector algorithms Static routes change slowly over time Dynamic routes change more quickly periodic update in response to link cost changes E g RIP February 21 2006 EECS122 Lecture 11 AKP 14 7 The internet has many Administrative Domains 5 7 4 8 6 11 2 10 3 1 13 February 21 2006 12 15 EECS122 Lecture 11 AKP The internet has many Administrative Domains B 5 7 4 8 6 11 2 10 3 1 13 C A February 21 2006 12 EECS122 Lecture 11 AKP 16 8 Border Routers B 5 44 7 RIP 8 66 11 22 10 OSPF BGP 33 1 13 13 12 C IGRP A February 21 2006 17 EECS122 Lecture 11 AKP Hierarchical Routing 44 B 66 B BGP 5 2 2 4 InterDomain InterDomain 33 7 IntraDomain 8 6 RIP 13 13 11 2 10 OSPF IntraDomain 3 1 IntraDomain 13 IGRP A February 21 2006 12 C EECS122 Lecture 11 AKP 18 9 Link State Protocols Every node learns the topology of the network 1 Flooding of Link State Packets LSP An efficient shortest path algorithm computes routes to every other node Node updates Forwarding Table 2 3 February 21 2006 19 EECS122 Lecture 11 AKP Flooding 5 7 4 8 6 11 2 1 February 21 2006 10 3 13 EECS122 Lecture 11 AKP 12 20 10 Flooding 5 7 4 8 6 11 2 10 3 1 13 February 21 2006 12 21 EECS122 Lecture 11 AKP Flooding 5 7 4 8 6 11 2 1 February 21 2006 10 3 13 EECS122 Lecture 11 AKP 12 22 11 Flooding 5 7 4 8 6 11 2 10 3 1 February 21 2006 13 12 EECS122 Lecture 11 AKP 23 Flooding 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 perfect February 21 2006 EECS122 Lecture 11 AKP 24 12 Some Issues What happens if sequence numbers wrap Hardware errors could cause arbitrary behavior What happens when a partitioned network …
View Full Document
Unlocking...