利用遗传算法在服务器上分发在线内容

Neha Mangla
印度班加罗尔Atria理工学院副教授

摘要

互联网上看到的所有流量都被平等对待，这通常被称为互联网中立。互联网中立性要求所有网络流量都应被平等对待，并应遵循“尽力”路由策略。但随着智能应用程序的出现，这种情况正在发生巨大变化。每个网络应用程序都有自己的带宽需求。我们面临的问题是，关键应用程序所需的带宽与互联网带宽不匹配。由于网络中立性原则，核心路由器不能优先处理某一流量，可能会对关键应用造成影响。这类问题仍处于研究阶段。作为一种解决方案，我们将在边缘路由器上看到应用级路由优化机制与GA方法如何适用于这类应用。

关键字

GA, QoS, QoE，带宽，延迟

介绍

近年来，实时应用被广泛应用。此外，实时嵌入式系统被发现在许多不同的应用领域，包括电子、电信、空间系统、医疗成像和消费电子产品。利用有线多媒体传输在因特网上传输实时视频流面临着带宽短缺和存储容量有限等挑战。此外，还有不同的应用有不同的QoS要求，以达到用户的满意。QoS依赖于一些参数，如:吞吐量、带宽、延迟、错误率控制和丢包。根据这些参数，选择运输路径。因此，路由算法的经验质量必须具有足够的适应性、灵活性和智能，以便快速做出决策。为了实现这一目标，使用了基于受自然过程启发的计算策略的遗传算法(GA)。遗传算法是由自然选择原理和进化计算技术发展而来的一种全局优化技术。从理论上和经验上都证明了遗传算法是一种稳健的搜索技术。 Each possible point in the search space of the problem is encoded into a suitable representation for applying GA. In GA, each population of individual solutions with fitness value is transformed to a new generation of the population, depending on the Darwinian principle of the survival of the fitness. By applying genetic operators, such as crossover and mutation, GA produces better approximations to the solutions. Many routing algorithms based on GA have been proposed. Selection and reproduction processing at each iteration produces a new generation of approximations.

遗传算法的阶段是:

•选择初始人口。

•确定种群中所有初始个体的适合度

做

•选择排名最好的个体进行繁殖。

•通过交叉和突变(遗传操作)培育新一代并生育后代。

•评估后代的个体适应性。

•用后代取代人口中排名最低的部分。

While(终止条件)

在此，我们提出了一种基于遗传算法的新方法，以获得利用过去经验来改进当前决策以选择有效路径的能力。

路由的历史

通常在所有的路由算法中，我们构造路由表来将通信数据包转发到目的地，并为每个目的地指定路由或下一跳。问题与这些路由方法是自适应的。RIP和OSPF采用静态距离度量，如跳数度量和延迟信息带来的不确定性。自适应算法可能会导致振荡、路由不可达等。为了适应，我们需要频繁地观察，而广播无法频繁地观察。观测开销改变网络状态。然而，我们可以通过以下方式减少开销:尽可能减少广播的频率。限制观测，即对经常使用的有限路线进行观测(值得观测开销)，通过自主控制，即每个节点应利用本地获得的信息独立确定路线。在智能控制方面，如预测算法、学习方案、建立解决方案数据库等。进化计算(EC)是一个很有希望的答案。 As Evolution is essentially a distributed process. Adaptation in evolutionary process needs less frequent communications (eg. no broadcast is necessary) among individuals. Evolution is considered robust to environmental changes.

关键理念

在提出的算法中，我们将利用现有的网络路由协议，如BGP。我们将根据网络特性和媒体特性学习一个内容的可选路径和路由应用数据。对于视频来说，视频的连续性比总下载时间更重要。在网络方面，我们称之为体验质量。连续播放的视频需求取决于它的带宽。媒体带宽是指一秒钟视频所包含内容的大小。例如，一个800kbps的视频意味着该媒体的每秒钟大小为800kb字节。该算法综合考虑备选路由的媒体带宽和网络带宽，对请求进行最优路由，使用户获得最佳的体验质量。

以下术语

C_我-第i个内容请求

Si -内容的大小

fsz -片段大小

Bi:内容带宽要求

因此，Ci可以被分成n个片段，使得

Ci = Ci0, Ci1, Ci2 ....CSi) / fsz

Ri: ith路线

Rbi:第i条路由带宽

当从网络中获取内容的速率与媒体带宽要求匹配时，用户将获得最佳的体验。

它是适应度函数。目标函数是最大带宽利用率。实现算法的要求是:

•获取媒体请求总数。

•获取每个请求的媒体带宽。

•获取备选路径/服务器总数。

•整理每条路径的网络带宽。

•创建初始人口。

•获得总代数。

•找到交叉点。

•对每个解决方案应用适应度函数，选择最佳解决方案。

•利用精英主义(最佳解决方案)和跨界(解决方案)培养下一代

•重复最后一步，直到我们得到最优解(0延迟)或直到最大代数。输出将是用户感知到的延迟。

适应度函数的算法

适应度函数将采用一个建议的解决方案，并将返回用户感知到的延迟。目标函数的算法为

1.对于每个服务器遍历在其上排队的媒体请求

2.计算服务器上的总负载

3.检查服务器将根据总负载和网络带宽发送多少内容

4.计算每个请求由所有服务器交付的总内容。

5.计算每个内容所需的内容(媒体带宽)和交付的内容之间的差异。

6.计算用户感知到的延迟(差值除以媒体带宽)

7.将每个媒体请求的延迟相加，除以总请求，得到用户/感知到的平均延迟

8.返回平均延迟。

初始总体算法

对于每个内容

做

•生成1到100之间的随机数。

•将内容块按随机数字的比例放置在服务器1上。

•在其他服务器上重复相同的过程

•生成n个这样的解。应用适应度函数

While(最大初始解)

交叉算法

•选择两个解决方案。

•对于每个服务器，在两种解决方案的交叉点之外切换内容。

服务器上内容的编码方案

这里我们假设有n个服务器和m个内容。各内容分为:

Xa,丫……咱

Xb,……Zb

Xm, Ym……Zm评选

其他方案编码

可以有许多划分内容的解决方案。这是两个解的表示。一个在上面，第二个在这里。

内容分发中的交叉

这里我只展示了一个交叉点。然而，在我的实现中，我已经考虑了所有。在这里，我们将首先看到来自两个解决方案的碎片化内容将保持不变。其余的会互换。

内容分布的突变

生成任意随机数。

如果

随机数<=选择的概率

然后

从1减少^圣按随机数分组。

其他的

根据随机数字在任何其他块中减少的部分。

结果分析

输入如下:

输入Total content:8

输入各内容质量:100 120 60 90 150 70 80 95

输入Total servers: 4

每个服务器的BW输入:180 70 160 40

输入Total Generation: 5

进入交叉点

输入突变概率(概率*100):0.2

在这里，我没有展示交叉点1、交叉点2和交叉点3的输入的编码和输出日志。以上部分仅为交点为1的输入示例。

我们通过对三个交叉算子点取相同的输入进行了分析。我们从第五代输出中获得数据，其中包含交叉1、交叉2和交叉3点算子。

我们分析了这三张图。我们看到交点1的最佳结果。

结论

QoE被定义为衡量系统或应用程序满足用户期望的程度。这个概念不同于服务质量，后者侧重于从网络的角度衡量性能。例如，QoE侧重于用户感知的影响，如语音或视频质量的下降，而QoS侧重于网络影响，如端到端延迟或抖动。另一个需要注意的要点是，单个节点上的测量可能表明可接受的QoS，但最终用户可能仍然无法接受QoS。

未来的范围

下一代路由协议需要改变，需要向QoE而不是QoS方向发展。由于体验质量是一种动态现象，依赖于不同利益相关者的反馈，因此下一代路由协议应该适应动态条件，并随着时间的推移而发展。

参考文献

