route-rs / route-rs

A multithreaded, modular software defined router library, written in rust. Safe, fast, and extensible.

route-rs

A multithreaded, modular software defined router library, written in rust. Safe, fast, and extensible.

Original click modular router: https://github.com/kohler/click Click Paper: https://dl.acm.org/citation.cfm?id=354874

We plan to follow the general concepts of Click, but we want to build Route-rs the way that Click would be built today. Namely:

• Concurrency by default (Using Tokio-rs as a runtime)
• Type safe (Written in Rust)
• Easily Extensible
• Runs in userspace

Much like the original Click, units of computation are loosely defined around processors, which are objects that implement the process function. Processors are wrapped by ProcessorLinks, which is what the library will use to chain computation together, producing a functioning, modular, software-defined router. Processors come in either synchronous or asynchronous flavors. In general, synchronous processors should be used for short transformations; asynchronous processors are intended to carry out more computationally heavy tasks. They may also carry out tasks that wait for some period of time before returning, such as an processor that calls out to a seperate database to make a classificiation.

The router is laid out in a pull fashion, where the asynchronous processors drive the synchronous processors ahead of them, and the asynchronous processors are polled by the runtime. The last processor in the chain, generally a to_device processor that communicates with the networking stack, drives much of the router by trying to fetch packets from the processors connected to its input ports. This provides a nice feature; back-pressure. The processors stop processing packets when they have nowhere to put them, since most processors are "lazy" and do not attempt to fetch new packets unless asked by the processor connected to their output.

route-rs's Issues

Improve Classify Function

The Classify function in ClassifyElement could probably just return the port the packet should be output on, rather than a tuple of (port, packet).

Build integration tests for graphgen

Graphgen creates pipelines from a graph file. Right now, we don't have any tests that this continues to work, and we only have one example crate to test against. We should have an extensible testing framework for these and more examples.

Join element: Investigate use of Crossbeam selectors

Crossbeam provides a Select type that will choose among multiple input channels based on whichever one becomes ready first. This could possibly help with task waking in the JoinElement.

Join Element: Task waking without Overseer

Much like the task_park used in the classify and async elements, we want to be able to use the task_park for thread sleeping in the join element.

Support Join and Classify in graphgen

Right now graphgen doesn't handle any sort of joining or splitting behaviors, so it's hard to write an interesting router with it. We should support JoinElementLink and ClassifyElementLink, which requires a bunch of thought about how to autogenerate the dispatching logic.

Rename "Consumer" and "Provider" to "UpstreamConsumer" and "DownstreamProvider" in concurrent elements

We decided that the Consumer Provider names aren't clear enough in internal discussion. Let's update the Consumers and Providers of AsyncElement, ClassifyElement, and JoinElement with clearer names.

Add support for packet_mmap mode to AF_PACKET crate

See here for more detail.

Create test elements with different input and output types

For testing, we should have an element that takes in an int and outputs a char, for example.

Move router-rs api to it's own crate (route-rs-runtime).

Right now the API lives in a head crate, but we would like the repo to contain multiple independent crates. This will make testing easier, and keep dependencies cleaner in the project. Let's move the API to a crate sub-directory and give it a more descriptive name. #22

Create library element with multiple outputs

Create "basic transformation elements"

This is referring to the elements provided in the Click paper.

These are:

