L3 - Scaling IP for Size and Speed
Overview
这节课会介绍互联网网络层使用的一些技术，这些技术使得互联网可以扩展到数百万个网络并连接数以亿计的计算机。
1. Address Structure
互联网能达到如此规模的根本原因在于它的网络层使用了拓扑化的地址（topological addressing）。以太网地址与位置无关，并且总是标识一个网卡，不论这个网卡连接在网络的什么位置。而一个网卡的IP地址却与其在网络拓扑中的位置强相关。这使得IP地址的路由可以在路由器的转发表中汇聚，并且路由可以进一步汇总，通过参与到互联网路由协议的路由器与其他网络进行交换。如果没有这种激进的汇聚汇总，是不可能达成大规模系统。事实上，按照目前互联网上使用的技术，挑战也是很大。这节课我们会讨论这些技术中最重要的一部分，并解释它们如何工作。
因为一个IP地址表明了其在网络拓扑中的位置，互联网的网络层可以看成是一个经典的区域路由（area routing）来大规模的实现IP转发路径。
1.1 Area routing hierarchy
经典区域路由的最简单方式是将网络地址分成了2个部分：位于高比特位的固定长度表示“区域”和“区域内”地址。将这两部分结合起来就是一个网络地址。例如，可以设计一个32bit的区域路由方案，用8bit来表示区域，24bit来表示区域内地址。在这个模型中，转发将很简单，如果一个路由器发现一个packet不在它的区域中，那么路由器会查找对应的“区域”并完成转发。转发表中有关不在同一个区域内的路由数目最多等于网络中区域的数目，通常来说都远小于地址的总数。
以上只是一层汇总，实际中可以设计多层区域，在每层区域汇总转发表。这样的话，可以将每个路由器定义为level 0；将一组共享了一段地址前缀的路由器定义为level 1；将一组level 1的路由器定义为level 2；以此类推。通过这样的定义，level i - 1中的任意两个路由器，都可以通过level i连接。（注，这就是clos网络架构和其他园区网构成）
有两个原因导致这种经典的区域路由在实际中无法工作。
每个网络的大小是不一样的，因此通常很难定义每一个level的大小。定义固定的大小不能工作。
管理和维护一个仔细工程化的结构在实际中很难达成，并且从管理的角度来说扩展性不好。
1.2 Applying area routing: Address classes
上面的第二个原因表明我们不应该使用一个需要人工分配和管理的，深的层级化结构。我们可以尝试解决第一个问题，通过预期的区域大小，将网络地址分配出去。互联网使用了这种方式（在32bit的IPv4地址），对应的是被称作classful addressing structure。在这种方式中，区域被分为3类:
Class A拥有 2^24个地址，并且其地址的第一个bit位0
Class B拥有2^16个地址，并且其地址以bit 10起始
Class C拥有2^8个地址，并且其地址以bit 110起始
这种分类方法会稍微修改转发方式（但是仍然很简单）: 路由器会确定不在其区域的地址的Class，然后根据Class完成固定长度的区域查找。（注，因为Class确定了区域的地址长度）
1.2.1 The problem with class-based addressing
上面的方法使得互联网较好的工作了几年，但是之后就陷入了扩展性问题，因为接入互联网的网络急剧增加。具体的问题是地址耗尽：可用的地址开始不够了。这里很重要的一点是：并非32bit地址对应的2^32个地址快要不够了（这里有大约40亿个地址），而是class-based的网络地址开始不够了。这本质是由于Class A和Class B低效的粗粒度地址分配导致的。（注：MIT和Standford之前都各自有一个完整的A类地址，MIT现在还有！）
1.2.2 Solution 1: CIDR
对于这个问题的解决方式之一就是摆脱class-based addressing以及转发路径上对应的固定长度区域查找。IETF设计了一种方法叫做：Classless Inter-Domain Routing(简称CIDR，发音cider)。在这种方法中，每一个网络通过两个字段确定一段地址空间：A，一个32bit的数字（通常用十进制和点表示）表明地址空间；m，一个介于1和32之间的数字表明地址空间大小。如果一个网络的地址空间是A/m，那表示它有2^m个地址，所有地址的前32-m个bit都是A。例如，18.31/16表示这里有2^16个地址，地址空间是[18.31.0.0, 18.31.255.255]
1.2.3 Solution 2: IPv6
地址耗尽问题的长期解决方案是一个新版本的Internet Protocol，IPv6。这会在本节课的第三部分介绍。
1.3 CIDR lookups: Longest prefix match
基于CIDR的转发不能够再根据地址所属的Class进行固定长度掩码匹配了。相应的，一个Router需要实现prefix match来检查地址是否属于其转发表中的某一条A/m CIDR。
当Internet的拓扑是树状且任意两个网络中间仅有一个最短路径时，prefix match可以正常工作。但是互联网不是一个树状。出于冗余和流量负载均衡的目的（如今冗余是最常见的原因），很多network与多个其他network互联。
拥有多路径的后果是，一个Router需要决定使用转发表中的哪条路径来转发一个地址。很明显，转发表中拥有最长前缀（longest prefix）的条目是应该选择的路径。所以，每个Router都必须在其转发逻辑上实现一个LPM（Longest Prefix Match）算法。
2 Fast LPM
当进行每秒数百万次转发查找时，LPM是一个比较重的操作。过去，最好的实现方式是使用一个旧的算法，叫做Patricia trees，这是数十年前发明的一个trie数据结构。但是这个算法只在低速传输时流行且有效，在高速传输时无法工作。
Last updated