B. M. Leiner, V. G. Cerf, D. D. Clark, R. E. Kahn, L. Kleinrock, D. C. Lynch, J. Postel, L. G. Roberts和S. S. Wolff，“互联网的过去和未来历史”，ACM通讯，第40卷，第102.108页，1997年2月。
D. Awduche, A. Chiu, A. Elwalid, I. Widjaja和X. Xiao，“互联网流量工程的概述和原理”，IETF, RFC 3272, 2002年5月。
J. Moy，“OSPF版本2”，IETF, RFC 2328, 1998年4月。A. Zinin，《思科IP路由》。波士顿，马萨诸塞州”:Addison-Wesley, 2002。
G. Iannaccone等人，“IP骨干链路故障分析”，ACM IMW进程，2002年，第237页。
Z. Wang等人，“支持多媒体应用的服务路由质量”，IEEE JSAC，第14卷，no. 1。1996年9月7日，第1228-34页。
G. Pallis和A. Vakali，“内容交付网络的洞察和展望”，ACM通讯，第49卷，第1期，ACM出版社，纽约，美国，101-106页，2006年1月
彭国强，“CDN:内容分发网络”，技术报告TR-125，实验计算机系统实验室，纽约州立大学石溪分校，纽约，2003。http://citeseer.ist.psu.edu/peng03cdn.html
M. Day, B. Cain, G. Tomlinson和P. Rzewski，“内容互联网络(CDI)的模型”，互联网工程任务组RFC 3466, 2003年2月。www.ietf.org/rfc/rfc3466.txt
M. Hofmann和L. R. Beaumont，内容网络:架构、协议和实践，Morgan Kaufmann出版社，旧金山，CA，美国，129-134页，2005年。
T. Plagemann, V. Goebel, A. Mauthe, L. Mathy, T. Turletti和G. Urvoy-Keller，“从内容分发到内容网络——问题和挑战”，计算机通信，第29卷，第5期，551-562页，2006。
倪俊杰，曾德宏，杨i.s.h.，和X. Hei，“大规模多媒体内容分发网络中的分层内容路由”，《IEEE国际通信会议论文集》，2003 (ICC ' 03)，第2卷，第854-859页，2003年5月。
B. Huffaker, M. Fomenkov, D. J. Plummer, D. Moore和K. Claffy，“Internet中的距离度量”，IEEE国际电信研讨会论文集，IEEE CS出版社，Los Alamitos, CA, USA, 2002。
B. Krishnamurthy, C. Willis和Y. Zhang，“关于内容分发网络的使用和性能”，第一届国际互联网测量研讨会论文集，ACM出版社，169-182页，2001。
A. Barbir, B. Cain, R. Nair和O. Spatscheck，“已知内容网络请求路由机制”，互联网工程任务组RFC 3568, 2003年7月。www.ietf.org/rfc/rfc3568.txt
M. Howarth等人，“通过供应商间流量工程实现端到端服务质量供应”，Comp. comm。，[110]陈晓峰，王晓明，“一种基于网络的BGP路由选择算法”，计算机工程，2003,29(4):366 - 366。
A. Riedl，“利用带宽和延迟度量在IP网络中路由优化的混合遗传算法”，在IEEE IP操作和管理(IPOM)研讨会上，德克萨斯州达拉斯，10月10日。2002.
弗雷泽(1994)。c++遗传编程。技术报告040，索尔福德大学。
戈德堡，D. E. &史密斯，R. E.(1987)非平稳函数优化使用遗传算法与二倍体和优势。在j.j. Grefenstette，编辑，第二届遗传算法国际会议论文集，59-68。Lawrence Erlbaum事务所。
科扎，J.R.(1992)。遗传程序设计:用自然选择方法进行计算机程序设计。马萨诸塞州剑桥:麻省理工学院出版社。
Cisco白皮书，“BGP带宽链路”，http://www.cisco.com/univercd/cc/td/doc/product/software/ios122/122newft/122t /122t2/ftbgpl .htm
T. Bates等人，“BGP-4的多协议扩展”，IETF RFC 4760, 2007年1月。
S. Agarwal等人，“BGP动态对域内流量的影响”，ACM SIGMETRICS Perf。Eval。启示录，第32卷，no。2004年6月1日，第319-30页。
S. Kalyanaraman，“使用在线模拟和动态NAT在BGP环境中的负载平衡”，发表于2001年互联网统计和度量分析Wksp。
M. Howarth等人，“通过供应商间流量工程实现端到端服务质量供应”，Comp. comm。，[110]陈晓峰，王晓明，“一种基于网络的BGP路由选择算法”，计算机工程，2003,29(4):366 - 366。第29卷，no。6, 2006年3月，第683-02页。
Cisco Systems，“MPLS-VPN中eBGP和iBGP的BGP多路径负载共享”，2005年。
关于检测用户代理类型和客户端设备功能的教程http://www.developershome.com/wap/detection/
手机浏览器id http://www.zytrax.com/tech/web/mobile_ids.html
复合能力/偏好配置文件(CC/PP):用于内容协商的用户端框架。http://www.w3.org/TR/NOTE-CCPP/
基于HTTP扩展框架的CC/PP交换协议http://www.w3.org/TR/NOTE-CCPPexchange
RDF词汇描述语言1.0:RDF Schema http://www.w3.org/TR/rdf-schema/
Mozilla开发者中心-用户代理字符串参考- https://developer.mozilla.org/en/User_Agent_Strings_Reference