网络层与运输层的不同之处在于，运输层只存在于主机中，为不同主机进程之间提供通信服务，而网络层存在于主机和路由器中，为不同主机之间提供通信服务。
4.1 概述
计算机网络采用分组交换技术，发送方主机的网络层将运输层的报文段封装成网络层分组，将分组向相邻的路由器发送；各路由器的网络层将分组从输入链路转发到合适的输出链路；接收方主机的网络层接收来自相邻的路由器的分组，解封出报文段，向上交付给运输层。
1、网络层功能
将分组从发送主机到接收主机，主要包括
转发：当分组到达某路由器的输入链路时，该路由器必须将其移动到合适的输出链路，由分组首部和转发表决定。
选路：通过若干路由器的转发，形成从发方到收方的传输路径。一般由路由器上的选路算法(路由协议)来创建维护转发表。
2、转发表
每台路由器都有，也叫路由表，是分组的目的地址或连接标识与路由器输出链路的映射表，由选路算法决定。
集中式选路算法：在某个中心设备运行。
分布式选路算法：在多个路由器分布式运行(常用)。
路由器根据到达分组的目的地址或输入连接ID查转发表，找到相应的输出链路接口，转发出去。
3、术语
分组交换机：根据分组的首部值查转发表，将分组从输入链路接口转发到某个输出链路接口。
链路层交换机：工作在链路层，根据目的设备链路层地址查转发表。
路由器：工作在网络层，根据目的设备的网络层地址查转发表。
4、网络连接
传输层连接：在进程数据传输之前，双方进程经过三次握手建立端到端连接，不需要负责具体传输路径。如因特网的TCP协议。
网络层连接：在主机数据传输之前，经过双方主机以及所选路径上路由器之间相互握手，建立连接，需要负责选择具体路径。如ATM、帧中继网络的网络层。因特网的网络层使用无连接方式(IP协议)。
网络层可能提供的服务有确保交付、时延有上界、分组有序交付、确保最小带宽、确保最大时延抖动(两个连续分组的发送时间间隔与其接受间隔的差异不超过特定值)、安全(机密性、数据完整性和身份鉴别)，但因特网的网络层都不提供。
因特网网络层提供无连接的、尽力而为的服务(best-effort service)，相当于根本无服务。不保证分组的传输时延，不保证分组的按序接收，不保证分组的最终交付，但措施少，效率高。
ATM网络层采用面向连接的网络层，可为不同的连接提供不同服务，有恒定比特率CBR(Costant Bit Rate)服务和可用比特率ABR(Available Bit Rate)服务。
CBR服务是标准的ATM服务，可用于需要实时通信、固定比特率的音视频流传输，目标是用分组交换模拟电路交换，在发收主机之间实现具有按序到达、低时延抖动和固定带宽的传输。
ABR服务比尽力而为服务好一点，保证最小信元传输速率，如资源允许，速率可能更高；能按序达到，但不保证时延和丢包；能够为发送方提供拥塞反馈信息(如拥塞比特，路由器接收速率等信息)。
4.2 虚电路和数据报网络
4.2.1 虚电路网络
如X.25、帧中继、ATM等网络，是一种面向连接的分组交换网，通信设备根据分组的虚电路号查转发表来转发分组。
1、虚电路VC
源和目的主机之间建立一条固定连接路径：经过多条链路和路由器。同一会话的分组都沿此路径传送。一条链路上可同时通过多条虚电路（非独占）。
VC号：路径上每段链路的编号(仅具有局部意义)。
转发表：每台路由器中都有(主机也有，但简单)，含VC号与端口信息。设备根据分组首部的VC号查转发表来转发分组，并修改分组的VC号。
2、转发表
转发表的维护：创建新的表项，建立连接时，路径上各路由器的转发表就增加一行表项；删除一个表项，拆除连接时，路径上各路由器的转发表就删除对应表项；一个连接的每条链路采用不同本地VC号，优点是减少VC字段的长度(因为全网通信量大)，路由器间无需交换大量报文，来约定全局统一的VC号。
虚电路工作的三个阶段：虚电路建立，在发送方与接收方之间通过呼叫(1~4步)建立一条虚电路，即确定路径，并为其上的每条链路分配一个VC号，进行相关路由器转发表的更新、资源预留等；数据传送，沿该虚电路传输各分组(5~6步)，路由器收到分组，根据分组VC号查转发表，得到出链路VC号和出接口，更改跟组VC号，再转发；虚电路拆除，一方通知另一方结束呼叫，删除相关路由器的转发表项，并释放资源。
信令报文：虚电路建立与拆除时主机及路由器之间传递的报文。
信令协议：交换信令报文的协议。
4.2.2 数据报网络
如因特网，是一种无连接的分组交换网，网络设备根据分组的目的地址转发分组。无呼叫过程建立连接，无固定路径，同一会话的分组可能选用不同的路径，因为路由器的转发表在选路算法作用下，会随网络变化；而在虚电路网络中，连接建立后，同一会话的分组传输路径相同。
传输过程：发送方给各分组加上接收方地址，并送入网络；各分组经过若干路由器存储转发，到达接收方，由于路由器的转发表通常是动态的，所以各分组走的路径可能不一样。
数据报网络的路由器转发：路由器根据分组的目的地址查询转发表，决定输出接口，并转发。每台路由器都有转发表，含目的地址与数据接口的映射表，合并表项及默认表项。
路由器的查表方法：将分组目的地址前缀与转发表的前缀比较，若存在一个匹配，则向对应输出链路转发，若不存在匹配，使用默认路由表项。
虚电路服务：采用分组交换、面向连接、固定路径、按序到达、带宽与时延波动小；不同通信共享使用链路(对比：电路交换通信独占电路，带宽时延固定)；通过呼叫建立连接；网络复杂，但端系统简单；用于X.25，帧中继，ATM等网络的网络层。
数据报服务：采用分组交换、无连接、无固定路径、不保证按序到达、带宽与时延波动大；不同通信共享使用链路；网络简单，端系统复杂：如计算机，可靠通信由计算机高层来实现，如实现按序交付、可靠传输、拥塞控制等；用于因特网的网络层。
4.3 路由器
路由器：实现网络层转发，将分组从输入链路传送到合适的输出链路。
路由选择处理器：执行路由协议、更新转发表、执行网络管理功能。
4.3.1 输入端口
输入端口：实现物理层功能；实现链路层解封功能；查找、排队、等待转发；将路由信息分组传给路由选择处理器，用于更新转发表。通常，路由器的多个端口集中实现在一块线路卡上，对于双向链路，输出端口与其输入端口在同一线路卡上成对出现。
查找：输入端口根据分组的目的地址查找转发表，确定通过交换结构后的输出端口，为此，每个输入端口存放一份转发表拷贝，由路由选择处理器更新。
查转发表：规则为最长前缀匹配规则，若无匹配，则使用默认表项，否则查表失败。查表速度与路由器速度、链路速率、查找算法等相关，目标是输入端口的查表速度超过分组平均输入速率。即一次查找的时间小于输入端口接收一个分组的时间，这样就不容易排队。
查找算法：当网络速率为吉比特，转发表的查找必须在纳秒级，需使用高效查找方法。
线性查找：顺序查找表项，不适用于大的转发表。
二分查找：用于大的转发表，所有表项都在一棵二叉树中表示，可以高效地表达和查找。树的每一层对应目的地址的一个比特，从树的根节点开始，按目的地址比特信息在树中流动，最多经过32个比特进入叶子节点，即可知转发端口。
其他高效查找方法：高速缓存(cache)，存储最近查找过的内容；通过硬件实现查找，如采用内容可寻址内存(CAM)，可在常数时间返回结果。
输入端口可能的问题：分组阻塞(blocked)，其他输入端口正在使用交换结构，被阻塞的分组在输入端口处排队等待。
4.3.2 交换结构
交换结构的作用是将分组从输入端口转发到输出端口，分为内存交换，总线交换，纵横式交换。
1、内存交换
早期用计算机作为路由器，CPU完成路由选择处理器功能，输入与输出端口类似I/O设备，当分组到达输入端口时，通过中断向CPU发出信号，将分组拷贝到内存中，CPU根据分组目的地址查表，将该分组拷贝到对应输出端口内存中。现在的路由器由输入线路卡执行查找和将分组存储到对应输出端口内存的功能，无需CPU参与。
2、总线交换
输入端口通过共享总线将分组直接传送到输出端口，不需要路由选择处理器的参与。每次只能有一个分组在总线传送。若总线忙，则分组暂时阻塞，在输入端口排队。路由器交换带宽受总线速率限制，用于小网络的路由器。
3、纵横式交换
如纵横式交换机，含$2n$条总线，实现$n$个输入端口与$n$个输出端口连接，交叉点由控制器开合。可并行转发多个分组，只要其输入和输出总线不冲突。若分组被阻塞，在输入端口排队。
4.3.3 输出端口
将分组传输到输出链路上，这包括排队、链路层和物理层功能。当交换结构到输出端口的速率超过输出链路速率，就需要排队。
排队：路由器的输入和输出端口都可能排队，排队位置取决于输入线路速率、交换结构速率、输出线路速率等。假定路由器有$n$个输入端口和$n$个输出端口，输入线路速率与输出线路速率相同。令交换结构速率为将分组从输入端口移动到输出端口的速率。
若交换结构的速率小于输入线路速率的$n$倍，在某些输入端口排队，最坏情况：$n$条输入线路同时接受分组。
若交换结构的速率大于输出线路速率的$n$倍，将在某些输出端口排队。最坏情况：分组都被发往同一个输出端口。
分组调度程序：在输出端口队列，选择输出的分组。规则有先来先服务FCFS，加权公平排队WFQ：在不同通信之间公平地共享输出链路。
分组丢弃：若输出端口的队列已满，可丢弃到新的分组，或删除一个或多个已排队的分组，为新分组腾空间。
主动队列管理AQM：在队列满之前，通过丢弃分组(并向发送方报告)或在分组首部标记(由接收方告知发送方)，以便向发送方提供拥塞信号。如广泛使用随机早期检测RED算法。
随机早期检测RED算法：设置最小阈值$min{th}$和最大阈值$max{th}$，若输出端口的平均队列长度小于$min{th}$，到达分组直接进入队列；大于$max{th}$，到达分组全部被标记或丢弃；在$[min{th},max{th}]$之间，到达分组以某种概率被标记或丢弃。
线头HOL(head-of-the-line)阻塞：输入队列中后面的分组被位于线头的分组阻塞(即使其对应的输出端口空闲)，等待交换结构发送。
4.4 因特网的网络层
网络层的协议：IP、ICMP、IGMP、ARP、RARP、路由协议等。核心协议是IP协议。
互联网协议IP：提供无连接、不可靠、尽力而为的主机间分组交付服务。
IP数据报分片和重组
链路层帧有最大传输单元(MTU:帧数据区的最大长度)，不同网络帧的MTU不同。
分片：在源主机或路由器，一个大的IP数据报被分割并封装成几个帧传输到下一个网络。
重组：数据报分片在目的主机重组。
相关字段：标识、标志、片偏移。
IP地址：网络层地址，用于标识设备的网络连接。路由器通常有多个IP地址。IPv4长度为32位，IPv6为128位。
IPv4地址用点分十进制表示，由网络号(指明主机所在的网络)和主机号(指明主机所在的设备)组成。
4.5 选路算法
每个路由器都有一个转发表，选路算法决定表的内容。选路指由分组所经过的路由器的转发表，确定分组的传输路径。
默认路由器(默认网关)：主机去往其他网络的首路由器。
源路由器：源主机的默认路由器。
目的路由器：目的主机的默认路由器。
从源主机到目的主机的选路=从源路由器到目的路由器的选路。
选路算法的目的是找到一条从源路由器到目的路由器的最小费用路径。这里费用指传播距离、传播时延、传输成本等。
用网络拓扑图(用图表示的网络结构)来分析选路算法：节点表示路由器，边表示路由器之间的链路，边权表示链路费用，选路算法的目的是在给定网络中找出从源节点到目的节点的最低费用路径。
选路算法的分类
静态或动态：人工手工配置或路由协议自动配置。
全局式或分散式：需要全局网络知识或只需周围部分网络知识。
负载敏感或负载迟钝：链路费用是否反应链路拥塞水平，英特网采用后者。
因特网常用动态全局负载迟钝的链路状态LS选路算法和动态分散负载迟钝的距离向量DV选路算法。
4.5.1 链路状态选路算法LS
路由器节点需要知道全网的网络拓扑和链路费用。获取全局信息的方法是每个节点知道直连链路的费用，都向其他所有节点广播，最终所有节点都知道了全网视图。然后每个节点采用Dijkstra算法计算本节点去往其他节点的最小费用路径，并以此决定本路由器的转发表。
Dijkstra算法，太基础，略。
LS算法的不足：可能产生路由振荡，即计算出的方向不断反转陷入死循环。避免方式是避免所有路由器同时运行LS算法，让每台路由器发链路通告的时间随机化。
4.5.2 距离向量选路算法DV
分布式：一开始，每个路由器节点知道直接相连链路的情况，每个节点从其邻居接收信息(路由通告)并计算，最后每个节点都知道去往各地的最佳下一跳节点，每个节点不需要全局网络知识。
异步：不要求所有节点步伐一致地操作。
迭代：邻居之间信息交换一直持续到无新信息需要交换为止。
自我终止：算法能自行停止。
用$d_x(y)$表示节点$x$到节点$y$的最小费用，有$Bellman-Ford$方程：
其中$v$是指$x$的任何邻居。
1、DV算法
设
$D_x(y)$：节点$x$到节点$y$的当前最小距离(费用)。
$D_x$：节点$x$的当前最小距离向量$D_x=[D_x(y):y\in N]$，即节点$x$到$N$中所有节点的估计费用。
基本思想：每个节点$x$维护$D_x$，即本节点去往所有节点的当前最小费用。若$x$发现变化(如发现直连链路变化，或者邻居$w$发现变化并发来它的路由通告)，都要重新计算$D_x$，若$D_x$有变化则通告其所有邻居。
(1)初始化
给出本节点$x$到任一目的点$y$的$D_x(y)$，若$x$与$y$是邻居，则$D_x(y)=c(x,y)$，否则$D_x(y)=\infty$。
此时，$x$不知道任意邻居$w$去往目的地$y$的最小距离：$D_w(y)=\infty$。
把$D_x$发给每一个邻居$w$。
(2)计算距离向量
$x$发现直连链路变化，或收到某邻居的路由通告时，重计算$D_x$，$D_x(y)=\min_v{c(x,v)+D_v(y)}$，$v$为$x$的任意邻居，即$x$到$y$的最小费用=$x$通过任意邻居去往$y$费用的最小值。
若$D_x$有变化，将$D_x$通告所有邻居；若所有节点:都无变化，算法静止等待。
2、链路费用变化的影响
“好消息“(如链路费用减少)传的快，”坏消息“(如链路费用增加)传的慢。
链路费用增加可能造成路由选择环路问题，又称计数到无穷问题。原因是为到达目的地，$y$通过邻居$z$选路，$z$反过来又通过邻居$y$选路。
毒性逆转法可部分解决路由选择环路，基本思想：如果$z$通过邻居$y$选路到达目的地$x$,则$z$对$y$撒谎说，$z$到$x$的距离是无穷大，这样可避免$y$反过来选择经过$z$去往$x$的可能，从而避免路由选择环路，实现快速收敛。
毒性逆转法的局限是，对于有三个或更多节点的环路，毒性逆转不能解决计数到无穷问题。
LS与DV算法都在因特网中广泛应用，下为两者区别
工作过程：LS算法每个节点与所有其他节点广播交流，每个节点最终知道全局网络知识；DV算法每个节点只与邻居互相交流，每个节点无需知道全局网络知识。
报文复杂性：LS算法报文包含本节点直连链路信息，向所有节点传送，当直连链路的费用变化时，必须重新通知所有节点，DV算法报文包含有本节点去往其他节点的最小估计费用，只向邻居传递，当直连链路变化或收到邻居路由通告DV时，重计算DV，如DV有变化，再通知所有邻居。
收敛速度：LS算法为$O(N^2),N$为节点数；DV算法收敛较慢，还可能遇到路由选择环路问题。
健壮性：当一台路由器发生故障错误时，LS算法路由器会广播错误的局部直连链路信息，而各路由器根据全局网络各自计算转发表，局部错误信息的影响较小，有一定健壮性；DV算法错误信息由近至远影响其他节点的选路，有可能使其他路由器大量流量引向故障路由器(好消息传播快)。
4.5.3 层次选路
前面的选路算法，要求网络中所有路由器执行相同选路算法，难以满足大的网络，难以实现管理自治。
大网络的需求：路由器很多，网络与主机更多，各路由器的转发表非常大，选路计算非常复杂。LS算法向所有路由器广播链路状态，开销大；DV算法大量路由器可能不收敛。
管理自治的需求：希望自己的网络运行特定的选路算法，或对外部隐藏网络结构等。
可将一个大的网络划分成若干自治系统(Autonomous System)，即一个由相同机构管理，运行相同选路算法的大的网络。
内部路由协议：用于自治系统内部，有采用DV算法的RIP路由信息协议，采用LS算法的OSPF开放最短路径优先协议。
外部路由协议：用于自治系统之间，有采用DV算法的BGP边界网关协议。
网关路由器(又称AS边界路由器)：负责将一个AS内的分组转发到另一个AS。
网关路由器的转发表：由内部路由协议和外部路由协议共同决定。
自治系统的优点：减少规模大的网络选路计算的复杂性，AS内部路由器运行相同的自治系统内部选路协议，仅需要知道本AS内的路由器与网关路由器；各AS之间，运行相同的AS间选路协议。
管理职权灵活：一个组织可自行选择AS内部选路协议，每对相连的AS运行相同AS间选路协议，交换信息。
组播特性：实现一个发送方向多个接收方传送相同数据，带宽利用率高，只需要较少的主机/路由器来处理，应用如视频/音频广播(电视，无线电类)，视频会议，实时新闻转发。属于因特网组管理协议IGMP(网络层协议，在IP之上)