Unofficial guide to the LISP map-encap solution for the routing scalability problem

To the main Ivip page

Robin Whittle rw@firstpr.com.au 2009-07-31

Disclaimer and link to the official LISP site

This page is my attempt at maintaining an up-to-date list of LISP Internet drafts (IDs) and other documents, created when the LISP people did not yet have such a page.

From late July 2008, they have a page:

www.lisp4.net <<<< Please refer to this page for authoritative info from the LISP team.  

This site has tutorials, articles, presentations, diagrams, links to Internet Drafts etc.

See also the LISP mailing list: http://www.ietf.org/mail-archive/web/lisp/current/maillist.html

In March 2009, there are plans for an IETF Experimental Working Group for LISP.

My page still contains a bunch of hopefully useful things about LISP, so I will keep it going - not least the section on some of the critiques of LISP.

Please let me know of any errors or suggestions for improvements, and don't confuse what you read below with what the LISP developers themselves write or how they depict their proposals.

I need to update this page!


Contents

>>> Introduction

>>> Main LISP web pages and documents

>>> Internet Drafts

>>> Significant RRG messages

>>> Critiques


Explanation of LISP-ALT map-encap system

A diagram from Dino Farinacci.  Please see related explanation in the RRG list 2008-06-29: here and here.

Introduction

LISP (Locator Identity Separation Protocol) is the most prominent of the "map-encap" schemes being considered by the IRTF Routing Research Group.
"Map-encap" or means "map and encapsulate".  The ITR (Ingress Tunnel Router) receives a traffic packet to a "mapped address" and looks up some mapping information for that destination address.  It then encapsulates the packet in an outer header and so tunnels the packet to an ETR (Egress Tunnel Router) specified in that mapping information, where it is decapsulated and sent to the proper destination.  See my introduction to this field for Newbies: psg.com/lists/rrg/2008/msg00623.html .

I am critical of LISP and believe that my own proposal, Ivip, or APT would be better than LISP.  Despite all this activity, including major contributions from engineers at Cisco - who build most of the Internet's routers and have a reputation for extraordinarily reliable equipment and great support - I find LISP a generally unadventurous and technically problematic set of proposals.  

There are various LISP Internet Drafts (IDs), by various authors and some of them are different solutions to a single problem.  For instance, one would not ordinarily implement more than one of the mapping distribution solutions: CONS, ALT, NERD or Modified Distributed Hash Tables.  So it can be tricky reading these documents trying to imagine a complete system.  Be sure to check the RRG list psg.com/lists/rrg/ and before 2007-09-12 the RAM list www.ietf.org/mail-archive/web/ram/ for discussions on these proposals.

If you find LISP IDs hard to understand, you are not alone, as one RRG member wrote on 2007-11-26: 2007/msg00615.html .  Internet Drafts are technically dense, and my original monolithic Ivip ID has been too much for some folks.  

The RRG home page www.irtf.org/charter?gtype=rg&group=rrg lists the charter of the group.  The charter and a December 2007 announcement by the co-chairs: psg.com/lists/rrg/2007/msg00686.html is the best information I know of regarding the RRG process.  My summary of this is that the RRG is developing various proposals to deal with the routing scalability problem, with a view to achieving rough consensus in March 2009 on what to recommend to the IESG for development in one or perhaps more IETF WGs.

All the proposals are listed at the RRG wiki page: www3.tools.ietf.org/group/irtf/trac/wiki/RoutingResearchGroup . You may well find more up-to-date LISP information there than what I have below.  In the event that a central, comprehensive, LISP page appears, I will point to it from here and delete most of the links, but will probably retain links to major critiques of LISP.

Main LISP web pages and documents

Be sure to see: www.lisp4.net

There is a public discussion list for LISP-ALT.  The LISP-Interest mailing list archives are at: www.queuefull.net/lisp-interest/  To subscribe, send a message with the subject line "subscribe" to <lisp-interest@ lists.civil-tongue.net>.  (For good measure I made the body of the message "subscribe" too.)

