互动科普

用编码终结网络塞车

撰文  米歇尔·埃弗罗斯（Michelle Effros）

         拉尔夫·克特尔（Ralf Koetter）

         米里埃尔·梅达尔（Muriel Médard）

翻译  郭凯声

新的技术革命往往得益于科学天才电光石火般的惊人灵感，现代通信系统的发展史上也不乏这样的例子。60多年前，数学家兼工程师克劳德·E·香农（Claude E. Shannon）提出的关于数据压缩与可靠传输的理论，推动了一场革命，崭新的通信数学理论（现在称为信息论）由此诞生。今天，无论是在互联网、有线与无线电话网中，还是从硬盘、CD、DVD到闪存的各种存储装置中，香农定理及相关理论的影响都无处不在。

在香农那个时代，通信电话线一般用于传送单次通话；现在，越来越多的信息是在共享网络（如互联网）上传送，即众多用户同时使用同一传输介质，如电缆、光纤或无线电波等进行通信。共享网络蕴藏着巨大潜力，能使通信系统变得更加实用高效，但它也造成了众多用户争抢公共资源的局面。如果有太多用户想同时连接一个歌曲下载服务器或登录同一个无线网点，那网络很可能要被挤爆了。

当务之急是实现平稳有序的共享。网络运营商通常采用增加资源供给量的方法来改善僧多粥少的局面，但不足以解决根本问题。现在的铜导线、电缆和光纤虽然能为商业和小区用户提供较高的带宽，但铺设费用相当昂贵，升级改造也十分麻烦。超高宽带和多天线传输系统可以增加无线网络覆盖的用户数量，依然难以满足与日俱增的需求。

因此，增加带宽并不能根本解决问题，还需要想办法提升网络传输效率。目前，互联网和其他共享网络上传送的信息是通过路由器（router，一种交换装置，在多条链路汇聚的网络节点处负责转接信息）中转的。进入路由器的信息被分转到通往目的地的各条链路上。然而，如果想要提高效率，路由器真是网络交接点上最合适的设备吗？“交换”真是正确的操作吗？

长期以来，几乎没有人考虑此类问题，直到7年前，情况才有所改变。德国比勒费尔德大学的鲁道夫·阿尔斯韦德（Rudolf Ahlswede）以及中国香港中文大学的蔡宁（Ning Cai）、李硕彦（Shuo-Yen Robert Li）和杨伟豪（Raymond W．Yeung）等人联合发表了具有开拓意义的研究论文，提出了一套在共享网络上传送信息的全新思路：“网络编码”。按照这一方法，传统的路由器将被编码器所取代，但编码器传送的将是信息的线索而非信息本身。接收方接收到这些线索之后，只需要适当组合，便可推断出原始信息。

网络编码现在仍处于研究阶段。虽然乍听起来这一方法不合常理，但它的确具有大大加快通信速度并提高可靠性的潜力，极有可能引发通信领域的下一场革命。当然，研究人员也在探索用其他方法来提高通信效率。不过就我们所知，这些方法往往只是对现有方法的一些补充扩展而已。

消除传统传输方式的瓶颈

阿尔斯韦德和同事提出的这个方案，借鉴了香农的一项创意，即传送信息的线索可能比直接传送信息本身更有用。同时他们也意识到，只要收集了足够多的线索，接收方就能够推断出原始信息。注意！这里只是要求“足够多”，也就是说，接收方无须收到发送方发出的全部线索，某类线索可以用另一类线索来代替。最重要的是，收到的各类线索组合起来，能够得知原始信息的内容（如果接收方事先获知生成线索的规则，或者线索本身就包含了关于如何使用线索的说明，那么接收方就能够解读出线索的含意）。

如果把传统的网络看作公路上的车道，信息流中的一个个二进制数字（即比特）就是公路上奔驰的一辆辆汽车。网络编码打破了这种传统概念。不过，了解这种车流模型，将有助于我们理解新方案的运作原理，并弄清它为何具有如此大的潜力。

香农从数学上证明，每个信息传输通道都有一定的容量（即给定时间范围内它能传送的信息总量），只要不超出这一容量，信息就能够可靠地传送。车道的容量（即通过能力）是每秒钟能够安全地通过多少辆汽车，只要车流量不超过道路的通过能力，在道路一端驶入的汽车就必定可以安全地从道路另一端驶出（当然前提是没有发生车祸）。基于这个车流模型，工程师们打造出了日益复杂的通信系统。在这类系统中，每次通话要占用一条单独的“道路”； 传统电话线上传送的两个通话绝不会在同一时间以相同频率共享同一条线路。

