Subject: Re: [RAM] draft-lear-lisp-nerd-01

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 3 Jul 2007 13:57:39 +0200

On 13-jun-2007, at 16:27, Eliot Lear wrote:

> I've put together an internet draft that talks about a push-based  
> distribution method for LISP.  I call it NERD (Not-so-novel EID- 
> RLOC Database).

Hm, is it worth the effort to do push and:

    In order to specify a mapping it is important to understand how it
    will be used, and the nature of the data being mapped.  In the case
    of LISP, the following assumptions are pertinant:

    o  The data contained within the mapping changes only on  
provisioning
       or configuration operations, and is not intended to change when a
       link either fails or is restored.  Some other mechanism (via LISP
       or other) handles healing operations, particularly when a tail
       circuit within an service provider's aggregate goes down.

With this limitation, ALL encapsulation devices must somehow track  
the reachability status of locators. In my opinion, you're solving  
the easy problem here and leaving the hard one.

A better way to avoid solving the hard problem is to do pull and  
cache for some amount of time. That's probably not good enough for  
multihoming, but it is good enough for portable address space.

    This memo does not specify who the database authority is.  That is
    because there are several possible operational models.  In each case
    the number of database authorities is meant to be small so that ITRs
    need only keep a small list of authorities, similar to the way a  
name
    server might cache a list of root servers.

    o  A single database authority exists.
    o  Each region runs a database authority.
    o  Each country runs a database authority.

I REALLY don't like this. Whenever stuff comes together in a central  
place, that means the people that run that place are important, there  
need to be policies, arbitrary restrictions pop up etc etc.

The size figures don't seem to include data structure overhead.  
Depending on the allocation policies, these could be negligible or  
huge. I.e., a routing table for 2^32 /32s could be a 4 GB array, but  
a routing table for 200k prefixes of all possible sizes requires a  
good deal of overhead to accommodate varying prefix sizes and to  
compress unused holes in the address space.

    with 10% daily change spread over 24 hourly updates

This is a dangerous assumption if there are no mechanisms to enforce it.

Last but not least, doing the crypto for hundreds of megabytes worth  
of information that is signed could easily be a bottleneck.

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: Eliot Lear <[email-masked]>
Date: Tue, 03 Jul 2007 14:47:16 +0200

Iljitsch van Beijnum wrote:
> With this limitation, ALL encapsulation devices must somehow track the 
> reachability status of locators. In my opinion, you're solving the 
> easy problem here and leaving the hard one.

In part I'd have to say, "Guilty as charged", but I am thinking about 
the other problem.  We'll need some sort of feedback mechanism between 
ETR and ITR to indicate when an ETR is or is not available.  Dino has 
posited some form of ICMP unreachable message.  Some people don't like 
ICMP.  Another approach is simply a periodic acknowledgment of some form 
built into the tunneling mechanism, where one would expect an 
acknowledgment initially and then periodically.  But I heartily agree 
this area needs more work.

>
> A better way to avoid solving the hard problem is to do pull and cache 
> for some amount of time. That's probably not good enough for 
>    need only keep a small list of authorities, similar to the way a name

You live with these already from the context of the RIRs.  However, I 
think it would be quite possible for these things to not be regionally 
based at all, and so you could shop for an authority whose policies you 
trust and like.  I still maintain, however, that you want to keep the 
number relatively small or life gets ugly.

> The size figures don't seem to include data structure overhead. 

The only overhead not included is database header, which is insignificant.

> huge. I.e., a routing table for 2^32 /32s could be a 4 GB array, but a 
> routing table for 200k prefixes of all possible sizes requires a good 
> deal of overhead to accommodate varying prefix sizes and to compress 
> unused holes in the address space.

This seems overly complex.  We know how to store this stuff today.

> This is a dangerous assumption if there are no mechanisms to enforce it.

Remember: this is a provisioned database.  Show me a day in the last 
twenty years when the Internet's connectivity changed more than 1%.

