Subject: [lisp] Comments to draft-cheng-lisp-shdht-03

From: Dino Farinacci <[email-masked]>
Date: Wed, 13 Mar 2013 15:22:51 -0700

See my comments inline.

> 1.  Introduction
> 
>    Locator/ID Separation Protocol (LISP) [RFC6830] specifies an
>    architecture and mechanism for replacing the address currently used
>    by IP with two separate name spaces: Endpoint IDs (EIDs), used within
>    LISP sites, and Routing Locators (RLOCs), used on transit networks
>    that make up the Internet infrastructure.  To achieve this
>    separation, LISP defines protocol mechanisms for mapping from EIDs to
>    RLOCs.  As a result, an efficient database is needed to store and
>    propagate those mappings globally.  Several such mapping databases
>    have been proposed, among them: LISP-NERD [I-D.lear-lisp-nerd], LISP-
>    ALT[RFC6836], LISP-DDT[I-ietf-lisp-ddt], and LISP-DHT [LISP-DHT].

Since you are supplying a comprehensive list, I would add draft-curran-lisp-emacs as well.

>    According to hybrid model databases such like LISP-ALT [RFC6836] and
>    LISP-DDT [I-ietf-lisp-ddt], architectures of these mapping databases

What do you mean by hybrid? And why isn't LISP-NERD or LISP-DHT hybrid?

>    are based on announcement/delegation of hierarchically-delegated
>    segments of EID namespace (i.e., prefixes).  Therefore, based on
>    these architectures, when a roaming event occurs and a LISP site or a
>    LISP MN receives new RLOCs, the site or MN has to anchor pre-
>    configured map-server to register its new mapping information no
>    matter where the site or MN currently locates, just in order to
>    protect EID prefixes announced aggregately in the database
>    [I-D.meyer-lisp-mn].

Yes, this is a huge scaling feature. A static address allocation should not be affected by movement or change of location.

I am not sure if you are stating a disadvantage that LISP-SHDHT will fix? Can you clarify please?

>    1.  Each SHDHT Node maintains routing information for all other SHDHT
>        Nodes.  Thus, messages interaction between SHDHT Nodes in the
>        same SHDHT overlay just need one or two hops.

So you are making a state/lookup-latency tradeoff favoring lookup-latency.

>    This draft specifies the outline of SHDHT and the basic application
>    of LISP SHDHT.  In actual deployment of LISP SHDHT, mapping database
>    could be maintained by multiple mapping service providers and could
>    be deployed as collaborative combination of multiple Domain LISP
>    SHDHTs.  Details about Domain LISP SHDHT Deployment are introduced in
>    Section 5.  Security strategies on/between Domain LISP SHDHTs is for
>    future study.

Are you saying you can connect multiple SHDHTs together when each are managed by separate entities?

> 3.  SHDHT Overview
> 
> 3.1.  Node ID and Partition ID
> 
>    Most of existing DHTs use node IDs for both maintenance and hash
>    space arrangement.  For example, in LISP-DHT[LISP-DHT], each chord
>    node of the DHT ring has a unique k-bits identifier (ChordID).  Nodes
>    perform operations such like put/get/remove based on ChordIDs.
>    Furthermore, ChordIDs are also used to associate nodes with hash
>    space segments that the nodes responsible for.
> 
>    In SHDHT, two roles of maintenance and hash space arrangement are
>    separated and a new kind identifier called Partition ID is adopted.
>    Each SHDHT node has a unique Node ID which identifies the physical
>    node and multiple Partition IDs which represent hash space segments.
>    All Partition IDs in the overlay are also unique.  Node IDs and

I have noticed you are using the term "overlay" a lot. That could get confused with the encapsulation overlay that is employed at the LISP sites. Do you really just mean "mapping database system", or simply the DHT ring? Or are you suggesting that SHDHT is more than a ring topology since it has some shorter paths to get control messages from one node to another?

>    Partition IDs are mapped into two ring-shaped spaces respectively.
>    The ring containing Node IDs indicates the overlay's topology.  The
>    ring containing Partition IDs determines how the hash space is
>    partitioned into segments and how these segments are assigned to
>    nodes.  It is noteworthy that SHDHT Nodes could determine number of

So all nodes in a segment will hold the data values for all keys in that partition?

>    Partition IDs on them separately and could generate Partition IDs
>    randomly just need to make sure that the generated Partition IDs will
>    not conflict with existing Partition IDs on the SHDHT plane.
> 
>   +--------------------+                          +--------------------+
>   |Node ID:      0x0123|                          |Node ID:      0x4444|
>   |Partition ID: 0x1234| +-----+          +-----+ |Partition ID: 0x9000|
>   |              0x7000| |Node1+----------+Node2| |              0x3234|
>   +--------------------+ +--+--+          +--+--+ +--------------------+
>                             |                |
>                             |                |
>                             |                |
>                             |                |
>   +--------------------+ +--+--+          +--+--+ +--------------------+
>   |Node ID:      0xe000| |Node3+----------+Node4| |Node ID:      0xc000|
>   |Partition ID: 0x5000| +-----+          +-----+ |Partition ID: 0xaaaa|
>   |              0xeeee|                          |              0xcccc|
>   +--------------------+                          +--------------------+

Are the partition IDs a range of key values? Can they overlap? Meaning can Node 0x0123 and 0x4444 have the same partition-ID range?

Or, in the above diagram, is the partition-ID a single key value, like 0x1234 and then another partition-ID 0x7000?

>    For example, for a data object whose Resource ID is 0x8213, the
>    Resource ID locates between Partition ID 0x7000 and Partition ID
>    0x9000.  As Partition ID 0x9000 is closer to Resource ID 0x8213, the
>    data object will be stored and maintained on Node2 who is assigned
>    with the hash space segment indexed by Partition ID 0x9000.