Please check the entries at the LISP section of the RRG wikiwww3.tools.ietf.org/group/irtf/trac/wiki/RoutingResearchGroup#LISP.

Analysis of LISP with respect to the RRG Design Goalstools.ietf.org/html/draft-brim-lisp-analysis .

Proposal for a LISP BOF (Birds of a Feather) meeting at the IETF meeting in Dublin (July 2008), which would consider accelerating the development of LISP in the IETF, apparently in advance of the RRG's timetable. psg.com/lists/rrg/2008/msg00783.html which points to: www.1-4-5.net/~dmm/lisp.bof (2008-03-14). This message included a list of LISP IDs - presumably only the ones which are considered part of the future LISP project.  On 2008-06-27 Jari Arko wrote about this proposal for a LISP experimental Working Group in the IETF: psg.com/lists/rrg/2008/msg01638.html.



LISP Internet Drafts

I have not been able to keep this up to date . . .

This is a list of LISP IDs, in approximate date order of first publication with my quick notes.  I link to the generic name, not the latest version.

* Those with an asterisk were not mentioned in the list of IDs in the above-mentioned BOF proposal of 2009-03-14, and so should probably not be considered as part of the overall LISP project from that date.

See also the link above to draft-brim-lisp-analysis, which evaluates LISP with respect to the RRG Design Goals.

To find the LISP IDs in the IETF system (some mentioned below were not in the system yet): https://datatracker.ietf.org/idtracker/?search_filename=lisp  .


draft-farinacci-lisp (2007-01-17)

Basic architectural ID.  Be sure to read this before any of the others.  Assumed reading for anyone who is involved in the RRG.

draft-lear-lisp-nerd * (2007-05-11)

Eliot Lear's proposal for a full-push mapping system distribution for LISP.  All ITRs get (or rather retrieve for themselves) the full mapping database.  This is likely to be pretty slow (my guess is latencies such as 30 minutes or more).  Please see my analysis of mapping approaches for a quick summary and list of benefits and critiques of NERD, and of other approaches: psg.com/lists/rrg/2008/msg00707.html (2008-03-11). The good thing is all ITRs can forward packets without delay.  The bad news is that it is probably overkill and prohibitively expensive to push the full mapping database to every ITR on the planet. While this ID is not in the list of other LISP IDs in the above-mentioned BOF proposal, it remains an important ID, since it is the only one of the map-encap proposals which involves "full push" of the whole mapping database to every ITR.

draft-meyer-lisp-cons * (2007-07-03)

A fancy full-pull mapping distribution system involving a novel global query server system.  Superseded by ALT around late November 2007.

draft-curran-lisp-emacs * (2007-11-09)

Tentative approach to dealing with the problem of the delay of initial packet(s) in a new communication session while the ITR waits for its mapping request to be replied to.  This is a problem with LISP-CONS, LISP-ALT and any other pure pull system, such as TRRP - but TRRP has "Waypoint Routers" as a potential solution.  There is a multicast arrangement over the ALT network for sending the traffic packets out from the ITR, so they arrive by some means at the correct ETR.  I critiqued this (to do: link to the RRG message) and the proposal hasn't been mentioned much since.

draft-fuller-lisp-alt (2007-11-11)

An alternative network is created both for sending mapping queries from ITRs to the authoritative query servers (typically ETRs) and for transporting packets from the ITRs to those ETRs before the ITR has the mapping information.  In practice, the two tasks are achieved at once - the traffic packet is the request.  The mapping reply could come back via the ALT network, but it is faster to send it back via the ordinary Internet. The IPv4 ALT network is comprised of router functions (typically implemented in actual routers) operating with the IPv4 address space, but completely separately from the IPv4 Internet.  The ALT routers are linked by tunnels, forming a global virtual network, whose structure is determined by strong address aggregation, rather than geographic proximity.  ALT is a pure pull system - a global query server system, which also delivers packets to ETRs before the ITR has the mapping information for that packet's EID prefix.

