LEAD：大规模WiFi系统边缘缓存部署策略

姓名：胡娟

学号：20021110092

嵌牛导读

为了适应移动设备数量的激增和不断增长的数据流量需求，大多数企业场所（如企业、机场和校园）都部署了大规模的 WiFi 系统，为用户提供室内的大范围覆盖和高速互联网体验。作者在本文中针对一个校园网大型 WiFi 系统进行数据分析和建模，以期最大化系统的长期缓存收益（long-term caching gain），即减少回传流量（backhaul traffic）的总量。作者首先对收集到的大量用户网络连接记录数据进行了深入的统计分析，并提出名为   LEAD   的缓存部署策略（Large-scale wifi Edge cAche Deployment），在该策略中，作者首先将大型 AP 群集到大小合适的边缘节点中，然后对边缘级别的流量消耗进行静态测量，并对流量统计数据进行采样，以便精确地描述未来的流量状况；作者最后设计了TEG（Traffic-wEighted Greedy）算法来解决长期缓存收益最大化问题。文章进行了大量以轨迹为驱动的仿真，结果证明了 LEAD 的有效性。

嵌牛鼻子

LEAD（Large-scale wifi Edge cAche Deployment）,TEG（Traffic-wEighted Greedy）

嵌牛正文

大规模WiFi系统边缘缓存部署策略主要挑战：

想要在大规模 WiFi 系统中以经济高效的方式部署边缘缓存，在以下三个方面非常具有挑战性。第一，在大规模的 WiFi 系统中部署边缘缓存要耗费大量的人力和时间资源，不太可能在每个 AP 上部署边缘缓存。因此，高效的缓存配置策略非常重要。第二，AP 的部署范围很广，在用户连接记录和流量消耗方面可能会有明显的特征。如何将有限的缓存存储预算分配给更多的用户，同时减轻后台的负担并不是一件轻而易举的事。一方面，如果将过多的缓存分配给用户关联较少的 AP ，则会浪费缓存资源；另一方面，对于那些用户频繁连接并消耗密集数据流量的热门 AP ，为其分配不足的缓存存储空间可能无法充分释放边缘缓存的潜力。第三，由于网络的动态和用户移动性，接入点的流量消耗是随时间动态变化的，而缓存部署是静态的一次性解决方案，因此在不知道未来流量状况的情况下，很难长期保持最高的缓存收益。

系统描述和问题定义

作者在其所在校园内的 WiFi 系统中进行了大量的数据收集和实验，该 WiFi 系统由 30925 区域中的 8000 个 AP 组成，可为 40000 多个用户提供网络连接服务，系统的架构如图 1 所示。
作者首先提出了一个大规模的 WiFi 缓存增益最大化（Caching Gain Maximization）问题：给定总的缓存存储预算 C ，如何将它们分配给大型 WiFi 系统中的 AP ，使总时间内减少的总回程流量最大？我们将长期持续时间划分为 T 个连续的时隙，并假设系统中有 N 个 AP，记为 。另外，对于  ，假设在时隙 t 期间有 个用户与 AP 建立了连接，表示为。因此，CGM 问题可以表述为：
数据收集和分析

作者持续两个多月，在 7710 个 AP 中收集了 41119940 条网络连接记录，覆盖 36952 个用户，总数据大小超过 35 GB。通过对数据的深入分析，得出以下结论。

1． 广泛的流量消耗

图 2 显示了 5月8日 - 6月8日以及 6月9日 - 7月9日每个 AP 的平均每日流量消耗，可以看出，两条曲线非常接近，这意味着每天的流量消耗规律相似，如果缓存初始部署策略设计得当，缓存收益可以长期维持。在两条曲线中，每日流量消耗的比例在 KB 和 KB 之间占 90％以上，流量消耗大于 KB 的总比例不超过 10％，这意味着如果可以在流量消耗非常大的那几个 AP 上正确部署缓存，则可以获得相当可观的缓存收益。
2． AP 受欢迎程度呈指数型分布

作者在本文中提出 AP 流量加权熵的概念来量化一个 AP 的受欢迎程度。具体来说，在某个时间段内与一个 AP 建立连接的用户数越多，消耗的流量越多，则流量加权熵越大，代表受欢迎程度越高。图3展示了两个月中所有 AP 的流量加权熵，可以看出具有相对较大的流量加权熵值（即非常受欢迎）的 AP 的比例很小。这启发我们仅在少数具有最大流量加权熵值的 AP 上部署更多的缓存资源，以提供缓存服务，会取得更好的缓存收益。
系统设计

一、 LEAD 策略设计

作者根据上述的数据收集和分析，设计了名为 Clustering Edge Nodes 的聚簇缓存节点策略：根据 AP 的物理位置，将相邻的 AP 聚集成大小合适的边缘节点。当建筑物较小，例如少于 20 个 AP 时，只需在该建筑物中部署一台边缘缓存服务器，即可通过将服务器连接到这些 AP 的 PoE 交换机来覆盖该建筑物中的所有 AP。对于可能具有超过 100 个 AP 的大型建筑物，我们将每个楼层划分为不同的边缘节点，即同一楼层中的 AP 由于物理上彼此靠近而被聚集成一个边缘节点，并且适合于应用边缘节点缓存部署。根据 GPS 定位，作者将分布于校园中 201 座建筑物上的 7710 个 AP 划分到 667 个边缘节点，并在这些节点上进行边缘缓存的部署。
二、 TEG 算法提出

