Errors

Question 1

Cyclic Redundancy Check - Can detect

Answer 1

Detects all single bit errors, almost all 2-bit errors, any odd number of errors, all bursts up to M (where generator length is M), longer bursts with probability 2^-m.

Question 2

Cyclic Redundancy Check - Implementation

Answer 2

Hardware - shift register which is easy with ASIC/FPGA

Software - precompute remainders for 16-bit words, add remainders to a running sum, needs only one lookup per 16-but block

Question 3

CRC - TCP/UDP/IP

Answer 3

Treat data bytes as 16-bit integers, add with end-around carry, one’s complement = checksum, catches all 1-bit errors, longer with low prob

Question 4

Types of Packet Error

Answer 4

Loss, Duplication, Insertion, Reordering

Question 5

Sequence Numbers

Answer 5

Contain in each header, increment for non-retrnasmitted packets.

Using them:

loss - gaps indicate
reordering - trivially
duplication - trivially
insertion - if received seq # is v. different

Question 6

Sequence number size

Answer 6

Must be long enough so sender does not confuse sequence numbers on acks.

2^seq_size > R(2 MPL + T + A) where R is rate, MPL is maximum packet lifetime, T is timeout time, A is time taken for receiver to respond)

Question 7

MPL

Answer 7

Maximum Packet Lifetime

Bounded by counter in header which is decremented per hop.

Question 8

Packet Insertion

Answer 8

Packets have source IP, dest IP, source port, dest port. Insertion occurs if open connection to B, then terminate on transport layer, then open new connection with same port numbers and delayed packet from old connection arrives.

Question 9

Preventing Packet Insertion

Answer 9

Per-connection incarnation number -incremented for each connection from each host. (Takes up header space and may repeat on crash)

Reassign port numbers only after 1 Maximum Packet Lifetime

Wait 1 MPL after boot up to flush old packets from network.

Question 10

3-way handshake

Answer 10

Protects against delayed SYNs

Question 11

Timeout Schemes - Static

Answer 11

Know round trip time a priori
Timer set to this value
Works well when RTT changes little

Question 12

Timeout Schemes - Dynamic

Answer 12

Measure RTT

Timeout is a function of measured RTTs

Question 13

Timeout Schemes - Old TCP

Answer 13

RTTs are measured periodically.

Smoothed RTT:

srtt = a * srtt + (1-a) * RTT

timeout = b*srtt

a = 0.9, b=2

bad in practice

Question 14

Timeout Schemes - New TCP

Answer 14

Introduce new term = mean deviation from mean

m = |srtt - RTT|
sm = a *sm + (1-a) * m

timeout = srtt + b*sm

Question 15

Go Back N Retransmission

Answer 15

On timeout, retransmite entire error control window so receiver only accepts in-order packets. Used in TCP.

Question 16

Selective Retransmission

Answer 16

Find out which packets lost then only retransmit them. Each ack has bitmap of received packets, sender periodically asks receiver for bitmap, fast retransmit.

Question 17

Fast Retransmit

Answer 17

Assume cumulative acks, if sender sees repeated cumulative acks, packet likely lost, send cumulative_ack + 1.

Question 18

SMART

Answer 18

Ack carries cumulative sequence number also sequence number of packet causing ack. Sender creates bitmap so no need for timers. If retransmitted packet lost, periodically check if cumulative ack increased.