一种基于位置与身份标识分离协议的映射查询方法

陈前斌，王 磊，唐 伦

(重庆邮电大学移动通信技术重庆市市级重点实验室，重庆 400065)

0 引言

目前，日益增长的网络规模和用户需求给互联网带来了众多挑战。随着应用及计算模式的日益丰富及社会对互联网依赖程度的增强，原先主要以科学研究为目的而设计的TCP/IP网络体系架构已经难以满足社会经济发展的要求。因此，近年来研究人员开展了面向变革式的未来网络研究。未来网络将采用全新的网络设计和创新理念来构建安全可信、可控可管、高效可扩展的全新网络体系。

在当前的TCP/IP协议中，IP地址在语义上具有双重含义，既代表了网络节点的拓扑位置又是节点的标识，即所谓的IP地址语义过载问题［1］。IP地址语义过载问题导致不利于支持移动性，IP地址过载还弱化了其作为位置标识的聚合特性，导致路由表规模过大，同时IP地址语义过载还带来了一些安全问题。

文献［2］提出网络可扩展性成为未来网络发展面临的主要问题。目前研究人员提出基于位置(Locator)与标识(Identifier)分离的思想来解决当前互联网的问题［3-5］。通过引入Locator和Identifier概念来分别表示位置与节点标识解决IP地址语义过载的问题，从而实现对路由表规模的有效控制。节点标识不会因为拓扑变化而改变，从而更好地支持多宿主、流量工程、主机移动性。位置与标识分离网络一般都是在路由器完成节点标识与位置信息的映射，然后，基于位置信息进行核心网络的路由。I-dentifier不支持全局范围路由，为了将报文转发到对端，需要将Identifier映射为其对应的Locator。可扩展的映射查询机制所面临的挑战主要包括如何控制查询响应延迟;如何控制映射表规模;如何减小路径查询长度等。本文基于 LISP［6］协议和 Chord［7］算法提出了一种新的映射方法—LISP-Chord。根据LISP协议的特点以及Chord算法在查询方面的优点，改进了文献［8］在路由表复杂度，节点加入退出开销以及路径查询长度相关指标。

1 相关工作

为了解决现有互联网名字空间在结构和解析机制方面的问题，本文提出了很多设计方案。为了完成2个地址空间的转换 ，LISP引入5种映射机制(NERD［9］，ALT［10］，EMACS［11］，CONS［12］，LISPMAP［8］)来将一个 EID(electronic identify)与一个Locator相关联，并维护Locator地址的可达状态。每个EID对应Identifier身份标识，RLOC对应Locator位置节点，两者都为IP地址表示。

NERD(a not-so-novel EID to RLOC database)提供了一种用于存放映射信息的网络数据库。NERD被分布在一组公开的服务器上，每个入口隧道路由器(ingress tunnel router，ITR)都需要存储整个映射数据库，报文的映射与转发在本地进行，避免了查询机制带来的延迟和报文丢失。但是当映射数据库规模很大时，每个ITR维护映射数据库的开销也很大;ALT(alternative logical topology)利用层叠网来完成映射服务，该机制将映射数据库分布式存储在出口隧道路由器(egress tunnel router，ETR)中，ALT负责转发查询和响应消息;EMACS(EID mappings multicast across cooperating systems)采用“目的端默认转发”的方式，由一组默认转发节点(路由器)来转发报文，该默认转发节点中存储的映射数据库规模大于 ITR。CONS(content distribution overlay network service)采用了“Push”和“Pull”相混合的映射服务方式。CONS机制中的ITR无需维护整个映射数据库，映射查询也无需经过层次结构，因此，减小了包延迟与丢失;LISP-MAP是一种基于CAN算法的位置与标识分离机制。该机制利用CAN算法进行查询映射关系。通过修改CAN算法，使该机制增加了映射数据库进行备份及节点加入退出的功能。本文基于LISP协议和Chord算法提出映射方法(LISPChord)。LISP-Chord映射查询机制采用 Chord算法，将端标识—路由位置(EID-to-RLOC)映射关系分布式的存储在映射服务器上进行资源查询，改进了路由表复杂度，节点加入退出开销以及路径查询长度相关指标。

2 LISP-Chord协议设计

