也谈谈TRILL

TRILL最近很火。
最早在09年的时候，就有rfc提出来，要设计一个新的协议，改进现有STP的种种问题。11年小半年时间更是连发了5个rfc出来讨论TRILL的设计和应用（6325-6327，6361，6439）。

可能有对网络不太熟悉的同学，先来介绍下STP。
STP是Spanning Tree Protocol的缩写。我们知道对于现在的局域网（LAN）来说，交换机是实现多个节点互相通信的基础。而想要连接多个LAN，就需要交换机之间能有一定的机制来互通。如果交换机拓扑中含有环，那么就可能会出现循环转发，整个网络也就容易挂掉。因此，被称为“互联网之母”的Radia Perlman大妈就跳出来设计了个STP，还因此开心的写了一首小诗。

I think that I shall never see
A graph more lovely than a tree.

A tree whose crucial property
Is loop-free connectivity.

A tree that must be sure to span
So packets can reach every LAN.

First, the root must be selected.
By ID, it is elected.

Least-cost paths from root are traced.
In the tree, these paths are placed.

A mesh is made by folks like me,
Then bridges find a spanning tree.

其实STP的理念十分简单，拓扑中有环存在不是么？我禁掉其中的某些链路，自然就没有环了（当然要具体实现还需要很多的机制和协议）。STP因为其简洁有效，成为了事实上二层网络互通的标准。当然，凡事都会有利有弊，STP的问题主要有两点，一个是仅仅用了某些链路，很可能降低网络的性能；另一个是一旦出现链路故障，重新计算STP收敛不够快。

也正是为了解决这两个问题，Radia Perlman和其他的一些专家一同又提出了TRILL。
TRILL的设计理念也十分明确，把二层和三层各自的优点都结合起来，设计一个新的2.5层的协议出来。总的想法是在每个二层网络内部用传统的二层，而在各个交换机之间采用类似三层路由的机制，来实现多路径和快速收敛等。

TRILL的提出，为实现大规模的二层网络和保持高性能的互通带来了曙光。而现代云计算数据中心的发展，更是在这两方面提出了很强的需求，这也是为何TRILL在近些年讨论的越来越多，并被Cisco等支持，还作为其面向下一代数据中心核心网络技术FabricPath中的核心技术。

话说在TRILL的rfc6325中，Radia大妈又写了一首小诗。

I hope that we shall one day see
A graph more lovely than a tree.

A graph to boost efficiency
While still configuration-free.

A network where RBridges can
Route packets to their target LAN.

The paths they find, to our elation,
Are least cost paths to destination!

With packet hop counts we now see,
The network need not be loop-free!

RBridges work transparently,
Without a common spanning tree.

让人不得不赞叹，大妈真是个人才（随便搜搜大妈的简历，就知道大妈功力之深厚）。

附：Radia大妈照

关于SDN和未来云计算数据中心的报告

昨天，在首届SDN和数据中心技术研讨会上，我做了一个报告，给与会的各位专家介绍SDN相关技术和其在新一代数据中心中的应用，以及我对未来云计算发展方向的展望。
在报告中主要提出两个核心的理念。
一是关于信息技术从性能阶段往智能阶段的转变。
人类文明的发展，基础是对各种新技术的应用。而对任何新技术的应用大体可以分为两个阶段。第一阶段是简单依赖新技术变革带来的生产力飞跃，是一种粗放式的增长模式，可以称为性能主导阶段。而这种粗放式的模式必定会碰到瓶颈。一方面是对技术自身潜力的挖掘总有限制，在性能主导阶段，性能提升的代价必然是越来越大的，到了后面，这种代价可能已经超越了性能提升本身带来的收益。再一方面是人对新技术的需求，是越来越多的，简单的性能增长并不能满足所有需求。因此，过了性能主导阶段，必然会寻求一种更为精细化的阶段，可以称为智能主导阶段。以印刷术为例，开始是整版印刷，工人不断提升刻板速度，改进版面质量，但很快就变得难以继续提升了。这个时候就需要向智能化方向发展——活字印刷也就出现了。往往，在智能化阶段，孕育着更新一代技术的种子。此前的时期石器时代到电气时代，无不如此。而现在的信息时代，实际上已经到了性能主导阶段的后期，社会对智能化的需求也来越强烈。从生活中，我们也可以慢慢体会到这点。nokia破落，iphone大卖；汇编绝迹，C#盛行；pc收缩，平板兴起；甚至手动档已经越来越少见，自动档越来越流行，都证明了这点。这些年云计算的流行、社交网络、移动应用的兴起，也都是因为这个原因。所以，我预言，智能相关技术，特别是人工智能，春天已经到来了。而SDN的相关技术，恰好是智能化网络的一个很好的例子。
另外一个观点就是对于未来云计算数据中心的发展方向。
这个问题我也多次想过，这次算是有了个比较清晰的想法。我认为，未来的数据中心至少要具备两个基本特征。一是必须是性能（带宽、延迟）与智能（绿色、管理、配置、可靠、安全）需求都要能满足。二是必须是实现真正的完全虚拟化。当前的数据中心，其实并没有实现完全的虚拟化，无论提供的是iaas，paas，还是saas，都是针对用户的需求进行了深度的定制。一个提供saas的datacenter，很难同时服务需要其他xaas的用户。这个问题出在哪里？就出现在网络上，因为datacenter中的三个基本元素，计算、存储、网络，前两者的虚拟化都已经实现，唯独网络的虚拟化，最近几年才开始相关研究。未来的datacenter中，所有的资源，不论是什么类型，都应该统一的虚拟化，为“虚资源”。用户需要什么样的服务，就用这些“虚资源”组织起来，满足成能满足用户需求的形式。
以上两点想法，不知道是否是由我最早提出来的，但我坚信，都会被逐渐证实。

