从二到三

“道生一，一生二，二生三，三生万物”
                              ——《道德经》

初读这句话的人，可能觉得这就是句颇为罗嗦的大白话，也有人会说这就是归纳法的基本思想。
从一到二，再从二到三，是否是代表了相同的含义呢？为何是“三生万物”，而不是一或二生万物呢？
今天，我们就来谈谈二和三这两个神奇的数字。

二——完备的最小集
在东方的哲学里，从一开始，二就有着无可替代的神奇含义。任何事物都是存在着对立面，即万物为阴阳，阴阳相生相克，才有了世界的运行。如果只有一，那么孤阳不生，独阴不存，世界这个大系统也就不能成为循环演变的系统，而只是单一的元素了。从这个意义上，二乃是系统的最小集。
现代的计算机科学有二进制，简简单单的0和1构造起了无穷复杂可能的虚拟系统。有人说之所以不选其他进制乃是为了方便制造的实现，这有道理，但并不全对。实际上，从信息论的角度来看，给定固定长的空间，若想表达尽可能多的信息，是存在最有解的。
例如，给N位状态，选择X进制，使得X^(N/X)尽可能的大，采用微积分运算容易求得X=e。使得，并非是巧合，最大的信息密度出现在我们选择自然对数作为进制的时候。但是由于自然对数自身为无理数，所以我们只能选择2进制或者3进制。
实际上，可以证明，3进制的表达效率是要优于2进制的。但是考虑到2进制的表达效率其实不差，再加上系统实现的代价，我们还是选择了2进制。
当然，当年发明计算机的时候是否考虑过表达效率，我无法获知。

三——变化的开始
我们生活的空间是三维的，因此，对于人类来说，考虑超过3维的问题往往就意味着复杂度的爆炸。
有一个有趣的问题，一个酒鬼喝醉了酒，随机的晃荡，问他能否晃荡到家。假设随机往各个方向的概率相等。
这个问题的答案相信很多人都不那么容易猜到：当酒鬼游荡的空间是1维或者2维的时候，他晃荡回家的概率是无限大，即他总能瞎猫碰到死耗子；但是一旦达到3维或以上，回家的概率将变成无限小，即宇宙毁灭也回不了家。
从二到三，简单的量变引发了根本的质变，很神奇，对不对？
只有二态的系统往往是简单的，线性的，而一旦引入另外的维度，系统的复杂性就瞬间增加，变得复杂，非线性。
计算机中著名的set问题，当是2-set时，该问题为P问题；当为3-set时，则跳跃为NP问题。类似的例子，举不胜数。
三是复杂的开始，是变化的开始。但若是继续引入更多的维度，系统的复杂和非线性度进一步增加，则系统将可能极度不稳定，也难以构造稳定的存在。
所以，或许人类该万分的庆幸，我们的世界，刚刚好。
反过来再看“三生万物”，冥冥中，我们已无法再多感慨古人的智慧和直觉。

VXLAN

近期，业界大鳄Cisco联合VMWare、Broadcom等提交了名为VXLAN的RFC draft。链接在此。该标准是Cisco阵营暧昧许久以来，第一次对面向新一代数据中心特殊环境的网络架构核心解决方案。
一时间，引发了业界和学术界对这一敏感话题的关注。
那么，首先VXLAN是要解决什么问题？
简单的说，就是L2 over L3，或者说，在传统的IP层上虚拟出一个lan环境。
这一技术的典型应用就是新一代的数据中心。我在《拨云探月——云计算话题浅析》一文中曾提到过。物理的L2连接，具有简单、敏捷等优势，但难以适用到大规模网络。而在数据中心的环境中，恰恰需要有一套简单而大规模的网络连接。于是，在L3之上虚拟L2就成为了很自然的策略。使用L3来解决规模带来的代价，实现跨多个物理子网，利用虚拟的L2提供简单方便的网络部署和业务实现。
要实现这一策略，有不同的手段。在包头上做文章，实现管道是Cisco等老牌设备商最擅长也是最喜欢的手段之一。VXLAN的实现，也是这一技术的体现。通过添加一个8个字节的VXLAN包头，网包携带了8位的标识和24位的vlan id信息。因此，理论上将支持达到16M的不同虚拟子网。
Cisco宣称将在2011年9月份试图在其数据中心的大杀器——nexus 1000中尝试支持（beta）。这样做的优势是显然的，即
Cisco的老用户们只需要继续花钱购买Cisco的新产品，即可解决问题。另一方面，且不谈使用不断的添加包头的手段来解决一个个新的问题，思路是否正确，问题自然也是显著的。
1 新用户必须要让自己绑定到Cisco的漏水严重的大船上，而且很可能不能兼容其他家的产品。
2 使用额外的包头携带信息，会造成额外的传输代价
3 16M的限制，目前虽然够用，但是不scalable，未来的事情谁也不好说。
4 贵。
实际上，真正用户的需求还应该有下面几个方面。
1 开放。不仅要某家能做，其他家也可以做，而且还可以支持多家一起混合。
2 可扩展。
3 便宜。
从我的角度，要实现满足上述需求的L3 over L2解决方案，并非是个太难的问题。学术界已经有了很多有益的尝试和成果。甚至有些成果也已经开始逐渐变成产品，包括风头甚盛的infinetics和一些更开放更具有性价比的方案。
当然，根本上还是屁股决定脑袋，站在传统龙头设备制造商的角度，自然恨不得所有问题都自家一个设备解决了，哪怕解决的ugly点，解决的昂贵点，因为都是客户在买单。
但在IT领域，任何一家企业，到了技术不占主导的时候，也往往就是开始走下坡路的时候。