This is implying each node does not have ranges, but a lower and upper range value much be search for, or a delta from the resource-ID from any partition-ID from any node.

>    Replications of data objects in a particular node are always stored
>    in the preceding node or successor node of the root node.  The backup
>    preceding node or successor node will automatically become the new
>    closest node if the root node leaves the overlay.

So does this mean if a Map-Server gets a registration for a /32 mobile-node, it will have to find the SHDHT nodes that will store it?

And shouldn't the partition-IDs for the Map-Server be the ones that map to EIDs that are going to be registered for?

The Map-Resolver equivalent I believe is simpler but the Map-Server side needs a bit more text. Let's see if you explain this later in the draft.

>    In SHDHT, the whole hash space is partitioned into segments based on
>    partition IDs.  The root node of a data object is the node, which has
>    the closest partition ID to the data object's Resource ID.  In SHDHT,
>    each node can maintain multiple hash space segments with respective

I think you should give an example, how node-IDs are used, what a partition-ID looks like for say a registered 10.1.0.0/16 EID and what is the resource-ID for this EID registration.

> 3.3.  Node Routing Table
> 
>    In SHDHT, each node maintains a Node Routing Table containing routing
>    information of all other SHDHT Nodes locate in the same SHDHT
>    overlay.  Table I shows the Node Routing Table on SHDHT Nodes of
>    Fig.1.  A Node Routing Table contains all Partition IDs and their
>    associated Node IDs and node addresses.  For simplification, Node IDs
>    and Partition IDs shown in the draft are only 16-bit numbers.

Can you say in the above paragraph how each node builds this routing table? Is it statically configured or is there a message exchange routing protocol of sorts that builds the table.

>    When SHDHT Node receives a message points to a particular Resource

I think you mean a lookup request? If not, please make it more clear.

>    ID, it could look up Node Routing Table and find out the Partition ID
>    which is closest to the Resource ID.  Furthermore, message could be
>    transferred to the corresponding SHDHT Node.
> 
>                 +--------------+---------+---------------+
>                 | Partition ID | Node ID | Address       |
>                 +--------------+---------+---------------+
>                 | 0x1234       | 0x0123  | 10.0.0.2:2000 |

Shouldn't the node ID just be the locator of the SHDHT node that is routable in the underlying routing system so you can et messages from you to other SHDHT nodes? Otherwise, you will have to maintain yet another mapping.

>                 | 0x3234       | 0x4444  | 10.0.0.3:2000 |

And what is 10.0.0.3:2000? Is 10.0.0.3 the IP address of a SHDHT node. Is 2000 a UDP port number of something else? Providing a simple clear example would really be helpful.

>                 | 0x5000       | 0xe000  | 10.0.0.4:2000 |
>                 | 0x7000       | 0x0123  | 10.0.0.2:2000 |
>                 | 0x9000       | 0x4444  | 10.0.0.3:2000 |
>                 | 0xaaaa       | 0xc000  | 10.0.0.5:2000 |
>                 | 0xcccc       | 0xc000  | 10.0.0.5:2000 |
>                 | 0xeeee       | 0xe000  | 10.0.0.4:2000 |
>                 +--------------+---------+---------------+
> 
>                      TABLE I SHDHT Node Routing Table
> 
>    For example, if Node 1 (ID: 0x1234) in Fig.1 needs to implement put/
>    get/remove operations for a data object with Resource ID 0x8213.
>    Node 1 first looks up its Node Routing Table and finds out that the
>    closest Partition ID corresponding to this Resource ID is 0x9000.
>    Then Node 1 will send put/get/remove request to the node owns the
>    Partition ID, in Fig.1 is Node2, whose Node ID is 0x4444 and address
>    is 10.0.0.3:2000.

Shouldn't the closeness function be a comparison of EID with a partition-ID that looks like a power-of-2 address of some sort?

> 
> 4.  LISP SHDHT
> 
>    LISP SHDHT is proposed to provide "EID-to-RLOC(s)" mapping
>    information lookup service for sites running the Locator/ID
>    Separation Protocol (LISP).
> 
>    In LISP SHDHT, mapping overlay consists of SHDHT Nodes which play
>    roles of SHDHT Map Server and/or SHDHT Map Resolver.  In this draft

Or neither, right? Can't there be a SHDHT node that is neither a map-resolver or map-server?

>    SHDHT-MS and SHDHT-MR just represent function entities, and these
>    entities could be collocated on the same SHDHT Node.

I think true for a map-resolver, but not clear for a map-server. Say an EID-prefix is closer to a SHDHT node than a SHDHT-MS node?

>    All EID-to-RLOC mapping entries are stored in SHDHT Nodes as data
>    objects.  Each SHDHT Node has a RLOC address.  EIDs in mapping
>    entries can be hashed as Resource IDs of data objects.  All SHDHT
>    Nodes in the same SHDHT overly perform hash operation based on the
>    same hash algorithm.

You really don't want to do this. Let me explain with an example:

(1) I register to a map-server provided by ARIN. The exact map-server is selected by ARIN since it is based on the value of my EID-prefix.
(2) I am sitting in San Jose so I provide the locator that equals my home DSL router.
(3) I register to 2 map-servers at ARIN and the EIDs I am talking to, I SMR to tell them to do lookups to get my locator.
(4) I know get off a plane in Orlando. My locator now is my AT&T cell phone provider. 
(5) All I have to do is update the map-servers that I have already been talking to.

With SHDHT, not only does the above have to happen, but the ARIN map-servers will need to find all SHDHT nodes that are in the "closest" partition to update the data objects (the data objects are the locators for my EID-prefix).

The fact that the data object must be replicated, will cause scale and out of sync problems.

I would suggest you change the model where the partition-IDs for a given "registered EID-prefix" is the map-server so any SHDHT node sends Map-Requests directly to the ARIN map-server(s).