> of information that is signed could easily be a bottleneck.
You're not doing it that often such that it would matter.  The only time 
you check the entire database is when you have none to start with.  
Otherwise you have an incremental update.  However, suppose you didn't 
want to check the entire database.  It would be possible to have 
signatures and versions of each EID entry.  That would involve a fair 
amount more storage overhead, of course, and one would have to wonder if 
it were worth it.

Eliot

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 3 Jul 2007 15:04:18 +0200

> In part I'd have to say, "Guilty as charged", but I am thinking  
> about the other problem.  We'll need some sort of feedback  
> mechanism between ETR and ITR to indicate when an ETR is or is not  
> available.  Dino has posited some form of ICMP unreachable  
> message.  Some people don't like ICMP.  Another approach is simply  
> a periodic acknowledgment of some form built into the tunneling  
> mechanism, where one would expect an acknowledgment initially and  
> then periodically.  But I heartily agree this area needs more work.

Actually not as much work as you may think:

http://www.ietf.org/internet-drafts/draft-ietf-shim6-failure- 
detection-08.txt

This does pretty much what's needed here. It would have to be adapted  
to run between middleboxes and to make sure that only active  
communication is monitored which means you don't detect a failure  
until you first try to communicate. But I guess that's a reasonable  
limitation.

>> I REALLY don't like this. Whenever stuff comes together in a  
>> central place, that means the people that run that place are  
>> important, there need to be policies, arbitrary restrictions pop  
>> up etc etc.

> You live with these already from the context of the RIRs.

Hence my reluctance...

> The only overhead not included is database header, which is  

In transit, but in the systems it must be easily searchable, which  
means there will be additional overhead.

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 3 Jul 2007 07:28:56 -0700

> then periodically.  But I heartily agree this area needs more work.

ICMP unreachable messages are not what the LISP-01 draft solely  
depends on for Locator reachability. We have put "Locator  
Reachability Bits" in the encapsulation header to piggyback Locator  
status for returning packets.

The LISP-01 draft should be in the ID directory today. If people  
can't wait, I can post it here.

Dino

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 4 Jul 2007 15:43:25 +0200

> available.

Hm, what if we create a rather static mapping database. Then, when an  
ITR sees traffic towards a given destination, it retrieves the latest  
ETR reachability info and expresses an interest in receiving updates  
when this reachability info changes. So we flood the static info and  
pull the reachability stuff.

If we engineer this right, this should be very fast but still much  
lighter than doing end-to-end reachability checks between the  
cartesian product of the sets of ITRs and ETRs with active  
communication between them.

I.e., if you want to subscribe to Google's reachability status, you'd  
just ask the next upstream mapping server. But if you want to know  
the reachability status of some obscure destination, you'll probably  
have to talk to a mapping server fairly close to that destination.  
Extra credit: DHT so any given mapping server only has to talk to a  
limited number of other mapping servers.

And/or deltas to reachability information can be highly compressed  
since the static mapping info is known.

---

From: Michael <[email-masked]>
Date: Thu, 05 Jul 2007 10:45:58 +0800

Hi, Eliot, Iljitsch,

Another approach is simply a periodic acknowledgment of some form 
> acknowledgment initially and then periodically. 

This would have some scalability issue, like RSVP soft state.

Michael

---

From: Robin Whittle <[email-masked]>
Date: Thu, 05 Jul 2007 14:40:35 +1000

Hi Dino,

You wrote:

> The LISP-01 draft should be in the ID directory today. If people can't
> wait, I can post it here.

Please post your new version to the RAM list soon - I am keen to
read it.

In my experience I-D's can take a day or two to appear on the IETF
site.

  http://tools.ietf.org/html/draft-farinacci-lisp

  - Robin

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 4 Jul 2007 22:11:09 -0700

> Please post your new version to the RAM list soon - I am keen to

Enclosed.

Dino

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 5 Jul 2007 19:53:20 +0200

Hi dino,

