Wiki
Clone wikimobilityfirst / Click_Router_Software_Design
Contents:
Overview
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.
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.
Chunk Management
A chunk can have the follow status:
CHUNK STATUS ++++++++++++ ST_INITIALIZED //a chunk that memory was allocated, but routing information is missing ST_COMPLETE //all packets have been received, ST_INITIALIZED must be set. ST_RESOLVING //chunks that lookup packets have been sent to GNRS. ST_BUFFERED //stored chunks ST_CACHED //cached chunks ST_EXCLUSIVE //chunks that cannot be modified by other click elements. ST_READY_TO_DEL //chunks that are ready to delete ----------------------------- A ST_COMPLETE chunk must be ST_INITIALIZED at the same time. A chunk without ST_INITIALIZED cannot be ST_RESOLVING, ST_BUFFERED, ST_CACHED at the same time. A ST_READY_TO_DEL chunk cannot be other status.
Buffer Management
TBD
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
Updated