LISP Database Architecture: LISP-DDT
The real magic that overcomes the challenges of the Internet and provides the LISP functionality is the mapping database. The mapping database contains the EID-to-RLOC mappings, which make it possible to identify which EIDs map to what locators. This mapping database allows support for millions of sites and changes happening across the sites. You can deploy multiple stand-alone MRs and MSs, but for a truly globally scaled MS, a hierarchical mapping system is required. In addition, a scaled and resilient mapping system needs to have an interface to the mapping system. LISP Delegated Database Tree (LISP-DDT) is one such mapping system that provides scalability and resiliency in a LISP-enabled network.
LISP-DDT provides a hierarchy for instance IDs and EID prefixes. LISP-DDT defines a new device type called a DDT node. DDT nodes are preconfigured with delegations that are based on static and secure delegation hierarchy, much like DNS. The parent DDT node is configured with a set of more specific sub-prefixes that are further delegated to other DDT nodes lower in the hierarchy. The DDT map resolvers send map requests to a preconfigured DDT node RLOC. The DDT nodes return map referral messages in response to the map request messages. The map referral message is a new LISP message type that assists with traversing the database tree. When the DDT node responds with a map referral message, it indicates either of the following:
It is able to or will be able to find the requested mapping.
Another DDT node is queried for more specific information.
Before discussing what different map referral messages mean, it’s vital to understand the extended EID prefix (XEID prefix). In order to have uniquely identifying prefixes in the mapping database, a unique database index key is created. This index key is formed by logically prepending and appending several fields to the EID prefix. These fields include a 16-bit database ID (DBID) field, a 32-bit instance ID (IID) field, a 16-bit AFI field, and a variable-length EID prefix field. The resulting concatenation of these fields is called an XEID prefix. All the EID prefixes in DDT are DDT clients and are referred to as XEID prefixes.
A map referral message can indicate two kinds of responses:
Positive referrals: These responses are used to discover a DDT node’s RLOC for a given EID prefix:
Type 0 (NODE-REFERRAL): This type indicates that the replying DDT node delegated an XEID prefix that matches the requested XEID to one or more other DDT nodes. The map referral message contains a map record with additional information, most significantly the set of RLOCs to which the prefix was delegated.
Type 1 (MS-REFERRAL): This type indicates that the replying DDT node delegated an XEID prefix that matches the requested XEID to one or more DDT map servers.
Type 2 (MS-ACK): This type indicates that a replying DDT map server received a DDT map request that matches an authoritative XEID prefix for which it has one or more registered ETRs. This means that the request can be forwarded to one of those ETRs to provide an answer to the querying ITR.
Negative referrals: These responses are used to indicate the following actions:
Type 3 (MS-NOT-REGISTERED): This type indicates that the replying DDT map server received a map request for one of its configured XEID prefixes that has no ETRs registered.
Type 4 (DELEGATION-HOLE): This type indicates that the requested XEID matches a non-delegated sub-prefix of the XEID space. This is a non-LISP “hole” that was not delegated to any DDT map server or ETR.
Type 5 (NOT-AUTHORITATIVE): This type indicates that the replying DDT node received a map request for an XEID request for which it is not authoritative. This occur if a cached referral becomes invalid due to a change in the database hierarchy.
Figure 2-19 shows a global LISP mapping system using LISP DDT. It is clear from this figure that there are primarily three different LISP nodes:
DDT root nodes
DDT map resolver nodes
DDT map server nodes
)
FIGURE 2-19 Global LISP Mapping System Using LISP-DDT
The DDT root node forms the logical top of the database hierarchy. It is configured to be authoritative for all IIDs, AFIs, and EIDs included in the DDT hierarchy. The root node also delegates IIDs, AFIs, and EIDs to the lower-level DDT nodes that are authoritative for their piece of hierarchy. DDT root nodes perform the following functions:
Accept map requests (from DDT map resolvers)
Compute and return map referral Type 0 messages (positive)
Compute and return map referral Type 4 messages (negative)
The DDT map resolvers performs the following functions:
Accept and cache map requests from ITRs and PITRs
Forward map requests to DDT root nodes
Accept and follow map referral messages iteratively to query the DDT hierarchy
Resolve the location of the DDT map server (map referral MS-ACK)
Detect loops/delegation errors
Send negative map reply (NMR) messages to ITRs and PITRs
The DDT map server nodes performs the following functions:
Forward map requests to registered ETRs
Return proxy map replies to ITRs
Compute and return map referral DELEGATION-HOLE messages
Compute and return map referral MS-NOT-REGISTERED messages
LISP-DDT Operations
To understand the LISP-DDT operations, examine the topology shown in Figure 2-20. In this topology, nodes Root-N1, DDT-N2, DDT-N3, and MS are configured with child prefixes and authoritative prefixes. Here are some instances:
Root-N1 is configured as root for *
Root-N1 delegates IID=0, 10.0.0.0/8 to DDT-N2
DDT-N2 delegates IID=0, 10.0.0.0/16 to DDT-N3
DDT-N3 delegates IID=0, 10.0.0.0/17 to MS
)
FIGURE 2-20 Topology with LISP-DDT
The topology also consists of MR, ITR1 and ITR2, and an ETR1 node. In this topology, MR is configured to point to the DDT root RLOC. The ETR1 node registers its prefix with MS, where the ETR prefix is within the delegation range of the MS node.
When the ITR sends a first map request message to the MR, the MR caches the map request and queues the pending requests. It then checks the referral cache, where it finds no entry. It then forwards the map request to its statically configured DDT root, which is the Root-N1 node in this case. Root-N1 then sends the map referral to the MR. In the map referral, Root-N1 tells the MR which node to try next, which in this case is the DDT-N2 node. This process keeps on happening until the map-request reaches the MS device that has the EID delegation. On receiving the map request, the MS node processes the map request and sends a map referral/MS-ACK to the MR, which then dequeues the pending request and caches the map referral. The MS node also forwards the map request to the ETR. Finally, the ETR sends a map reply to the ITR.
If the MR, on receiving the map request, finds an entry in the referral cache, it sends the map request to the cached referral MS. The MS node receives and processes the map request and sends the map referral/MS-ACK to the MR, which dequeues the pending request and forwards the map request to the ETR. The ETR then sends the map reply to the ITR.
The scenario and operational flow just described occur when the ETR EID prefix is registered with the MS, but imagine what happens when the EID prefix is not registered with the MS node. In such a scenario, the MS node, on receiving the map request, computes the DELEGATION-HOLE and sends a map referral/DELEGATION-HOLE (Type 4, negative referral, message) to the MR. The MR, on receiving the negative map referral, dequeues the pending request and caches the map referral. The MR then sends a negative map reply with the TTL value 15 minutes for the DELEGATION-HOLE to the ITR. The DELEGATION-HOLE set in the ACT (Action) field of the map referral message indicates that the XEID is not a LISP destination.