thanks for the draft
just took a quick read on this....

One comment:

As i understand it, the new version of LISP described in this 01  
version of the draft, no longer uses pure IP in IP tunneling, but  
adds a LISP header to the packets (which contains the nonce for  
security reasons) right?

In section 7, it is stated that:

7.  Router Performance Considerations

    LISP is designed to be very hardware-based forwarding friendly.  By
    doing tunnel header prepending [RFC1955] and stripping instead of  
re-
    writing addresses, existing hardware could support the forwarding
    model with little or no modification.

MB> in the new version, not only the IP header needs to be added but  
also the LISP header, so i guess this is not the only action that  
needs to be performed. Would this still be hardware friendly meaning  
that you could do little reprogramming of the software in the router  
to support that? I mean, this appending of the LISP header is  
supposed to be done for every data packet, right? In the previous  
version, when IP in IP tunneling was used, i guess the IP in IP  
encapsulation was already available in hardware, but i guess that the  
new LISP header will need to be added to the hardware?

    Where modifications are
    required, they should be limited to re-programming existing hardware
    rather than requiring expensive design changes to hard-coded
    algorithms in silicon.

    A few implementation techniques can be used to incrementally
    implement LISP:

    o  On an ITR, prepending a new IP header is as simple as adding more
       bytes to a MAC rewrite string and prepending the string as  
part of
       the outgoing encapsulation procedure.  Many routers that support
       GRE tunneling [RFC3056] or 6to4 tunneling [RFC2784] can already
       support this action.

MB> same applies here, not only adding the outer IP header is needed  
but also the new LISP header needs to be added

Regards, marcelo

  El 05/07/2007, a las 7:11, Dino Farinacci escribió:

> <draft-farinacci-lisp-01.txt>
>

---

From: Robin Whittle <[email-masked]>
Date: Fri, 06 Jul 2007 12:49:40 +1000

My understanding of LISP-01 is that LISP-00's IP-in-IP
encapsulation is not used at all, but that the original packet
becomes part of a new UDP packet.

The UDP packet's contents begin (page 12) with a "LISP header",
but this is not a header in the sense of an IP, TCP or UDP header.

UDP packets are also used for messages between ITRs and ETRs.
Similarly formatted messages are used with TCP, to the same port
number as the UDP messages, for the LISP-CONS system.

After reading LISP-01 I think that Ivip, as I am developing it,
has less and less in common with LISP-00.  Now that LISP-01 has
adopted UDP instead of IP-in-IP - and since I think IP-in-IP is
just fine for Ivip - there is even less in common.

What Ivip takes from LISP is some vital basic concepts:

  Using existing IP address space in two ways - some addresses
  as "Ivip-mapped addresses" ("EIDs" in LISP) where packets
  addressed to these are tunneled to some other IP address (an
  "RLOC" in LISP).

  A large number of ITRs to do the encapsulation.

  ETRs near wherever hosts with Ivip-mapped addresses are
  located.

  Some kind of push and/or pull global distributed database
  to control the operation of ITRs.

  The aims of providing portability of addresses, down to
  single IP address granularity (at least for IPv4) and
  multihoming.

A list of differences between LISP and Ivip would be much longer.

Probably in late August I will be able to create one or more Ivip
I-Ds with more fully-baked ideas - with a more cohesive
presentation.  I will continue to write up my ideas for this list
for those who are interested in reading fresh ideas.  This is
primarily to help people who are devising their own schemes and
want to copy or improve on my ideas - or to avoid them!  I see
this as the brainstorming phase, with this RAM list the place
where we throw ideas into the pot, combine them in different ways,
critique and improve upon them etc.

Some of what I write may be applicable to some LISP variants - but
I am concentrating on what I think are more expansive goals, with
a more incrementally deployable scheme, rather than trying to
contribute directly to LISP.

