Homework 6

Changelog

  • v1: December 2, 2019

Overview

This homework assignment asks you to solve some brief pencil-and-paper exercises on the topics covered over the last few weeks of the course. You should write up your solutions to all exercises in a file named solutions.pdf and submit it on CMS.

Due Date

  • 11:59pm, December 10, 2019

Academic Integrity

This assignment must be completed individually. All work you submit must be your own and sharing or receiving code is forbidden, with the exception of your partner. Do not look for or submit code you find on the Internet, and do not post solutions or partial solutions on the discussion site. If you make use of any outside materials, you must give attribution. You may ask general questions discuss high-level details of the exercises with your classmates. If you have any questions about what is allowed and what is not allowed, please ask the instructor first!

Exercise 1: P4 Program Repair

Consider the following declarations from a P416 program written against the V1Model architecture:

action forward(bit<9> port) {
  hdr.ipv4.ttl = hdr.ipv4.ttl - 1;
  standard_metadata.egress_spec = port;
}
action drop() {
  mark_to_drop(standard_metadata);
}

table l3_routing {
  key = { hdr.ipv4.dstAddr : lpm }
  actions = { forward; drop; }
}

You may assume that the type of hdr is a struct containing Ethernet and IPv4 headers and that thee parser populates these headers using the standard algorithm.

Now suppose that the apply block for the ingress control is defined as follows:

apply { 
  l3_routing.apply(); 
}

Clearly the programmer intended to implement basic destination-based forwarding. More precisely:

  • Given an IPv4 packet, if the control-plane has inserted a prefix-based rule that matches the packet’s destination address, then the corresponding action, either forward or drop should be executed.

  • Given a non-IPv4 packet, or an IPv4 packet for which the control-plane has not inserted a rule that matches the packet’s destination address, the packet should be dropped.

Unfortunately the program does not correctly implement this specfication—e.g., consider what happens to non-IPv4 packets. Your task in this exercise is to repair the program. To make the problem more interesting, we’ll implement two different repair strategies.

  1. For the first repair, add a default_action and modify the apply block to ensure that the desired behavior is implemented.

  2. For the second repair, find a way to modify the declaration of the table (but not the apply block!), and identify suitable control-plane constraints (e.g., you might require that it insert a rule with match 0.0.0.0/0 and action drop) needed to ensure that the desired behavior is implemented.

To submit: write up your solution in a section titled “Repair”

Exercise 2: Latency-Equalized Pathlet Routing

Suppose we are given a network topology with three pathlet routers, A, B, and C arranged in a simple triangle topology. Each router has a single virtual node with the same name (and so we will ignore the distinction between routers and virtual nodes used in the paper on pathlets).

Upon receiving a packet, a router first matches on the top-most pathlet identifier and then executes a sequence of zero or more actions, each of the following form:

  • Pushes one or more pathlet identifiers (e.g., push 7,2)
  • Forwards the packet to an adjacent router (e.g., forward B)

Your task in this exercise is to develop forwarding configurations for A, B and C such that:

  • a packet originating at A with initial pathlet identifiers [1] will eventually delivered to B
  • a packet originating at A with initial pathlet identifiers [2] will eventually delivered to C
  • a packet originating at B with initial pathlet identifiers [3] will eventually delivered to A
  • a packet originating at B with initial pathlet identifiers [4] will eventually delivered to C
  • a packet originating at C with initial pathlet identifiers [5] will eventually delivered to A
  • a packet originating at C with initial pathlet identifiers [6] will eventually delivered to B

However, to make the problem more interesting we will add the additional constraint that all packets should traverse the same number of hops (For an extra challenge – i.e., karma – you could also try to minimize the number of distinct rules.)

You should describe the forwarding configurations by speecifying the concrete entires for the forwarding table on each router.

To submit: write up your solution in a section titled “Pathlets”

Exercise 3: Packet Scheduling

Note: the lecture on Thursday, December 5th will cover ideas that may be useful for completing this exercise. However, the exercise is self-contained, so it should be feasible to complete it from first principles even before attending that lecture.

A push-in first-out queue or PIFO, is a data structure that has been proposed as an abstraction for programmable packet scheduling. To a first approximation, a PIFO can be understood as a priority queue. It allows elements to be inserted at an arbitrary rank but it always removes the element with the smallest rank.

More formally, a PIFO supports the following operations:

  • enqueue(v, n), which inserts v with rank n
  • dequeue(), which removes the element with least rank

We can model many (but certainly not all!) packet scheduling algorithms using PIFOs. For example, to implement simple first-come first-served scheduling, we can insert each packet into the PIFO with increasing rank, computed from a state variable maintained on the switch. In pseudo-code, such a scheduler might look like this:

int rank = 0;
procedure schedule(packet) { 
  rank = rank + 1;
  pifo.enqueue(packet, rank);
}

We are tacitly ignoring issues thaht would arise when the rank variable overflows and “wraps around” back to 0. You may make analogous assumptions in your solution to this exercise.

Intuitively, the switch invokes the schedule procedure when it receives a packet and pifo.dequeue() when it is ready to emit the next packet. Hence, given two flows A and B with three packets that arrive in the following order:

A1 B1 A2 A3 B2 B3

the packets would be transmitted in the same order.

Your task in this exercise is to write pseudo-code to implement round-robin scheduling. Hence, given any of the following interleaving of packets from two flows A and B:

A1 A2 A3 B1 B2 B3
A1 A2 B1 A3 B2 B3
A1 B1 A2 A3 B2 B3
B1 A1 B2 A2 B3 A3

the packets would be emitted in the following order:

A1 B1 A2 B2 A3 B3

For simplicity, you may assume that the packets arrive in a single “burst” so that schedule is invoked on all packets before pifo.dequeue is invoked. (Otherwise a work-conserving scheduler might not implement strict round-robin scheduling depending on the arrival times of the packets.)

To submit: write up your solution in a section titled “Scheduling”

Exercise 4: Course Evaluation

We’re done! I would appreciate hearing any informal feedback about the course (e.g., in your debriefing below). In addition, the College of Engineering likes to see high levels of participation on the official course evaluations. Everyone who submits a course evaluation form will receive full marks for this exercise.

To submit: nothing, but do be sure to fill out the official course evaluation!

Debriefing

  • How many hours did you spend on this assignment?

  • Would you rate it as easy, moderate, or difficult?

  • If you worked with a partner, please briefly describe both of your contributions to the solution you submitted.

  • How deeply do you feel you understand the material it covers (0%-100%)?

  • If you have any other comments, I would like to hear them! Please write them down or send email to jnfoster@cs.cornell.edu

To submit: debriefing.txt