• 4.1 概述
• 4.2 虚电路和数据报网络
• 4.3 路由器
• 4.4 IP
• 4.5 选路（routing）算法
• 4.6 因特网的选路：RIP、OSPF、BGP
• 4.7 广播和多播选路

4.1 概述

网络层的PDU称为Datagram。
路由器的主要作用便是将数据报从入链路转发到出链路。

转发和路由

转发：查表，选择输出端口，将分组传到下一跳。
选路：指分组从源到目的地时，决定端到端路径的网络范围的进程。这是全局路径！

网络服务模型

因特网的网络层提供了单一的服务，被称为尽力而为服务。但是有些其他网络体系结构（ATM）定义和实现了超过因特网尽力而为服务的服务模型。ATM相当于一条专线，保证服务质量，但是价格较为昂贵。

4.2 虚电路和数据报网络

虚电路：仅在网络层提供连接服务的计算机网络。
数据报网络：仅在网络层提供无连接服务的计算机网络。
说明，在网络层两者只能使用一个。

虚电路网络（类似于电话系统）

ATM、帧中继和X.25的体系结构是虚电路网络。
在网络层建立一条连线，然后数据通过这条线路传输。现代因特网不使用虚电路网络。

数据报网络（类似于邮政系统）

• 不在网络层进行呼叫
• 不维持端到端的连接状态
• 路由器根据目的IP地址进行转发

路由器没有必要记录40亿（2^32）个路由，只需要进行最长前缀匹配原则。

image.png

4.3 路由器工作原理

路由器收到一个封包，检查目的IP地址，查路由表，然后决定输出端口。路由器对单个封包的处理很简单，复杂之处同时处理很多封包和路由表的建立和更新（需要一些协议）。

路由器由四部分组成：

• 输入端口
• 交换结构
• 输出端口
• 选路处理器

输入端口

输入端口实际就是一块网卡。

交换结构

• 经内存交换：最简单、最早的路由器
• 经总线交换：广播，需要抢占
• 经一个互联网交换：相当于2n条总线

输出端口

当交付给输出端口的速率超过输出链路速率时，就需要排队与缓存管理功能。

路由器体系结构.png

4.4 IP协议

• IPv4 （32bit）
• IPv6 （128bit）

IPv4数据报格式.png

IPv4编址

一台主机通常只有一条链路连接到网络；当主机中的IP向发送一个数据报时，它就在该链路上发送。主机与物理链路之间的边界叫做接口（interface）。

也就是说，IP是与接口绑定的，而不是与主机。对于路由器来说，有多少端口就有多少接口，也就是有多少IP。

获取一块地址

• 由ISP分配

获得主机地址

• 手动更改
• DHCP：动态分配

网络地址转换（NAT）

把网络分为内网和外网，内网主机拥有相同的IP地址。NAT路由器使用NAT转换表，并且在表项中包含了端口号和IP地址。使用NAT协议的主机可以主动连接外部，但是外部无法主动连接内部。具有一定的安全性作用。

但NAT存在争议，它使用了端口号以定位内网的主机。违反了路由器只处理第三层的规则。另外，解决网址枯竭问题的方法应该是IPv6，而不是权宜之计NAT。

ICMP，网际控制报文协议

当有运行一次Telnet、FTP和HTTP会话时，会遇到一些诸如“目的网络差错报告”之类的错误报文。这种报文就是在ICMP中产生。

ICMP通常被被认为是IP的一部分。它在IP的上一层，但是不把它当作第四层。

IPv6

• 简单高效的40字节首部
• 报文不可分割

如何解决兼容问题？
采用隧道技术，把v6的报文包在v4的数据部分。

4.5 选路算法

选路算法的作用：找最短路径。

• 全局选路算法
• 分散式选路算法

链路状态选路算法

• 迪克斯特拉，Dijkstra

时间代价，O(n^2)

• 普瑞姆，Prim

距离向量选路算法

• Bellman-Ford算法
  

每个node会维持自己的向量和邻居的向量。

4.6 因特网中的选路

• RIP（AS内部）
• OSPF（AS内部）
• BGP（AS间）

RIP

基于距离向量选路算法；
两个路由器之间的代价为1；
最大跳数为15跳；
每30秒通过相应报文交换；
每个AS最多有25个路由器；
RIP是一个运行在UDP上的应用层协议。

OSPF

基于链路状态信息和Dijkstra最短路径算法；
与RIP不同，OSPF的权值可以自己定义；

BGP（或称BGP4）

不是世界标准，但是在业界应用广泛。
（详细看书4.6.3）

4.7 广播和多播选路

广播选路算法

• 无洪范控制
• 受控洪范
• 生成树广播

缺点：可能会绕路。

多播选路算法

• 距离向量多播选路，DVMRP
• 协议无关的多播选路协议，PIM

参考文献:
國立清華大學開放式課程OpenCourseWare(NTHU, OCW) - 計算機網路概論