Hopefully writing these ideas up on this public web-archived
mailing list will mean anything which might have been patentable
will no longer be so.  If even one of my ideas winds up being part
of the final system, my efforts will have been worthwhile.

  - Robin     http://www.firstpr.com.au/ip/ivip/

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 5 Jul 2007 23:27:24 -0700

> adds a LISP header to the packets (which contains the nonce for  

That is correct. We are using UDP encapsulation with a LISP header  
for the following reasons:

o Get through firewalls
o ITR hashes on inner header to produce a source port LAG router can  
hash on
o Can carry nonce for ETR anti-spoofing
o Can carry Locator reachability bits

>    doing tunnel header prepending [RFC1955] and stripping instead  
> of re-
> MB> in the new version, not only the IP header needs to be added  
> but also the LISP header, so i guess this is not the only action  
> that needs to be performed. Would this still be hardware friendly  
> meaning that you could do little reprogramming of the software in  
> the router to support that? I mean, this appending of the LISP  
> header is supposed to be done for every data packet, right? In the  
> previous

On the ITR, yes if you can preload an encapsulation string that  
contains the outer IP header, the UDP header, and the LISP header.

There is a per-packet selection of the source-port but we felt it was  
important enough to make LAGs work well in the core (which use 5- 
tuple hashing to load-split
traffic over the members of the LAG).

The locator reachability bits and the nonce for a resolved EID entry  
can be preloaded in the encapsulation string.

> encapsulation was already available in hardware, but i guess that  
> the new LISP header will need to be added to the hardware?

Well what was proposed (IP protocol number 4) isn't in a lot of  
hardware. GRE and L2TP are the popular encapsulations.

>    rather than requiring expensive design changes to hard-coded

Right. But let's first solve the problems we need to solve. If ITRs  
and ETRs are placed at CE routers, the performance requirement isn't  
as strong as in other parts of the network (you would need around a 1  
Gig of forwarding performance which can be done in software these days).

> MB> same applies here, not only adding the outer IP header is  
> needed but also the new LISP header needs to be added

Right, like I said above, you just need to add more bytes.

The problem is on the ETR that has to parse the new format. Typically  
this is either done via:

o Hardwired silicon (in an ASIC).
o In software using general purpose processors.
o In microcode for line-rate performance.

In the later 2 cases, it is much easier to rev the product.

> Regards, marcelo

Thanks again for your comments,
Dino

---

From: Robin Whittle <[email-masked]>
Date: Fri, 06 Jul 2007 18:17:02 +1000

> need to be policies, arbitrary restrictions pop up etc etc.

In "4 User-interface and delegation tree for central database
(LISP/Ivip)" and "5 Database <--> ITR push, pull and notify" I
also depicted a central database.  I will post a reply to the
second message with a decentralised alternative.

 - Robin

---

From: Robin Whittle <[email-masked]>
Date: Fri, 06 Jul 2007 20:35:29 +1000

Dino wrote:

> That is correct. We are using UDP encapsulation with a LISP
> header for the following reasons:
>
>  o Get through firewalls
>  o ITR hashes on inner header to produce a source port LAG
>    router can hash on

With Ivip, there is no TE functionality in the ITR, no
reachability detection of the ETR and no signalling one way or the
other between ITR and ETR.  All that happens is the packet is
tunneled to an IP address which the end-user selects - presumably
the address of an ETR.  So Ivip doesn't need the last three things.

I don't know enough about firewalls in all the various situations
to know what problems IP-in-IP would suffer.

What sort of firewalls would an ETR be located behind?

If an edge network wanted to put an ETR behind a firewall, maybe
they should configure their firewall to handle a major
architectural aspect of getting packets to the ETR - the simplest
and most standardised of which is IP-in-IP, as far as I know.

I am not arguing against UDP encapsulation, except that it is
longer, since it requires a UDP header too.  Ivip could easily use
UDP instead of IP-in-IP.

By the way, links to the current LISP I-Ds are at:

  http://www.firstpr.com.au/ip/sram-ip-forwarding/#LISP

The RRG wiki:

  http://www3.tools.ietf.org/group/irtf/trac/wiki/RoutingResearchGroup

doesn't yet point to all three LISP I-Ds.

 - Robin

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 6 Jul 2007 17:59:06 +0200

Hi Dino,

i have a question about the new version of LISP i.e. draft-farinacci- 
lisp-0

How does an initiator node informs the receiver about its multiple  
RLOCs?

I mean, in the described packet flow sequence, the initiator sends a  
LISP data packet containing its EID and RLOC in the source address  
fields of the inner and outer header, and this is how the receiver  
ETR learns about the EID-to-RLOC mapping of the initiator. However,  
this only conveys a single RLOC, what happens if the initiator has  
multiple RLOCs (the most common in a multihomed site) and wants to  
inform the receiver ETR about them?

In the previous version of LISP, it was possible for the initiator to  
send an unsolicited Map-Reply message containing the whole RLOC set  
to the receiver. however, the current version includes the nonce, so  
Map-reply messages can only be sent as replies to data packets or map  
request messages. So, does this means that the initiator cannot  
inform spontaneously of its locator set and must wait for the  
receiver to ask for it? or there is a mean for the initiator to send  
the locator set to the receiver even if the receiver haven't asked  
for it?

Thanks, marcelo

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 6 Jul 2007 19:57:14 +0200

El 06/07/2007, a las 17:59, marcelo bagnulo braun escribió:

> Hi Dino,
>
> i have a question about the new version of LISP i.e. draft- 
> farinacci-lisp-0
>

i meant  draft-farinacci-lisp-01

> I mean, in the described packet flow sequence, the initiator sends  
> a LISP data packet containing its EID and RLOC in the source  
> address fields of the inner and outer header, and this is how the  
> receiver ETR learns about the EID-to-RLOC mapping of the initiator.  
> However, this only conveys a single RLOC, what happens if the  
> initiator has multiple RLOCs (the most common in a multihomed site)  
> and wants to inform the receiver ETR about them?
>
> In the previous version of LISP, it was possible for the initiator  
> to send an unsolicited Map-Reply message containing the whole RLOC  
> set to the receiver. however, the current version includes the  
> nonce, so Map-reply messages can only be sent as replies to data  
> packets or map request messages. So, does this means that the  
> initiator cannot inform spontaneously of its locator set and must  
> wait for the receiver to ask for it? or there is a mean for the  
> initiator to send the locator set to the receiver even if the  
> receiver haven't asked for it?
>
> Thanks, marcelo
>
>

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 6 Jul 2007 17:00:09 -0700

> How does an initiator node informs the receiver about its multiple  

This has not changed from the -00 draft. the receiver can glean *a*  
locator from the packet it is decaping (the ETR that is). If the ETR  
wants the complete set of locators with their associated priorities  
and weights, it must either 1) send a packet returning with the outer  
DA equal to the inner DA (I call this a data probe) or 2) if there is  
a mapping service in place, do a lookup to get the mapping.