1. ARPQuerier(...) Push. First input takes IP packets, second input takes ARP responses with Ethernet headers. Output emits ARP queries and IP-inEthernet packets. Uses ARP to find the Ethernet address corresponding to each input IP packet’s destination IP address annotation; encapsulates the packet in an Ethernet header with that destination Ethernet address.
2. ARPResponder(ip eth, ...) Agnostic. Input takes ARP queries, output emits ARP responses. Responds to ARP queries for IP address ip with the static Ethernet address eth.
3. CheckIPHeader(...) Agnostic. Input takes IP packets. Discards packets with invalid IP length, source address, or checksum fields; forwards valid packets unchanged.
4. CheckPaint(p) Agnostic. Input takes any packet. Forwards packets with paint annotation p to both outputs; otherwise just to first.
5. Classifier(...) Push. Input takes any packet. Examines packet data according to a set of classifiers, one classifier per output port. Forwards packet to output port corresponding to the first classifier that matched. Example classifier: “12/0800” checks that the packet’s data bytes 12 and 13 contain values 8 and 0, respectively. See also IPClassifier.
6. DecIPTTL Agnostic. Input takes IP packets. Decrements input packets’ IP time-to-live field. If the packet is still live, incrementally updates IP checksum and sends modified packet to first output; if it has expired, sends unmodified packet to second output.
7. Discard Push. Discards all input packets.
8. DropBroadcasts Agnostic. Input takes any packet. Discards packets that arrived as link-level broadcasts; forwards others unchanged.
9. EtherSpanTree Agnostic. Inputs take IEEE 802.1d messages. Implements the IEEE 802.1d spanning tree algorithm for Ethernet switches.
10. EtherSwitch Push. Inputs take Ethernet packets; one input per output. Learning, forwarding Ethernet switch. Learns the interfaces corresponding to Ethernet addresses by examining input packets’ source addresses; forwards packets to the correct output port, or broadcasts them if the destination Ethernet address is not yet known.
11. FixIPSrc(ip) Agnostic. Input takes IP packets. Sets the IP header’s source address field to the static IP address ip if the packet’s Fix IP Source annotation is set; forwards other packets unchanged.
12. FromDevice(devicename) Push. No inputs. Sends packets to its single output as they arrive from a Linux device driver.
13. FromLinux(devicename, ip/netmask) Push. No inputs. Installs into Linux a fake Ethernet device devicename and a routing table entry that sends packets for ip/netmask to that fake device. The result is that packets generated at the router host and destined for ip/netmask are emitted on FromLinux’s single output as they arrive from Linux.
14. GetIPAddress(16) Agnostic. Input takes IP packets. Copies the IP header’s destination address field (offset 16 in the IP header) into the destination IP address annotation; forwards packets unchanged.
15. HashDemux(offset, length) Push. Input takes any packet; arbitrary number of outputs. Forwards packet to one of its outputs, chosen by a hash bytes [offset, offset + length) of the packet’s data.
16. ICMPError(ip, type, code) Agnostic. Input takes IP packets, output emits ICMP error packets. Encapsulates first part of input packet in ICMP error header with source address ip, error type type, and error code code. Sets the Fix IP Source annotation on output packets.
17. IPClassifier(...) Push. Input takes IP packets. Examines packet data according to a set of classifiers, one classifier per output port. Forwards packet to output port corresponding to the first classifier that matched. Example classifier: “ip src 1.0.0.1 and dst tcp port www” checks that the packet’s source IP address is 1.0.0.1, its IP protocol is 6 (TCP), and its destination TCP port is 80. See also Classifier.
18. IPEncap(p, ipsrc, ipdst) Agnostic. Input takes any packet, output emits IP packets. Encapsulates input packets in an IP header with protocol p, source address ipsrc, and destination address ipdst.
19. IPFragmenter(mtu) Push. Input takes IP packets. Fragments IP packets larger than mtu; sends fragments, and packets smaller than mtu, to first output. Too-large packets with the don’t-fragment IP header flag set are sent unmodified to the second output.
20. IPGWOptions Agnostic. Input takes IP packets. Processes IP Record Route and Timestamp options; packets with invalid options are sent to the second output.
21. LookupIPRoute(table) Push. Input takes IP packets with valid destination IP address annotations. Arbitrary number of outputs. Looks up input packets’ destination annotations in a static routing table specified in the configuration string. Forwards each packet to the output port specified in the resulting routing table entry; sets its destination annotation to the resulting gateway address, if any.
22. Meter(r) Push. Input takes any packet. Sends packets to first output if recent input rate averages < r, second output otherwise. Multiple rate arguments are allowed.
23. Paint(p) Agnostic. Input takes any packet. Sets each input packet’s paint annotation to p before forwarding it.
24. PrioSched Pull. Inputs take any packet; one output port, arbitrary number of input ports. Responds to pull requests by trying inputs in numeric order, returning the first packet it receives. Thus, lower-numbered inputs have priority.
25. Queue(n) Push input, pull output. Input takes any packet. Stores packets in a FIFO queue; maximum queue capacity is n.
26. RED(min-thresh, max-thresh, max-p) Agnostic. Input takes any packet. Drops packets probabilistically according to the Random Early Detection algorithm [Floyd and Jacobson 1993] with the given parameters; forwards other packets unchanged. Examines nearby router queue lengths when making its drop decision.
27. RoundRobinSched Pull. Inputs take any packet; one output port, arbitrary number of input ports. Responds to pull requests by trying inputs in roundrobin order; returns the first packet it receives. It first tries the input port just after the one that succeeded on the last pull request.
28. ScheduleInfo(elementname param, ...) No inputs or outputs. Specifies elements’ initial task queue scheduling parameters by element name. Each scheduling parameter is a real number; an element with parameter 2p will be scheduled twice as often as an element with parameter p.
29. ScheduleLinux No inputs or outputs. Places itself on the task queue, and returns to Linux’s scheduler every time it is run.
30. SetIPAddress(ip) Agnostic. Input takes IP packets. Sets each packet’s destination IP address annotation to the static IP address ip. Forwards modified packets to first output.
31. SetIPDSCP(c) Agnostic. Input takes IP packets. Sets each packet’s IP diffserv code point field [Nichols et al. 1998] to c and incrementally updates the IP header checksum. Forwards modified packets to first output.
32. Shaper(n) Pull. Input takes any packet. Simple pull traffic shaper: forwards at most n pull requests per second to its input. Pull requests over that rate get a null pointer in response.
33. Strip(n) Agnostic. Input takes any packet. Strips off each packet’s first n bytes; forwards modified packets to first output.
34. StripIPHeader Agnostic. Input takes IP packets. Strips off each packet’s IP header, including any options; forwards modified packets to first output.
35. Suppressor Agnostic. Inputs take any packet; arbitrary number of input ports, same number of output ports. Normally forwards packets arriving on each input port to the corresponding output port. A method interface allows other elements to ask Suppressor to drop packets arriving on particular input ports.
36. Tee(n) Push. Input takes any packet; n output ports. Forwards each input packet to all n output ports.
37. ToDevice(device) Pull. Input takes Ethernet packets; no outputs. Hands packets to a Linux device driver for transmission. Activates pull requests only when the device is ready.
38. ToLinux Push. Input takes Ethernet packets; Linux will ignore the Ethernet header except for the protocol field. No outputs. Hands input packets to Linux’s default network input software.

