Wednesday, July 11, 2012

What is LISP DDT?

Some background on LISP

LISP (Locator/Identifier Separation Protocol) is a smart and novel method to create overlay networks with features such as multi-homing, mobility and VPN-segregation. These feats are possible because LISP makes a distinction between the 'who' and the 'where'.
"The separation of location and identity is a step which has recently been identified by the IRTF as a critically necessary evolutionary architectural step for the Internet."
- N. Chiappa in draft-chiappa-lisp-introduction-00 
An example would be that my IPv6 prefix 2001:67c:208c:10::/64 (the 'who') currently is located behind the following WAN IP addresses: 62.194.155.106, 217.8.107.2 and 2001:67C:21B4:1::2 (the 'where'). In this example my prefix is multi-homed behind 3 connections, and I'm doing IPv6 over IPv4 next to IPv6 over IPv6. This is possible because this single IPv6 prefix can have multiple Routing Locators (the 'where') and LISP is address-family agnostic.

Mapping systems for location information

As you can imagine, the key to protocols like LISP is locating who is where in a fast and efficient way.

To create more context: with the Border Gateway Protocol (BGP) all participating nodes (routers) have all information about everybody in memory. When an organisation announces a prefix to the internet, all routers attached to the default-free zone have to store how they can reach that prefix. This is called a "push-based" mechanism, because information is pushed towards all nodes regardless of whether they need that information. After all, not all networks have to send packets to all other networks on the planet.

The designers of LISP choose a vastly different approach: a "pull-based" mechanism. The moment a LISP node receives a packet it needs to forward to a certain destination, it will do a lookup in the mapping system where that destination is actually located. This ensures LISP routers only need to store a limited amount of information compared to routers running BGP. I imagine my CPE at home is only communicating with say 200 networks at any given time.

LISP DDT

To get a better understanding of what LISP DDT is, an analogy can be made between the DNS mapping system and LISP DDT. RFC 1034 states:
"The sheer size of the database and frequency of updates suggest that it must be maintained in a distributed manner, with local caching to improve performance. Approaches that attempt to collect a consistent copy of the entire database will become more and more expensive and difficult, and hence should be avoided."
DNS is not copying /etc/hosts around, it is an hierarchical distributed database maintained by many organisations. At the top there is the DNS root ".", and for instance the ccTLD "nl." is delegated to the Dutch Registry SIDN. Then in turn, that registry delegates a domain like "snijders-it.nl" to me.

LISP DDT stands for LISP Delegated Database Tree, it is an hierarchy for prefixes and other LISP related information. The root of the tree is authoritative for "key-ID 0, EID 0, AFI 0 and EID-prefix 0/0". This basically means 'everything'. At the root, prefixes within an address-family are delegated to Map Servers, which in turn could delegated smaller chunks of those prefixes down to other Map Servers.

Time for an example! The prefix 2001:67c:208c::/48 belongs to my organisation. I've asked the LISP DDT Root operators to delegate that prefix to certain Map Servers operators with which I have a (business) relation. These Map Servers (currently for instance 217.8.98.42 and 195.50.116.18) are authoritative for my /48, and it is to these Map Servers my LISP routers register 'who' and 'where' they are (think dynamic DNS!).

Now if some LISP router "LISP-CORP-B" wants to send packets towards a HOST-A (e.g. 2001:67c:208c:10::1) in my prefix, it will ask it's Map Resolver where to find that host. The Map Resolver will query the root where it can find more information, and the DDT Root will refer the Map Resolver for this /48 to 217.8.98.42 and 195.50.116.18. The Map Resolver will then query these Map Servers and eventually return all relevant information to the original request LISP-CORP-B.

The following image providers a simplified overview of how LISP-CORP-B learns how to reach an host at Job's office (click for larger image):



Status of LISP DDT

LISP DDT is currently being developed inside the IETF, this Internet-Draft describes how it works: draft-fuller-lisp-ddt. Cisco has developed a few implementations of LISP DDT, which are currently being used in production environments. In May 2012 the LISP Beta Network migrated from LISP-ALT to LISP-DDT and has been running smoothly ever since. The LISP DDT-ROOT is operated by  volunteers from various organisations such as Verisign, InTouch NV, Cisco and myself

Closing words

LISP DDT is the most promising mapping system in the LISP world, there is still some work to be done to develop this novel technology into a mature protocol. If you have any questions don't hesitate to contact me, I can help you assess what LISP and DDT can mean for your organisation.