For the later, if LISP-NERD is used, the lookup is local the the ITR  
since the mappings are pushed. If LISP-CONS is used, a Map-Request is  
sent by the ITR to it's configured CAR over a TCP connection.

> and wants to inform the receiver ETR about them?

Right, the ETR has some flexibility here. It can use the single  
locator to return packets while in parallel send a Map-Request to get  
the rest of them. When the ITR is sending packets this ETR, the  
Locoator Reachability bits are continually updated for each packet  
the ITR encaps to the ETR. So the ETR will know the reachability status.

There is a detail about which loc-reach-bit to associated with the  
outer SA but I can tell you about that offline.

> set to the receiver.

No, it was never unsolicited, because the sender of the Map-Reply  
would not know where to send it.

> however, the current version includes the nonce, so Map-reply  
> messages can only be sent as replies to data packets or map request  
> messages. So, does this means that

The -01 draft uses both the fact that the Nonce much match as well as  
the ITR keeping a local cached entry for the EID in a "incomplete"  
state. Similar to how some ARP implementations are coded.

> the initiator cannot inform spontaneously of its locator set and  
> must wait for the receiver to ask for it? or there is a mean for  
> the initiator to send the locator set to the receiver even if the  

The Map-Reply is never sent unsolicited.

Dino

---

