以最大链路流量最小化为目标的内容中心网络(Content-Centric Networking，CCN)缓存节点放置启发式方法

《IEEE Access》：Heuristic Approaches for Cache Node Placement in Content-Centric Networking Under Maximum Link Traffic Minimization

　　

本文提出面向内容中心网络(Content-Centric Networking，CCN)在最大链路流量最小化目标下的缓存节点放置启发式方法。该研究建立在研究人员前期提出的精确整数线性规划(Integer Linear Programming，ILP)模型基础上，该模型联合建模路由与缓存决策，但在大规模网络中计算开销过高。为解决此局限，研究人员开发了可扩展启发式算法，以远低于ILP的计算时间逼近最优解。研究人员引入四种启发式方法，包括两种基于线性规划(Linear Programming，LP)的局部搜索算法2Swap与GreedySwap（其利用ILP的LP松弛的分数解），以及两种代理(proxy)启发式方法Population-Weighted Closeness（PWC）与Population-Weighted Betweenness（PWB）（其使用人口加权中心性度量估计缓存效用且无需求解任何优化模型）。在四种网络拓扑上的实验评估表明：LP类启发式结果与ILP最优值的差距保持在0–6%，同时计算时间降低约40×至160×以上；与代理启发式相比，LP类启发式在所有设定下均产生更低的最大链路流量；这些结果表明所提启发式可为实际CCN部署提供有效且可扩展的缓存节点放置方案。

本文发表在《IEEE Access》。研究背景方面，内容中心网络（CCN，Content-Centric Networking）是从以主机为中心通信向以内容为导向检索转变的新型网络架构，其通过内容名义直接命名、网内缓存机制提升可扩展性并降低时延。每个CCN节点维护转发信息库（FIB，Forwarding Information Base）、未决兴趣表（PIT，Pending Interest Table）和内容存储（CS，Content Store），除了CS中 opportunistic缓存外，许多部署还会选择具有增强存储能力的缓存节点。缓存节点放置是关键设计问题，受拓扑、人口分布、内容流行度和路由行为共同影响。传统随机放置或简单聚类未显式考虑流量集中，可能导致关键链路高负载；基于中心性（如介数中心性（BC，Betweenness Centrality））的方法只捕捉拓扑重要性，未考虑流量体积、内容源与拥塞传播，常导致缓存过度集中在拓扑中心区域，不能真正缓解拥塞；基于整数线性规划（ILP，Integer Linear Programming）的优化可联合建模路由、需求和缓存决策并以最小化最大链路流量等为全局目标求得最优放置，但组合复杂度高，仅适用于中小规模拓扑，在大规模实际网络中求解成本不可接受。因此研究人员需要开发既保留ILP流量感知特性又具计算效率的缓存节点放置算法。

为开展研究，研究人员用到的主要关键技术方法包括：基于前期工作中以最小化最大链路流量v并次最小化总流体积为目标的分层目标整数线性规划（ILP，Integer Linear Programming）模型，该模型在网络图G=(V,E)下定义缓存预算K、内容集C、节点请求量D(p)、内容源指示s_p^c、二进制缓存决策变量y_p、链路流变量x_ij^c、有效请求R(c,p)=D(p)(1?s_p^c)(1?y_p)，并施加流守恒约束、最大链路流量约束∑_c∈Cx_ij^c≤v及缓存预算∑_p∈Vy_p≤K；在此基础上构建LP松弛（LP relaxation）将y_p松弛为连续值?_p∈[0,1]，以其分数值作为节点重要性排名；提出两类各两种启发式：第一类为LP基局部搜索启发式2Swap与GreedySwap，先用LP松弛得到分数值选前K节点初始化缓存集，然后2Swap遍历当前缓存集与非缓存集的两两交换（2-swap）并接受降低最大链路流量的交换，GreedySwap每轮遍历所有单节点交换选取降低最大链路流量最多的交换并迭代至无改进，且支持增量更新受影响路径的链路计数器以降低开销；第二类为代理基启发式Population-Weighted Closeness（PWC，按PWC(p)=∑_u∈V,u≠pD(u)/d(u,p)评分）与Population-Weighted Betweenness（PWB，按PWB(p)=∑_s≠tD(s)σ_s,t(p)/σ_s,t评分），仅需全对最短路径与加权中心性计算，无须优化求解；评估采用COST239、JPN12、NSFNET、JPN25四种拓扑，内容数|C|=1,2,3，缓存预算K=1至5，节点请求量D(p)设为人口数的1/10000，内容源枚举所有分配取平均，使用IBM ILOG CPLEX 12.9.0求解LP/ILP，性能度量为平均最大链路流量相对ILP的差距(%)与计算时间加速比，并进行LP引导初始化与随机初始化的消融实验。

研究结果如下：

SECTION I. Introduction：研究人员指出CCN架构下缓存节点放置对流量分布、时延与可扩展性的重要影响；传统中心性方法（如BC）仅反映拓扑结构重要性，未考虑流量、内容源与需求分布，易导致缓存集中于拓扑中心、链路拥塞转移；ILP可全局最优最小化最大链路流量但计算昂贵；因此研究人员提出LP基启发式（利用LP松弛分数解全局排名+局部搜索）与代理基启发式（人口加权中心性，无优化求解），以兼顾精度与效率。

