Question? Leave a message!




Computer Communication Networks (CCN)

Computer Communication Networks (CCN) 12
Computer Communication Networks (CCN) 1Overview • Syllabus, administratrivia • Networking: An Overview of Ideas and Issues Rensselaer Polytechnic Institute 2 Shivkumar Kalvanaraman, Biplab SikdarWho’s Who • Instructors: – Shiv Kalyanaraman; kalyas ; x8979 – Biplab Sikdar; sikdab ; x6664 • Course secretary: (oncampus) – Jeanne DenueGrady: JEC 6049 ; x6313 • PDE/RSVP Pointofcontact: – Kari Lewick; CII 4011; x2347 • TAs: – G.Liu, H. Yang, Y. Pei (PDE), S. Raghunath (PDE) Rensselaer Polytechnic Institute 3 Shivkumar Kalvanaraman, Biplab SikdarWeb Resources • WebCT Course Web Site: – http://webct.rpi.edu – (backup) http://www.ecse.rpi.edu/Homepages/s hivkuma/teaching/fall2001/index.html • WebCT: bulletin board, video streams, homework dropbox etc • Text book Web Site: http://www.awl.com/kuroseross Rensselaer Polytechnic Institute 4 Shivkumar Kalvanaraman, Biplab SikdarCourse Description Highlights • Syllabus: – Networking layers: application, transport, network, link • Issues: application models, multiplexing, reliability, flow/congestion control, error detection/correction, multiple access etc – Network Modeling: Elementary probability, queuing theory, analysis of a router queue, network of queues, LAN performance Rensselaer Polytechnic Institute 5 Shivkumar Kalvanaraman, Biplab SikdarCourse Description Highlights (Continued) • Lectures • Informal quizzes: Every two weeks • WebCT bulletin board: Post your questions TAs monitor it daily. • WebCT: Grades, papers, RFCs, Internet drafts… • 2 Labs: Transport/Network layers 20 pts • 6 Homeworks: 30 pts • 3 exams: 15 pts, 15 pts, 20 pts: 50pts Rensselaer Polytechnic Institute 6 Shivkumar Kalvanaraman, Biplab SikdarPrerequisites • Background in elementary probability – Probability for Engineering Applications, ECSE4500, Discrete structures, CSCI4320, or Modeling and Analysis of Uncertainity, ENGR 2600 • Knowledge of basic computer organization – ECSE2660 Computer Architecture, Networks and Operating Systems or CSCI2500 Computer Organization • C programming knowledge • If you do not have the required prerequisites, you must drop the course and take it later Rensselaer Polytechnic Institute 7 (next year). Shivkumar Kalvanaraman, Biplab SikdarStill trying to get into the course • Do you have the prerequisites • Please submit course add form to course secretary: Jeanne, JEC 6049 by tomorrow (Wed, Aug 29th), noon time (12 pm). • Depending upon the number of people who drop the class, space available, TA resources available, we will add more students. – Decisions to be emailed to you by Jeanne. – Make sure you mention your email address to her. Rensselaer Polytechnic Institute 8 Shivkumar Kalvanaraman, Biplab SikdarAnswers to FAQ • All homeworks labs due at the beginning of the class indicated on the course calendar – Up to one late submission: no penalty – Beyond that 10 penalty: only if submitted before solutions are posted. • Exams are openbook and extremely time limited. • Exams consist of design qns, numerical, truefalse, and short answer questions. Rensselaer Polytechnic Institute 9 Shivkumar Kalvanaraman, Biplab SikdarAnswers to FAQ – Focus will be on conceptual understanding, and problemsolving skill. • Labs are based upon the programming assignments suggested in chap 3 and 4 of the textbook • Informal quizzes will be given for your benefit once in 23 weeks to recap/test recently covered material and reading assignments. No grading. Rensselaer Polytechnic Institute 10 Shivkumar Kalvanaraman, Biplab SikdarInformation, Computers, Networks • Information: anything that is represented in bits – Form (can be represented as bits) vs – Substance (cannot be represented as bits) • Properties: – Infinitely replicable – Computers can “manipulate” information – Networks create “access” to information Rensselaer Polytechnic Institute 11 Shivkumar Kalvanaraman, Biplab SikdarNetworks • Potential of networking: – move bits everywhere, cheaply, and with desired performance characteristics – Break the space barrier for information • Network provides “connectivity” Rensselaer Polytechnic Institute 12 Shivkumar Kalvanaraman, Biplab SikdarWhat is “Connectivity” • Direct or indirect access to every other node in the network • Connectivity is the magic needed to communicate if you do not have a direct ptpt physical link. – Tradeoff: Performance characteristics worse than true physical link Rensselaer Polytechnic Institute 13 Shivkumar Kalvanaraman, Biplab SikdarConnectivity. • Building Blocks – links: coax cable, optical fiber... – nodes: generalpurpose workstations... • Direct connectivity: – pointtopoint – multiple access Rensselaer Polytechnic Institute 14 Shivkumar Kalvanaraman, Biplab SikdarConnectivity.. • Indirect Connectivity – switched networks = switches – internetworks = routers Rensselaer Polytechnic Institute 15 Shivkumar Kalvanaraman, Biplab SikdarConnectivity … • Internet: – Besteffort (no performance guarantees) – Packetbypacket • A ptpt physical link: – Alwaysconnected – Fixed bandwidth – Fixed delay Rensselaer Polytechnic Institute 16 – Zerojitter Shivkumar Kalvanaraman, Biplab SikdarPointtoPoint Connectivity A B • Physical layer: coding, modulation etc • Link layer needed if the: – link is shared between apps (framing, medium access control, multiplexing) – link is unreliable (reliability) – link is used sporadically and traffic can flood receivers (flow control) • No need for protocol concepts like addressing, names, routers, hubs, forwarding, filtering … Rensselaer Polytechnic Institute 17 Shivkumar Kalvanaraman, Biplab SikdarConnecting N users: Directly ... • Bus: broadcast, collisions, media access control • Full mesh: Cost vs simplicity . . . Bus Full mesh  Address concept needed if we want the receiver alone to consume the packet Rensselaer Polytechnic Institute 18 Shivkumar Kalvanaraman, Biplab SikdarList of Problems (so far) • Topologies • Framing • Error control • Flow control • Multiple access – How to share a wire Rensselaer Polytechnic Institute 19 Shivkumar Kalvanaraman, Biplab SikdarHow to build Scalable Networks • Scaling: system allows the increase of a key parameter. Eg: let N increase… – Inefficiency limits scaling … • Direct connectivity is inefficient hence does not scale – Mesh: inefficient in terms of of links – Bus architecture: 1 expensive link, N cheap links. Inefficient in bandwidth use Rensselaer Polytechnic Institute 20 Shivkumar Kalvanaraman, Biplab SikdarFiltering, forwarding … • Filtering: choose a subset of elements from a set – Filtering is the key to efficiency scaling • Forwarding: actually sending packets to a filtered subset of link/node(s) – Packet sent to one link/node = efficient • Solution: Build nodes which filter/forward and connect indirectly = “switches” “routers” Rensselaer Polytechnic Institute 21 Shivkumar Kalvanaraman, Biplab SikdarConnecting N users: Indirectly • Star: Onehop path to any node, reliability, forwarding function • “Switch” S can filter and forward – Switch may forward multiple pkts in parallel for additional efficiency Star Rensselaer Polytechnic Institute 22 Shivkumar Kalvanaraman, Biplab Sikdar SConnecting N users: Indirectly … • Ring: Reliability to link failure, nearminimal links • All nodes do “forwarding” and “filtering” Ring Rensselaer Polytechnic Institute 23 Shivkumar Kalvanaraman, Biplab SikdarTopologies: Indirect Connectivity Ring Star Tree Rensselaer Polytechnic Institute 24 Shivkumar Kalvanaraman, Biplab Sikdar SInterNetworks: Networks of Networks …… = Internet …… Our goal is to design this black box on the right Rensselaer Polytechnic Institute 25 Shivkumar Kalvanaraman, Biplab SikdarInterNetworks: Networks of Networks • Internetworking involves two fundamental problems: heterogeneity and scale • Concepts: – Translation, overlays, address name resolution, fragmentation: to handle heterogeneity – Hierarchical addressing, routing, naming, address allocation, congestion control: to handle scaling • Covered in more detail in "Internet Protocols“ course Rensselaer Polytechnic Institute 26 Shivkumar Kalvanaraman, Biplab SikdarAdditions to Problem List • Fragmentation • Switching, bridging, routing • Naming, addressing • Congestion control, traffic management • Reliability Rensselaer Polytechnic Institute 27 Shivkumar Kalvanaraman, Biplab SikdarHow to do system design • Eg goal: Design an Internetwork… • Resources: – Space – Time – Computation – Money – Labor • Design: tradeoff cheaper resources against expensive ones to meet goals. Rensselaer Polytechnic Institute 28 Shivkumar Kalvanaraman, Biplab SikdarBuilding blocks: Multiplexing • Multiplexing = sharing – Trades time and space for money – Cost: waiting time, buffer space packet loss – Gain: Money = Overall system costs less Rensselaer Polytechnic Institute 29 Shivkumar Kalvanaraman, Biplab SikdarStatistical Multiplexing • Reduce resource requirements by exploiting statistical knowledge of the system. – Eg: average rate = service rate = peak rate – If service rate average rate, then system becomes unstable • First design to ensure system stability – Then, for a stable multiplexed system: • Gain = peak rate/service rate. • Cost: buffering, queuing delays, losses. Rensselaer Polytechnic Institute 30 Shivkumar Kalvanaraman, Biplab SikdarStability of a Multiplexed System Average Input Rate Average Output Rate = system is unstable How to ensure stability 1. Reserve enough capacity so that demand is less than reserved capacity 2. Dynamically detect overload and adapt either the demand or capacity to resolve overload Rensselaer Polytechnic Institute 31 Shivkumar Kalvanaraman, Biplab SikdarWhat’s a performance tradeoff • A situation where you cannot get something for nothing • Also known as a zerosum game. • R=link bandwidth (bps) • L=packet length (bits) • a=average packet arrival rate Traffic intensity = La/R Rensselaer Polytechnic Institute 32 Shivkumar Kalvanaraman, Biplab SikdarWhat’s a performance tradeoff • La/R 0: average queuing delay small • La/R 1: delays become large • La/R 1: average delay infinite (service degrades unboundedly = instability) Rensselaer Polytechnic Institute 33 Shivkumar Kalvanaraman, Biplab SikdarExample Design: CircuitSwitching Circuitswitching: A form of multiplexing – Divide link bandwidth into “pieces” – Reserve pieces on successive links and tie them together to form a “circuit” – Map traffic into the reserved circuits – Resources wasted if unused: expensive. – Mapping can be done without “headers”. – Everything inferred from timing. Rensselaer Polytechnic Institute 34 Shivkumar Kalvanaraman, Biplab SikdarExample Design: PacketSwitching Packetswitching: Another form of multiplexing: – Chop up data (not links) into“packets” Bandwidth division into “pieces” • Packets: data + metadata (header) Dedicated allocation Resource reservation – “Switch” packets at intermediate nodes • Storeandforward if bandwidth is not immediately available. Rensselaer Polytechnic Institute 35 Shivkumar Kalvanaraman, Biplab SikdarPacket Switching 10 Mbs statistical multiplexing C Ethernet A 1.5 Mbs B queue of packets 45 Mbs waiting for output link D E  Cost: selfdescriptive header perpacket, buffering and delays for applications.  Need to either reserve resources or dynamically detect/adapt to overload for stability Rensselaer Polytechnic Institute 36 Shivkumar Kalvanaraman, Biplab SikdarSummary of System Design Ideas • Multiplexing • Statistical Multiplexing • Stability and performance tradeoffs • Circuit switching • Packet switching Rensselaer Polytechnic Institute 37 Shivkumar Kalvanaraman, Biplab SikdarWhat are protocols • Networking software is organized as protocols • Eg: Human protocol vs network protocol: Hi TCP connection req. Hi TCP connection Got the reply. time Get http://www.rpi.edu/index.htm 2:00 file time Rensselaer Polytechnic Institute 38 Shivkumar Kalvanaraman, Biplab SikdarAnalogy: Organization of air travel ticket (complain) ticket (purchase) baggage (claim) baggage (check) gates (unload) gates (load) runway landing runway takeoff airplane routing airplane routing airplane routing • Protocols: a series of functions performed at different locations Rensselaer Polytechnic Institute 39 Shivkumar Kalvanaraman, Biplab SikdarOrganization of air travel: a different view ticket (complain) ticket (purchase) baggage (claim) baggage (check) gates (unload) gates (load) runway landing runway takeoff interface airplane routing airplane routing airplane routing Layers: each layer implements a service – via its own internallayer actions – relying on services provided by layer below Rensselaer Polytechnic Institute 40 Shivkumar Kalvanaraman, Biplab SikdarLayered air travel: services Countertocounter delivery of person+bags baggageclaimtobaggageclaim delivery people transfer: loading gate to arrival gate runwaytorunway delivery of plane airplane routing from source to destination Similarly, we organize network protocols into a bunch of layers Rensselaer Polytechnic Institute 41 Shivkumar Kalvanaraman, Biplab SikdarDistributed implementation of layers ticket (complain) ticket (purchase) baggage (claim) baggage (check) gates (unload) gates (load) runway landing runway takeoff airplane routing airplane routing intermediate air traffic sites airplane routing airplane routing airplane routing Rensselaer Polytechnic Institute 42 Shivkumar Kalvanaraman, Biplab Sikdar Departing airport arriving airportProtocol Implementations • Are building blocks of a network architecture • Each protocol object has two different interfaces – service interface: defines operations on this protocol – peertopeer interface: defines messages exchanged with peer L L i+1 i+1 service interface L L i i peer interface Rensselaer Polytechnic Institute 43 Shivkumar Kalvanaraman, Biplab SikdarReference Models for Layering TCP/IP Model TCP/IP Protocols OSI Ref Model Application Application FTP Telnet HTTP Presentation Session Transport TCP UDP Transport Internetwork IP Network Datalink Host to EtherPacketPointto Network net Radio Point Physical “Topdown” approach means we will first learn the application layer and then learn about lower layers Rensselaer Polytechnic Institute 44 Shivkumar Kalvanaraman, Biplab SikdarInternet protocol stack • application: supporting network applications – ftp, smtp, http application • transport: hosthost data transfer transport – tcp, udp network • network: routing of datagrams from source to destination link – ip, routing protocols • link: data transfer between physical neighboring network elements – ppp, ethernet • physical: bits “on the wire” Rensselaer Polytechnic Institute 45 Shivkumar Kalvanaraman, Biplab SikdarLayering: logical communication data application E.g.: transport transport transport • take data from network app link physical • add ack network addressing, application link reliability check transport physical data info to form network “datagram” link data physical • send datagram application application to peer transport transport transport network network • wait for peer to link link ack receipt physical physical • analogy: post office Rensselaer Polytechnic Institute 46 Shivkumar Kalvanaraman, Biplab SikdarLayering: physical communication data application transport network link physical network application link transport physical network link data physical application application transport transport network network link link physical physical Rensselaer Polytechnic Institute 47 Shivkumar Kalvanaraman, Biplab SikdarProtocol layering and data Each layer takes data from above • adds header information to create new data unit (“encapsulation”) • passes new data unit to layer below source destination message M M application application segment M H t transport M H transport t H H M datagram network n t network M H H n t H H H M link link l n t frame M H H H l n t physical physical Rensselaer Polytechnic Institute 48 Shivkumar Kalvanaraman, Biplab SikdarDesign Perspectives • Network users: services that their applications need, e.g., guarantee that each message it sends will be delivered without error within a certain amount of time • Network designers: costeffective design e.g., that network resources are efficiently utilized and fairly allocated to different users • Network providers: system that is easy to administer and manage e.g., that faults can be easily isolated and it is easy to account for usage Rensselaer Polytechnic Institute 49 Shivkumar Kalvanaraman, Biplab SikdarSummary • Administratrivia • Networks, connectivity, topologies … • Pot Pourri of networking concepts and problems to be explored in this course ... Rensselaer Polytechnic Institute 50 Shivkumar Kalvanaraman, Biplab Sikdar