You will also need to consider that if I register my cell-phone with a /32 EID, say 10.1.1.1, and there are parts of the DHT ring that are willing to support requests fro 10.1.0.0/16, how the partition-IDs work. Otherwise, you are going to a flat key space which can't possibly scale when replicated in all nodes (even if the partition is small).

> 
>    Data objects stored in LISP SHDHT Nodes may be in the following
>    format:
> 
>           Object (lisp) = [EID prefix, (RLOC1, priority, weight),
>                         ...,RLOCn, priority, weight), TTL ]
> 
> 4.1.  ITR Operation
> 
>    According to LISP-MS [RFC6833], LISP ITRs use Map Resolvers as proxy
>    to send control messages, such like encapsulated Map-Requests and
>    Map-Replies.
> 
>    In Scenario of LISP SHDHT, an ITR send Map-Requests directly to the
>    SHDHT Node which is selected to play roles of SHDHT Map Resolver for
>    the ITR.

Yes, just like a map-resolver can be connected to an ALT or a DDT. This part is good and obvious.

> 4.2.  ETR Operation
> 
>    According to LISP-MS [RFC6833], LISP ETRs register mapping
>    information onto the Map Server by sending Map-Register messages.
> 
>    In scenario of LISP SHDHT, ETR could send Map-Register messages
>    directly to the SHDHT Node which is selected to play roles of SHDHT
>    Map Server for the registered EIDs.
> 
>    Alternatively, ETRs could send Map-Register messages to a nearest
>    SHDHT Node who will hash registered mapping entries to be Resource

If you do this, a cell-phone that is doing ETR functions will have to do SHDHT. Architecturally, we should have an opt-in to do this but it definitely should not be required. If it is required, the solution will be a non-starter IMO.

>    IDs.  Then, the SHDHT Node forwards Map-Register messages to the
>    corresponding SHDHT Map Servers based on Resource IDs.  This
>    alternative strategy will be more efficient for roaming scenario.

No, it won't. Now the message has to take 2 hops. Rather than being routed on the shortest path from the ETR to the MS. And not only 2-hops but there will be queuing and processing delay on the first node.

>    Furthermore, ETRs are no longer anchoring to fixed SHDHT Map Server

If you wanted no anchors, use an anycast map-server address. That can be done with any of the mapping systems now.

> 
> 4.3.  SHDHT Map Resolver Operation
> 
>    In LISP SHDHT, when a SHDHT Map Resolver receives a Map-Request
>    message from an ITR, it will perform the following operations,
> 
>    1.  SHDHT Map Resolver extracts destination EID address from the Map-
>        Request message.
> 
>    2.  SHDHT Map Resolver hashes the EID address to be Resource ID based
>        on the shared hash algorithm.
> 
>    3.  SHDHT Map Resolver looks up Node Routing Table and finds out the
>        Partition ID which matches the Resource ID.

The description looks all good up to here.

So illustrate here what happens if it is a map-server (the easy case) versus an intermediate SHDHT node.

>    4.  SHDHT Map Resolver forwards Map-Request message to the
>        corresponding SHDHT Node.  This SHDHT Node maintains the hash
>        space labeled by matched Partition ID and plays the role of SHDHT
>        Map Server for the requested mapping entry.
> 
>    In LISP SHDHT, when a SHDHT Map Resolver receives a Map-Register

You mean the Map Server, I think a typo.

>    message from an ETR, it will perform the following operations,
> 
>    1.  SHDHT Map Resolver extracts registered EID information of the
>        Map-Register message.
> 
>    2.  SHDHT Map Resolver hashes the registered EID address to be
>        Resource ID based on shared hash algorithm.
> 
>    3.  SHDHT Map Resolver looks up Node Routing Table and finds out the
>        Partition ID which matches the Resource ID.
> 
>    4.  SHDHT Map Resolver forwards Map-Register message to the
>        corresponding SHDHT Map Server.

Change all occurrences of "Map Resolvers" to "Map Servers". But I would eliminate this section all together since it completely overlaps with the next section 4.4.

> 
> 4.4.  SHDHT Map Server Operation
> 
>    In LISP SHDHT, when a SHDHT Map Server receives a Map-Request
>    message, it will perform the following operations,
> 
>    1.  SHDHT Map Server first check if it is responsible for the
>        requested mapping entry, i.e. if it has a hash space whose
>        Partition ID matches Resource ID of the requested EID.
> 
>    2.  SHDHT Map Server then looks for data objects in its hash space
>        according to the matched Partition ID.
> 
>    3.  If there's no data object corresponds to the requested EID, SHDHT
>        Map Server responses a negative Map-Reply message.
> 
>    4.  If there's a data object corresponds to the requested EID, SHDHT
>        Map Server will forward the Map-Request to registered ETR or
>        return Map-Reply message if it offers proxy Map-Reply service.

When a Map-Server receives a Map-Request, it should either proxy reply or forward the Map-Request to one of the registered ETRs.

>    In LISP SHDHT, when a SHDHT Map Server receives a Map-Register
>    message, it will perform the following operations,
> 
>    1.  SHDHT Map Server first checks if it is responsible for the
>        registered mapping entry, i.e. if it has a hash space whose
>        Partition ID matches Resource ID of the requested EID.
> 
>    2.  SHDHT Map Server then stores and maintains the registered mapping
>        information in its hash space according to the matched Partition
>        ID.

If a SHDHT is a Map-Server but also acting as a SHDHT node, and gets a Map-Request that is not for one of its registered EID-prefixes, it should act as a SHDHT and forward to the correct Map-Server. One would have to ask why did this map-server get this Map-Request, unless it was a Map-Resolver and the Map-Request was received from an ITR. But it should not get it from a SHDHT node. Would you agree?

