While Computer Systems Engineering should be a course I’m excited for, this has been a course I’ve been somewhat dreading as it seems to have the least straightforward way of approaching it on MIT OpenCourseWare. Searching for it normally shows a version from 2018, however this only contains lecture slides and very scarce notes from the lectures. There are archived versions of the course from 2005 and 2009 which contain more detailed notes and most of the lectures. The text course is also split up with only the second half available on Open CourseWare and only the first half is published as a book which I ordered from Amazon. Luckly, while the first couple of lectures were pretty light on details, they mostly contained information seen before in Software Construction and Computation Structures, and further lectures had enough details that the 2018 version of the course felt about as complete as the other lectures even without the videos themselves.
This course feels like a natural follow up from Computation Structures and starts off talking more about operating systems, client-server communication and buffers and threads before moving into networking, security, fault tolerance and distributed systems. Computer Systems Engineering covers a broad scope of topics with lectures on DNS, TLS, Bitcoin and Tor as well as a lot more and ends by recommending a large list of follow up courses. With this being the 11th course in this series, I did start to see some algorithms and topics rehashed from other courses such as Software Construction and Computation Structures, but it still mostly had new content and mostly information on topics and concepts I’d previously heard of but hadn’t gone into depth on. If computation structures was everything that went into building a single machine, this is probably the equivalent for networks and distributed systems.
MIT Courses #11: Computation Structures – 6.033 by Dr. Katrina LaCurts
Lecture 1 – Coping with Complexity
The slides for this focus on systems, complexity, modularity and abstraction and how to enforce modularity with client/server models. A system is defined as a set of interconnected components with an expected behavior observed at the interface with its environment. Complexity makes building systems difficult and systems today are incredibly complex with Facebook or Windows Vista having way more lines of code than a pacemaker or space shuttle. Complexity limits what can be built and causes a number of unforeseen issues. Modularity and abstraction can help mitigate complexity. The client/server model is a way of enforcing modularity, where a client machine makes a request and receives a reply from a server. The two modules reside on different machines and communicate with RPCs (remote procedure calls), though network and server failures are still issues.
Lecture 2 – Naming in Systems
The second lecture slides focus on naming in systems with a focus on DNS. Examples of names are hostnames (ex.com), email addresses, usernames, register names (R0), function names, class names, file paths, URLs, phone numbers and IP addresses. To help with using names, a lookup algorithm should translate a name into its associated value. An example of this is a domain name system, where hostnames are translated to IP addresses (ex. web.mit.edu to 18.9.22.69). With this, your computer knows where to send data while the user can remember a meaningful name. Naming is what lets modules such as clients and servers communicate. In DNS a single value can have multiple names. An example of the DNS hierarchy is shown though it likely needs some more explanation (I think something similar was shown in Software Construction).
Lecture 3 – Operating Systems and Virtual Memory
The third lecture slides talk about operating operating systems and virtual memory. Operating systems are used to enforce modularity on a single machine. To enforce modularity and build an effective operating system, programs shouldn’t be able to refer to and corrupt each other’s memory. Programs should be able to communicate and share a CPU without one program halting the progress on the others. Operating systems enforce modularity on a single machine with virtualization. Memory is virtualized so programs can’t refer to or corrupt each other’s memory. Programs communicate with virtualized communication links and share a CPU without stopping other programs’ progress by virtualizing processors. The focus of this lecture is virtualizing memory so programs can’t refer to each other’s memory. If two CPU’s used for different programs simply access data in main memory, there can be problems as there aren’t boundaries. A MMU can be added to translate virtual addresses to physical ones for the specific program. A simple method could be to store every mapping with virtual addresses acting as an index to the MMU table, though this can require large amounts of space to store the table. Page tables can be used to help this process. One page is typically 212 bits of memory and mapping to pages in memory is a better system, taking much less space. For instance, 232 entries at 32 bits per entry would take 16GB to store, while 220 entries would only take 4MB in this case. Page table entries are 32 bits as they contain a 20-bit physical page number and 12 bits of additional information. A present bit asks if the page is in DRAM, a read/write bit which states if the program is allowed to write to the address, and a user/supervisor bit which says if the program can access the address. A space efficient mapping maps to pages in memory which is better, though 4MB is still a bit of space, which can be improved by paging the page table. The kernel manages page faults and interrupts. Operating systems also give abstractions for devices via system calls, implemented by interrupts, where the kernel accesses devices directly, as opposed to the user. A linked reading discusses the implementation of UNIX. http://people.eecs.berkeley.edu/~brewer/cs262/unix.pdf
Lecture 4 – Bounded Buffers and Locks
To enforce modularity and build an effective operating system with virtualization, bounded buffers can help so programs can communicate by virtualizing communication links. For today, it’s assumed only one program is used per CPU. A bounded buffer is a buffer that stores up to N messages and has an API with send and receive commands which take the size and number of messages in the buffer into consideration. Locks allow only one CPU to be inside a piece of code at a time, with a lock API with acquire and release functions and send and receive need to acquire and receive the lock to avoid a deadlock and make sure there’s space in the buffer. Bounded buffers allow programs to communicate but are tricky to implement due to concurrency. Locks allow for atomic actions and a proper locking discipline is required to handle race conditions, deadlock, and performance issues.
Lecture 5 – Threads
To handle the problems of programs being able to share a CPU without one program halting the progress of others, threads can be used to virtualize processors. An example thread API has a suspend method which saves the state of the current thread to memory and a resume method for restoring a state from memory. A yield function is added which acquires the lock, suspends the current thread, choosing a new thread and resuming the new thread, before releasing the lock. Send calls yield before.
Example code for send is
send(bb, message):
acquire(bb.lock)
while bb.in - bb.out == N:
release(bb.lock)
yield()
acquire(bb.lock)
bb.buf[bb.in mod N] <- message
bb.in <- bb.in + 1
release(bb.lock)
return
And yield code is
yield():
acquire(t_lock)
id = cpus[CPU].thread
threads[id].state = RUNNABLE
threads[id].sp = SP
threads[id].ptr = PTR
do:
id = (id + 1) mod N
while threads[id].state != RUNNABLE
SP = threads[id].sp
PTR = threads[id].prt
threads[id].state = RUNNING
cpus[CPU].thread = id
release(t_lock)
Condition variables let threads wait for events and get notified when they occur with a condition variable API having wait and notify functions which take an input of cv, with wait taking a lock as well. Wait yields the processor, releases the lock and waits to be notified of the cv. Notify notifies waiting threads of the cv. Send can be altered to replace the release, yield and acquire (in the while loop) with wait(bb.not_full, bb.lock) and notify(bb.not_empty) before the return statement.
wait(cv, lock):
acquire(t_lock)
release(lock)
id = cpus[CPU].thread
threads[id].cv = cv
threads[id].state = WAITING
yield_wait()
release(t_lock)
acquire(lock)
notify(cv):
acquire(cv):
for id = 0 to N-1:
if threads[id].cv == cv && threads[id].state == WAITING:
threads[id].state = RUNNABLE
release(t_lock)
yield_wait():
id = cpus[CPU].thread
threads[id].sp = SP
threads[id].ptr = PTR
SP = cpus[CPU].stack
do:
id = (id + 1) mod N
release(t_lock)
acquire(t_lock)
while threads[id].state != RUNNABLE
SP = threads[id].sp
PTR = threads[id].ptr
threads[id].state = RUNNING
cpus[CPU].thread = id
Preemption can be used to forcibly interrupt threads with timer_interrupt function.
timer_interrupt():
push PC
push registers
yield()
pop registers
pop PC
Though, this shouldn’t be called while yield or yield_wait is running, and interrupts can be disabled then using hardware. In summary, threads can virtualize a processor so it can be shared across programs. Yield allows the kernel to suspend the current thread and resume another. Preemption is useful for interrupting threads without relying on programmers to correctly use yield, though they require a special interrupt and hardware support to disable other interrupts.
Lecture 6 – Operating Systems Structure and Virtual Machines
This lecture focuses on running multiple OSes at once and dealing with kernel bugs. With virtual machines, virtual machines running guest operating systems can run on top of the same physical hardware (or another VM). To safely share access to physical hardware, they run on a VMM or virtual machine monitor that’s on top of the physical hardware. The goal of the VMM is to virtualize hardware. PTR and page tables are set on both virtual hardware and separate ones on the physical hardware. The guest’s virtual address in the guest OS is mapped to the guest’s physical address running in the virtual hardware which the VMM maps to the host’s physical address. The guest OS loads the PTR from the virtual hardware which the VMM intercepts. The guest OS page table and VMM page table lead to the host’s page table. In modern hardware, the physical hardware is aware of both page tables and performs the translation from virtual to host physical by itself. In monolithic kernels, no modularity is enforced in the kernel itself. The application interacts with basic interprocess communication, virtual memory, file servers, device drivers, network, etcetera on top of the hardware. Microkernels are used to enforce modularity by putting subsystems in user programs (such as the application IPC, device driver, and network, etc). Redesigning monolithic kernels as microkernels is a challenging process. Each virtual machine also has its own U/K bit.
Lecture 7 – Performance
You can improve performance of a system by measuring the system to find its bottleneck and relax it. Latency is the amount of time for a single request and throughput is the number of requests over a unit of time. As the system becomes heavily loaded, high latency occurs and a system can have its requests queue up and throughput plateaus can occur when the system can’t serve requests faster. To relax the bottleneck, you could batch requests, cache data, or use concurrency or parallelism for improvements. Performance requirements influence a systems design. Better algorithms can also help where applicable. Given that Moore’s law is plateauing and different improvements happen at different paces, replacing hardware may not be enough. Caching is good when all data fits in the cache and there is temporal or spatial capacity. LRU is a popular eviction policy. Concurrency and schedule can improve performance by using different orders of execution, though there isn’t a single right answer to scheduling. Batching is based on how the disk access works. Parallelism is the idea of having multiple disks and accessing them in parallel, but depends on how data is divided across them. In the case of many requests for small files, the bottleneck is data seeks. Put each file on a single disk and allow multiple disks to seek multiple records in parallel. On the other hand, if you need a few large reads and are limited by sequential throughput, you can stripe files across disks. Caching is useful regardless of HDD or SSD.
HDDs (magnetic disks) work with several platters on a rotating axle. Platters have circular tracks on either side which are divided into sectors. A cylinder is a group of aligned tracks. The disk arm has a head for each surface, all moving together. Each head reads and writes sectors as they rotate past and the size of a sector is a unit of its read/write operation (typically 512B). To read/write, move the arm to the desired track, wait for the platter to rotate the desired sector under the head and read/write as the platter rotates. SSDs, on the other hand, are organized into cells, each holding one (or 2 or 3) bits. Cells are organized into pages and pages into blocks. Reads happen at page level and writes happen at page level only to new pages with no pages being overwritten. Erases and overwrites are at block level and it takes a high voltage to erase. Read and write can be time consuming on HDD and flash or SSDs would help if available. Avoiding random access and doing long sequential reads where possible can help. Laying out big files contiguously on the disk and grouping small related pieces of data can help with this.
Lecture 8 – Introduction to Networking
This lecture focuses on how networks work since they’re the source of many failures in systems. Networks are modeled as graphs with endpoints on the outskirts and switches in the middle. An edge is a direct connection between two nodes that could be a wire. Problems in networks are addressing, naming, routing and transport. For small networks, naming/addressing is solved by assigning a unique name to each node. The problem of routing is “how do nodes figure out to get data to other nodes?” One problem with transport is reliability and another is what to do when a packet gets dropped. The internet isn’t a normal network. The launch of Sputnik led to the creation of ARPA/DARPA and in the 1970’s ARPAnet was created, starting small and combining addressing and transport. It grew by connected existing networks. In 1978, the internet was made more flexible with the typical seven layered model. Layer 1 is physical, layer 2 is link (point to point links), layer 3 is Network – IP, with addressing and routing. Layer 4 is the transport layer with delivery. Layers 5 and 6 are session and presentation and layer 7 is the application layer. This course mostly cares about the application, transport, network and link layers. Layering can be useful for switching out protocols. TCP was introduced around 1983, providing reliable transport removing the need for apps to reimplement reliable delivery. Between 1978 and 1979, link-state routing and EGP came out providing more scalable routing and DNS came in 1982 for scalable naming and growth through distributed management. Growth led to problems with congestion collapse in the mid 80’s where many packets were in the network but none were useful, leading to a congestion control mechanism in TCP. In the early 90’s, policy routing came along, the internet was becoming commercialized and policy routing such as BGP was a result. Addressees were assigned in chunks of different sizes, typically class B chunks of 65K, until we ran out. The CIDR protocol was developed to divide those up. Changing addresses meant changing switches as all switches were made by cisco and forwarding was done in software. With the commercialization, in 1993, changes came to a stop.
In the current day, there are still lots of problems with the internet due to its design and lack of upgrades. One issue is DDoS, done by sending a lot of traffic to a single machine to consume its resources, which is hard to present as the internet was designed with accountability in mind. It wasn’t designed for security or mobility either and address space depletion led to the switch from IPv4 to IPv6. Congestion control is another area that likely needs change. In terms of new features, there are a lot of new uses of the internet such as P2P, wireless, mobile, streaming, cloud computing, datacenter networks and security threats and defenses. Almost everything happens on the internet, though more changes are expected as time goes on.
Lecture 9 – Routing
Link-state and distance-vector are different routing protocols, though neither is used to route across the entire internet. The goal of a routing protocol is for every node X, after the protocol runs, X’s routing table should contain a minimum-cost route to every other reachable node. A path is the full path that packets will travel on while a route is the first hop of that path. Nodes only need to know the first hop. Link costs can represent factors such as delay or congestion. Sometimes all costs are 1 and the minimum cost path is the one with the fewest hops. Link costs can also change. Once a routing table is set up, when a switch gets a packet, it can check the packet header for the destination address, look it up in the routing table and add the packet to the queue for the outgoing link. Distributed routing protocols scale better than centralized ones and have three steps. First, nodes learn about their neighbors via the HELLO protocol. Then nodes, learn about other reachable nodes via advertisements. Lastly, nodes determine minimum cost rules. All of the steps happen periodically, letting routing protocols adapt as link costs change and as advertisements get lost, and links and nodes fail. The HELLO protocol lets nodes discover node and link failures.
Link-state routing is based on the idea that through advertisements, nodes disseminate information about the topology of the graph to all other nodes. Once all nodes have that information, they can run a shortest path algorithm. Each node’s advertisement is a list of its neighbors and its link cost to them. Each node sends advertisements to their neighbors who forward them on. Advertisements are “flooded” and each node gets a complete map of the network (except for rare cases of advertisement loss) and use this to run Dijkstra’s shortest path algorithm. One way to do Dijkstra’s algorithm, assuming all nodes are known, keeps track of W, the set of not-yet processed nodes in each step. Initially, W is all nodes in the network. Current costs and routes to all nodes are also tracked. Initially, routing_table[self]=Self; routing_table[any_else] = ?, cost_table[self]=0 and cost_table[anyone_else] = infinity. Then while W isn’t empty, remove the node with the minimum cost so far, u, from W. For each of it’s neighbors,
d = cost_table[u] + cost(u,v)
if d < cost_table[v]
cost_table[v]=d
routing_table[v] = routing_table[u]
Flooding makes link-state routing robust to failure but has a high overhead, with around 2NL advertisements given N nodes and L links.
While link-state routing’s nodes calculate full shortest paths, they only need the first hop to a destination. Distance-vector routing exploits that. Each node’s advertisement is a list of all nodes it knows of and their current costs. This starts as [(self, 0)]. When a node receives an advertisement from its neighbor, it will be a list of destination/cost pairs, each representing the cost of the sending node to the destination. For each pair in the advertisement, the receiving node checks if it already uses the sending node to get to the destination and if it is, updates the cost information. If not, it checks if the sending node provides a better path and updates its cost and routing information accordingly. The overhead is much better as it only needs 2L advertisements, but a problem arises from counting to infinity. When node A has no route to destination B, it advertises a cost of infinity to B. Infinity must be larger than the longest path in the network, but can cause the nodes to to think there’s a path when there isn’t, which leads to an infinitely long process trying to find it. A split-horizon strategy can help mitigate against this in some cases, by not sending advertisements about a route to the node providing the route. Overall, link-state is easy to reason about failures but doesn’t scale well while it’s easier to scale distance-vector routing but harder to figure out failures. Unfortunately, neither can scale to the size of the internet.
Lecture 10 – Networking: Routing (BGP)
This lecture focuses on routing and addressing. The next few sections take a look at three questions about the “internet of problems.” This week looks at how to route and address in a scalable way, while dealing with issues of policy and economy and the solution of BGP. The other questions are how to transport data scalably and deal with varying application demands and how to adapt new applications and technologies to an inflexible architecture. The internet’s enormous growth led to routing protocols designed to scale and enforce policy. Three tools for dealing with scale are path-vector routing, routing hierarchies and topological addressing. Path-vector routing is similar to distance-vector routing but includes the full path in routing advertisements. The overhead increases but convergence time decreases and avoids counting to infinity. This still has a lower overhead than link-state routing. With a routing hierarchy, the internet is divided into autonomous systems (ASes), which can be universities, ISPs, government branches and more. Each AS has a unique ID known as its AS number and there are tens of thousands of ASes. A routing protocol is used to route across ASes and a different protocol is used to route within them. There are devices on the edge of each to translate between protocols. BGP is the path vector protocol used across ASes. Despite being between Ases, BGP routes to IP addresses (ex. 18.0.0.1 instead of AS3). Topological addressing gives addresses to ASes in contiguous blocks so they can be specified with CIDR notation. This keeps advertisements smaller than they would be otherwise.
ASes make use of policy routing where switches make routing decisions based on a set of policies. The routing protocol needs enough information to enable those policies. ASes don’t want to send traffic on a path without financial incentive to do so in BGP. One way of enforcing this is with selective advertisements where AS1 doesn’t tell AS2 about a path unless it makes money by letting AS2 use the path. Each AS will have a different view of the network which won’t contain every link. A typical BGP relationship has a customer and provider where customers pay for transit provided by the provider. Peers provide mutual access to a subset of each other’s routing tables, specifically the subset containing their transit customers. Peering can save money and improve performance and may be the only way to connect customers to part of the internet. BGP relationships lead to BGP export policies. An AS’s export policies determine which routes to advertise. Providers export its customer’s routes to everyone and a customer exports its provider’s routes to its customers. Since the customer is paying for the internet, the provider should give them routes to as many destinations as possible and allow other parts of the network to reach its customers. AS exports only customer routes to peers instead of the full table as the peers aren’t paying it for transit. Almost every AS is a customer of someone else. Small ASes typically buy internet from tier-3 ISPs, which buy from tier-2, which buy from tier-1 ISPS, which are huge and there are only 10-15. All tier-1 ISPs peer with each other so they can provide global connectivity.
If an AS hears of a route to X from multiple neighbors it will use import policies to decide where to go. For BGP import policies, the first goal is to make money, preferring routes via customers to routes via peers to routes on providers. Money is made on customers and lost on providers. In the case of a tie, a common tactic is based on AS-hop-count, though each AS sets its own policies. With distributed routing, the HELLO protocol is used and BGP sends KEEPALIVE messages to neighbors. Advertisements sent to neighbors look different depending on the neighbor. BGP runs on TCP, which is a reliable transport protocol, and doesn’t have to do periodic advertisements to handle failure, pushing them when routes change insteads. Routes can be explicitly withdrawn in BGP on failure and routing loops are avoided as BGP is a path-vector algorithm. While BGP works well on the internet, it’s routing tables are getting big and exceeding the amount of memory dedicated to the table in some switches. Route instability can occur due to misconfigurations or conflicting AS policies. Route-flap damping ignores advertisements about frequently changing routes to help with this, but increases convergence times. ASes can be “multi-home” by buying internet from multiple ISPs, usually for back-up or load balancing, which causes bigger routing tables. An AS has multiple BGP routers on its edge and a protocol called iBGP keeps them in sync. iBGP requires AS’s BGP routers to be connected in a complete graph and doesn’t scale well. BGP isn’t secure and ASes can advertise prefixes they don’t own. DNS has a similar problem. There’s a lot of room for operator error due to complexity of setting policies. While the protocol is simple and BGP provides a means for autonomous systems to do policy routing, how it works in practice is complex due to competing economic interests and other factors. The internet has grown enough that BGP’s scalability is a concern.
Lecture 11 – Transport Layer
Last lecture was about scalable routing while this week is about transport scalability with diverse application needs. The goals of reliable transport and preventing congestion and achieving these scalably and sharing the network. This lecture focuses on TCP congestion control, specifically on the “New Reno” version of TCP. Reliable transport can be achieved with a sliding-window protocol. The receiving application gets a complete, in-order byte stream from the sender and one copy of every packet in order. This is desirable since networks are unreliable and packets can get dropped or arrive out-of-order. With the sliding-window protocol, each data packer gets a sequence number. The sender has W outstanding packets at any given time where W is the window size. What’s the correct value for W? Too small leaves an underutilized network while too large leads to congestion. When the receiver gets a packet, it sends ACK back, where ACKs are cumulative. An ACK for X means it’s received all packets up to and including X. If the sender doesn’t receive an ACK saying X was received then it will wait for a timeout before retransmitting X. X or its ACK could have been lost. The timeout is proportional to, but larger than the RTT of the path between the sender and receiver. At the receiver, a buffer is used to avoid delivering packets out of order and the last packet delivered is kept track of to avoid duplicates.
Congestion control is the idea of controlling source rate to achieve high performance. The goals are efficiency and fairness, minimizing drops and delay and maximizing utilization. Bandwidth should be shared fairly among all connections using the network. For now, all senders are assumed to have infinite offered load with fairness meaning bandwidth is equally split. No senders know how many other senders there are, which can change over time. Window-based congestion control is used, where switches are dumb and can only drop packets and senders are smart. Packet drops are a signal for congestion in the network which senders can react to. Every RTT, if there’s no loss, W=W+1 and if there is, W=W/2. This is AIMD, additive increase multiplicative decrease. Senders constantly readjust, changing the number of senders or offered loads. AIMD is safe since senders are hesitant to increase and scale back quickly with congestion, as well as efficient and fair.
If offered loads are finite, the process changes. For instance, if S1 and S2 have offered loads of 1Mb/s, S3 has an offered load of .5MB/s and they share a bottle neck with a capacity of 2Mb/s, in theory, S3 will stop increasing once its sending .5Mb/s, while S1 and S2 will increase up to .75Mb/s. This achieves “max-min fairness,” though in practice a sender could have a much longer RTT and not increase its window at the same rate. TCP’s congestion control utilizes the network reasonably well, but fairness is hard to measure or claim to be achieved with variance present. A slow start could be used to decrease the time taken for the initial window to ramp up by exponentially increasing the window at the beginning of the connection. This could mean doubling it every RTT until there’s loss. Another mechanism is fast retransmit or fast recovery can be used where when a sender receives an ACK with sequence number X and then 3 duplicates, it immediately retransmits X+1, as ACKs are cumulative. On fast-retransmit, the window decrease is still W=W/2 and when a packet is lost due to timeout, TCP sets W to 1, then does a slow-start until the last good window and starts an additive increase. If there’s a retransmission due to timeout, then there is significant loss in the network and senders should back off. Overall, TCP is a massive success requiring no changes to the internet’s infrastructure and is something endpoints can opt-in to, letting the network be shared among different users with different and changing types of traffic in a distributed manner. TCP provides reliable transport and congestion control. Senders increase their window additively until they experience loss and backoff multiplicatively, and can use slow-start and fast-retransmit/fast-recovery to increase the window and recover from loss. Unfortunately, senders don’t react to congestion until it’s already happening and queues are already full.
Lecture 12 – In-Network Resource Management
While TCP congestion control is a massive success overall as it helps prevent congestion in a distributed manner, it has some drawbacks. It can result in long delays if routers have too much buffering and doesn’t react to congestion until queues are full. Full queues lead to long delays, though queues are needed to absorb bursts. The goal is to have transient queues instead of persistent queues. If packets are dropped before queues are full, then TCP senders will back off before congestion gets too bad. “Drop tail” is the original queue management scheme. When a packet arrives, it’s dropped when the queue is full and enqueued otherwise. One positive is that drop tail is simple, only dropping packets when it needs to, though a dropped packet means retransmission which wastes resources. Drop tail synchronizes sources. For instance, if a source sends a burst of traffic “x x x x”, the queue will drop the three packets at the tail and the sender will likely timeout, dropping its window to 1. If multiple senders do this, all sources’ bursts will lead to packets dropped from all. All sources will throttle back, sources increase and the cycle repeats. Flow synchronization means decreased utilization, which is a drawback. Drop tail is unfortunately not very fair, tends to result in mostly full queues and is bad for bursty traffic.
An active queue management scheme is called RED. Packets are dropped before the queue is full to give senders an early signal. This requires a measure for the average queue size, q_avg = a*q_instant + (1-a)*q_avg where a is greater than zero and below 1. RED drops packets with probability p where p is 0 when q_avg <= min_q, p increases linearly when q_avg is greater than min_q and at most max_q and 1 when q_avg is greater than max_q. With RED, queue length doesn’t oscillate as much as q_avg is a low-pass filter. There’s smooth change in drop rate with congestion, as q_avg increases, so does p, keeping q_avg stable. Flows are desynchronized, spreading drops out. Unfortunately, RED still drops packets. ECN is a scheme like RED, but where packets are marked instead of dropping them. To mark a packet, a bit in its header is set to 1 and sources learn about congestion by marked ACKs. While this seems good, sources have to know how to do this. They know how to react to packet drops but not to marks. The advantages of RED and ECN vs DropTail are that their smaller persistent queues lead to smaller delays, have less dramatic queue oscillation and are less biased against bursty traffic. RED and ECN’s disadvantages are that they are more complex, it can be hard to pick parameters such as q_min and q_max, as the right parameters depend on flows, bottleneck, and more. Bad parameters make things worse. Neither RED nor ECN are the final word on active queue management.
Traffic differentiation is the idea of putting different types of traffic in different queues and using custom logic accordingly. Delay-based scheduling and priority queues can be used to prioritize certain traffic such as latency-sensitive traffic. Two or more queues are used and the prioritized queue is served if it has a packet, otherwise another queue is served. Asking what queue to send a packet form is the problem of scheduling, compared to queue management which asks when to drop or mark packets in a single queue. The lingering problem is a lot of traffic in a priority queue can starve out the traffic in other queues. Another idea is bandwidth-based scheduling where a certain amount of bandwidth is allocated to each queue. For instance, if you want an xbox and email traffic queue to each get 50 percent of bandwidth, a round-robin scheduler could take a packer from the xbox queue then email, then xbox, then email, and so on. If packet sizes are different with xbox having packets of 10 bytes and email having packets of 100 bytes, then traffic wouldn’t be balanced. In its purest form, round-robin can’t weight traffic differently and the system can’t handle variable packet sizes.
A better solution of weighted round robin takes the weights and factors in packet size. In each round:
for each queue q:
q.norm = q.weight / q.mean_packet_size
min = min of q.norm’s over all flows
for each queue q:
q.n_packets = q.norm / min
send q.n_packets from queue q
Different weights and norm values can be used to customize traffic. Another type of round-robin algorithm is deficit round-robin where queues accumulate credit which specify how many bytes they can send in the next round and credit can carry over to handle larger packet sizes. Here, in each round:
for each queue q:
q.credit += q.quantum
while q.credit >= size of next packet p:
q.credit -= size of p
send p
The quantum value can be configured for each queue to determine how much to increase it’s credit. Quantums should reflect packet size. Small quantums mean there are a lot of rounds before sending a packet and large quantums can potentially lead to a lot of sent packets from one queue before moving on to the next. Credit carrying over helps to deal with variable packet sizes. Some pros of deficit round-robin are that you don’t need a mean packet size, it gives near-perfect fairness and 0(1) packet processes. Schemes that increase fairness also increase packet processing.
Traffic differentiation is a good idea in theory, but it can be hard to decide what granularity of isolation makes sense. Per-app requires deep packet inspection, is expensive and thwarted by encryption. Per-flow means lots of state. For fair queueing, schemes except for deficit round-robin are expensive, switches need to be changed and you have to decide how to prioritize traffic. For priority queueing it’s unclear how multiple methods would interact across the internet. There’s also enough bandwidth that a single FIFO queue usually works fine. Similarly, queue management works well in theory. RED and ECN or their ideas are used in some environments such as DCTCP (Data Center TCP), but not on the entire internet it is hard to set parameters and figure out how schemes should interact and switches need to be changed. Traffic differentiation requires a scheduling discipline such as one of the round robins with the goal of giving weighted fairness in the face of variable packet sizes while having low processing overhead. The lecture ends by asking if in-network resource management is even a good idea.
Lecture 13 – Networking: P2P Networks and Content Distribution Network (CDN)
How do we adapt new applications and technologies to an inflexible architecture? This week focuses on new technologies on the internet such as file-sharing, VoIP and video-streaming, all of which deal with P2P networks or similar constructs such as CDNs. File-sharing is the idea of getting a file from one person or machine to another. HTTP and FTP use a client/server setup where the client requests a file and the server responds with the data. The downsides are that there’s a single point of failure and it’s expensive and doesn’t scale. CDNs can be used to help by putting multiple servers near clients to decrease latency. With CDNs there wouldn’t be a single point of failure and the system would scale better.
Peer-to-peer networks can also be used for file-sharing. This distributes the architecture “to the extreme.” When a client downloads part of the file from the server, that client can upload part of the file to others, putting clients to work. THis is theoretically infinitely scalable. P2P networks (and CDNs) create overlays on top of the underlying internet, but what if users don’t want to upload. BItTorrent is a way of incentivizing peers to upload. The basics of the BitTorrent protocol are that you create a .torrent file with emta-information about the file such as the file name, length, information about pieces comprising the file, and the URL of the tracker. Then you have a tracker which is a server that knows the identity of all peers involved in your file transfer. To download a file, a peer contacts the tracker which responds with a list of other peers involved in the transfer. The peer connects to other peers and begins to transfer blocks. Some peers are seeders and already have the entire files (such as servers hosting the file or nice peers willing to stick around). In the actual download, peers request blocks which are pieces of pieces. Blocks are small chunks of the file that are around 16KB and are requested in a random order. Users aren’t allowed to download from a user unless they’re also uploading to the user, so peers want to have mutual interest where each has blocks the other wants. The protocol is divided into rounds. In round n, some number of peers upload blocks to peer X. In round n+1, peer X sends blocks to the peers that uploaded the most in round n (typically to the top four peers). Peers get started by reserving a small amount of bandwidth to give away freely. This method of incentivizing peers helped P2P file-sharing takeoff. Since the tracker is a central point of failure, most of today’s BT clients are trackerless using distributed hash tables instead.
VoIP is Voice over IP, such as skype. Skype used to be a P2P network for improving performance and allowing certain connections to work. Internet bred Network Address Translators. With client A behind a NAT wanting to initiate a connection to a server S, A’s IP is private and can’t be routed to, but S’s and N’s are public. A sends a packet to S. N receives it, rewrites the header and stores some state before sending it to S. S receives it and sends the response back to N which uses its stored state to figure out the packet is meant for A. N keeps track of the ports A communicates on and knows communication via those ports is meant for A. With two clients (A and S) behind NATs (N1 and N2 respectively), A wouldn’t even know S or N2’s IP. For skype this means that A and S can’t call each other. Skype provides a directory service. Assuming we can get N2’s public IP, when N2 gets a packet destined for S it has no idea what to do with it. Skype employs a supernode P with a public IP and routes A and S’s calls through P, which has a lot of state to work. A and S need to be registered Skype users and connect to P as part of starting up the Skype client (private Ip users initiate connections to public IPs). There is actually a network of supernodes and A and S connect to nodes in that network and the overlay network routes data between them. Skype lets you be a supernode if your memory and CPU are sufficient and you have a public IP. Some drawbacks are that A and S may not want their encrypted call routed through someone else and supernodes might not want to pay for transit traffic for other nodes. Today, Microsoft owns all of the supernodes and this is more of a hierarchy than P2P network. Skype claims its P2P system improves quality by allowing for more optimal routing.
Lastly, BitTorrent can’t be used to stream live video. Streaming requires getting blocks roughty in order and requires a certain amount of bandwidth at all times. BitTorrent works as peers can acquire blocks in any order and most peers are on residential links with weak upload bandwidth. CDNs on the other hand can be used for streaming.
Lecture 14 – Fault Tolerance: Reliability via Replication
Moving on from operating systems and networking, this lecture focuses on dealing with failures systematically and building fault-tolerant systems. More complicated failures will be shown such as with large distributed systems of machines across the globe and have to think about what applications are doing what they need. The general approach to building fault-tolerant systems is to identify possible faults (in hardware, software, design, operation, environment, etc), detect and contain them and handle the fault in the appropriate manner. Unfortunately, components are always unreliable and guarantees of a reliable system are probabilistic. Reliability usually involves a tradeoff such as with simplicity or monetary cost. It’s easy to miss possible faults and iteration is needed. Some portion of mission critical code will be required for the system to work and those components need stringent development processes.
With the goal of increasing availability, some useful metrics for quantifying reliability are mean time to failure and mean time to repair. Availability = MTTF/(MTTF+MTTR). Reliability can be improved via replication, adding redundancy. Replication within a single machine can be used to deal with disk failures or across machines to deal with machine failures. If a disk fails, your data is gone. You can replace other components like CPU easily, but the cost of disk failure is high. Though manufacturers claim the MTTF is 700K or more hours, this likely isn’t accurate due to averaging. Failures aren’t memoryless and the disk is more likely to fail at the beginning or end of its lifespan than than the middle. Whole-disk failures can occur. If the entire disk fails, all of its data is lost. RAID provides techniques for mitigating against this, replicating data across disks in smart ways and protecting against single disk failures. RAID 1 mirrors data across 2 disks, handling single-disk failures and improving performance on reads and not a bad performance hit on writes (since two writes can be done in parallel). Unfortunately, to mirror N disks worth of data, you need 2N disks. With RAID 4, given N disks, an additional parity disk is added. Sector i on the parity disk is the XOR of all of the sector i’s from the data disk. This can handle single-disk failure as if one disk fails, you can xor the other disks to recover its data. The same technique can be used to recover from single-sector errors. With RAID 4, to store N disks worth of data, only N+1 disks are needed. Performance can also be improved if files are striped across the array. FOr instance, an N-sector-length file can be stored as one sector per disk. Reading the whole file means N parallel 1-sector reads instead of 1 long N-sector read. RID is a system for reliability but performance influenced much of its design. A problem with RAID 4 is that every write hits the parity disk. RAID 5 is the same as 4 but the parity sectors are interspersed among all N+1 disks to load balance writes, though you need a way to figure out which disk holds the parity sector for sector i (which isn’t hard). RAID 5 is used in practice as it protects against single-disk failure and maintains good performance, though it is replaced often with RAID 6 which uses the same techniques but provides protection against two disks failing at once. RAID and replication don’t solve everything, such as independent failures.
Lecture 15 – Fault Tolerance: Introduction to Transactions
How do you build a reliable system out of unreliable components? Replication masks failures from users but doesn’t solve all problems and everything can’t be replicated. For failures it can’t handle, reasoning about them can be hard. Today focuses on achieving atomicity, where atomic actions happen entirely or not at all. Atomicity enables simplifications for reasoning about fault-tolerance since we don’t have to worry about in-between states and it will also be realistic for applications. For instance, a bank transaction shouldn’t be able to deduct from one account while failing before depositing to another. Which actions need to be atomic depend on the application. The first attempt at achieving atomicity is to store a spreadsheet of account balances in a single file. The file is loaded into memory, updates are made and it’s written back to the disk when done.
transfer (bank_file, account_a, account_b, amount):
bank = read_accounts(bank_file)
bank[account_a] = bank[account_a] - amount
bank[account_b] = bank[account_b] + amount
write_accounts(bank_file)
With this attempt, if the system crashed halfway through a write it wouldn’t be able to recover. A golden rule of atomicity is never to modify the only copy. A second attempt tries to write to a shadow copy of the file first and renames the file in one step, replacing the last line with
write_accounts(tmp_file)
rename(tmp_file, bank_file)
If a write fails halfway, the original copy will still be intact. The rename is a “commit point” and crashes before that point leave old values while crashes leave new values. The commit point itself needs to be atomic. To make rename atomic, rename needs to point “bank_file” at “tmp_bankfile”’s inode, remove “tmp_bankfile” directory entry and remove refcount on the original file’s inode. The directory entries are filename “bank_file” -> inode 1 and filename “tmp_file” -> inode 2. Inode 1 contains the old data with existing data blocks and a refcount of 1, while inode 2 contains new data, starting with no data blocks and a refcount of 1.
rename(tmp_file, orig_file):
tmp_inode = lookup(tmp_file) // = 2
orig_inode = lookup(orig_file) // = 1
orig_file dirent = tmp_inode
remove tmp_file dirent
decref(orig_inode)
If crashing before setting dirent, the renaming didn’t happen. If crashing after, the rename happened but refcounts are wrong. Crashing while setting dirent is bad as the system is inconsistent. This leaves the problem of needing to fix refcounts and needing to deal with a crash while setting the dirent. Single sector-writes can be provided by the disk as an atomic action. The time spent writing a sector is small and a small capacitor is enough to power the disk for a few microseconds. The problem of dealing with a crash while setting the dirent can be handled this way by stopping it from happening. To handle the issue of refcounts, the disk can be recovered after a crash, cleaning up refcounts and deleting tmp files. If a crash occurs during recover, then recover can just be run again.
recover(disk):
for inode in disk.inodes:
inode.refcount = find_all_refs(disk.root_dir, inode)
if exists(“tmp_file”):
unlink(“tmp_file”)
Shadow copies work but don’t perform well as it’s hard to generalize to multiple files and directories, they require copying the entire file for even small changes and can have issues with concurrency. For concurrency, isolation is important. Isolation is when multiple transactions run concurrently, they appear to have been run sequentially. Transactions are a useful abstraction providing atomicity and isolation. An entire transaction acts as a single atomic action. Solving isolation by just putting locks everywhere would perform poorly and a better way will be talked about later. Isolation and atomicity (and transactions) make it easier to reason about failures.
Lecture 16 – Atomicity via Logging
So far we have a poorly performing version of atomicity with shadow copies. This lecture focuses on using logging for reasonable performance for atomicity. Logging also works with multiple concurrent transactions. The basic idea is to keep a log of all changes and whether a transaction commits or aborts. Each transaction gets a unique ID. UPDATE records include old and new values of a variable, COMMIT records specify that the transaction committed and ABORT records specify that the transaction aborted. This is useful as updates are small appends and code is written to handle each case. To use a log for transactions, start by allocating a new transaction ID. On a write, append the entry to a log. On a read, scan the log to find the last committed value. On a commit, write the commit record which is the commit point and can be assumed to be a single-sector write and tomic. On an abort or recover nothing needs to be done. Logs perform well for writes and sequential writes are fast. Reads are terrible as the entire log must be scanned. Recovery is instantaneous.
Cell storage improves read performance and data is stored on disk or non-volatile storage. Updates go to a log and cell storage and reads are done on cell storage. To log is to write to the log while to install is to write to cell storage. Recovery can be done by scanning the log backwards, determining what actions aborted and undoing them. Recovery is idempotent and recover can be rerun if a crash occurs during recovery. To write, log before installing, known as write-ahead logging. The performance of log with cell storage is okay for writes as the disk needs to be written to twice. Reads are fast, but recovery is bad as the entire log needs to be scanned. Write performance can be improved by using a volatile cache. Reads go to the cache first, while writes go to the cache and are eventually flushed to cell storage. A problem is that after a crash, there can be updates that didn’t make it to cell storage and updates in cell storage may need to be undone. A redo phase can be used in addition to an undo phase during recovery to solve this. Recovery can be improved by truncating the log. Assuming no pending actions, flush all cached updates to cell storage, write a CHECKPOINT record and truncate the log prior to that record (usually means deleting a file). With pending actions, delete before the checkpoint and earliest undecided record. ABORT records can help recovery and skip undoing aborted transactions. Write-ahead logs provide atomicity with better performance than shadow copies and the primary benefit is making small appends for each update.
Lecture 17 – Fault Tolerance: Isolation
This lecture focuses on isolation. Given multiple atomic transactions, how do you schedule the steps of the transactions so they appear to have run sequentially. A naive solution is to run the transaction sequentially with a single global lock, though this gives poor performance. A better solution is fine-grained locking, but this was also error prone. What does it mean for transactions to appear to have run in sequence? There are different types of serializability and the right one depends on the application’s needs. Final-state serializability is where a schedule’s final written state is equivalent to that of some serial schedule. Two operations conflict if they both operate on the same object and at least one of them is a write. Concurrent reads are generally fine. A schedule is conflict serializable if the order of all of its conflicts is the same as the order of the conflicts in some sequential schedule. The order of conflicts is the ordering of the steps in each individual conflict. A schedule can be final state serializable but not conflict serializable.
Conflict graphs can be drawn where nodes are transactions, edges are directed and there is an edge from transaction I to J if and only if they have a conflict between them and the first step in the conflict occurs in I. An acyclic conflict graph means that the sequence is conflict-serializable. Two-phase locking (2PL) can be used to generate conflict-serializable schedules. With two-phase locking, each shared variable has a lock (fine-grained locking) that the transaction must acquire before an operation on the variable. After a transaction releases a lock, it can’t acquire any other locks. This is fine grained locking in a systematic way. The two phases are the acquire phase where transactions acquire locks and release phase where they release them. Unfortunately, this can result in dead locks where two transactions are trying to acquire a lock another is holding. Global ordering is a solution, but not very modular. A better solution is to use atomicity and abort one of the transactions. Detecting deadlocks is possible using wait-dependency graphs which capture the locks each transaction has and wants. A cycle in this graph means a deadlock. A transaction could also be aborted after a specified timeout.
Reader-writer locks offer a performance improvement. You can acquire a reader lock at the same time as other readers but only acquire a writer lock when there are no other writers or readers. For fairness, usually if a writer is waiting, new readers have to wait too. Locks can also be read prior to commit since once a transaction acquires all of its locks (reached its lock point) any conflict transaction will run later. If the transaction reaches its lock point and will no longer access the data, releasing read locks on it will be fine. Write locks are held on commit in case the transaction aborts. Relaxing requirements on serializability and isolation can also improve performance or giving up on conflict serializability. While conflict serializability can seem too strict, it’s easy to test for it, where view serializability is an NP-hard problem. Conflict serializable schedules are also view schedules and ones that are view serializable, but not conflict serializable involve blind writes (which aren’t read).
Lecture 18 – Distributed Transactions
This lecture focuses on distributed transactions. For instance, a given setup is a client and coordinator and two servers, one with accounts A-M and the other with accounts N-Z. The coordinator and servers all have logs and the coordinator passes messages from the client to appropriate servers. Responses from servers and coordinators indicate whether the action completed successfully or needs to abort. There are new problems to deal with besides server failure, such as network loss or reordering, and coordinator failure. The main problem is that multiple servers can experience different events. For instance, one could commit while the other crashes or aborts. Message loss re-ordering is easy with reliable transport. If messages are lost, they’re retransmitted. If duplicates are received, they’re ignored. If messages arrive out of order, they can be put back in order. A protocol is needed that provides multi-site atomicity in the face of various failures. A basic two-phase commit protocol helps here. With this protocol, the coordinator sends tasks to servers (workers) and once all tasks are done, sends “prepare” messages to workers. Prepared is tentatively committed and means all workers will definitely commit even if they crash. Once all workers are prepared, the coordinator tells them to commit and tells the client the transaction was committed. The two phases are the prepare and commit phases.
For worker and network failures prior to the commit point, it’s okay to abort. If a prepare message is lost, the coordinator times out and resends. If the prepare message experiences persistent loss, then the coordinator considers the worker to have failed. If prepare messages make it to some workers but not others, the coordinator resends to missing workers until everyone is prepared or considered to have failed. If the ACK is lost for prepare, the coordinator times out and resends. Reliable transport means workers don’t repeat the action and ACK the duplicate instead. If a worker fails before prepare, the coordinator sends abort messages to all workers and the client and writes an ABORT record to its log. On recover, the worker finds the transaction aborted. For worker and network failures after the commit point, it’s not okay to abort. For a lost commit message, the coordinator times out and resends. The worker sends a request for the status of the transaction. For a lost ACK for a commit message, the coordinator times out and resends. For a worker failure before receiving the commit, you can’t abort. Instead, after receiving prepare messages, workers write PREPARE records to their logs. On recovery, they scan logs to determine what transactions are prepared but not committed or aborted and make a request to the server asking for the status of the transaction. If it was committed, the server will send back a commit message. Whenever a worker prepared but hasn’t committed or aborted a transaction, it makes periodic request to the server for its status. The coordinator typically keeps a table mapping transaction ID to state for quick lookup.
Coordinator failures before a commit point can abort and failures after can’t. Once the coordinator hears all workers are prepared, it writes COMMIT to its own log, which is the commit point. Once the coordinator has heard that all workers are committed, it writes DONE to its log and the transaction is done. Coordinator failure before prepare should be handled by sending an abort message to workers and client on recovery since the client has likely timed out. Failure after the commit point but before DONE can be handled by resending commits on recovery.The DONE record keeps the coordinator from resending commit messages for every commit message on recovery. The coordinator can forget the state of a transaction after it is done, but workers can’t forget the state of a transaction until they hear commit or abort messages from the coordinator.
2PC can be impractical and sometimes compensating actions are used instead, such as banks letting you cancel a transaction for free with a certain amount of time. 2PC provides a way for a set of distributed nodes to reach agreement, whether commit or abort but doesn’t guarantee they agree at the same instant or agree in bounded time. This is an example of the “two-generals paradox.” Another problem is that when the coordinator is down, the whole system is inaccessible and when a worker is down, part of the data is unavailable. The solution is replication and single-copy consistency is used to keep data consistent. This is a property of the externally visible behavior of a replicated system. Operations appear to execute as if there’s a single copy of the data. PNUTs is a more relaxed version of consistency, since single-copy adds a lot of overhead and relaxing can lead to better performance. DNS is a system that doesn’t use single-copy consistency.
Lecture 19 – Availability via Replication
With multi-site atomicity, the next goal is to improve availability with replication, using single-copy consistency. While not always required, some systems need it. One problem that can occur is messages arriving at replicas in different orders, resulting in an inconsistent state, which is a problem that can be caused by a network. Replicated state machines or RSMs ensure that each replica ends at the same final state by starting with the same initial state on each server, providing each replica with the same input operations in the same order and ensuring that all operations are deterministic (no randomness or reading of current time). The assumption made is that failures are independent, which isn’t always true. RSMS use a primary/backup model where clients talk to a coordinator who talks to a primary server which talks to a backup server. The primary does important tasks and ensures it sends all updates to the backup before ACKing the coordinator, chooses an ordering for all operations, so primary and backup agree, and decides all non-deterministic values. If the primary fails, the coordinator could know about both primary and backup and decide which to use. This wouldn’t work since multiple coordinators would come to different conclusions about who is primary with network partitions. Having a human decide when to switch may be feasible for small web servers.
View servers can be added to the primary/backup model. The view server keeps a table that maintains a sequence of views. Each view contains the view number, primary and backup server. The view server alerts each server to whether its the primary or backup. ON receiving updates, the primary gets an ACK from the backup before responding to the view server. Coordinators make requests to the view server to ask who the primary is and can then contact the primary. To discover failures, replicas ping the view server. If it misses N pings in a row, the view server treats a server as dead. A basic failure could occur if a primary fails and pings cease. In this case, the view server lets another server know it’s the primary and it handles any client requests. Then the view server recruits a new idle server as a backup. To handle network partitions, a few rules for view servers are put in place. First, the primary wait for backup to accept each request. Then, the non-primary must reject direct coordinator requests. The primary must also reject forwarded requests (so it won’t accept an update from the backup) and the primary in view i must have been primary or backup in view i-1. A newly recruited backup will copy the state front he primary and be ready to go. If the primary fails during that copy, don’t promote the backup to primary as its state is incomplete. Instead, keep the failed primary as primary, since if its a network issue it may come back up. Having multiple backups isn’t a bad idea. Here, the view server is the central point of failure, but it can be distributed across different view servers handling different partitions of replica sets. Distribution isn’t the same as replication and we can’t replicate the view server the same way. A mechanism for distributed consensus is needed such as raft or paxos.
Lecture 20 – Introduction to Security
Previously, we’ve been building reliable systems to handle random and independent failures. This lecture starts focusing on building systems to maintain their goals against targeted attacks from an adversary who could steal personal information, perform phishing attacks, or use botnets or worms and viruses. Computer security and general security as compartmentalization helps use different keys for different things, logging can help detect compromises and the legal system can be a deterrence for attackers. The differences are that the internet allows for fast, cheap and scalable attacks and the number and type of adversaries is huge. Adversaries can be anonymous and have lots of resources and attacks can be automated. It can be difficult to enumerate all possible threats against computers and achieving something despite what an adversary could do is a negative goal that can’t be easily checked. Even a single attack could be too many and it can be hard to reason about failure probabilities. There’s no complete solution, but there are strategies for assessing common risks and combat common attacks.
For modeling security, we need goals or “policy” and assumptions or “threat model.” Common goals are privacy and integrity, which are limiting who can read and write data respectively, and availability, which is ensuring a service keeps operating. Threat models are what we’re protecting against, such as assuming an adversary controls some of the computers or networks, some software on the computers or knows some but not all passwords or encryption keys. Many systems are compromised due to incomplete or unrealistic threat models such as assuming the adversary is outside the company network when they’re not, or not preparing for social engineering. Benign overambitious with threat models makes modularity hard and being precise makes it easier to evolve a threat model over time.
Looking back at the client/server model, usually the client makes a request to access a resource on the server and we’re worried about security at the server. To try and secure the resource, the server needs to check accesses to it with “complete mediation.” The server puts a “guard” in place to mediate every request to a particular resource and the only way to access the resource is via the guard. The guard often provides authentication, verifying the identity of the principal (ex. via username and password) or authorization, verifying whether the principle has access to perform its request on the resource (such as by checking an access control list). The guard model can apply lots of places and not just client/server. The guard model assumes that the adversary can’t access the resources directly and that the guard is invoked properly in the right places. The guard model makes it easier to reason about security.
Examples of the guard model are a unix file system. The client is a process, server is the OS kernel and the resources are files and directories. The client’s requests are read() and write() system calls. Mediation is done with the U/K bit and system call implementation and the principal is a user ID. Authentication is done by the kernel keeping track of a user ID for each process and authorization by permission bits and an owner UID in each file’s inode. For a web server running on UNIX, the client is an HTTP-speaking computer, server is a web application, the resource may be wiki pages or something similar and requests are to read and write those pages. For mediation, the server stores data on the local disk and accepts only HTTP requests, requiring setting file permissions and assuming the OS kernel provides complete mediation. The principal is the username, authentication the password and authorization done by a list of usernames that can read and write each wiki page. For the last example, a firewall is a system acting as a barrier between an internal network and the outside world that keeps untrusted computers from accessing the network. The client is a computer sending packets, the server is the internal network, the desired resources are internal servers, and the requests are packets. Mediation is done by the internal network not being connected to the internet in other ways, having no open wifi access points on the internal network and no internal computers under the control of an adversary. There aren’t any principal or authentication, and authorization checks for the IP address and port in a table of allowed connections.
Complete mediation can be bypassed by software bugs or an adversary. You could reduce complexity by reducing the number of components that need to invoke the guard. The principle of least privilege says that privileged components are trusted and the number of trusted components is limited since one breaking is bad. The high level policy should be concise and clear while security mechanisms such as guards provide lower level guarantees. Users can make mistakes as well and the cost of security may be an inconvenient cost of security measures for users. The cost shouldn’t outweigh the value.
Lecture 21 – Authentication and Passwords
The security guidelines shown so far are to be explicit about our policy and threat model, use the guard model to provide complete mediation and to make as few components trusted as possible. The guard often lets some users in systems be anonymous. This lecture focuses on principal authentication primary with passwords. The goal of authentication is to verify the user is who they say they are. An attacker shouldn’t be able to impersonate a user. Passwords are useful because there are a lot of options. A random 8 letter password has 26^8 possible options and 60^8 with cases, numbers and symbols. Variable length passwords are even better and guessing is expensive making a brute-force attack infeasible. In the case of logging into an account on a shared computer system, a threat model used here is that the attacker has access to the server that password information is stored on, but not the network between client and server for now. Storing plaintext passwords on the server is a very bad idea as if the adversary is a sysadmin or has access, they could just read them from the accounts table. Even if they don’t have table access, they could use a buffer overflow to get access.
A better option is to store hashes of passwords on the server. A hash function H takes an input string of arbitrary size and outputs a string of fixed-length. Hash functions should be collision resistant and if two input strings are different, the probability their hashes are the same is virtually zero. Cryptographic hash functions are one-way and it’s hard to get the original input from the hash. This way, if an adversary gets access to the table, they’ll just get hashes and not passwords. Another problem arises if you compare that table to the hashes for popular passwords, potentially calculating hashes on a rainbow table., though more complex in practice. With a rainbow table, an adversary can figure out who has one of the most common passwords. Hash functions are easy to compute, though slow hashes (key-derivation functions) take longer, and it’s possible to create rainbow tables of common passwords either way. It’s important to consider human behavior when designing secure systems. A third attempt is to salt the hashes, storing username, a salt (random string unique per user) and the hash of the password concatenated with the salt. The adversary will see the salt if they get the table, but they’d have to calculate the salt of every common password concatenated with every possible salt, making it impractical to build the table. They could build a rainbow table for a particular user (for a particular salt value), which could be useful if targeting a specific user, but the goal of attacks is often to get as many accounts as possible. Rainbow tables are convenient since even if they take time to create, they can be used forever. Creating one per user per salt is much more troublesome, though.
While passwords are usually used to bootstrap authentications, we don’t continuously authenticate with the password for every command. Typing, storing, transmitting and checking a password can be a risk and no one wants to type their password for every command. Automating password entry would mean storing the password, which is another security risk. Web apps often provide session cookies in exchange for passwords. Session cookies act as temporary passwords good for a limited time. The client sends its username and password to a server. If that checks out, the server sends back a cookie which is something like {username, expiration, H(serverkey|username|expiration)}. The client can use that tuple to authenticate itself for a period of tie. The server key is used in the hash so that the user can’t fabricate hashes and the server can switch the server key to invalidate old cookies. The user can’t change the expiration without changing the hash which they can’t do without serverkey.
Phishing attacks are an attack where an adversary tricks users into visiting a legitimate-looking site owned by the adversary. That site asks for the username and password. This works regardless of secure networks as a user can just hand over their password. One solution is a challenge-response protocol. Assuming (for now) that the server stores plaintext passwords, instead of asking for the password, the server chooses a random value, r, and sends it to the client. The client computes H(r+password) and sends it back to the server. The server checks if the hash matches its computation of the hash with the expected password. If the server didn’t already know the password, it still doesn’t. A problem is if the server stores salted hashes, the client could compute H(r | H(p)) or (H(r| H(s|p))) and send that, but H(p)) is effectively the password and the server is effectively still storing passwords. A solution to this is SRP, the Secure Remote Password protocol. This isn’t explained, but lets the server store hashes of passwords and do a challenge-response. Overall, the idea is to make the server prove it knows a secret without revealing what the secret is.
Another problem can arise with how a password is initially set. If an adversary can subvert that process, there’s not much that can be done. For instance, MIT’s admissions office hands out new account codes and many websites let anyone with an email create a new account. MIT could require a user to show their ID and an admin can reset the password. Lots of websites use additional security questions to reset passwords. Password bootstrap and reset mechanisms are part of the security system and it’s important they aren’t weak. Alternatives to passwords, are password managers which can generate good passwords and track them securely (protected by another password you set). These keep users from picking bad passwords or reusing them, but less convenient since you may not know the passwords if you lose the one password protecting them. You also may not trust the authors of the password manager. Two step verification is another alternative, where the server texts you a code to input along with the password. Attackers will need the password and your phone to attack. Biometrics such as retina scans or finger prints would require attackers to be near you to login, but it can be hard to be anonymous or reset the “password.” Passwords aren’t perfect, and many alternatives are more secure with trade-offs with complexity and convenience.
Lecture 22 – Secure Channels
Last lecture looked at situations where adversaries could access a server. What about an adversary that’s already in the network and can observe, corrupt, inject, and drop packets. Some can be combated with techniques such as TCP senders retransmitting dropped packets and dropping corrupt packets faster (usually at a router). A plan is needed for carefully corrupted, injected or sniffed packets. This lecture focuses on stopping an adversary on the network from observing or tampering with contents of packets. The goals are confidentially where the adversary can’t learn message contents and integrity where the adversary can’t tamper with message contents. If the adversary tampers with the message contents, the sender or receiver needs to detect it. The result of this is a secure channel.
Secure channels ensure confidentiality with encryption. Encrypt(k, m) -> c and Decrypt(k, c) -> m, where k is the key (a secret unknown to the adversary and never transmitted), m is the message, and c is a cipher text. Given c, it is virtually impossible to obtain m without knowing k. Encryption doesn’t provide integrity by itself, since the adversary could change some bits in the cipher text and for “mathematical reasons.” You can ensure integrity with message authentication codes (MACs), where MAC(k,m) -> t, taking a key and message and giving an output. The difference between MACs and hash functions is that MACs use a key. Another name for MACs is “keyed hash function.” The adversary can’t compute the MAC of a message without the key and there are other subtle differences such as different mathematical requirements.
So far, if an adversary intercepts c= encrypt(k,m) and h = MAC(k,m), MAC(k, decrypt(k,c)) == h won’t check out. Instead of [c|h], a sender could send c|MAC(c), encrypt(k, m | MAC(k,m)), and all provide a needed level of integrity, but different level of security against other types of attacks. A problem is that the adversary can intercept and retransmit (“replay”) a message. A solution is to put a sequence number in each message and choose a random sequence number for each connection. If the adversary intercepts the message, they can’t replay it in the same way as the sender won’t reuse the sequence number. Assuming the sequence numbers don’t wrap around. If there is a conversation long enough to exhaust the sequence number space, a session is renegotiated between the sender and receiver where they change a random variable known as the session ID. If the receiver is also sending to a sender, the receiver may use that sequence number and an adversary could replay in the other direction known as a reflection attack. The solution is to use different keys in each direction.
The sender and receivers need a secure way of exchanging keys. One technique is the Diffie-Hellman key exchange. The sender and receiver pick a prime number, p, and a generator, g (which has to be a primitive root modulo p). They don’t need to be secret and an adversary can know them. The sender picks a random number a (secret) and receiver picks random number b (secret). The sender sends g^a mod p to the receiver which sends g^b mod p back. The sender computes (g^b mod p) ^ a mod p = g^ab mod p and receiver computes (g^a mod p) ^ b mod p = g^ab mod p, which is the secret key both can use. The adversary can learn of p, g, g^a mod p, and g^b mod p, but can’t calculate the secret key without knowing a or b. The problem is a man in the middle attack. If an adversary in the middle of the network intercepts and responds to messages in both directions, the client and server will think they’ve established connections with each other when they’ve both established a connection with the adversary.
The problem with Diffie-Hellman was that messages weren’t authenticated and the server doesn’t know if they’re really talking to the client and vice versa. Sharing the key between the parties was known as symmetric key cryptography. For signatures, public-key cryptography can be used. Each user generates a key pair (PK, SK) where PK is public and known to everyone and SK is secret with only the user knowing it. These are related mathematically and RSA is a scheme for generating key pairs. SK lets you sign messages and PK lets you verify signatures but not perform a signing. Sign(SK,m) gives a signature using the secret key and message. Verify(PK, m, signature) gives yes or no (if the signature is verified or not). This is similar to MACs and signatures don’t require parties to share a key. There are lots of ways to distribute public keys. The client could remember the key used to communicate with the server last time, which is easy to do and useful against following man in the middle attacks, but doesn’t protect against a first man in the middle attack or let parties change keys. Another way is to consult an authority which knows everyone’s public key, but it doesn’t scale as the client asks for a PK every time and the client needs the server’s public key beforehand. Another way is to use an authority but to pre-compute responses. The authority creates signed messages {Server, PK_Server}_{SK_as}. Anyone can verify the authority signed the message with PK_as. When the client wants to talk to the server, it needs a signed message from the authority which can come from anywhere as long as the signature checks out. The signed message is a certificate and this approach scales better.
Generally, certificate authorities come with a browser and authorities need to agree on how to name principles and check if a key corresponds to a name. If a CA makes a mistake, a way to revoke certificates is needed. Expiration dates are useful in the long term but not for immediate problems. Querying an online server to check certificate freshness is another idea. You can also avoid CAs by using public keys as names, which works well for names users don’t have to remember. TLS is a protocol that does all of this. There are lots of parts and its complexity can cause problems. The client and server use public key cryptography to exchange a secret which they use to generate keys for symmetric cryptography (much faster than public-key). In general, traffic isn’t encrypted by default since it can be computationally expensive, complex to implement and wasn’t thought about until recently.
Lecture 23 – Network Security and DDoS Attacks
Last time focused on an adversary trying to observe or tamper with packets. For this lecture, the adversary is trying to use the network to attach users more actively. Some attacks don’t require the adversary to observe packet contents and secure channels won’t help. For instance, in a DoS (“denial of service”) attack, the adversary wants to bring down a service, potentially by taking down the root DNS servers. A strategy is to congest the service, making it spend time handling the adversary’s requests so it can’t get to real ones. In a DoS, the adversary sends a bunch of traffic to the service (maybe even invalid requests), queues fill up and packets are dropped. A DDoS (distributed DoS) attack uses multiple machines. Any resource can be targeted, such as routing systems or databases. This can cause a server to be down for a few hours and can be impactful for banks, DNS root servers or high frequency trading machines.
Botnets are large collections of around 100,000 compromised machines that an attacker can control. This makes DDoS attacks easy and can be rented cheaply. There are common ways for machines to get compromised and become part of the botnet. A common way is for a user to visit a vulnerable website which usually uses a cross-site scripting a track. For instance, if a blog site lets users enter comments on blogs, an attacker could embed an executable script in their comment and when users browse, the servers send comments to their browsers which execute the script, sending the user’s cookie to the attacker’s site. An XSS script to compromise a botnet machine causes a user to download a rootkit which compromises the machine. Bots then contact command and control servers to receive commands. To combat botnets, simply blocking IP addresses is ineffective since they can be rapidly changed. A better solution would be to distribute systems so DDoS attacks can’t bring down a central component, though this leads to complexity.
A better solution is a Network Intrusion Detection System or NIDS. To block IP addresses, how could you figure out which IP’s were part of the botnet. For that matter, how do you detect a network attack? There are two approaches. First, you could keep a database of known attack signatures and match traffic against the database. This is easy to understand and useful for detecting known attacks, but it can’t discover new attacks and requires an attack to have previously happened. The other approach is anomaly based where traffic is matched against a model of normal traffic and abnormalities are flagged. This can be used to deal with new attacks, but detects known attacks less accurately and requires a model of normal traffic. Many systems use a hybrid-approach and also let users actively prevent passively detected attacks. Snort and Zeek are examples of examples of intrusion detection systems. NIDS can be evaded, however. If a NIDS was built to scan traffic for a particular string, it could be difficult as the attacker could force a confusing state on the NIDS. ANother way to evade is to mount an attack on the detection mechanism.
Attacks that mimic legitimate traffic are even harder to detect. For instance, in HTTP flooding, an attacker floods a webserver with legitimate HTTP requests to download a large file or perform an intensive database operation. TCP SYN floods work by TCP connections starting a handshake causing the server to keep state about the connection until complete. An attacker can initiate many handshakes to exhaust that state. Optimistic ACKs work by an attacker starting a TCP connection with the victim and ACKs packets it hasn’t received yet. The victim sends more and more traffic to the attacker saturating their own link. DNS reflection and amplification works with bots locating DNS name servers (better if DNSSEC-enable) and sending DNS requests to those nameservers. Sources are spoofed to be the victim’s IP address and if DNSSEC-enable, the relevant info is requested as the responses tend to be large. This results in large DNS responses going to the victim’s machine.
Attacks can also happen on routers. If an adversary gained access to routers, they could overload the router’s CPU with lots of routing churs or overload the routing table with too many routes. An attacker could also hijack prefixes by getting an AS to announce it originates a prefix it doesn’t own or announces a more specific (and more preferred) prefix, or just lies that a shorter route exists. There are lots of examples of this and the solution is secure BGP with a similar mechanism as DNSSEC but with authentication, creating and signing advertisements takes much longer. A lot of ASes are needed to buy into this at once, otherwise, hijacking isn’t worth it. Overall, secure channels are great, but attackers can still use the network for attacks which can be devastating on the internet’s infrastructures. While proposals exist to secure infrastructure such as DNSSEC and secure BGP, there are problems and much of the internet is insecure.
Lecture 24 – Bitcoin
Bitcoin is a digital currency system which may provide anonymity. In general, money is a medium for exchange which isn’t valuable for itself but is for future exchanges. It’s also a store of value. Physical money is portable, semi-anonymous (though there are serial numbers to track), and you can’t double spend (or have the same bill in two places). You also can’t repudiate after payment (or say you didn’t). There’s no need for a trusted third party for a transaction and you just hand the bill to the other person. The government can also print more money as needed. Physical money is difficult to tax or monitor transactions, but is easy to steal and doesn’t work online. Electric money such as credit cards and paypal work online and may be harder to steal, but provide no privacy.
What about a decentralized digital currency? With the goal of building a digital currency that doesn’t require a trusted third party such as a bank, you need to address forgery (you can’t generate money you don’t have), double-spending (can’t spend the same money twice), and theft. If, to send money, you just wrote a message saying “sender gives X coin to receiver,” that would be easy to forge. Requiring a signature so only the sender can send the message, you could still run into a problem with duplication causing more money to be send. Sequence or serial numbers can be used to clear that up. This still requires keeping track of who owns which coins, assigning new serial numbers and verifying a coin hasn’t been spent
What if the sender tries to send the same coin to two people to spend it twice. You could publish all transactions in a public log and let everyone track all transactions. There needs to be a way to secure the log and make sure everyone has the correct version. One approach is if the sender sends a coin to the receiver, the receiver publishes the transaction and alerts everyone. When trying to send it again, the network will see the coin was previously spent. If sent to both at the same time, though, this doesn’t work. One fix is to get consensus from enough of the network to determine which transaction is valid. Simply saying more than half of the network would be a problem since we might not know the size and the sender could create multiple identities known as a Sybil attack where a user subverts a system by creating multiple identities.
Proof-of-work is used to thwart Sybil attacks by making it computationally expensive to perform an action. Multiple identities alone won’t work and computation power is needed instead. Bitcoin’s proof-of-work works as follows. A user broadcasts their intent to send a coin to all users on the network. Users who hear the message add it to their queue of pending transactions with the goal to verify a block of transactions. After a user checks the block is valid and everyone owns the coins they’re trying to spend, they have to solve a “puzzle.” The goal is to find x such that H(t|x) < target, where t is a block of transactions as a bit string. The target changes frequently and it takes roughly ten minutes to solve the puzzle. When a user solves the puzzle and finds x, they broadcast the block out with x and receive a monetary reward used to motivate users to take part in the process. This is the process of “mining” bitcoins.
The log contains verified transaction blocks and a pointer to the previous block, providing an ordering on the transactions to know who owns which coin. The pointer is a hash of the previous block and the log is called the blockchain. If two people solve the puzzle at the time, the blockchain forks. When a fork occurs, miners keep track of both forks and work to extend the longest one. The shorter fork is invalidated quickly. A transaction isn’t confirmed until it’s a part of a block on the longest fork and at least five blocks follow it. An unrealistic amount of compute power would be required for an attacker to try and undo spending a coin or force another part of a fork once one is confirmed. Bitcoin provides a distributed public ledger and other tools beyond currencies can be built on that. Some drawbacks are that proof-of-works waste computation, users are typically either miners or users who spend but don’t mine, and it can take time to confirm a transaction. A couple of alternatives that help with these problems are Ethereum and Algorand.
Lecture 25 – Tor
Tor is a network used for users to remain anonymous. With Tor, the goal is to hide information from a network adversary. A secure channel model encrypts data so packets have hidden information. Adversaries can know which servers are communicating as the to and from packet headers can’t be encrypted and that can be bad if a client wanted to communicate with a sensitive website. Tor can provide anonymity so a client, Alice, will be the only one who knows what server she’s communicating with. The server won’t even know that it’s talking to Alice. A starting idea is to create a proxy server. Alice sends data to the proxy server and the header shows “To:Proxy|From:Alice.” The proxy receives the packet, rewrites the header and sends it to the server (“To:Server|From:Proxy”). Traffic back from the server goes to the proxy which sends it back to Alice, by keeping some state. An adversary between Alice and the proxy would only know that Alice communicated with the proxy and an adversary on the network between the proxy and server would only know the proxy communicated with the server. The problem is that the proxy knows that Alice is communicating with the server.
A better idea is a network of N proxies. Alice chooses three or more and the traffic goes from alice to proxy 1 to proxy 2 to proxy 3 to server. Nodes on this path are part of a circuit.If the circuit Id is 5, then each node keeps the circuit ID and the info on the node it sends data to and receives data from. The state at each node only knows the previous and next hop, which lets nodes send traffic in forward and reverse directions by updating the traffic header. A problem here is that the adversary can observe the network between Alice and proxy 1 and between proxy 3 and the server to see that the same packet data was sent, even if encrypted and know that Alice is talking to the server.
Tor combines a network of proxies with encryption. Each proxy gets its own key pair. Alice encrypts data with keypairs for all three proxies and each proxy strips off a layer of encryption. Layers are stripped off like onions, so Tor stands for The Onion Router. Tor uses slightly different encryption, but a similar idea. The most popular attack against Tor is a traffic correlation attack. If the adversary observes traffic into the entry node (P1) and out the exit node (P3), they see different data in the packets, but some factors remain preserved such as packet sizes and timing. An attacker can use that info to correlate traffic and infer that Alice is communicating with the server. Tor doesn’t defend against this but has users use a few entry nodes in the hopes they are trusted. The idea is that having traffic identified some of the time is as bad as having it identified all of the time. There is a nonzero chance that it will never be identified, unlike a setup where users choose a new random entry node each time. The Tor developers clearly state what it protects against. Tor can be slow and latency is high since traffic bounces across the globe with decryption at every step. Bitcoin and Tor are somewhat, but not completely anonymous, but they use cryptography in clever ways and solve interesting technical problems.
Lecture 26 – Policy vs. Mechanism
In 2015, the FCC made a net neutrality ruling which prohibits three things. First, it prohibits ISPs blocking access to legal content, applications, services and non-harmful devices. It prohibited ISPs throttling or impairing traffic on the bases of these legal factors and prohibited paid prioritization where ISPs can’t favor some traffic in exchange for “consideration of any kind.” ISs can regulate the flow of traffic to and from directly connected networks, still, so Comcast can charge more money for a faster connection to their networks. GDPR is a measure to protect users from data breaches. Under GDPR, organizations need to request consent which should be clear and easy to withdraw. Users need to be able to access their data, transfer it to other services and erase it, and organizations should only keep data that’s absolutely necessary. GDPR regulations apply to companies processing the data of EU subjects and advocate for privacy by design.
Lastly, there are a variety of recommended follow-up courses that go further on content touched upon in this one. Operating Systems (6.828), Computer Networks (6.829), Database Systems (6.830/6.814) go into more details on networks and systems. Computer Systems Security (6.858) and Network and Computer Security (6.857) talk more about systems while Cryptography and Cryptanalysis (6.875) and Cryptocurrencies (6.892/MAS.S62) are more math heavy. The most natural follow up is Distributed Systems (6.824) though Principles of Computer Systems (6.826) and Distributed Algorithms (6.852) are grouped similarly. Lastly, Intellectual Property and Ethics for Engineers are suggested (6.903 and 6.904 respectively).
Recitations and links
Most of what is listed for recitations are various articles and readings that go into detail on the implementation of some systems from papers and other sources that would presumably be discussed in that recitation session. Admittedly, I haven’t read most of these in full and am listing them here to come back to.
The Rise of Worse is Better by Richard P. Gabriel which is about a philosophy of the same name
The UNIX Time-Sharing System from Bell Laboratories, which discusses the implementation and design of UNIX
Eraser: A Dynamic Data Race Detector for Multithreaded Programs
MapReduce: Simplified Data Processing on Large Clusters, from Jeffrey Dean and Sanjay Ghemawat at Google
The Design Philosophy of the DARPA Internet Protocols by David D. Clark at MIT
The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks, by Paul F. Tsuchiya at MITRE
Resilient Overlay Networks, from MIT
Data Center TCP, from Microsoft and Stanford
The Akamai Network: A Platform for High-Performance Internet Applications, from Akamai
The Google File System, from Google
Log-Structured File Systems, by R. and A. Arpaci-Dusseau
Concurrency Control and Recovery, by Michael Franklin
Replicated Data Consistency Explained Through Baseball, by Doug Terry at Microsoft
In Search of an Understandable Consensus Algorithm, from Stanford and about the Raft consensus algorithm
Why Cryptosystems Fail, by Ross Anderson
Security Vulnerabilities in DNS and DNSSEC
Meltdown: Reading Kernel Memory from User Space
Reflections on Trusting Trust, by Ken Thompson
The Night Watch, by James Mickens
Conclusion
While this may be the course that leaves me with the most to go back to for information on security and network communications, it’s also broad enough that I’d want to check out some more specific courses in those fields. The readings leave a lot left to explore further from here although I’m moving on for now. This course along with Software Construction and Computation Structures combine to give a pretty good basis for programming, and how computer systems and networks work along with different areas that allow for future deep dives. The next and last course I’m looking at is Artificial Intelligence, which I’m looking forward to since the first project I attempted with this site was going through Kaggle competitions. It will be interesting to see MIT’s approach as I’m expecting it to be more similar to the mathematics and algorithms courses than the last couple of courses.
Leave a Reply