经过作者的数据分析得到两个主要结论：第一，每个 AP 的流量消耗在很大的范围内变化，并且 AP 比例在该范围内平均分布，这表明应根据基础流量需求对缓存大小进行异构分配；第二，与单个 AP 相比，一组 AP（按物理位置划分集群）的流量消耗更加稳定，这意味着短期流量统计信息可用于推断未来的长期流量状况。

于是作者提出使用短期流量消耗平均值 来近似代替边缘节点 的未来长期流量消耗期望，于是可将 CGM 问题重写为：
作者设计了 TEG 算法，以贪心策略迭代地分配缓存存储。具体来说，如图5所示，给定总的缓存存储预算 ，我们首先分配缓存预算的第一个节点 ，使 处的缓存收益最大，即 ,以此类推,直到没有缓存预算可用，得到最终缓存分配结果  。TEG 算法的时间复杂度为 ，考虑到缓存的部署是一次性的解决方案，该复杂度是可以接受的。
作者使用 5月8日至 6月8日的用户连接数据作为训练数据集求得 ，将 6月9日至 7月9日的数据作为测试数据集来评估系统性能。作者选取了三种基准策略与本文提出的 LEAD 策略进行对比：Optimal（在已知未来流量消耗下的最优分配策略，这种策略无法实现，仅作为 CGM 问题的上限参考）、Equipartition（系统提供商通常会采用的策略，总缓存预算平均分配给每个边缘节点）、Demographics（根据用户密度分配缓存）。作者以缓存收益率（Caching gain ratio，成功缓存的流量与总消耗流量的比值）为指标来衡量以上四种算法的好坏，结果如图 6所示，可以看出 LEAD 缓存部署策略远远优于 Equipartition 和 Demographics 策略，并已非常接近最优策略，证明了本文策略的有效性。
论文出处：

Lyu F , Ren J , Cheng N , et al Demystifying Traffic Statistics for Edge Cache Deployment in Large-Scale WiFi System[C]// 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) IEEE, 2019

前端缓存机制有多种，如浏览器缓存、CDN缓存、DNS缓存、代理服务器缓存等。

CDN全称是Content Delivery Network，即内容分发网络。CDN的原理是将资源存放在各地的缓存服务器上，当用户请求资源时，从就近的服务器上返回缓存的资源，而不需要每次都从源服务器获取，减轻源服务器的压力，又能提升用户的访问速度。

浏览器可以将用户请求的资源进行缓存，存放在本地。浏览器缓存一般通过请求头来设置。
与浏览器缓存有关的头部有：

浏览器会将服务器的域名与IP地址的映射缓存在本地，这样用户在访问网站时，不用每次都去查询DNS映射表。

在浏览器和服务器之间架设的一个服务器 ，这个代理服务器会帮助浏览器去请求页面，然后将页面进行处理和压缩(例如压缩和文件)，使页面变小，再传输给浏览器。大部分代理服务器都有缓存的功能，如果浏览器所请求的文件在它本机中存在且是最新的，就不需要再从源服务器请求数据，提高了浏览速度。

在浏览某个页面时，浏览器会判断页面的关联内容，进行预加载。用户在浏览A页面时，就加载好B页面，这样当用户去访问B页面时，B页面很快就出来，提升了用户体验。但这个机制有一定的缺陷，就是预判不一定准确，可能会造成流量和资源的浪费。

这一现象的原因可能是因为1000台服务器使用不均造成的，假设每台服务器缓存了100位用户的数据，而A服务器的用户使用频繁，B服务器的用户却很少使用，这样A服务器就会出现死机的情况。解决方案有很多种，这里我说我想到的一种，通过设定每台服务器数据缓存的限定值，例如为缓存最高值的80%，当数据缓存到达这个值时，将服务器中缓存数据最大的用户移到新服务器中或者用户使用不频繁的服务器中。

你可以尝试使用一些预设的页面缓存答案，比如使用>缓存的基本思想是利用客户端访问的时间局限性，将客户端访问过的内容做一个副本，在一定时间内存放到本地，当改数据下次被访问时，不必连接到后端服务器反复去查询数据，而是由本地保存的副本响应数据。

保存在本地的这些副本具有一个过期时间，超过该时间将会更新。判断一个副本数据是否为过期数据的办法有很多，可以使用保留时间来判断，也可以使用数据完整度来判断。

许多Web服务器还具有校验功能，就是当某些副本数据过期以后，先向后端服务器发送校验请求，后端服务器对这些数据进行校验，如果发现原数据和副本没有差别，则将过期副本重新置为可用副本。

以上nginx配置结合使用：

proxy_params文件的配置如下：

访问一次页面，并向 >在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法 典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。 常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。1、Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法为例说明。由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。 用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。 Consistent Hashing原理示意图 新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。 Consistent Hashing添加服务器示意图 虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。 虚拟节点对Consistent Hashing结果的影响 从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际节点的100-200倍的时候，结果还是很均衡的。 第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；” 为何是 (N-1)/N 呢？解释如下： 比如有 3 台机器，hash值 1-6 在这3台上的分布就是：host 1: 1 4host 2: 2 5host 3: 3 6如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成：host 1: 1 3 5host 2: 2 4 6 可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能 consistent hashing 的办法上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的。以下部分为一致性哈希算法的一种PHP实现。点击下载

---