Note that some of these elements don't map exactly to elements in route-rs, generally because:

• We make a distinction between Elements and Links for data operations and control flow
• We are not embedding ourselves inside the Linux kernel
• We are going to make a distinction between Elements for data operations and Stores for accumulating state
• We are going to make a distinction between Elements for data operations and Interfaces for receiving and sending data from the host system
• We are pull-only for inter-Element communication

Write an example crate that uses Join and Classify

ClassifyElement: Test more edge cases

We should add more tests, specifically we need tests that contain more output branches, have longer to compute split functions, have multiple layers of channels. etc etc.

Investigate state tracking elements/actors/agents.

do client ip table?

Create BlackHoleLink

We should have an element a link that discards all packets that are passed into it. Since this is super generic, it should go in the runtime rather than a separate elements crate.

Edit: I realized that this should be a link type rather than an element, because it will poll but not emit anything, which is different from how everything else works.

AsyncElement: Test more edge cases

We need move tests to figure out if there are any additional bugs with our AsyncElement. We need help writing more tests that do more interesting things. Even basic cases like a stream that immediately returns None as input. Or seeing if there are any tests that should panic and writing those.

Task Waking without the overseer

This would allow us to remove the *ElementOverseer since this might remove the deadlock.

The observation is that the deadlock occurs when both Consumer and Provider have both parked their tasks in their respective channels and gone to sleep, so neither of them can wake up. In other words, there is no milk in the fridge. If we enforce that at most 1 task can be queued up, then we ensure that the deadlock never occurs.

Rename ClassifyElementLink to ClassifyLink

Same as #72

Prefer ImmediateStream for tests.

Unless a different stream is needed to accurately test, we should prefer ImmediateStream in our basic test cases since it runs quicker, allowing us to run the the suite of tests in less time.

Create AF Packet crate

DO STUFF

Yes

Async Elements: Tests with a continous input can deadlock the channel.

This is a bug which results when the channel between the AsyncElement consumer and provider fills to capacity, and is drained to empty repeatedly in quick succession. There is a race condition around writing the task handle to the other side and going to sleep. This can result in both the consumer and provider being asleep. We need to actually fix this bug.

