本发明公开了一种基于联合缓存架构的网络内视频缓存方法。其实现方案是：在采用联合缓存架构的网络中，预留一部分比例为α的总缓存空间来缓存最受欢迎的视频，并利用剩下空间保证网络缓存所有视频。并且，视频缓存完成后，根据视频请求模式和链路状态信息的动态变化，为视频请求者寻找最佳视频源节点。本发明有效解决了网络内视频缓存的问题，能够保证移动网络内视频数据的可靠、高效存储和调用，节省了系统带宽，并有效降低了网络时延成本。
1.一种基于联合缓存架构的网络内视频缓存方法，其特征在于，包括以下步骤：步骤一：在所有节点缓存特定的视频；
在基于联合缓存架构的网络中，预留一部分比例为α的空间缓存用户请求最多的视频；
然后利用剩下的空间保证网络可以缓存所有视频；若节点仍有剩余空间，则继续在每个节点中缓存视频，填满所有节点缓存空间；寻找一个最佳α，使网络的总缓存命中量达到最大；
视频缓存完成后，当一个节点i接收到对视频k的请求时，节点i先在本地缓存中寻找视频k，如果有则直接将视频k发送给用户；否则在其他网络节点的缓存中寻找视频k；当存在多个其它网络节点都缓存有视频k时，根据视频请求模式和链路状态信息的动态变化，为视频用户寻找一个最佳的视频源节点。
2.根据权利要求1所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤一中在所有节点缓存特定的视频：M为网络中所有节点i的集合，N为所有需要缓存的视频k的集合，Sk为视频k的大小， 表示节点i中收到用户请求为视频k的概率，其中 可通过历史统计计算或预测得到； 表示节点i的缓存中是否有视频k， 表示节点i的缓存中没有视频k， 表示节点i的缓存中有视频k，即 表示总缓存空间的缓存命中量，
缓存命中量越大表示缓存空间中请求概率高的视频越多，资源利用率越高，系统更高效；
在存储空间和链路带宽受限的情况下，通过合理地在各个网络节点中缓存视频数据，使本地网络节点的总缓存命中量达到最大，即 取得最大值；节点缓存容量受限，Di为节点i的缓存容量，则缓存视频时必须满足
3.根据权利要求2所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤一在所有节点缓存特定的视频中的(1-1)缓存请求概率最高的视频：将网络中所有节点i的总缓存容量 中预留比例为α的部分 来缓存每个网络节点中请求概率最高的视频，假设α为一个给定的数值；用Pi表示节点i缓存的视频集合，Di′表示节点i的剩余缓存容量；
对于集合M中的每个节点i，初始化集合Pi为空集，令 为总容量中比例为α的部分容量，初始化集合W＝{(i,k)|i∈M,k∈N}为所有可能的(i,k)配对的集合，初始化节点i的剩余缓存容量Di′＝Di；
当D大于0且集合W不为空集时，令 如果 即视频k*的大
小不大于节点i*的剩余缓存容量，则令 即把视频k*缓存到节点i*中，同时将用来缓存请求概率最高视频的部分容量D和节点i*的剩余缓存容量 均减去视频k*的大小Sk*；令W＝W-{(i*，k*)}，即把集合W中的(i*，k*)配对去掉，同时令 表示节点i*的缓存中有视频k*；
如果D大于0且集合W不为空集，则继续缓存视频；如果D等于0或者集合W为空集，则表示用来缓存请求概率最高视频的空间已经分配完，或者网络中所有的节点均分配到所有的视频；
缓存视频结束后，得到每个节点i中缓存视频的集合Pi以及全部Pi的并集N0，集合N0中的元素表示网络中任一节点缓存的视频，所有视频中请求概率最高的视频缓存完毕。
4.根据权利要求2所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤一在所有节点缓存特定的视频中的(1-2)保证缓存所有视频：令Nr表示网络中没有缓存的视频的集合，即 为了利用剩余的1-α部分空间实现所有视频全覆盖，并在保证缓存全部视频的前提下使缓存命中量 最大，则每个视频只需在所有网络节点中缓存唯一复本即可；
对于集合Nr中的每一个视频k，令Yk表示所有可以用于缓存视频k的节点集合，初始化Yk＝M；
在集合Yk中寻找一个使 取得最大值的节点i*，即 若视频k的大小Sk大于节点i*的剩余空间 则令Yk＝Yk-i*，即表示节点i*不可以用于缓存视频k；继续在集合Yk中寻找一个使 取得最大值的节点i*缓存视频，直到Yk变为空集；Yk为空集表示当前网络内没有节点具有足够的空间来缓存视频k，即网络无法保证缓存所有视频，则当前给定的α值是不合理的；
若Sk不大于节点i*的剩余空间 令Nr＝Nr-k，将视频k缓存到节点i*中，同时更新为 减去视频k的大小Sk；
5.根据权利要求2所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤一在所有节点缓存特定的视频中的(1-3)填满节点剩余空间：视频缓存完成后，各个节点i可能还有部分剩余空间；
Ni表示节点i没有缓存的视频的集合，Pi″表示节点i将要缓存的视频k的集合；在不超过节点i的剩余缓存容量的条件下，即 将使得 最大的视频加入集合Pi″中，同时将Pi″中的视频缓存到节点i中；
遍历集合M中的所有节点i，初始化集合Pi″为空集；
当Di′大于0且集合Ni不为空集时，令 即Ni中最受欢迎的视频；如果视频k*的大小Sk*不大于此时节点i的剩余容量Di′，则令集合Pi″＝Pi″∪k*，Ni＝Ni-k*，把视频k*缓存到节点i中，将节点i剩余容量Di′更新为Di′减去Sk*；如果视频k*的大小Sk*大于此时节点i的剩余容量Di′，令集合Ni＝Ni-k*，不缓存视频k*；
如果Di′大于0且集合Ni不为空集，则继续按照所述方法，给节点继续缓存视频；如果Di′等于0或者集合Ni为空集，则表示节点i的剩余缓存空间已经分配完，或者节点i已经缓存所有的视频，集合Pi＝Pi∪Pi″，得到节点i中缓存的全部视频；
遍历完集合M中的所有节点i后，此时所有节点的缓存空间都已经被填满，并得到全部k节点i和视频k对应的yi 值；记录每个节点的缓存分配结果，即每个节点缓存的视频集合Pi，并根据节点缓存空间分配结果得到缓存命中量 的值。
6.根据权利要求2所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤一在所有节点缓存特定的视频中的(1-4)寻找最佳分配方式：总缓存空间中用于缓存请求概率高的视频的空间比例α越大，缓存命中量也越大，则将缓存命中量 表示为α的一个函数H(α)，即选择一个更大的α能够提升系统的性能，避免网络无法缓存全部视频，采用二分法在[0,1]区间内寻找最佳α，在保证缓存全部视频的前提下，使得目标值H(α)取得最大值，为α值设置一个下界αl＝0，得到对应H(αl)的值；
若集合Yk为空集，表示当前α值不合理，即系统全部容量都无法保证覆盖全部视频，系统对容量不足的情况不作处理；
若集合Yk为空集，为α值设置一个上界αu＝1，得到对应H(αu)的值，如果没有缓存视频的集合Nr为空集，则表示用系统全部容量的α倍缓存的请求概率最高的视频即为所有的视频N，因此直接得到最佳α为1；
如果有缓存视频的集合Nr为空集，在αl和αu之间使用二分查找法，若H(αl)H(αu)，则令αu＝(αl+αu)/2，重新计算H(αu)，直到H(αl)＝H(αu)，此时得到的H(α)为最大。
7.根据权利要求1所述基于联合缓存架构的网络内视频缓存方法，其特征在于，步骤二中确定获取视频的最佳源节点：当一个节点i接收到对视频k的请求时，节点i先在本地缓存中寻找视频k，如果有则直接将视频k发送给用户，否则在其他网络节点的缓存中寻找视频k；当存在多个其他网络节点都缓存有视频k时，选择其中一个网络节点作为所请求视频k的最佳源节点；
把网络进行视频缓存的时间划分为若干个轮，每一轮持续时间为△t，在每一轮时间内，每个网络节点从用户端接收请求；
对于网络中的所有链路l，用fl表示链路l上的总的传输速率；用L(j,i)表示从节点j到节点i的路径；用ζl(·)表示已知的链路时延函数，是一个关于负载fl的单调递增函数，则表示从节点j发送一个单元的数据到节点i的时延成本；用Ri表示一轮时间内节点i中被请求但没有缓存的视频的集合；用rk表示视频k的传输速率；用Tk表示拥有视频k复本的所有节点的集合；用 表示所有节点获取视频的加权时延成本之和；
通过为每个视频k的请求选择最佳的视频源节点，使所有节点获取视频的加权时延成本之和达到最小，即使 取得最小值；
(2-1)建立本地负载表，网络中的路由器定期地将各条链路的负载信息，即传输速率报告给各个网络节点，每个节点接收报告后建立一个具有全部链路负载信息的本地负载表；
(2-2)根据本地负载表寻找最佳源节点，每轮时间△t结束时，网络节点i处理接收到的视频请求，假设收到对于视频k的请求，则合并节点i中对于视频k的全部请求；若节点i的本地缓存中无视频k，则节点i根据本地负载表获取每条链路的负载fl，由得到传输视频k到节点i时延成本最小的节点j*，其中每条链路l必须满足fl≤Cl，Cl表示链路l的容量，即该链路所允许的最大的传输速率；确定最佳源节点j*后，节点i向节点j*请求发送视频k；
(2-3)更新本地负载表，节点i向节点j*发送对于视频k的请求后，节点i和节点j*更新节点i和节点j*的本地负载表，将路径L(j*,i)经过的所有链路l的负载fl变成fl+rk，并将更新消息发送给网络中的路由器；路由器将更新消息广播给网络中的每一个节点，各个节点收到更新消息后更新本地负载表；
为节点i中的对视频k的请求找到了最佳的源节点j*，用户通过最佳源节点j*得到所请求的视频。
一种基于联合缓存架构的网络内视频缓存方法
技术领域
[0001] 本发明属于通信技术领域，尤其涉及一种基于联合缓存架构的网络内视频缓存方法。
背景技术
[0002] 随着移动互联网的迅速发展及在线视频内容的急剧增长,在网络内缓存视频时，提升终端用户体验以及降低用户费用便显得尤为重要。然而，由于互联网中视频数量和用户视频需求与有限的存储容量和链路带宽之间的矛盾，在网络内高效地缓存视频是一件比较困难的事情。
[0003] 当前存在的关于网络内视频缓存问题的解决方案的不足有：(1)依赖于静态配置和时间平均请求到达率，并不能有效地解决动态请求模式中出现的问题；(2)同时解决视频缓存问题和源节点选择问题，导致算法复杂度过高，且耗费时间较长，效率过低。
发明内容
[0004] 本发明的目的在于改进当前网络内视频缓存技术的不足，提出一种基于联合缓存架构的网络内视频缓存方法，让所有网络节点共同缓存用户所需的视频，从而使视频在存储容量和链路带宽受限的网络中传输的总成本最小。
[0005] 本发明提出的联合缓存架构，指的是一种网络中所有节点各自开辟一定的缓存空间，并共同缓存用户所需视频资源的架构。网络节点包括直接与用户基站相连的服务节点和与外界互联网相连的分组数据网络PDN网关，下面简称节点。
[0006] 为实现上述发明目的，本发明提出的技术方案是：
[0007] 一种基于联合缓存架构的网络内视频缓存方法，包括以下步骤：
[0008] 步骤一：在所有节点缓存特定的视频；
[0009] 在基于联合缓存架构的网络中，预留一部分比例为α的空间缓存用户请求最多的视频；然后利用剩下的空间保证网络可以缓存所有视频；若节点仍有剩余空间，则继续在每个节点中缓存视频，填满所有节点缓存空间；寻找一个最佳α，使网络的总缓存命中量达到最大；
[0010] 步骤二：确定获取视频的最佳源节点；
[0011] 视频缓存完成后，当一个节点i接收到对视频k的请求时，节点i先在本地缓存中寻找视频k，如果有则直接将视频k发送给用户；否则在其他网络节点的缓存中寻找视频k；当存在多个其它网络节点都缓存有视频k时，根据视频请求模式和链路状态信息的动态变化，为视频用户寻找一个最佳的视频源节点。
[0012] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤一中在所有节点缓存特定的视频：
[0013] M为网络中所有节点i的集合，N为所有需要缓存的视频k的集合，Sk为视频k的大小，λik表示节点i中收到用户请求为视频k的概率，其中λik∈[0，1]，可通过历史统计计算或预测得到；yik表示节点i的缓存中是否有视频k，yik＝0表示节点i的缓存中没有视频k，yik＝1表示节点i的缓存中有视频k，即yik∈{0，1}； 表示总缓存空间的缓存命中量，
缓存命中量越大表示缓存空间中请求概率高的视频越多，资源利用率越高，系统更高效；
[0014] 在存储空间和链路带宽受限的情况下，通过合理地在各个网络节点中缓存视频数据，使本地网络节点的总缓存命中量达到最大，即 取得最大值；节点缓存容量受限，Di为节点i的缓存容量，则缓存视频时必须满足
[0015] 具体步骤如下：(1-1)缓存请求概率最高的视频；(1-2)保证缓存所有视频；(1-3)填满节点剩余空间；(1-4)寻找最佳分配方式。
[0016] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤一在所有节点缓存特定的视频中的(1-1)缓存请求概率最高的视频：
[0017] 将网络中所有节点i的总缓存容量 中预留比例为α的部分 来缓存每个网络节点中请求概率最高的视频，假设α为一个给定的数值；用Pi表示节点i缓存的视频集合，Di′表示节点i的剩余缓存容量；
[0018] 对于集合M中的每个节点i，初始化集合Pi为空集，令 为总容量中比例为α的部分容量，初始化集合W＝{(i,k)|i∈M,k∈N}为所有可能的(i,k)配对的集合，初始化节点i的剩余缓存容量Di′＝Di；
[0019] 当D大于0且集合W不为空集时，令 如果 即视频k*的大小不大于节点i*的剩余缓存容量，则令 即把视频k*缓存到节点i*中，同时将用
来缓存请求概率最高视频的部分容量D和节点i*的剩余缓存容量 均减去视频k*的大小
Sk*；令W＝W-{(i*，k*)}，即把集合W中的(i*，k*)配对去掉，同时令 表示节点i*的缓存中有视频k*；
[0020] 如果D大于0且集合W不为空集，则继续缓存视频；如果D等于0或者集合W为空集，则表示用来缓存请求概率最高视频的空间已经分配完，或者网络中所有的节点均分配到所有的视频；
[0021] 缓存视频结束后，得到每个节点i中缓存视频的集合Pi以及全部Pi的并集N0，集合N0中的元素表示网络中任一节点缓存的视频，所有视频中请求概率最高的视频缓存完毕。
[0022] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤一在所有节点缓存特定的视频中的(1-2)保证缓存所有视频：
[0023] 令Nr表示网络中没有缓存的视频的集合，即 为了利用剩余的1-α部分空间实现所有视频全覆盖，并在保证缓存全部视频的前提下使缓存命中量
最大，则每个视频只需在所有网络节点中缓存唯一复本即可；
[0024] 存储容量受限，则必须满足
[0025] 对于集合Nr中的每一个视频k，令Yk表示所有可以用于缓存视频k的节点集合，初始化Yk＝M；
[0026] 在集合Yk中寻找一个使 取得最大值的节点i*，即 若视频k的大小Sk大于节点i*的剩余空间 则令Yk＝Yk-i*，即表示节点i*不可以用于缓存视频k；继续在集合Yk中寻找一个使λik取得最大值的节点i*缓存视频，直到Yk变为空集；Yk为空集表示当前网络内没有节点具有足够的空间来缓存视频k，即网络无法保证缓存所有视频，则当前给定的α值是不合理的；
[0027] 若Sk不大于节点i*的剩余空间 令Nr＝Nr-k，将视频k缓存到节点i*中，同时更新 为 减去视频k的大小Sk；
[0028] Nr变为空集，缓存所有视频结束。
[0029] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤一在所有节点缓存特定的视频中的(1-3)填满节点剩余空间：
[0030] 视频缓存完成后，各个节点i可能还有部分剩余空间；
[0031] Ni表示节点i没有缓存的视频的集合，Pi″表示节点i将要缓存的视频k的集合；在不超过节点i的剩余缓存容量的条件下，即 将使得 最大的视频加入集合Pi″中，同时将Pi″中的视频缓存到节点i中；
[0032] 遍历集合M中的所有节点i，初始化集合Pi″为空集；
[0033] 当Di′大于0且集合Ni不为空集时，令 即Ni中最受欢迎的视频；如果视频k*的大小Sk*不大于此时节点i的剩余容量Di′，则令集合Pi″＝Pi″∪k*，Ni＝Ni-k*，把视频k*缓存到节点i中，将节点i剩余容量Di′更新为Di′减去Sk*；如果视频k*的大小Sk*大于此时* *
节点i的剩余容量Di′，令集合Ni＝Ni-k，不缓存视频k；
[0034] 如果Di′大于0且集合Ni不为空集，则继续按照所述方法，给节点继续缓存视频；如果Di′等于0或者集合Ni为空集，则表示节点i的剩余缓存空间已经分配完，或者节点i已经缓存所有的视频，集合Pi＝Pi∪Pi″，得到节点i中缓存的全部视频；
[0035] 遍历完集合M中的所有节点i后，此时所有节点的缓存空间都已经被填满，并得到全部节点i和视频k对应的yik值；记录每个节点的缓存分配结果，即每个节点缓存的视频集合Pi，并根据节点缓存空间分配结果得到缓存命中量 的值。
[0036] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤一在所有节点缓存特定的视频中的(1-4)寻找最佳分配方式：
[0037] 总缓存空间中用于缓存请求概率高的视频的空间比例α越大，缓存命中量也越大，则将缓存命中量 表示为α的一个函数H(α)，即
[0038] 选择一个更大的α能够提升系统的性能，避免网络无法缓存全部视频，采用二分法在[0,1]区间内寻找最佳α，在保证缓存全部视频的前提下，使得目标值H(α)取得最大值，为α值设置一个下界αl＝0，得到对应H(αl)的值；
[0039] 若集合Yk为空集，表示当前α值不合理，即系统全部容量都无法保证覆盖全部视频，系统对容量不足的情况不作处理；
[0040] 若集合Yk为空集，为α值设置一个上界αu＝1，得到对应H(αu)的值，如果没有缓存视频的集合Nr为空集，则表示用系统全部容量的α倍缓存的请求概率最高的视频即为所有的视频N，因此直接得到最佳α为1；
[0041] 如果有缓存视频的集合Nr为空集，在αl和αu之间使用二分查找法，若H(αl)H(αu)，则令αu＝(αl+αu)/2，重新计算H(αu)，直到H(αl)＝H(αu)，此时得到的H(α)为最大。
[0042] 进一步根据所述基于联合缓存架构的网络内视频缓存方法，步骤二中确定获取视频的最佳源节点：
[0043] 当一个节点i接收到对视频k的请求时，节点i先在本地缓存中寻找视频k，如果有则直接将视频k发送给用户，否则在其他网络节点的缓存中寻找视频k；当存在多个其他网络节点都缓存有视频k时，选择其中一个网络节点作为所请求视频k的最佳源节点；
[0044] 把网络进行视频缓存的时间划分为若干个轮，每一轮持续时间为△t，在每一轮时间内，每个网络节点从用户端接收请求；
[0045] 对于网络中的所有链路l，用fl表示链路l上的总的传输速率；用L(j,i)表示从节点j到节点i的路径；用ζl(·)表示已知的链路时延函数，是一个关于负载fl的单调递增函数，则 表示从节点j发送一个单元的数据到节点i的时延成本；用Ri表示一轮时间内节点i中被请求但没有缓存的视频的集合；用rk表示视频k的传输速率；用Tk表示拥有视频k复本的所有节点的集合；用 表示所有节点获取视频的加权时延成
本之和；
[0046] 通过为每个视频k的请求选择最佳的视频源节点，使所有节点获取视频的加权时延成本之和达到最小，即使 取得最小值；
[0047] 按如下步骤进行：
[0048] (2-1)建立本地负载表，网络中的路由器定期地将各条链路的负载信息，即传输速率报告给各个网络节点，每个节点接收报告后建立一个具有全部链路负载信息的本地负载表；
[0049] (2-2)根据本地负载表寻找最佳源节点，每轮时间△t结束时，网络节点i处理接收到的视频请求，假设收到对于视频k的请求，则合并节点i中对于视频k的全部请求；若节点i的本地缓存中无视频k，则节点i根据本地负载表获取每条链路的负载fl，由得到传输视频k到节点i时延成本最小的节点j*，其中每条链路l必
须满足fl≤Cl，Cl表示链路l的容量，即该链路所允许的最大的传输速率；确定最佳源节点j*后，节点i向节点j*请求发送视频k；
[0050] (2-3)更新本地负载表，节点i向节点j*发送对于视频k的请求后，节点i和节点j*更新节点i和节点j*的本地负载表，将路径L(j*,i)经过的所有链路l的负载fl变成fl+rk，并将更新消息发送给网络中的路由器；路由器将更新消息广播给网络中的每一个节点，各个节点收到更新消息后更新本地负载表；
[0051] 为节点i中的对视频k的请求找到了最佳的源节点j*，用户通过最佳源节点j*得到所请求的视频。
[0052] 本发明的有益效果：
[0053] (1)本发明提出了一个可以解决网络内视频缓存问题的联合缓存架构，能够保证移动网络内视频数据的可靠、高效存储和调用；
[0054] (2)本发明通过决定网络中各个节点应该缓存的视频，使网络总缓存命中量达到最大值，从而节省了系统带宽，提高资源利用率；
[0055] (3)本发明考虑了视频请求模式和链路状态信息的动态变化，为用户在网络中选择一个最佳的视频源节点，有效地降低了网络时延成本。
附图说明
[0056] 图1为本发明所述基于联合缓存架构的网络内视频缓存方法的流程图。
具体实施方式
[0057] 以下结合附图对本发明的技术方案进行详细的描述，以使本领域技术人员能够更加清楚地理解本发明的方案，但并不因此限制本发明的保护范围。
[0058] 如图1所示，本发明所述基于联合缓存架构的网络内视频缓存方法，具体如下：
[0059] 步骤一：在所有节点缓存特定的视频。
[0060] 为了便于描述，令M为网络中所有节点i的集合；N为所有需要缓存的视频k的集合；Sk为视频k的大小；λik表示节点i中收到用户请求为视频k的概率，其中λik∈[0，1]，可通过历史统计计算或预测得到；yik表示节点i的缓存中是否有视频k，yik＝0表示节点i的缓存中没有视频k，yik＝1表示节点i的缓存中有视频k，即yik∈{0，1}； 表示总缓存空间
的缓存命中量，缓存命中量越大表示缓存空间中请求概率高的视频越多，资源利用率越高，系统更高效。
[0061] 在存储空间和链路带宽受限的情况下，通过合理地在各个网络节点中缓存视频数据，使本地网络节点的总缓存命中量达到最大，即 取得最大值。由于节点缓存容量受限，令Di为节点i的缓存容量，则缓存视频时必须满足
[0062] 如图1所示，在所有节点缓存特定的视频，具体步骤如下：
[0063] (1-1)缓存请求概率最高的视频。
[0064] 将网络中所有节点i的总缓存容量 中预留比例为α的部分 来缓存每个网络节点中请求概率最高的视频，假设α为一个给定的数值。用Pi表示节点i缓存的视频集合，Di′表示节点i的剩余缓存容量。
[0065] 对于集合M中的每个节点i，初始化集合Pi为空集，令 为总容量中比例为α的部分容量，初始化集合W＝{(i,k)|i∈M,k∈N}为所有可能的(i,k)配对的集合，初始化节点i的剩余缓存容量Di′＝Di。
[0066] 当D大于0且集合W不为空集时，令 如果 即视频k*的大* * *
小不大于节点i的剩余缓存容量，则令 即把视频k 缓存到节点i中，同时将用
来缓存请求概率最高视频的部分容量D和节点i*的剩余缓存容量 均减去视频k*的大小
* * * * *
Sk*；令W＝W-{(i ，k)}，即把集合W中的(i ，k)配对去掉，同时令 表示节点i的缓存中有视频k*。如果D大于0且集合W不为空集，则继续缓存视频；如果D等于0或者集合W为空集，则表示用来缓存请求概率最高视频的空间已经分配完，或者网络中所有的节点均分配到所有的视频。
[0067] 缓存视频结束后，得到每个节点i中缓存视频的集合Pi以及全部Pi的并集N0，集合N0中的元素表示网络中任一节点缓存的视频，所有视频中请求概率最高的视频缓存完毕。
[0068] (1-2)保证缓存所有视频。
[0069] 令Nr表示网络中没有缓存的视频的集合，即 为了利用剩余的1-α部分空间实现所有视频全覆盖，并在保证缓存全部视频的前提下使缓存命中量
最大，则每个视频只需在所有网络节点中缓存唯一复本即可。由于存储容量受限，则必须满足
[0070] 对于集合Nr中的每一个视频k，令Yk表示所有可以用于缓存视频k的节点的集合，初始化Yk＝M。
[0071] 在集合Yk中寻找一个使 取得最大值的节点i*，即 若视频k的大小Sk大于节点i*的剩余空间 则令Yk＝Yk-i*，即表示节点i*不可以用于缓存视频k；继续在集合Yk中寻找一个使λik取得最大值的节点i*缓存视频，直到Yk变为空集。Yk为空集表示当前网络内没有节点具有足够的空间来缓存视频k，即网络无法保证缓存所有视频，则当前给定的α值是不合理的。
[0072] 若Sk不大于节点i*的剩余空间 令Nr＝Nr-k，将视频k缓存到节点i*中，同时更新为 减去视频k的大小Sk。Nr变为空集，缓存所有视频结束。
[0073] (1-3)填满节点剩余空间。
[0074] 视频缓存完成后，各个节点i可能还有部分剩余空间。Ni表示节点i没有缓存的视频集合，Pi″表示节点i将要缓存的视频k的集合。在不超过节点i的剩余缓存容量的条件下，即 将使得 最大的视频加入集合Pi″中，同时将Pi″中的视频缓存到节点i中。
[0075] 遍历集合M中的所有节点i，初始化集合Pi″为空集。
[0076] 当Di′大于0且集合Ni不为空集时，令 即Ni中最受欢迎的视频；如果视频k*的大小Sk*不大于此时节点i的剩余容量Di′，则令集合Pi″＝Pi″∪k*，Ni＝Ni-k*，把视频k*缓存到节点i中，将节点i剩余容量Di′更新为Di′减去Sk*；如果视频k*的大小Sk*大于此时* *
节点i的剩余容量Di′，令集合Ni＝Ni-k，不缓存视频k。
[0077] 如果Di′大于0且集合Ni不为空集，则继续按照所述方法，给节点继续缓存视频；如果Di′等于0或者集合Ni为空集，则表示节点i的剩余缓存空间已经分配完，或者节点i已经缓存所有的视频，令集合Pi＝Pi∪Pi″，得到节点i中缓存的全部视频。
[0078] 遍历完集合M中的所有节点i后，此时所有节点的缓存空间都已经被填满，并得到全部节点i和视频k对应的yik值。记录每个节点的缓存分配结果，即每个节点缓存的视频集合Pi，并根据节点缓存空间分配结果得到缓存命中量 的值。
[0079] (1-4)寻找最佳分配方式。
[0080] 总缓存空间中用于缓存请求概率高的视频的空间比例α越大，缓存命中量也越大，则将缓存命中量 表示为α的一个函数H(α)，即
[0081] 选择一个更大的α能够提升系统的性能，避免网络无法缓存全部视频，采用二分法在[0,1]区间内寻找最佳α，在保证缓存全部视频的前提下，使得目标值H(α)取得最大值。为α值设置一个下界αl＝0，得到对应H(αl)的值。
[0082] 如果集合Yk为空集，表示当前α值不合理，即系统全部容量都无法保证覆盖全部视频，系统对容量不足的情况不作处理。
[0083] 如果集合Yk为空集，为α值设置一个上界αu＝1，得到对应H(αu)的值，如果没有缓存视频的集合Nr为空集，则表示用系统全部容量的α倍缓存的请求概率最高的视频即为所有的视频N，因此直接得到最佳α为1。
[0084] 如果有缓存视频的集合Nr为空集，在αl和αu之间使用二分查找法，若H(αl)H(αu)，则令αu＝(αl+αu)/2，重新计算H(αu)，直到H(αl)＝H(αu)，此时得到的H(α)为最大。
[0085] 所有网络节点都缓存了特定的视频。
[0086] 步骤二：确定获取视频的最佳源节点。
[0087] 当一个节点i接收到对视频k的请求时，节点i先在本地缓存中寻找视频k，如果有则直接将视频k发送给用户；否则在其他网络节点的缓存中寻找视频k。当存在多个其他网络节点都缓存有视频k时，选择其中一个网络节点作为所请求视频k的最佳源节点。把网络进行视频缓存的时间划分为若干个轮，每一轮持续时间为△t。在每一轮时间内，每个网络节点从用户端接收请求。
[0088] 对于网络中的所有链路l，用fl表示链路l上的总的传输速率；用L(j,i)表示从节点j到节点i的路径；用ζl(·)表示已知的链路时延函数，是一个关于负载fl的单调递增函数，则 表示从节点j发送一个单元的数据到节点i的时延成本；用Ri表示一轮时间内节点i中被请求但没有缓存的视频的集合；用rk表示视频k的传输速率；用Tk表示拥有视频k复本的所有节点的集合；用 表示所有节点获取视频的加权时延成
本之和。
[0089] 通过为每个视频k的请求选择最佳的视频源节点，使所有节点获取视频的加权时延成本之和达到最小，即使 取得最小值。
[0090] 如图1所示，确定获取视频的最佳源节点，按如下步骤进行：
[0091] (2-1)建立本地负载表。网络中的路由器定期地将各条链路的负载信息，即传输速率报告给各个网络节点，每个节点接收报告后建立一个具有全部链路负载信息的本地负载表。
[0092] (2-2)根据本地负载表寻找最佳源节点。每轮时间△t结束时，网络节点i处理接收到的视频请求，假设收到对于视频k的请求，则合并节点i中对于视频k的全部请求。若节点i的本地缓存中无视频k，则节点i根据本地负载表获取每条链路的负载fl，由得到传输视频k到节点i时延成本最小的节点j*，其中每条链路l必
须满足fl≤Cl，Cl表示链路l的容量，即该链路所允许的最大的传输速率。确定最佳源节点j*后，节点i向节点j*请求发送视频k。
[0093] (2-3)更新本地负载表。节点i向节点j*发送对于视频k的请求后，节点i和节点j*更新节点i和节点j*的本地负载表，将路径L(j*,i)经过的所有链路l的负载fl变成fl+rk，并将更新消息发送给网络中的路由器；路由器将更新消息广播给网络中的每一个节点，各个节点收到更新消息后更新本地负载表。
[0094] 为节点i中的对视频k的请求找到了最佳的源节点j*，用户通过最佳源节点j*得到所请求的视频。
[0095] 以上仅是对本发明的优选实施方式进行了描述，并不将本发明的技术方案限制于此，本领域技术人员在本发明的主要技术构思的基础上所做的任何公知变形都属于本发明所要保护的技术范畴，本发明具体的保护范围以权利要求书的记载为准。
