intro

OSI and TCP/IP models

	OSI	Five-layer	TCP/IP
Data	Application	Application		Software
Data	Presentation
Data	Session
Segment	Transport (תעבורה, תובלה)			Hardware/Software
Packet	Network	Internet (or Network)		Hardware
Frame	Data Link (קו, ערוץ)		Link (or Network Access) (קשר, ערוץ)
Bit	Physical

Link layer

• Link Classification

  • Last-Mile
  • Backbone
  • LAN

• Connection-oriented service

• Connection-less service

Framing

• A frame

Point-to-Point Protocol (PPP)

Byte-Oriented

1 byte	1	1	2		2	1 byte
Flag (0x7E)	Address (0xFF)	Control (0x03)	Protocol	Information (payload)	FCS (Frame Check Sequence)	Flag (0x7E)
	Header			Data	Footer

• Link Control Protocol (LCP)

High-Level Data Link Control (HDLC)

bit-oriented

Error detection and correction

• A message (סיביות מידע, מילת מידע) $M$ of length $m$.

• Redundant bits (סיביות ביקורת) $R=f(M)$ of length $r$ (where $r\ll m$).

• The sender transmits the codeword (מילת קוד) $P=(M,R)$ of length $n=m+r$.

• The receiver receives $(M^{\prime },R^{\prime })$ and checks if $R^{\prime }=f(M^{\prime })$, if yes, assume no error with high probability, else, error detected.

• (code rate) $R_c=\frac{m}{n}$

• (overhead, תקורה) $\frac{r}{n}$

• (redundancy) $\frac{r}{m}$

• A bit error is when a bit is received incorrectly (0 instead of 1 or vice versa)

• A burst error is when a sequence of bits is received incorrectly

