brunorijsman / rift-python Goto Github PK
View Code? Open in Web Editor NEWRouting In Fat Trees (RIFT) implementation in Python
License: Apache License 2.0
Routing In Fat Trees (RIFT) implementation in Python
License: Apache License 2.0
Add ipv6 loopbacks to config_generator
The topology file currently uses underscores (for historical reasons - this is what the Juniper configuration file used).
The meta-topology file currently uses dashes (which I prefer).
Make them consistent.
Compatibility with Juniper is no longer a major issue -- that has already been given up, the chaos scripts regenerate the topology file anyway.
If we do this, we must do it before the Day One book is published. Once that happens it will be painful to make such a major change.
In function check_minor_change in module interface.py handle the following additional minor changes:
Add error callback to receive handlers
The UDP receive handler that processes received RIFT packets should call bump_rx_real_errors_counter when there is an error reading the socket
Discussed in RIFT spec under "Originating Non-Default Route Southbound"
Will require an optional configuration knob to specify what the fabric default is.
Send all RIFT packets with network control precedence
Add support for key-values:
Encode key-value TIEs
Decode key-value TIEs
Mechanism to originate key-values (manually)
Originate some key-values automatically (see what Juniper does)
Process and store received key-values
CLI to report received key-values
Add support for fabric bandwidth balancing
This will lead to NECMP routes, where the weight of each next-hop is determined by the available bandwidth on that path.
Note: the configuration of metric vs bandwidth in the configuration / topology file is also not consistent.
Currently the UDP receive handler for received flooding packets (TIEs, TIREs, TIDEs) accept packets from any remote address: the IPv4 receive handlers registers 0.0.0.0 as the remote address and the IPv6 receive handler registers :: as the remote address. We know the address of the remote RIFT speaker (it was discovered from the LIEs). Security would be improved if we only accept (i.e. listen for) UDP packets from that particular address.
Add interactions with BFD (see RIFT spec)
No need to implement BDF itself -- just find an existing BFD implementation (preferably the most widely used one) and enhance RIFT-Python to interact with it.
A new MultipleNeighborsWait was added to the LIE FSM in the RIFT specification when we discovered that connecting three RIFT routers to one broadcast domain caused exponential oscillations. The new MultipleNeighborsWait state has not yet been added to RIFT-Python.
In the single-process approach, all simulated links in a topology run over a single physical interface. The simulated links are separated from one another by assigning different UDP ports and multicast addresses. Currently this assignment is done manually as follows:
- name: node1
rx_lie_mcast_address: 224.0.1.1
rx_lie_v6_mcast_address: ff02::abcd:1
rx_lie_port: 20001
interfaces:
- name: if1 # Connected to node2-if1
tx_lie_port: 20002
rx_tie_port: 10001
This is very cumbersome and error prone.
Instead, each interface should simply be able to configure its peer interface, and assignment of UDP ports and multicast addresses should happen automatically:
- name: node1
interfaces:
- name: if1
peer-interface: node2:if1
Convert remaining TODOs in code into GitHub issues
Once no TODOs remain, add a Travis check to not allow new TODOs
In function default_interface_name in module config.py dynamically discover the name of the primary physical interface (to be used for single-process approach simulation) instead of hard-coding it to be en0 (which is what macOS uses).
Maybe also make it a rift command-line option to hand-pick one in case the dynamic algorithm does a bad job picking the right one
Since RIFT in inherently loop-free, we don't have to restrict ourselves to using only the shortest routes, we can use ALL routes (or the k-best routes).
By default don't do that.
Add a configuration option to enable using all paths (including non-best paths) or k-best paths.
Add multicast routing
At this point (28-Jun-2020) there is not IETF specification for RIFT multicast routing yet
Use netlink to determine actual interface MTU (currently hard-coded to 1400)
See function Interface:get_mtu
RIFT-Python currently only supports Telnet to connect to the CLI. Add support for SSH.
Document configuration file (= topology file) syntax in doc/configuration-file.md
Also review meta-topology
Currently configuration is only done using the configuration / topology file
The CLI only supports operational commands (show, clear,... ) and a very small number of set commands for non-persistent changes.
Add support for configuration using the CLI and store it in a persistent configuration data store.
Implement the following functions in interface.py:
action_store_hal
action_store_hat
action_store_hals
action_update_level
Add optimized route computation on leaves
Don't need to run full SPF on leaves (details in RIFT spec)
Add support for mobility as described in the mobility section of the RIFT draft, including:
Just fixed the AWS not doing IPv6 LIE multicast and here is the finding:
Currently rates in statistics are computed over the last 10 changes, for example:
All Interface LIE FSMs:
+------------------------------------------------------------+-----------------+-------------------------+-------------------+
| Description | Value | Last Rate | Last Change |
| | | Over Last 10 Changes | |
+------------------------------------------------------------+-----------------+-------------------------+-------------------+
| Events TIMER_TICK | 224 Events | 68.08 Events/Sec | 0d 00h:00m:00.41s |
+------------------------------------------------------------+-----------------+-------------------------+-------------------+
This leads to very misleading results.
For example, if there is a very quick burst of 10 changes at some point, the rate becomes extremely high. Then if there are zero changes forever after that, the rate continues to be reported as very high forever.
Instead, compute the rate over the last 10 seconds.
Add support for pod numbering:
Add type annotations to the Python code. This will help reduce run-time errors.
Use netlink to monitor dynamic interface changes
All sent RIFT packets (LIEs, TIEs, TIREs, TIDEs) must have TTL 1
All received RIFT packets must have TTL 1: packets with TTL greater than 1 must be ignored (keep stats for this)
Set TTL as follows:
ttl_bin = struct.pack('@i', MYTTL)
if addrinfo[0] == socket.AF_INET: # IPv4
s.setsockopt(socket.IPPROTO_IP, socket.IP_MULTICAST_TTL, ttl_bin)
else:
s.setsockopt(socket.IPPROTO_IPV6, socket.IPV6_MULTICAST_HOPS, ttl_bin)
Add context-sensitive help for CLI parameter values
For example typing ? after "set interface if1 failure" should display all valid value for the parameter
Or typing ? after "set interface ?" should display all names of all existing interfaces
Add plane-redundancy parameter to config_generator; this parameter is called R in section 4.1.2.1. Terminology of RIFT draft version 12.
If plane-redundancy = 1 (the default) then the 1st top-of-pod switch in a pod is connected to plane 1, the 2nd top-of-pod switch in a pod is connected to plane 2, etc.
If plane-redundancy = 2 then the first 2 top-of-pod switches in a pod are connected to plane 1, the next 2 top-of-pod switches in a pod are connected to plane 2, etc.
Add support for policy guided prefixes:
Currently, RIFT-Python support Thrift datamodel 2.0 (draft-ietf-rift-rift-10).
Upgrade to datamodel 4.0 (draft-ietf-rift-rift-12)
Python 3.8 installation step on Travis currently fails with following error:
$ pip install -r requirements.txt
Collecting anybadge==1.1.1
Downloading anybadge-1.1.1-py2.py3-none-any.whl (17 kB)
Collecting astroid==2.0.1
Downloading astroid-2.0.1-py3-none-any.whl (172 kB)
Collecting atomicwrites==1.1.5
Downloading atomicwrites-1.1.5-py2.py3-none-any.whl (7.5 kB)
Collecting attrs==18.1.0
Downloading attrs-18.1.0-py2.py3-none-any.whl (28 kB)
Collecting awscli==1.18.66
Downloading awscli-1.18.66-py2.py3-none-any.whl (3.1 MB)
Collecting botocore==1.16.16
Downloading botocore-1.16.16-py2.py3-none-any.whl (6.2 MB)
Collecting Cerberus==1.2
Downloading Cerberus-1.2.tar.gz (48 kB)
Collecting certifi==2018.4.16
Downloading certifi-2018.4.16-py2.py3-none-any.whl (150 kB)
Collecting chardet==3.0.4
Downloading chardet-3.0.4-py2.py3-none-any.whl (133 kB)
Collecting codecov==2.0.15
Downloading codecov-2.0.15-py2.py3-none-any.whl (11 kB)
Collecting colorama==0.4.3
Downloading colorama-0.4.3-py2.py3-none-any.whl (15 kB)
Collecting coverage==4.5.1
Downloading coverage-4.5.1.tar.gz (379 kB)
Collecting docutils==0.15.2
Downloading docutils-0.15.2-py3-none-any.whl (547 kB)
Collecting gprof2dot==2019.11.30
Downloading gprof2dot-2019.11.30.tar.gz (31 kB)
Collecting HeapDict==1.0.0
Downloading HeapDict-1.0.0-py3-none-any.whl (3.9 kB)
Collecting idna==2.7
Downloading idna-2.7-py2.py3-none-any.whl (58 kB)
Collecting isort==4.3.4
Downloading isort-4.3.4-py3-none-any.whl (45 kB)
Collecting jmespath==0.10.0
Downloading jmespath-0.10.0-py2.py3-none-any.whl (24 kB)
Collecting lazy-object-proxy==1.3.1
Downloading lazy-object-proxy-1.3.1.tar.gz (32 kB)
Collecting mccabe==0.6.1
Downloading mccabe-0.6.1-py2.py3-none-any.whl (8.6 kB)
Collecting more-itertools==4.2.0
Downloading more_itertools-4.2.0-py3-none-any.whl (45 kB)
Collecting netifaces==0.10.7
Downloading netifaces-0.10.7.tar.gz (29 kB)
Collecting pexpect==4.6.0
Downloading pexpect-4.6.0-py2.py3-none-any.whl (57 kB)
Collecting pluggy==0.7.1
Downloading pluggy-0.7.1-py2.py3-none-any.whl (14 kB)
Collecting ptyprocess==0.6.0
Downloading ptyprocess-0.6.0-py2.py3-none-any.whl (39 kB)
Collecting py==1.5.4
Downloading py-1.5.4-py2.py3-none-any.whl (83 kB)
Collecting pyasn1==0.4.8
Downloading pyasn1-0.4.8-py2.py3-none-any.whl (77 kB)
Collecting pylint==2.0.0
Downloading pylint-2.0.0-py3-none-any.whl (732 kB)
Collecting pyroute2==0.5.3
Downloading pyroute2-0.5.3.tar.gz (687 kB)
Collecting pytest==3.6.4
Downloading pytest-3.6.4-py2.py3-none-any.whl (196 kB)
Collecting pytest-cov==2.5.1
Downloading pytest_cov-2.5.1-py2.py3-none-any.whl (21 kB)
Collecting pytest-profiling==1.7.0
Downloading pytest_profiling-1.7.0-py2.py3-none-any.whl (8.3 kB)
Collecting python-dateutil==2.8.1
Downloading python_dateutil-2.8.1-py2.py3-none-any.whl (227 kB)
Collecting pytricia==1.0.1
Downloading pytricia-1.0.1.tar.gz (20 kB)
Collecting PyYAML==4.2b1
Downloading PyYAML-4.2b1.tar.gz (263 kB)
Collecting requests==2.20.0
Downloading requests-2.20.0-py2.py3-none-any.whl (60 kB)
Collecting rope==0.11.0
Downloading rope-0.11.0.tar.gz (247 kB)
Collecting rsa==3.4.2
Downloading rsa-3.4.2-py2.py3-none-any.whl (46 kB)
Collecting s3transfer==0.3.3
Downloading s3transfer-0.3.3-py2.py3-none-any.whl (69 kB)
Collecting six==1.11.0
Downloading six-1.11.0-py2.py3-none-any.whl (10 kB)
Collecting sortedcontainers==2.0.4
Downloading sortedcontainers-2.0.4-py2.py3-none-any.whl (28 kB)
Collecting thrift==0.11.0
Downloading thrift-0.11.0.tar.gz (52 kB)
Collecting typed-ast==1.1.0
Downloading typed-ast-1.1.0.tar.gz (200 kB)
Collecting urllib3==1.24.2
Downloading urllib3-1.24.2-py2.py3-none-any.whl (131 kB)
Collecting wrapt==1.10.11
Downloading wrapt-1.10.11.tar.gz (27 kB)
Requirement already satisfied: setuptools in ./env/lib/python3.8/site-packages (from pytest==3.6.4->-r requirements.txt (line 30)) (47.3.1)
Building wheels for collected packages: Cerberus, coverage, gprof2dot, lazy-object-proxy, netifaces, pyroute2, pytricia, PyYAML, rope, thrift, typed-ast, wrapt
Building wheel for Cerberus (setup.py) ... done
Created wheel for Cerberus: filename=Cerberus-1.2-py3-none-any.whl size=49686 sha256=46a8be9fff48d91667a7d63424b7910bc9e462cc8898c72e1a86d70d083b19f1
Stored in directory: /home/travis/.cache/pip/wheels/eb/7e/93/ad2d779beda9965b03eceadfdf92262b6dda9036e49b4cd9cb
Building wheel for coverage (setup.py) ... done
Created wheel for coverage: filename=coverage-4.5.1-cp38-cp38-linux_x86_64.whl size=202283 sha256=9dc63896628082d5cfb7efe69e5cd055e00eaca160fa90b73420618346159e19
Stored in directory: /home/travis/.cache/pip/wheels/d7/be/80/50ca9380d915773eb79a8e9a7aa57e235ce3efce7528f7d9d4
Building wheel for gprof2dot (setup.py) ... done
Created wheel for gprof2dot: filename=gprof2dot-2019.11.30-py3-none-any.whl size=27722 sha256=4e892a2dd44d8d5a38431c3d2285ae79576469252f999714f53a1559a372ec16
Stored in directory: /home/travis/.cache/pip/wheels/ff/1c/e6/b0fa3f25f10fc2168f5d785e448be44f0525c071d6fa57dfff
Building wheel for lazy-object-proxy (setup.py) ... done
Created wheel for lazy-object-proxy: filename=lazy_object_proxy-1.3.1-cp38-cp38-linux_x86_64.whl size=53220 sha256=0c3c4b85fb62a44a17098db1ae9256e45273cef3187563e0c7ebac5f8aaee5c9
Stored in directory: /home/travis/.cache/pip/wheels/63/fc/fc/f2853723dd9e05ea138dbb7af223dae018a4bea60a94578cf8
Building wheel for netifaces (setup.py) ... done
Created wheel for netifaces: filename=netifaces-0.10.7-cp38-cp38-linux_x86_64.whl size=33266 sha256=ebe4f17356d661e089be8769590df55c7e1333366a55a27587d0333a1fc0783f
Stored in directory: /home/travis/.cache/pip/wheels/88/7a/57/049d460cf9520234ad669c989b7a74de964ff1cab6f4f56af0
Building wheel for pyroute2 (setup.py) ... done
Created wheel for pyroute2: filename=pyroute2-0.5.3-py3-none-any.whl size=300243 sha256=f87a0fe281399116331d48f5a73e26135a67ec409f356dd6fea2f49c661adc99
Stored in directory: /home/travis/.cache/pip/wheels/4d/ab/9c/fd676c09eed0051aa42caf67ac294d7768219423d35135568c
Building wheel for pytricia (setup.py) ... done
Created wheel for pytricia: filename=pytricia-1.0.1-cp38-cp38-linux_x86_64.whl size=47880 sha256=0d448d79252c3b3f1bfc92cf0c8744d01aaee3187bb1822eaafb45e948c6d859
Stored in directory: /home/travis/.cache/pip/wheels/e8/ca/55/0aa0960a200788699ac953dfac15d6015c525707c7f8ce823a
Building wheel for PyYAML (setup.py) ... done
Created wheel for PyYAML: filename=PyYAML-4.2b1-cp38-cp38-linux_x86_64.whl size=442838 sha256=21a8bf1472782acf8f473e7df974dcb4799410a4c241323e21c00e81370f87e0
Stored in directory: /home/travis/.cache/pip/wheels/ec/8a/c7/cbb04cd0657f34b885b7fe73434a14f5dd63ba5da69b09682c
Building wheel for rope (setup.py) ... done
Created wheel for rope: filename=rope-0.11.0-py3-none-any.whl size=183785 sha256=57ec11c68f7b333e0b3e43d487e8d04743081b4768c2d6ff4ff0cfc380e64803
Stored in directory: /home/travis/.cache/pip/wheels/18/2f/24/8571548f1be0ba1aad1fd3ce51bc856b717e984fe7d95144df
Building wheel for thrift (setup.py) ... done
Created wheel for thrift: filename=thrift-0.11.0-cp38-cp38-linux_x86_64.whl size=368292 sha256=da0310afb0fea00fb144f5540136cc5505c4d22e51b35cf00b5ee5202fb43e28
Stored in directory: /home/travis/.cache/pip/wheels/1b/96/3d/25fd2c11b01cd0c233d916b80d0f4d9c9a4370bb66b548754d
Building wheel for typed-ast (setup.py) ... error
ERROR: Command errored out with exit status 1:
command: /home/travis/build/brunorijsman/rift-python/env/bin/python3 -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-h5qo4vz5/typed-ast/setup.py'"'"'; __file__='"'"'/tmp/pip-install-h5qo4vz5/typed-ast/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' bdist_wheel -d /tmp/pip-wheel-zo2i23d6
cwd: /tmp/pip-install-h5qo4vz5/typed-ast/
Complete output (21 lines):
running bdist_wheel
running build
running build_py
creating build
creating build/lib.linux-x86_64-3.8
creating build/lib.linux-x86_64-3.8/typed_ast
copying typed_ast/ast27.py -> build/lib.linux-x86_64-3.8/typed_ast
copying typed_ast/conversions.py -> build/lib.linux-x86_64-3.8/typed_ast
copying typed_ast/ast3.py -> build/lib.linux-x86_64-3.8/typed_ast
copying typed_ast/__init__.py -> build/lib.linux-x86_64-3.8/typed_ast
running build_ext
building '_ast27' extension
creating build/temp.linux-x86_64-3.8
creating build/temp.linux-x86_64-3.8/ast27
creating build/temp.linux-x86_64-3.8/ast27/Parser
creating build/temp.linux-x86_64-3.8/ast27/Python
creating build/temp.linux-x86_64-3.8/ast27/Custom
gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -g -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -fPIC -Iast27/Include -I/opt/python/3.8.0/include/python3.8 -c ast27/Parser/acceler.c -o build/temp.linux-x86_64-3.8/ast27/Parser/acceler.o
ast27/Parser/acceler.c:13:25: fatal error: pgenheaders.h: No such file or directory
compilation terminated.
error: command 'gcc' failed with exit status 1
----------------------------------------
ERROR: Failed building wheel for typed-ast
Detect and report RIFT crashes in chaos testing (config_generator --check):
Enhance logging:
Set default to WARNING instead of INFO
Change chaos script in each iteration of chaos-test-suite.
Currently it runs the exact same chaos script multiple times.
Add segment routing
There is going to be a separate spec for this, but as of now (28-Jun-2020) that spec does not yet exist.
Add anycast support
For now, anycast already works
But when support for mobility is added (issue #44) then we have to make sure that anycast prefixes don't carry a clock attribute (or -less likely- the clock is always the same for anycast prefixes) See RIFT spec for details
Support the RIFT YANG model being defined in the IETF RIFT working group (still work in progress as of 28-Jun-2020)
Add CLI Tab Completion:
The latter requires the CLI to be aware of valid parameter values (retrieved using a callback into the code)
Add interface packet rate check in config_generator --check:
Higher packet rates typically indicate a problem with persistent oscillation (quite a common problem)
RIFT-Python currently supports east-west links between top-of-fabric nodes that are only used for control traffic (needed for negative disaggregation) but that are never used for forwarding user traffic.
Add support for east-west links between the leafs. These are called leaf-to-leaf shortcuts. These ARE used for forwarding.
Honor received overload bit in received TIEs (avoid forwarding traffic through those nodes)
Leaf nodes should set overload bit
Consider allowing overload bit to be set manually (e.g. before software update)
Fix intermittent errors in 3rd iteration of chaos test on Travis
RIFT-Python does not use the concept of shards in configuration / topology files.
Shards were introduced for configuration file compatibility with Juniper's alpha code configuration, which in turn was deemed important for chaos testing.
However, since then chaos testing has taken a different approach and chaos testing does not rely on configuration file compatibility between RIFT-Python and Juniper anymore. Instead, the Juniper configuration is generated fresh.
To make the configuration / topology file syntax as simple as possible, remove the unused concept of shards.
If we ever add support for running large topologies in multiple AWS instances connected by VXLAN tunnels, this will be supported by having the config_generator.py tool generate the scripts for creating the VXLAN tunnels. It will not rely on the concepts of shards.
The multi-process approach is used to run medium to large topologies. Each RIFT node runs in its own Python process. The RIFT nodes are connected using veth interface pairs.
The scripts and configurations for such topologies are generated by the config_generator tool.
Currently such large topologies are limited to a single server (typically and AWS instance).
Enhance the config_generator.py script to allow very large topologies to run on multiple servers (i.e. multiple AWS instances). Use VXLAN tunnels to carry veth links from one server to another. The config_generator.sh should generate the commands to create the required VXLAN tunnels in the start.sh script.
Bruno, chained events that you introduced are NOT special. The PUSH simply adds events at the end of the queue and they are processed after events in front of them got processed. There is nothing special about the "events that a transition generates".
The interpretation you use currently can lead to interop problems albeit the FSM is built towards very resilient self-stabilization so stable oscillations should not happen unless we'll get some very, very pathological timer sequences (albeit @ 1sec timer the FSM would have to be incredibly slow in processing) ...
Add label binding as described in the label binding section of the RIFT spec
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.