Click-based MobilityFirst Router
Contents
- 0. Requirements
- 1. System architecture
- 2. Installation
- 3. Running the MobilityFirst Router
- 4. Performance
- 5. Known Issues
- 6. Release Notes
0. Requirements
- Software prototype with reference implementations of dynamic GNRS resolution, hop-by-hop block transfer, storage aware routing (GSTAR)
- Reference implementation/handling of network layer header with service identifier, 160-bit src/dst GUID, src/dst NA(s) and extensible headers for service options processing
- Multicast and anycast forwarding implemented using GNRS maintained membership and routing state from GSTAR
- Configuration and parameter tuning for router roles: core, access
1. System architecture
PKT PROCESSING OVERVIEW
+++++++++++++++++++++++
___________
| |
-->| Routing X |--->
/ |___________| \
/ | \
/ _________|_ \
ctrl path / | | | \ ctrl path
/----- ->| GSTAR | |--------\
/ |_________|_| \
in / | | \ out
_________ __________ / _________v__v__ \ ___________ _________
| | | | / | | -->| | | |
|Device(s)| -> |Classifier| -> | Forward LUT | | PrioSched | -> |Device(s)|
|_________| |__________| \ |_______________| -->|___________| |_________|
\ ^ | /
\ ________|__v______ /
\ | | /
--> | Data pkt proc. | ----
data path |__________________| data path
Figure above shows the packet-processing pipeline of the Click-based MobilityFirst (MF) software router. The pipeline shows two main paths: data and control. The data path handles the forwarding of MF data packets and composed mainly of modules for short/medium term buffering, dynamic network address resolution, multi-service routing, and an optional compute-plane interface for advanced packet processing and forwarding ops. As indicated in the figure, the control path can potentially comprise of multiple independent protocol implementations. Protocols would ideally complement (and not compete with) each other while populating the lookup table (LUT) with forwarding entries. The baseline prototype implements the GSTAR intra-domain routing protocol with modules for neighbor discovery, link quality estimation, and link- and storage-state dissemination.
Since Click's modular structure enables easy composition, MF data and control functions are broken down and implemented as distinct elements, while reusing existing Click library elements where possible. Custom router configurations such as an access router (allows hosts to attach to it), a core router, or a router with integrated name-resolution are achieved through configuration changes. While configurations for the baseline prototype support up to 2 router interfaces or ports (a core-facing, and edge-facing), the configurations can also easily be modified for larger number of physical or virtual ports.
Finally, a note on the separation of data and control paths. The Click modular router is a good option as a forwarding engine. While the control path can also be embedded in it (as is done for GSTAR), a more flexible architecture could allow for user processes outside of Click to implement the control protocols. Presently, the prototype does not export the required messaging API for this. Similar effect can be achieved, however, by constructing a proxy element within Click that interacts with external control processes using traditional sockets. The proxy element can then inject control packets into the MF network either as raw layer 2 pkts or as MF data packets. The current base prototype uses this solution for interfacing to a GNRS service instance. The convenience messaging API is an item for a future release.
1.1 Data Path
DATA PATH
+++++++++
_ _ _ _
( ) ______________
( GNRS ) | |
( _ _ _ _ ) | Forward LUT |
^ | |______________|
GUID lookup | | ^ |
____________ ____|_v__ ______|__v___ ___________
| | | | | |forward| |
data pkt | Hop |chunk | Network | | Next-Hop |-----> | Hop | data pkt
----->| Aggregator | --> | Binder | -> | Lookup | | Segmentor | ----->
|____________| |_________| |_____________|----. |___________| to out port
^ |
| |store
| ____v______
| rebind after timeout | |
. ---------------------- |Chunk Store|
|___________|
Hop Block Transfer
In MF, data blocks (or "chunks" as we call them) are delivered in a hop by hop manner to the destination, with the option of temporarily storing the block at each hop. A simple link-level data transport protocol (called "Hop") achieves reliable transfer at each hop. Such a transport has been shown to perform significantly better than end-to-end reliable transports (e.g., TCP) for paths with wireless segments with variable link conditions and where end-hosts may get temporarily disconnected. The implementation at each hop uses two complementary elements, a Segmentor at the upstream node and an Aggregator at the downstream node. The Segmentor fragments and transmits the block as MTU-sized packets, and the Aggregator reassembles the chunk for routing. A bit-array based ACK response(a bit for each fragment of the block) to a CSYN (chunk SYN) from the upstream node implements reliable transmission. To exercise back pressure, the downstream node can skip acknowledging the CSYN that precedes transmission of a chunk.
To minimize the delays due to fragmentation and reassembly, cut-through processing of the chunk is employed (to be implemented) wherein the chunk is available for routing soon as the first fragment with the routing header has been received by the Aggregator. Also, for reliable segments of the network, we propose a layer-3 bypass that will allow fragments of a chunk to bypass routing decisions and be forwarded to downstream node using a layer-2 label set up on per flow basis(to be implemented). The bypass solution effectively consolidates multiple physical links into a single 'virtual hop'.
Name Resolution
When deployed in a single domain, the routers can work without external name resolution - at the cost of propagating all end point GUIDs through the network. For a scalable control plane and limiting the forwarding table size, however, an external service such as the GNRS can be accessed to retrieve end point network addresses (NA). No resolution is required for a packet (routeable data block) with a previously established NA, until and unless a forwarding failure occurs. For packets that have only a dest. GUID, a resolution (i.e., an address lookup for the GUID) is initiated at the NetBinder module. This request is asynchronous and the packet is buffered while awaiting a response. Later, NAs from the response are used to populate the packet before progressing it to the forwarding stage. The implementation supports a GNRS client module that should be configured with the address (IP, port) of a GNRS server. The server itself may reside either on the router (this is common deployment scenario for our software router) or on a separate node on the network.
Buffer Management
TBD
1.2 Control path
Generalized Storage Aware Routing (GSTAR)
GSTAR CONTROL PATH
++++++++++++++++++
lnk. prb ____________ lnk prb
+ ack | | + ack
------->| Link Est. |------
/ |____________| \
/ ____________ \
ctrl. pkt / lsa pkt | | lsa pkt \ ctrl. pkt
----------------------------->| LS Rtg. |-----------------> to out port
\ |____________| /
\ ____________ /
\ | | /
------->| DTN Rtg. |------
d-lsa pkts |____________| d-lsa pkts
____________ ____________ Periodic _____________
| | | | Updates | |
|Neighbor Tbl| | Routing Tbl|--------> | Forward LUT |
|____________| |____________| |_____________|
LUT: lookup table, LS: link state, LSA: link state announcement, D-LSA: DTN LSA
Figure 1: Main components of the Click-based MobilityFirst router
2. Installation
The following instructions are for Ubuntu distributions and in particular have been tested with 10.04 and 12.04 (with the differences noted where applicable).
2.1 Required Packages
sudo apt-get update sudo apt-get -y install git-core subversion curl libpcap-dev
2.2 Click Modular Router
MobilityFirst router elements are currently implemented as user-level elements, and pose no compatibility issues with kernel versions. The latest versions of Click can be obtained from it's public site. Click sources are also maintained on a Git repository and can be pulled as shown below :
git clone git://github.com/kohler/click.git click
While the latest Click sources presented no issues as of this writing, a safe option is to check out version 2.0.1 from the installed repository:
cd click git checkout v2.0.1
Set and export the path of Click sources root folder ('click') to env. variable CLICK_SRC.
2.3 MobilityFirst Sources
- Release tarball:
Uncompress the MobilityFirst release tar ball and set the path of root folder ('mobilityfirst') to the variable MF_SRC.
An early internal release for GEC-16 experimentation is available from here
- SVN: The development versions of the prototype components can be checked out from the MobilityFirst SVN (this presently requires an account on the ORBIT testbed that has been approved for accessing MobilityFirst SVN):
svn checkout https://svn.orbit-lab.org/mobilityfirst/trunk/code/prototype mobilityfirst
Set and export path of folder 'mobilityfirst' to the variable MF_SRC
Note: A stable release of the GNRS server is packaged with the release and can be located under the directory $MF_SRC/gnrsd/jserver, which is the Java language implementation and is the current version used within MobilityFirst projects. Below, you can also find instructions to install GNRS sources from the development git repository.
2.4 Compiling Click with MobilityFirst Elements
Copy sources of MobilityFirst elements into designated folder under Click sources for compilation:
cd $MF_SRC/click/elements cp gstar/* gnrs/* app/* test/* utils/* $CLICK_SRC/elements/local/
From within Click source root folder, configure and compile for user-level operation, to include locally added elements, and to support multi-threading:
cd $CLICK_SRC ./configure --disable-linuxmodule --enable-local --enable-user-multithread make elemlist make sudo make install
The last step should install user-level Click binary under /usr/local/bin
2.5 Optional Packages
2.5.a OML Client Libraries (required for Click Monitor)
This is required for compiling the optional Click monitor module. It can be installed from the OML repository at Opensuse.org:
Append the following line to /etc/apt/sources.list
#10.04 deb http://download.opensuse.org/repositories/home:/cdwertmann:/oml/xUbuntu_10.04/ ./ #12.04 deb http://download.opensuse.org/repositories/home:/cdwertmann:/oml/xUbuntu_12.04/ ./
You will also need to add the repository key:
#10.04 curl http://download.opensuse.org/repositories/home:/cdwertmann:/oml/xUbuntu_10.04/Release.key | sudo apt-key add - #12.04 curl http://download.opensuse.org/repositories/home:/cdwertmann:/oml/xUbuntu_12.04/Release.key | sudo apt-key add -
You can now install the necessary OML client packages:
sudo apt-get update sudo apt-get -y install liboml2 liboml2-dev
Refer to detailed installation instructions at the OML project site.
2.5.b JDK/JRE and Maven Build Tools (required for GNRS)
Java JRE 1.6 or later is required to run the GNRS server and can be installed as:
# Ubuntu 10.04 sudo apt-get install openjdk-6-jre # Ubuntu 12.04 sudo apt-get install openjdk-7-jre
The above is sufficient if the pre-built server jar is available. If building GNRS from the sources then the full JDK and Maven build tools are required:
# Ubuntu 10.04 sudo apt-get install openjdk-6-jdk maven2 # Ubuntu 12.04 sudo apt-get install openjdk-7-jdk maven
2.6 Compiling Click Monitor (optional)
Note: This is known to compile correctly on 10.04 only, and is being adapted to work with updates to OML libraries for Ubuntu 12.04.
cd $MF_SRC/click/monitor make
2.7 Building GNRS Server (optional)
If building from the sources distributed along with the release or SVN versions of MobilityFirst sources, the GNRS server (Java version of server) can be located under $MF_SRC/gnrsd/jserver. The sources may also be obtained directly from the git repository on our open development project site as follows:
git clone git@bitbucket.org:romoore/gnrs.git
Next you have to install the external JAR dependencies. A handy Python script is provided to automate this task for you. Just run:
python install-to-project-repo.py -i
When prompted, the version is "0.6" (option 2) and the artifactId is "patricia-trie" (option 1). Once that's installed, you can compile and build the .jar file with:
mvn clean package
The first time you compile, Maven will automatically resolve and download all dependencies (be sure you have internet access). It will then compile the code and assemble the JAR. The output will be in the target/ subdirectory.
Note: If you are building the .jar as root user, then certain unit tests as part of the maven build may fail. You can avoid this by building as a regular user or if unavoidable then you may have to skip tests (not suggested), and can be done as below:
mvn clean package -DskipTests=true
3. Running the MobilityFirst Router
3.1 Router Configurations
Several sample configurations for MobilityFirst routers with differing functions can be located under MF_SRC/eval/conf/click eval/conf/click.
3.1.a Basic Router
This version implements GSTAR with Hop and GUID based forwarding. It does not resolve NAs for GUIDs using the GNRS service.
The below command line starts up a basic MobilityFirst router instance:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_BasicRouter.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<interface>
For example, the following brings up a router with GUID=1,
listening on interface 'eth0', as part of a 3-node configuration:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_BasicRouter.click \
my_GUID=1 \
topo_file=$MF_SRC/eval/topology/testcfg_1-gstar_3node.tp \
core_dev=eth0
where MF_BasicRouter.click defines the packet processing pipeline, topology file defines the GUID-based connectivity graph with other routers, and the interface is the network interface to operate on (e.g., eth0 or wlan0)
The Click options variable $MF_CLICK_OPTIONS can be '-j 4 -p xxxx', where option '-j' defines number of task threads, and option '-p' sets the port number for Click's control interface - to query the read handlers of named elements for current state, traffic statistics, etc.
3.1.b Router with Dynamic Name Resolution (GNRS) Support
The following starts up a router that supports GUID to NA resolution by interfacing to a GNRS server instance:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_Router.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<interface> \
GNRS_server_ip=<server-IP> GNRS_server_port=<port> \
GNRS_listen_ip=<local-IP> GNRS_listen_port=<client-port>
where MF_Router.click defines the packet processing pipeline, topology file defines the GUID-based connectivity graph with other routers, and the interface is the network interface to operate on (e.g., eth0 or wlan0). The GNRS server parameters correspond the location of local or remote instance of the global name resolution service - see following section on running the GNRS server.
3.1.c Multi-Router: Support for Multiple Routing Services
The basic routers above support the default set of delivery/routing services: unicast, GSTAR, and GNRS-based dynamic address binding. The MultiRouter configuration additionally supports a rich set of alternate delivery services, including multihome delivery, multicast and anycast services, which are invoked according to the Service IDentifier (SID) field in the packet's network header.
The following brings up a MultiRouter instance:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_MultiRouter.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<interface> \
GNRS_server_ip=<server-IP> GNRS_server_port=<port> \
GNRS_listen_ip=<local-IP> GNRS_listen_port=<client-port>
which, besides the Click element configuration file, has identical parameters as a basic router with GNRS support. The implementation currently supports anycast and multihome delivery services (multicast is being integrated).
3.1.d Access Router / IP Access Router: Host-Network Access Services
Host ---- (edge-interface) Access_MFR (core-interface) ---- MFR ---- ....
See MobiStack Project for details on configuring a host.
An access router implements three important functions to enable network access for MobilityFirst hosts. First, the router implements one or more access network interfaces corresponding to particular radio access networks or Ethernet. Second, the router (along with the host protocol stack) implements a low-level association protocol whereby it pairs the host's GUID (or the GUID of the network-attached object) with the network address (NA) of the attachment point and inserts the mapping into the GNRS. Third, it implements any protocol translation required to accommodate limited support in the access networks for new layer-3 protocols such as MobilityFirst.
The sample access router configurations packaged in the distribution support 1 access or edge-side interface and 1 back-haul or core-side interface (see figure above) as indicated in start-up command below:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_AccessRouter.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<core interface> \
GNRS_server_ip=<server-IP> GNRS_server_port=<port> \
GNRS_listen_ip=<local-IP> GNRS_listen_port=<client-port> \
edge_dev=<edge interface>
IP Access Router: In cases where access network supports only IP packets, the host protocol stack can encapsulate all MF packets (data and control) within IP packets with the destination IP set to the IP-addressed edge interface on the access router. The router then performs the protocol translation by either stripping or adding IP headers to provide connectivity to/from the MobilityFirst network, respectively. Any number of hosts can associate with an access router in this manner, and the router embeds a MAC/IP learning module that enables it to forward properly encapsulated packets on the correct interfaces that a particular host is connected on.
An IP access router configured with a single edge and core interfaces can be brought up with the following:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/MF_IPAccessRouter.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<core interface> \
GNRS_server_ip=<server-IP> GNRS_server_port=<port> \
GNRS_listen_ip=<local-IP> GNRS_listen_port=<client-port> \
edge_dev=<edge interface> \
edge_dev_ip=<edge i/f IP> \
3.1.e Test Configurations: File Sender and Receiver
File transfer based traffic source and sink are available for setting up quick tests of the routing functions. The sender constructs packets with MF network headers and (as is) requests default unicast delivery. Simple modifications will enable traffic generation for other delivery types such as multicast (by basically changing the SID). Since these functions are implemented as extensions of basic routers, these sender/receiver nodes also participate in MF control protocol. They cannot, however, forward packets for others.
The following brings up an instance of file sender:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/test/MF_FileSender.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<interface> \
GNRS_server_ip=<server IP> GNRS_server_port=<port> \
GNRS_listen_ip=<local-IP> GNRS_listen_port=<client-port> \
src_GUID=<sender GUID> \
dst_GUID=<dest GUID> \
file_to_send=<full path of file to send> \
chk_size=<size of chunk in bytes> \
delay=<seconds to wait before starting to send> \
pkt_size=<size of L2 (header + payload) in bytes>
Note the the router GUID and sender GUID above can be the same. The chunk or block is the hop-by-hop reliable data transfer granularity. We expect chunk sizes to be between a few MB to a few hundred MB for large data transfers, but they can also have small payloads corresponding to short messages.
The following brings up a file receiver instance:
/usr/local/bin/click $MF_CLICK_OPTIONS $MF_SRC/eval/conf/click/test/MF_FileReceiver.click \
my_GUID=<router GUID> topo_file=<topology file> \
core_dev=<interface>
The file receiver is a simple sink, and does not even require GNRS support. Note that the router GUID of the receiver should be the GUID used as destination while configuring the sender.
3.2 Topology Control
Since multiple routers may run in a single LAN, connectivity needs to be enforced and packets destined to non-neighbor nodes be dropped. This is enabled in the MobilityFirst router pipeline by way of topology enforcement element that takes a GUID-based connectivity graph passed as a topology file at start up time. Consider below a simple topology with three MobilityFirst routers:
Sender ---- MFR1 ---- MFR2 ---- MFR3 ---- Receiver
100 1 2 3 101
MFR - MobilityFirst Router, and Sender/Receiver are source/sink configs described above.
The following file defines the 3-node topology illustrated above:
#syntax: <node-GUID> <neighbor-count> <neighbor-GUID1> [<neighbor-GUID2>] ... 100 1 1 1 2 2 100 2 2 1 3 3 2 2 101 101 1 3
Sample topology definition files can be located under the folder MF_SRC/eval/topology.
3.3 Logging Configuration
Set environment variable 'MF_CLICK_LOG_LEVEL' to integer between 0 and 7, corresponding to the following debug levels:
| Value | Log Level | Description |
| 0 | TRACE | |
| 1 | DEBUG | |
| 2 | INFO | |
| 3 | TIME | Same as INFO. In addition, the message is prefixed with a micro-second precision timestamp |
| 4 | WARN | |
| 5 | ERROR | |
| 6 | CRITICAL | Cases of out of memory, approaching resource limits, etc. |
| 7 | FATAL | Unable to proceed, or when integrity may be compromised |
3.4 Running GNRS Service Instance
The GNRS server can be run from within the $MF_SRC/gnrsd/jserver or the corresponding installation directory if GNRS sources were installed from the project git repository:
java -jar target/gnrs-server-1.0.0-SNAPSHOT-jar-with-dependencies.jar \
<server.xml>
Sample configuration files, including a server.xml, can be located under $MF_SRC/gnrsd/jserver/src/main/resources.