计算机网络（尤其是互联网）实际是一个庞大的道路网，无数条道路在其中时而汇合、时而分岔、时而交叉，构成错综复杂的超级迷宫。从一台电脑发送到另一台电脑的信息通常要经过好几条道路才能到达目的地。一条信息中的全部数据位（即比特）被打包成若干个数据包，数据包就相当于信息高速公路上的拼车组合或公共汽车，每个数据包上都标明了它预定的目的地。路由器就位于道路的交叉点上，它们负责检查每个数据包的包头，然后把数据包转发到它应该去的地方。

讽刺的是，这个当初推动现代通信系统走向成熟的车流模型，如今却成了阻碍进步的绊脚石。毕竟比特并不是汽车，两辆汽车如果同时想过一座窄桥，除了依次通过以外别无他法；数据位则不同，当两个数据位同时到达网络中的瓶颈地段时，它们可以有更多的选择。数据位的这一特点使网络编码有了大显身手的机会。

网络编码工作原理

为了弄清楚数据位在到达传输瓶颈时可以有些什么选择，我们来看看一个假想的六节点数字网络（参见本页插图）。记住，在电脑中所有信息都是用一串二进制代码表示的。假定这个网络中的每条链路（即“道路”）每秒可传送1比特（不是1就是0）的信息，且只能沿链路旁边的箭头所示的方向传送。现在节点A处的网友埃米打算以1比特/秒的速率给节点D处的网友达娜发送消息；恰好就在这时，节点B处的网友本也打算以同样的速率给节点C处的网友卡尔发送消息。在不超负荷的前提下，网络能否同时满足埃米和本的需求呢？

如果用路由器系统来实现传送，希望是相当渺茫的。埃米到达娜的发信路径和本到卡尔的发信路径都必须经过链路5，这条链路对他们来说就相当于一座单车道的独木桥。独木桥的起点处是节点E，这个节点上的路由器每秒接收到两个比特的数据（分别来自于链路2和链路3），但由于链路5的容量只有1比特，路由器每秒只能让1比特的数据通过链路5。在车流模型中，这样的瓶颈将导致网络严重堵塞，随着时间的推移，聚集在瓶颈处等候通过的数据位将越来越多。

新的方法则用编码器取代了路由器，编码器控制信息流的手段比交警控制车流的手段可高明多了，它不是把聚集在瓶颈处的数据流一个比特一个比特地依次转发出去，而是发送另一类完全不同的信息。例如，它可以统计出某一秒内到达瓶颈的“1”的总数：如果此总数为偶数，它就发送一个“0”；如果为奇数，则发送“1”。在上面提到的这个最简单的例子中，如果节点E从链路2接收到1， 同时又从链路3接收到0， 那么编码器将发送“1” 经过链路5。如果节点E从链路2和链路3接收到的数据都是0或都是1，那么链路5传送的将是“0”。然后路由器F将链路5传送过来的这一数据分别沿链路6和链路7分别发送给达娜和卡尔。

这一方法其实就是把同时到达节点E的每两个数据位整合成一个，并用它顶替原始数据发送出去。乍一看，这种方法显得有点可笑——我们提出的这种编码器所做的事情，无异于打电话时把两段通话混在一起发送出去，结果当然是什么也听不清。在很长一段时期内，这一构想都被束之高阁。

但有时候，恰恰是异想天开能带来真正的革新。把两段数据流合二为一，或许不能帮你完美解读出它们原来的内容，但至少提供了与两者都有关的一些线索。假设我们又通过链路1将埃米的信息传送给卡尔，同时通过链路4将本的信息传送给达娜。注意，传送这两项信息所使用的网络资源（即链路1与链路4），对于满足埃米和本的传输要求是没有什么用处的，反正都是闲着。这样卡尔所在的节点既收到了埃米发来的信息，同时又从链路6传来的数据中，随时得知埃米和本发出的信息内，1的个数是偶数还是奇数。如果卡尔的节点还“知道” 链路5起点处的编码器所依据的编码规则，或者它能够从接收到的数据本身推断出这些规则，那么上述两项线索合起来，就能使它破解出本所发来的信息。同理，达娜的节点也可如法炮制，解读出埃米发来的信息。