SECTION II. Related Works：研究人员综述了缓存放置研究，指出BC等中心性方法忽视流量体积与流交互，跳数最小化方法不针对链路拥塞，ILP最优但难扩展，已有启发式不能与ILP最优一致逼近；本文创新点在于结合LP松弛提取流量感知节点排序再局部搜索修正，以及将人口加权与中心性结合作为轻量代理方法，填补了流量感知最优与可扩展启发式间的空白。

SECTION III. Maximum Link Traffic Minimization Model for Cache Node Placement：研究人员形式化网络为无向图G=(V,E)，定义ILP模型：分层目标min Mv+∑_c∈C∑_(i,j)∈Ex_ij^c（M为大常数优先最小化v），有效请求R(c,p)=D(p)(1?s_p^c)(1?y_p)，流守恒下界R(c,p)?L(s_p^c+y_p)≤∑_j:(p,j)∈Ex_pj^c?∑_j:(j,p)∈Ex_jp^c与上界∑_j:(p,j)∈Ex_pj^c?∑_j:(j,p)∈Ex_jp^c≤R(c,p)，最大链路流量约束∑_c∈Cx_ij^c≤v ?(i,j)∈E，缓存预算∑_p∈Vy_p≤K；该ILP可提供最优基准但规模大时计算昂贵。

SECTION IV. Heuristic Approaches for Cache Node Placement：研究人员提出LP基启发式先解LP松弛得?_p∈[0,1]作为排名，2Swap初始化选前K高分节点然后迭代两两交换(cache?non-cache)若降v则接受；GreedySwap初始化同样，每轮试所有单节点交换选降v最多者迭代至收敛，可用增量更新受影响的路径链路计数器；代理基启发式PWC按PWC(p)=∑_u≠pD(u)/d(u,p)算分选前K，PWB按PWB(p)=∑_s≠tD(s)σ_s,t(p)/σ_s,t算分选前K；分数或中心性同分时按节点索引升序保证确定性。

SECTION V. Performance Evaluation：研究人员在COST239、JPN12、NSFNET、JPN25上取|C|=1,2,3、K=1~5、D(p)=pop(p)/10000，枚举所有内容源分配求平均；结果显示LP基启发式（2Swap、GreedySwap）相对ILP的最大链路流量差距普遍在0–6%（如JPN12上GreedySwap为<1%、NSFNET上多为0–0.04%、JPN25上为0.31–5.64%），计算时间加速比约40×–160×（LP求解占主导，局部搜索少量迭代）；代理基启发式PWC差距约40–55%，PWB在对称拓扑差距>200%；计算时间上代理基更快（PWC、PWB可达70×–100×+加速比）；LP引导初始化显著优于随机初始化（GreedySwap+LP引导收敛快、避局部最优）；在稳定需求下LP分数排名可复用，仅需增量局部搜索适应需求漂移；PWB因过度集中缓存在核心节点引起流量集中与瓶颈，LP基显式平衡全网流；所有启发式确定性，结果可复现；敏感性与异质需求（Zipf等）下相对排序不变。

SECTION VI. Conclusion：研究人员总结所提四种启发式：LP基（2Swap、GreedySwap）接近ILP最优（差距0–6%）且提速40×–160×，适合离线规划与周期重配；代理基（PWC、PWB）无优化、速度更快（加速比更高）但最大链路流量差距较大，适合极端受限场景；LP基启发式在精度与扩展性间提供实用折衷；未来可将流量感知放置与分散式编码缓存（decentralized coded caching）结合，联合优化缓存位置与编码内容分布以进一步降峰链路流量。

讨论部分总结：研究人员讨论明确ILP虽为最优基准但指数复杂度与大网络高时耗限制实用；LP松弛分数值?_p主要由结构流模式与需求分布驱动，在需求适度变化（比例缩放、渐变、Zipf扰动）下高影响节点排序稳定，可跨周期复用LP排名仅做增量GreedySwap以适应动态环境，显著降低开销；LP引导初始化提供高质量全局流量地图，对称稠密网（如COST239）分数近整数最优使GreedySwap极少迭代即匹配ILP，异构网（如JPN25）可避免随机初始化陷局部最优；GreedySwap一般4–10轮收敛，适合运营网周期重配，动态下可从当前配置做触发式局部交换；超大网（|V|>100）若LP成为瓶颈可用代理基或复用旧LP分数；纯拓扑中心性（如PWB）过度集中缓存于核心hub引发瓶颈（JPN25上PWB最大链路流量是GreedySwap的约3倍：1.88×10⁷vs 5.80×10⁶），PWC提供极速但精度中等；所有评估同硬件同求解器设置，枚举内容源分配平均消偏，启发式确定可复现，异质人口与Zipf需求下相对结论稳健；LP基优势源于全局流交互平衡而非特定拓扑抽象；结果发表于《IEEE Access》。