理工科phd必备高效工具

updated: 2013/10/12

理工科的phd们多不容易，除了要搞项目，还得攒论文。因此，高效率的工作模式无疑十分重要。

以下筛选了个人在使用过程中感觉能明显提高效率的工具，遵循“少而精”的原则，多数支持通用平台（win, linux, mac, etc.），希望后入门的phd们可以藉此做更高效的科研。部分工具对于研发人员也很有用。

数学计算

matlab、maxima

笔记整理

evernote

论文管理

Mendeley Desktop

Peaya paper

参考文献

jabref

书籍管理

calibre

文本编辑

Vim

emacs

编程实验

注重开发效率：Python等脚本语言

注重运行效率：C, C++或Java

注： IDE，还是首推eclipse

版本管理

集中式：SVN

分布式：Git，Hg

注：最大的git服务托管github。

数据同步

Dropbox

云诺、坚果云（大陆地区）

注：自己搭建，可以用ifolder。

图表相关

数据分析，GNUPlot/QtiPlot（带图形界面）

用python的可以看看matplotlib。

数据可视化

比较全面的可视化：Gephi

图形自动生成：Nodebox

论文写作

LaTeX

注：配套平台包括TexMaker（通用）或Winedt（仅限win）。

报告演讲

latex beamer包

ppt、keynote相关软件

附：一份不太长的关于做高质量学术报告的指南。

欢迎建议，持续更新ing...

转载请注明来源：http://yeasy.blogspot.com/2011/08/phd.html

网络流管理与交通流管理

曾经有幸听过一个交通流管理方向的专家做过一个研究报告。提到他们的研究成果被美国政府采用后，提高了接近十个百分点的性能（具体啥性能指标已经忘记了）。那时我刚接触网络流量管理这个课题不久，还只有个大概的认识。但即使如此，那个讲座还是引发了我不少的思考。

网络流管理跟交通流管理，貌似风马牛不相及的两个课题，其实有着惊人的内在关联。

从目的上看，两者都是为了提高系统的某种性能，包括容量、鲁棒性等，同时要尽量减少突发情况带来的损失，尤其典型的场景是拥塞避免。对网络来说，拥塞意味着大量的数据包挤占了有限的带宽，造成数据丢失（目的不可达）；对于交通来说，则是为了减少堵车发生，也是为了保障可达性。但是两者在可控手段上和物理过程上的差异，造成了在实际应用中的天壤之别。

网络上的流量管理，特别是现代的互联网，已经被研究了二十多年，但一直到今天都没有有效的手段去达到让人满意的控制。而交通流管理，已经有太多行之有效的思路和手段。我曾总结说，现在的交通网在讨论解决的类似问题，至少十年前互联网的专家们就已经研究过了（所以搞交通网络的专家们翻翻互联网上的相关问题的研究论文，未必不是一个好思路）。

抽象的看，一个系统，要避免拥塞，要么从提高容量角度入手，要么从降低压力峰值入手。提高容量，对于交通网络来说意味着增加更多的车道，对通信网络则意味着升级设备。无论对交通网络还是通信网络，这都不是能即时有效的手段。因此，两者都想到了如何去降低压力峰值，或者说如何做好调度优化。恰恰在这一点上，交通网络上的控制显示出了巨大的可操作性。

相比较互联网中以接近光速穿行的信号来说，交通网络中的承载单元——典型的如汽车，不仅速度慢，而且随时随地可以停住。将载荷停住对通信网来说则意味着存储。无论是技术的限制还是机制的设计约束，随时随地的高性能存储对于现代的通信网络来说都是“不可能的任务”。因此在流量调度上通信网络的要求要高的多，也难得多。同时也因为互联网是多个自治系统的自由连接，在交换节点上大规模的部署新的调度技术更是难上加难。

那么，通信网上的流量管理就没有一点优势了么？