优势尽显

这个方案可以一举两得，这在过去的车流模式中是难以想象的。首先，某一节点发出的数据可以同时沿两条路径传送，而汽车显然分身乏术；其次，同时抵达某一瓶颈地段起点的两个数据流可以合并成一个，但同时驶到一座窄桥的两辆汽车显然不能捏成一辆，只能是其中一辆停下来等另一辆过去后才能过桥。

上面这个六节点模型，是阿尔斯韦德及其同事在2000年首次提出的新构想的简化版本，而我们以此模型为例所阐述的数据处理方案，有助于消除网络堵塞，无须增添新的线路就可提高网络的传输能力。单靠路由器，我们这个六节点网络只能维持平均0.5比特/秒的同步传输速度。（因为两项互相争路的传输任务必须共用链路5，所以对于其中每一项任务来说，有效数据传输速率就是2秒1比特，即0.5比特/秒。）而借助于网络编码，同样的系统可以支持1比特/秒的同步传输。因此，在这个例子中，网络编码技术使网络的传输能力翻了一番。

网络编码技术有时会使网络传输能力获得更大幅度的提升，而有时却不会，但它绝对不会降低网速，最糟也不过就是完全模拟路由器系统的行为而已。同时，对于较大的网络，它还能提高传输的可靠性并加强网络安全防御能力，其原因在于信息线索具有通用性，这样即使携载线索的数据包有部分丢失也不会造成问题。

组播网的启示

到现在为止，关于如何实现网络编码的研究工作大部分集中在组播网络（multicast network）上。在这种网络中，所有的接收方需要收到相同的信息。例如，在多人在线游戏中，每当参加游戏的某一方有所动作，网络就必须通过组播方式，立即更新每一方的游戏画面。网上的广播视频节目或直播体育赛事，以及向大群客户发布新软件，也是通过组播网实现的。

目前，组播网络仍在使用路由器，再次借用车流的比喻，将有助于我们认识到，为何设计这类系统通常都是极其棘手的任务。

想象一下，美国的公路上到处都是汽车，而每台路由器就是一位站在路口指挥车流的交警。驶到路口的汽车必须呆在先到车辆的后面排队等候。交警（即路由器）的任务是依次确定每辆车的目的地，并引导它们驶上自己该去的那条路。系统设计的要求是，每台路由器在指挥调度车流时，不但要使该路口的每辆车尽快到达目的地，而且还要让全国的公路网提高整体效率，让尽可能多的驾驶员感到满意。

一位总设计师即使握有全国所有道路的详尽地图，恐怕也很难确定每台路由器应该遵循的最佳策略。公路网的情况通常千变万化，这使得问题更加棘手。高峰时段的车流暴增、道路维修、突发车祸以及公路上举行的赛事等等，都意味着道路网状况和相应的需求是瞬息万变的。

或许我们会凭直觉认为，设计一个采用网络编码技术的系统应该更难，因为必须将更多的选择考虑进来。比如说，一个节点可以不对接收到的数据进行任何加工而直接发送，也可以把接收到的两个或两个以上的数据流混合后再发送，数据流混合的方式也不止一种。此外，不同的节点还可以采用不同的算法。

幸运的是，这种逻辑存在缺陷。有时候选项越多反而越简单。如果不使用网络编码，组播网络的设计者就必须找到从发送点到每个接收点所有可能的路径，然后确定网络能够同时支持其中的多少条路径。要找出所有的路径组合方式，并加以检验，即使是最简单的网络，难度也大得足以令人叫苦连天。

反观使用了网络编码的组播系统，设计相当简单：编码网络仅需要运用加法和乘法两种简单的数学运算。此外，在选择网络中每台编码器所要设置的函数（即规则）时，即使不考虑所传送的信息及其他的编码函数，也不知道网络的整体布局，整个系统仍然有很高的几率会在最佳性能下运行。就算系统随时可能出现变化（例如无线网络和可重构网络就是这样），网络还是能继续保持最佳运行状态而无须重新设计。

未来的网络

