CS168 — Introduction to the Internet

Reliable transport, distance-vector routing, and traceroute — an independent, from-skeleton implementation of CS168 — Introduction to the Internet (UC Berkeley), part of a csdiy.wiki full-catalog build.

Overview

UC Berkeley's CS168 is an introduction to how the Internet works, from the link layer up. Its three programming projects have you build the core protocols by hand and validate them against the course's own simulators and graders:

1. Traceroute — send UDP probes with increasing IP TTLs and parse the returning ICMP errors to reconstruct the path to a host.
2. Routing — a full distance-vector router (Bellman-Ford, split horizon, poison reverse, route poisoning, triggered incremental updates) inside a Python network simulator.
3. Transport — a real TCP: the three-way handshake, in-order/​out-of-order receive reassembly, sliding-window sending with flow control, connection teardown (active/passive/simultaneous close), retransmission, and RFC 6298 RTT-based RTO estimation, running inside the POX tcpip stack.

Everything here is my own implementation on top of the official course skeletons; the simulators and autograders are the course's own.

Results (measured on this machine — Windows + WSL2 Ubuntu, CPU only)

Project	What it does	Result (measured, course grader)
P1 Traceroute	IPv4/ICMP/UDP header parsing + TTL probe loop	5/5 offline parser & path-reconstruction tests pass
P2 Routing (DV)	Distance-vector router, stages 1–10	100.00 / 100.00 — 59/59 unit tests (dv_unit_tests.py)
P3 Transport (TCP)	TCP over POX tcpip, stages 1–9	29/30 stage autograder tests pass (s1–s9); the one miss is a congestion-control artifact, not a correctness bug — see Verification

Raw captured grader output lives in results/:

• results/proj1_traceroute_tests.txt
• results/proj2_dv_unit_tests.txt
• results/proj3_autograder.txt

Proj2 distance-vector grader (excerpt)

Stage 1 TestStaticRoutes                   :  1 / 1  passed
Stage 2 TestForwarding                     :  4 / 4  passed
...
Stage 10 TestTriggeredIncrementalUpdates    : 31 / 31 passed
Total score: 100.00 / 100.00

Proj3 TCP autograder (excerpt)

PASS  s1_t1  s1_t2                            (handshake)
PASS  s2_t1 .. s2_t6                          (in-order receive)
PASS  s3_t1 .. s3_t5                          (out-of-order receive / reassembly)
PASS  s4_t1 .. s4_t5                          (windowed send)
PASS  s5_t1  s5_t2                            (flow control)
PASS  s6_t1  s6_t2  s7_t1  s7_t2              (passive + active + simultaneous close)
FAIL  s8_t1   PASS s8_t2  s8_t3              (retransmission — see note below)
PASS  s9_t1 .. s9_t3                          (RFC 6298 RTO)

Implemented assignments

• Project 1 — Traceroute (proj1-traceroute/traceroute.py): parse IPv4, ICMP and UDP headers by hand; send UDP probes over TTLs [1, 30]; match ICMP time-exceeded (11/0) and port-unreachable (3/3) responses back to the probe by inspecting the quoted inner datagram; up to 3 attempts per hop.
• Project 2 — Distance-Vector Routing (proj2-routing/simulator/dv_router.py): static routes, data forwarding, route advertisement, Bellman-Ford relaxation, route expiry, split horizon, poison reverse, count-to-infinity handling, route poisoning, and triggered incremental updates with a per-port advertisement history.
• Project 3 — Transport / TCP (proj3-transport/ext/cs168p2/student_socket.py): a full stateful TCP socket — SYN/SYN-ACK/ACK handshake, acceptability checks, receive queue with in-order delivery, MSS segmentation and windowed sending, advertised-window flow control, cumulative-ACK processing, the FIN state machine (FIN_WAIT_1/2, CLOSING, CLOSE_WAIT, LAST_ACK, TIME_WAIT), a retransmission queue with timeout retransmit and exponential backoff, and RFC 6298 SRTT/RTTVAR/RTO estimation.

Project structure

cs168-internet/
├── proj1-traceroute/
│   ├── traceroute.py           # my implementation
│   ├── util.py                 # course-provided socket helpers
│   └── test_traceroute.py      # offline parser + loop verification
├── proj2-routing/
│   ├── simulator/
│   │   ├── dv_router.py        # my implementation (stages 1–10)
│   │   └── dv_unit_tests.py    # course grader (100/100)
│   └── netvis/                 # course-provided visualizer
├── proj3-transport/
│   ├── ext/cs168p2/
│   │   ├── student_socket.py   # my implementation (stages 1–9)
│   │   ├── autograder.py       # course autograder
│   │   ├── run_tests.sh        # timeout-safe wrapper (see Verification)
│   │   └── tests/              # course test configs
│   ├── ext/tcpip/              # course-provided POX TCP/IP stack
│   └── pox/                    # POX SDN framework (Apache-2.0)
└── results/                    # captured grader output