当然也不是。相比较交通网来说，通信网上的流量管理也存在显著的优势。一是对载荷的可控性。载荷在经过每个节点时都存在被任意处理的潜能；二是允许丢弃重传；三是可控。每个载荷都严格遵守“交通规则”。也正是从这几点出发，以MPLS为代表的相关技术成为了ISP网络中事实上的标准。

写到这里，突然想到除了交通网和通信网之外的另一张大网——电网，也存在类似的问题。电网的调度跟互联网类似，也不存在任意灵活的存储（目前的电力存储，还有太多问题，最显著的就是容量和吞吐率，其次是效率）。另一方面电网又没有通信网络可以任意丢弃重传的灵活性。因此，电力网络的调度将更加困难，也是下一步马上面临的更大的挑战。美国前几年的电力网故障造成大面积停电，中国西部大开发早了很多发电基地，却无法输送出来。这都是一些经典的例子。当然，凡事有利有弊，电网调度也存在它有优势的一点。因为电力是能源，其应用十分广泛，既然现在输送不出来，为何不能本地消化掉？例如东部的生产基地如果直接建造到西部去，即消耗了西部的富余电力，又降低了东部的用电压力，可谓一举两得。

随机——概率幽灵

有一个程序员都看的懂的网络流行笑话，说有人写了一个超快的随机数生成函数，全部代码如下：
int getRandomNumber(){
return 4;
}
相信不少人看了都会会心一笑，说这程序员也太懒了，一直返回4，怎么就能生成随机数了呢？可是等我们仔细想象随机数的定义，随机数应该是跟此前发生的数无关的数，这也就意味着，无论此前生成的是什么数字，都不管，需要重新生成。
那么，每次产生4有什么问题呢？？
有数学家宣称，让一只长生的猴子敲击键盘无数次，总有一段是莎士比亚的某一部作品。其实我们可以推广下，让一只长生的猴子敲击键盘无数次，我们总可以找到人类历史上出现过的所有信息。
回到我们的问题，一个随机数生成器，某天生成的序列是“444444444……”，并非毫无可能，按照概率论的说法，随机数生成器生成的序列中，总会有任意一个数字的无限长的重复子序列。
也许有人已经开始迷糊了：“等一下，你怎么能说一直是某个数字的重复序列是随机序列呢，虽然你说的似乎有道理……”
让我们再来看一个简单的例子。
给你一枚普通的硬币，抛起来，掉到地上，假设硬币不能立起来，那么你猜正面的可能性有多大？
“这还用问，小孩子都知道，是1/2。”
好的，我们抛一下，结果是正面，那么我再抛一下，结果还是正面的概率是多少呢？
“嗯，应该也是1/2吧”
好的，我们再抛一下，结果还是正面，那么再抛一下呢？如果我连续抛出来了10个正面之后，下一次我再抛出正面的概率是多大呢？
可能有人额头已经开始出汗了，掏出笔，想一想概率论上学到的道理：每次抛都是独立事件，互相应该不受干扰，那么下一次结果是正面的概率应该仍是1/2。但是连续抛出11次正面，天哪，这个概率太小了。。。。似乎下一次更有可能出现反面啊。。。
好吧，相信到这里，大部分人已经彻底晕了。如果你还没晕，相信我，要么是你概率论没学好，要么是……你的神经无比粗壮。
这几个例子说明的其实都是随机。
现代概率论可以告诉我们某某事情发生的概率是多少，但是永远无法准确的告诉我们发生与否。事实上，概率为1的事情不一定会发生，而概率为0的事情也有可能会发生。
是不是听起来挺可怕？就像一个数学幽灵一样，无法捉摸。
实际上，当我们再仔细思考概率论的基础时，会发现数学上的假设与真实之间，出现了那么一丝的不和谐。什么叫相互独立事件？之前抛硬币跟下次抛硬币之间的独立真的符合数学上的理想定义么？
问题到了这一步，是现代最伟大的数学家或物理学家都无法回答的了。因为这涉及到这个宇宙的基本性质。在时空上看，多个事件点之间的联系并不是那么好理解。
一种最粗鲁的解释是我们的宇宙在时空中是不断分裂的，任何事件的发生的多个可能结果都导致了一个新的宇宙，我们在这个宇宙中只是一种偶然。因此，我们未来要做什么其实跟过去无关，因为总会导致均等机会的新的宇宙产生。
另一种解释，是宇宙中有某种神秘的力量，让整体稳定分布符合概率统计，小概率事件的发生，其实类似池塘水波的震荡，有波峰，就有波谷，而且当没有外在力量影响的时候，产生大水波的可能性很小，但允许极小概率的局部小震荡。这样的话，某天我们发现一件不可思议的小概率事件发生的时候，其实是发生了震荡的缘故。
以上两种解释似乎都有一定道理，但可能只有后人才有可能更完善的理解这个问题了。