> Cheng & Sun              Expires August 25, 2013               [Page 12]
> Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013
> 
> 
>         0                   1                   2                   3
>         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      / |                       IPv4 or IPv6 Header                     |
>    OH  |                      (uses RLOC addresses)                    |
>      \ |                                                               |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      / |       Source Port = xxxx      |       Dest Port = 4342        |
>    UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      \ |           UDP Length          |        UDP Checksum           |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    LH  |Type=8 |S|                  Reserved                           |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      / |                       IPv4 or IPv6 Header                     |
>    IH  |                  (uses RLOC or EID addresses)                 |
>      \ |                                                               |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      / |       Source Port = xxxx      |       Dest Port = yyyy        |
>    UDP +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>      \ |           UDP Length          |        UDP Checksum           |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    LCM |                      LISP Control Message                     |
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> 
>                  Fig.2 Encapsulated Control Message Format

You don't need a new message type. Use the same one DDT uses, it is just an ECM as defined in RFC6830.

> 
> 4.5.1.  Encapsulated Map Request
> 
>    Suppose that the selected SHDHT Node of an ITR is Node1.
> 
>    When the ITR sends Encapsulated Map-Requests to Node1, source address
>    and destination address in message OH (Outside Header) should be RLOC
>    addresses of ITR and Node1 respectively.
> 
>    In the IH (Inside Header), source address is still RLOC address of
>    Node1, while destination address is the inquired EID address.
> 
>    Consider Node1 is a configured Map Resolver, and then the
>    configuration of Encapsulated Map-Request message has not been
>    changed.

You do not need to spec this. This procedure is the same for any Map-Resolver that is implemented on an ITR that interfaces to ANY mapping system.

>    Each Domain SHDHT Overlay has one or more Border Nodes which are not
>    only to store EID-to-RLOC mapping just like normal SHDHT Nodes, but
>    also be used to flood cross domain routing and forward the cross
>    domain packets.
> 
>    Each SHDHT Border Node maintains an Inter-Domain Routing Table, which
>    contains information of all other domain overlays, such like EID
> 
> 
> 
> Cheng & Sun              Expires August 25, 2013               [Page 14]
> Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013
> 
> 
>    prefixes other domain overlays maintain, IP addresses and ports
>    information of other overlays' Border Nodes.

So does a Border Node, that learns about EIDs from other Border Nodes, tell the rest of the SHDHT nodes in its domain? Or do they kind of route to a default edge?

>    At the beginning, Inter-Domain Routing Table could be configured on
>    SHDHT Border Nodes.  Then, a SHDHT Border Node will flood cross
>    domain routing periodically to trigger other Border Nodes update
>    their Inter-Domain Routing Tables.

Do you believe coarse EID-prefix aggregation will happen across these Border Node boundaries? That is not at all clear to me.

And did you just implement a BGP like function and each domain is doing an IGP like function? 

If this is the case (maybe not), BGP could be used to distribute this data. But that is so close to the ALT I am not sure where the benefits lie by having a DHT.

> 5.2.  Mapping Register
> 
> 5.2.1.  Intra Domain Mapping Register
> 
>    All SHDHT Nodes of a Domain SHDHT Overlay must be noticed the EID
>    prefixes that local domain overlay responsible for.  When a SHDHT
>    Node of a domain overlay receives a Map-Register message, it checks
>    if the registered EIDs are covered by local domain overlay's EID
>    prefixes.  If local domain overlay is responsible for registered
>    EIDs, SHDHT Node who receives Map-Register message will process the
>    message as procedures listed in Section 4.3.

Again, we should not forward Map-Register messages. There is no benefit and it creates a synchronization requirement that will slow down roaming handoffs.

> 5.3.1.  Intra Domain Mapping Request
> 
>    When SHDHT Node of a Domain SHDHT Overlay receives a Map-Request
>    message, it checks if the requested EID is covered by local domain
>    overlay's EID prefixes, i.e. if the requested mapping entry is stored
>    on local domain overlay.  If local domain overlay is responsible for

By examining the node's own routing table, right?

>    Suppose in Fig.3, ITR1 send a Map-Request message to Node1 of Domain
>    1 to get mapping information of EID 12.2.0.1.
> 
>    1.  Node1 extract requested EID from the Map-Request message.
> 
>    2.  Node1 determines that EID 12.2.0.1 is covered by Domain 1's EID
>        prefix 12.0.0.0/8.  The mapping entry is now stored on a SHDHT
>        Node of Domain 1.
> 
>    3.  Node1 hashes requested EID 12.0.0.1 to be Resource ID.
> 
>    4.  Node1 forwards Map-Register message to the Node whose Partition
>        ID matches the Resource ID.

This should be explaining the case of Inter-Domain. You already explained the intra-domain case. Why did you repeat it here?

> Cheng & Sun              Expires August 25, 2013               [Page 16]
> Internet-Draft     LISP Single-Hop DHT Mapping Overlay     February 2013
> 
> 
> 5.3.2.  Inter Domain Mapping Request
> 
>    When SHDHT Node of a Domain SHDHT Overlay receives a Map-Request
>    message, it checks if the requested EID is covered by local domain
>    overlay's EID prefixes.  If the requested EID entry is not stored on
>    local domain overlay, SHDHT Node directly forwards the Map-Request to
>    Border Nodes.  Border Nodes of local domain overlay then forwards it
>    to corresponding domain overlay based on Inter-Domain Routing Table.

Which border node? All of them?

>    Suppose in Fig.3, ITR2 send a Map-Request message to Node 5 of Domain
>    2 to get mapping information of EID 12.0.0.1.
> 
>    1.  Node5 extracts requested EID from the Map-Request message.
> 
>    2.  Node5 determines that EID 12.0.0.1 is not covered by Domain 2's
>        prefix 16.0.0.0/8.
> 
>    3.  Node5 forwards the Map-Request message to BN2.
> 
>    4.  BN2 extracts requested EID and looks for Inter-Domain Routing
>        Table to find corresponding domain overlay of EID 12.0.0.1.
> 
>    5.  BN2 finds out Domain 1 is responsible for EID 12.0.0.1.  BN2
>        forwards Map-Request message to Domain 1's Border Node ( BN1).