Please see the diagram above regarding LISP+ALT and the explanation of it at: psg.com/lists/rrg/2008/msg01667.html

draft-lewis-lisp-interworking (2007-12-05)

How to make LISP incrementally deployable by supporting packets sent from hosts in networks which do not have ITRs.  There are two approaches - LISP-NAT and Proxy Tunnel Routers (PTRs).  PTRs are the same mechanism, purpose and results as Ivip's OITRDs (Open ITRs in the DFZ, previously known as "anycast ITRs in the core".   For comparison, see the Ivip material in the parent directory, based on the idea first publicly documented in the RAM list on 2007-06-15 www.ietf.org/mail-archive/web/ram/current/msg01518.html and APT's approach to the same problem: www.ops.ietf.org/lists/rrg/2008/msg00468.html (2008-02-21) and more fully: www.cs.ucla.edu/~meisel/draft-apt-incremental-00.txt (2008-03-06).  I think PTRs are essential to LISP's ability to be incrementally deployed, and that LISP-NAT has to many problems and limitations to be used.  See my critique below.

draft-iannone-openlisp-implementation (2008-02-18)

Description of an implementation of LISP on FreeBSD, separate from the one being developed by Dino and the other LISP people at Cisco Systems.

draft-mathy-lisp-dht (2008-02-25, but not yet in the IETF system - still not there in July 2008)

This can be found at: inl.info.ucl.ac.be/publications/lisp-dht-towards-dht-map-identifiers-locators which points to: inl.info.ucl.ac.be/system/files/draft-mathy-lisp-dht-00.txt .  I wrote to the RRG list requesting further information, including examples, exactly how a mapping request and response would be handled etc.  In an off-list reply, I was told the authors were working on an updated version which would answer these questions.  

Distributed Hash Tables are a way of building a distributed system of servers to store information and to respond to queries about this information.  This proposal is an alternative to NERD and ALT (and before that to CONS) - a full pull mapping distribution system for LISP (global query server system), based on some modifications of the traditional DHT.


draft-meyer-lisp-eid-block

Proposal for a  /16 of IPv6 space to be reserved for LISP-ALT.

draft-farinacci-lisp-multicast


Abstract: "This draft describes how inter-domain multicast routing will function in an environment where Locator/ID Separation is deployed using the LISP architecture."


Significant RRG Messages

To do.


Some critiques of LISP

There are many critiques of LISP, by me and other folks.  Here is list of my main critiques since November 2007 - and one from Christian Vogt.  These URLs are for the RRG list.  They do not list all the discussions, but some of them are for responses from the LISP team.  Please read the full discussion to get a better picture of the debate than you will get just from these linked-to messages.

There are far more critiques of LISP than of other proposals (APT, Ivip and TRRP).  This is probably largely attributable to LISP being the first such map-encap proposal, to so many people writing IDs for it and to the fact that LISP's major developers work for the world's biggest router company.

The fact that there has been essentially no detailed critique of Ivip does not necessarily mean that Ivip has less weaknesses (though I think it has far fewer problems than LISP).  I think that the absence of such critical attention for APT, Ivip and TRRP is largely to do with people not reading up on these proposals as much as they have the LISP IDs.  Mailing list discussions tend to thrive on negative sentiment, so if you have something positive to say about any of these proposals, it would be good to write to the list about it.  The absence of such messages could give the developers the impression that no-one is reading their proposals.

LISP-ALT & NERD inefficient - and some suggested improvements

A sprawling discussion starting on 2008-01-22: 2008/msg00176.html  I write that ALT and NERD wouldn't be deployed together, prompted by Dino Farinacci's suggestion that two approaches could be blended 2008/msg00176.html .  I then take a stock standard NERD deployment and soup it up with query servers, caching ITRs etc.  The result starts to resemble Ivip.


