CPS 196, Duke University: Systems and Networks

Disclaimer: This topic list is a superset of what we will cover in this class. It is wildly optimistic and will evolve.

Topic	ppt	pdf	pdf6
Course introduction.
Slides for course introduction
Physical machines and privileged mode. Review of instruction set architecture (ISA) features to support virtualization and protected resource sharing: protected mode, address space, context. Machine event handling: traps, faults, interrupts. Use of protected features by operating system kernels (OS supervisors). Importance of common machine model and ISA standards, and ABI. See more about this topic Patterson and Hennessy: section 7.4.
Slides for: Physical machines, privileged mode, address spaces
Classical OS structure and Unix. Kernel abstractions and system calls: processes and IPC, file systems, time management, and event handling. Process states and blocking I/O. The Unix operating system: fork, exec, pipes, signals, etc. See more about this topic [Ritchie78] The Unix Time-Sharing System, by D. M. Ritchie and K. Thompson, Bell Systems Technical Journal, July 1978. [WIB] Worse is Better, by Richard Gabriel. Unix philosophy
Slides for: Classical OS structure and Unix
Virtual machines. Motivation for virtual machines. Machine virtualization and virtual machine models: VMware, Xen, Java, C#. Architectural alternatives for virtual machines and isolation: virtualization vs. paravirtualization. How a kernel or virtual machine hypervisor uses privileged instructions to virtualize a physical machine. Cost of virtualization and isolation. Challenges of virtualization: devices, time, virtual-physical-real mapping, privileged instructions in user mode. The Xen hypervisor and its interactions with the operating system above and the hardware below. How to use Xen. (Discussion: operating systems as guest applications, virtualization in hypervisor vs. in the operating system itself, hosting markets, PlanetLab, VM innovation such as migration/ISR and replay.) [SmithNair05] The Architecture of Virtual Machines, by J.E. Smith and Ravi Nair. IEEE Computer, May 2005. [local pdf] [Intel05] Intel virtualization technology, by Uhlig, R.; Neiger, G.; Rodgers, D.; Santoni, A.L.; Martins, F.C.M.; Anderson, A.V.; Bennett, S.M.; Kagi, A.; Leung, F.H.; Smith, L. IEEE Computer, May 2005. [local pdf] [Barham03] Xen and the Art of Virtualization, by Paul Barham and his Cambridge buddies. ACM Symposium on Operating System Principles, October, 2003. [SK] chapter 5 (skip material related to threads)
Slides for: Virtual machines
Internet naming and addressing. Global vs. local name spaces. Uniformity vs. local control and customization. The role of hierarchy in scale and administrative control. Internet naming and addressing: domain names and the Domains Name Service, IP addresses, and LAN/Ethernet (MAC) addresses. Standards, interoperability, and Internet governance.
Slides for: Internet naming and addressing
Networking and the Internet. Packet flow and router structure, queueing, and bottlenecks.
Client/server networking and sockets. Unix/Java networking: sockets, stream vs. datagram communication, connections, ports. Rudimentary HTTP, Web servers and Web application servers. [SK] section 4A for material on client/server
Slides for: Client/server networking and sockets
Server structure, concurrency, and performance. Server blocking and its impact on performance, concurrency models: events, threads, processes. Introduction to performance and queuing behavior: arrivals, throughput and response time, queue length, Little's Law. Server overload, admission control, server clusters, distributed services. [SK] section 6A for material on server performance and overload
Slides for: server structure, concurrency, and performance
Threads and synchronization. Java synchronization: mutexes and condition variables. Synchronization alternatives: semaphores. OS kernel synchronization: blocking, interrupts, atomic instructions and spinlocks. [SK] section 5A for material on threads [Birrell89] An Introduction to Programming with Threads, by Andrew Birrell, January 1989. This paper uses Modula, which may be syntactically different from languages you are familiar with, but the fundamentals are the same. The Birrell paper demands some reflection but it is well worth the time.
Slides for: concurrency and synchronization
Scheduling. Process/thread scheduling, batch/interactive, impact of I/O. Overview of real-time scheduling and continuous media: the problem of jitter, and streaming vs. on-demand media. Service quality, reservations, and proportional share scheduling.
Slides for: basic scheduling
Network protocols. Overview of protocols focusing on reliable and secure stream communication on the Internet: TCP. Fundamentals of TCP implementation: checksums, sequence numbers, ordering and duplicate suppression, flow control. The problem of congestion: the Internet's end-to-end congestion control architecture and the threat of congestion collapse.
Slides for: TCP and congestion.
Secure communication. Fundamentals of secure communication: properties of symmetric and asymmetric cryptosystems, digital signatures, certificates, public key infrastructure (PKI). Secure socket layer (SSL) protocol: certificate exchange, session key exchange, secure HTTP, ssh. The end-to-end principle. Authorization: capabilities and access control lists.
Slides for: secure communication.
Slides for: end-to-end argument.
File systems and NFS. Fundamentals of Unix file system implementation: vnodes, inodes, blocks, block maps, directories. Kernel extensibility: device drivers, file system drivers, mounting. Introduction to the Network File System: remote procedure call (RPC) and NFS protocol operations. Caching and the problem of consistency. Covered in less detail or discussed briefly: Failures and failure model in NFS. File system recovery. Failure atomicity: logging and shadowing. Disk striping and mirroring, error correction, and RAID. RAID performance issues: small writes and hot spots. Implementation of Network Appliance filers: WAFL and NVRAM.
Slides for: file systems and NFS.
Distributed systems. We spent a couple of classes on distributed systems topics sampling from the intended lists of topics below.
Slides for: Distributed consensus.
Slides for: Large-scale distributed systems.
Distributed systems. Discussed in passing. Byzantine vs. fail-stop failures, failure detection, group membership, basic consensus results. The fundamental choice of consistency vs. availability in a world with network partitions. Approaches to cache consistency in file systems, DNS, and the Web: polling, callbacks, time-to-live, and leases. Replication and quorum voting. Distributed Hash Tables. The Google service architecture.
Storage cache management. Discussed in passing. Block caching: prefetching, clustering, delayed writes, seek scheduling. Block/page cache replacement: LRU, LFU, and approximations. Interaction with disk layout and disk performance.
Internet infrastructure and vulnerability. Discussed in passing. Security threats and the mechanisms to deal with them: denial of service, viruses, worms, phishing, firewalls, malicious or misconfigured routers, snoopers, man-in-middle, spyware, promiscuous hosts, wireless/WEP. Robustness of the Internet to physical attack: dynamic routing, Internet topology, scale-free networks. (one class)
Internet computing. Discussed in passing. Models for resource sharing: hosting utilities, grids, peer-to-peer systems, file sharing. Example: Cereus utility leasing service. Administrative domains, trust management, and failure issues. PlanetLab and network overlays. Content distribution, multicast, and large-scale services. (one class)
Pervasive and embedded computing. Not covered. Platforms and abstractions for pervasive, mobile, ubiquitous, embedded. What can we give up? What new problems must we address? Power management, user interfaces, programmability, disconnected operation, failure handling.