Why BN2? What if there were multiple paths to Domain 1 via BN2 and BN3?

> 6.  Mobility Considerations
> 
>    As specified in section 4.2 and 4.3, ITR/ETR could choose a nearest
>    LISP SHDHT Node as proxy to send control messages.
> 
>    Based on LISP SHDHT, when roaming events occurs, the roamed LISP
>    sites or LISP MNs are no longer need to anchor pre-configured map-
>    servers.

The need to anchor is not a disadvantage. Mobile-phone providers will want to provision, just like DNS, so having a statically configured one or a well-known map-server address sent in a DHCP will allow existing provisioning systems to be used.

The cost of the non-anchoring comes at synchronization multiple places for a mobility event. This will cause more dropped and mis-routed packets.

Thanks,
Dino

---

From: [email-masked]
Date: Fri, 15 Mar 2013 02:10:49 +0800

Hi Dino,

Thank you very much for your comments. Please see my responses inline.

> curran-lisp-emacs as well.

Ok, I will add the [LISP-EMACS].

> What do you mean by hybrid? And why isn't LISP-NERD or LISP-DHT hybrid?

This is my mistake. LISP-DHT is also a hybrid model database, and I should 
not 
classify them by this. In my opinion, LISP-NERD is a push model database, 
isn't 
it?

> Yes, this is a huge scaling feature. A static address allocation 
> should not be affected by movement or change of location.
> 

In LISP-SHDHT, LISP sites especially LISP-MNs need not anchor a configured 

map-server. Let take a LISP-MN for example. A LISP-MN could send the 
register 
message to any SHDHT Node which will forward the message to the SHDHT Node 
who 
plays roles of Map-Server for this LISP-MN. Of course, there is a 
Map-Server 
for a particular LISP-MN. The difference with other mapping database is 
that, 
LISP-MN does not need to maintain connection with the Map-Server. Its 
register 
message will be forward to the Map-Server.

> So you are making a state/lookup-latency tradeoff favoring 
lookup-latency.

Yes.

> are managed by separate entities?

Yes.

> I have noticed you are using the term "overlay" a lot. That could 
> get confused with the encapsulation overlay that is employed at the 
> LISP sites. Do you really just mean "mapping database system", or 
> simply the DHT ring? Or are you suggesting that SHDHT is more than a
> ring topology since it has some shorter paths to get control 
> messages from one node to another?

Yes, the "overlay" means the mapping database system, i.e. the LISP-SHDHT. 

If it causes confusion, I will modify it.

> So all nodes in a segment will hold the data values for all keys in 

In our strategy, there are at most two nodes maintain the same segment. 
For 
example, Node 1 maintains a Hash segment, so it holds data values for all 
keys in this partition. Node 2 is the preceding node of Node1, and is 
configured to be the backup node for Node 1. So Node 2 also maintains all 
data values on Node 1. Node 1 sends update message to Node 2 periodically.

> Are the partition IDs a range of key values? Can they overlap? 
> Meaning can Node 0x0123 and 0x4444 have the same partition-ID range?
> 
> Or, in the above diagram, is the partition-ID a single key value, 
> like 0x1234 and then another partition-ID 0x7000?

Partition IDs are identifiers of hash space segment. They do not overlap. 
A 
SHDHT node maintains multiple Partition IDs means all key values fall in 
these 
hash space segments should be stored on this SHDHT node.

If Node 0x0123 is backup node for Node 0x4444, it stores all data values 
of Node 
0x4444. But Node 0x123 is not the responsible node for these partition-IDs 

ranges, unless there's something wrong with Node 0x4444.

> This is implying each node does not have ranges, but a lower and 
> upper range value much be search for, or a delta from the resource-
> ID from any partition-ID from any node.

Yes.

> So does this mean if a Map-Server gets a registration for a /32 
> mobile-node, it will have to find the SHDHT nodes that will store it?

Yes.

> 
> And shouldn't the partition-IDs for the Map-Server be the ones that 
> map to EIDs that are going to be registered for?
> 
> The Map-Resolver equivalent I believe is simpler but the Map-Server 
> side needs a bit more text. Let's see if you explain this later in the 
draft.

I answer this question behind the example you list for Section 4.

> I think you should give an example, how node-IDs are used, what a 
> partition-ID looks like for say a registered 10.1.0.0/16 EID and 
> what is the resource-ID for this EID registration.

Also please see answers behind the example.

> Can you say in the above paragraph how each node builds this routing
> table? Is it statically configured or is there a message exchange 
> routing protocol of sorts that builds the table.

A SHDHT node floods it routing information to other nodes belong to the 
same 
LISP-SHDHT.A SHDHT node floods it routing information to other nodes 
belong to 
the same LISP-SHDHT.

> I think you mean a lookup request? If not, please make it more clear.

Not just lookup requests, but also map-register messages. Map-Register 
messages 
could also be forwarded by a SHDHT Node.

> Shouldn't the node ID just be the locator of the SHDHT node that is 
> routable in the underlying routing system so you can et messages 
> from you to other SHDHT nodes? Otherwise, you will have to maintain 
> yet another mapping.

Node ID is just an identifier of a SHDHT node. The partition ID and Node 
ID both 
described in the routing table, and it does not need to maintain another 
mapping. 
Ok, I will also consider to take Node IDs as the nodes’ locators, it 
seems simpler.

> And what is 10.0.0.3:2000? Is 10.0.0.3 the IP address of a SHDHT 
> node. Is 2000 a UDP port number of something else? Providing a 
> simple clear example would really be helpful.

Sorry, my mistake. I should write the title as "Address: UDP Port".

> Shouldn't the closeness function be a comparison of EID with a 
> partition-ID that looks like a power-of-2 address of some sort?