From: "Ved Kafle" <[email-masked]>
Date: Thu, 12 Jul 2007 14:35:05 +0900

Hi Dino,

I have the following questions and comments on LISP v01.

Section 6.1.1

	What is a CAR? Its description is missing.
	ITR-AFI and CAR-AFI has the same description. How to distinguish
them?
	Why do you set Originating ITR RLOC Address to zero for
UDP-based messages? What are its other possible values?
	What is a Path Vector List? Its description is missing.
	You say LISP Nonce is 6 bytes long, in Map-Request Message
Format it's just 5 bytes. 
	(Why the LISP Nonce is 6 bytes long? Any reasons?)

Section 6.1.3
	How many Locs can be included in each Rec? How to know that
there are many Locs in each Rec? If there is only one Loc in each Rec,
then using Record count and Locator count fields is redundant. If many,
then the Locator count field should be inside Rec. In that case, the
total number of locators would be equal to the summation of number of
Recs multiplied by the number of Locs in each Rec.

Some typos:
----------------------
Section 4.1
(First line )  ... unicast unicast packet flow ... 
(Last para) ... section Section 6 ...
Section 6.1.1
Record count:  ... the a number of times .
Section 6.1.3
Record Count: The number of records in this request message => or reply
message?

Thank you.

Ved Kafle @NICT, Japan

> -----Original Message-----
> From: Dino Farinacci [mailto:[email-masked]] 
> Sent: Saturday, July 07, 2007 9:00 AM
> To: marcelo bagnulo braun
> Cc: [email-masked]
> Subject: [RAM] Re: question about LISP v1
> 
>

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 12 Jul 2007 01:04:58 -0700

> 	ITR-AFI and CAR-AFI has the same description. How to distinguish

CAR is defined in the CONS reference. Will fix the typo. Nice find.

> UDP-based messages? What are its other possible values?

Because in LISP 1.5 the Map-Request is being originated by the ITR  
itself. In CONS, the ITR sends the Map-Request over a TCP connection  
to the CAR and when the CAR receives the Map-Reply back it needs to  
route the Map-Reply to the originating ITR.

Hence we have to preserve the identity of the ITR.

> 	What is a Path Vector List? Its description is missing.

See the CONS reference. I will make sure I refer to it in this spec.

> Format it's just 5 bytes.

The description says it is 6 bytes even though it looks like it is  
drawn as 5 bytes. The intent is 6 bytes. I will fix the packet format  
illustration.

> 	(Why the LISP Nonce is 6 bytes long? Any reasons?)

Wanted it longer than 32-bits and didn't see a need for 64-bits.

> there are many Locs in each Rec? If there is only one Loc in each Rec,

The 'Locator Count' field 8 bits in width per EID-prefix record.

> then using Record count and Locator count fields is redundant. If  

Record count is there to allow you encode multiple mappings, each  
mapping has one EID-prefix associated with a locator-set. The number  
of locators in a locator-set is determined by the 'Locator Count' field.

> Recs multiplied by the number of Locs in each Rec.

No, not true.

> Some typos:

Thanks for the careful reading. I have fixed all of the above  
occurrences and will be reflected in the -02 update of the draft.

> Ved Kafle @NICT, Japan

Thank you,
Dino

---

From: "Templin, Fred L" <[email-masked]>
Date: Tue, 17 Jul 2007 07:51:40 -0700

One small point from several days back: 

> Sent: Thursday, July 05, 2007 11:27 PM
> Subject: Re: [RAM] Re: LISP-01 I-D
> 

I think the UDP encapsulation will also get through NATs,
as for other UDP encapsulation schemes like Teredo.

Fred
[email-masked]