[rrg] Summary of "Enhanced Efficiency of Mapping Distribution Protocols in Map-and-Encap Schemes"

["Sriram, Kotikalapudi" <[e-mail]>]

My message posted to the list encountered a problem the first time.
Resending ... please pardon the repetition if you get this message twice.

Sriram 
________________________________________
From: Sriram, Kotikalapudi
Sent: Tuesday, December 22, 2009 10:44 PM
To: Lixia Zhang; [e-mail]
Cc: Tony Li
Subject: Summary of "Enhanced Efficiency of Mapping Distribution Protocols in Map-and-Encap Schemes"

Lixia:
Tony:

As you would remember, I had presented this work at Dublin RRG meeting.
I do not intend it to be a contribution for the mainstream set of proposals
for a solution for scalability. Also, it relates in part to making mapping distribution
more efficient -- I have followed some of the discussion about relevance of including
"mapping systems" between you, Michael Menth, Biran and others.
Well, this is not a proposal for a new type of  "mapping system"
but it is about making map-and-encap (LISP type of) schemes
more efficient by suitable enhancements to the mapping distribution
protocol. There is a part of this proposal which deals with hierarchy of
locators (ETRs) for hierarchical map-and-encap schemes (there is some possible
conceptual overlap with the GLI-Split proposal).

My main intent in submitting this proposal/document is for archival value.
As the RRG work moves further along, I would be happy if we can
revisit the ideas presented here. At that point, I would also plan to further assist
with more details and performance modeling of this proposal.

Sriram

Summary (980 words) follows.
---------------------------------------------------------------------------------------------------------
Summary of
"Enhanced Efficiency of Mapping Distribution Protocols in Map-and-Encap Schemes"

We present some architectural principles pertaining to the mapping distribution protocols, especially applicable to map-and-encap (e.g., LISP) type of protocols. These principles enhance the efficiency of the map-and-encap protocols in terms of (1) better utilization of resources (e.g., processing and memory) at Ingress Tunnel Routers (ITRs) and mapping servers, and consequently, (2) reduction of response time (e.g., first packet delay). We consider how Egress Tunnel Routers (ETRs) can perform aggregation of end-point ID (EID) address space belonging to their downstream delivery networks, in spite of migration/re-homing of some subprefixes to other ETRs. This aggregation may be useful for reducing the processing load and memory consumption associated with map messages, especially at some resource-constrained ITRs and subsystems of the mapping distribution system. We also consider another architectural concept where the ETRs are organized in a hierarchical manner for the potential benefit of aggregation of their EID address spaces. The two key architectural ideas are discussed in some more detail below. A more complete description can be found in a document that was presented at the RRG meeting in Dublin. Links to the document and slides presented at Dublin RRG meeting are:
Document:
http://www.antd.nist.gov/~ksriram/NGRA_map_mgmt.pdf 
Presentation slides:
http://www.antd.nist.gov/~ksriram/MDP_Dublin_KS_Slides.pdf 

It will be helpful to refer to Figures 1, 2, and 3 in the document noted above for some of the discussions that follow here below.

A.      Management of Mapping Distribution of Subprefixes Spread Across Multiple ETRs

To assist in this discussion, we start with the high level architecture of a map-and-encap approach (it would be helpful to see Fig. 1 in the document mentioned above). In this architecture we have the usual ITRs, ETRs, delivery networks, etc. In addition, we have the ID-Locator Mapping (ILM) servers which are repositories for complete mapping information, while the ILM-Regional (ILM-R) servers can contain partial and/or regionally relevant mapping information.

While a large endpoint address space contained in a prefix may be mostly associated with the delivery networks served by one ETR, some fragments (subprefixes) of that address space may be located elsewhere at other ETRs. Let a/20 denote a prefix that is conceptually viewed as composed of 16 subnets of /24 size that are denoted as a1/24, a2/24, :::, a16/24. For example, a/20 is mostly at ETR1, while only two of its subprefixes a8/24 and a15/24 are elsewhere at ETR3 and ETR2, respectively (see Fig. 2 in the document). From the point of view of efficiency of the mapping distribution protocol, it may be beneficial for ETR1 to announce a map for the entire space a/20 (rather than fragment it into a multitude of more-specific prefixes), and provide the necessary exceptions in the map information. Thus the map message could be in the form of Map:(a/20, ETR1; Exceptions: a8/24, a15/24). In addition, ETR2 and ETR3 announce the maps for a15/24 and a8/24, respectively, and so the ILMs know where the exception EID addresses are located. Now consider a host associated with ITR1 initiating a packet destined for an address a7(1), which is in a7/24 that is not in the exception portion of a/20. Now a question arises as to which of the following approaches would be the best choice:

1) ILM-R provides the complete mapping information for a/20 to ITR1 including all maps for relevant exception subprefixes.
2) ILM-R provides only the directly relevant map to ITR1 which in this case is (a/20, ETR1).

In the first approach, the advantage is that ITR1 would have the complete mapping for a/20 (including exception subnets), and it would not have to generate queries for subsequent first packets that are destined to any address in a/20, including a8/24 and a15/24. However, the disadvantage is that if there is a significant number of exception subprefixes, then the very first packet destined for a/20 will experience a long delay, and also the processors at ITR1 and ILM-R can experience overload. In addition, the memory usage at ITR1 can be very inefficient as well. The advantage of the second approach above is that the ILM-R does not overload resources at ITR1 both in terms of processing and memory usage but it needs an enhanced map response in of the form Map:(a/20, ETR1, MS=1), where MS (more specific) indicator is set to 1 to indicate to ITR1 that not all subnets in a/20 map to ETR1. The key idea is that aggregation is beneficial and subnet exceptions must be handled with additional messages or indicators in the maps.

B. Management of Mapping Distribution for Scenarios with Hierarchy of ETRs and Multi-Homing

Now we highlight another architectural concept related to mapping management (helpful here to refer to Fig. 3 in the document). Here we consider the possibility that ETRs may be organized in a hierarchical manner. For instance ETR7 is higher in hierarchy relative to ETR1, ETR2, and ETR3, and like-wise ETR8 is higher relative to ETR4, ETR5, and ETR6. For instance, ETRs 1 through 3 can relegate locator role to ETR7 for their EID address space. In essence, they can allow ETR7 to act as the locator for the delivery networks in their purview. ETR7 keeps a local mapping table for mapping the appropriate EID address space to specific ETRs that are hierarchically associated with it in the level below. In this situation, ETR7 can perform EID address space aggregation across ETRs 1 through 3 and can also include its own immediate EID address space for the purpose of that aggregation. The many details related to this approach and special circumstances involving multi-homing of subnets are discussed in detail in the detailed document noted earlier. The hierarchical organization of ETRs and delivery networks should help in the future growth and scalability of ETRs and mapping distribution networks. This is essentially recursive map-and-encap, and some of the mapping distribution and management functionality will remain local to topologically neighboring delivery networks which are hierarchically underneath ETRs.