There could be multiple methods to choose the corresponding partition ID. 
Based 
on the closeness function, it will help to balance load on SHDHT Nodes. 
Also, 
you could choose a simpler method.

> map-resolver or map-server?

No "neither". In our strategy, each SHDHT node could receive messages 
(Map-Request/Map-Register) from xTRs and could hold data value according 
to 
its hash segment. 

> I think true for a map-resolver, but not clear for a map-server. Say
> an EID-prefix is closer to a SHDHT node than a SHDHT-MS node?

Yes.

> (1) I register to a map-server provided by ARIN. The exact map-
> server is selected by ARIN since it is based on the value of my 
EID-prefix.
> (3) I register to 2 map-servers at ARIN and the EIDs I am talking 
> to, I SMR to tell them to do lookups to get my locator.
> With SHDHT, not only does the above have to happen, but the ARIN 
> map-servers will need to find all SHDHT nodes that are in the 
> "closest" partition to update the data objects (the data objects are
> the locators for my EID-prefix).
> 
> I would suggest you change the model where the partition-IDs for a 
> given "registered EID-prefix" is the map-server so any SHDHT node 
> sends Map-Requests directly to the ARIN map-server(s).
> 
> You will also need to consider that if I register my cell-phone with
> a /32 EID, say 10.1.1.1, and there are parts of the DHT ring that 
> are willing to support requests fro 10.1.0.0/16, how the partition-
> IDs work. Otherwise, you are going to a flat key space which can't 
> possibly scale when replicated in all nodes (even if the partition is 
small).

As I explained before, there are at most two nodes maintain the same data 
value. 
One single node play roles of Map-Server for the registered EID-prefix, 
and 
another backup node is updated by the "Map-Server Node". As a result, 
there is
no problem of "data object replication" and "out of sync".

I see what you mean. For Map-Register, it may register mapping information 
for 
such like 10.1.0.0/16 and 10.1.1.1/32. How to hash and store these 
map-registers, right?

Ok, I will take an example. Also answer questions posted earlier.

Suppose a Domain SHDHT is operated by a mapping service provider who is 
responsible to maintain all mapping information for 10.1/14. It assigns a 
"hash 
bits" for its domain SHDHT which is 16bits. All map-request/register will 
be 
hashed as a /16 EID-prefix. When a node receives a register message for 
10.1.0.0/16, it hash 10.1.0.0/16 to be the resource ID 0x8200 for example, 
and 
the mapping information of 10.1.0.0/16 is stored based on corresponding
 Partition ID(The node who receives register message looks up its routing 
table 
to determine which SHDHT node maintains the corresponding Partition ID, 
and 
forwards the Map-Register message to that node.). When the LISP-MN 
registers 
10.1.1.1, the node also hashes it as 10.1.0.0/16. As a result mapping 
information 
of 10.1.0.0/16 and 10.1.1.1/32 are hashed to be the same resource ID and 
are 
stored on the same node. 

I am sorry that I haven’t specified this problem clearly. I will add a 
section in 
our next version.

> If you do this, a cell-phone that is doing ETR functions will have 
> to do SHDHT. Architecturally, we should have an opt-in to do this 
> but it definitely should not be required. If it is required, the 
> solution will be a non-starter IMO.

ETR just chooses the nearest SHDHT Node and sent Map-Register message to 
it.

> No, it won't. Now the message has to take 2 hops. Rather than being 
> routed on the shortest path from the ETR to the MS. And not only 2-
> hops but there will be queuing and processing delay on the first node.

The efficiency is for roaming scenarios. LISP MNs do not need to maintain 
their connections with LISP-MS. 

For LISP-Sites which do not always move, normally their nearest SHDHT 
Nodes 
are their Map-Servers. The map-registers for these LISP-Sites also need 
just one-hop.

> If you wanted no anchors, use an anycast map-server address. That 
> can be done with any of the mapping systems now.

LISP MNs could also use anycast address to choose the nearest SHDHT node.

> You mean the Map Server, I think a typo.

A SHDHT node play roles of Map-Resolver could also forward Map-Register 
messages.

> Change all occurrences of "Map Resolvers" to "Map Servers". But I 
> would eliminate this section all together since it completely 
> overlaps with the next section 4.4.

See explanations above.

> When a Map-Server receives a Map-Request, it should either proxy 
> reply or forward the Map-Request to one of the registered ETRs.

Yes.

> If a SHDHT is a Map-Server but also acting as a SHDHT node, and gets
> a Map-Request that is not for one of its registered EID-prefixes, it
> should act as a SHDHT and forward to the correct Map-Server. One 
> would have to ask why did this map-server get this Map-Request, 
> unless it was a Map-Resolver and the Map-Request was received from 
> an ITR. But it should not get it from a SHDHT node. Would you agree?

In LISP SHDHT, a SHDHT node which play roles of Map-Server for an ETR may 
play 
roles of Map-Resolver for another ITR.

> >    UDP 
> >    UDP 
> just an ECM as defined in RFC6830.

I'll remove it.

> You do not need to spec this. This procedure is the same for any 
> Map-Resolver that is implemented on an ITR that interfaces to ANY 
> mapping system.

I'll remove it.

> So does a Border Node, that learns about EIDs from other Border 
> Nodes, tell the rest of the SHDHT nodes in its domain? Or do they 
> kind of route to a default edge?

Rest of SHDHT nodes maintain default route to Border Nodes.

> Do you believe coarse EID-prefix aggregation will happen across 
> these Border Node boundaries? That is not at all clear to me.
> 
> If this is the case (maybe not), BGP could be used to distribute 
> this data. But that is so close to the ALT I am not sure where the 
> benefits lie by having a DHT.

No, this is not the same with ALT. EID-prefix aggregation is configured 
according to Domain SHDHT. Coarse EID-prefixes are not aggregated based 
on BGP.

