Secret of Earning an Engineering Phd Degree

Created at July 8, 2013

Engineering is always decoupling things, making it as simple as possible with a run-able solution.

However, research is mostly of a different style.
Not only to show how it works, but also to know why.
Abstract into theory, and demonstrate with scenarios.

Hence, the secret of earning an engineering Phd degree is to master both, and keep clear to pick the correct one at correct time.


Updated at Sep 18, 2013
So what exactly a Phd should be?
I think Phd = Dreamer + Engineer + Artist + Orator.

与网络相关的几个Law

Sarnoff's law
广播网络的价值跟用户数成正比（the value of a broadcast network is directly proportional to the number of viewers.）。
这个很容易理解。在传统广播网络模式下，每增加一个用户，网络的影响力就增加1。
这种网络的代表有电视网、广播网等。

Metcalfe's Law
网络标准的价值随连接的节点数增加呈平方增长（ the value of a telecommunications network is proportional to the square of the number of connected users of the system）。
在通信/计算机网络，这个定律很容易被理解。因为网络里用户会跟其他用户进行交互。每增加一个节点，通信和可提供的容量会增加一个跟网络原先节点数线性的规模。可能存在的连接数目跟节点数N的关系是（N(N-1)/2）。
这种网络的代表有移动通信网、互联网等。

Reed's law
网络的效用随网络规模增加呈指数增长（the utility of large networks, particularly social networks, can scale exponentially with the size of the network.）。
这里网络更专注在社交网络上。这里的指数增长源自网络中可能存在的子组数目是指数增长的（2^N - N - 1）。
这种网络的代表有目前facebook以及类似模式的网站。

以上（数学）规律很好地解释了不同类型网络的增长速度的差异。即便传统的电视、广播网已经发展的如此普及，互联网还是以势不可挡的势头快速发展了起来；即便传统互联网网站做得如火如荼，现代的社交化网站还是在一夜之间改变了格局。

世界上没有偶然的事情，背后都有其必然的规律。而发现和合理利用这些规律，正是有“技术含量”的人应该孜孜不倦追求的。

其他一些有意思的定律。

Pareto distribution
幂律，是指网络中的某些量分布呈现幂律的形式。比如节点的度、链路的使用，社交网络中的交互等。
通俗的一些说法包括二八定律等。
其实该定律还可以推广到非网络的领域，比如说人类居住城市大小的分布、自然界中石头的大小，甚至硬盘的错误等等，都符合该定律。
这个定律背后的深层次含义其实是正态分布。
其他相关的定律还有Zipf's law、Long Tail law等。

NSDI 2012 论文选读 - Header space analysis: Static checking for networks

abstract:

Today’s networks typically carry or deploy dozens of protocols and mechanisms simultaneously such as MPLS, NAT, ACLs and route redistribution. Even when individual protocols function correctly, failures can arise from the complex interactions of their aggregate, requiring network administrators to be masters of detail. Our goal is to automatically find an important class of failures, regardless of the protocols running, for both operational and experimental networks.

To this end we developed a general and protocol-agnostic framework, called Header Space Analysis (HSA). Our formalism allows us to statically check network specifications and configurations to identify an important class of failures such as ReachabilityFailures, Forwarding Loops and Traffic Isolation and Leakage problems. In HSA, protocol header fields are not first class entities; instead we look at the entire packet header as a concatenation of bits without any associated meaning. Each packet is a point in the {0, 1}^L space where L is the maximum length of a packet header, and networking boxes transform packets from one point in the space to another point or set of points (multicast).

We created a library of tools, called Hassel, to implement our framework, and used it to analyze a variety of networks and protocols. Hassel was used to analyze the Stanford University backbone network, and found all the forwarding loops in less than 10 minutes, and verified reachability constraints between two subnets in 13 seconds. It also found a large and complex loop in an experimental loose source routing protocol in 4 minutes.

阅读笔记：

有一种论文，看似得来轻松，却是功到自然；看似设计简单，却是大巧不工。这样的文章一出，即便学霸、专家看了，也往往觉得眼前一亮。倘若又能联系实际，碰巧解决一两个工程问题，那就更加站得住脚了，哪怕顶级会议也是问题不大。msra的Chuanxiong Guo曾发过一些类似风格的文章，后来功力日深，不常走这类轻巧路线了。

今天读的这篇论文，无疑可称得上精妙。

sdn的概念提出早期，大家一起讨论，这玩意能干啥，当时就有人提出能做diagnosis，大家的思路就是说一旦发生了问题，通过计算能快速的发现或者解决问题。这样的工作现在也有一些成果，但都是靠solid的设计和实现取胜。这篇文章中要解决的问题，则更加大胆。给我你的网络配置（转发策略等）情况，我能告诉你有哪些问题，比如，网络中是否存在环路？并给其了一个好听的名字，叫做Header Space Analysis (HSA)。

问题提出，先别看别人咋做的，自己想一想，要解决这个问题其实技术上来说并无太大难度，如果能拿到所有节点的配置，把所有可能情况遍历一遍即可。这样做，就落入传统的解决工程问题的一般套路了。能否拔高点？这也是本文最大的亮点。网包在网络中转发，无非就是个空间变换。包头104位（5元），最多就是104维嘛。转发无非就是从一个子空间，映射到了另一个子空间。先别管这样直接粗糙的定义是否合适，但问题一下子便拔高了，有了数学上的意义。然后再自然的定义一些基本概念，一个很好的数学问题便被提出了。

之后，文章中还实现了一些简单的工具，并分析了实际的一个网络，用这些工具发现的一些可能的问题。当然，这些问题可能只是在理论意义上存在的。有理有据，这正是大家写论文该模仿的典范！

当然，原创性太强的工作，自然解决的不会那么完美，仍有很多坑等着大家去继续深入。

比如：

目前只能分析static的情况；

只能解决映射到一个点的问题；

计算复杂度如何快速降低？

能否扩展到考虑payload的情况。

解决了这些问题，这种分析的方法才会有更多的实践意义，才会被用到更多的领域，特别是安全领域。

ref: https://www.usenix.org/conference/nsdi12/header-space-analysis-static-checking-networks

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并没有给出证明。

SIGCOMM 2012 论文选读 - Surviving Failures in Bandwidth-Constrained Datacenters

Session:
Session 10: Data Centers: Network Resilience

Abstract:
Datacenter networks have been designed to tolerate failures of network equipment and provide sufficient bandwidth.  In practice, however, failures and maintenance of networking and power equipment often make tens to thousands of servers unavailable, and network congestion can increase service latency. Unfortunately, there exists an inherent tradeoff between achieving high fault tolerance and reducing bandwidth usage in network core; spreading servers across fault domains improves fault tolerance.

阅读笔记：

这篇文章延续了MS一贯的风格，从实践中发掘有趣的问题，提升到理论高度，并提出初步解法。

文章关注的问题是不太容易想到的。去年的SIGCOMM中有篇文章讨论了数据中心中如何进行资源分配，以降低核心网的带宽压力。本文敏锐的指出，降低带宽压力和提高容错性之间往往存在矛盾。要理解这个矛盾，就要从实际出发，分析网络流量。这也是写文章的一般思路。

首先，文章通过分析bing数据中心中的流量数据，发现了一些有趣的pattern。数据中心中的网络流量多发生在同一类服务之内，而非之间，并且存在着不均匀的情况。例如只有2%的服务对（service pairs）之间存在流量，98%的服务对之间不需要流量交换。同时，在发生的流量中，0.1%的服务对产生了60%的流量，4.8%的服务对产生了99%的流量。

有了这个观察，就可以给出一个直观的例子。例如一种应用的多个服务器，如果放在同一个TOR中，大量流量仅发生在内部，这降低了核心网的带宽压力。但是，一旦TOR的交换机发生故障，则所有服务器都无法提供服务；反之，如果分布在多个TOR，会提高容错性能，但需要利用核心网交换大量数据。

问题提出后，便可以进行建模。这是个典型的多目标优化问题。

进行优化的目标主要包括两点，容错（FT）、带宽（BW）。

其中容错又包括了网络、电力、制冷等多个方面，并提出了容错域和最坏存活性能（即发生最坏情况的单点故障后的服务率）。

带宽则主要是降低核心网的带宽压力。同时要考虑到实际的限制。

最后，虚拟机的迁移（#M）也是个很费资源的行为，所以要尽量的少迁移现有的虚拟机，将其作为限制条件。

分析单一目标的FT优化和BW优化自身都是NP-hard（一个是最大独立集问题，一个是最小割问题），因此，本文考虑的多目标自然也是很难的。这里的思路主要两点，一个是解决FT问题可以采用凸优化，局部解就是全局最优解了。同时由于流量分布十分稀疏，可能存在一些能利用的地方。比如迁移可能并不太改变BW。

文章提出了两套优化框架，FT + #M，以及FT + BW + #M。

考虑FT + #M，提出一个FTC（FT的惩罚函数）函数，是个凸优化，将存在不同TOR上的不同服务之间的虚拟机进行贪婪的swap（swap可以保证不同服务对应的虚拟机个数不变，并同时可以不提高对核心网的压力），尽量将它们分散在不同的TOR上，即可提高FT。

而对于FT + BW + #M，则没有那么简单，并不能保证取得比较优的解。可以通过一个系数\alpha来tradeoff两者。对这个问题也提出了两种算法。第一种算法是CUT+FT+BW的思路是首先，我们采用最小割算法来实现最小的BW，之后，通过迁移虚拟机试图最小化FTC（提高FT），并尽量降低BW的提高。第二种算法是FT+BW算法，仅执行第二步，在迁移虚拟机的时候同时考虑FTC和带宽的惩罚，最小化\delta{} FTC + \alpha{} \delta{}BW。

最后，实验在四个产品级的cluster上进行。结果表明CUT+FT+BW算法效果最好，降低了30-60%的核心网带宽，提高了40%-120%的容错性能。

总结下，本文最大的亮点，是第一次将带宽利用率和容错性结合到了一起进行讨论，同时，建模分析和解决思路也都有可取之处（设计符合凸优化的FTC）。当然，文章中使用的实际数据中心的采集数据也是不小的加分点。

NSDI 2011论文选读

1、ServerSwitch: A Programmable and High Performance Platform for Data Center Networks

作者：MSRA

概述：用通用芯片为未来DCN平台提供更灵活、可编程且快速的交换，并支持流控等功能；

目前问题：软件交换仍然不够快，且延迟大；fpga-based编程复杂度高，且昂贵；

基础：通用交换芯片已经支持编程；PCI-E接口提供CPU和IO子系统之间微秒级延迟

架构

 

2、Efficiently Measuring Bandwidth at All Time Scales

作者：UCSD和Cisco

概述：解决细粒度的（高速）带宽抖动的测量问题；

目前方案问题：要么内存占用太多，要么是为某个粒度或目的设计，不能在全尺度上测量；

思路：提出两个算法，一是在不同尺度（指数比例）上用计数器统计，一是根据带宽动态分块，速率越高，自然需要分的块越多，在统一时间单元上块就越窄。

3、ETTM: A Scalable Fault Tolerant Network Manager

作者：University of Washington

概述：提出一种scale、fault tolerant、包粒度上的网络管理机制

目前方案问题：middle box功能单一、位置局限在网络边缘；of不支持复杂的包处理，依赖支持of的交换机

基础：交换机可控性增强、终端支持安全控件等

思路：终端安装软件，利用分布式的交互来实现逻辑上的集中控制

架构：

4、Design, Implementation and Evaluation of Congestion Control for Multipath TCP

作者：University College London

概述：为Multipath TCP提出一种流控机制

设计原则：公平性、跟目前的TCP的合作性

实验：在multihomed servers、DCN 和mobile clients中进行实验验证

5、SliceTime: A Platform for Scalable and Accurate Network Emulation

作者：RWTH Aachen University，Germany

概述：提出一套可扩展、准确的网络模拟平台，支持超过10K的节点实时模拟

目前方案问题：实时性很重要，但现有方案计算复杂性太高

设计：