LISP-Chord协议描述了一种基于网络的处理机制，在网络边缘设备上完成映射和报文处理，通过查询映射服务系统完成对Locator/ID的解析转换。LISP不需要改变主机和核心路由设施，采用映射＆封装和隧道的方式，由边缘网络路由器ITR/ETR来完成报文头中目的EID与目的RLOC的转换。EID用来标识终端主机身份;RLOC是边缘路由器地址，用于标识位置信息。ITR是源端主机的第一跳路由器，它接收源端主机发送来的数据包，该数据包源地址和目的地址为通信双方的EID。ITR将目的EID作为检索词，利用Chord算法，采用哈希(Hashing)把检索词分配到对应的节点上。Chord算法为每个节点和关键词分配m位的标识符。标识符长度m必须足够长，这样才能保证2个节点或者关键词不会哈希到同一个标识符上。每个节点哈希后的标识符由MapServer保存EID-to-RLOC映射关系数量来决定。而关键词的标识符可以哈希EID的IP地址且关键词的标识符为每个EID-to-RLOC映射的索引。关键词都保存在它的后继节点中，后继节点标识符大于等于关键词标识符的第一个节点，它是从k开始沿环顺时针方向的第一个节点。当查询映射时，用同样的哈希算法计算出每个关键字的标志符key，再根据关键字标识符知道该关键字标志对应信息的映射位置，从而能够快速定位资源的位置，并在服务器中查询到EID-to-RLOC映射关系。映射服务器返回目的终端RLOC，用于确定当前节点到目的端的边缘网络。随后ITR将该数据包进行封装报头并转发，目的地址为出口路由器的RLOC，而源地址为入口路由器的RLOC。ETR为目的终端最后一跳路由器，接收来自ITR的数据包并除去报头，再根据目的端EID地址将数据转发到目的节点。

2.1 新节点加入与退出规则

当一个新的节点想要加入Chord网络的时候，它必须与一个已知的Chord节点联络，请它为自己查找后继节点的IP地址。然后，新节点再请后继节点查找它的前驱节点。最后，新节点请求找到的这2个节点分别更新自己的记录，从而将新节点插入在它们之间。这样新节点就进入了Chord网络。在Chord环中，当节点失效后，所有指针表包含向指向节点指针的节点都必须把该节点替换成该节点的后继节点。

2.2 EID-to-RLOC映射注册过程

当一个终端主机要接入ITR时，它首先应从ITR获得一个映射关系，并注册该映射关系在网络中。由于这个目的，该网络需要一个映射关系的注册过程。映射注册过程如图1所示。

图1 EID-to-RLOC映射注册过程Fig.1 EID-to-RLOC registration process

步骤1 源端主机发送一个消息，该消息包括终端EID的IP地址。该EID-to-RLOC的映射关系通过哈希EID的IP地址索引。

步骤2 当ITR收到信息的时候，首先查询本地Cache缓存，是否已经保存了EID-to-RLOC映射关系的关键字，如果存在该映射则保留;若不存在该映射关系，则自动将该映射关系加入到Cache，并且ITR也将该映射关系发送到MapServer上。文献［13］对ITR设置了一个时间限制，若该映射过期，则自动删除。

步骤3 当MapServer接收到信息的时候，将该映射关系根据关键字添加算法加入到对应的节点上，并进行路由表的更新;如果终端主机离开ITR或者ITR检测到终端离开，ITR则发送一个消息到MapServer。在 MapServer中，移除该终端在 Chord中对应的映射，并进行路由表的更新。

2.3 EID-to-RLOC映射查询过程

当一个ITR收到一个查询对端RLOC地址的请求时，ITR首先查询本地Cache。若本地Cache保存了该EID-to-RLOC映射关系，则直接返回到ITR;若Cache中无该映射关系，需要在网络中进行查询找到EID-to-RLOC映射关系。该映射查询过程如图2所示。

图2 EID-to-RLOC映射查询过程Fig.2 EID-to-RLOC resolving process

步骤1 源端EID发送一个路由请求到入口隧道路由器ITR。该数据包包含源端与目的端EID的IP地址。

步骤2 当数据包到达ITR时，ITR检查本地缓存Cache是否保存了目的端EID-to-RLOC映射关系。如果Cache可以查询到该映射关系，则直接进行步骤7将该映射返回到ITR;若Cache中无该映射关系，则进行步骤3。

