1700496880
1700496881
T.H.帕尔默
1700496882
1700496883
如果一开始你不成功，那就尝试，再尝试一次。
1700496884
1700496885
今天，我们希望我们的设备能够进行无线通信，例如，我们的键盘和鼠标可以与电脑相隔几米，通过无线的方式相互连接。但是无线网络的出现是出于必要，尤其是在一个没有电线用来这样做的地方——夏威夷。20世纪60年代末和70年代初，诺曼·艾布拉姆森试图将位于檀香山的夏威夷大学的7个校区和分布在4个岛屿和数百英里外的许多研究机构联系在一起。他的想法是通过无线电实现包交换（而不是通过电话系统）将这些岛屿与一个个的发射器和接收器连接起来。这个系统后来被称为阿罗哈网络（ALOHAnet）。
1700496886
1700496887
阿罗哈网络必须克服的最大障碍是干扰。有时两个站点会在同一时间发出信号，这就无意中干扰了彼此的信号。（当然，这也是人类对话中的一个常见特征。）如果两个站点都只是立即重新传输，以送达它们的信息，它们就会冒着永远被困在干扰之中的危险。显然，阿罗哈网络协议需要告诉竞争信号如何给彼此空间，如何为彼此让路。
1700496888
1700496889
发送者需要做的第一件事就是所谓的“打破对称”。就像人行道上的行人所知道的那样，当迎面而来的人偏向左边时，自己就躲向右边，两人都向同一边，就什么也解决不了。类似地，当两个说话的人都停下来，做出让另一个人说的手势以示尊重，然后又在同一时间开始说话；或者当两辆车在十字路口相遇，两车都停下来让对方，然后又试着同时加速。这是一个普遍使用随机性的领域，事实上，如果没有它，网络设计是不可能实现的。
1700496890
1700496891
一个简单的解决办法就是让每个站点都抛硬币。正面，就再发送一次，反面，就等待一个回合，然后再发送。毫无疑问，其中肯定有一个很快就能轻松送达。当只有两个发送者时，这就能很顺利地运行了。但是如果有三个信号同时发送呢？或是4个？在这一点上，网络只有1/4的机会能获得一个单独的数据包（在此之后，你仍然会有三个相互冲突的站点，甚至可能会有更多的相互竞争的信号等待到达）。随着冲突数量的进一步增加，网络的吞吐量可能会如悬崖掉落般骤降。1970年的一份关于阿罗哈网络的报告显示，在电波的平均利用率仅为18.6%的情况下，“这个频道变得不稳定……再传输的平均数量变得不可控了”。这样并不好。
1700496892
1700496893
那么，应该怎么做呢？有没有一种方法可以避免陷入这种命运？这一突破在每次连续失败最后都提高了平均延迟时间，具体来说，就是在试图再次传输之前将潜在的延迟加倍。因此，在最初的失败之后，发送者会在一个或两个回合之后随机地重新传输，在第二次失败之后，它会在1~4个回合之后再次尝试，第三次失败将意味着要再等待1~8个回合，以此类推。这种简练的方法使网络能够容纳各种潜在的竞争信号。因为最大延迟长度（2，4，8，16……）呈现一种指数级的递增，因此它被称为指数退避算法。
1700496894
1700496895
从1971年开始，指数退避算法就成为阿罗哈网络成功运作的一个重要组成部分，20世纪80年代，它被应用于传输控制协议，并成为互联网的一个重要组成部分。几十年后的现在，它仍然是如此重要。正如一篇有影响力的论文所言，“对于一个嵌入在未知拓扑网络中的传输端点，以及一个未知的、不可知的并不断变化的相互竞争的会话的群体，只有一个有可能有用的方案——指数退避算法”。
1700496896
1700496897
但该算法的其他用途表明了一些更规范、更深奥的内容。除了避免冲突，指数退避已经成为处理几乎所有网络故障或不可靠性的默认方式。例如，当你的电脑试图到达一个看起来马上就要瘫痪的网站时，它会使用指数退避算法，一秒后再试一次，几秒后再试一次，直到成功。这对每一个人都有好处：它可以防止瘫痪的主机服务器在恢复之后不会因为过多访问而又被再次攻击，同时防止你自己的机器浪费大量的精力做无用功。但有趣的是，它也不会强迫（或允许）你的机器完全放弃。
1700496898
1700496899
指数退避算法也是网络安全的一个重要组成部分，当你登录一个账户时，密码连续错误，就会受到指数倍增长的锁定周期的惩罚。这可以防止黑客对账户进行“字典攻击”，你可以用可能的密码一个个尝试登陆，直到最终密码正确，登陆成功。与此同时，它也解决了另一个问题：无论电脑账户的真正所有者是多么健忘，在一些任意的中断之后，他不会被永远锁定。
1700496900
1700496901
在人类社会中，我们倾向于采取一种政策，给人们一些有限的机会，然后完全放弃。三振出局，你出局了。这种模式在几乎任何需要宽恕、宽容或坚持的情况下都是默认的。简单地说，也许我们做错了。
1700496902
1700496903
我们的一个朋友最近在思考关于一个童伴的故事，她常因结束一段关系而陷入窘迫。要怎么做呢？决定一次又一次之后，她最后已经受够了，完全放弃了这段感情，这种行为似乎很武断且后果严重，不停地重新决定似乎过于天真，因为有可能会导致无穷无尽的失望和浪费时间。解决方案是：在邀请率上的指数退避。试着在一周内重新安排时间，然后是两周，然后是四周，然后是八周。“重发”率趋向于零，但你永远不需要完全放弃。
1700496904
1700496905
我们的另一个朋友在思考是否该为一个有毒瘾史的家庭成员提供住所和财政援助，她为此感到很痛苦。她不忍心放弃希望，希望他能幡然悔悟，又无法忍受自己再回头犹豫。但她也不能倾其所有满足他的一切要求——给他买衣服，为他做饭，为他重新开设银行账户，并每天早晨开车送他上班，在某个神秘和突然的时刻，他也许会拿着所有的钱消失，然后在几周后再打来一个电话，请求原谅及再次收留。这似乎是一个悖论，一个残酷而不可能的选择。
1700496906
1700496907
在这样的情况下，指数退避算法并不是灵丹妙药，但它确实能提供一种可能的方法。例如，需要一个指数增长的清醒时期，可以抑制再次违反家庭内的规则。这将使这位家庭成员要更加努力地证明自己是认真的回归，并且会保护主人免受循环往复的持续压力。也许最重要的是，主人永远不会告诉那位亲戚她已经放弃了他，要不他就无法挽救了。这提供了一种能够拥有有限的耐心和无限仁慈的方法。也许我们就不需要做选择了。
1700496908
1700496909
事实上，在美国，过去的十年见证了一场悄无声息的革命的开始，这场革命让司法系统本身就能处理好对毒品犯罪者的社会监控。这场革命是由一个名为“希望”的试点项目发起的，该项目采用了阿罗哈网络的指数避退原则。而这也是一个惊人的巧合，它也始于阿罗哈网络的诞生地——檀香山。
1700496910
1700496911
在向夏威夷第一巡回法院宣誓就职后不久，法官史蒂文·阿尔姆注意到了一个显著的模式。缓刑犯会多次违反他们的缓刑条款，巡回法官通常会使用他们的自由裁量权警告他们。但在某种程度上，也许在十几次或更多的违规之后，法官将决定严格执行，并将违反者判为有期徒刑。阿尔姆说：“我想，尝试改变别人的行为是一种疯狂的方式。”所以阿尔姆提出了一种几乎完全相反的想法。他提出，取消在未来的很长一段时间里进行的违规听证会，而是希望项目进行不确定的裁判，有时还会判决巨大的惩罚，这都是建立在即时的、预先设定好的惩罚基础上的，这种惩罚开始只会让违反者入狱一天，然后在每次犯规后都逐渐增加入狱时间。美国司法部的一项为期5年的研究报告称，希望项目中的缓刑犯被逮捕或直接撤销缓刑的可能性是普通缓刑犯的一半，他们吸毒的可能性降低72%。之后，有17个州效仿夏威夷的做法，推出了自己版本的希望项目。
1700496912
1700496913
1700496914
1700496915
1700496917
算法之美：指导工作与生活的算法 流量控制和拥塞避免
1700496918
1700496919
计算机网络设计首先集中于研究如何在不可靠的链接上建立可靠的传输。这些努力被证明是非常成功的，紧接着便出现了第二个问题：要确保已经过载的网络如何能够避免灾难性的崩溃。传输控制协议刚一解决数据从A点传到B点的问题，之后就遇到了阻塞问题。
1700496920
1700496921
最重要的早期预警发生在1986年，连接劳伦斯伯克利实验室和加州大学伯克利分校的一条线路被一个足球场长度的地段隔开。（在伯克利，这个地段恰好是一个足球场。）有一天，这条线上的带宽突然从每秒32000位下降到每秒40位。其中的受害者就包括劳伦斯伯克利实验室的范·雅各布森和加州大学伯克利分校的迈克尔·卡雷尔，“他们对这突如其来的带宽速度的剧烈下降现象很感兴趣，并着手调查它为什么会变得如此糟糕”。
1700496922
1700496923
与此同时，他们听到美国其他网络设计团队的抱怨，他们都遇到了同样的事。雅各布森开始研究其深层的代码。“协议中有什么错误吗？”他想，“这是在小规模的测试中进行的，然后突然之间它就崩溃了。”
1700496924
1700496925
电路交换和包交换之间最大的差异在于它们是如何处理拥塞的。在电路交换中，系统要么批准通道请求，要么如果请求不能被满足，就直接否定。这就是为什么，如果你在某个高峰时期尝试使用电话系统，可能会收到“特殊信息音”和“所有电路都很繁忙”的信息。
1700496926
1700496927
包交换是完全不同的。电话系统会变得忙碌，邮件系统会变慢。网络拥塞可以清楚地告诉发送者，还有多少其他的发送者，或者在某一时刻网络的拥挤程度，以及拥塞的量是如何不断变化的。因此，发送方和接收方不仅必须保持沟通，还必须进行元沟通：他们需要弄清楚数据发送的有多快。不知何故，组合的数据包流（没有明确的管理或协调）必须停止相互挡路，并迅速利用任何可用的新空间。
1700496928
1700496929
雅各布森和卡雷尔的调查结果是修订了一组流量控制和拥塞避免算法，这是40年来对传输控制协议最大的修改之一。
[
上一页 ]
[ :1.70049688e+09 ]
[
下一页 ]