从数楼层问题到最大熵原理

先来看一道智力题目。
有2个鸡蛋和100层楼。可以站在某层往下扔鸡蛋，问尝试多少次，可以一定能获知在哪一层的时候刚好让鸡蛋碎。

——————分割线，请先自行思考30s————————

初看此题，可能认为答案是100。很自然，挨着试呗。
我们假设第k层（k=1...100）的时候鸡蛋刚好碎，那么从第一层开始依次往上是最保险的。因为一旦一开始某次尝试的楼层>k，则鸡蛋碎掉。
当我们手头只有一个鸡蛋的时候，确实只能采取这种方法，因为我们不知道k，不能去冒险。但是，现在有2个鸡蛋，能否减少尝试的次数？
毫无疑问，肯定是可以减少的，比如我们在第50层扔下来第一个鸡蛋，如果碎了，说明k<=50，然后从1...49挨着试第二个即可，最多需要50次（1次第一个，49次第二个）。如果第一个鸡蛋没碎，说明k>50，再用这两个鸡蛋尝试剩下的51...100楼层即可。
那么最优解是多少呢？
仔细思考这个问题，我们尝试扔鸡蛋有两种方法，一种是可以冒险猜一层，一种是挨着保险的线性尝试。对于第一个鸡蛋来说，冒险或者保险都可以。问题在于，一旦第一个鸡蛋碎了，则我们手头就只剩下一个鸡蛋了，这个时候就不能冒险了，只能采取保险的线性方法。因此，关键在于第一个鸡蛋应该采取什么样的策略？冒险还是保险？

——————分割线，请再自行思考30s————————

先暂时把刚才的问题放到一边，我们来看“最大熵原理”。
“最大熵原理是在1957 年由E.T.Jaynes 提出的，其主要思想是，在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。”
这段话来自百度百科，未必是最准确的定义，但意思已经讲透了。熟悉信息论的同仁相比已经理解了。
用大白话解释这段话，就是说，如果我们不知道足够多的信息，那么对于不知道的部分应该采取最保守的策略，不能添加任何的先验预测。
或者更直白点，如果不知道，千万不要蒙。
一个很平凡的例子就是掷骰子。假如实现你对这个骰子一无所知，请问它掷的结果该是什么样子的？很显然，大家都会说，六个面概率一样，肯定都是1/6.
那么现在告诉你它掷出来1的概率是1/2，那么结果是啥？因为我们只知道1的概率，对其他面依然一无所知，所以，六个面的概率只能是(1/2,1/10,1/10,1/10,1/10,1/10)，即剩下的五个面应该是彼此均匀等价的。
回到我们的问题，我们在扔第一个鸡蛋的时候，假如我们选择了第N层作为第一次扔的层数，则有两个可能：
N >= k: 鸡蛋1碎，鸡蛋2可以线性查找1...N-1层，一共需要1+N-1=N次。
N<k: 鸡蛋2没有碎，我们在N+1...100层中解决同一个问题，但是扔的次数少了1.
按照最大熵原理，因为我们不知道任何事先的信息，这两种选择的概率都是等价的，我们要求得最优，就只能让它俩带来的代价一致，也即我们应当选择N，使得无论那种情形发生，我们最终的尝试次数都是一致的。
对于N >= k的情况，一共需要N次，所以对于N<k的情况一共也必须是N次才成。则我们在N+1...100中解决问题，所尝试的次数应当为N-1，此时我们已经成功排除了N层.
可以观察到类似的决策中，从第一次到第N次，我们依次排除了N, N-1, ...1层。
所以我们有
N+N-1+...+1 = 100，或者
N(N+1)/2 =100
容易求得N=14

就是按照这样一个平凡的基本原理，我们求出了这个问题的最优解。实际上，从最大熵原理出发，可以推出近现代信息学上一堆著名的公式和方法，比如大名鼎鼎的卡尔曼滤波器，比如人工智能中的语义分析。或许，越是简单自然的东西，越能反映出这个世界终极的秘密吧。

备注：
这道问题是一个朋友出给我的，我想了大约一分钟，就想透了其中的关键。问题本身并不难，但其解决思路却蕴含了一个基本的原理——最大熵。这或多或少让我感到意外和惊喜。

扩展思考，
一般的，如果我们手头有m个鸡蛋，去尝试n层楼，需要试多少次？

从二到三

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

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

二——完备的最小集
在东方的哲学里，从一开始，二就有着无可替代的神奇含义。任何事物都是存在着对立面，即万物为阴阳，阴阳相生相克，才有了世界的运行。如果只有一，那么孤阳不生，独阴不存，世界这个大系统也就不能成为循环演变的系统，而只是单一的元素了。从这个意义上，二乃是系统的最小集。
现代的计算机科学有二进制，简简单单的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领域，任何一家企业，到了技术不占主导的时候，也往往就是开始走下坡路的时候。