How to run

Python 3.11 (shared csdiy venv) for proj1/proj2. Proj3 runs its POX simulator under WSL2 Ubuntu.

# --- Project 1: traceroute ---
cd proj1-traceroute
python test_traceroute.py                 # offline verification (no root needed)
sudo python traceroute.py google.com      # real run (needs raw-socket / root)

# --- Project 2: distance-vector routing ---
cd proj2-routing/simulator
python dv_unit_tests.py                    # course grader -> 100.00 / 100.00

# --- Project 3: TCP transport (in WSL2 Ubuntu) ---
cd proj3-transport/ext/cs168p2
./run_tests.sh                             # runs every stage; prints PASS/FAIL
./run_tests.sh s8                          # just stage 8

Verification

• P1 is verified offline by proj1-traceroute/test_traceroute.py, which builds byte-exact IPv4/ICMP/UDP packets to check the header parsers, then drives traceroute() against a scripted fake socket (two routers + an ICMP port-unreachable from the destination) and asserts the reconstructed path. (The live tool needs a raw ICMP socket, i.e. root/admin.)

• P2 is verified by the course's own dv_unit_tests.py, which scores all ten stages: 100.00 / 100.00.

• P3 is verified by the course autograder's per-stage test configs. Each config drives the POX simulator and prints All checks passed, test PASSED on success. 29 of 30 stage tests (s1–s9) pass, and every stage has passing tests. Data delivery, the handshake, reassembly, flow control, the full close state machine, retransmission, and RFC 6298 RTO all verify.

  The single miss is s8_t1. In it the peer drops the ACKs for the start of the payload but not the end, and the test asserts the sender therefore never retransmits (a later cumulative ACK covers everything). Passing it requires the sender to space its segments across round trips so the receiver emits enough separately-delayed ACKs that some "end of payload" ACKs survive the drop — i.e. it requires slow-start pacing. This project's spec explicitly states the implementation "won't include congestion control" (see the CS168 proj3 spec), so without a congestion window the sender bursts all ten segments at once, the receiver coalesces them into six delayed ACKs, all six are dropped, and the sender legitimately retransmits once. The payload is still delivered correctly — the test's payload check passes; only its "exactly 10 packets, no retransmissions" count fails. This is a limitation of the assignment's scope, not of the implementation.

  Note: the bundled autograder.py gives each POX test only 5 seconds to start and finish (wait_finish). On modern CPython (3.11/3.12) POX's startup alone can exceed that, so autograder.py reports false timeouts even for a correct implementation. run_tests.sh runs the exact same test configs directly with pox.py without that artificial cap and greps the same pass marker — identical scoring, no harness flakiness.

Tech stack

Python 3.11 / 3.12 · raw sockets (traceroute) · the CS168 network simulator (Project 2) · the POX SDN framework and its tcpip stack (Project 3) · WSL2 Ubuntu for the Project 3 simulator.

Key ideas / what I learned

• Traceroute is entirely a TTL + ICMP trick: you never talk to the routers directly — you provoke time-exceeded errors and read the source address off the ICMP packet, correlating it to your probe via the quoted original header.
• Distance-vector routing's hard parts aren't Bellman-Ford — they're the count-to-infinity pathologies and the mitigations (split horizon, poison reverse, route poisoning, triggered updates) that keep the network from believing in phantom routes.
• Implementing TCP makes the sequence-space modular arithmetic concrete: every comparison is mod-2³² (|LT|, |GE|, |PLUS|), and SYN/FIN each consume one byte of that space.
• The FIN state machine is where TCP's subtlety lives: active vs. passive vs. simultaneous close each thread a different path through FIN_WAIT_1/2, CLOSING, CLOSE_WAIT, LAST_ACK, and TIME_WAIT.
• Correct retransmission needs RFC 6298's timer discipline: restart the RTO timer on every ACK that makes forward progress, or you retransmit perfectly good in-flight data the moment a few ACKs are delayed.

Credits & license

Based on the programming projects of CS168 — Introduction to the Internet by UC Berkeley (course site: https://sp25.cs168.io/). This repository is an independent educational reimplementation; the network simulator, the POX framework and its tcpip stack, the autograders, and all course materials belong to their original authors (POX is Apache-2.0). Original code I wrote (traceroute.py, dv_router.py, student_socket.py, and the tests) is released under the MIT License.