Note: Multiprocessor Synchronization

• volatile in Java, it’s for thread context
• static in Java, it’s for object context
• thread-oblivious and

Note: Networks

Questions

• What about hard-coded maxlen for now
• what is relay in hardware
• IP packet header length: in 32-bit units
• Fragment offset?
• delete when metric = 16?
• IGP EGP BGP?
• Mixed use of Printf.printf and Lwt_io.printf

Midterm Review

01. Intro

Circuit switching vs Packet switching

STDM: waste capacity; doesn’t degrade gracefully; illusion of direct link

Statistical Multiplexing: maximizes link utilization; unfair; unpredictable; packet may take different paths; more overhead(additional information like destination address)

Address for link layer: MAC address; Address for IP: IP address

02. Layers

03. Physical Layer

Shannon’s law

NRZ: Non-Return to Zero

NRZ Drawbacks: no signal is 0; consecutive 1s or 0s are problematic; baseline wander problem; clock recovery problem

NRZI: Non-Return to Zero Inverted; encode 1 with transition, 0 with staying the same

Solve problem of consecutive 1s

Manchester: map 0 to chips 01; 1 to chips 10

Solve clock recovery and baseline wander but transmission rate now in half

4B/5B: every 4 bits encoded as 5 chips; transmit using NRZI

Never get more than 3 consecutive 0s

Encoding goals: page 24

Framing

• Sentinels

  • Byte-oriented
  • Bit-oriented
• Length counts
• Clock-based

Byte-oriented: character stuffing

Bit-oriented: bit stuffing

Drawback of sentinel: variable length

Length-based: put length in header

Drawback: length get corrupted

CRC checksum helps detect error

Clock-based: 125 us, encode with NRZ but XOR payload with 127-bit string to ensure lots of transitions

04.Link Layer

Metrics

At Least Once Semantics

Duplicate data: add sequence numbers

At Most Once Semantics

Uniquely identify each packet

Sliding Window Protocol

How big is the window? “Bandwidth-Delay Product” BW B/s x RTT s

Sender:

• send window size (SWS)
• last acknowledgment received (LAR)

• last frame sent (LFS)

• Invariant LFS - LAR <= SWS
• Advance LAR when ACK arrives
• Buffer up to SWS frames

Receiver:

• receive window size (RWS)
• largest acceptable frame (LAF)

• last frame received (LFR)

• Invariant LAF - LFR <= RWS
• cumulative ACKs

Tuning send window

SWS- fill the pipe RWS- 1 <= RWS <= SWS SWS <= max valid seq# / 2

Error Detection

Hamming distance

If min HD between valid codewords is d:

• can detect d-1 bit error
• can correct (d-1)/2 bit error (round down)

2-D Parity

IP Checksum

n-bit code should capture all but 2^-n fraction of errors- Why?

CRC - Error Detection with Polynomials

05. Switching

Media Access Control

• Partitioned Access
• Random Access

Ethernet

Addressing: MAC address

Collision detection

10Base2:

• Manchester encoding- for constant average voltage so that it can be detected
• if collision, jam for 32 bits
• transmission time >= 2 x propagation delay
• exponential backoff nth time k x 51.2us, for k = 0 .. 2^min(n,10)-1
• capture effect

Token Ring

• Interface Cards: Hardware relay

Switching

• Virtual circuit switching
• Datagram Switching
• Source Routing

Virtual circuit switching

• Explicit set-up and tear down phases
• connection-oriented model
• one RTT before sending first packet

Datagram switching

• connectionless model
• no delay for connection setup

Source routing

• packets carry entire route: ports

Bridging

Learning Bridges

Dealing with loops

Spanning Tree Protocol

• Doesn’t scale
• Broadcast doesn’t scale
• no way to route around congested links

VLAN

Topology doesn’t have to mirror physical locations

Switch architecture

Buffering

• head-of-line blocking

07. IP

ARP- address resolution protocol

DHCP- dynamic host configuration protocol: for obtaining host IP addresses

NAT- network address translation

ICMP- internet control message protocol

A protocol runs on top of IP

08. Intra-domain Routing

09. Inter-domain Routing

TCP

• Sequence number is the number for the first of byte of data carried in that segmant
• Acknowledge number is the next sequence number expected
• RST: when receiver receives a segment it did not expect to receive
• Handling lost ACK packet before ESTAB
• Biggest advised window: 2^16 - 1, buffer size: 2^16

Notes: Database Management Systems

• relational algebra <=> relational calculus
• procedural = imperative
• Datalog adds recursion which relational calculus can’t do
• check will be run for every DB update, so think carefully before adding check to database
• cannonical cover algorithm for functional dependencies(search about it)
• materialize
• extension language for SQL(PL/SQL, PL/pgSQL)
• Lossless joins; Dependency preservation; Redundancy Avoidance
• always close PreparedStatement and ResultSet for JDBC when working with Java, or you’ll get memory leak

• Calculate closures:

  • Attribute closures
  • Armstrong’s axioms
• 3NF? Didn’t mention it at all

Note: jQuery

The .attr() method

• setter: $('a').attr('href', 'example.com')
• getter: $('a').attr('href')

Selecting Elements

1. By ID: $('#myId')
2. By Class Name: $('.myClass')
3. Compound: $('#contents ul.people')

4. Pseudo-selectors:

   $('a.external:first')

Does My Selection Contain Any Elements?

if ($('div.foo').length) {
  // do things
}

Refining & Filtering Selections

// Refining selections.
$( "div.foo" ).has( "p" );         // div.foo elements that contain <p> tags
$( "h1" ).not( ".bar" );           // h1 elements that don't have a class of bar
$( "ul li" ).filter( ".current" ); // unordered list items with class of current
$( "ul li" ).first();              // just the first unordered list item
$( "ul li" ).eq( 5 );              // the sixth

Note: Data Science

Relational Database

1.(g)

For matrix multiplication, use GROUP BY both row_num and col_num will help a lot.

MapReduce

3

Find a key that works for both pairs.