464 Exam 1 Content

Network Reference Model

1. Application (HTTP, DNS, IMAP, SMTP)

2. Transport (TCP, UDP, MPTCP, QUIC, End-to-end datagrams)

3. Network (IP, DSR, AODV, DSDV, ICMP)

4. Data Link (Ethernet, 802.11, Bluetooth)

5. Physical (Bits on wire)

TCP

• Reliable ordered delivery (with retransmission if necessary)

• Congestion Avoidance and Control

• ACK sent to sender as confirmation after data received by receiver

• Issues: Often guesses wrong reason for packet loss in wireless (mobility and interference usually are the reason more than congestion)

• Establish connection: Handshake 🙂 SYN (send open packet), SYN ACK (acknowledgement from dest), ACK (acknowledgement of dest ACK from src)

• Closing connection: FIN (Close and receive remaining bytes), FIN ACK (acknowledgement), RST (Reset to close and NOT receive remaining packets)

• ACKs is src’s sequence number + 1

• Sends acknowledgements to sender to confirm delivery

Window Size

• Amount of data sent per round trip time

• Receiver’s advertised window (available buffer space)

• Congestion window (determined by sender from network feedback)

Packet Loss

• Detected by Retransmission Time Out (RTO) and DUPACKs

• DUPACK: Fast Retransmission indicates packet loss if 3 DUPACKs received. Retransmit after.

• RTO: If ACK not received before RTO timer fires, packet lost. RTO doubles for each time-out.

Congestion Avoidance & Control

• Slow Start: Exponential cwnd

• Congestion Avoidance: Linear cwnd

• Slow Start Threshold (ssthresh) = max[min(min(cwnd, receiver’s adv. window / 2), 2 * Min Segment Size)]

• Fast Recovery after Fast Retransmit (No Slow Start needed)

• 3 dup acks trigger retransmission

MPTCP

• Implemented in the kernel

• Use sequence numbers to reassemble segments at the receiver

• Benefits: Higher throughput, failover from one path to another, seamless mobility

• Challenges: Out of order packets (RTT differences), hard to retransmit packet on different subflow

• Connection Established same way as TCP, except SYN ACK contains MP_CAPABLE

• ADD_ADDR and REMOVE_ADDR used to add/remove IP addresses to MPTCP connection

• MP_JOIN used to associate new subflow with existing MPTCP connection

• All subflows should add up to one TCP flow

• Contains congestion window for each subflow

• Picking a path depends. Least congested path has low loss, but high RTT, etc

• Uses key during connection setup to verify authenticity of created subflows

• Ex: Primary TCP Wifi connection, Backup TCP cellular connection

TLS/SSL (OpenSSL)

• Handshake done in clear text

• Transport Layer Security and Secure Socket Layer

• Standard for Internet Security

• Uses shared secret keys between client and sever

• Certificate Authorities (CA) verify public keys from websites

QUIC

• UDP is connectionless, so less reliable but faster than TCP

• Uses TCP congestion control

• Uses NON-blocking transport protocol

• Used for time-sensitive transmissions mostly

• Combines UDP speed with TCP reliability (hard to make changes in TCP, faster to implement new protocol on UDP)

• Lost packets only impact the individual resource

• Encrypted

• Helps with congestion control and loss recovery

Routing protocols

• Reactive (high latency, low overhead): DSR, AODV

• Proactive (low latency, high overhead): OLSR, DSDV

• Next-hop tables: AODV, OLSR, DSDV

• Floods control packets: DSR, AODV

Dynamic Source Routing (DSR)

• Route discovery

  • Src floods RREQ to each node up to Dest, each adding its own identifier when forwarding

  • Dest sends RREP through reverse route

  • Does not work for non-bidirectional routes

• Schemes reduce impact of Broadcast storm problem (multiple nodes broadcast the same message simultaneously, leading to collisions and redundancy)

• RERR received means broken link will be removed from from route cache.

• Large packet header (entire path)

• Intermediate nodes can send RREP if they already know path to dest

Ad Hoc On-Demand Distance Vector Routing (AODV)

• Maintains routing tables (with reverse path) at nodes to avoid large packet headers and improve performance.

• Uses destination sequence numbers to avoid loops

• Only maintains routes when necessary

• Doesn’t work with asymmetric routes

• Intermediate nodes can send RREP if they already know path to dest (less likely than in DSR)

• Timeout for routing tables to avoid stale routes

• Dest. Sequence numbers used to avoid old/broken routes and loop formation

Link State Routing (LSR)

• Nodes periodically floods the status of its links to all other nodes to maintain a complete view of the network (node id, cost of link to each neighbor)

• Routing table computed after LSP received for all nodes

• Uses Dijkstra’s Algorithm to find shortest path

• Not scalable

Optimized Link State Routing (OLSR)

• Optimized LSR which requires fewer nodes to forward LSP

• Multipoint relays used: each 2 step neighbor of src is a 1 hop neighbor of at least one MPR

Distance-Vector Protocol (DV)

• Nodes maintain a table (sent to neighbors periodically) of:

  • available destinations

  • next node to reach each destination

  • number of hops to each destination

• Broken links lead to loops and count to infinity

• Doesn’t do well with mobility

Destination-Sequenced Distance-Vector (DSDV)

• Uses sequence numbers to prevent loops

• Routing table:

  • Next hop

  • Cost path to each dest

  • Dest. seq num

  • Seq num

• Each time table is advertised, sequence number increases to next even number

• If dest num received from another node is greater, we change our sequence number to it and that node is the next hop