draft-fuller-lisp-alt

The structure of the ALT network is highly aggregated, which precludes the structure of linkages and of which router aggregates which prefix being optimized according to geography.  Consequently, as a packet ascends the hierarchy of routers, until it gets to a level which covers its destination and then starts its descent towards that destination, it will be traveling over many links between these routers.  Since each router could be almost anywhere, it is reasonable to expect that the paths will tend to be very long.

Consequently, in many cases, packets traversing the ALT network will tend to take circuitous paths.  These are initial traffic packets which function as a map request and are sent by the ITR on the ALT network to get them to the right ETR ASAP, while the ITR awaits mapping information.  The response is best sent back directly over the Net from the authoritative ETR to the ITR.

The initial critique ALT's strong aggregation often leads to *very* long paths 2008/msg00229.html (2008-01-29). There were dozens of responses, generally not from the LISP team, many of whom were busy with a new product release at the time.  K. Sriram illustrated the problem with a diagram:  www.antd.nist.gov/~ksriram/strong_aggregation.png and discussed it in messages including: 2008/msg00235.html and 2008/msg00246.html .

A defense of this critique from Scott Brim appeared in the thread "Why delaying initial packets matters" (2008-03-04)  2008/msg00584.html .  (To do: response to this.)

Even if ALT was in some way optimised, with more meshiness to generally give shorter paths, I still think it is a bad idea.  I think any global query server system for mapping is a bad idea, due to inherent delays and chances of query and response packets being lost.  

An earlier critique of ALT and EMACS (multicasting initial traffic packets so they get to the ETR before the ITR has mapping) is this message 2007/msg00540.html (2007-11-16), which Scott Brim responded to in separate threads on ALT 2007/msg00545.html and EMACS 2007/msg00546.html.

The long path debate continued in June 2008:

psg.com/lists/rrg/2008/msg01675.html  DF
psg.com/lists/rrg/2008/msg01676.html  RW


Why delaying initial packets matters

A long discussion ensued from this (2008-02-08): 2008/msg00272.html .  (To do: add links to some defenses.)


LISP-ALT's Aggregation implies provider dependence

Christian Vogt raised this critique (2008-01-31) psg.com/lists/rrg/2008/msg00259.html
 

LISP gleaning looks insecure and therefore unusable

My critique 2008/msg00674.html (2008-03-08), Dino Farinacci's response 2008/msg00686.html and my reply: 2008/msg00695.html .


LISP PMTUD & fragmentation problems

My critique 2008/msg00678.html (2008-03-08), Dino Farinacci's response 2008/msg00687.html , my reply 2008/msg00693.html and Fred Templin's comments 2008/msg00692.html .   See also the discussion between Fred and Dino on the LISP-Interest list in July 2008, starting here: www.queuefull.net/lisp-interest/msg00031.html .


draft-lewis-lisp-interworking

I suggest that Proxy Tunnel Routers (PTRs) are both necessary and sufficient for supporting packets sent from networks without ITRs, and that LISP-NAT has too many limitations and problems to be used:  2007/msg00674.html2008/msg00737.html2008/msg00739.html and 2008/msg00740.html. There is a very simple explanation of LISP-NAT here: 2008/msg01005.html but it doesn't make any sense to me.

My  summary of the March 2008 debate about the aparrent lack of business incentive to deploy LISP PTRs is: psg.com/lists/rrg/2008/msg02021.html .

The business case for Ivip OITRDs (which do the same thing as LISP PTRs) is here: psg.com/lists/rrg/2008/msg01158.html .

Debate about whether LISP's RLOC and EID roles for addresses involve separate namespaces

Please see:  ../namespace .

Critique of Mobile LISP draft-meyer-lisp-mn-00 and a suggestion to use the TTR approach instead

Please see these and following messages on the LISP mailing list:   http://www.ietf.org/mail-archive/web/lisp/current/msg00749.html and msg00772.html .



































x