Show Menu

Operating Systems Cheat Sheet by

Computer systems course at UofT


Forwarding vs Routing
Forwarding: data plane - Directing a data packet to an outgoing link - individual router using a forwarding table Routing: control plane - computing paths the packets will follow - Routers talking amongst themselves - individual router creating a forwarding table.
Link State vs Distance Vector:
- DV error propog­ates, LS only computes its own table. - DV: conver­tence times varies (count­-to­-in­finity problem), LS: O(n^2) algo requires O(nE) messages
Flow control vs Congestion control
Flow control: keeping one fast sender from overwh­elming a slow receiver Congestion control : keep a set of senders from overlo­ading the network


Connec­tio­nless: No handsh­aking between sending and recieving adapter.
Unreliable: receiving adapter doesnt send ACKs or NACKs; Packets passed to network later can have gaps; Gaps will be filled if applic­ation using TCP
Carrier sense: wait for link to be idle
Channel idle: start transm­itting; Channel Busy: wait until idle
Collision detection: listen while transm­itting
No collision: transm­ission is complete; Collision: abort transm­ission and send jam signal

Path-v­ector Routing

-Advertise entire path
-Distance vector: send distance metric per dest d
-Path vector: send the entire path for each dest d

BGP path selection

BGP uses both policy and shortest path based routing.
Route learned from customer preferred over route learned from peer, preferred over route learned frompr­ovider

Congestion Control

Congestion cntrl is preventing a set of senders from overwh­elming the network, flow cntrl is preventing one fast sender from overwh­elming a slow receiver.
Congestion strategy
Drop one flow, buffer and send after one is gone, reschedule on flow, ask both to reduce flow
Congestion Collapse
Increase in net load results in a decrease of useful work -Causes: False trans, undeli­vered pckts
Simple Resource Allocation
is FIFO queue, drop tail (incoming) if buf full.
TCP Congestion Control
feedback based, hosted based, congestion window. Send at rate of slowest component, window = min(co­nge­stion, receiver wndw) Increase linearly, but half if there is a loss. (w <- w + w/1 or <- w/2) never below 1 MSS though. Congestion window is rep in BYTES because of MSS. #packets per window : CWND/MSS Inc per ACK : MSS*(M­SS/­CWND) Sending rate = Congestion Window size / RRT. Expone­ntial fast start, because linear is too slow to start and wasteful starting @ 1 MSS/RRT and 1MSS cwnd.
Triple dup ACKs
multip­lic­ative decrease. Timeout – start over @ 1MSS.
Nagel's Algo
buffer small data if less than 1 MSS while waiting for ACK of outgoing packet. Basically sending 1 small packet per RTT. Batching bytes!
Delayed ACK/Pi­ggy­backing
send ACK as part of a data packet from B->A if data generated within wait time of 200 – 500 msec.

Interc­onn­ecting LANs

carrier sense multiple access w/ collision detection
is connec­tio­nless and unreliable
Spanning Trees
no loops in topolo­gy.(no cycles) Select switch with smallest ID as root. Initially each switch thinks its root and sends msg (X,0,X). add1 to distance from neighbor node from root. (Root, dist to root, self)
Cut thru switching
start transm­itting as soon as possible. Overla­pping transm­issions (transmit head of packet while still receiving tail)
Switch over router
PnP, Fast filtering and fwd, cut thru

Interior Routing Protocols (IGP)

uses distance vector; updates sent every 30 seconds; no authen­tic­ation; not used much anymore
Link-state updates sent (using flooding) as ad when required; Every router runs Dijkstra's algorithm; Authen­ticated updates; widely used

Network Layer

Different devices switch different things:
physical later: electrical signals (repeaters and hubs)
link layer: frames (bridges and switches)
network layer: packets (routers)

Link Layer / Error Detection / Correction

