Computer Systems Engineering Introduction to Systems PDF

Computer Systems Engineering Introduction to (Computer) Systems Rodrigo Bruno 1 Computer Systems Engineering Who am I? (Rodrigo Bruno) ○ Assistant Professor @ Técnico ○ Senior Researcher @ INESC-ID Lisboa ○ Where to f...

Computer Systems Engineering Introduction to (Computer) Systems Rodrigo Bruno 1 Computer Systems Engineering Who am I? (Rodrigo Bruno) ○ Assistant Professor @ Técnico ○ Senior Researcher @ INESC-ID Lisboa ○ Where to find me online: https://rodrigo-bruno.github.io/ ○ Where to find me in person: Room 534, INESC-ID Lisboa ○ Before Técnico Senior Researcher @ Oracle Labs Zurich Postdoc @ ETH Zurich PhD @ Técnico Google Microsoft Research … 2 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering What is my research focused on? ○ 10 thousand foot view making applications run more efficiently ○ 10 hundred foot view optimizing applications running on the cloud ○ 10 foot view focus on the intersection between programming languages and systems to optimize performance of cloud applications such as microservices and serverless. 3 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Minor in Informatics (Computer Science) What is Computer Science? ○ Computer Science is the study of computers and computer systems ○ Many areas: Systems, Programming Languages, ArtificiaI Intelligence, Networks, etc Computer Science vs Computer Programming ○ Computer science offers a holistic view ○ Computer programming offers a local view ○ A computer scientist knows how to build complex, efficiency, and large-scale systems ○ A computer programmer knows how to tell computers what to do (application) 4 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Minor in Informatics (Computer Science) Algorithm Design Using Python Artificial Intelligence Programming for Data Science Computer Systems Engineering ○ introduction to computers and computer systems ○ how to build systems ○ umbrella course compose multiple building blocks written using techniques from multiple areas 5 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Why do you need this course? In this course you will understand the fundamental abstractions and building blocks that computers are made of. You will also understand how to effectively and efficiently take advantage of computers. Why isn’t knowing how to program enough? Programming allows you to create simple programs. Understanding how computer systems work will allow you to design efficient and complex programs. 6 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Goals of the course Introduce the notion of Computer Systems Identity and study Computer Systems at different levels ○ Computer Architecture ○ Operating Systems ○ Distributed Systems After completing the course, you should be able to ○ analyze and identify trade-offs in computer systems ○ design, build, and/or modify computer systems ○ quickly identify and investigate different areas of computer systems 7 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Syllabus Introduction to Computer Systems Hardware Virtualization Networks Cloud Computing Information Security Performance in Systems Fault Tolerance Consistency 8 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Course Organization Lectures ○ 2 lectures per week Monday and Thursday ○ Principles of Computer System Design: An Introduction 2 volumes (second volume is available online) Labs Classes ○ 2 classes per week Monday and Thursday ○ exercise tutorials + project support (project description will be next week) 9 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Course Organization Office hours @ INESC 534 ○ mondays from 15h00 to 17h00 ○ thursdays from 14h00 to 16h00 ○ any other time, send me an email [email protected] 10 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Evaluation (theoretic component) Final exam (50% of your final grade) ○ minimum grade 9.5/20 ○ covers course bibliography ○ first exam: January 20th ○ second exam: February 6th 11 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering Evaluation (practical component) Project (50% of your final grade) ○ minimum grade 9.5/20 ○ uses the technology learned during lab classes ○ groups of 1-2 students ○ project description published next week ○ project deadline on the 12th of Jan def grade(exam, project): ○ deliverables: report + code if exam < 9.5: return “RE” ○ project visualization + discussion if project < 9.5: Final grade return “RE” return (exam + project)/2 12 Computer Systems Engineering - Introduction to Systems Computer Systems Engineering For today! Computer Systems and Complexity ○ What is a System? What is a Computer System? ○ Complexity of Computer Systems ○ How to cope with complexity Enforced Modularity ○ Common pattern to cope with complexity 13 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity 14 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity What is a system? A system is a set of interconnected components that has an expected behavior observed at the interface with its environment. Component A Component C Component B Environment Interface 15 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity What is a system? A system is a set of interconnected components that has an expected behavior observed at the interface with its environment. Examples of systems? Cars, Planes, Trains, Mobile Phones, Televisions, Computers,... What is a computer system? A system intended to store, process, or communicate information under automatic control. 16 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Granularity of a system Systems can be decomposed into subsystems which are also systems. 17 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Purpose of a system Gaming station Working station Movie station Single entity can be interpreted as multiple different systems according to its purpose. 18 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Common challenges in Computer Systems Emergent properties ○ properties that are not evident in the individual components of a system Propagation of effects ○ effects in one or more components of a system can easily propagate effects to other components Incommensurate scaling ○ different parts of the system exhibit different orders of growth Trade-offs ○ system design options favor some performance metrics in detriment of others 19 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Complexity in Systems Complexity is a subjective and relative concept often associated with systems. There are a few signs that evidence the presence of complexity: ○ large number of components ○ large number of interconnections ○ many irregularities ○ long description ○ large maintenance team 4778 pages 20 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Sources of Complexity There are two main sources of complexity in systems: ○ Cascading and Interacting Requirements adding a new requirement to a system increases its complexity complexity comes not only from the requirement but also from Principle of escalating complexity. its interactions with other existing requirements 21 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Sources of Complexity There are two main sources of complexity in systems: ○ Maintaining High Utilization higher resource utilization leads to increased complexity improving utilization requires exponentially harder effort Law of diminishing returns. compared to the last utilization improvement 22 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity Modularity Abstraction Layering Hierarchy Iteration Simplicity 23 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Modularity Divide and conquer strategy ○ analyze the system and divide it into a collection of subsystems (modules) Changes in the system become localized in modules ○ For a program with N lines and K modules solving a bug may require looking at ~N/K instead of ~N lines ○ For a program with I subsystem interactions and K modules developing a new feature in a module may require looking at ~I/K instead of I interactions 24 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Abstraction How to divide the system into modules? Division should ○ reduce the number of interactions between modules ○ reduce the propagation of effects from one module to another changing (bug fixing, new feature, etc) one module requires changing other modules? if a module fails, will the fault propagate to other components? Abstraction is a way of separating ○ the implementation (internal interactions) from the specification (external interactions) it allows one to interact with a module without understand its internals 25 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Layering User Interface Layer Way to organize modules in layers ○ multiple modules that accomplish a certain Service Layer mechanism/goal make a layer ○ a module only interacts with other modules Logic Layer in the same layer in the upper or lower layer Data Access Layer Reduces and identifies interactions between modules Storage Layer Layering in Web apps. 26 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Hierarchy User Interface Layer (Another) Way to organize modules in hierarchy levels ○ multiple modules that accomplish a certain Service Layer mechanism/goal make a hierarchy Application Back-end ○ a module only interacts with other modules Logic Layer in the same level in the upper or lower level Data Access Layer System is divided into a tree-like shape Storage Reduces and identifies interactions between modules Storage Layer Hierarchy of Layerers in Web apps. 27 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Iteration Large systems are not designed all at once ○ start with less and simple features ○ over time, add more and more complex features Design for iteration ○ changes are inevitable ○ take small and planned steps ○ requirements change over time Lines of code in the Linux kernel ○ technology changes over time 28 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Copying with Complexity - Keep it Simple! Simplicity requires designers to ○ avoid non-critical features which would significantly increase complexity Features might look straightforward and well within the technology budget ○ interactions between old and new features might not be foreseen ○ complexity accumulates over time Features should be weighted against their potential contribution for complexity The lifetime of a system is usually limited by the complexity that accumulates over time. 29 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Computer Systems are not the same as other systems The complexity of a computer system is not limited by physical laws; ○ unlike other analog systems, digital systems are not limited by computer systems are limited by the designer’s ability to understand them The rate of change of computer system technology is unprecedented; 30 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Physical limits in Computer Systems 31 Computer Systems Engineering - Introduction to Systems Enforced Modularity 32 Computer Systems Engineering - Introduction to Systems Enforced Modularity Soft vs Enforced Modularity Large applications are can divided into modules ○ modules expose interfaces which, if well designed, reduces complexity ○ however… software has bugs and problems can propagate between modules def function foo():... All modules terminate! log(0) def function log(value):...... CRASH!... 33 Computer Systems Engineering - Introduction to Systems Enforced Modularity Procedure Calls as a form of Soft Modularity def function measure(func): procedure call start = getTime(‘sec’) def function getTime(unit): func() time = hwclock finish = getTime(‘sec’) time = convertTo(time, unit) return end - start return time 34 Computer Systems Engineering - Introduction to Systems Enforced Modularity Procedure Calls as a form of Soft Modularity def function measure(func): procedure call start = getTime(‘sec’) def function getTime(unit): func() time = hwclock finish = getTime(‘sec’) time = convertTo(time, unit) return end - start return time Procedure Calling convention: single stack for all modules stack resides in memory ○ accessible from all modules stack frame per procedure call 35 Computer Systems Engineering - Introduction to Systems Enforced Modularity Procedure Calls as a form of Soft Modularity Ways in which modularity can break: ○ the callee corrupts the caller’s are of the stack e.g., local variables or saved register values leading to incorrect results ○ the callee corrupts the return address control will not return to the caller ○ callee saves the return value in the wrong place ○ divide by zero, forbidden operation fate sharing ○ corrupting global variables 36 Computer Systems Engineering - Introduction to Systems Enforced Modularity How to achieve stronger modularity? Reduce the number of possible interactions between modules Interactions must be well defined def measure(func) PC1 soft modularity ○ Input and Output space specified procedure call ‘physical’ isolation def getTime(unit) ○ different hardware (different machine?) enforced modularity ○ different process (more on that later) def measure(func) PC1 ○ communication through a communication link remote procedure call requests to modules only through messages def getTime(unit) PC2 Error propagation becomes limited to messages 37 Computer Systems Engineering - Introduction to Systems Enforced Modularity Clients and Services (extremely) Popular modular architecture ○ Client uses a service offered by the Service Interaction between client and service 38 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Summary What is a system? ○ set of interconnected components that observed at the interface with its environment Sources of complexity: cascading requirements and high utilization How to cope with complexity: ○ Modularity ○ Abstraction ○ Layering ○ Hierarchy ○ Iteration ○ Simplicity 39 Computer Systems Engineering - Introduction to Systems Computer Systems and Complexity Where to go now? (Enforced) Modularity helps keeping up with complexity ○ does this mean that we need separate computers for every application? What if we now want ○ scalability? ○ fault-tolerance? ○ security? ○ high-performance? 40 Computer Systems Engineering - Introduction to Systems  Computer Systems Engineering Organization of Computer Systems Rodrigo Bruno 1 Introduction to (Computer) Systems Recap! Computer Systems and Complexity ○ What is a System? Components with the same goal, interface, environment ○ What is a Computer System? System that processes data, automatic control ○ Complexity of Computer Systems requirements, utilization ○ How to cope with complexity modularity, abstraction Enforced Modularity 2 Computer Systems Engineering Organization of Computer Systems For today! The main abstractions/building blocks of a computer The hardware layer The software layer 3 Computer Systems Engineering Organization of Computer Systems Three main abstractions of Computer Systems the memory ○ provides storage, ability to recall Interpreter the interpreter Communication Link ○ provides processing capabilities the communication link Memory ○ enables communication between components These abstractions appear in most systems either on a micro or macro scale. 4 Computer Systems Engineering Organization of Computer Systems 5 Computer Systems Engineering Organization of Computer Systems 6 Computer Systems Engineering Organization of Computer Systems 7 Computer Systems Engineering Organization of Computer Systems Interpreter Memory Communication Link System component that “remembers” data (instructions or values) Memory Examples include: ○ Hardware memory devices: RAM chips, Flash Memory, Magnetic tap/disk, CD-R and DVD-R, etc ○ Higher level memory systems: RAID, File System, Databases, Caches, etc All memory devices offer (at least) two operations ○ WRITE(name, value) saves a value and labels it with a name; ○ value load(thread->SP, thread->PC, thread->PMAR); processor->run(); User Thread User Thread processor->save(thread->SP, thread->PC, thread->PMAR); User Thread } } 11 Computer Systems Engineering Operating Systems Cooperative Scheduling Control Flow 12 Computer Systems Engineering Operating Systems Cooperative Scheduling Implementation 13 Computer Systems Engineering Operating Systems Cooperative Scheduling Implementation 14 Computer Systems Engineering Operating Systems Cooperative Scheduling Implementation 15 Computer Systems Engineering Operating Systems Cooperative Scheduling Implementation 16 Computer Systems Engineering Operating Systems Cooperative Scheduling Implementation 17 Computer Systems Engineering Operating Systems Preemptive Scheduling vs Collaborative Scheduling What is the thread never calls yield? ○ for loop ○ waiting for input ○ etc? Timer sends interrupts every N microseconds ○ interrupt handler forces a switch from the user layer thread into the processor layer thread 18 Computer Systems Engineering Operating Systems Scheduling Algorithms First-Come, First-Served (FCFS) Scheduling Round Robin(RR) Scheduling Shortest-Job-Next (SJN) Scheduling Shortest Remaining Time Priority Scheduling Multiple-Level Queues Scheduling Multilevel Feedback Queues Scheduling Highest Response Ratio Next 19 Computer Systems Engineering Operating Systems How can two threads communicate? Editor needs to send message to File Service Bounded buffer is provided by the OS ○ piece of memory accessible by both Coordination problem: ○ where to write? ○ where to read? ○ when to write? ○ when to read? 20 Computer Systems Engineering Operating Systems Producer-Consumer 21 Computer Systems Engineering Operating Systems Producer-Consumer 22 Computer Systems Engineering Operating Systems (Naive) Producer-Consumer Two producer/sender threads: A, B ○ can anything go wrong? A6, A7, A8, B6, B7, B8 (expected!) A6, B6, B7, A7, A8, B8 (race condition!) ‘in’ is now 2 but only one message in the buffer 23 Computer Systems Engineering Operating Systems Race conditions (C/C++) ○ in = in + 1 // inc in by 1 Assembly ○ 1: LOAD in, r0 // load in into register 0 ○ 2: ADD r0, 1 // increment register 0 ○ 3: STORE r0, in // store register 0 back into ‘ in’ Impossible to control/estimate thread interleaving order! 24 Computer Systems Engineering Operating Systems Race conditions (C/C++) ○ in = in + 1 Assembly ○ 1: LOAD in, r0 ○ 2: ADD r0, 1 ○ 3: STORE r0, in Lost notification! 25 Computer Systems Engineering Operating Systems Solution to Race Conditions Locks! ○ shared variable that acts as a flag to coordinate usage of other shared variables A single thread can hold the lock at any moment ○ creates zones of mutual exclusion critical sections Two primitives: acquire and release Implementation using HW support (checks if any thread in any processor has the lock) ○ acquire(lock) ○ in = in + 1 // critical section! ○ release(lock) 26 Computer Systems Engineering Operating Systems Producer-Consumer w/ locks 27 Computer Systems Engineering Operating Systems Deadlock! 28 Computer Systems Engineering Operating Systems Deadlocks (wait graph) 29 Computer Systems Engineering Operating Systems Preventing Deadlocks How to prevent deadlocks? ○ up to programmer good practises always acquire locks in the same order across different threads/modules T1: acquire(L1), acquireL2 T2: acquire(L1), acquire(L2) (if L1 is already take, T2 cannot acquire L2) release locks in the inverse order (good practise) T1: release(L2), release(L1) T2: release(L2), release(L1) ○ very hard to debug! May only happen in specific runs. Subject to scheduling, input delay, etc. 30 Computer Systems Engineering Operating Systems Summary Virtualization ○ What is it? Operating System ○ What is it? Threads ○ How to multiplex the processor? ○ How to schedule threads? Producer-Consumer ○ How to communicate between threads? 31 Computer Systems Engineering Operating Systems Where to go now? Virtualizing memory (book reference: Section 5.4) ○ virtual memory ○ processes File System (book reference: Section 2.5) 32 Computer Systems Engineering  Computer Systems Engineering Operating Systems (part II) Rodrigo Bruno 1 Operating Systems Recap! Virtualization ○ virtualize processors into threads 2 Computer Systems Engineering Operating Systems Recap! Virtualization ○ virtualize processors into threads ○ how to communicate between threads 3 Computer Systems Engineering Operating Systems Recap! Virtualization ○ virtualize processors into threads ○ how to communicate between threads acquire(lock) in = in + 1 // critical section! release(lock) 4 Computer Systems Engineering Operating Systems For today! How to virtualize memory? ○ Virtual Memory How to persist memory? ○ File System 5 Computer Systems Engineering Operating Systems Virtualizing Memory App A App B App C Bus Memory 6 Computer Systems Engineering Operating Systems App A App B App C Virtualizing Memory Bus Memory Requirements for virtualization ○ isolation apps cannot read/write to each other’s memory ○ transparency apps should not be aware of other applications using the same physical device (memory) ○ multiplexing physical device should be utilized at the same time by multiple apps 7 Computer Systems Engineering Operating Systems Virtualizing Memory (Apps access physical memory) How to grow memory for a particular Thread? App A App B App C Bus Mem App A Mem App B Mem App C Memory 0 232 8 Computer Systems Engineering Operating Systems Virtualizing Memory (Apps access virtual memory) App A App B App C Virtual Addresses Virtual Memory Manager Physical Addresses Bus Memory 0 232 9 Computer Systems Engineering Operating Systems Virtual Memory Decouple modules with indirection Two main advantages (w.r.t. using physical addresses) ○ Apps can grow memory utilization at any moment adjacent virtual memory positions may not be adjacent in physical memory ○ The same virtual memory address can be given to different Apps some Apps expect components to be located at constant/well-defined memory addresses 10 Computer Systems Engineering Operating Systems Mapping between Virtual and Physical Addresses 264 264 Addresses with 64 bits ○ each usually address identifies 8 bit / 1 byte ○ 264 virtual addresses ○ 264 physical addresses ○ 64 bits to store a single address 2 * 64 bits * 264 2 * 26 * 264 0 0 at least 271 bits to store all addresses Virtual Addresses Physical Addresses 11 Computer Systems Engineering Operating Systems Mapping between Pages and Blocks 12 Computer Systems Engineering Operating Systems Virtual Memory Manager Still 252 entries! Multi-level tables. 13 Computer Systems Engineering Operating Systems x86 Virtual Page Table PMAR 14 Computer Systems Engineering Operating Systems x86 Translation Lookaside Buffer (TLB) 15 Computer Systems Engineering Operating Systems Virtual Address Spaces App A App B 16 Computer Systems Engineering Operating Systems Putting it all together… 17 Computer Systems Engineering Operating Systems Thread vs Address Space vs Process In mainstream Operating Systems… ○ a process is a set of one or more threads that share a single address space ○ applications (i.e., processes) always start with one thread and one address space additional thread can be allocated and started using the OS API ○ threads within a process share the address space a virtual memory address translates to the same physical address ○ different processes cannot read/write to each others’ memory why? 18 Computer Systems Engineering Operating Systems File System one of the main OS components determines the layout of files in storage controls read and writes from/to storage two main types of items: ○ directories set of files and/or directories ○ files stream of data 19 Computer Systems Engineering Operating Systems File System API 20 Computer Systems Engineering Operating Systems File System Layers 21 Computer Systems Engineering Operating Systems Block Layer Storage devices (HDD, SDD, NVMe) ○ split into fixed size blocks Tradeoff between block size ○ too small incurs into a metadata overhead ○ too large and some block space becomes unutilized recent systems use 8 KB Blocks indexed by an integer 22 Computer Systems Engineering Operating Systems File and Inode number Layers Files may be larger than a single block ○ or may change their size over time Traditional file systems use the concept of an inode ○ maps an id to a list of blocks and total size Inodes can be identified with an id ○ inodes’ id identify the inode from the inode table 23 Computer Systems Engineering Operating Systems File name and Path layer Files are given names instead of just inode numbers Names can point to files or directories ○ directories aggregate multiple files and/or directories Paths are composed by a sequence of names that ultimately point to a file or directory 24 Computer Systems Engineering Operating Systems Absolute path name and symbolic layer File paths are all connected at the root of the file system Symbolic links create synonyms for files ○ the same file name, same inode but ○ under different path 25 Computer Systems Engineering Operating Systems Putting it all together to open file /a/b/c.c 26 Computer Systems Engineering Operating Systems Putting it all together Inode data structure 27 Computer Systems Engineering Operating Systems Putting it all together to open file /programs/pong.c (block layer) 28 Computer Systems Engineering Operating Systems Opening a file 29 Computer Systems Engineering Operating Systems Reading a file 30 Computer Systems Engineering Operating Systems Summary How to virtualize memory? ○ Virtual Memory How to persist data? ○ File System 31 Computer Systems Engineering Operating Systems Where to go now? Networks (book reference: Sections 7.1 to 7.7) ○ how can computer communicate with each other? 32 Computer Systems Engineering  Computer Systems Engineering Computer Networks (part I) Rodrigo Bruno 1 Computer Networks Recap! Virtual Memory App A App B App C Virtual Addresses Virtual Memory Manager Physical Addresses Bus Memory 0 232 2 Computer Systems Engineering Computer Networks Recap! File System 3 Computer Systems Engineering Computer Networks For today! Computer Networks! ○ Physical limitations ○ Isochronous networks ○ Asynchronous networks ○ Network delay ○ Packet duplicates ○ Packet ordering 4 Computer Systems Engineering Computer Networks Again? Interpreter Computer Networks Communication Link Memory 5 Computer Systems Engineering Computer Networks Computer Networks 6 Computer Systems Engineering Computer Networks Fundamental Physical Properties The speed of light is finite ○ ~300000 Km / second (in vacuum), fast enough? ○ 1 ms to transmit a signal from Lisbon to Porto (~300 Km) These are optimal times with a direct cable sending data ○ 6 ms to transmit a signal from Lisbon to Paris set speed of light! ○ 18 ms to transmit a signal from Lisbon to New York ○ 30 ms to transmit a signal from Lisbon to San Francisco ○ 65 ms to transmit a signal from Lisbon to Auckland In reality, latency is much higher… 7 Computer Systems Engineering Computer Networks Fundamental Physical Properties The speed of light is finite Communication environments are hostile Source: https://www.mentalfloss.com/article/60150 ○ computers are made of relatively reliable components ○ computers operate in controlled environments ○ networks may operate under hostile environments cables through the ocean radio signals over unpredictable weather entire atmosphere (e.g. Starlink) Internet’s Undersea Cables 8 Computer Systems Engineering Computer Networks Fundamental Physical Properties The speed of light is finite Communication environments are hostile Communication media have limited bandwidth ○ transmission rate limited by noise/attenuation of the communication medium and environment distance between sender and receiver strength of the signal ○ bandwidth needs to be shared (multiplexed) Difference between bandwidth and latency? 9 Computer Systems Engineering Computer Networks Fundamental Physical Properties The speed of light is finite Communication environments are hostile Communication media have limited bandwidth Network infrastructure cost doesn’t follow technological trends ○ while processors, memory, storage get cheaper every year ○ the cost of installing network infrastructure doesn’t (or even increases) digging up streets to layout cables launching satellites legal actions to deploy antenas etc 10 Computer Systems Engineering Computer Networks Time-division Multiplexing 11 Computer Systems Engineering Computer Networks Time-division Multiplexing Isochronous Multiplexing 12 Computer Systems Engineering Computer Networks Time-division Multiplexing Advantages: ○ predictable bandwidth and latency good for continuous streams of data (voice and video for example) Disadvantages: ○ requires a connection (reserving a bandwidth slot) ○ limited number of open connections ○ fixed size frames ○ wasteful for irregular data transfers (burts, infrequent communication) 13 Computer Systems Engineering Computer Networks Asynchronous Multiplexing Computer networks tend to send data on an irregular basis ○ instead of frames, computer networks send messages ○ tradeoff between predictability and flexibility 14 Computer Systems Engineering Computer Networks Asynchronous Multiplexing 15 Computer Systems Engineering Computer Networks Packet Forwarding Route: 1,3 16 Computer Systems Engineering Computer Networks Delay (transit time) Different packets may experience different transit times ○ propagation delay time to traverse the link ○ transmission delay time to write the packet to the link ○ processing time time to decide where to forward the packet ○ queueing time time a packet waits to be processed in a packet switch 17 Computer Systems Engineering Computer Networks Queuing Time Packet switches can be modelled as a queue ○ upon arrival, the packet goes into the queue ○ waits for its turn to be processed ○ queueing time can be estimated 1/(1-p) where p is the utilization ○ tradeoff? utilization will not reach 100% ○ what happens when there is congestion? packets are dropped 18 Computer Systems Engineering Computer Networks Packet Loss (scenario 1) 19 Computer Systems Engineering Computer Networks Packet Loss (scenario 2) 20 Computer Systems Engineering Computer Networks Packet Loss (scenario 2) How to deal with duplicates? ○ idempotent functions ○ detecting duplicates nounces 21 Computer Systems Engineering Computer Networks Packet Loss (scenario 3) 22 Computer Systems Engineering Computer Networks Packet Reordering 4 23 Computer Systems Engineering Computer Networks Packet Reordering How to deal with packet reordering? ○ for all packages between A and B to follow the same route ○ keep track of packet ordering delay packets until all expected packets arrive 24 Computer Systems Engineering Operating Systems Summary 25 Computer Systems Engineering Operating Systems Summary 26 Computer Systems Engineering Operating Systems Where to go now? Networks (book reference: Sections 7.1 to 7.7) ○ Network Layers 27 Computer Systems Engineering  Computer Systems Engineering Computer Networks (part II) Rodrigo Bruno 1 Computer Networks Recap! Fundamental physical properties of networks ○ speed of light (limited latency) ○ communication over hostile environments ○ limited bandwidth ○ high cost, not in line with technological advances 2 Computer Systems Engineering Computer Networks Recap! Synchronous network ○ advantages? Asynchronous network ○ packet ○ forward ○ route ○ queueing max utilization? ○ duplicates ○ packet order 3 Computer Systems Engineering Computer Networks For today! Computer Networks (part II)! ○ Network Protocols ○ Network Layers ○ Internet 4 Computer Systems Engineering Computer Networks Network Protocols fire(nmissiles, target, action_if_defended) Conventions/specifications Local Procedure Call def fire(nmissiles, where, reaction): … fire(nmissiles, target,action_if_defended) Network Protocols Remote Procedure Call def fire(nmissiles, where,reaction) 5 Computer Systems Engineering Computer Networks Network Protocols Can these subs be automated? 6 Computer Systems Engineering Computer Networks Protocol Layers 7 Computer Systems Engineering Computer Networks Protocol Layers 8 Computer Systems Engineering Computer Networks Protocol Layers 9 Computer Systems Engineering Computer Networks Why layers? 10 Computer Systems Engineering Computer Networks End-to-End Layer Networks Protocol Layers Link layer (hardware): Network Layer ○ moves data from one device to another ○ deals with frames Link Layer Network layer (hardware) ○ moves data across multiple devices (forwarding) ○ deals with packets End-to-End layer (software) ○ “door to door” communication (application to application) ○ deals with messages 11 Computer Systems Engineering Computer Networks Link Layer What if there are multiple computers? 12 Computer Systems Engineering Computer Networks Link Layer (MAC and CAM table) 13 Computer Systems Engineering Computer Networks Link Layer (switch + ethernet cable) 14 Computer Systems Engineering Computer Networks Network Layer 15 Computer Systems Engineering Computer Networks Routers need to know all IP? Network Layer (routing across networks) 16 Computer Systems Engineering Computer Networks What is the maximum number of IPs? Network Layer (routing tables) CIDR (Classless Inter-Domain Routing) Network: 10.11.0.0/16 |< Network Bits (16)>| 00001010.00001011.|00000000.00000000 First address: 10.11.0.1 00001010.00001011.|00000000.00000001 Last address: 10.11.255.254 00001010.00001011.|11111111.11111110 17 Computer Systems Engineering Computer Networks Network Address Translation (NAT) Source: wikipedia.org 18 Computer Systems Engineering Computer Networks Network Layer (routers) 19 Computer Systems Engineering Computer Networks End-to-End Layer 20 Computer Systems Engineering Computer Networks End-to-End Layer (services) deal with lost packets, out-of-order packets divide packets and reassemble segments setting up client-server connections encryption compression encoding … 21 Computer Systems Engineering Computer Networks Open Systems Application Layer Interconnection (OSI) Presentation Layer Layers Software Layers Session Layer Transport Layer Network Layer Hardware Layers Data Link Layer Physical Layer 22 Computer Systems Engineering Computer Networks Open Systems Application Layer HTTP, FTP, SSH, etc Interconnection (OSI) Encoding, compression Presentation Layer encryption/decryption, etc Layers Session Layer Communication Sessions Reliable communication (TCP) Transport Layer Multi-network communication (IP) Network Layer Frames between two nodes Data Link Layer Bits over a physical medium Physical Layer 23 Computer Systems Engineering Computer Networks Internet Map 24 Computer Systems Engineering Computer Networks Internet Traffic 25 Computer Systems Engineering Computer Networks Internet Backbone 26 Computer Systems Engineering Computer Networks Tracing Internet Routes rbruno@elara~> traceroute -q 1 tecnico.ulisboa.pt traceroute to tecnico.ulisboa.pt (193.136.128.169), 30 hops max, 60 byte packets 1 vodafonegw (192.168.1.1) 1.267 ms 2 3.96.54.77.rev.vodafone.pt (77.54.96.3) 8.566 ms 3 107.41.30.213.rev.vodafone.pt (213.30.41.107) 12.877 ms 4 Router6.Lisboa.fccn.pt (193.136.250.10) 13.490 ms 5 Router30.Lisboa.fccn.pt (194.210.6.104) 13.797 ms 10 hops! 6 Router61.Lisboa.fccn.pt (194.210.6.209) 15.828 ms 7 ULisboa-IST.Lisboa.fccn.pt (193.136.1.94) 16.190 ms 8 e1.gatekeeper1.tecnico.ulisboa.pt (194.117.12.133) 16.167 ms 9 irb-2.sw-dc1-edge2.tecnico.ulisboa.pt (193.136.134.170) 18.902 ms 10 proxy-lb.ist.utl.pt (193.136.128.169) 13.716 ms 27 Computer Systems Engineering Computer Networks Domain Name Service rbruno@elara~> nslookup tecnico.ulisboa.pt Server: 146.193.41.2 Address: 146.193.41.2#53 Non-authoritative answer: Name: tecnico.ulisboa.pt Address: 193.136.128.169 Name: tecnico.ulisboa.pt Address: 2001:690:2100:1::c03a:216e 28 Computer Systems Engineering Operating Systems Summary Organization of computer networks in layers ○ link layer ○ network layer ○ end-to-end layer Internet 29 Computer Systems Engineering Operating Systems Where to go now? Cloud Computing! ○ Virtual Machines ○ Containers ○ Functions ○ AWS EC2 30 Computer Systems Engineering