Mid-Term Test Notes

Sockets

IP: stateless, unacknowledged, unreliable, unordered.

TCP/UDP add ports on top of IPv4 for addressing.

TCP/Stream:

• Acknowledgements of failure
• Record boundaries not preserved

UDP/Datagram:

• One write, one packet; one read, one packet

API:

• bind: socket to IP port/address family
• listen: declare accepting incoming requests
  • accept: waits until request received. Returns a new socket
• connect
  • TCP: request establishment of connection
  • UDP: default receiver when using send/write
• read/recvfrom: get received data. Blocking if no data
• write/sendto: send data. Blocking if buffer is full
• sendto/recvfrom specifies port/address family of sender/receiver
• close: free resources

Network byte order: big endian.

Protocol Layering

Service access point: interface to service for higher layer.

| Header | Higher-layer payload/service data unit | Trailer |

OSI

Physical/Link layers single-hop scope.

Network layer use single-hops to achieve end-to-end communication.

Routers implement physical, link and network which are intentionally kept simple (and thus allows hardware implementations for high performance).

Physical:

• Bits to modulation of signal
• Specifies signal, modulation, bit synchronization etc.

Link:

• MAC: flow control etc.
• LLC: frames, error detection/coding, retransmission

Network:

• Addressing and routing; end-to-end delivery of messages
• Specifies addressing format, exchange of routing information, possibly establishment etc. of connections

Transport:

• Reliable, in-sequence, transparent end-to-end transfer
• Error control to guard against routers dropping packets
• Congestion control (stopping network overload, fair resource allocation) and end-to-end flow control (stopping receiver overload)

Session:

• Communication sessions between applications
• May involve several transport layer connections
• Controls duplex/half-duplex/simplex operation

Presentation:

• Endian conversion

Application:

• High-level support functions e.g. HTTP

TCP/IP reference model: physical/network interface/internet/transport/application.

Transport:

• End-to-end communication using the socket interface
• SAPs called ports; multiplexing over a single network adapter
• PDUs generated by this layer called segments

Service Primitives

Confirmed service:

• User A sends request (with data?)
• Provider A generates PDU(s)
• Provider B receives PDU(s), sends indication to user B
• User B generates response (with data?)
• Provider B generates response PDU
• Provider A receives response, sends confirm to user A

Unconfirmed: no response or confirm e.g. UDP.

Confirmed Delivery: Provider B sends PDU when request PDU received regardless what user B does.

Multiplexing:

• Several N SAPs transmitting data over a single N-1 SPA
• Scheduling to determine which SAP to serve
• Requires identifier (e.g. port numbers)

Splitting:

• Single N entity using several N-1 SAPs
• Scheduling to determine which SAP to use for a given PDU
• May require sequencing mechanisms

Fragmentation:

• When PDU is too large for the lower-layer protocols; partition into fragments
• Numbering of fragments

Blocking:

• Buffering small SDUs into a single PDU
• Markers required to separate SDUs

Physical Layer

• Formatting: ADC - source signal into digital data
• Source coding/compression. Lossy coding/relevancy reduction and lossless/redundancy reductiom
• Channel coding: adding redundant information for error correction - reduces bit-error probability
• Modulator: maps bits to physical signal/waveform of a certain duration - symbol time
• Baseband transmission. Bipolar NRZ: 1=x V, 0=-x V. Unipolar: 1=x V, 0=0 V
• Attenuation: signal power at transmitter divided by receiver. Lower is better
• Thermal noise: normal distribution added to signal

Passband transmission:

Where t is less than duration T, the symbol duration, A(t) is the amplitude, f(t) is the frequency offset, f_c is the center frequency and \phi(t) is the phase.

• Amplitude shift keying: varies A(t) for each symbol
• Frequency: varies f(t) for each symbol
• Phase: varies \phi(t)

Quadrature Amplitude Modulation: varies amplitude and phase. n unique amplitudes and n unique phases for n^2 symbols. Greater throughput but higher error rate.

Carrier synchronization: synchronizes frequency and phase.

NRZ can lead to long runs of the same bit and loss of synchronization.

Manchester encoding: [-x, x] voltage range:

• 1: high to low in middle of symbol duration
• 0: low to high “”

Frame synchronization, ethernet: preamble at start for carrier synchronization, then start-frame-delimiter.

End of frame detection: gap between frames, deliberate code violations, dedicated length fields, special flags (with escape codes).