Manchester Coding
Low to high if 0, High to low if 1.
invert on every 1, do nothing if 0.
more efficient than Manche­ster, map data bits to code bits 80%
mark start and end of frames from stream of bits. Use a flag 0x7E
Propog­ation Delay
distance / speed of light, Transm D = messag­e/rate bps
2 * one way delay (latency)
Prop + Trans + Queue = Arrival - Departure
Bandwi­dth­-Delay Product
measures data in flight = Bandwidth * latency
Parallel Transm­ission
latenc­y=M/R + SUM(Pr­op_i)
Actual end to end latency
SUM(Tr­ansp_i + Prop_i + Q_i)
detect and retran­smit, typically at higher levels (Network +)
FEC (Forward error checking)
correct codes, good for real-time, less retran­smi­ssions.
CRC (cyclic redundancy check)
divide n bits of data by C(x), compare to k bits
Hamming Distance
tells us how much error can safely be tolerated. d+1 Detect. 2d+1 correction

Internet Topology and Routing

physical location access point to internet. Large dense popula­tion, part of backbone
>= 2 providers, better perfor­mance, extra reliab­ility, financial leverage through compet­ition
AS Prepending
artifi­cially inflate AS path length seen by others to convince some AS's to send traffic another way (Export policy)
Increm­ental Protocol
Learn multiple routes, pick one with policy
distri­butes BGP info within AS, sessions between routers, maps an egress point to out link. BGP increm­ental updates, maps dest prefix to egress point
Causes of BGP routing
Topol changes, changes in routing policy, BGP session failure, conflicts in protocols in diff AS's

Software Defined Networking

Vertically integrated Closed, propri­etary Slow innovation -> horizo­ntal, open interface, rapid innova­tion. OS abst.
Network OS
has global view of network to make decisions. Control plane is in one place. Distri­buted sys. Control program operates on top of network OS.
Routing Overlays
IP Tunneling - packet delivery service with new routing strategies
IP multicast
delivering same data to many receivers
resilient overlay network. Increase perfor­mance and reliab­ility of routing, more than IP. Adapts to congestion
Overlay Networks
A logical network built on top of a physical network. tunnels between host computers. Hosts implement new protocols and services. Effective way to build networks on top of the internet. P2P
centra­lized directory, gnutella –query flooding, kazaa-­super nodes, bittor­rent- distri­buted downlo­adi­ng/no free loading BitTorrent prevents free riding: Allow the fastest peers to download from you. Occasi­onally let some free loaders download

Network Security

availa­bility, protec­tion, authen­ticity, data integrity, privacy
SYN Flooding
Make so many sessions it runs out of memory
DoS aplenty
Attacker guesses TCP seq# for an existing connec­tion. Attacker can send rst to close cnnctn.
Bellov­in/­Moc­kapetis attack
make target trust attacker using reverse DNS, take control of DNS server that target talks to and find a trusted connec­tion.
DNS rebinding
send short ttl for dns query, target requests IP of your domain, but feed IP of private server.
IP Spoofing
expose trusted connec­tion, predict Seq # from SYN and predict port => guess state. Now Impers­onate one end and send packets.
Stateful Packet Filter
only allow traffic initiated by client. Track all conn.

Queuing Mechanisms

End to End principle
Design principle for the internet that says you should keep functi­ona­lities at the end-hosts (Appli­cation specific functions)
Random Early Detection (RED)
randomly drop packets to signal congestion before it happens as queue fills up. Probab­ility is prop queue size. If below a threshold, don’t drop anything. Use average queue len to allow short term bursts. -RED is hard to use, must have the right parameters to work. -Desyn­chr­onizes senders to have stead aggregate flow, not bursty.
Explicit Congestion Notifi­cation (ECN)
router marks packets with ECN bit, 2 bits 1 for ECN enabled and 1 for congestion in IP TOS. Must be supported by end hosts and router to work. But better since it does not drop packets like RED.
NAT soft state
if no packets arrive in time window, then delete mapping.
filters packets based on src/dst IP addr, TCP/UDP src/dst port, ICMP type, TCP SYN and ACK bits
Traffic shaping
rate limiting certain traffic like p2p Inspecting every packet is challe­nging on high speed links. Place compli­cated firewall rules on edge low speed, and simple in core high speed.
users must login, only point that accepts telnet. (central, caching) 1-Detailed policies 2-Avoid rogue machines 3-central logging 4-caching
Pros: Fewer IPs, Blocking unwanted traffic, Making fair use of net resources, Improcing web perfor­mance. Cons: No longer globally unique, no longer assume simple delivery of packets


No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets