SIGCOMM 2012 论文选读 - A Smart Pre-Classifier to Reduce Power Consumption of TCAMs for Multi-dimensional Packet Classification

session:
Session 7: Network Formalism and Algorithmics

abstract:
Ternary Content-Addressable Memories (TCAMs) has become the industrial standard for high-throughput packet classification. However, one major drawback of TCAMs is their high power consumption, which is becoming critical with the boom of data centers, the growing classifiers and the deployment of IPv6. In this paper, we propose a practical and efficient solution which introduces a smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification. We reduce the dimension of the problem through the pre-classifier which pre-classifies a packet on two header fields, source and destination IP addresses. We then return to the high dimension problem where only a small portion of a TCAM is activated and searched for a given packet. The smart pre-classifier is built in a way such that a given packet matches at most one entry in the pre-classifier, which make commodity TCAMs sufficient to implement the pre-classifier. Furthermore, each rule is stored only once in one of the TCAM blocks, which avoids rule replication. The presented solution uses commodity TCAMs, and the proposed algorithms are easy to implement. Our scheme achieves a median power reduction of 91% and an average power reduction of 88% on real and synthetic classifiers respectively.

阅读笔记:


计算机科学领域有一个很有趣的现象。一方面新的问题和技术层出不穷，另一方面，少数的几个问题被数年甚至数十年的研究着。不管是搞什么类型的网络，这几个问题始终绕不开。这样久经考验过的问题，往往是如同一堆泥沙中淘得的些许金粒一般珍贵，值得人们细细揣摩。
幸运地，也同时不幸地，这样的问题并不太多。网包分类问题，算是一个经典。
网包分类问题，作为网络安全领域的核心技术，已经被研究了十几年。2000年到2004年这段时间，是这个问题最火热的时候。那个时候，恰是网络设备硬件性能急剧上升的时代，爆炸式增长的带宽给网络处理带来了诸多新的诉求。作为规则查找类最为全面和典型的问题，网包分类得到大家的关注并不稀奇。经过略显平淡的沉寂后，近些年，这一话题开始被重新探讨起来。sigcomm10（Efficut）、11（TreeCAM）、12（SmartPC）连续三年都有这方面的文章。一方面，是随着从性能到智能的跨越，规则的复杂性、规模、内在的逻辑特性越来越复杂，另一方面，也是对规则查找的灵活性上要求越来越高。
自问题提出以来，大致就分为两大区域，一是利用软件算法的解决方案，即采用精妙设计的算法来满足诸多的限制和性能需求，部分算法也能部署到一些通用网络处理硬件平台，学术界讨论这方面的 文章颇多；另一类是基于硬件（多为CAM）的方案，这一类多为工业界所关注，要基于硬件的特殊结构，达到设计的目标。
今天要谈的这篇文章，是基于TCAM平台，研究的目标已经不是传统的如何提高分类速度，而是如何来减少TCAM的功耗。
我们知道，TCAM是个很神奇的东西，可以实现软件梦寐以求的并行匹配。激活单元越多，性能越强大，而激活单元越多，功耗也变成了问题。一般的，实现100K条规则匹配，达到1Gbps的吞吐量，大概功耗是15W。在能源问题颇受关注的今天，自然降低功耗有着诸多的好处。
那么，如何来降低功耗呢？很自然的想法，我查找的时候不用激活那么多单元不就可以了么？之前有文章采用软件预过滤，首先把规则集分为子集，然后网包只需要在子集中进行查找，这样激活的单元自然仅限制在子集中了。本文的思路大致类似，将TCAM划分为三部分，Pre-filter、Specific、General。Pre-filter是根据规则集生成的粗分类规则，相当于划分规则集为子集的规则（文中只考虑了源地址和目标地址两个域）。Specific则存储具体的各个子集。General是在划分中，部分可能出现在多个子集中的规则，比如很多wildcard的情况就容易出现。
因此，在最终的分类过程，只需要激活Pre-filter、少量的General和Specific块，自然省了功耗，从实验效果上来看，大概平均能变为原先功耗的10%左右，甚至更低。
这个方案遗留了几个比较有趣的问题，并没有进行进一步的探讨，一个是划分子集的效率问题。目前的方案采用了逐条规则比较的简单方案，一方面是复杂度高（最坏复杂度为O(n^2)），另外是不清楚优化度有多高。这里完全可以借鉴一些软件算法，比如优化度很高的各类Cuts、DBS/D^2BS等。另外，采用多级分类，自然可能导致分类的性能有所下降，比如latency，这方面并没有相关数据。最后，预分类性能的好坏跟规则集内部特性关系甚大，可能构造某些特殊规则集来让最终性能变得很差。当然，这一点很多现有算法都无法保障，除非能给出最坏的复杂度情况分析。

