2020-02-02 04:20:04 +00:00
|
|
|
|
2020-02-02 05:52:28 +00:00
|
|
|
__ __ __
|
|
|
|
|
__/ // /_/ /___ _____ ____ _ __ ___ ____ __
|
|
|
|
|
/_ _ __/ / __ `/ __ \/ __ `/ / / / / | /| / / / / /
|
|
|
|
|
/_ _ __/ / /_/ / / / / /_/ / / /_/ /| |/ |/ / /_/ /
|
|
|
|
|
/_//_/ /_/\__,_/_/ /_/\__, / \__,_/ |__/|__/\__,_/
|
|
|
|
|
/____/
|
|
|
|
|
|
|
|
|
|
## High level approach
|
|
|
|
|
|
|
|
|
|
The design of this "BGP" router is based on an internal radix tree structure containing the routing
|
|
|
|
|
database. Routes are indexed in the tree based on the bit pattern of their subnet, and route lookup
|
|
|
|
|
walks the tree to find the most specific route node corresponding to the requested destination
|
|
|
|
|
address. The router itself is based on Racket's built-in I/O multiplexing to automatically manage
|
|
|
|
|
I/O between multiple sockets.
|
|
|
|
|
|
2020-02-15 01:02:47 +00:00
|
|
|
### Update since milestone submission
|
|
|
|
|
|
|
|
|
|
There were three major parts to the post-milestone effort. We implemented the "being mean to peers
|
|
|
|
|
that don't pay you" rules with fairly little effort, and we also implemented route aggregation and
|
|
|
|
|
disaggregation with minimal changes to the existing radix tree backend and some additional router
|
|
|
|
|
logic. Finally, (the most time-consuming part) we fixed bugs in the existing implementation that we
|
|
|
|
|
found when evaluating against the full test suite. Besides bugs, just adding aggregation and
|
|
|
|
|
meanness functionality was all that was necessary to pass all the tests.
|
|
|
|
|
|
2020-02-02 05:52:28 +00:00
|
|
|
## Challenges
|
|
|
|
|
|
|
|
|
|
- **No existing radix tree package in Racket.**
|
|
|
|
|
Due to Racket's unfortunate lack of adoption in the networks field, nobody has written any public
|
|
|
|
|
radix tree library for Racket that we could find, so we had to implement our own. This went
|
|
|
|
|
through approximately 3 iterations and it's still mildly spaghetti code.
|
|
|
|
|
- **No stdlib `SOCK_SEQPACKET` support.**
|
|
|
|
|
There's no support for `SOCK_SEQPACKET` in the standard UNIX domain socket module, so we pulled
|
|
|
|
|
the source code for this module and added a mode for `SOCK_SEQPACKET`.
|
|
|
|
|
- **Interesting simulator dependencies.**
|
|
|
|
|
The provided simulator has a hard dependency on Python 3.6, which neither of us actually had
|
|
|
|
|
installed or were capable of installing, and it did not work with Python 3.8.
|
|
|
|
|
|
|
|
|
|
## Testing
|
|
|
|
|
|
|
|
|
|
For the milestone submission, we included some basic internal unit tests but there isn't a lot of
|
|
|
|
|
code coverage on those yet. We also ran the simulator milestone tests against the current router
|
|
|
|
|
implementation and both milestone tests are passing.
|
2020-02-15 01:02:47 +00:00
|
|
|
|
|
|
|
|
For the final submission, we included some more basic internal unit tests where necessary when
|
|
|
|
|
implementing new features. We also ran the provided simulator (the newest version provided) against
|
|
|
|
|
the router testing for all tests. Currently, all provided tests pass when testing on the CCIS login
|
|
|
|
|
server.
|