• (bit error ratio) $\text{BER}=\frac{\text{\# bit errors}}{\text{Total transmitted bits}}$

• (bit error probability) $p_e=\mathrm{E}[\text{BER}]$

נצילות השידור

parity checks

• even parity: $R=0$ if number of 1s in $M$ is even, else $R=1$
• odd parity: $R=0$ if number of 1s in $M$ is odd, else $R=1$
• two-dimensional parity check: $\begin{array}{cccc}{b}_{1,1}& \cdots & b_{1,j}& r_1\\ b_{2,1}& \cdots & b_{2,j}& r_2\\ ⋮& \ddots & ⋮& ⋮\\ b_{i,1}& \cdots & b_{i,j}& r_i\\ c_1& \cdots & c_j& p\end{array}$
  • $M$ is an $i\times j$ matrix of bits $b_{m,n}$
  • row parity bits $r_m$ for each row $m$
  • column parity bits $c_n$ for each column $n$
  • overall parity bit $p$

internet checksum

(note: used in IP, not used in link layer)

• message is divided into words of 16 bits: $w_1,w_2,\dots ,w_m$
• the checksum is $R=\sim (w_1+w_2+\dots +w_m)$ (where $\sim$ is the bitwise NOT operation. The sum is done using ones’ complement addition)
• the sender sends $(M,R)$
• the receiver computes $S=w_1^{\prime }+w_2^{\prime }+\dots +w_m^{\prime }+R^{\prime }$ (using ones’ complement addition) and checks if $\sim S=0$, if yes, assume no error, else, error detected

cyclic redundancy check (CRC)

• the message has $n+1$ bits
• $G(x)$ is the generator polynomial of degree $k$
• $M(x)$ is the message polynomial of degree $\text{deg}(M)\le n$
• the transmitted word will be a polynomial $T(x)$ of degree $n+k$ such that $G(x)\mid T(x)$.
• $T(x)$ construction:
  1. multiply $M(x)$ by $x^k$ to get $M^{\prime }(x)=M(x)\cdot x^k$
  2. divide $M^{\prime }(x)$ by $G(x)$ to get the remainder $R(x)$
  3. compute $T(x)=M^{\prime }(x)-R(x)$
• the receiver receives $T^{\prime }(x)=T(x)+E(x)$ where $E(x)$ is the error polynomial (non-zero coefficients indicate bit errors)
• the receiver checks if $G(x)\mid T^{\prime }(x)$, if yes, it means that $E(x)=0$ (no error), else, error detected

Error control

Stop-and-wait ARQ

sender:
	n = 0 
	while true:
		send frame[n]
		if ack[n] received within T time:
			n = n + 1
		else: # timeout, we start over

receiver: 
	expected = 0
	while true:
		receive frame[n]
		if n == expected:
			deliver data to upper layer
			expected = expected + 1
		send ack[n]
		

Sliding window protocol

• sender:

  • constants:
    • SWS: send window size
  • variables:
    • LFS: last frame sent
    • LAR: last frame acknowledged
    • $\text{Send Window}=[\text{LAR}+1,\text{LFS}]$
  • invariant:
    • $\text{LFS}-\text{LAR}\le \text{SWS}$
  • algorithm:
    • if ack for frame k received and $k>\text{LAR}$:
      • set $\text{LAR}=k$
    • if $\text{LFS}-\text{LAR}<\text{SWS}$:
      • send frame $\text{LFS}+1$
      • increment $\text{LFS}$
    • if timeout for frame k:
      • resend frame k

• receiver:

  • constants:
    • RWS: receive window size, s.t. $\text{RWS}\le \text{SWS}$
  • variables:
    • LAF: last acceptable frame
    • LFR: last frame received
    • $\text{Receive Window}=[\text{LFR}+1,\text{LAF}]$
  • invariant:
    • $\text{LAF}-\text{LFR}\le \text{RWS}$

• $\text{SWS}<\frac{1}{2}\times (\text{MaxSeqNum}+1)$

• negative acknowledgment

• selective acknowledgments

  • the receiver could acknowledge exactly those frames it has received rather than just the highest numbered frame received in order

• Go-Back-N ARQ

  • $\text{RWS}=1$
  • $\text{SWS}=N$

• Selective Repeat ARQ

Ethernet

Frame format (Ethernet II)

	Ethernet frame (64–1522 bytes)
Ethernet packet (72–1530 bytes)
Preamble	Dest addr	Src addr	EtherType	Payload	CRC
8 (bytes)	6	6	2	46-1500	4

MAC address

MAC address (12 hex digits = 6 bytes = 48 bits)
XX:XX:XX:XX:XX:XX
XX:XX:XX	XX:XX:XX
OUI (Organizationally Unique Identifier)	NIC (Device Identifier)

• unicast address:

• broadcast address: FF:FF:FF:FF:FF:FF = all 1s

  • an adpaptor will pass all frames addressed to this address up to host

• multicast address: the first bit is 1 but the address is not the broadcast address

  • an adpaptor can be configured to accept frames addressed to set of multicast addresses

• Ethernet adaptor receives all frames, but accepts only:

  • frames addressed to its unicast address
  • frames addressed to the broadcast address
  • frames addressed to multicast addresses it is configured to accept
  • (all frames if in promiscuous mode)

• Classic Ethernet uses the 1-persistent CSMA/CD

CSMA

• Carrier Sense Multiple Access (CSMA)
  • CSMA/CD (Collision Detection)
  • CSMA/CA (Collision Avoidance)

$t_{\text{tx}}\ge 2\cdot t_{\text{prop}}$

• The slot time is the time to transmit the minimum frame size, given by $\text{slot-time}=\frac{n_{\text{min}}}{R}=2\frac{d_{\text{max}}}{v}$
  • $d_{\text{max}}$ is the maximum distance of the Ethernet segment (in meters)
  • $n_{\text{min}}$ is the minimum frame size (in Ethernet, 512 bits (= 64 bytes))
  • (10 Mbps Ethernet) $51.2\mu \mathrm{s}=\frac{512\text{bits}}{10\times 10^6\text{bps}}$
  • (100 Mbps Ethernet) $5.12\mu \mathrm{s}=\frac{512\text{bits}}{100\times 10^6\text{bps}}$
• $a=\frac{t_{\text{prop}}}{t_{\text{tx}}}$
• backoff time = $k\times \text{slot time}$,
  • $k$ is a random integer in $[0,2^n-1]$
  • $n$ is the number of collisions for the frame (up to a maximum value, e.g., 10)
  • algo:
    • $n=0$
    • while not transmitted:
      • choose random $k$ in $[0,2^n-1]$
      • wait $\text{backoff time}=k\times \text{slot time}$
      • try to transmit
      • if collision:
        • $n=\min (n+1,n_{\text{max}})$

access methods

1-persistent

flowchart TD
    C{Channel Status?} -->|Busy| C
    C -->|Idle| F[Transmit Frame]
    F -->|successful transmission| A[done]
    F -->|collision| R[Wait random time] --> C

p-persistent

flowchart TD
    C{Channel Status?}
    
    C -->|Busy| D[Wait for Next Time Slot]
    D --> C
    
    C -->|Idle| E{Random}
    
    E -->|Random ≤ p| F[Transmit Frame]
    E -->|Random > p| D
    
    F -->|successful transmission| A[done]
    F -->|failed transmission| C
    

non-persistent

flowchart TD
	A[has data to send?] -->|yes| C
    C{Sense: Channel Status?}
    
    C -->|Busy| D[Wait random time] --> C
    C -->|Idle| F
    
    E{Random}
    F[Transmit Frame]