Test Notes

Distance-Vector

Periodically send DxD_x, node xx’s estimates of the least cost path to all nodes in the networks: Dx(y)=min([C(x,v)+Dv(y) for v in neighbors(x)])D_x(y) = min([C(x, v) + D_v(y) \text{ for } v \text{ in } neighbors(x)]), to its neighbors.

Poisoned reverse: if xx routes to zz through yy, xx will say that Dx(z)=∞D_x(z) = \infty, ensuring yy will not route to zz through xx if the link cost changes. This reduces the time to converge when link cost increases.

RIP

Each router reliably floods information about its neighbors and independently calculates the least-cost path to every other router.

Add nearest node not in tree to the tree, calculate distance to each neighbor through the node.

O(n2)O(n^2) algorithm, O(nE)O(nE) messages.

OSPF

Hierarchy

IPv6

When forwarding packet through IPv4 router:

BGP

Pairs of routers, either in the same (iBGP) or different AS (eBGP), exchange information over TCP. If a node advertises a prefix, it promises that it can forward datagrams to the prefix. Some attributes:

Import policy used to accept/reject advertisements.

Route selection uses local preference (policy decision), shortest AS_PATH, closest NEXT_HOP router etc.

Reliable Data Transfer

Internet checksum:

def ones_complement_addition(shorts):
  result = 0
  for short in shorts:
    result += short
    if result > 0xFFFF:
      result -= 0xFFFF
  return result

def checksum(shorts):
  return 0xFFFF - ones_complement_addition(shorts)

def check_checksum(shorts, checksum):
  return 0xFFFF == (ones_complement_addition(shorts) + checksum)

CRC

RDT

1.0: no bit errors, buffer overflows, out-of-order packets, packet loss

2.0: bit errors; checksum. Stop and wait for ACK/NACK after each packet

2.1: 1-bit sequence numbers in case ACK/NACK corrupted

2.2: No NACK. Sends ACK with sequence number - last packet that was received successfully

3.0: bit errors and lost packets. Assumes packets are not reordered in the channel (although this can be solved by having a time to live and sufficiently large sequence space)

Go-Back-N

No more than N unacknowledged packets. Receiver sends cumulative ACK. On timeout, all packets reset.

Selective Repeat

An ACK for each packet.

On timeout, resend oldest packet without ACK. If duplicate packet received, send ACK for that packet again.

Worst case scenario:

To prevent this from being interpreted as a new packet, the sender base number must not be in the receiver window. Hence, the window size must be larger than 2N−12N - 1.

UDP and TCP

UDP

|   16 bits   |      16 bits     |
| Source port | Destination port |
|   Length    |     Checksum     |
|              Data              |

Identified by destination port and IP.

TCP

| 16 bits     | 16 bits           |
| Source port | Destination port  |
|         Sequence Number         |
|      Acknowledgement Number     |
| Flags       | Receive window    |
| Checksum    | Urg. data pointer |
|     Options (variable)          |
|        Application Data         |

Handshake and Termination

Segments with SYN or FIN treated as if they have a 1 byte payload.

Three-way handshake:

  1. Client sends TCP SYN segment
  2. Server replies with SYNACK: ack = client_isn + 1
  3. Client replies with ACK: ack = server_isn + 1, sequence_number = client_isn + 1

Termination:

  1. Client sends FIN
  2. Server responds with ACK
  3. Once connection closed, server sends FIN
  4. Client responds with ACK, waiting twice the max segment lifespan to ensure the ACK arrived

Acknowledgements

ACK: largest byte received (cumulative ACK).

Sender events:

Receiver events:

Timeout value requires finding round trip time: use exponential weighted moving average:

Flow control

Congestion Control

Overflowing router buffers:

Slow start:

AIMD (after first loss):

After 3 duplicate ACKs, half window and move to AIMD.

After timeout, slow start until it reaches half of window size before timeout. Then move to AIMD.

LastByteSent - LastByteAcked <= min(CongestionWindow, ReceiveWindow)

Lab 4

Ping failure modes:

ASes: