0%

学习TCPIP(6)-网际协议 IPv4-无分类与子网地址扩展(CIDR)

[toc]

引言

前面几篇文章讨论了最初的互联网编址方案,并介绍了ABC类单播地址。但是,这种网络前缀固定的编址方式有个致命的缺点:及其容易造成IP地址的浪费。(准确的说是网络前缀的浪费)。本文将讨论4种现有的为了节省网络前缀而设计的扩展编码形式:点对点链路、代理ARP、子网编址和无分类编址。

对现有编码形式的回顾

在前面介绍过的互联网编址方案里,每个地址都被分成了两个部分:前缀部分和主机部分。设计人员把前缀部分看成是互联网地址的网络前缀部分,其余部分看作是主机部分。在最初的互联网编址方案里,前缀划分是固定的:A类地址将前8个比特用于网络部分,B类地址将前16个比特用于网络部分,C类地址将前24个比特用于网络部分,这种固定的前缀分配方式有个致命的缺点:设计人员没有考虑到今后互联网的增长。当时设计人员设计TCP/IP协议时,预见未来因特网上只有几百个网络和几千个大中型主机(当时个人计算机还没有出现),可是,现如今互联网增速之快,可以预见到未来不久时间IPv4地址空间将会用完(实际上现在IPv4地址块已经用完了)。

为了解决这种情况,设计人员创造出了用于为了节省网络前缀而设计的扩展编码形式:点对点链路、代理ARP、子网编址和无分类编址。本文将会讨论这4种形式。

代理ARP

术语代理ARP(Proxy ARP)混杂ARP(Promiscuous ARP)、和ARP窃用(ARP hack)指的是将同一个网络前缀用于两个物理网络时用到的技术。

说人话?其实就是用一个路由器连接两个物理网络,当物理网络A需要访问物理网络B的主机时,这个路由器就会“假装”是其主机并代理该访问请求。

举个例子,假设主机H1,H2,H3在物理网络A,主机H4,H5,H6在物理网络B,网络A和B之间通过路由器R连接。

代理ARP(Proxy ARP)的目的是为了将网络A和B“直连”起来,让主机H1,H2,H3,H4,H5,H6互相通信的时候就感觉是在同一个物理网络一样。

为了说明此效果,我们假设现在主机H1需要向主机H5发送一个数据报。此时H1为了发送到H5,使用ARP协议查询H5的MAC地址。当R接收到此ARP请求,就会将路由器R自身的MAC地址返回,所以H1发往H5的数据报实际上被R接收了,然后R就像正常在物理网络B发送数据报的流程将收到的数据报转发给H5。这就是代理ARP的工作流程。

子网编址

允许多个物理网络共用一个网络前缀的第二种技术称为子网编址(Subnet addressing)子网转发(Subnet forwarding),或划分子网(subnetting)。这个技术已经被标准化了,因此它成为了三种技术应用最为广泛的一种。(事实上,子网编址是IP编址中不可缺少的一部分)

子网编址有如下三条原则:

  • 各个网点都有修改地址和路由的自由,但是这种修改必须对其他网点不可见。也就是说,其他网点将此网点视为黑匣子。
  • 网点上的所有主机和路由器都认同该网点的编址方案,并按此方案编址。
  • 因特网上的其他网点可以把地址处理为一个网络前缀和主机后缀。

在子网编址之前,互联网IP地址结构是这样的:

1
2
3
+-----------+-----------+
| 网络号部分 | 主机号部分 |
+-----------+-----------+

经过子网编址之后,互联网IP地址变成了这样:

1
2
3
+-----------+-------------------+-----------+
| 网络号部分 | 物理网络(子网)部分 | 主机号部分 |
+-----------+-------------------+-----------+

从概念上讲,增加子网只是轻微的改变了对IP地址的解释。划分子网不是把32比特的IP地址划分为网络前缀和主机前缀,而是划分成了网络部分(Network Portion)本地部分(Local Portion)

当一个划分过子网的路由器R接收到发往本网络的数据报后,会继续将IP地拆为原网络号部分(用来指定该网点的网络本身的地址)、物理网络部分和主机号部分,再根据物理网络部分决定应该转发到哪个具体的子网(物理网络)。

举个例子,10.0.0.0/16的网络被划分成了两个子网:10.0.1.0/24(下文简称网络A)和10.0.2.0/24(下文简称网络B)。当连接了网络A、B、广域网的路由器从广域网接收到一个目的站是10.0.2.1的数据报,经过IP拆解后发现物理网络部分是2,自然这个数据报就会被转发到物理网络B去了。

而经过子网编址后的IP地址的形式又被称为分层编址(Hierarchical Addressing)的形式,它导致了相应的分层路由选择(Hierarchical Routing)

灵活的分配子网(定长划分子网)

由于不是每个网点都有完全相同的子网划分需求,因此TCP/IP协议允许网点灵活地划分子网,这里的划分子网专指定长划分子网。

也即网点可以自由选用任意长度(当然得小于32个比特位)的网络部分长度来划分子网,但由于是定长划分子网,因此划分得到的每个子网的大小都相同(也即每个子网的主机号部分长度相同,可容纳的最大主机数也相同)。在划分子网的过程中,应当避免使用全0或全1的地址来分配子网号和主机号,因为全0用于指代网络本身,全1则是广播地址。

灵活的分配子网(变长子网)

变长子网区别于定长划分子网的最显著的区别在于,变长子网划分方式允许划分得到的各个子网大小各异。这是因为各个单位的主机数量不一定相同,甚至于一个单位里的各个部门之间的主机数量也不一定相同。因此出现了所谓的变长划分子网(Variable-length subnetting)的技术,再次强调,这里的变长不是指子网大小随时间而变化,而是指各个子网的大小不一定相同。一旦为某个网络选择了一个子网划分方法,该网络上的所有的主机和路由器就都必须遵循这个抉择,否则有可能会出现数据报丢失或选择了错误路由的情况。

其次,在进行变长子网划分的时候,必须非常小心地给子网分配值,否则就有可能出现地址二义性(Address ambiguity)的问题:一个地址可能与多个子网相匹配,这种情况的结果是,该网络上无效的变长子网可能造成所有主机之间都无法通信,路由器不能解决这种二义性问题,这意味着只能通过子网重新编号来修复。

子网掩码与子网

为了区分互联网中IP地址的网络部分与主机部分(特别是经过了子网划分后的网络),TCP/IP引用了一个32位比特的掩码来划分网络部分与主机部分。这个掩码就是所谓的子网掩码(Subnet mask)。TCP/IP协议将子网掩码中的二进制位1看作是网络部分,而将二进制位0看作是主机部分。

下面是一个例子:IP地址192.168.1.7和子网掩码255.255.255.0

由于子网掩码的前24位是1,后8位是0,因此TCP/IP将192.168.1看作是网络部分,将7看作是主机部分。

注意子网掩码通常情况下需为连续的1后面跟上连续的0(但是TCP/IP并没有规定!).一些错误的子网掩码(比如说255.255.0.255)通常会被常见的操作系统拒绝(如Windows)。

子网转发算法

子网转发算法适用条件

首先值得注意的是,子网转发仅仅发生在物理网络之间找不到合适的最短路径的时候。为了理解这句话,来看一个例子:

image-20210116133755745
image-20210116133755745

如图所示,假设网2和网3都错误地分配到了同一个子网地址,并且假设这三个网络都无条件地使用子网转发。现在来考虑一下H需要发送一个数据报到子网N,那么主机H使用无条件的子网转发时,就必须要考虑是将这个数据报发送给路由器R1还是R2。因为主机H不属于子网N的一部分,所以它并不知道子网N在网络2和网络3的分布情况,那么此主机就不知道如何发送这个数据报。如果主机随机地向路由器R1和R2发送的话,那么这就意味着这个数据报可能不是沿着最短路径传输过去的,当通信量大的时候,因为额外的转发操作而造成的消耗是相当可观的,会加重路由器的负担并且会影响到这个网路的性能。

因此,当两个互联网机器(可能是主机或路由器)之间有一条最短路径存在时,这两个机器之间就不会使用子网转发。

具体算法

从前面的文章可以知道,IP转发算法使用了路由表这一数据结构。与此类似,子网转发算法也会搜索路由表。原始的路由表项的格式如下所示:

1
(网络地址,下一跳地址)

由于原始的IP地址分类方案可以从IP地址前3个比特分辨出这个IP地址是一个A,B,还是C类地址,从而可以划分出网络部分和主机部分。但是在子网转发时,不可能从从IP地址本身推断出哪一部分是网络部分,哪一部分是主机部分。

为了解决上述问题,需要附加一个地址掩码字段进路由表。修改过的路由表项结构如下图所示:

1
(子网掩码,网络地址,下一跳地址)

在进行路由选择时,需要使用子网掩码来从数据报的IP地址里提取出目的地址的网络部分(也就是说,在进行路由选择时,会将目的地址和子网掩码按位相与,得到目的地址的网络部分),与网络地址字段进行比对,如果相等就会跳转到下一跳地址。

如果采用这种跳转的方法,那么路由表中的特例,比如说到主机的特定路由,默认路由,都是不必要的了---子网转发算法能够轻松应对所有的特殊情况。

比如说,为了达成到主机的特定路由,那么可以用二进制全1的掩码与主机IP地址相与,这种情况下只有目的地址与路由表的地址完全相同的时候才会跳转。又比如说,为了达成默认路由,可以用二进制全0的掩码与主机IP地址相与,结果肯定全0,因此相与的结果恒等于0.0.0.0的二进制表示。在这种情况下,任何目的地址都会跳转到默认的下一跳地址。

最终得到了一个统一的转发算法,如下所示。

1
2
3
4
5
6
7
8
9
10
11
从数据报中提取出目的IP地址:I;
IF I的前缀与任何一个直接相连的网络地址匹配
THEN 通过该网络把数据报发送到目的站。
ELSE
FOR i IN 路由表
N = I & i.子网掩码
IF N == i.网络地址
THEN 将数据报发往指明的下一跳地址 AND 退出循环
END IF
END FOR
END IF

匿名的点对点链路

在一开始的IP网络设计中,人们给每个网络都分配了一个唯一的前缀。特别是因为IP协议将没对机器之间的点对点连接都看成是一个”网络“,所以给这种连接也分配了一个网络前缀,给点对点链路的一对计算机分配了主机后缀。当地址资源紧张时,每个点对点连接还是使用唯一前缀似乎就不太合理了。而对于有很多条点对点链路的单位,这个问题会显得相当严重,想象一下,如果一个单位有10台计算机,其中两两计算机相连形成一个点对点链路,那么这个单位就要消耗掉90个网络前缀!

为了解决这个问题,研究人员发明了一种简单的技术,即避免给每个点对点链路分配一个单独的后缀,称为匿名组网(Anonymous Networking):因为点对点链路上一台主机发送数据报,这个数据报只能是沿着这条链路传输并由另一端的主机接收,那么这个链路分配一个单独的网络前缀就显得没必要了。

当匿名组网技术用于点对点连接时,这种连接又称为无编号网络(Unnumbered Network)匿名网络(Anonymous Networking)。由于在点对点连接传输数据报的过程中只有一个可能的目的地,即位于线路另一端的主机,所以底层硬件传输帧时不会使用物理地址。于是,当IP把一个数据报交给网络接口时,可以给下一跳指定任何值,因为硬件会忽略它。因此,IP路由表的下一跳字段可以包含任意值(例如0).

无分类编址

到了1993年,上述的技术都无法阻止因特网的增长而导致的IP地址耗尽。因此,人们开始定义一个还有更多地址的新版本IP(即IPv6),但是在这个新版本得到标准化并广泛应用之前,为了适应网络的增长,人们发明了一个临时的解决方法,即无分类编址(Classless Addressing)

超网

这种编址方案扩展了子网编址中所用的思路,允许网络前缀具有任意的长度。除了新的编址方案之外,设计人员还发明了新的转发和路由传播技术,这些方案和技术整体被称为无分类域间路由选择(Classless Inter-Domain Routing),简称CIDR。一种无分类编址的最初用法被称为构造超网。此技术将一些连续的小的网络范围合并为一个大的网络范围,例如,一个单位需要一个B类地址空间,这项技术就允许分配多个连续的C类地址空间给该单位。

CIDR地址块与网络掩码的表示

虽然可以将CIDR看成是用一些小的的地址空间代替一个大的地址空间的技术,但是CIDR提议者最初设计它的目的是为了将它应用到更广泛的场合,也即每个商业因特网服务提供者(Internet Service Provider,简称ISP)可以得到一个一大块因特网地址,然后ISP再将这个大的地址空间划分为小的地址空间并分配给用户。由于网络地址的网络前缀与主机后缀的边界允许出现在网络地址的任意位置上,所以ISP可以将自己的大的地址空间划分为任意小的地址空间给客户。

与子网编址类似,CIDR使用了一个32位的地址掩码(Address mask)用于指明网络前缀与主机后缀的边界。该掩码只能是连续的二进制位1(可以没有)后面接上连续的二进制位0,因此该地址掩码可以用二进制位1的长度(也即网络前缀的长度)来表示该掩码。具体表示方式是在IP地址后面附加一个/符号,再在该符号后面附上网络前缀的长度。例如:

1
128.211.124.0/21

表示IP地址前21位二进制位属于网络前缀部分。这种记法被称之为CIDR记法(CIDR notation),又称斜线记法(slash notation)。其中/8、/16、/24划分对应于传统的A、B和C类划分。

为了在互联网中划分CIDR块,应将IP地址看成是一个32位任意无符号整数,并且允许一个网络管理员把地址划分成若干连续的块,其中一块的长度是2的幂。

学习TCPIP(5)-网际协议 IPv4-差错与控制报文(ICMP)

引言

当互联网通信的过程中在某一结点发生错误时,IP会通过差错与控制报文(ICMP)最初源站发送一个ICMP包从而向源站上的网际协议软件报告发生了差错。

ICMP协议是由ICMP软件负责处理的;也就是说,当一个ICMP报文到达后,ICMP软件模块会对它进行处理。当ICMP确定是由某个高层协议或应用程序引起的问题,它会通知相应的模块。

值得注意的是,ICMP报告错误总是报告给最初源站。也就是说,即使这个错误是由传输过程中的负责转发的某个路由器造成的,ICMP也只会报告给最初发送这个数据包的路由器/主机。

Read more »

Tessellation 曲面细分阶段

Tessellation 总览

曲面细分(Tessellation), 在计算机图形学中的含义是从任意网格创建光滑曲面1。该阶段分别于DirectX 11和OpenGL 4.0, OpenGL ES 3.2 首次出现2。(注:对应于SM5.03)如下图所示。

来源于论文M. Nießner & B. Keinert & M. Fisher & M. Stamminger & C. Loop & H. Schäfer / Survey on Hardware Tessellation, Page 4
来源于论文M. Nießner & B. Keinert & M. Fisher & M. Stamminger & C. Loop & H. Schäfer / Survey on Hardware Tessellation, Page 4

上图靠左边的是输入Tessellation的原始网格(mesh)数据。靠右边是Tessellation之后的结果。可以看到,通过Tessellation阶段的处理,可以生成比原来光滑的多的曲面。

由此看来,Tessellation的好处2有:

Read more »

QuickSort 快速排序时间复杂度的推导与证明

1 算法的描述

快排的主要思想来源于分治法.下面是快排应用分治法的主要步骤:

  • 分解: 将原数组A[p..r]原址划分为两个子数组A[p...q-1]和A[q+1..r],使得数组A[p...q-1]中的元素都小于数组A[q+1..r]中的元素.

  • 解决: 通过递归调用完成对A[p...q-1]和A[q+1...r]的快速排序.
  • 合并: 由于快排是原址排序算法,因此不需要合并操作,数组A[p...r]已经有序

下面给出QuickSort的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
QUICKSORT(A,p,r)
if p < r
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)

PARTITION(A,p,r)
x=A[r]
i=p-1
for j=p to r-1
if A[j] <= x
i++;
swap A[i] and A[j]
swap A[i+1] and A[j]
return i+1

本文从最好时间复杂度、最差时间复杂度、平均时间复杂度三个方面进行算法时间复杂度的推导与分析。

Read more »

学习CSAPP(1) - 并行和并发

CSAPP 有言:

We use the term concurrency to refer to the general concept of a system with multiple, simultaneous activities, and the term parallelism to refer to the use of concurrency to make a system run faster.

并发,英文叫Concurrency,是指一个系统在同一时间执行多个程序的能力;在处理器只有单核的年代,OS通过分时技术来模拟多个程序并发的假象。

到后来,出现了名为指令级并行(Instruction-Level Parallelism)的技术和被称为SIMD(Single-Instruction, Multiple-Data)的技术。指令级并行使得处理器可以在同一时刻执行多条指令,SIMD则使得处理器可以在同一指令里处理多条数据。

学习TCP/IP(1):分类的Internet地址

一个互联网主机可由名字(Names), 地址(Address), 路由(Route)来进行标识。Shoch 是这样定义这三个术语的:

Names,即名字,标识这个对象是什么;

Address,即地址,标识它在哪里;

Route,即路由,指出如何到达哪里。

首先,让我们把互联网想象成由众多物理网络构成的大网络,每个物理网络有若干个主机。我们依次给物理网络编上号(即网络号),然后再给物理网络里的主机编上号(即主机号,注意,主机号是相对于物理网络而言的;比如说我们有两个物理网络,每个物理网络各有2台主机,那么第一个和第二个物理网络中包含的主机号都是1,2。并非1,2,3,4。)

这样组成的互联网地址就能分为网络号主机号两部分,网络号标识了是哪个物理网络,主机号则指明了这个主机是这个物理网络的第几台主机。但请注意,IP地址并非唯一地标识互联网上的主机。事实上,存在一种特殊的多归属主机,这种主机具有1个以上的物理连接,同时归属于不同的物理网络,这个主机自然就拥有多个IP地址。最为典型的例子是路由器,路由器是用于连接两个或多个物理网络的设备。

Read more »

学习TCPIP(2)-ARP协议

ARP 协议是这样一个协议:它负责将高层地址(IP地址)映射为底层物理地址(MAC地址)

其中,IP地址是针对于TCPIP网络而言的,当目的地是网络A的主机H一个数据包抵达网络A的路由器时,该路由器需要知道主机H的MAC地址才能完成数据交付任务。

为什么需要MAC地址?很简单,网卡只认识MAC地址。准确地说,IP协议处于网络层,回忆一下基本的网络分层模型:最低下是物理层,最高层是应用层,重点在于:为了实现各层协议的解耦(各层协议可替换),高层协议对于底成协议是透明的,这意味着底层协议不知道也不需要了解它所搭载的高层协议数据包时什么协议的,有哪些属性,有什么数据,它就只管原样发送接受传输就行。

应用上述观点,以太网帧并不知道它封装的IP数据报的IP地址是什么,实际上,它就根本不知道有IP地址这个东西。

它靠MAC地址来识别每一个以太网帧。回到上面的问题,如果它已经知道了目的地主机H的MAC地址,那么它直接在本地网络广播这个以太网帧就行了,对方在检测到MAC地址匹配的情况下会接受该帧,其余主机会由于MAC地址不匹配而忽略该帧。

那么还剩下一个问题尚未解答:TCPIP协议是怎么从IP地址找到对应的MAC地址的呢?换句话说,IP地址如何映射到MAC地址?

这个如何把高层地址映射为物理地址的问题被称为地址解析问题(Address resolution problem)

Read more »

学习TCP/IP(3):网际协议 Internet Protocol for IPv4 :无连接的数据报交付

引言

最基本的互联网服务包含一个分组交换系统,该交换系统不可靠尽最大努力交付无连接

  1. 由于分组可能丢失、重复、延迟、失序,因此认为该服务不可靠
  2. 由于互联网软件会努力尝试发送每一个分组,除非遇到资源耗尽或底层网络故障,否则互联网软件不会随意丢弃任何一个分组,因此该服务是尽最大努力交付的。
  3. 在数据报传送的过程中,每个分组都被独立处理,不同分组可能经由不同的路径抵达目的站,所以认为该服务是无连接的。
Read more »