网络服务器的摇尾舞

网络服务器的摇尾舞


发布日期: 2016-10-24 更新日期: 2016-11-09 编辑:xuzhiping 浏览次数: 3633

标签:

摘要: 罗马学者及作家瓦罗相信,蜜蜂是绝佳的建筑工程师。在检视了它们的六角形蜂巢后,他就怀疑这是一种以最少蜂蜡盖出最多蜂蜜储藏空间的结构。但最近又有人指出,蜜蜂也是极佳的计算机工程师。在瓦罗之后2000年,牛津大学的纳克拉尼及佐治亚理工学院的托维在研讨会中提出了一篇论...

罗马学者及作家瓦罗相信,蜜蜂是绝佳的建筑工程师。在检视了它们的六角形蜂巢后,他就怀疑这是一种以最少蜂蜡盖出最多蜂蜜储藏空间的结构。但最近又有人指出,蜜蜂也是极佳的计算机工程师。在瓦罗之后2000年,牛津大学的纳克拉尼及佐治亚理工学院的托维在研讨会中提出了一篇论文,主题是社会性昆虫的数学模型。他们模仿蜜蜂寻找花蜜的行为,找出了网络服务器的最优负荷分配方式。

1930年代的诺贝尔奖得主,动物学家弗里施发现了所谓蜜蜂的摇尾舞,可以在蜂巢中为其他蜜蜂提供关于花丛的距离及品质的信息。空闲的蜜蜂看到同事的摇尾舞后,就可以启程工作(蜂窝里很黑,因此它们并不是用眼睛“看” 舞蹈,而是从空气压力的变化来推断)。蜜蜂起飞前,彼此之间并不做沟通,所以它们不知道哪个花丛可以收获多少花蜜,但依旧能让采集花蜜的速率达到最大。贫瘠的花丛只由少数蜜蜂采集,而收获量大且距离近的花丛则有大量蜜蜂造访。发生这种现象的原因是所谓群体智慧:即使每只蜜蜂只遵循少数指示,整个群体仍会表现出几近最优化的行为。

纳克拉尼及托维感兴趣的是网络服务器提供者面临的问题。网络服务提供者提供数种网络服务,如拍卖、股票买卖、订购机票等,他们依照预测的每种服务的需求,分配特定数目的服务器(称为一个群集)给各项服务。

两位科学家根据蜜蜂的行为,设计了服务器分配模型,并进行了模拟测试。接踵而来的使用者需求,分别被分配到各类服务的等候队伍中,待需求完成之后,服务提供者就可以得到一笔收入。涌进来的不同服务的订单数目不断变动,如果能把使用率过低的服务器分配到过载的群集中,就能增加利润。但这同时也会提高成本,因为重新分配的服务器需要再度设定,也需要输入新服务的软件。在这段时间内(通常是5分钟左右),服务器将无法响应新进来的要求与订单。如果等候时间(停工期)过长,失望的客户就会离开,让潜在的利润消失。因此,为了让利润最大化,服务提供者必须不断地在不同的应用软件间调度计算机系统,以适应需求量的变化。

计算获利能力的传统算法有3种。第一种是“无所不知算法”:在规定时间间隔内决定前一个时段的最优分配方式;第二种是“贪 婪算法”:依照经验法则,假设每个时段的所有服务需求水平,到下 一个时段仍维持不变;第三种是“最优静态算法”: 倒回去计算整个时期内服务器的最优、不变(静态)分配。

纳克拉尼及托维以蜜蜂的策略来比喻这3种算法。在他们的模型中,需求排成的队伍代表等着被采集的花丛,个别的服务器代表采蜜的蜜蜂,服务器群集表示负责采集特定花丛的蜜蜂群。摇尾舞 成为模型中的“告示板”,满足要求之后,服务器将以特定概率贴出一张关于这个被服务队伍特性的告示。其他服务器读到告示的概率愈高,表示它们现在服务的队伍获利愈低。基于它们自己最近的经验及张贴的告示,服务器就像观看摇尾舞的工蜂,决定是否要转换到新的队伍。从一套网络应用软件转换到另一套的成本,被比喻为蜜蜂观看摇尾舞并转换花丛所花费的时间。

模拟的结果显示,从获利能力的角度来看,蜜蜂采蜜的行为比3种算法中的2要好1%~50%,只有无所不知算法能产生较高的利润。但这个算法计算的是获利的最高上限,在现实中并不适用,原 因有二:其一,假设现在就能事先确知未来的客户行为,是不切实际的;其二,计算最优分配所需的计算机资源太庞大。

说些题外话,直到1988年,美国数学家黑尔斯才证明六角形蜂窝(六角晶格)是将平面分割为相等面积的最有效率方式。但蜜蜂不是完美的,虽然它们有能力做出二维空间中的最优结构配置,但在三维空间里,备受赞美的蜂巢只是近似最优。匈牙利数学家托斯在1964年设计出的蜂巢,比蜜蜂盖蜂巢所用的蜂蜡少了0.3%。

关注公众号
获取免费资源

随机推荐


Copyright © Since 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org