> Again, we should not forward Map-Register messages. There is no 
> benefit and it creates a synchronization requirement that will slow 
> down roaming handoffs.

No synchronization problem as I specifies above. A single node plays roles 
of 
Map-Server for a Map-Register.

> By examining the node's own routing table, right?

In Domain SHDHT, each node is notified with the EID prefix which is 
configured 
for this domain SHDHT. 

> This should be explaining the case of Inter-Domain. You already 
> explained the intra-domain case. Why did you repeat it here?

It is not the same with Intra-domain case specified in Section 4. SHDHT 
node 
needs to determine if the requested EID belong to locate domain SHDHT 
(proposal 2).

> Which border node? All of them?

Just like in LISP Sites, there may be multiple ITRs. SHDHT Node will 
choose 
one border node to forward the message.

> Why BN2? What if there were multiple paths to Domain 1 via BN2 and BN3?

In Fig.3, there is just BN2 for the domain SHDHT 2.

> The need to anchor is not a disadvantage. Mobile-phone providers 
> will want to provision, just like DNS, so having a statically 
> configured one or a well-known map-server address sent in a DHCP 
> will allow existing provisioning systems to be used.
> 
> The cost of the non-anchoring comes at synchronization multiple 
> places for a mobility event. This will cause more dropped and mis-
> routed packets.

I will consider the scenarios with well-know map-server address, thank 
you.

> Dino

Best Regards,
Li Cheng
--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail (and any attachment transmitted herewith) is privileged and confidential and is intended for the exclusive use of the addressee(s).  If you are not an intended recipient, any disclosure, reproduction, distribution or other dissemination or use of the information contained is strictly prohibited.  If you have received this mail in error, please delete it and notify us immediately.
--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail (and any attachment transmitted herewith) is privileged and confidential and is intended for the exclusive use of the addressee(s).  If you are not an intended recipient, any disclosure, reproduction, distribution or other dissemination or use of the information contained is strictly prohibited.  If you have received this mail in error, please delete it and notify us immediately.

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 14 Mar 2013 13:11:49 -0700

> Thank you very much for your comments. Please see my responses inline. 

You are welcome. I trimmed some of your email and included the parts that I am replying to in this email.

> This is my mistake. LISP-DHT is also a hybrid model database, and I should not 
> classify them by this. In my opinion, LISP-NERD is a push model database, isn't 
> it? 

Sure, fine, but define hybrid in this context. I think you mean a "push/pull" hybrid? I am not sure if you are.

> map-server. Let take a LISP-MN for example. A LISP-MN could send the register 
> message to any SHDHT Node which will forward the message to the SHDHT Node who 

You shouldn't spec this or even support it, because now you are defining a new API that an xTR uses to interface to the mapping system. We have one already in the draft-ietf-lisp-ms RFC.

> plays roles of Map-Server for this LISP-MN. Of course, there is a Map-Server 
> for a particular LISP-MN. The difference with other mapping database is that, 
> LISP-MN does not need to maintain connection with the Map-Server. Its register 

The mapping database systems we have experimented to date with are modular. That means they are called "mapping database transport systems", which means only the MRs and MSes need to change to support a new one. The sites do not need to change.

Architecturally, we would like to keep this modularity. There is no reason SHDHT cannot fit in as another mapping database transport system.

> If Node 0x0123 is backup node for Node 0x4444, it stores all data values of Node 

What does responsible mean in this context? Meaning 0x4444 will be the one that forwards the Map-Request?

> A SHDHT node floods it routing information to other nodes belong to the same 
> LISP-SHDHT.A SHDHT node floods it routing information to other nodes belong to 
> the same LISP-SHDHT. 

Okay, so you are implementing a new routing protocol of sorts. You haven't spec'd that out. Like how are these flood messages sent reliably. Do you assume a transport under you?

> Not just lookup requests, but also map-register messages. Map-Register messages 

You shouldn't do this. You are changing the definition of the Map-Register. It is defined in the RFCs to be sent from ETR to Map-Server. Not to a specific type of node in a specific type of mapping database transport system.

> Node ID is just an identifier of a SHDHT node. The partition ID and Node ID both 
> described in the routing table, and it does not need to maintain another mapping. 
> Ok, I will also consider to take Node IDs as the nodes’ locators, it seems simpler. 

Yes, I know what it is. Why can't it be an IP address that is routable.

> Sorry, my mistake. I should write the title as "Address: UDP Port". 

And why do you need a UDP port here?

> There could be multiple methods to choose the corresponding partition ID. Based 
> on the closeness function, it will help to balance load on SHDHT Nodes. Also, 

You did not answer my question. I will raise it at the mic tomorrow in the LISP WG.

> (Map-Request/Map-Register) from xTRs and could hold data value according to 
> its hash segment. 

A receiver of a Map-Request does not define a system to be a map-resolver.

> I see what you mean. For Map-Register, it may register mapping information for 

Right.

> responsible to maintain all mapping information for 10.1/14. It assigns a "hash 
> bits" for its domain SHDHT which is 16bits. All map-request/register will be 
> 10.1.0.0/16, it hash 10.1.0.0/16 to be the resource ID 0x8200 for example, and 
>  Partition ID(The node who receives register message looks up its routing table 
> to determine which SHDHT node maintains the corresponding Partition ID, and 
> forwards the Map-Register message to that node.). When the LISP-MN registers 
> 10.1.1.1, the node also hashes it as 10.1.0.0/16. As a result mapping information 
> of 10.1.0.0/16 and 10.1.1.1/32 are hashed to be the same resource ID and are 
> stored on the same node. 

We need voice for this. We can discuss in WG. Not sure if there will be enough time.

> ETR just chooses the nearest SHDHT Node and sent Map-Register message to it. 

This is not good because now the mapping system will have the same entropy as the roaming devices. We want roamability to scale and to have hand-offs occur fast, so you have to allow roaming to update the fewest possible network entities.

