Systems engineering · UChicago coursework · Winter 2019

Telegraph

An IRC server, IP router, and TCP/IP stack, built from scratch in C.

Three layers of the network, each relaying to the next. Three networking systems, one C codebase apiece: an IRC server — parsing, channel state, the numeric reply protocol end to end. An IP router — ARP, ICMP, longest-prefix forwarding — run as the data plane under an OpenFlow controller against real simulated topologies. A TCP/IP stack implementing the state machine itself, with its own retransmission timing and out-of-order buffering.

The instrument

Nineteen IRC commands, one dispatcher

NICK, JOIN, PRIVMSG, MODE, WHOIS, and more route through a single command dispatcher, channel and user state tracked separately from the wire-format reply layer.

ARP resolution queues packets, not requests

An unresolved lookup doesn't block the router — the pending frame waits on the address and forwards the moment the reply lands. ICMP echo, unreachable, and time-exceeded handled alongside it.

Tested against real topologies

The router ran as the data plane under an OpenFlow controller driving live Mininet topologies — checked against simulated network traffic, not just a canned test harness.

A TCP state machine with all the unglamorous states

The full set — SYN_SENT through TIME_WAIT — backed by its own retransmission queue, a custom timer, and buffering for segments that arrive out of order.

The movement

The engineering underneath

Three binaries, one problem repeated — state that has to stay correct while the network around it isn't.

RTO tracked by hand

A per-connection retransmission queue recomputes its timeout as ACKs arrive, off a floor value, through a small custom timer rather than one OS timer per connection.

tcp.c

int chitcpd_update_RTO(tcp_data_t* data, retrans_q_t* retrans_packet)
{
    struct timespec curr_time;
    clock_gettime(CLOCK_REALTIME, &curr_time);

    struct timespec ts_rtt;
    timespec_subtract(&ts_rtt, &curr_time, &retrans_packet->time_sent);

    uint64_t rtt = ts_rtt.tv_sec * SEC + ts_rtt.tv_nsec;

    if (data->RTO == (1 * SEC))
    {
        data->SRTT = rtt;
        data->RTTVAR = rtt / 2;
        data->RTO = data->SRTT + max(G, K * data->RTTVAR);
    }
    else
    {
        data->RTTVAR =
            (1 - BETA) * data->RTTVAR + BETA * abs(data->SRTT - rtt);
        data->SRTT = (1 - ALPHA) * data->SRTT + ALPHA * rtt;
        data->RTO = data->SRTT + max(G, K * data->RTTVAR);
    }

    if (data->RTO < MIN_RTO)
    {
        data->RTO = MIN_RTO;
    }
    return CHITCP_OK;
}

Out-of-order segments get buffered, not dropped

A segment ahead of the expected sequence number is held and folded back into the stream once the gap closes.

tcp.c

int insert_ooo_packet(tcp_packet_list_t* pl, tcp_packet_t* packet)
{
    tcp_packet_list_t* node = calloc(1, sizeof(tcp_packet_list_t));
    node->packet = packet;

    DL_INSERT_INORDER(pl, node, cmp_ooo);

    return CHITCP_OK;
}

ARP doesn't stall forwarding

Pending requests and their frames sit in their own list; other traffic keeps moving while one address resolves.

arp.c

int chirouter_arp_pending_req_add_frame(chirouter_ctx_t *ctx, chirouter_pending_arp_req_t *pending_req, ethernet_frame_t *frame)
{
    ethernet_frame_t *frame_copy = calloc(1, sizeof(ethernet_frame_t));

    frame_copy->raw = calloc(1, frame->length);
    memcpy(frame_copy->raw, frame->raw, frame->length);
    frame_copy->length = frame->length;
    frame_copy->in_interface = frame->in_interface;

    withheld_frame_t *withheld_frame = calloc(1, sizeof(withheld_frame_t));
    withheld_frame->frame = frame_copy;

    DL_APPEND(pending_req->withheld_frames, withheld_frame);

    return CHITCP_OK;
}

Specification

Language: C
Protocols: IRC · IP + ARP + ICMP · TCP
Simulation: Mininet topologies driven by an OpenFlow controller
Testing: Automated suite per subsystem
Origin: University of Chicago · CMSC 23300 (Networks and Distributed Systems) · Winter 2019
Team: Partner project, completed with one collaborator