虚电路与数据报

网络层提供服务有两大类:

  • 无连接的网络服务(数据报服务)

  • 面向连接的网络服务(虚电路服务)

虚电路

  • 需建立连接

  • 由VC号来标识

  • 连接状态需要维持,路径上的交换节点都参与

  • 涉及资源预留问题

VC号与转发表

VC号为局部的而非全网的,简化虚电路的连接建立。

转发表示例:

入接口 入VC号 出接口 出VC号
1 12 2 22
2 63 1 18
3 7 2 17
1 97 3 87

虚电路的三个阶段

  • 虚电路建立

  • 数据传输

  • 虚电路拆除

数据报网络

  • 在网络层无呼叫建立

  • 路由器:没有端到端连接的状态

    • 无网络级“连接”的概念
  • 分组使用目的主机地址转发

    • 在相同的源和目的对可能采用不同的路径

最长前缀匹配

当路由器收到一个IP数据包时,它会将数据包的目的IP地址与自己本地路由表中的所有路由表进行逐位(Bit-By-Bit)对比,直到找到匹配度最长的条目,这就是最长前缀匹配机制。

举例:

存在以下转发表

前缀匹配 链路接口
11001000 00010111 00010 0
11001000 00010111 00011000 1
11001000 00010111 00011 2
otherwise 3

① 目的地址 11001000 00010111 00011 哪个接口?(0)
② 目的地址 11001000 00010111 00011000 10101010 哪个接口?(1)

IP

不可靠的、尽力而为的、无连接分组交付系统

IP数据报格式

IP数据报格式.gif

[4位]版本 [4位]首部长度 [8位]服务类型 [16位]总长度
[16位]标识 [3位]标志 [13位]片偏移
[8位]生存时间 [8位]协议 [16位]首部检验和
源地址
目的地址
---- 可选字段(长度可变)---- || ---- 填充 ----
数据部分
  • 版本:4位。表示IP协议版本

  • 首部长度:4位。可表示的最大十进制数值为15。单位为【32位字长】(4字节)即:该字段数值为1时,表示首部长度为32位(4字节);又由该字段最大值为1111,首部长度最大为60位。

    当IP首部长度不是32的整数倍时,用结尾的填充部分填充至整数倍。

  • 服务类型:8位。只有在使用区分服务时,该字段才起作用

  • 总长度:16位。首部+数据的长度之和,单位为字节。故首部+数据总长度最大值为2^16^-1=65535字节

  • 标识:16位。

    • IP协议在存储器中维持一个计数器,每产生一个数据包,计数器就+1,并将值赋给标识字段。

    • 当数据包的长度超过网络的MTU而必须分片时,这个标识字段的值就被复制到所有分片中

    • 拥有相同标识字段值的分片会被重组呈原来的数据报。

  • 标志:3位。

    • 第一位未使用,值为0

    • 第二位称为DF(不分片),表示是否允许分片:

      • 取值为0时,表示允许分片

      • 取值为1时,表示不允许分片

    • 第三位称为MF(更多分片),表示是否还有分片正在传输。设为0时表示没有更多分片需要发送。

  • 片偏移:13位。当报文被分片后,该字段标记该分片在原报文中的相对位置。片偏移单位为【8字节】。

  • 生存时间(TTL):8位。表示数据包在网络中的寿命,由发出数据包的源主机设置,目的是防止无法交付的数据报无限制地在网络中传输,从而消耗网络资源。

    路由器在转发数据报之前,先把TTL值-1,若TTL值减少到0,则丢弃这个数据报,不再转发。

    TLL最大值为255(2^8^-1),若把TTL初始值设为1,则表明这个数据包只能在本局域网中传送。

  • 协议:8位。表示数据部分使用的协议(TCP:6;UDP:17;ICMP:1……)

  • 首部检验和:16位。校验数据报的首部。

  • 源地址:32位。

  • 目的地址:32位。

IP 分片和重新组装

  • 网络链路有MTU(最大传输长度)-最大可能的链路级帧

  • 在网络中,大IP数据报被分割(分段)

    • 一个数据报变为几个数据报

    • 仅在最后目的地“重新装配”

    • IP首部比特用于标识\排序相关段

举例:

MTU = 1500字节;下方为一个4000字节的数据报

长度 ID MF位 偏移
4000 X 0 0

分片后产生以下三个数据报:

长度 ID MF位 偏移
1500 X 1 0
长度 ID MF位 偏移
1500 X 1 185
长度 ID MF位 偏移
1040 X 0 370

长度=数据段1480+首部20=1500(字节)

偏移=$\frac{1480}{8}=185$

IP地址表示方式:点分十进制法

8位一组,用十进制表示,并利用点号分割各部分,可以表示为从0.0.0.0255.255.255.255

IP地址结构:

两级IP:{ <网络号> + <主机号> }

三级IP:{ <网络号> + <子网号> + <主机号> }

如图:

IP地址结构.png

  • ABCDE五类网络:

    以IP地址结构为W.X.Y.Z来说明:

    • A类:

      • 网络ID占用一个字节W,W第一位固定为0,剩余7位可用, 又因为IP地址中0.与127.要保留,故可用的7位取值范围为二进制的000 0001到111 1110,即十进制的1-126,即它可以提供126个A类的网络ID。

      • 主机ID共占用X、Y、Z字节(24位),此24位可以支持(2^24^)-2=16777214台主机。

    • B类:

      • 网络ID占用两个字节W、X。W前两位固定为10,后六位范围为00 0000~11 1111;故整个W的范围为128(1000 0000)到191(1011 1111),X的范围为0到255,故它可提供(191-128+1)*256=16384个B类的网络。

        又∵128.0.0.0与191.255.0.0为保留位,故实际上可提供的网络ID为16384-2=16382个。

      • 主机ID共占用Y、Z两个字节,因此每个网络可支持(2^16^)-2 = 65534台主机

    • C类:

      • 其网络ID占用三个字节W、X、Y。W前三位固定为110,故其范围为192(1100 0000)到223(1101 1111),它可以提供(223-192+1)* 256*256=2097152个C类的网络。(保留位同上,不再复述)

      • 主机ID只占用一个字节Z,因此每个网络可支持(2^8^)-2=254台主机

    • D类:它是组播(multicast,或译为多播)所使用多组ID(group id),这个组内包含着多台主机。W前四位固定为1110,范围为224到239

    • E类:它保留给未来使用或供实验用途,W前四位固定为1111,范围为240到254

    地址范围(包括网络地址本身,广播地址,私有地址等)

    A类:1.0.0.0 ~ 127.255.255.255

    B类:128.0.0.0 ~ 191.255.255.255

    C类:192.0.0.0 ~ 223.255.255.255

    D类:224.0.0.0 ~ 239.255.255.255

    E类:240.0.0.0 ~ 247.255.255.255

子网掩码

子网掩码用二进制标识,也是一个32位的数字,对应IP地址网络标识部分的位(网络号 + 子网号)全部为1,对应IP地址主机标识的部分都为0。

子网掩码不能单独使用,必须结合IP地址,它屏蔽IP地址的一部分以区别网络标识和主机标识,并说明该IP地址是局域网还是远程网。

10001101 00001110 01001000 00011000 IP:141.14.72.24

11111111 11111111 11000000 00000000 掩码:255.255.292.0

以IP逐位并掩码:

10001101 00001110 01000000 00000000 网络地址:141.14.64.0

无类型域间选路 (Classless InterDomain Routing) CIDR

若子网号连续,则可以用斜号+数字表示网络部分的长度。

某地址块为200.23.16.0/23,则其

子网掩码为:255.255.254.0(
11111111.11111111.11111110.0000)

网络地址为:200.23.16.0 (主机比特全0)(
11001000.00010111.00010000.00000000)

可用主机地址为:200.23.16.1~200.23.17.254(
11001000.00010111.00010000.00000001 ~
11001000.00010111.00010001.11111110)

广播地址为:200.23.17.255 (主机比特全1) (
11001000.00010111.00010001.11111111)

子网掩码应用

某A类网络20.0.0.0的子网掩码为255.224.0.0,请确定可以划分的子网个数,写出每个子网的子网号。

解析:A类网络子网掩码默认为255.0.0.0,所以多出来的224就是子网号,也就是11100000。前三位全是1,所以子网号占据前三位,共有2^3^=8个子网个数

解答:A类网络的默认子网掩码为255.0.0.0,根据题意,第二个字节的子网掩码为224,即11100000,可知该网络使用第二个字节的前三个比特进行了子网划分,因此划分的子网数为2^3^=8

8个子网号分别为:

20.00000000.0.0 即 20.0.0.0
20.00100000.0.0 即 20.32.0.0
20.01000000.0.0 即 20.64.0.0
20.01100000.0.0 即 20.96.0.0
20.10000000.0.0 即 20.128.0.0
20.10100000.0.0 即 20.160.0.0
20.11000000.0.0 即 20.192.0.0
20.11100000.0.0 即 20.224.0.0

将某c类网200.161.30.0划分为4个子网,请计算出每个子网的有效的主机IP地址范围和对应的子网掩码。

解析:C类网络占据三个字节,默认子网掩码为255.255.255.0。划分子网需要在最后一个字节上添加掩码,由于要划分为4个子网,故使用2位掩码,剩余6位为主机IP使用范围。

解答:解析见上方

子网掩码为255.255.255.11000000 即 255.255.255.192

两位掩码提供了4个子网IP容量,分别是:

200.161.30.00000000 即 200.161.30.0
200.161.30.01000000 即 200.161.30.64
200.161.30.10000000 即 200.161.30.128
200.161.30.11000000 即 200.161.30.192

每个子网内的有效主机IP范围分别是:

子网IP+000001 ~ 子网IP+111110

某公司申请到的网络地址为192.3.2.0,现要划分给5个子公司,最大的一个子公司有28台计算机,每个子公司在一个子网中,则
(1) 子网掩码应是多少?
(2) 5个子公司的网络地址分别是什么?

解析:由第一个字节为192判断出该地址为c类地址。由于要5个子网,2^2^<5<2^3^,故应使用3位子网掩码,提供8个子网IP容量。
剩下5位可以提供2^5^-2=30个IP地址,足够供应28台机器。。

解答:192.3.2.0为C类地址,默认子网掩码为255.255.255.0。要划分子网,应在最后一个字节处添加掩码。

由于要划分为5个子网,故使用3位掩码

即255.255.255.11100000,即255.255.255.224

5个子公司的网络地址可以在以下8个IP中选择:

192.3.2.00000000 即 192.3.2.0
192.3.2.00100000 即 192.3.2.32
192.3.2.01000000 即 192.3.2.64
192.3.2.01100000 即 192.3.2.96
192.3.2.10000000 即 192.3.2.128
192.3.2.10100000 即 192.3.2.160
192.3.2.11000000 即 192.3.2.192
192.3.2.11100000 即 192.3.2.224

某单位申请了一段IP地址:200.23.16.0/23。单位内由4个部门(A,B,C,D)组成,每个部门的主机数量分别是:200(A), 100(B), 50(C), 40(D)。试将单位的总地址块200.23.16.0/23划分为4个子网分配各4个部门。

  1. 写出每个子网(地址块)
  2. 每个子网的网络前缀?子网掩码?
  3. 每个子网的广播地址?主机可用地址范围?

注:200.23.16.0/23的二进制表示
11001000 00010111 00010000 00000000

解析:2^8^-2 > 200 > 2^7^-2 > 100 > 2^6^-2 > 50>40 > 2^5^-2
故A公司至少使用8位主机IP,B公司至少使用7位,C/D至少使用6位
即A可以使用子网网络前缀/24,B可以使用/25,C/D可以使用/26

解答:(解析略,见上文)

故存在以下方法划分子网:

A:11001000 00010111 00010000 00000000
子网网络前缀/24 子网掩码255.255.255.0
子网广播地址200.23.16.255 主机可用地址范围:200.23.16.00000001~200.23.16.11111110
B:11001000 00010111 00010001 00000000 子网网络前缀/25 略
C:11001000 00010111 00010001 10000000 子网网络前缀/26 略
D:11001000 00010111 00010001 11000000 子网网络前缀/26 略

私有地址

在互联王中不使用,仅在局域网中使用的IP地址

  • 10.X.X.X A类

  • 172.16.0.0~172.31.255.255 B类

  • 192.168.X.X C类

NAT技术

所有数据报离开本地网络具有相同的单一源地址:NAT IP地址;拥有不同的源端口号

示例:

存在NAT转换表

LAN侧地址(内网地址) WAN侧地址(公网地址)
10.0.0.1 : 3345 138.76.29.7 : 5001
…… ……

存在NAT结构:

graph LR

    subgraph NAT
        LAN(LAN 10.0.0.4) --> WAN(WAN 138.76.29.7)
    end

    1(主机一 10.0.0.1) --> LAN
    2(主机二 10.0.0.2) --> LAN
    3(主机三 10.0.0.3) --> LAN

    WAN --> 公网

主机一与外网交流过程:

① 主机10.0.0.1发送数据报到128.119.40.186:80

② NAT路由器将数据报源地址从10.0.0.1:3345改变到138.76.29.7:5001,更新表

[目的地处理数据报…]

③ 回答返回到目的地址138.76.29.7:5001

④ NAT将数据报目的地址从138.76.29.7:5001改变到138.76.29.7:5001

ICMP

IP网络尽力而为,不可靠,ICMP通过差错报文和询问报文来辅助IP网络的功能

IPv6

懒得写

选路算法

选路协议:决定从源到目的地通过网络的“好的路径”(路由器序列)

链路状态选路算法

Dijkstra算法

  • 所有节点知道网络拓扑、链路费用

    • 经“链路状态广播”完成

    • 所有节点具有相同信息

  • 从一个节点到所有其他节点计算最低费用路径

    • 给出对这些节点的转发表
  • 迭代:k次迭代后,得知k个目的地的最低费用路径

概念

  • D(v):从源到目的地v,沿着最低费用路径的费用

  • c(x,y):从节点x到y的链路费用;若xy不相邻,则c(x,y) = ∞

  • p(v):从源到v沿最低费用路径,v的前一个节点

  • N’:一个节点集合,如果从源节点到v的最低费用路径已知,则v在N’中

具体算法

初始化:

  1. N’={u} (u为源节点)

  2. 对所有节点v:

     if v临近u:
         D(v)=c(u,v)
     else:
         D(v) = ∞
    

算法开始:

  1. 找出不在N’中,且D(w)最小的w

  2. 将w加入N’中

  3. 对于所有v临近w并且不在N’中,更新D(v):
    D(v) = min( D(v), D(w)+c(w,v) )
    /*到v的新费用或是到v的老费用,或是到w加上从w到v的已知最短路费用*/

  4. 重复1~3,直到所有点都在N’中

算法复杂性:

对于n个节点

每次迭代:需要检查所有不在N中的节点

距离矢量算法

动态规划算法

概念

  • dx(y):从x到y最低费用路径的费用

  • 方程:dx(y) = minv{ c(x,v) + dv(y) }

    v表示x的邻居,minv{}表示对x的所有邻居遍历

算法

对于每个节点x

  1. 在每个节点建立自己的距离向量表并初始化

  2. 每个节点将自己维护的距离向量表向其邻居节点转发

  3. 每个节点收到邻居节点发送的距离向量表以后,基于新的信息采用方程来更新自己的距离向量表

  4. 当自己的距离向量表发生变化时,将新的距离向量表发送给自己的邻居节点,如果与以前的向量表相同则不向其邻居节点转发,知道每个节点的距离向量表达到稳定为止

应用举例:

距离矢量算法举例.png

要求du(z),显然已知dv(z)=5,dx(z)=3,dw(z)=3

则du(z) = min{
c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z)
} = min{
2 + 5,
1 + 3,
5 + 3
} = 4

迭代、异步

每次本地迭代由下列引起:

  • 本地链路费用改变

  • DV从邻居更新报文

如果DV变化,通知邻居

互联网中选路

“距离”的定义

  • 从一路由器到直接连接的网络的距离定义为1

  • 从一个路由器到非直接连接的网络的距离定义为所经过的路由器数+1

  • RIP协议中的“距离”也称为“跳数”,因为每经过一个路由器,跳数就+1

  • RIP认为一个好的路由就是经过的路由器数目少,即“距离短”

  • RIP允许一条路径最多只能包含15个路由器,“距离”的最大值为16时认为不可达

RIP协议的三个要点

  • 仅和相邻路由器交换信息

  • 交换的信息是当前本路由器所知道的全部信息

  • 按固定的时间间隔交换路由信息

路由表的建立

  • 路由器在刚刚开始工作时,只知道到之间连接的网络的距离(该距离定义为1)

  • 之后,每一个路由器也之和相邻的路由器交换并更新路由信息

  • 经过若干次更新后,所有路由器最终都会知道本自治系统中任何一个网络的最短距离和下一跳路由器的地址

距离向量算法

收到邻居的路由器表,将所有“距离”字段+1

  1. 若收到的项目不在路由器表中,加入

  2. 若收到的项目距离小于路由器表中的记录,更新

若三分钟没有收到相邻路由器的更新,将该邻居设为16,不可到达。