> Just like in LISP Sites, there may be multiple ITRs. SHDHT Node will choose 

I don't known what you mean "just like LISP Sites". ITRs select RLOCs based on the best priority value. But that is orthogonal to what you are doing.

Dino

---

From: [email-masked]
Date: Thu, 14 Mar 2013 20:14:22 -0500

Hi Dino,

Please see my responses inline.

I understand that you mean Map-Register messages MUST NOT be transmited. 
ETR MUST send Map-Register directely to Map-Server.

I will consider the scenarios based on [LISP-MS].

For some comments mentioned this problem, I didn't reply inline.

Thank you.

Dino Farinacci <[email-masked]> 写于 2013/03/14 16:11:49:
> > This is my mistake. LISP-DHT is also a hybrid model database, and 
> > I should not classify them by this. In my opinion, LISP-NERD is a 
> > push model database, isn't it? 
> 
> Sure, fine, but define hybrid in this context. I think you mean a 
> "push/pull" hybrid? I am not sure if you are.

Yes, I mean the "push/pull" hybrid mode.

> > > >    these architectures, when a roaming event occurs and a LISPsite 
or a
> > In LISP-SHDHT, LISP sites especially LISP-MNs need not anchor a 
> > configured map-server. Let take a LISP-MN for example. A LISP-MN 
> > could send the register message to any SHDHT Node which will forward
> > the message to the SHDHT Node who 
> 
> You shouldn't spec this or even support it, because now you are 
> defining a new API that an xTR uses to interface to the mapping 
> system. We have one already in the draft-ietf-lisp-ms RFC.
> 
> > Map-Server for a particular LISP-MN. The difference with other 
> > mapping database is that, LISP-MN does not need to maintain 
> > connection with the Map-Server. Its register message will be forward
> > to the Map-Server. 
> 
> The mapping database systems we have experimented to date with are 
> modular. That means they are called "mapping database transport 
> systems", which means only the MRs and MSes need to change to 
> support a new one. The sites do not need to change.
> 
> Architecturally, we would like to keep this modularity. There is no 
> reason SHDHT cannot fit in as another mapping database transport system.
> 
> > If Node 0x0123 is backup node for Node 0x4444, it stores all data 
> > values of Node 0x4444. But Node 0x123 is not the responsible node 
> > for these partition-IDs ranges, unless there's something wrong with 
> > Node 0x4444. 
> 

In the example, responsible means that Node Ox4444 is requested to store 
mapping information according to the partition-IDs. Node 0x123 is the 
backup node.

> > A SHDHT node floods it routing information to other nodes belong 
> > to the same LISP-SHDHT.A SHDHT node floods it routing information to
> > other nodes belong to the same LISP-SHDHT. 
> 
> Okay, so you are implementing a new routing protocol of sorts. You 
> haven't spec'd that out. Like how are these flood messages sent 
> reliably. Do you assume a transport under you?
> 
> > Not just lookup requests, but also map-register messages. Map-
> > Register messages could also be forwarded by a SHDHT Node. 
> 
> You shouldn't do this. You are changing the definition of the Map-
> Register. It is defined in the RFCs to be sent from ETR to Map-
> Server. Not to a specific type of node in a specific type of mapping
> database transport system.
> 
> > Node ID is just an identifier of a SHDHT node. The partition ID 
> > and Node ID both described in the routing table, and it does not 
> > need to maintain another mapping. Ok, I will also consider to take 
> > Node IDs as the nodes’ locators, it seems simpler. 
> 

I will consider about this.

> And why do you need a UDP port here?

I will modify it in the next version.

> > There could be multiple methods to choose the corresponding 
> > partition ID. Based on the closeness function, it will help to 
> > balance load on SHDHT Nodes. Also, you could choose a simpler method. 
> 

Yes, I see. It's not the comparison of EID with a Partition-ID.

SHDHT Node hashes EID to be a Resource ID. Closeness function is a 
comparison of Resource ID with a Partition ID.

> > No "neither". In our strategy, each SHDHT node could receive 
> > messages (Map-Request/Map-Register) from xTRs and could hold data 
> > value according to its hash segment. 
> 
> > I see what you mean. For Map-Register, it may register mapping 
> > information for such like 10.1.0.0/16 and 10.1.1.1/32. How to hash 
> > and store these map-registers, right? 
> 
> Right.
> 
> > Suppose a Domain SHDHT is operated by a mapping service provider 
> > who is responsible to maintain all mapping information for 10.1/14. 
> > It assigns a "hash bits" for its domain SHDHT which is 16bits. All 
> > map-request/register will be hashed as a /16 EID-prefix. When a node
> > receives a register message for 10.1.0.0/16, it hash 10.1.0.0/16 to 
> > be the resource ID 0x8200 for example, and the mapping information 
> > of 10.1.0.0/16 is stored based on corresponding Partition ID(The 
> > node who receives register message looks up its routing table to 
> > determine which SHDHT node maintains the corresponding Partition ID,
> > and forwards the Map-Register message to that node.). When the LISP-
> > MN registers 10.1.1.1, the node also hashes it as 10.1.0.0/16. As a 
> > result mapping information of 10.1.0.0/16 and 10.1.1.1/32 are hashed
> > to be the same resource ID and are stored on the same node. 
> 
> This is not good because now the mapping system will have the same 
> entropy as the roaming devices. We want roamability to scale and to 
> have hand-offs occur fast, so you have to allow roaming to update 
> the fewest possible network entities.
> 
> > Just like in LISP Sites, there may be multiple ITRs. SHDHT Node 
> > will choose one border node to forward the message.
> 
> I don't known what you mean "just like LISP Sites". ITRs select 
> RLOCs based on the best priority value. But that is orthogonal to 
> what you are doing.

My fault. It's not the same with LISP Sites.
Domain SHDHT Nodes maintain default routes pointing to the Border Nodes.