步骤3 当缓存Cache中没有保存该映射关系时，则ITR发送一个映射查询请求消息到MapServer。MapServer进行EID-to-RLOC映射查询。

步骤4 当MapServer收到请求时，将对端EID的IP地址作为关键字进行哈希，根据Chord算法在环上查询保存EID-to-RLOC映射的MapServer。

步骤5 该映射关系查询结束并进行返回。若该拓扑图有n个节点。当查询到该映射时所经过的节点的个数a≤n/2时，则该映射消息从原路返回;反之，该映射消息经过剩余节点返回。(该消息每经过一个节点时计数器进行加1)

步骤6 当MapServer查询到该映射关系时，将该消息回复给ITR。ITR将该映射信息存储在本地缓存中，并且在原数据包外面封装上LISP包头，该包头以对端主机ETR的RLOC为目的地址，以本地ITR的RLOC为源地址。封装结束后将该数据包发送至网络上，并最终到达对端的ETR。

步骤7 将在Cache中查询到的映射关系返回ITR。

2.4 查询时延分析

T1:源端EID发送一个路由请求到入口隧道路由器ITR时间，假定为T1=5 ms。

T2:ITR本地查询缓存Cache时间，假定为T2=5 ms。

T3:ITR发送消息到MapServer时间，假定为T3=5 ms。

T4:该时间为EID-to-RLOC映射查询过程中步骤4和步骤5，该时延由Chord网络决定，假定为T4。

T5:MapServer返回到ITR查询回复时间，假定T5=5 ms。

查询过程总共时延T=T1+T2+T3+T4+T5=16 ms+T4。T4的时延由 Chord环中查询MapServer的跳数决定。同时，MapServer的存储空间，转发消息能力也决定了Chord中查询的时延。

2.5 映射存储分析

每条映射EID-to-RLOC映射关系存储空间为100 Bytes［8］，假设每个 MapServer 的存储空间为 K Bytes，则每个MapServer保存映射关系数量为d=k/100条记录。每个节点哈希后的标识符由MapServer保存EID-to-RLOC映射关系数量来决定。假设d=1010时，则第1个保存d条映射关系的MapServer标识符为1010，则根据chord算法节点标示符顺时针方向依次增大原则，第2个节点标识符为2×1010，第3个节点标识符为3×1010，第n个MapServer标识符为n×1010(每个MapServer的存储空间大小相同)每个MapServer保存d条映射关系，每条映射关系对应一个EID的IP地址，同时每个ITR/ETR也对应一个IP地址。则MapServer的数量为EID数量的d倍。当Chord网络中有n个MapServer时，则可以存储EID-to-RLOC映射关系的数量即EID的数量N=d×n个。

在Chord中，节点并不需要知道所有其他节点的信息。每个Chord节点只需要知道其他节点的少量“路由”信息。在由n个节点组成的系统中，每个节点只需维护其他O(lb n)［7］个节点的信息。每次查找平均跳数为(1/2)×(lb n)［7］。当节点加入或者离开系统时 ，Chord需要更新路由信息 ，每次加入或者离开需要传递O(lb 2n)［7］条消息。

3 仿真分析

每个MapServer存储映射关系数量由其存储空间决定。假设每个MapServer存储空间为K Bytes，且存储d条映射记录。因为每个MapServer的存储空间较大，所以，较小数量的节点就可以包含d×n个映射关系。仿真设为4至200个节点。本文通过路由表复杂度，节点加入退出开销以及路径查询跳数3个方面将LISP-Chord与 LISP-MAP［8］方法进行比较。

第1组实验仿真了由4至200个MapServer节点组成的Chord环中LISP-Chord方法与LISP-MAP方法路由表复杂度的比较，仿真结果如图3所示。

图3 路由表复杂度Fig.3 Complexity of routing table

随着节点数目的增加，LISP-MAP方法中路由表复杂度保持不变;而LISP-Chord方法的路由表复杂度上明显较低。

第2组实验仿真了由4至200个MapServer节点组成的Chord环中LISP-Chord方法与LISP-MAP方法节点加入退出开销的比较，仿真结果如图4所示。在4至200个节点时，LISP-MAP方法节点开销复杂度保持不变，但是开销复杂度明显大于LISPChord方法。

