第三章实现原则-USTC

《第三章实现原则-USTC》由会员分享，可在线阅读，更多相关《第三章实现原则-USTC（11页珍藏版）》请在金锄头文库上搜索。

1、标题页本章介绍作者归纳的 15 条实现原则。这些实现原则是从比较成功的协议实 现中归纳出来的。 其实许多实现者已经有意无意地使用了这些原则， 本章只是更 清楚地将它们表达出来，以使实现者可以更加主动地去运用它们。3.1 运用实现原则的例子：更新 TCAM下面用一个例子来说明为什么要使用原则。使用 TCAM 进行 IP 地址查找图 3.4是 TCAM 用于 IP 地址查找的例子。 IP 地址前缀是长度为 32比特的三 态字符串，通配符都在字符串的尾部。我们稍微改变一下表示法，使得* 表示任意数量的通配符。按照 TCAM 的工作原理以及最长前缀匹配的要求， TCAM 中的地址前缀必 须按照前缀长度

2、从大到小的顺序排列。路由表是动态变化的，如何在 TCAM 中添加或删除一条地址前缀，与此同 时仍然保持前缀长度从大到小的排列顺序？假定在图3.4的TCAM中需要添加一条新的前缀11*。假定TCAM是向上扩 展空间的，最朴素的方法是在长度为 2的前缀表项中插入前缀 11*，比如插在前 缀 0*的前面，为此，需将前缀 10*至前缀 010001*整体向上移动一个位置。对于 包含大量路由表项的路由器来说，这种更新的速度太慢了。有没有快一点的方法呢？我们再来看一下图 3.4的前缀排列方法：长度相同 的前缀排列在一起， 按照从长到短的顺序排列， 相同长度的前缀还按照大小进行 了排序。事实上，相同长度前缀

3、的顺序对于 TCAM 执行最长前缀匹配不是必须的， 因为一个 IP 地址不可能同时匹配两个相同长度的前缀。我们只需要按照前缀长 度进行排序，并不需要相同长度前缀之间排序， 因此这是一个可以利用的自由度。理解并利用自由度（ 1 ）利用该自由度，我们可将 11*插入到 00*和111*之间。当然，如果为此将 111* 及以上前缀向上移动一个位置， 则不会有多大优化的效果。 我们的想法是将 111* 移出，将 11*插入 1 1 1 *的位置，然后再为 111*寻找一个插入位置。 尽管这个问题 和原来的差不多，仍然要向 TCAM 中插入一条前缀，但是问题的规模缩小了一 点。理解并利用自由度（ 2）我

4、们可以将这个方法推广：。显然我们可以采用递归的思想来设计一个 算法。使用算法技术 采用递归实现的时候展开递归：。如果每一种长度的前缀都有（即最坏情况），需要（32-i）次访存。对于较小 的i，访存次数接近32。这个算法已经比朴素的算法好了很多，但是不是最好了 呢？还能减小最坏情况下的访存次数吗？（想一想）我们再来看这张图，这张图假设空闲空间在 TCAM 的顶部，实际上空闲空 间可以放在 TCAM 的任何地方，因此空闲空间的位置也是一个设计自由度。进一步利用自由度利用这个自由度，可以将空闲空间放在中间，比如放在长度为 16 的前缀项 后面，这时最坏情况下的访存次数可以减少一半。当然，空闲空间的数

5、量也可以是一个自由度，可以进一步减少最坏情况下的 访存次数。除了空闲空间的位置及数量之外，还有没有可以利用的自由度了呢？提示： 长的前缀是否一定要出现在短的前缀之前？比如，010*能否放在 111001*之前？完全可以，因为不可能有一个地址会同时匹配这两项。一个更复杂的自由度是，“如果ij，那么长度为i的前缀必须出现在长度为 j 的前缀之前”，这是一个充分条件，但不是必要的。一个不那么严格的要求是，“如果两个前缀P和Q可能匹配同一个地址，且 P比Q长，那么P必须出现在 Q 之前”。这样修改规范后，可以进一步减少最坏情况下的访存次数。缺点是提 高了复杂度。尽管以这么复杂的方法来减少访存次数有点不

