time for crab
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
haskal c4d164c952 Write readme 5 months ago
private Implement disaggregation :meowdab: 5 months ago
scripts Create parallel test runner script 5 months ago
.gitignore ignore python downloads 5 months ago
Makefile Write readme 5 months ago
README.md Write readme 5 months ago
router Implement disaggregation :meowdab: 5 months ago

README.md

      __ __  __
   __/ // /_/ /___ _____  ____ _   __  ___      ____  __
  /_  _  __/ / __ `/ __ \/ __ `/  / / / / | /| / / / / /
 /_  _  __/ / /_/ / / / / /_/ /  / /_/ /| |/ |/ / /_/ /
  /_//_/ /_/\__,_/_/ /_/\__, /   \__,_/ |__/|__/\__,_/
                       /____/

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.

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.

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.

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.