图4 节点加入退出开销Fig.4 Cost of the node joining and quiting

第3组实验仿真了由4至200个MapServer节点组成的Chord环中LISP-Chord方法与LISP-MAP方法路径查找长度比较，仿真结果如图5所示。随着节点数量增加，2种方法的查询跳数都在增加，但是在4至200节点内，LISP-Chord方法路径查询跳数较LISP-MAP有明显降低。

图5 查询跳数Fig.5 Number of lookup hops

4 结论

本文以LISP协议为基础，针对LISP-MAP路由表复杂度、节点加入退出开销较大且路径查询跳数较多的缺点，提出了基于LISP协议的映射查询方案LISP-Chord。该方案以Chord算法为核心，将MapS-erver组成Chord网络进行位置与标识分离映射的查询，并且优化了映射返回路径选择。仿真结果表明，本文提出的LISP-Chord协议在路由表复杂度、节点加入退出开销和路径查找长度方面较原有的LISP-MAP方案都有较大改进。

［1］钱华林，鄂跃鹏，葛敬国，等.双层IP地址空间体系结构［J］.软件学报，2012，23(1):97-107.QIAN Hualin，E Yuepeng，GE Jingguo，et al.Dual IP Address Spaces Architecture［J］.Journal of Software，2012，23(1):97-107.

［2］刘韵洁.三网融合与未来网络的发展［J］.重庆邮电大学学报:自然科学版，2010，22(6):693-697.LIU Yunjie.Development of net work convergence and future internet［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2010，22(6):693-697.

［3］MICHAEL M， MATTHIASH， MICHAELHöfling.FIRMS:A Mapping System for Future Internet Routing［J］.IEEE Journal on Selected Areas in Communications，2010，28(8):1326-1331.

［4］LUO Hongbin，ZHANG Hongke，QIAO Chunming.Effcient Mobility Support by Indirect Mapping in Networks With Locator/Identifier Separation［J］.IEEE Transactions on Vehicular Technology，2011，60(5):2265-2279.

［5］LORAND J，ALBERT Ca-A，FLORIN C，et al.LISPTREE:A DNS Hierarchy to Support the LISPMapping System［J］.IEEE Journal on Selected Areas in Communications，2010，28(8):1332-1343.

［6］MEYER D.The Locator Identity Separation Protocol(LISP)［J］.The Internet Protocol Journal，2008，11(1):23-36.

［7］STOICA I，MORRIS R，KARGER D，et al.Chord:A Scalable Peer-To-Peer Lookup Service for Internet Applications［C］//Proceedings of ACM SIGCOMM.San Diego，CA，USA: ［s.n.］，2001:149-160.

［8］LEAR E.NERD:A Not-so-novel EID to RLOC Database［EB/OL］.(2008-01-23)［2012-12-22］.http://tools.ietf.org/html/draft-lear-lisp-nerd-03.

［9］FARINACCI D，FULLER V，MEYER D.LISP Alternative Topology(LISP-ALT) ［EB/OL］.(2011-11-06)［2012-12-22］.http://tools.ietf.org/html/draft-ietf-lisp-alt.

［10］BRIM S，FARINACCI D，MEYER D J.EID Mappings Multicast Across Cooperating Systems for LISP［EB/OL］.(2007-11-09) ［2012-12-22］.http://tools.ietf.org/html/draft-curran-lisp-emacs-00.

［11］BRIM N，CHIAPPA D，FARINACCI V，et al.Lewis.ISP-CONS:A Content distribution Overlay Network Service for LISP［EB/OL］.(2008-04-09)［2012-12-22］.http://tools.ietf.org/html/draft-meyer-lisp-cons-04.

［12］LUO Hongbin，QIN Yajuan，ZHANG Hongke.A DHTBased Identifier-to-Locator Mapping Approach for a Scalable Internet［J］.Parallel and Distributed Systems，IEEE Transactions on，2009，20(12):1790-1802.

［13］MATHY L，LANCASTER U.LISP-DHT:Towards a DHT to map identifiers onto locators［EB/OL］.(2008-11-9)［2012-12-22］.http://conferences.sigcomm.org/co-next/2008/CoNext08_proceedings/ReArch08Papers/1569143769.pdf.