1-intro (2).ppt

CS 4850/7850 Computer Networks I MWF 11:00 am – 11:50 am Prof. Michael Jurczyk Naka 121 884-8869 [email protected]  Vita of Michael Jurczyk Born: Yes When: ? Where: Essen, Germany 1990: MS in EE, University of...

CS 4850/7850 Computer Networks I MWF 11:00 am – 11:50 am Prof. Michael Jurczyk Naka 121 884-8869 [email protected]  Vita of Michael Jurczyk Born: Yes When: ? Where: Essen, Germany 1990: MS in EE, University of Bochum, Germany 1990-93: Institute for Microelectronics Stuttgart, Germany  Vita of Michael Jurczyk 1996: PhD in EE, University of Stuttgart, Germany interconnection networks for parallel processing and communication networks 1996/97: visiting professor at the School of ECE, Purdue University 1997-2003: assistant prof., CECS, UMC 2003: associate prof, CS, UMC 2004-2019: director of Undergrad. Studies Hobbies: hiking, biking, music CS-4850/7850 Computer Networks I Syllabus Class Hours: MWF 11:00 AM – 11:50 AM, Room: Naka 116 Instructor: Michael Jurczyk , Room 121 EBW, Phone 884-8869, Email Address: [email protected] Office Hours: The TA's office hours are posted on Canvas. Prerequisite: CS 3050 Textbook: Computer Networks: A Systems Approach, Larry L. Paterson and Bruce S. Davie, Morgan Kaufmann, 6th Edition, 2021 https://book.systemsapproach.org/index.html  Homework and Project Policies: Written homework will be assigned throughout the semester. There will also be one socket programming project. The socket programming project has two parts. Part one is required for all students. Part two is required for graduate students but optional for undergraduate students. Assignments (homework and project) will be due at the beginning of the lecture on the dates announced. It is your responsibility to keep track of assignments and their due dates. Assignments will not be accepted late unless prior permission has been given by the instructor due to extraordinary circumstances Canvas Submissions: As stated above, homework and project assignments have to be submitted electronically via Canvas before 11:00am on the due date. It is the student’s responsibility to double-check their submission before the deadline to ensure that the correct file was uploaded. We will grade what has been submitted, not what a student intended to submit. Lectures: The lectures in this course are an important way to impart to students the concepts and skills to be gained in this course. It is assumed that all students attend all lectures unless a grievous emergency occurs.  Exams: There will be two exams during the semester (NO final exam). Exam 1 is tentatively scheduled for Friday, October11, during class. Exam 2 is tentatively scheduled for Friday, November 22, during class. Both exams will be held in the class room. All exams are closed-note. Makeup Exams: For those having verified legitimate reasons to be absent during an exam, makeup exams will be arranged on an individual basis. Legitimate reasons are either being verifiably sick or being verifiably out-of-town (but NOT to extend Spring/Thanksgiving Break). A makeup exam will NOT be arranged for any other reason (e.g., could not attend exam because a student overslept, the alarm did not go off, the car did not start, the shuttle did not run or was late, to leave early for or arrive after Spring/Thanksgiving Break, etc.) Please contact the instructor at least 1 week prior to the scheduled test date, as it will not be possible to schedule a makeup "after the fact". Grading: Homework ----------------------> 25% Project ---------------------------> 25% Exam 1 --------------------------> 25% Exam 2 --------------------------> 25% A straight-scale grading scheme will be used to derive your final letter grade.  Incompletes: A grade of 'I' will be given only for cases in which there are documented medical problems or family emergencies. Usage of AI in this course: This course maintains a strict policy against the use of AI software in any aspect of the learning process. Students are expected to rely solely on their own cognitive abilities and academic skills when drafting, editing, and revising assignments. This course policy is in place to uphold the principle of individual academic achievement and to ensure that assessments accurately reflect each student’s independent learning and writing capabilities. Class Material Intellectual Property: All class materials including lecture slides, lecture videos, homework assignments, homework solutions, project assignments, exam assignments, and exam solutions are the intellectual property of Dr. Jurczyk. It is strictly prohibited for a student to post any of this material anywhere, including sites such as CourseHero. Violations will be reported to the Provost office.  Abuses of Trust: Academic honesty is fundamental to the activities and principles of a university. All members of the academic community must be confident that each person's work has been responsibly and honorably acquired, developed, and presented. Any effort to gain an advantage not given to all students is dishonest whether or not the effort is successful. The academic community regards academic dishonesty as an extremely serious matter, with serious consequences that range from probation to expulsion. See the information online at http://osrr.missouri.edu/academicintegrity/index.html and http://engineering.missouri.edu/cs/degree-programs/academic-honesty/. Duplicate homework/project written in collaboration with others is NOT acceptable. Although it is permissible to discuss the homework/project with others, these discussions should be of a general nature. All work at a detailed level must be done on your own. Students submitting the same or similar solutions to the homework or project or a student who submits a program downloaded off the Internet (or obtained from other sources such as AI tools) will be considered as having cheated. Any evidence of cheating, copying or collusion, plagiarism, etc., will be graded as zero for all students involved and will be referred to both the department Chairman and the Provost for other disciplinary action.  ADA Statement: If disability related accommodations are necessary (for example, a note taker, extended time on exams, captioning), please register with the Office of Disability Services (http://disabilitycenter.missouri.edu), S5 Memorial Union, 882-4696, and then notify me of your eligibility for reasonable accommodations. For other MU resources for students with disabilities, click on "Disability Resources" on the MU homepage. Lecture Recording: University of Missouri System Executive Order No. 38 lays out principles regarding the sanctity of classroom discussions at the university. The policy is described fully in section 200.015 of the Collected Rules and Regulations. In this class, students may not make audio or video recordings of course activity, except students permitted to record as an accommodation under section 240.040 of the Collected Rules. All other students who record and/or distribute audio or video recordings of class activity are subject to discipline in accordance with provisions of section 200.020 of the Collected Rules and Regulations of the University of Missouri pertaining to student conduct matters. Those students who are permitted to record are not permitted to redistribute audio or video recordings of statements or comments from the course to individuals who are not students in the course without the express permission of the faculty member and of any students who are recorded. Students found to have violated this policy are subject to discipline in accordance with provisions of section 200.020 of the Collected Rules and Regulations of the University of Missouri pertaining to student conduct matters.  What will we learn in this course? What is a computer network? – Architectures, protocols, physical communications How to connect to a network? – Switching, addressing How to scale a network? – Routing, transmission control How to allocate resources? – Congestion control, resource allocation How to connect applications to the network? – Application protocols How to address the security threats to a network? – Threats, security strategies MU CS 4850/7850 10  Introduction Slides adapted from Larry Peterson and B. Farouzan Outline Applications and Features Statistical Multiplexing Inter-Process Communication Network Architecture Performance Metrics Implementation Issues Reading: Chapter 1 MU CS 4850/7850 11  What’s a Network: Key Features Providing certain services – transport goods, mail, information or data Shared resources – used by many users, often concurrently Basic building blocks – nodes (active entities): process and transfer goods/data – links (passive medium): passive “carrier” of goods/data Typically “multi-hop” – two “end points” cannot directly reach each other – need other nodes/entities to relay MU CS 4850/7850 12  What’s a Network: “Nuts and Bolts” View network edge: millions of end-system router workstation devices: – pc’s workstations, servers server mobile – PDA’s, phones, toasters local net running network apps network core: routers, switches forwarding data – packets: packet switching regional net – calls: circuit switching communication links – fiber, copper, radio, … – Point-to-point or multiple access company net MU CS 4850/7850 13  Switched Networks A network can be defined recursively as... – two or more nodes – two or more networks connected by a link, or connected by a node MU CS 4850/7850 14  Brief History of the Internet 70’s: started as a research project, 56 kbps, < 100 computers 80-83: ARPANET and MILNET split, 85-86: NSF builds NSFNET as backbone, links 6 Supercomputer centers, 1.5 Mbps, 10,000 computers 87-90: link regional networks, NSI (NASA), ESNet(DOE), DARTnet, TWBNet (DARPA), 100,000 computers 90-92: NSFNET moves to 45 Mbps, 16 mid-level networks 94: NSF backbone dismantled, multiple private backbones Today: backbones run at >10 Gbps, >600 millions computers in >190 countries MU CS 4850/7850 15  Spring 2016 CMP_SC 4850/7850 16 The Internet today Peering point Peering point  Strategies Circuit switching: carry bit streams – original telephone network Packet switching: store-and-forward messages – Internet MU CS 4850/7850 17  Addressing, Routing, and Forwarding Address: byte-string that identifies a node – usually unique – What other properties? Types of addresses – unicast: node-specific – broadcast: all nodes on the network – multicast: some subset of nodes on the network Routing: process to determine which path a packet will take through a network to reach its destination Forwarding: Operation to send an incoming packet to the correct switch/router output MU CS 4850/7850 18  Multiplexing Synchronous Time-Division Multiplexing (STDM) Frequency-Division Multiplexing (FDM) – E.g., TV channels L1 R1 L2 R2 Switch 1 Switch 2 L3 R3 MU CS 4850/7850 19  Statistical Multiplexing Used in Internet On-demand time-division Schedule link on a per-packet basis Packets from different sources interleaved on link Buffer packets that are contending for the link Buffer (queue) overflow is called congestion MU CS 4850/7850 20  Inter-Process Communication Turn host-to-host connectivity into process-to-process communication (to support common services). Fill gap between what applications expect and what the underlying technology provides. Host Host Application Channel Host Application Host Host MU CS 4850/7850 21  IPC Abstractions Request/Reply Stream-Based – distributed file systems – video: sequence of frames 1/4 NTSC = 352x240 pixels – digital libraries (web) (352 x 240 x 24)/8=247.5KB 30 fps = 7500KBps = 60Mbps – video applications on-demand video video conferencing – More demanding MU CS 4850/7850 22  What Goes Wrong in the Network? Bit-level errors (electrical interference) Packet-level errors (congestion) Link and node failures Packets are delayed Packets are delivered out-of-order Duplicate packets are delivered MU CS 4850/7850 23  Layering Architecture Use abstractions to hide complexity Abstraction naturally lead to layering Alternative abstractions at each layer Application programs Request/reply Message stream channel channel Host-to-host connectivity Hardware MU CS 4850/7850 24  Protocols Building blocks of a network architecture – protocols define format, order of msgs sent and received among network entities, and actions taken on msg transmission, receipt Each protocol object has two different interfaces – service interface: operations on this protocol (e.g., how to get a message) – peer-to-peer interface: messages exchanged with peer (e.g., definition of message format) Term “protocol” is overloaded – specification of peer-to-peer interface – module that implements this interface MU CS 4850/7850 25  Interfaces Host 1 Host 2 Service High-level interface High-level object object Protocol Peer-to-peer Protocol interface MU CS 4850/7850 26 Spring 2016 CMP_SC 4850/7850 27 TCP/IP protocol suite Application: supporting network Application Application Layer 5 applications FTP, SMTP, HTTP Transport: process-process data Transport Transport Layer 4 transfer TCP, UDP Internet Network Layer 3 Network: host-host data transfer IP, Routing protocols Data link: data transfer between neighboring network elements PPP, Ethernet Hardware Devices Physical Layer 1 Physical: bits “on the wire” Spring 2016 CMP_SC 4850/7850 28 ISO/OSI model vs. TCP/IP e.g., FTP, SMTP, HTTP (UDP, TCP) (IP, Routing Protocols) (PPP, Ethernet, etc) Spring 2016 CMP_SC 4850/7850 29 Communication through Internet Switch 1 Switch 2 Switch 3 Spring 2016 CMP_SC 4850/7850 30 Identical objects between layers in TCP/IP Identical objects (messages) Identical objects (segment or user datagram) Identical objects (datagram) Identical objects (datagram) Identical objects (frame) Identical objects (frame) Identical objects (bits) Identical objects (bits) Spring 2016 CMP_SC 4850/7850 31 Encapsulation (Header/Body) Spring 2016 CMP_SC 4850/7850 32 ISO/OSI model vs. TCP/IP e.g., FTP, SMTP, HTTP (UDP, TCP) (IP, Routing Protocols) (PPP, Ethernet, etc)  Internet Architecture Defined by Internet Engineering Task Force (IETF) Hourglass Design Application vs Application Protocol (FTP, HTTP) FTP HTTP NV TFTP Transport Layer TCP UDP Internet Layer IP NET1 NET2 NETn MU CS 4850/7850 33  Implications of Hourglass A single Internet layer module: Allows all networks to interoperate – all networks technologies that support IP can exchange packets Allows all applications to function on all networks – all applications that can run on IP can use any network Simultaneous developments above and below IP MU CS 4850/7850 34  Network Performance How long does it take to transmit a data block – Latency – over single link – over a network of routers/switches connected by links Latency depends on – Initial time to set up communication (setup time) – time it takes to put data block on a link (transmit time) – length of links and link speed (propagation delay) – delay in a router (queuing delay) – Latency = setup time + transmit time + propagation delay + queuing delay Overall network performance – Throughput = Size-Of-Data-Block / Latency – Effective Bandwidth  Performance Metrics Transmit time – Time it takes to put data block on a link – Determined by link bandwidth – Bandwidth data transmitted per time unit e.g., 10 Mbps (Mega-bit-per-second) notation – KB = 210 bytes = 1024 bytes; MB = 220 bytes = 1048576 bytes – Mbps = 106 bits per second – Transmit Time = Data Size / Bandwidth Propagation Delay – Determined by length of links and link speed – Propagation Delay= Distance / c c = transmission speed c = 2.0 x 108 m/s in fiber; c = 2.3 x 108 m/s in cable MU CS 4850/7850 36  Data Size: Size Bits Bits in Decimal 1 KB (KiB) 8 x 210 8,192 1 MB (MiB) 8 x 220 8,388,608 1 GB (GiB) 8 x 230 8,589,934,592 Bandwidth: BW bps bps in Decimal 1 Kbps 103 1,000 1 Mbps 106 1,000,000 1 Gbps 109 1,000,000,000  Network Performance Packet-switched networks – Network can only handle fixed-sized data packets Need to chop data block up into packets and send packets one-by-one Latency: total time between sending the first data bit to having received the last data bit – In some networks, after sending a packet, sender waits for a response from the receiver that that packet was received, before sending the next packet Need to wait RTT (Round Trip Time) between sending packets – RTT = 2 x one-way time (time for data packet + time for response) For example, if need to send 10 packets – Need 9 RTT to send first 9 packets, then 0.5 RTT for last packet to be received -> 9.5 RTT delay  Exercise Calculate the total time required to transfer a 1.5 MB file, assuming an RTT of 80 ms, a packet size of 1 KB, and an initial 2xRTT of “hand- shaking” before data is sent. The bandwidth is 10 Mbps and data packets can be sent continuously. Assume transfer is completed when last bit of the last packet arrives. Sol: – [Setup Time] = 2RTT (handshake) = 0.080s x 2 = 0.160s – [Transmit Time] = 1.5 MB / 10 Mbps = 1.5 x 220 x 8 /10,000,000s = 12,582,912/10,000,000s = 1.258s – [Propagation] = RTT/2 (last packet) = 0.080s/2 = 0.04s – Total Latency = 0.160s (setup) + 1.258s (transmit) + 0.04s (propagation) = 1.458s What is the effective bandwidth (or throughput)? – 12,582,912 bits [file size in bits]/1.458s [total time] = 8.63 Mbps MU CS 4850/7850 39  Exercise Same as before, but after finishing sending each data packet, must wait one RTT before sending the next. – How does this change the calculation? – Increase in Total Latency -> decrease of Effective Bandwidth – # of packets=1.5MB/1KB = 1.5 x 220 / 210 =1536 – Increase of Total Latency by 1535 x 0.080s = 122.8s – Total Latency = 1.458s + 122.8s = 124.258s Effective Bandwidth – 12,582,912 bits /124.258 s = 101,264.4 bps = 101.26 Kbps 8.63 Mbps (previous example) MU CS 4850/7850 40  Exercise The link allows infinitely fast transmit, but limits bandwidth such that only 20 packets can be sent per RTT. – How does this change the problem? – No Transmit time. Only RTT to account for in the calculation – 1536 packets / 20 packets => 77 batches – 2 RTT(handshaking) + 76 RTT (for the first 76 batches) + 0.5 RTT (last batch) = 78.5 RTT – 78.5 x 0.08s = 6.28s Effective Bandwidth – (1.5 x (220) x 8)/6.28 bps = 2,003,648.408 bps = 2.003 Mbps MU CS 4850/7850 41  Exercise Consider a point-to-point link 50 km in length. At what bandwidth would propagation delay (at a speed of 2×108 m/s) equal transmit delay for 100-byte packets? What about 512- byte packets? Answer: – 100-byte packets: 3.2 Mbps – 512-byte packets: 16.384 Mbps MU CS 4850/7850 42  Network Performance Revisited A S1 B Calculate the total time required to transfer a 1.5 MB file from host A to host B through switch S1. The delay on link A -> S1 is 25ms and the delay on link S1 -> B is 15ms. A packet size of 1 KB is used, and an initial 2xRTT of “hand-shaking” before data is sent occurs (RTT does not include switch delay). The bandwidth is 10 Mbps on each link. S1 has a processing time of 10ms before sending out a packet (i.e., packet encoding). Assume host A sends packets continuously and transfer is completed when last packet arrives at B. MU CS4850/7850 43  Network Performance Revisited 10 ms A 25 ms 10 Mbps S1 15 ms 10 Mbps B Latency = Setup Time + Propagation + Transmit (A->S1) + Transmit (S1->B) + Switch Processing Time RTT = 2 x (25ms + 15ms) = 80ms Setup Time 2xRTT Handshaking = 2 x 80ms= 160ms = 0.16s Propagation = RTT /2 = 40ms = 0.04s MU CS4850/7850 44  Network Performance Revisited 10 ms A 25 ms 10 Mbps S1 15 ms 10 Mbps B Latency = Setup Time + Propagation + Transmit (A->S1) + Transmit (S1->B) + Switch Processing Time Transmit A -> S1 = file size /BW = 1.5 MB / 10 Mbps = 8x 1.5x 220 /10,000,000 s =1.258s Transmit S1-> B = packet size/ BW = 1 KB / 10 Mbps = 8x 210 /10,000,000 s = 0.8192 ms Switch Processing Time Switch = 10 ms 1 Packet Buffer Proc. time MU CS4850/7850 45  Network Performance Revisited 10 ms A 25 ms 10 Mbps S1 15 ms 10 Mbps B Latency = Setup Time + Propagation + Transmit (A->S1) + Transmit (S1->B) + Switch Processing Time Latency = 0.16s + 0.04s+ 1.258s + 0.8192 ms + 0.01 s = 1.469s Throughput = file size/latency = 8 x 1.5 x 220 b/ 1.469s = 8,565,631 bps = 8.566 Mbps MU CS4850/7850 46  Delay x Bandwidth Product Amount of data “in flight” or “in the pipe” Usually relative to RTT Example: 100ms x 45Mbps ≈ 560KB Delay Bandwidth MU CS 4850/7850 47  Bandwidth versus Latency Relative importance – 1-byte message: Latency dominates Bandwidth 1ms vs 100ms dominates 1Mbps vs 100Mbps – 25MB message: Bandwidth dominates Latency 1Mbps vs 100Mbps dominates 1ms vs 100ms Infinite bandwidth – RTT (measured using a small size packet) dominates Throughput = TransferSize / TransferTime – Also called effective bandwidth TransferTime = RTT + TransferSize/Bandwidth MU CS 4850/7850 48  Other Metrics Application’s bandwidth need – VBR (variable bit rate) vs CBR (constant bit rate) Delay jitter – Buffering Reliability, packet loss rate Efficiency/overhead of implementation MU CS 4850/7850 49  Implementing Network Software Socket API Creating a socket int socket(int domain, int type, int protocol) domain = PF_INET, PF_UNIX type = SOCK_STREAM, SOCK_DGRAM, SOCK_RAW Active Open (on client) int connect(int socket, struct sockaddr *addr, int addr_len) MU CS 4850/7850 50  Sockets (cont) Passive Open (on server) int bind(int socket, struct sockaddr *addr, int addr_len) int listen(int socket, int backlog) int accept(int socket, struct sockaddr *addr, int addr_len) Sending/Receiving Messages int send(int socket, char *msg, int mlen, int flags) int recv(int socket, char *buf, int blen, int flags) MU CS 4850/7850 51 Example: Simple Socket Program (Client Side) sin.sin_addr.s_addr = SERVER_IP_ADDRESS; sin.sin_port=htons(SERVER_PORT); … s=socket(PF_INET, SOCK_STREAM, 0); connect(s, (struct sockaddr *)&sin, sizeof(sin)); send(s, buf, sizeof(buf),0); close(s); MU CS 4850/7850 52  Example: Simple Socket Program (Server Side) sin.sin_addr.s_addr = INADDR_ANY; sin.sin_port=htons(SERVER_PORT); … s=socket(PF_INET, SOCK_STREAM, 0); bind(s, (struct sockaddr *)&sin, sizeof(sin)); listen(s, MAX_PENDING); while(1){ new_s=accept(s, (struct sockaddr *)&sin, &len); while (len=recv(new_s, buf, sizeof(buf),0)) fputs(buf, stdout); close(new_s); } MU CS 4850/7850 53  Introduction Summary: Applications and Features Statistical Multiplexing Inter-Process Communication Network Architecture Performance Metrics Implementation Issues MU CS 4850/7850 54