SIGCOMM 2012 论文选读 - Optimizing Cost and Performance for Content Multihoming

session:
Session 8: Streaming and Content Networking

abstract:
Many large content publishers usemultiple content distribution networks to deliver their content, and many commercial systems have become available to help a broader set of content publishers to benefit from using multiple distribution networks, which we refer to as content multihoming. In this paper, we conduct the first systematic study on optimizing content multihoming, by introducing novel algorithms to optimize both performance and cost for content multihoming. In particular, we design a novel, efficient algorithm to compute assignments of content objects to content distribution networks for content publishers, considering both cost and performance. We also design a novel, lightweight client adaptation algorithm executing at individual content viewers to achieve scalable, fine-grained, fast online adaptation to optimize the quality of experience (QoE) for individual viewers. We prove the optimality of our optimization algorithms and conduct systematic, extensive evaluations, using real charging data, content viewer demands, and performance data, to demonstrate the effectiveness of our algorithms. We show that our content multihoming algorithms reduce publishing cost by up to 40%. Our client algorithm executing in browsers reduces viewer QoE degradation by 51%.

阅读笔记

本文研究的是“content multihoming”问题，即如何利用多个CDN来高效、省钱地提供内容给用户。文章主要从两个方面（publisher、viewer）研究了在对于不同内容选择CDN时候的算法，来优化cost和performance。
publisher主要面临的问题是：多家CDN对不同的内容收费不同（流量方案、带宽方案、功能、性能），该如何选择一个CDN来发布内容？提出的解决算法称为CMO。
本地的viewer则面临着：内容在多家CDN的不同服务器上都有提供，该选择哪个来提高用户体验（Quality of Experience，QoE）？
文章将这些问题抽象为优化问题（常见思路）。
所建立的模型中，利用一个集中式的优化器（central Optimizer），来响应对CDN的内容请求。根据请求客户端功能的不同，将客户端分为被动客户端和主动客户端。前者对某个内容只能连接到一台CDN服务器，因此，只能在server端进行优化。后者对一个内容可能利用多个CDN服务器。这样，当某台服务器服务能力不够时，主动客户端还可以利用其它的服务器。
因此，研究包括两个方面的优化，一个是服务器端的优化，一个是主动客户端的优化。
服务端优化问题最终抽象的模型是一个带有约束条件的最小优化问题。优化目标是整体的cost，约束条件是满足用户需求（Sec 5.1）。解决这一类问题的一般思路是线性规划或者凸优化。然而，当问题的规模比较大的时候，线性规划计算代价不可接受；目标函数是凹函数，无法直接进行凸优化。因此，作者提出可以转化为其他问题（分配问题），并进一步提出了优化的分配方案（考虑分配后的输出空间，使用凹优化），降低解决问题的复杂度。
在转化过程中，也应用了凸优化和凹优化的理论。近些年，类似优化理论以及图论理论在网络领域应用的越来越多，但国内相关领域还比较少见这方面的研究文章。
在主动客户端上，还借用了TCP的AIMD机制来进行流量调整。
在实验方面，采用了来自真实CDN的大量traffic做模拟。验证了提出的方案确实能降低cost。
整体来看，本文将一个实际问题成功抽象为理论问题。虽然模型比较简单，但解决的过程中降低复杂度的手法值得借鉴，体现出比较深的数学功底，同时对于阅读者数学背景要求也比较高。但部分细节说的不是太清楚，例如引理1并没有给出证明。