LAN

Geometric RV:

• Type 1, Bernoulli trial: returns probability of k failures before success: P(k)=p(1-p)^k, Expected value is (1-p)/p

• Type 2, probability of k trials before first success: P(k)=p(1-p)^(k-1), expected value 1/p

• Bus: tap line attaches all stations to bus. Broadcast medium

• Star: private full-duplex channel for each station. Central un it is a repeater or bridge/switch

• MAC: multiple stations, shared channel usable by one station at a time, no other channels, broadcast medium

• Want: small medium access delay, fairness, reuse of resources, low overhead, stability

Orthogonal: behavior of one station independent of another.

Frequency division multiple access:

• Bandwidth divided into sub-channels + guard channels
• Separate receivers/tunable receiver - latter requires switching before transmission starts
• 0 medium access delay, B/n bandwidth

Time:

• Full bandwidth for 1/n of the time. Avg MAD is half superframe time plus B/n
  • Avg better than FDMA for n>2
• Requires time synchronization

Both require some way of allocating sub-channels/time slots.

Random access protocol: no central station/shared state.

ALOHA:

• Transmit packet + checksum immediately
• Receiver sends immediate ack
• If timer expires, random backoff time chosen; repeat until threshold reached
• vulnerability period: if a station sends a packet of size n, vulnerability period one frame before and during sending of packet (if that packet has the same size)
• Unstable for high loads due to increasing collision rates

CSMA - carrier sense multiple access. Carrier sense: almost instantaneous check of if the medium is busy. Fails if time difference between two stations starting collisions is smaller than the propagation delay.

Non-persistent CSMA:

• If medium busy, generate random backoff time, then check again
• High probability of medium being idle after transmission finishes

p-persistent CSMA:

• Time is divided into very small frames
• Once medium is free, probability p of starting transmission. If collision occurs, restart
• If defers, repeats the process the next time slot
• Low p leads to stability in high load but low throughput in low load

1-persistent: CMSA/CD:

• Send unconditionally at end of transmission: avoid idle time
• Detect collision immediately if multiple stations transmit
  • Abort transmissions
  • Send jamming signal
  • Begin collision resolution

Ethernet

Manchester Encoding:

MAC address: 48 bit globally unique. If first of address is 1, multicast. Else, unicast address.

If L/T >= 1500, type field (e.g. IPv4, ARP) to allow for protocol multiplexing. Else, length field. Type assumed to be first two bytes of payload.

Broadcast: half-duplex, MAC needed, 10 Mbps PHYs.

MAC protocol: CSMA/CD:

• coll set to zero

• Carrier-sense; once medium idle, transmission starts immediately

• If collision detected

  • Abort, send jamming signal, increment coll
  • Drop packet if coll > 16
  • Wait for backoff time
    • Backoff window: [0, 2^{min(10, coll) - 1}]
    • Multiply by slot time; predefined time large enough for max round-trip time

• Minimum frame size: transmitter can only detect collision while it is still transmitting by measuring voltage on medium

• Repeater: amplify signal on analog level

• Regenerating repeater: demodulate then modulate on a symbol-by-symbol level. No error checking

• Hub: centralized repeater; broadcast signals to all ports. Basically a bus

• Bridge: interconnects LANs on the MAC layer - must have the same MAC address structure

  • Peeks at source address to learn what stations are on what LANs
  • If destination address unknown, broadcasts packet to all other LANs

• Switches: private full-duplex links for all stations. Frames transmitted to only the correct port - allows parallel transmissions

IP

Big endian byte ordering

Last fragment has MF unset, and non-zero FragmentOffset to differentiate from an unfragmented packet.

Protocol type: determines higher-level protocol that generated the payload (e.g. UDP/TCP).

Routing table: map from destination address to output port.

Host address of all 0s: network as a whole being referred to. All 1s: broadcast address.

Lookup:

• Check for full host address match
• Check for network address match
• Use default
• Drop packet, send ICMP message

End hosts have default route + entry for each network it is directly connected to.

Core routers: know almost all internet networks, have no default routers.

Address Resolution Protocol: map from IP to MAC:

• Each has ARP cache, entries discarded fixed time after insert (or last use)
• Broadcast message containing own IP/MAC + IP of target
• Target responds with own IP/MAC plus requester IP/MAC

Internet Control Message Protocol - optional protocol used to inform sender of error.