6、划算， 但它指出了一个重要的 原则，即放宽要求。 我们经常将一个大的问题划分为较小的子问题， 然后将子问 题及相关的规范交由相关人员去解决。比如， TCAM 的硬件设计人员可能将更 新问题交给写微代码的人去完成， 要求将长的前缀放在短前缀的前面。 但是这个 规范可能不是解决原始问题的唯一方法，改变规范（ P3 放宽要求）可能产生更 有效的解决方案。 当然，这需要有具有好奇心和自信的设计人员， 他理解整个大 问题，并且足够勇敢来提出危险的问题。这个例子其实是告诉我们，要去寻找和利用自由度来优化实现。3.2 算法 vs 算法学如果认为这个例子基本上是算法层面上的，不要求系统思维，那么下面再举 一个

7、例子来说明算法与算法学的差异。举例：安全物证问题假设一个入侵检测系统通过统计流量来检测异常节点， 比如在一个测量周期 内发现一个节点向网络中的不同机器发送了 10 万个包，就确定这个节点在进行 端口扫描攻击。 当判定某个节点为攻击源时， 要将该节点在测量周期内发送的包 写入安全物证日志，供管理员进一步分析。如何检测攻击不是我们要讨论的，我们关心的是当判定某个节点为攻击源 时，如何得到它已经发送过的那些包。解决方案为实现此目的，我们维护一个包队列，当一个数据包被转发时，路由器将该 包放入队头。为限制队列的长度（路由器的内存是有限的） ，当队列满时，删除 队尾的包。该方案的主要困难是，当检测到一个

8、可疑流时，该流已经有大量的数据包在 队列中了， 并且和大量其它的包混在一起。 如何高效地从队列中找到属于可疑流 的所有包？最相素的方法是顺序搜索队列， 这显然非常低效。 我们一般会采用什么方法， 快速找到流 F 的数据包呢？教科书上的算法教科书上的算法会构造某个索引结构来快速搜索流 ID 。比如，我们可以维护 一个流ID的哈希表。但是该算法仍有问题。它需要额外的空间来维护哈希表和指针列表，而对于 高速实现来说存储空间是非常宝贵的。 它还增加了包处理的复杂度， 需要维护哈 希表。这个算法的问题在哪里？就是我们潜意识里假设每一个流都有可能是可疑 流，因此，每一个包到来时都将其分到相应的流中。这样，

9、一旦某个流被认定是 可疑流，立即就可以得到属于该流的所有数据包。但事实上，可疑流只是少数， 这里面我们做了许多无用的处理， 将属于正常流的包也都组织在哈希表中了。 比 如，10万个流中只有一个流是异常的，但我们将 10 万个流的包都做了归类，这 是显而易见的浪费。那么我们怎么可以避免做无用功呢？联想到我们前面举过的例子 （检测异常URL）,我们可以采用推迟计算来解决这个问题。系统的解决方案 基本思想：将判断一个包是否属于可疑流这件事情，拖到不得不做（发现可 疑流，且包将移出队列）时再去做。什么时候不得不做？（ 1）发现了可疑流；（2）数据包将移出队列令路由器转发包时统计每个流（节点）发送的包数

10、。当流 F 发送的包数超过一个阈值（如10万）时，将流F添加到可疑节点列表中。当可疑节点列表非空 且队列满时， 每当往队列中添加一个包， 就从队尾中移出一个包， 判断该包是否 属于F。若属于F,将该包（或指针）拷贝到物证日志中；若否，将该包丢弃。该方案不需要维护哈希表和指针列表，节省了大量的存储空间和计算开销。3.3 十五条设计原则第一章的例子（设计一个检测异常 URL 的芯片）和前面这两个例子给了我 们有关网络算法学的一些初步体验， 下面介绍作者归纳的 15条原则，这 15条原 则我们会不断地使用。这 15 条原则可以分为三类：1）系统原则：第 1-5 条原则利用了系统思想，它将系统看成是由

11、子系统构 成，而不是一个黑盒子。2）兼顾模块化和效率：第 6-10 条原则允许保留复杂系统的模块化，与此同 时给出提高性能的方法。3）加速：第 11-15 条原则提出了加速某个关键功能的技术（仅考虑该功能 本身）。每条原则会用一个例子来说明，具体细节将在后续章节中讨论。P1:避免常见情形中的明显浪费在一个系统中，在一些特殊的操作序列中可能存在资源浪费。如果这些模式 经常出现，就有必要去除这个浪费，这样可以从整体上降低系统的开销。编译器的例子:消除重复的子表达式。经典的网络例子:操作系统和用户空间之间多次数据包拷贝（第五章介绍） 。 这条原则看起来容易做起来难，最难的是如何发现明显的浪费。这里，