因此，如果用编码器取代路由器，网络的运行状态将彻底改观。我们发送的信息穿越网络的方式将有所改变：它们不仅将和其他信息共用“道路”， 而且可能与来自其他信息源的数据流紧密地“纠缠”在一起。有人可能担心这种“纠缠”（entanglement）会危及信息安全。不过，更可能出现的情况是，穿过网络的信息将变成一种不可能在本地电脑上破解的代数流。网络用户们无意中形成了一种互利互惠的合作关系，结果不仅是数据下载更快，而且对于无线网络来说，还可以进一步节能。（由于每次无线传输都要消耗一定电力，一个节点可以把预定要发送给几个网上邻居的信息整合在一起，只发送一次便完事，自然就降低了用电量。）

此外，视频下载迟缓和手机通话丢失现象将大大减少。在互联网上，路由器发生故障或停机维护的情况可谓司空见惯，数据包丢失更是家常便饭。网友们上网时常常要反复刷新网页，有时登录一个网站慢如龟步，原因就在于此。网络编码将提高通信的可靠性，因为它不要求每项线索都被传送。

通过挖掘现有频道的潜力，网络管理员无须增加通信频道，就可让用户们享受到诸如此类的好处。网络编码将与其他各种通信技术互相配合，取长补短，使用户能够最充分地利用网络资源。

有时用户会察觉到网络编码在悄悄运行，因为它可能改变某些常用网络服务（如P2P下载）的运作方式。现在某网友若想下载一份文档，就在要网上寻找另一位电脑中存有此文档的网友合作。而在网络编码系统中，文档将不再整体存放，也不是被分成若干个可辨认的部分分开存放。

用户要获得所需文档，就必须找到线索。不过他们用不着亲自寻找，他们的电脑或手机会向网络发送一个请求，即可启动电脑或本地服务器，在网络上搜索与文档相关的线索。这些线索是由源文件通过代数运算重新整合成的信息片段，可以帮助我们恢复原始文件。为了恢复文档，服务器或用户的电脑需要解一组代数方程，而不是简单地把各项线索凑在一起。当然，大多数人自始至终都不知道幕后的这些运算过程，这就好比我们在打手机时，对手机内纠错代码间的复杂演算毫无所知一样。

美国军方已经意识到网络编码的鲁棒性（robustness，即系统在异常或危险情况下仍能正常运转，不致崩溃的特性），已经拨款研究网络编码技术在移动自组网（Mobile Ad Hoc Networks，又称为移动Ad Hoc网络）中的应用。移动自组网是一类随建随撤的“速成”网络，在瞬息万变的场合（如战场），有很大的实用价值。在战场上，保证部队联络的畅通可靠是取胜的关键之一，而要在炮火连天的环境中搭建和维护光纤网或手机发射塔显然非常困难。自组网把每位士兵的无线通信装置都变成通信系统中的一个节点，每个节点都尽力寻找邻近的节点并建立连接。这些连接合起来构成了网络的各条链路。每个节点既能发送又能接收信息，也可作为信息的中转站。这一方法极大地增强了网络的通信能力，使它远远超出单个节点的传输距离。移动自组网还是一种高度灵活的网络，可随用户移动，根据需要不断重新配置或建立连接。

与此同时，研究人员也在细细考量实现这项技术所面临的障碍。把路由器型通信系统改造成网络编码型通信系统，其实是所有问题中比较容易的一个。这一转换可以通过渐进式变革来完成，最好不要突然大动干戈。有的路由器只要重新设置一下就行了，其他一些无法执行编码操作的路由器应被逐步更换。

更大的挑战，是解决编码器取代路由器后引发的一些新问题。例如，如果接收节点能够搜集足够多的线索，从中找出需要的数据，把信息混合起来就成为一个好主意。在组播网络中的确是如此，但在一般情况下恐怕就不是这样了。此外，在某些场合中（例如网络传送的是多个组播信息时），把信息混合起来，会让用户难以提取出正确的输出。那么，当多重连接共用同一个网络时，节点如何确定哪些信息可以混合，哪些信息不可以混合呢？无线网络中的网络编码在哪些方面有别于有线网络中的网络编码呢？在安全性方面网络编码具有哪些优势，又将产生什么样的影响呢？如果某人的数据必定要与其他用户的数据混合，那么这种通信服务该如何收费呢？在横跨全球的合作研究中，我和其他许多研究人员正在反复思考如何破解这些难题。通信网已经与无数人的生活息息相关，我们的任务就是全力以赴地改造通信网，使它的性能再次跃升到一个新的高度。