2. 北京邮电大学 网络体系构建与融合北京市重点实验室, 北京 100876
内容中心网络路由的研究主要关注利用转发信息库端口来获取到达服务器的最优路径，路由路径外的节点缓存中内容无法得到充分利用.而利用多个转发信息库端口的多径路由虽可对缓存充分利用，但会带来冗余传输.针对这些问题，提出了一种基于内容轨迹的多径路由策略，利用内容轨迹将兴趣报文引导至原有路由表路径外的缓存处，使兴趣报文在到达服务器前搜索更多缓存，增加网内缓存命中率，减小服务器负载和兴趣报文平均跳数，并将多径路由冗余控制在一定范围内.仿真结果表明，基于内容轨迹的多径路由策略相对现有策略服务器负载降低约10%，且在服务器较远的场景下可有效降低请求平均跳数.相对于单径路由，基于内容轨迹的多径路由策略将网内缓存命中率提升了约20%；相对于多径路由冗余降低10%以上，且具有相近的网内缓存命中率.
2. Beijing Key Laboratory of Network System Architecture and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China
Current researches on content centric networking routing mainly focus on selecting the best routing path from forwarding information base (FIB). The path leads the requests to the server, so only the on-path caches are currently used, which results in low utilization of the in-network caches. More caches can be exploited if more FIB faces are used for multipath routing, but it will bring a lot of redundancies. To solve these problems, a content trace multi-path routing (CTMR) scheme is proposed. In this scheme, Interest packet is sent to the caches along with the traces of the former Data packet. Therefore, the Interest packets are routed to the in-network cache resources before they routing to the server, the utilization of the in-network caches is increased with a little redundancy, while the server load is decreased. Simulation shows that the CTMR decreases the server load about 10% and reduces the mean hops compared with the existing schemes. The cache hit rate in CTMR is increased about 20% relative to the single path routing. The redundancy in CTMR is reduced by more than 10% with the similar cache hit rate relative to the multipath routing.
在以内容获取为主体的互联网中，请求通过网络直接访问服务器，使服务器的负担加重，如视频直播业务.目前的解决方案是应用多服务器、负载均衡、内容分发等技术.在此背景下，内容中心网络[1](CCN, content centric networking)在其网络节点中加入存储功能，使节点成为内容服务的重要组成部分，而对CCN路由策略的改进可以更高效地利用节点资源为用户提供服务. CCN的路由从传统的端到端转化为端到内容的路由，当用户请求内容时发送包含该内容名的兴趣包，若缓存了该内容的中途节点或服务器收到兴趣包，则返回匹配的内容包. Shanbhag等[2]给出了基于蚁群的内容位置信息搜索策略，使转发信息库(FIB，forwarding information base)只保留一个端口，以单路径方法完成路由. Khan等[3]利用兴趣包传递FIB中全部端口时延信息，没有关注路径外的缓存资源及网内缓存的利用率.目前CCN路由基于其节点FIB，使兴趣包路由到服务器，只有在FIB路径上的缓存可以利用，而路径外的缓存未能参与响应请求.这导致了网内节点缓存的低利用率.当FIB表中的端口被全部使用时，虽能带来缓存使用率的提升，但也带来大量数据包冗余传输.本研究期望充分利用CCN多径路由特性，找到一种既能提高网内缓存命中率，又可以控制冗余传输的路由策略.基于以上目的笔者提出了基于内容轨迹的多径路由策略(CTMR, content trace multi-path routing)，并通过了仿真验证.
1 内容轨迹路由的基本思想Jacobson等[1]设计了CCN节点转发模型，给出了节点中内容存储库(CS, content store)、待定兴趣表(PIT, pending interest table)以及FIB的工作原理和查找顺序. CCN多径路由是指从FIB表中的所有或部分端口将兴趣包转发出去，存在以下问题：1) 缓存只发生在指向服务器路径上的节点中，导致错过附近的资源；2) 服务器可能远离请求者；3) 指向最近服务器的路径有限，许多可用缓存未被访问.而且节点缓存容量远小于全网内容总量[4]，因此需要充分地使用网内缓存，将请求快速准确地引导至缓存内容的网内节点上.基于上述原因，笔者提出基于内容轨迹的多径路由策略(CTMR, content trace multi-path routing)，将更多的请求引导至网内节点上，提高网内缓存的利用率.在CTMR中，需要记录内容包的轨迹，使兴趣包能够沿着之前内容包的轨迹找到其匹配的内容缓存.
如图 1(a)所示，网络远离内容服务器S，一个内容块从v1出发，最终到达v6和v8，内容的路线是v1—v4—v5—v6和v1—v4—v5—v8，假设内容轨迹上的所有节点最初都能缓存此内容，在一定时间后，由于缓存的替换，v1、v4和v5的内容缓存被替换.这时一个新的同名兴趣包从v7发出请求此内容.在原始CCN路由(CCNR, CCN routing)策略中(见图 1(b))，如果采用多径路由，v7会将兴趣包沿着路线1和2同时向服务器路由；或者采用单径路由只沿路线1路由.但无论哪种路由方式，中途都不会遇到内容缓存，最终只能把兴趣包路由到远端的内容服务器.如图 1(c)所示，CTMR中节点记录前一次内容经过的轨迹，下次路由时首先沿着内容经过的轨迹路由，把兴趣包转发到前一次内容经过的节点上. v7把兴趣包交付到v5，在v5上，兴趣包遇到内容轨迹，开始尝试向v4、v6和v83个方向搜索，最终在v6和v8上命中.由PIT表的工作原理，v5可以保证有且只有一份内容传输到v7.本次内容传输完成后留下新的内容轨迹供下次的相同请求使用.
|
图 1 CCNR与CTMR策略 |
CTMR需要节点建立一个多径搜索表(MST, multi-path search table)，MST条目包含3个表项：1) 命名(Name)，代表内容命名，如k表示内容包C(k)的命名；2) 潜在可用端口(PF, potential faces)，定义了一个关于内容命名的端口集合F，记录内容包的进出节点的端口fi，为随后的同名兴趣包路由端口；3) 本MST条目上一次更新时刻(UT, use time)，此表项为MST条目的删减提供依据.
CTMR策略首先在无内容缓存条件下计算节点到内容服务器的最短路径，初始化FIB表. FIB表中的端口在CTMR策略中并不是最优端口，但通过此端口一定会获得所请求的内容.假如MST路由失败，重发的请求将由FIB路径重新路由，这确保了路由的可靠性和稳定性.
2.1 MST条目的生成内容包C(k)到达当前节点时，查找PIT中是否有匹配命名k的条目.如果有，说明此C(k)是最快返回的，C(k)按照PIT中的L个端口转发.当前节点会缓存这个内容包，接着当前节点会记录内容包的命名k、到达端口fin和所有转出端口fouti，生成一个新的端口集合F′={fin, fout1, fout2, …, foutL}.通过fin关联的节点缓存如果可继续提供内容，一定会较快返回内容；通过fouti关联的节点一定是最新缓存此内容的节点，其缓存可用周期较长.此时查看MST表中是否有与命名匹配的条目，如果有，将其PF表项中的原集合F更新为F′，并将当前时刻tnow写入UT表项；否则，当前节点在MST中新建此命名条目(k, F′, tnow).最后，删除PIT条目.
MST条目建立后，F成为最可能找到且会较快返回内容的端口集.下一次到来的同名兴趣包会沿着由F中的端口组成的路径到达保留有缓存的节点.在最近最少使用(LRU，least recently used)缓存替换策略[5]中，节点最新缓存的内容一定是在当前所有缓存内容中最后一个被替换掉，设每个节点的缓存空间可缓存C个内容，请求的到达速率为每秒Y个，假设每个请求都成功得到内容，在到达的请求都不相同的情况下，会得到缓存在节点中存在的最短时间Tmin=C/Y，但是由于节点会收到相同内容的请求，所以，请求集中度高的内容缓存在节点中的时间要远大于Tmin.且按照MST路由相当于扩大了缓存搜索的范围，使得MST的有效性得到了更大的保证.
2.2 基于MST的路由兴趣包I(k)到达当前节点时，在节点内依次查询CS、PIT、MST和FIB.在没有遇到有匹配MST条目的节点时，兴趣包I(k)按照FIB中的端口向内容服务器转发.当I(k)在一个节点遇到关于内容C(k)的MST条目时，就开始沿着MST路径做内容缓存的搜索：首先查询CS表和PIT表，如果均未查到，开始MST表的查询.在MST查询过程中，先从Fk中删除I(k)到达的端口，之后以Fk中有无剩余元素为标准判断下一步的动作，过程见算法1.
算法1
Initialize: 1. Interest I(k) arrived in face fi
2.EntryCS(k) in CS does not exist
if EntryPIT(k) in PIT exist
add fi into EntryPIT(k)
drop I(k)
else
build EntryPIT(k) in PIT
then lookup MST
if EntryMST(k) in MST exist
if 
delete fi from Fk
if Fk=Ø then
delete EntryMST(k) in MST entry
build NData packet N(k)
forward N(k) to faces in EntryPIT(k)
delete EntryPIT(k)
else
forward I(k) to faces Fk－{fi}
end if
else
forward I(k) to faces in Fk
end if
else
forward I(k) to face in FIB
end if
end if
节点为每一个经过的内容保留一个MST条目. MST条目有一个有效期，如果MST条目在有效期内没有被使用，这个MST条目将被删除.可为MST条目设置有效期阈值Tmst，如果在Tmst时间内有内容包经过此节点，那么当前MST条目的UT被更新为本次时刻tnow，有效期延长，其结束时刻为t = t now+Tmst.在极端情况下，MST路径上所有匹配的内容在Tmst内都被替换，兴趣包沿着MST路径找不到所需的缓存，这时，引入一个特殊的通知报文NData保证路由继续执行. NData包含当前未请求到内容的命名和一个特殊的标志，节点通过此标志与普通内容包加以区分. NData的作用是通知节点从MST中删除NData到达的端口，放弃等待内容包从此端口返回，其传输路径与普通内容包一样，由PIT条目维护，而PIT条目被NData使用后也会被删除.算法2给出了节点在已有MST条目情况下对NData处理的过程.在MST条目不存在的情况下节点收到NData，如果有相应的PIT条目，则按照PIT条目转发NData；如果没有PIT条目，则丢弃NData包.
算法2
Initialize: NData packet N(k) arrived in face fi
if fi in Fk
delete fifrom Fk
if Fk=Ø then
delete EntryMST(k)
forward N(k) to faces in EntryPIT(k)
delete EntryPIT(k)
else
drop N(k)
end if
else
drop N(k)
end if
节点无论收到兴趣包还是NData，都表明这些包的到达端口外已经不存在可用的内容，MST条目会删除这些端口，保证下次路由不受影响. MST以条目中端口集合F是否为空为依据，判断MST条目是否需要删除.如果F=Ø，说明节点从F中所有端口都收到了兴趣包或NData包，已经不可能找到内容，则删除MST条目.
节点收到兴趣包后遵循MST的优先级高于FIB的查表顺序，如果节点中存在相应MST条目，将不再查找FIB表.如果在MST路径途中没有命中，会一直路由兴趣包到MST路径的最后一个节点.在所有MST支路的末端节点都没有找到缓存的情况下，由这些末端节点产生的NData将整个MST路径删除，并最终将一个NData发送到请求节点，请求节点重新发送兴趣包.这时MST路径已经不存在，重发的兴趣包会沿着FIB路径到达内容服务器.这限制了在一次路由中MST和FIB频繁交替使用，避免了不同表间切换带来的路由混乱.另外，PIT规则保证了兴趣包在路由过程中不会产生环路.所以，内容包回传时生成的MST路径也不存在环路.
CTMR的开销为节点开销和通信开销.节点开销为新建MST表的存储以及算法的运行，由于MST表结构简单，存储空间开销不大；另外CTMR是由包驱动，没有复杂计算，计算开销是可以接受的.另一方面CTMR增加了NData包，该包没有载荷，传输NData的数据量很小，且NData是事件触发生成和传输的，不是周期性发送，所以正常通信以外的通信开销很少，不会影响整个网络性能.
3 仿真分析3.1 性能指标考虑4个仿真指标：网内缓存命中率φe；内容服务器负载γd；兴趣包平均跳数η；冗余命中率φr.定义N为网络中产生兴趣包总数，M为节点的总数；定义K为每个节点的缓存命中次数，由于是多路径路由，K由2部分组成，分别是有效命中次数KE和冗余命中次数KR，K=KE+KR；内容服务器的命中次数表示为KS.
网内缓存命中率定义为
服务器负载γd=KS/N，表示服务器处理兴趣包占总兴趣包数量的比例.由于CCN的请求聚合与多路径特性，请求可能在网内聚合，也可能从多路转发到达服务器，所以φe与γd的和不一定为1.
平均跳数定义为
冗余命中率定义为
仿真建立了16节点的随机拓扑，在网络之外设置一个服务器与网络连接.在CCNR中使用CCNR-S(使用一个最优状态FIB端口)及两种多径路由方法CCNR-M-all(使用全部FIB端口[1])和CCNR-M-2(使用2个FIB端口[5])3种策略来和CTMR对比.服务器存储500种内容.兴趣包由边缘节点产生，速率为100个/秒，生成规则分别服从齐普夫(Zipf)分布和随机分布. Zipf分布的参数初始化值分别是：漂移量q =0.7，幂律指数s =0.7.缓存决定策略为“收到即存”(Always)，缓存替换策略为LRU[5].设服务器到网络的跳数为5，节点缓存容量与总内容种类比例大小从2%~20%，仿真时间120 s.结果由图 2、图 3、图 4和表 1所示.
|
图 2 缓存命中率结果 |
|
图 3 内容服务器负载结果 |
|
图 4 兴趣包平均跳数结果 |
|
表 1 冗余命中比例结果 |
由图 2可看出相同缓存容量的情况下，CCNR-S策略的网内缓存命中率最低，CCNR-M-all和CTMR结果相近，CCNR-M-2低于CTMR且高于CCNR-S.这体现了CCN缓存资源的重要特性，兴趣包对更多的缓存资源搜索会带来网内缓存命中率的显著提升，这也是CTMR策略解决的重要问题.而CCNR-M-all虽然搜索了比CTMR更多的缓存资源，但是其缓存命中率未体现出与CTMR的明显差别，这也说明CTMR的缓存搜索效率是有保证的.对于兴趣包按不同流行度分布的情况，φe的提升趋势不变.在流行度服从Zipf分布时，由于缓存替换发生的概率更小，所以φe在相同缓存容量的情况下略高于随机分布.
图 3给出了不同策略对γd的影响对比结果，可以看出CTMR对γd的影响明显. CTMR将大量的兴趣包引导至网内节点，所以降低了服务器的负载.而CCNR的3种策略中，其路由的目的节点都是内容服务器，无论路径数量是否受限，每次请求过程中一旦在中途节点不能命中内容缓存，兴趣包就会被路由到内容服务器，导致内容服务器承担了大量的工作，尤其是缓存较小的情况.
图 4显示了η的变化规律.在较小的缓存容量下，CTMR可以使兴趣包在附近节点的缓存命中内容，η值较低，体现了CTMR邻近缓存的优势. CCNR-S、CCNR-M-2与CTMR均明显体现了η减小的趋势，因为随着缓存容量的增加，更多兴趣包可以在附近命中缓存.在缓存容量增加到一定程度的情况下，出现了CCNR-S的结果要略低于CTMR的情况，因为此时兴趣包不需要到更远的节点搜索内容，在本地或更近的节点即可命中，而CTMR中多支路冗余传输的兴趣包跳数会占一定比例，导致兴趣包的总跳数下降较CCNR-S慢. CCNR-M-2比CCNR-S多搜索一条路径，所以其η要高. CCNR-M-all存在的支路比CTMR更多，所以冗余传输的兴趣包也更多，不会明显减少η的值. η的变化趋势在2种分布中是一致的，Zipf分布产生的兴趣包聚合度更高，部分兴趣包被PIT聚合，所以η在相同缓存容量下低于随机分布.
在CCNR-S中不会产生冗余的兴趣包传输，所以也不会出现冗余的缓存命中. 表 1给出了3种多径路由策略中由兴趣包冗余传输引起的冗余网内缓存命中的比例. CCNR-M的两种策略冗余明显高于CTMR.由于CCNR-M-2限制了路径数冗余略少于CCNR-M-all.可见CTMR有效地控制了冗余的兴趣包传输，减少了冗余的网内缓存命中.
4 结束语针对内容中心网络中如何提高网内节点缓存资源利用率的问题，提出了CTMR路由策略，将前一次内容包在网内节点的出入端口记录在一个新的结构MST中，在下一次相同命名的兴趣包到达时首先向MST中记录的端口路由.以较少的冗余代价获得网内缓存利用率的大幅提升，降低了服务器负载.在一定的条件下降低了兴趣包命中缓存时的平均跳数.仿真结果表明各项指标均有提升.
| [1] | Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[C]//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies. New York: ACM, 2009: 1-12. |
| [2] | Shanbhag S, Schwan N, Rimac I, et al. Soccer: services over content-centric routing[C]//ACM SIGCOMM Workshop on Information-Centric Networking. New York, USA: ACM, 2011: 62-67. |
| [3] | Khan A Z, Baqai S, Dogar F R. QoS aware path selection in content centric networking[C]//International Conference on Communications. Piscataway, USA: IEEE, 2012: 2645-2649. |
| [4] | Carofiglio G, Gallo M, Muscariello L, et al. Modeling data transfer in content-centric networking[C]//Proceedings of the 23rd International Teletraffic Congress. Piscataway, USA: IEEE, 2011: 111-118. |
| [5] | Rossi D, Rossini G. Caching performance of content centric networks under multi-path routing (and more) [R]. Technical Report, Telecom Paris Tech, 2011. |