XIA Prototype Overview
The XIA prototype implementation is based on the Click modular router. The current release supports the four basic XIA principal types: AD (Administrative Domain), HID (Host IDentifier), SID (Service IDentifier), and CID (Content IDentifier). The prototype includes the Click implementation of the XIP network stack, socket API for XIA (Xsocket API), and network bootstrap/support services (e.g., routing, initial host configuration, name service). XIA prototype can be running on various environments including a local machine, VMs, GENI testbeds.
[ 
XIA prototype stack modules ] (https://raw.github.com/wiki/XIA-Project/xia-core/Xia-prototype-modules.png)
The current XIA prototype release includes the Click implementation of the XIP network stack, socket API for XIA, and network bootstrap/support services (e.g., routing, initial host configuration, name service). Each of the modules is described in more detail below.
The XIA modules implemented in Click are:
- the core eXpressive Internet Protocol (XIP)
- X-Address Resolution Protocol (XARP)
- X-Control Message Protocol (XCMP)
- Content Cache Module
- XIA Transport Protocols
- X-Datagram Protocol (XDP)
- X-Stream Protocol (XSP)
- X-Chunk Protocol (XChunkP)
The prototype also provides an XIA socket API (Xsocket API) both in python and C versions for XIA application programmers.
In order to facilitate the network and the host configurations, the prototype packages the network bootstrap/support services including routing, X-Host Configuration Protocol (XHCP), and Name Service (NameSrv).
The following modules/functionalities (not included in the current release) will be added in the next version of the XIA prototype: Mobility support, a principal type for IPv4 (4ID), high-speed XIP implementation, etc.
XIA sockets leverage the standard BSD sockets, extending them to work with the XIA communication schemes. In the current implementation, the Xsocket used by the API is a normal UDP socket that is used to communicate with the click transport layer. X-datagram protocol (XDP), X-stream protocol (XSP), and X-chunk protocol (XChunkP) are implemented. Those sockets are used by the user process to send or receive packets in a lightweight connectionless way (XDP), in a reliable connection-oriented way (XSP), or for retrieving/publishing content chunks.
XIA Socket APIs in python and C are provided for XIA application programmers.
- C/C++ API Documentation
- Python API Documentation
The XIA prototype implements three different types of transport protocols: X-datagram protocol (XDP), X-stream protocol (XSP), and X-chunk protocol (XChunkP).
XDP is a simple message-based connectionless protocol. XDP does not set up a dedicated end-to-end connection, thus no handshaking establishment process for providing reliability, ordering, or data integrity. Communication is achieved by transmitting data in one direction from source to destination without verifying the readiness of the receiver.
- Unreliable – There is no concept of acknowledgment, retransmission or timeout.
- Not ordered – If two messages are sent to the same destination, the order in which they arrive cannot be predicted.
- Lightweight – There is no ordering of messages, no tracking connections.
- No congestion/flow control – XDP does not support any congestion or flow control.
Network service applications that use XDP include: routing, X-host configuration protocol (XHCP), and name service (NameSrv), etc.
Xsocket API associated with XDP include: Xsocket(XSOCK_DGRAM), Xsendto(), Xrecvfrom().
TCPSpeaker paper https://www.net.t-labs.tu-berlin.de/~dlevin/mthesis/main.pdf
XSP is a simple connection-oriented protocol, requiring handshaking establishment process to set up end-to-end communications. Once a connection is set up, data can be sent bi-directionally over the connection reliably.
- Reliable – XSP guarantees reliable data delivery by managing acknowledgment, retransmission and timeout; any packet not acknowledged within timeout is retransmitted.
- Ordered – The destination rearranges according to sequence number; when data packets arrive in the wrong order, XSP buffers the out-of-order data until all data can be properly re-ordered and delivered to the application.
- Handshaking – XSP requires two-way handshake to set up a socket connection, before any user data can be sent.
- No congestion/flow control – XSP does not support congestion control or flow control at this point.
Xsocket API associated with XSP include: Xsocket(XSOCK_STREAM), Xbind(), Xconnect(), Xaccept(), Xsend(), Xrecv().
To establish a connection, XSP uses a two-way handshake. Before a client attempts to connect with a server, the server must first bind to an SID to open it up for connections. To establish a connection, the two-way (or 2-step) handshake occurs:
- SYN: Connection establishment is requested by the client sending a SYN to the server. The SYN-packet's sequence number is set to zero.
- SYN-ACK: In response, the server replies with a SYN-ACK. The acknowledgment number is set to the received sequence number (zero), and the sequence number of the SYN-ACK packet is set to zero.
If any of those handshaking packets are lost, then the connection establishment process re-initiated by the client re-sending a SYN to the server. (The default maximum number of connection retries is set to 30).
At this point, both the client and server have connection states (sequence number, acknowledgment number, etc), and can start message exchange over the connection.
The connection termination allows each side of the connection to terminate independently. The current implementation of connection teardown is as follows:
- When Xclose() is called, it sets the tear_down_timer and keeps the states (e.g., window, unacked packets, etc).
- In the meantime, the other end side of the connection can properly operate (e.g., receive lost packets, if any).
- Once the tear_down_timer expires, the corresponding states are deleted.
There is no control message (exchanged for connection termination) that notifies the other end on closing the socket. (This works fine on conventional client-server apps. A server first Xclose() right after Xsend() all data; a client later Xclose() after Xrecv() all data from the server).
The default value for tear_down_timer is set to 4 minutes: _teardown_wait_ms = 240000;
XSP supports reliable data delivery by managing acknowledgment, retransmission and timeout; any packet not acknowledged within timeout is retransmitted. XSP uses a ''sequence number'' to identify each packet of data, and an initial sequence number is always zero. For acknowledgment, XSP uses a ''cumulative acknowledgment'' scheme, where the receiver sends an acknowledgment signifying that the receiver has received all data preceding (and including) the acknowledged sequence number. The sender maintains a single retransmission timer for each connection. When sending a new packet, the sender (re)sets the timer, and stores the packet in the retransmission buffer. The sender also updates (reset) the timer when receiving an acknowledgment for the previously unacked packets in the retransmission buffer (then they are cleared from the buffer). The timer expiration triggers the retransmission of all the unacknowledged packets in the buffer.
The default value for retransmission timer is set to 300 ms: _ackdelay_ms = 300;
XChunkP is a reliable transport protocol for content retrieval in the XIA network. XChunkP retrieves a requested content from any intermediate routers (or the original publisher) who hold a copy of the content.
- Reliable – XChunkP supports reliable content delivery by request timeout; if the requested content is not delivered within timeout, the request is retransmitted to the network.
- Chunk-based – The content request and delivery from/to the requesting application is chuck-based. (The actual underlying transmission in the network is packet-based, i.e., chunk packetization).
- Integrity check – The integrity of the delivered content is checked by applying the cryptographic hash (e.g., SHA-1) on the delivered content, comparing to the requested CID (i.e., supporting the intrinsic security).
Xsocket API associated with XChunkP include: Xsocket(XSOCK_CHUNK), XrequestChunk(), XrequestChunks(), XgetChunkStatus(), XgetChunkStatuses(), XreadChunk().
XChunkP supports reliable content retrieval in a very simple way. When requesting a content chunk, the XChunkP sets a timer, and sends out the request. If the requested content is not delivered within the timeout, the request will be resent to the network. The default value for the request timer is set to 300 ms.
In addition, the integrity of the requested content is also verified when the content is delivered to the requester. If failed, the content is discarded, and the XChunkP reports an error to the requesting application.
XIA facilitates content retrieval by allowing the content requests to be served by any intermediate routers (or the original publisher) who hold a copy of the content. In the XIA prototype, content cache module is responsible for such in-network caching at routers and also used for publishing and serving contents at end-hosts.
The current XIA prototype implements on-path caching (off-path caching will be added in the next release). Routers store chunk responses (i.e., contents) into their content cache when relaying them, and serve content requests when receiving them if found in the cache.
Routers recognizes a content response (i.e., relaying the content itself back to the original requester) by checking the primary intent of the packet's source DAG; if the principal type is CIDs, then it is a content response, which triggers the content caching at the routers.
Routers recognizes a content request (i.e., relaying the content request to the original publisher) by checking the primary intent of the packet's destination DAG; if the principal type is CIDs, then it is a content request, which triggers the cache lookup at the routers.
The in-network caching can take place in any routers that relays content chunks back to the original requesting hosts. The current implementation of the in-network caching procedure is as follows:
- When receiving a content chunk, a router's cache is first checked if the content is already stored.
- If it is a new content, the cache space available for the content is examined.
- The previously cached contents, in the case of no space for new content, are evicted according to the cache replacement policy setting.
- The new content is stored in the cache. The router relays the content chunk back to the original requesting host.
The default size of the content cache (at routers) is set to 1024 * 1024 * 1024 bytes.
The default cache eviction policy currently implemented is based on first-in first-out (FIFO).
Note that the actual transmission of content chunks in the network is packet-based (i.e., chunk packetization). In other words, a single content chunk may be divided into multiple packets, each of which is individually delivered via routers to the requesting host; those packets share the same CID information (but with different offset values) in the ''content header'' to signify that they make up a content chunk by using their offsets. The content header includes the offset field that specifies the offset of a particular fragment (i.e., packet) relative to the beginning of the original (unfragmented) content chunk.
If a packetized content chunk is relayed at routers, each packet of the chunk is partially stored in the cache, and reassembled into the original chunk once all the packets come through the router.
Routers, when relaying a content request, can directly serve the request if the content is found in the cache. The procedure is as follows:
- When receiving a content request, a router first looks up its cache for the content.
- If not found in the cache, the request is forwarded (towards the original publisher).
- If found in the cache, the content chunk is forwarded to the original requesting host.
If the chunk is larger than the packet size, then it is sent via multiple packets (i.e., chunk packetization). Each packet of the chunk is identified using the offset field in the content header, which is used for reassembling into the original chunk once all the packets reach the requesting host.
The default packet size for the chunk packetization is set to 1024 bytes.
The content cache module is also used for publishing and serving contents at end-hosts. When publishing contents (i.e., storing them) into the local content cache, hosts can specify some relevant cache control information associated with the contents. The user applications can specify such information when initializing its local cache space using Xsocket API call, XallocCacheSlice():
- Policy – the policy to use for the local cache, e.g., FIFO, LRU, etc
- Time-to-live (TTL) – the duration for which the contents can be stored in the cache (in sec); 0 means permanent(differ by policy)
- Cache size – the maximum cache size for the local cache
There are several policy options given for the local cache:
- Eviction policy – FIFO and LRU
- Exit policy – RETAIN_ON_EXIT and REMOVE_ON_EXIT
The default policy setting for the local cache is FIFO for cache eviction and RETAIN_ON_EXIT for exit (i.e., the published contents are kept in the cache even after the associated application terminates).
Once initializing the local cache, the applications can publish content(s) from a buffer (or a file) using Xsocket Chunking API calls.
Xsocket API associated with publishing contents include: XallocCacheSlice(), XputChunk(), XputFile(), XremoveChunk(), XfreeCacheSlice(), XfreeChunkInfo().
XIP is XIA's common network layer for all principal types. It handles per-hop packet forwarding and routing in routers as well as at end-hosts. In the XIA prototype, XIP is implemented as Click ''elements''. The Click configuration files provided in our source uses the elements to implement an XIA router and host. Best overview of XIP is provided in our NSDI paper.
-
We implement the following modules/functionality: ** Routing tables for 4 different principals (AD, HID, SID, CID) ** AD/HID/SID/CID routing table implementation using a simple hash table ** DAG processing ** DAG creation and simple verification
-
We did not implement the following: ** Cryptographic verification of identifiers
-
Implementation of DAG processing DAG processing is the core part of XIP. We implement the DAG processing logic in the Click configuration file, and each element performs simple task such as looking up an XID in the table, classifying the principal type, and choosing fallback XIDs. For those of you who want to implement a new principal type will need to change the configuration file and optionally add a special processing logic for the new principal type.
XARP is the XIA version of address resolution protocol, used for resolving target XIDs into link layer addresses (e.g., mac addresses). Similar to ARP, XARP is a request and reply protocol that runs encapsulated by the link layer protocol. The XARP operation and its message format are quite similar to ARP:
- XARP query – a broadcast XARP message (destination mac address FF:FF:FF:FF:FF:FF) requesting an answer for target XID
- XARP response – a unicast XARP message (to the source of XARP query) resolving target XID to link layer address
The XARP message header specifies these types, as well as the size of addresses of each. The message header is completed with the operation code for query (1) and response (2). The payload of the packet consists of four addresses, the hardware (e.g., MAC addresses) and protocol address (i.e., XIDs) of the sender and target. The protocol field in the XARP header specifies the internetworking protocol for which the XARP query is intended. In the XIA prototype, for eXpressive Internet Protocol (XIP), this has the value 0x9999.
More detailed XARP procedure is as follows:
-
When a default router understands/supports a certain XID type (say, HID):
- A host always first forwards a packet (whose destination is HID) to the default router. (so, no XARP query for HID).
- The router knows whether the target HID is in the same ethernet by looking up its routing table; router should know all HIDs in his network, otherwise he cannot deliver the incoming packets properly.
- If the target HID is in the same ethernet, the router sends ''XCMP redirect message'' to the host, instructing the host's XARP table so that subsequent packets will be sent directly to the target HID in the same network.
- Otherwise, the router forwards the packet as usual.
-
When the default router does not yet supports a certain XID type (say, CID):
- A host broadcasts XARP query for CID.
- If there is CID in the same network, then the corresponding XARP response will be generated and will handle the case.
- Otherwise, upon the XARP query timeout, the host sends the packet to the default router, which may follow the fallback path in the DAG.
XCMP is the XIA version of ICMP. It works in a very similar fashion to vanilla ICMP. However, XCMP only implements a subset of its features. The packet format is the same as ICMP except XCMP includes an XIP header as opposed to an IP header.
XCMP currently supports the following:
- Echo / Echo Reply
- Hop-Limit Expiry
- XCMP Redirect
- XID Unreachable
To test these functions, sample Xping and Xtraceroute code is included.
As a module within click, XCMP is stateless and thus can be instantiated in multiple places without any worry. As such, XCMP modules are used in numerous places within our click router code.
In order to facilitate the network and the host configurations, the XIA prototype provides the network bootstrap/support services including routing, X-Host Configuration Protocol (XHCP), and Name Service.
- The network-wide bootstrap procedure is as follows:
- Routing: Each router runs routing process so as to set up AD-level routing.
- XHCP server: XHCP-server process runs at routers, and sends out AD-wide broadcast of [AD, default gateway router HID, name server DAG].
- Name service: Name service process runs at a single specific host (its AD and HID are predefined), handling name register and query requests from other hosts in the network.
- XHCP client: XHCP-client process runs at hosts. Obtaining the network information from XHCP beacon, it registers itself to the default gateway router, and register its (host)name to the name service.
- Any user applications if requested by user.
The current release of XIA prototype supports a simplified XIA network where each AD has a single gateway router and all the hosts in an AD are directly connected to the gateway router. In such a network, routing at the AD level is necessary to make any hosts in the network communicate each other. The XIA prototype has each gateway router running an AD-level routing process in order to populate its routing table. The AD routing in the current release is quite simple and is based on link-state routing algorithm.
- XDP – routing process operates on top of the connectionless XDP.
- Hello – routers periodically transmit hello messages to their neighbors (i.e, neighboring AD routers), indicating the presence to their neighbors.
- LSA flooding – routers, based on the hello messages from neighbors, periodically broadcast their link-state advertisement (LSA) over the network.
- Shortest path – routers, with full knowledge of the network topology using received LSAs, calculate the shortest paths to all ADs in the network.
The default values for hello interval and LSA interval are set to 1 and 3 seconds, respectively.
XHCP is a host configuration protocol for the XIA network.
When hosts first boot up, they must be configured before they can communicate with other hosts.
The XHCP-server process, running at each gateway router, periodically sends out an XHCP beacon that contains the following configuration information:
- AD (Administrative Domain)
- Gateway router HID
- Name server DAG
When receiving an XHCP beacon, the XHCP-client process running at each host updates its AD information, gateway router HID, and name server DAG. In addition, the XHCP-client process registers its host HID to the gateway router so that the router can deliver incoming packets to the host properly.
The default values for XHCP-server beacon interval is set to 1 second.
XHCP runs on top of connectionless XDP.
Name service is a network service for registering names and providing responses to name queries. It maintains a table that maps a human-recognizable name to a DAG.
The Xsocket provides name service API calls:
- XregisterName(name, dag) – registers a name (e.g., www_s.webserver.cmu.xia) mapping to a DAG (e.g., AD0:HID0:SID1) into the name server
- XgetDAGbyName(name) – obtains a DAG by querying a name to the name server
If the name server receives a name query that is not resolved (i.e., not registered name), an error message is sent back to the querying host.
Name service runs on top of XDP.