To help with that we need:
An overseer part that can sidestep the issue for the time being
Better logging for the element. I'm thinking tokio-trace, with an emphasis on timestamps and such, so we know the order of events leading up to the deadlock.
Some sort of locking scheme that will prevent this issue, the better logging may help us figure out exactly what is in the race, and then lock that.

Improve logging capabilities through Tokio trace or middleware.

Investigate combining common logic in Asynchronous links

We noticed that among AsyncElementLink, ClassifyElementLink, and JoinElementLink, their subcomponents such as their consumers and producers, contain a lot of reoccurring logic. We should try to compose this in a helper function.

Rename JoinElementLink to JoinLink

See #72 for concept

Allow elements to drop packets

Right now, elements have no way to drop a packet, since they are forced to return a packet to the link due to the way their process function is implemented. We should change that, so that process returns the Option. Then links will unwrap the Option and forward the packet if it exists, if they get a None they will re-fetch and retry.

Discuss Pinning all our packages

We need to fully debate the best way to denote the versions of our dependencies in our cargo.toml files. Ideally we would set a specific version, maybe we could use more of a meta-version if they are available 'latest-stable' or whatever.

Create `netif` crate

Define traits that can be reused over different implementations.

Testing Utilities/Framework

Make git commit hook to enforce style standards

JoinElement: Test more edge cases

Let's add more tests, such as multiple layers of Join elements, add tests to ensure the join element can receive packets from all the other elements. Etc etc

Rename Tests in Links to not use the word Element unnecessarily.

Most of the link still use names like join_element rather than join_link in their internal testing. This is confusing since these tests are primarily testing links rather than elements.

Write and enable AF_Packet unit tests on CI

AF_PACKET unit tests should use the lo interface, making it possible to trivially run these tests on any Linux system.

Additionally, we should figure out how to make this work in CI. In particular, we'd need to enable the capability CAP_NET_RAW on our test binary for this to work.

Classify Element: Switch to new Identity Element style

Let's move this over like how we did for Async Element, shouldn't be a big change.
Reference PR #51

Rename ElementLink to SyncLink

See #72 for concept.

AsyncElementLink with queue_capacity zero deadlocks

Revisited my test case and realize the panic with a zero length queue doesn't actually occur until tear-down. It is possible to create and start using an AsyncElementLink with queue capacity of 0, but it deadlocks. I also tested this on PR #42 and encountered the same issue.

Rename AsyncElementLink to AsyncLink

Since we are just calling them links, lets change the struct to be AsyncLink instead of AsyncElementLink.

Icon for route-rs

We need an icon, IIRC Ben volunteered for this, something using the route-66 sign.

Support multiple I/O nodes in graphgen

Use Rust Analyzer to distinguish between sync and async elements in graphgen

Right now, graphgen doesn't have a way of determining whether to use a SyncElementLink or AsyncElementLink to connect elements, because it doesn't know if the element is Async. We currently assume that everything is Sync.

We should be able to use the Rust Analyzer to find out if an element has the Async trait and act accordingly.

Rename "element" in ClassifyLink to "classifier"

Create generic traits for Links

At this point, we've written several different types of Link structs, and they're shaping up to have a similar interface:

• link.ingressor is driven by Tokio to keep packets flowing
• link.egressor is polled by the next link to receive packets

We should codify this interface in a trait. This also means that we can have accessor methods for the ingressor and egressor so that we're not calling into the struct's internals as much, which is kind of gross.

Set up build agent to refuse PRs if tests dont pass

Create a diagram of internal `route-rs` constructs

It's easier to explain how route-rs works visually since it's a graph computation. Let's create a diagram that we can reference internally when we're building components, or show to people who are interested. It's debatable whether or not we want to expose internal components of the API, depending on the audience.

Move test element definitions to common location.

Some testing elements, like our IdentityElement, keep being redefined in each element link module. Let's define it in a common location.

Join Element: Switch to new Identity Element Style

Same as issue #52,
Reference PR #51

Define trait bounds on i/o for runtime elements

Sized, Display, Debug?

Create TeeLink

We'll need a link in the graph that can clone packets across multiple DownstreamProviders.

Investigate common trait bounds for all Asynchronous Elements

We wish that all of our various Elements would have the same trait bounds, especially the part of the trait that dictates that the Element inputs and outputs something of type Packet. We should try to lean on traits composition to achieve this.

Create library element with multiple inputs