12、每一 步操作孤立地来看没有浪费， 是由于特殊的操作序列导致了浪费。 显然，暴露的 上下文越大，越可能发现产生浪费的操作序列，因而这里需要系统思维。P3:放宽系统要求当一个系统从上到下进行设计时，先将功能在子系统间划分。在确定了子系 统的需求和接口后， 再设计每一个子系统。 当遇到实现困难时， 有些方面的要求 要改变。如图 3.8所示，一个系统由两个子系统组成，子系统 2 对子系统 1 的实现要 求称为规范S。如果子系统1实现困难，有时可以降低对其的实现要求，要求子 系统 1 遵循较为宽松的规范 W。在第 1 章的例子中，由于设计除法电路（ subsystem 1）比较复杂，改用移位 代替除法，

13、也就是放宽了子系统1的实现规范（S-W）:子系统1只需实现移位 操作而不是任意的除法操作。其代价是子系统 2 必须遵循更强的特性（ P-Q）： 门限须用 2 的幂次表示，而不是一个任意的浮点数。P3a：牺牲确定性换时间超级节点的检测：确定性的方法是统计以每一个节点作为源（或目的）的数 据包数量，这需要检查每个包的源地址（或目的地址）进行统计，这在高速网络 中是做不到的。 随机化方法是每隔一定数量的包统计一次， 虽然不能保证百分之 百正确，但在很大概率上是正确的。P3b:牺牲精度换时间图像压缩是一种很耗时的操作，对于实时视频要求压缩速度很快。离散余弦 变换可将信号能量集中在少数几个变换系数上，

14、然后只需对主要的变换系数进行 量化编码，达到快速压缩的目的。但是图像质量（精度）会受到一些影响。P3c：在空间中移动计算在空间中移动计算是指将计算从一个子系统移动到另一个子系统 （注意和前 两条原则的不同）。比如，数据包分片会影响路由器的吞吐量， IPv6 将分片的功 能从路由器移到了源节点。为此，源节点主动探测端到端路径上的 MTU ，确定 合适的分组大小， 路由器不再提供分片的功能。 这样就简化了路由器的实现。 当 然，这里的移动已经超出了一个网络设备的限制， 是在整个网络中的移动 （如果 将网络看成一个系统，则路由器、主机就是子系统） 。P4:利用系统组件系统设计采用黑盒视图，就是将系统

15、分解为若干子系统，然后独立地设计每 一个子系统， 而不去关心其它子系统的内部细节。 尽管这种自顶向下的方法具有 很好的模块化， 但实际上，性能关键的组件在构建时通常部分地采用 “自底向上” 的方法构建。比如，要在一个硬件上设计算法，通常要让算法适应硬件的特性， 而不是让硬件来适应算法。P4b:用空间换速度一个显而易见的技术是用较大的空间来减少计算时间， 比如将函数计算变为 查表。一个不那么显而易见的技术是用较小的空间来提高速度。比如，把一个很大 的数据结构压缩到可以放入cache,或者大部分可以放入cache，可以极大地提升 系统速度。当一个表的规模很大时，该技术特别有效。有人可能会问，空间和

16、时间都节省了，怎么会有这样的好事？事实上，计算 复杂度是增加的。比如，访问压缩的数据结构，其处理复杂度是提高的。但由于 现代处理器的计算速度比访存速度快得多得多，在多核处理器上这个差距更大。 在这种情况下， 适当增加计算复杂度并不会使处理器成为瓶颈， 却因为提升了访 存速度使得系统整体性能得到提升。 这是实践中用得很多的一种优化技术。 这也 启示我们， 在优化系统时一定要搞清楚瓶颈在什么地方， 如果计算不是瓶颈， 那么减少计算并不能提高系统速度如果 P4 原则使用过度，系统的模块化将受到损害。为此，需要注意两个问 题：（1）如果我们利用其它系统特性只是为了提高性能，那么对那些系统特性 的改变应当只影响性能，不影响正确性。（2）我们仅对确认为是系