< draft-chen-lisp-er-mo-00.txt   draft-chen-lisp-er-mo-01.txt >
Network Working Group G. Chen Network Working Group G. Chen
Internet-Draft H. Deng Internet-Draft H. Deng
Intended status: Informational B. Zhou Intended status: Informational B. Zhou
Expires: January 7, 2010 CMCC, Inc. Expires: January 12, 2010 CMCC, Inc.
M. Xu M. Xu
D. Huo D. Huo
Y. Cao Y. Cao
Tsinghua University Tsinghua University
July 6, 2009 July 11, 2009
An Incremental Deployable Mapping Service for Scalable Routing An Incremental Deployable Mapping Service for Scalable Routing
Architecture Architecture
draft-chen-lisp-er-mo-00 draft-chen-lisp-er-mo-01
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 38 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 7, 2010. This Internet-Draft will expire on January 12, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info). publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. and restrictions with respect to this document.
Abstract Abstract
This document describes a mechanism of providing mapping service for This document describes a mechanism of providing mapping service for
LISP-like architecture. The mapping service comprises of EID Router LISP-like architecture. The mapping service comprises of EID Router
(ER) mechanism and supplementary DHT Mapping Overlay (MO), in which (ER) mechanism and supplementary DHT Mapping Overlay (MO), in which
ER mechanism is for non-cached packets tunneling, while the DHT MO ER mechanism is for reducing forwarding entries in routers while
serves as a supplement that provides specific mappings to reduce driving the packets to the destination through tunnels, and the DHT
tunneling cost. The mechanism is flexibly deployable for ISPs since MO serves as a supplement that provides specific mappings to reduce
it costs little and is easy to progress. the number of tunnels. The mechanism is flexibly deployable for ISPs
since it costs little and is easy to progress.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4 2. Definition of Terms . . . . . . . . . . . . . . . . . . . . . 4
3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. When an ITR meets packets . . . . . . . . . . . . . . . . . . 6 4. When an ITR meets packets . . . . . . . . . . . . . . . . . . 6
5. Utilization of BGP advertising . . . . . . . . . . . . . . . . 7 5. Utilization of current BGP system . . . . . . . . . . . . . . 7
5.1. Automatic Mapping obtainment and storage . . . . . . . . . 7 5.1. Automatic Mapping obtainment and storage . . . . . . . . . 7
5.2. Mapping propagation by BGP . . . . . . . . . . . . . . . . 7 5.2. Mapping propagation by BGP . . . . . . . . . . . . . . . . 7
6. EID Router mechanism . . . . . . . . . . . . . . . . . . . . . 9 6. EID Router mechanism . . . . . . . . . . . . . . . . . . . . . 9
6.1. Address aggregation policy . . . . . . . . . . . . . . . . 9 6.1. Address aggregation policy . . . . . . . . . . . . . . . . 9
6.2. EID Router . . . . . . . . . . . . . . . . . . . . . . . . 9 6.2. EID Router . . . . . . . . . . . . . . . . . . . . . . . . 9
6.3. When an ER meets packets . . . . . . . . . . . . . . . . . 9 6.3. When an ER meets packets . . . . . . . . . . . . . . . . . 9
7. Supplementary DHT Mapping Overlay (MO) . . . . . . . . . . . . 11 7. Supplementary DHT Mapping Overlay (MO) . . . . . . . . . . . . 11
7.1. Mapping Node (MN) and Mapping Server (MS) . . . . . . . . 11 7.1. Mapping Node (MN) and Mapping Server (MS) . . . . . . . . 11
7.2. MNID Assignment and K-bucket Table . . . . . . . . . . . . 11 7.2. MNID Assignment and K-bucket Table . . . . . . . . . . . . 11
7.3. LOOKUP Process . . . . . . . . . . . . . . . . . . . . . . 12 7.3. LOOKUP Process . . . . . . . . . . . . . . . . . . . . . . 12
7.4. Security Consideration of Mapping Storage . . . . . . . . 12 7.4. Security Consideration of Mapping Storage . . . . . . . . 12
7.5. Self-adaptive Capability . . . . . . . . . . . . . . . . . 12 7.5. Self-adaptive Capability . . . . . . . . . . . . . . . . . 13
7.6. Dynamic Adjustment of K value and m value . . . . . . . . 13 7.6. Dynamic Adjustment of K value and m value . . . . . . . . 13
7.7. Mapping Storing and Exchanging in Multi-homing Scenario . 13 7.7. Mapping Storing and Exchanging in Multi-homing Scenario . 13
8. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 14 8. Incremental Deployment . . . . . . . . . . . . . . . . . . . . 14
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15
10. Security Considerations . . . . . . . . . . . . . . . . . . . 16 10. Security Considerations . . . . . . . . . . . . . . . . . . . 16
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18
12.1. Normative References . . . . . . . . . . . . . . . . . . . 18 12.1. Normative References . . . . . . . . . . . . . . . . . . . 18
12.2. Informative References . . . . . . . . . . . . . . . . . . 18 12.2. Informative References . . . . . . . . . . . . . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19
skipping to change at page 3, line 23 skipping to change at page 3, line 23
designed and built as database for storing mapping information, as designed and built as database for storing mapping information, as
well as providing mapping lookup results for mapping queries. well as providing mapping lookup results for mapping queries.
The problem they commonly share is that packets without any caches on The problem they commonly share is that packets without any caches on
current ITR have to be waiting for the reply of mapping lookup query, current ITR have to be waiting for the reply of mapping lookup query,
or simply be dropped by this ITR as long as no relevant cache exists or simply be dropped by this ITR as long as no relevant cache exists
on this ITR. on this ITR.
One solution to this problem could be that, instead of sending lookup One solution to this problem could be that, instead of sending lookup
queries to the Mapping Overlay (MO), data packet itself is sent to queries to the Mapping Overlay (MO), data packet itself is sent to
the MO as a query and get forwarded in the MO to the final ETR linked the MO as a query (e.g., "Data Probe" in [I-D.fuller-lisp-alt]>) and
to the site in which the destination EID resides. But usually when a get forwarded in the MO to the final ETR linked to the site in which
packet is going through the MO, long latency becomes a remarkable the destination EID resides. But usually when a packet is going
problem then. through the MO, long latency becomes a remarkable problem then.
In this draft we describe a mechanism that aims:
o to eliminate all forwarding entries to distant customer ASes in P
routers;
o to eliminate the forwarding entries, targeted to distant customer
ASes not behind the border routers, in the border routers;
o to be deployed incrementally; In this draft we describe an incremental deployable mapping service
for LISP. This mapping service comprises of EID Router (ER)
mechanism and supplementary DHT Mapping Overlay (MO). The ER
mechanism is designed for reducing forwarding entries in routers,
while driving the packets to the destination through tunnels. The
DHT MO serves as a supplement that provides specific mappings to
reduce the number of tunnels along the path to the destination. Note
that an ER can be deployed unilaterally in an AS for it's own
benefits and the DHT MO is unitedly built among ASes however whether
to join the MO is not compulsory to an AS (it can still benefit from
deploying the ER).
o to help reduce the number of tunnels. The remainder of this document is organized as follows: Section 2
provides the definitions of terms in this document. Section 3
sketches an overview of the mapping service. Section 4 describes how
an ITR handles the packets. Section 5 describes how to utilize
current BGP system in the mapping service. Section 6 describes how
the EID Router mechanism works, and Section 7 describes how to build
the DHT Mapping Overlay and how to retrieve mappings in it. And
Section 8 shows the steps for deploying the mapping service
incrementally.
2. Definition of Terms 2. Definition of Terms
Mapping: EID-to-ELOC mapping. Mapping: an EID-to-ELOC mapping.
EID Router (ER): a new introduced router which keeps entries to all
EIDs.
EID aggregated prefix: an aggregated prefix which covers some EID EID aggregated prefix: an aggregated prefix which covers some EID
blocks. blocks.
EID+RLOC aggregated prefix: an aggregated prefix which covers EID EID+RLOC aggregated prefix: an aggregated prefix which covers some
blocks and RLOCs. EID block(s) and RLOC(s).
EID Router (ER): a new introduced router which keeps entries to all
EID aggregated prefixes.
Mapping Node (MN): an entity used for storing a mapping. Each MN Mapping Node (MN): an entity used for storing a mapping. Each MN
holds and can only hold one mapping, and each mapping is related holds and can only hold one mapping, and each mapping is related
to only one MN. to only one MN. It can be implemented as a process in a MS, which
has a data structure to store the mapping as well as the ability
to manage and retrieve the mappings.
Master Mapping Node (MMN): a chosen Mapping Node used to be the Master Mapping Node (MMN): a chosen Mapping Node used to be the
representative among redundant MNs. It is in charge of initiating representative among redundant MNs. It is in charge of initiating
mapping query and exchanging mappings. mapping query and exchanging mappings.
Mapping Server (MS): a server specified to physically store Mapping Server (MS): a server specified to physically store
mappings. Each MS can hold more than one Mapping Nodes. mappings. Each MS can hold more than one Mapping Nodes.
Mapping Overlay (MO): a DHT overlay based on Kademlia protocol, Mapping Overlay (MO): a DHT overlay, which is designed for storing
which is designed for storing the distributed mapping information. the distributed mapping information. Only one MO exists among
Only one MO exists among ISPs in the Internet. ISPs in the Internet.
3. Overview 3. Overview
To achieve the four aims in Section 1, the mechanism described in The mechanism described in this draft aims:
this draft mainly comprises of the following two parts:
o to eliminate all forwarding entries to distant customer ASes in P
routers;
o to eliminate the forwarding entries, targeted to distant customer
ASes not behind the border routers, in the border routers;
o to be deployed incrementally;
o to help reduce the number of tunnels.
To achieve the four aims above, the mechanism described in this draft
mainly comprises of the following two parts:
o EID Router (ER) mechanism for non-cached packets tunneling, and o EID Router (ER) mechanism for non-cached packets tunneling, and
o DHT Mapping Overlay (MO) as a supplement, which provides specific o DHT Mapping Overlay (MO) as a supplement, which provides specific
mappings to reduce tunneling cost. mappings to reduce tunneling cost.
The EID Router mechanism is designed for the first three aims, and The EID Router mechanism is designed for the first three aims, and
the DHT MO is designed for the last aim. the DHT MO is designed for the last aim.
In EID Router mechanism, by manually or automatically setting the In EID Router mechanism, by manually or automatically setting the
skipping to change at page 6, line 15 skipping to change at page 6, line 15
4. When an ITR meets packets 4. When an ITR meets packets
When an ITR receives a packet originated from a customer site, it When an ITR receives a packet originated from a customer site, it
checks whether a copy of mapping exists in its cache first. checks whether a copy of mapping exists in its cache first.
If the mapping exists, the ITR encapsulates the packet in a LISP If the mapping exists, the ITR encapsulates the packet in a LISP
header, putting the RLOC extracted from the mapping onto the outer header, putting the RLOC extracted from the mapping onto the outer
destination address, meanwhile selecting one of the ITR's RLOC as the destination address, meanwhile selecting one of the ITR's RLOC as the
outer source address. outer source address.
Else if cache misses (i.e. no relevant copy of mapping exists in the Else if cache misses (i.e., no relevant copy of mapping exists in the
ITR), two concurrent events occur: ITR), two concurrent events occur:
o Data Plane Traffic: the packet simply follows a default route o Data Plane Traffic: the packet simply follows a default route
preset manually or automatically to an ER in current AS. Since ER preset manually or automatically to an ER in current AS. Since ER
knows whole global mapping information, it can forward every knows whole global mapping information, it can forward every
packet to the right ETR by encapsulating the packet in LISP header packet to the right ETR by encapsulating the packet in LISP header
with the ITR's RLOC in the outer source address and the ETR's RLOC with the ITR's RLOC in the outer source address and the ETR's RLOC
in the outer destination address. in the outer destination address.
o Control Plane Traffic: the ITR sends a Mapping Query to its o Control Plane Traffic: the ITR sends a Mapping Query to its
default Mapping Server (MS) in the AS. And then a mapping LOOKUP default Mapping Server (MS) in the AS. And then a mapping LOOKUP
process (details of mapping lookup process are shown in Section 7) process (details of mapping lookup process are shown in Section 7)
is launched in the Mapping Overlay (MO) by the Master Mapping Node is launched in the Mapping Overlay (MO) by the Master Mapping Node
(MMN) of the ITR. Finally a copy of queried mapping is returned (MMN) of the ITR. After the MMN receives a copy of queried
to the ITR which initiated the Mapping Query, and is cached for a mapping from the MO, it returns the copy to the ITR which
period of time. initiated the Mapping Query, and is cached for a period of time.
5. Utilization of BGP advertising 5. Utilization of current BGP system
The BGP is an inter-Autonomous System routing protocol. The primary The BGP is an inter-Autonomous System routing protocol. The primary
function of a BGP speaking system is to exchange network reachability function of a BGP speaking system is to exchange network reachability
information with other BGP systems. This network reachability information with other BGP systems. This network reachability
information includes information on the list of ASes that information includes information on the list of ASes that
reachability information traverses. This information is sufficient reachability information traverses. This information is sufficient
for constructing a graph of AS connectivity for this reachability, as for constructing a graph of AS connectivity for this reachability, as
well as inevitable for constructing the mappings from EIDs onto RLOCs well as inevitable for constructing the mappings from EIDs onto RLOCs
automatically. Moreover, especially for incremental deployment automatically. Moreover, especially for incremental deployment
requirement, which means ASes deployed new mechanism must work along requirement, which means ASes deployed new mechanism must work along
with those who not deployed, it is necessary to apply BGP to mapping with those not deployed ones, it is necessary to design mapping
service. service inherently adaptable for the current running BGP system
(i.e., the BGP system we use for basic routing and forwarding today).
The BGP in the mapping service has two functions: to obtain the The BGP in the mapping service has two functions: to obtain the
mappings automatically, and to propagate mappings to ERs in other mappings automatically, and to propagate mappings to ERs in other
ASes. ASes. They're both based on current running BGP system.
5.1. Automatic Mapping obtainment and storage 5.1. Automatic Mapping obtainment and storage
When an customer AS advertise an BGP UPDATE message to homed (no When an customer AS advertise an BGP UPDATE message to homed (no
matter single-homed or multi-homed) provider AS which is deployed the matter single-homed or multi-homed) provider AS which is deployed the
DHT mapping server described in Section 7, the provider AS would set DHT mapping server described in Section 7, the provider AS would set
or update the relevant mapping information according to the or update the relevant mapping information according to the
advertised route to the customer AS. The announced prefix is treat advertised route to the customer AS. The announced prefix is treat
as the EID in the mapping <EID, RLOC> and the address of the ETR as the EID in the mapping <EID, RLOC> and the address of the ETR
which directly receives BGP announcement from the customer AS is which directly receives BGP announcement from the customer AS is
chosen as the RLOC. chosen as the RLOC.
This mapping could be stored both in MN (Mapping Node) and ER (EID This mapping could be stored both in MN (Mapping Node) and ER (EID
Router) concurrently. In the former case, one mapping refers to one Router) concurrently. In the former case, one mapping refers to one
MN and vice versa as described in Section 7. However in the latter MN and vice versa as described in Section 7. However in the latter
case, the mapping is not only stored in the ER in current provider case, the mapping is not only stored in the ER in current provider
AS, but also propagated to distant provider ASes by BGP AS, but also propagated to distant provider ASes by BGP
advertisements and stored in ERs at those ASes. advertisements and stored in ERs at those ASes.
Note that the mappings obtained so far are original specific
mappings. In DHT MO, these original specific mappings are stored on
MNs and no changes on mapping granularity. However in ER mechanism,
during the mapping propagation by BGP, mapping granularity is changed
once a prefix aggregation occurs in an AS (details are shown in
Section 5.2).
5.2. Mapping propagation by BGP 5.2. Mapping propagation by BGP
BGP speakers work as what they act today, in addition that mapping BGP speakers work as what they act today, in addition that mapping
information is affiliated in BGP UPDATE message. Each BGP speaker on information is affiliated in BGP UPDATE message. Each BGP speaker on
the route SHALL keep the originality of the mappings (i.e., the the route SHALL keep the originality of the mappings (i.e., the
mappings stay untouched during propagation), except that it mappings stay untouched during propagation), except that it
aggregates some prefixes into one. New mapping SHOULD be formed when aggregates some prefixes into one. New mapping SHOULD be formed when
such aggregation occurs, in which case both EID and RLOC in mapping such aggregation occurs, in which case both EID and RLOC in mapping
<EID, RLOC> are updated, that EID is set to the new aggregated EID <EID, RLOC> are updated, that EID is set to the new aggregated EID
block which covers more prefixes while RLOC is set to the address of block which covers more prefixes while RLOC is set to the address of
skipping to change at page 9, line 22 skipping to change at page 9, line 22
For example, suppose two EID blocks 166.111.8/24 and 166.111.9/24 For example, suppose two EID blocks 166.111.8/24 and 166.111.9/24
belong to two customer ASes homed to a provider AS which has some belong to two customer ASes homed to a provider AS which has some
RLOCs range from 166.111.10/24 to 166.111.11/24, the provider AS can RLOCs range from 166.111.10/24 to 166.111.11/24, the provider AS can
aggregate either to an EID aggregated prefix 166.111.8/23 or to an aggregate either to an EID aggregated prefix 166.111.8/23 or to an
EID+RLOC aggregated prefix 166.111.8/22. EID+RLOC aggregated prefix 166.111.8/22.
6.2. EID Router 6.2. EID Router
An EID Router is no particular than a legacy router, except that An EID Router is no particular than a legacy router, except that
special configuration is applied. It is configured to act as an eBGP special configuration is applied. It is configured to act as an eBGP
speaker, and only loads the forwarding entries to all EIDs including speaker, and only loads the forwarding entries to all EID aggregated
EID aggregated prefixes. Note that the EID+RLOC aggregated prefixes prefixes. Note that the EID+RLOC aggregated prefixes don't have to
don't have to be loaded in EID Routers, since the RLOCs in the EID+ be loaded in EID Routers, since the RLOCs in the EID+RLOC aggregated
RLOC aggregated prefixes are supposed be reachable (i.e., forwarding prefixes are supposed be reachable (i.e., forwarding entries to these
entries to these prefixes should be preserved in the P routers). prefixes should be preserved in the P routers).
So the ideal situation becomes: So the ideal situation becomes:
o the EID Routers load the forwarding entries to all EIDs including o the EID Routers load the forwarding entries to all EID aggregated
EID aggregated prefixes, prefixes,
o the P routers load the forwarding entries to all RLOCs and all o the P routers load the forwarding entries to all RLOCs and all
EID+RLOC aggregated prefixes, and EID+RLOC aggregated prefixes, and
o the border routers load the forwarding entries to all EIDs, RLOCs o the border routers load the forwarding entries to all RLOCs and
and EID+RLOC aggregated prefixes of the distant ASes behind the the prefixes (i.e., EID aggregated prefixes and EID+RLOC
border routers. aggregated prefixes) of the distant ASes behind the border
routers.
So due to deploying the EID Router mechanism, P routers and border So due to deploying the EID Router mechanism, P routers and border
routers can get their FIB (Forwarding Information Base) size reduced. routers can get their FIB (Forwarding Information Base) size reduced.
6.3. When an ER meets packets 6.3. When an ER meets packets
When an ER receives a packet, it matches the destination address with When an ER receives a packet, it matches the destination address with
entries in its forwarding table (that can be seen as the mapping entries in its forwarding table (that can be seen as the mapping
table). Since the ER holds whole mapping table (from its angle of table). Since the ER holds whole mapping table (from its angle of
view), this packet can be encapsulated in a LISP header and sent out. view), this packet can be encapsulated in a LISP header and sent out.
skipping to change at page 11, line 7 skipping to change at page 11, line 7
the path to the destination, in which case the downstream AS the path to the destination, in which case the downstream AS
didn't pass the mapping information to this distant AS so that the didn't pass the mapping information to this distant AS so that the
ER in this distant AS created a new mapping (the ER's RLOC is set ER in this distant AS created a new mapping (the ER's RLOC is set
in the mapping). in the mapping).
o the destination ETR, in which case the originality of the mapping o the destination ETR, in which case the originality of the mapping
is maintained. is maintained.
7. Supplementary DHT Mapping Overlay (MO) 7. Supplementary DHT Mapping Overlay (MO)
The DHT Mapping Overlay (MO) is based on Kademlia, a highly efficient The DHT Mapping Overlay (MO) is based on [Kademlia], a highly
protocol of Distributed Hash Table (DHT) overlay for Peer-to-Peer efficient protocol of Distributed Hash Table (DHT) overlay for Peer-
network, which applies XOR as metric to measure distance. Here in to-Peer network, which applies XOR as metric to measure distance.
the MO, it is adapted to meet several requirements below: Here in the MO, it is adapted to meet several requirements below:
o MO should be scalable; o MO should be scalable;
o MO should have a good ability of redundancy; o MO should have a good ability of redundancy;
o MO should be self-adaptive for mapping adding or failure; o MO should be self-adaptive for mapping adding or failure;
o MO should be flexible for balancing performance and overhead; o MO should be flexible for balancing performance and overhead;
o MO should support multi-homing scenario. o MO should support multi-homing scenario.
skipping to change at page 11, line 32 skipping to change at page 11, line 32
The benefit of deploying the MO is that, it provides specific The benefit of deploying the MO is that, it provides specific
mappings since it doesn't aggregate prefixes (i.e., mappings stored mappings since it doesn't aggregate prefixes (i.e., mappings stored
in MO are finest-granulated that each mapping refers to one relation in MO are finest-granulated that each mapping refers to one relation
between a customer AS and one of its provider site). Due to the between a customer AS and one of its provider site). Due to the
large number of such fines-granulated mappings, the MO should be large number of such fines-granulated mappings, the MO should be
scalable and capable for redundancy. So DHT is chosen as the means scalable and capable for redundancy. So DHT is chosen as the means
of distributing the mappings. of distributing the mappings.
7.1. Mapping Node (MN) and Mapping Server (MS) 7.1. Mapping Node (MN) and Mapping Server (MS)
Each mapping is stored on one Mapping Node (MN) in the Mapping As described in Section 5.1, a mapping is automatically obtained from
Overlay (MO), and each Mapping Server (MS) can accommodate more than the BGP advertisement through the ETR. Afer that it is sent to a MS
one MNs. For example, an ISP is accessed by 5 customer ASes labeled in current provider AS and then stored in a new created MN (or
as a, b, c, d, e, whose corresponding EIDs are v, w, x, y, z manually set on the MN). Note that each mapping can only be
respectively. These five EID prefixes of customer ASes are one-to- initially stored on one MN in the MO, and each MS can accommodate
one mapped, forming five MNs physically existed on one or multiple more than one MNs. For example, an ISP is accessed by 5 customer
ASes labeled as a, b, c, d, e, whose corresponding EIDs are v, w, x,
y, z respectively. These five EID prefixes of customer ASes are one-
to-one mapped, forming five MNs physically existed on one or multiple
MSes administrated by the ISP. MSes administrated by the ISP.
7.2. MNID Assignment and K-bucket Table 7.2. MNID Assignment and K-bucket Table
In the MO, each MN is assigned a 160 bit ID. The DHT MO utilizes the In the MO, each MN is assigned a 160 bit ID. The DHT MO utilizes the
highest numerical IP address reserved in customer ASes as a MNID. highest numerical IP address reserved in customer ASes as a MNID.
For example, assume a customer AS with a prefix 162.137.2/24 is For example, assume a customer AS with a prefix 162.137.2/24 is
mapped to the RLOC 134.121.3.56. The lower 32 bits of the MNID of mapped to the RLOC 134.121.3.56. The lower 32 bits of the MNID of
the corresponding Master Mapping Node (MMN) is 0xA28902FE (i.e., the corresponding Master Mapping Node (MMN) is 0xA28902FE (i.e.,
162.137.2.254), and the rest 128 bits are all 0. The mapping will be 162.137.2.254), and the rest 128 bits are all 0. The mapping will be
stored on this MMN and several (at least one) other MNs whose MNIDs stored on this MMN and several (at least one) other MNs whose MNIDs
are closest to the MNID 0xA28902FE. are closest to the MNID 0xA28902FE.
Each MN manages a K-bucket table of its own that keeps addresses Each MN manages a K-bucket table of its own that keeps the
(RLOCs) and some other information (e.g. MNID) of other nodes. The information how it can reach other MNs (i.e., the RLOCs of the
table of a node N consists of 160 rows in which the i-th row (0 <= i resident MSes of these MNs). Each MN's reachability imformation is
< 160) preserves information (i.e. RLOCs and IDs) of some nodes stored on a node in K-bucket. The table of a MN N consists of 160
which are at a distance range 2^I ~ 2^(i+1) from node N. If i becomes rows in which the i-th row (0 <= i < 160) preserves the reachability
quite large, the number of nodes that the i-th row preserves is information of some MNs (i.e., the RLOCs of the resident MSes of
limited to K at most. these MNs) which are at a distance range 2^I ~ 2^(i+1) from N. If i
becomes quite large, the number of nodes that the i-th row preserves
is limited to K at most.
7.3. LOOKUP Process 7.3. LOOKUP Process
LOOKUP process needs to call FIND_MAP with MNID of destination MN as LOOKUP process needs to call FIND_MAP with MNID of destination MN as
parameter. Here describes the FIND_MAP procedure: parameter. Here describes the FIND_MAP procedure (MN B is the
destination MN):
1. MN A calculate the distance D from A to B (D = A XOR B); 1. MN A calculate the distance D from A to B (D = A XOR B);
2. Fetch m MNs from the right row of K-bucket table of MN A and then 2. Fetch m MNs from the right row of K-bucket table of MN A and then
query them (call FIND_MAP for every one of these m MNs); query them (call FIND_MAP for every one of these m MNs);
3. MN A set a timer waiting reply for each MN that a called 3. MN A set a timer waiting reply for each MN that a called
FIND_MAP. If it expires, then delete information of FIND_MAP. If it expires, then delete information of
corresponding MN in K-bucket table. corresponding MN in K-bucket table.
skipping to change at page 14, line 25 skipping to change at page 14, line 25
reduced however the length of the intra-domain route grows. It's up reduced however the length of the intra-domain route grows. It's up
to ISPs to decide whether to tolerate such length-stretch to obtain to ISPs to decide whether to tolerate such length-stretch to obtain
decrease of FIB (Forwarding Information Base) size. decrease of FIB (Forwarding Information Base) size.
As time goes by, suppose more and more ISPs have deployed ERs. Some As time goes by, suppose more and more ISPs have deployed ERs. Some
of them may then deploy the DHT MO to benefit from specific mappings of them may then deploy the DHT MO to benefit from specific mappings
(that can decrease number of tunnels needed in each data (that can decrease number of tunnels needed in each data
transmission) by simply putting MSes in their ASes and let them join transmission) by simply putting MSes in their ASes and let them join
the MO automatically as described in Section 7. the MO automatically as described in Section 7.
Note that unlike other mechanisms, no new particular devices are There're no new particular devices or functions required to support
required to support backward-compatibility. backward-compatibility.
9. Acknowledgements 9. Acknowledgements
10. Security Considerations 10. Security Considerations
The ERs can apply any existing security mechanisms for BGP to enhance The ERs can apply any existing security mechanisms for BGP to enhance
the security. And for DHT MO, existing authentication methods for the security. And for DHT MO, existing authentication methods for
DHT (especially for Kademlia) can be adapted to enhance its security. DHT (especially for Kademlia) can be adapted to enhance its security.
Other new security enhancements are expected to design to support the Other new security enhancements are expected to design to support the
mechanism in this draft in future. mechanism in this draft in future.
skipping to change at page 19, line 5 skipping to change at page 18, line 31
[I-D.fuller-lisp-alt] [I-D.fuller-lisp-alt]
Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "LISP Farinacci, D., Fuller, V., Meyer, D., and D. Lewis, "LISP
Alternative Topology (LISP+ALT)", draft-fuller-lisp-alt-05 Alternative Topology (LISP+ALT)", draft-fuller-lisp-alt-05
(work in progress), February 2009. (work in progress), February 2009.
[I-D.meyer-lisp-cons] [I-D.meyer-lisp-cons]
Brim, S., "LISP-CONS: A Content distribution Overlay Brim, S., "LISP-CONS: A Content distribution Overlay
Network Service for LISP", draft-meyer-lisp-cons-04 (work Network Service for LISP", draft-meyer-lisp-cons-04 (work
in progress), April 2008. in progress), April 2008.
[Kademlia]
Maymounkov, P. and D. Mazieres, "Kademlia: A Peer-to-peer
Information System Based on the XOR Metric", IPTPS'02,
Boston, 2002.
Authors' Addresses Authors' Addresses
Gang Chen Gang Chen
CMCC, Inc. CMCC, Inc.
53A, Xibianmennei Ave., 53A, Xibianmennei Ave.,
Xuanwu District Xuanwu District
Beijing 100053 Beijing 100053
P.R.China P.R.China
Phone: +86-10-1391-071-0674 Phone: +86-10-1391-071-0674
 End of changes. 30 change blocks. 
74 lines changed or deleted 119 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/