CMPE 150 Winter 2009 Lecture 10 February 10 2009 P E Mantey CMPE 150 Introduction to Computer Networks Instructor Patrick Mantey mantey soe ucsc edu http www soe ucsc edu mantey Office Engr 2 Room 595J Office hours Tues 3 5 PM Mon 5 6 PM TA Anselm Kia akia soe ucsc edu Web site http www soe ucsc edu classes cmpe150 Winter09 Text Tannenbaum Computer Networks 4th edition available in bookstore etc Syllabus Reading Assignment Thursday February 12 Chapter 5 sections 5 3 5 4 1 5 4 3 5 5 Today s Agenda Link Layer Bridge Routing Network Layer Functions IP Routing Text Chapter 5 sections 5 1 5 2 15 2 8 pp 343 370 Internet Layering Level 5 Application Layer rlogin ftp SMTP POP3 IMAP HTTP Level 4 Transport Layer a k a Host to Host TCP UDP ARP ICMP etc Level 3 Network Layer a k a Internet IP Level 2 Data Link Layer MAC sub layer a k a Network Interface or Network Access Layer Level 1 Physical Layer Bridging 802 x Fixed Route Bridging Source Route Bridging Transparent Bridging Plug n Play Flooding algorithm Backward Learning Spanning Tree avoids loops Ref http en wikipedia org wiki Bridging 28networking 29 Spanning Tree ApproachUses IEEE 802 1 Frame Forwarding Each bridge maintains Forwarding Table List of stations on the side of each port Forwards to port and on to LAN corresponding to Table Unless blocked Floods those whose MAC address not in Table Address Learning Spanning Tree Algorithm Address Learning When frame arrives on a port table records source address as being on that port Backward learning Timer set for each entry Timer expires entry is deleted Timer reset if new frame gives same info Spanning Tree Algorithm Algorithm to avoid Loops not needed if topology is a tree Root of tree is lowest serial number all bridges broadcast their serial number Tree constructed from root to every bridge with shortest path Algorithm runs continually to detect topology changes 801 1D http www cisco com warp public 473 lan switch transparent swf Network Layer Topics Network Layer Layer 3 Services for the Transport Layer Uses the Link Layer Datagrams Packets Internet Protocol IP Addressing IP Address Communication challenges Information Audio Video Text Data Images Signals Channels Networks Analog Digital Analog Digital Circuit Datagram Analog continuously varying value Digital sequence of symbols from a finite set Network challenge transmission of information across interconnected channels Circuit think telephone call Datagram think telegram First networks Which came first analog or digital Digital Signal fires 1200 BC Optical telegraph 1791 Electronic telegraph 1836 First analog telecommunication was telephone 1875 Telephone network Originally all analog Internal links replaced with digital in 1962 Internal links shared with FDM Allowed sharing with more efficient TDM Circuit switched Simple hierarchical static topology and routing First done by human operators then automatic relays Provide guaranteed Quality of Service QoS Dedicate resources to each connection Packet switched networks Defining characteristics Virtual circuit Data and addressing in packets Statistical multiplexing Dynamic topology and routing X 25 1974 Frame Relay 1984 ATM 1988 Datagram ARPAnet 1966 Internet 1977 Virtual circuit networks Generalization of telephone model Smart net architecture Compute route on demand at flow setup Per flow state in routers Assumes need of resource reservation for some flows Datagram networks Three inventors Defining characteristics Kleinrock 1961 efficiency Baran 1962 survivability Davies 1964 commercial service Controversy over who invented Pre compute routes to all destinations No per flow state Assumes best effort will be good enough ARPAnet First datagram network Modified smart net architecture 1966 project proposed September 1969 first IMP installed Built on reliable link technology Hop by hop reliability congestion and flow control Some end to end flow control RFNM Much redundant functionality E g reliability and flow control Led to the end to end argument End to end argument If a function can completely and correctly be implemented only with the knowledge and help of the application end points of a communication system then the function should not be implemented in the communication system itself although sometimes it may be useful to implement an incomplete version of the function in the communication system as a performance enhancement J Saltzer D Reed and D Clark End toend arguments in system design ACM Trans Comp Sys 2 4 277 88 Nov 1984 The Internet Goal encourage development of new network technologies Make minimal assumptions about links Attach many computers Transport datagrams Quickly send datagrams to different destinations Best effort delivery drop or out of order Smart host architecture End to end argument Network layer summary Communication across interconnected channels Two styles circuit vs packet switched Packet switching characteristics Data and addressing in packets Statistical multiplexing Dynamic topology and routing Datagram pre compute routes no flow state VC on demand routing per flow state Datagram vs VC Setup Addressing State Routing Router failure QoS Cong Datagram VC No Yes Full source and destination address Virtual Circuit ID All destination Per flow and all destination why Pre compute On demand Loss of buffered packets Loss of buffered packets and VC state Difficult Easy Difficult Easy Network Layer Design Issues Store and Forward Packet Switching Providing Services to the Transport Layer Implementation of Connectionless Service Implementation of Connection Oriented Service Comparison of Virtual Circuit and Datagram Subnets Routers or Level 3 Switches Determing route Run routing algorithms to build table Routing tables determine packet path output line Forwarding packets Routing Algorithms Attributes of Good algorithms for routing Correct Fair Simple Robust Stable Optimal Routing Flavors Non Adaptive static Adaptive dynamic Static Algorithms Non Adaptive Shortest path routing 2 Flooding 1 Non adaptive Routing Fixed routing static routing Do not take current state of the network e g load topology into decision Routes are computed in advance offline and downloaded to routers when booted Flooding Algorithm Static Every incoming packet forwarded on every outgoing link except the one it arrived on Problem duplicates Constraining the flood Hop count Keep track of packets that have been flooded Robust shortest delay picks shortest path as one of the paths Flooding
View Full Document
Unlocking...