简介

• 网络层功能：
  
  1. 转发（forwarding）：在单一路由器中，分组从一条输入链路转移到一条输出链路。
  2. 路由选择（routing）：在网络范围内，分组从源到目的地采取的端到端路径。
     
     • 转发表（forwarding table）通过检查到达分组的首部转发。
     • 转发表中的值由路由选择算法决定，分为集中式和分布式两种。
  3. 连接建立（connection setup）。某些网络层结构（ATM，帧中继，MPLS等）要求从源到目的选择的路径彼此握手。
• 因特网提供尽力而为服务（best-effort service）。
• ATM体系提供恒定比特率（Constant Bit Rate, CBR）和可用比特率（Available Bit Rate, ABR）服务。
• 虚电路网络（Virtual-Circuit, VC）：仅在网络层提供连接服务。
  
  • 两个端系统之间的路由器都要参与虚电路建立，且每台路由器完全知道经过他的所有虚电路，维护连接状态信息。
  • 启动和终止连接的报文称为信令报文。
• 数据包网络（datagrame network）：仅在网络层提供无连接服务。
  
  • 路由器使用最长前缀匹配规则（longest prefix matching rule）。
  • 转发状态信息表变化相对较慢。
  • 转发表能够在任何时刻修改，同一系列的分组可以走不同路径，并可能无序到达。

路由器

结构

• 
• 输入端口：
  
  • 物理层和数据链路层功能。
  • 分组经历查找、转发、排队过程。
  • 查找功能，通过查询转发表决定路由器的输出端口，每个输入端口会有转发表的影子副本。
• 交换结构：将输入端口和输出端口相连。
  
  • 分为内存交换、总线交换、纵横式交换。
• 输出端口：
  
  • 执行物理层和数据链路层功能。
  • 选择和取出排队分组进行传输。
  • 如果一条链路是双向的，则输入输出端口成对出现。
• 路由选择处理器：
  
  • 执行路由选择协议，计算转发表。
  • 网络管理。

排队

• 输入和输出端口形成分组队列，当队列增长，缓存空间耗尽，出现丢包（packet loss）。
• 输出端口排队
  
  • 通过分组调度程序，选择排队分组发送，如先来先服务（FCFS）、加权公平（WFQ）等。
  • 通过主动队列管理（Active Queue Management, AQM）在缓存满之前丢弃分组，如随机早期检测（Random Early Detection, RED），为输出队列维护加权平均值。长度

IP协议

• 网络层三个组件：IP协议、路由选择协议、因特网控制报文协议ICMP。
  

数据包格式

• 
• 版本号：包括IPv4、IPv6。
• 首部长度：通常20字节。
• 服务类型：区分不同类型数据报，如实时流量（IP电话）和非实时流量（FTP）。
• 数据报长度：首部+数据长度，很少超过1500字节。
• 标识、标志、片偏移：用于分组分片。IPv6不分片
• 寿命（Time-To-Live, TTL）：经过一台路由器，TTL减一。
• 上层协议：数据报交付给哪个应用层协议。
• 首部检验和：只对首部校验，TCP/UDP与IP不一定属于同一协议栈（如ATM代替IP）。
• 源和目的IP。
• 选项：IPv6不使用。
• 数据：交付给运输层的数据，也可能是ICMP报文等其他类型。

IP数据报分片

• 链路层MTU限制数据报长度，不同链路使用不同的协议，MTU不同，所以一个数据报可能分成数个小的数据报，称为分片（fragment）。
• 数据报在端系统中重新组装，然后上传传输层。
• 标识标记初始IP数据报。
• 最后一个片的标志为0，其余为1。
• 偏移字段指定该片在初始IP数据报的位置。
• 

IPv4地址

• 每台主机和路由器接口拥有自己的IP地址。
• 因特网地址分配策略为无类别域间路由选择（Classless Interdomain Routing, CIDR）。
  
  • a.b.c.d/x ：x最高比特为IP地址的网络部分，称为前缀。
  • 地址聚合（address aggregation）：使用单个网络前缀通告多个网络的能力，也称为路由聚合或路由摘要。
• IP地址、DNS根服务器由ICANN管理，IP地址块也可从ISP获得。

DHCP

• 动态主机配置协议（Dynamic Host Configuration, DHCP），允许主机自动获取一个IP地址，还有其他信息，例如子网掩码、第一条路由器地址（默认网关）、本地DNS服务器地址。
• DHCP是C-S协议，客户是新到达的主机，服务器是子网中的DHCP服务器或者是DHCP中继代理（通常是路由器）。
• 4个步骤
  
  1. DHCP服务器发现。使用广播目的地址255.255.255.255和源地址0.0.0.0，进行链路层广播。
  2. DHCP服务器提供。使用广播发送推荐IP、地址租用期等信息。
  3. DHCP请求。从一个或多个服务器提供的选择中响应，回显配置参数。
  4. DHCP ACK。对请求报文响应，证实要求的参数。
     
• 不足：移动节点连接到一个新的子网，就要从DHCP获得新的IP，不能维持远程应用之间的TCP连接。

NAT

• 网络地址转换（Network Address Translation, NAT），通过NAT转换表管理小型子网络，对外隐藏网络细节。
• 子网络中的主机使用专用地址（10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16），该地址只有在该网络中才有意义，不能用于因特网。
• NAT路由器将因特网的IP和端口号、子网的IP和端口号进行转换，对外行为就像具有单一IP的单一设备。
  
• 问题
  
  1. 使用端口号，影响子网中的服务器。
  2. 路由器处理传输层报文（提取端口号）。
  3. 妨碍P2P应用。一方在NAT之后，需要通过中间对等方创建TCP连接，这被用于NAT穿越。

UPnP

• 通用即插即用，主机上的应用程序能够请求NAT映射，使得外部节点能够发起到该主机的TCP连接。

ICMP协议

• 因特网控制报文协议，主机和路由器之间沟通网络信息。
• ICMP报文封装在IP**数据报**中，占用数据字段，为IP数据报的有效载荷。
• ICMP报文包括类型字段、编码字段、引起该ICMP报文的IP数据报的手部和前8个字节的内容。
  
  
  • ping发送类型8编码0的ICMP报文到指定主机，目的主机发回类型0编码0的ICMP报文。

IPv6

• 报文格式
  
  
  • 地址：由32比特增加到128比特。任播地址将数据报交付给一组主机中的任意一个（例如GET一组镜像站点中的某个）。
  • 下一个首部：与IPv4**协议**字段相同，表示数据字段交付上层哪个协议。
• 取消的字段
  
  • 分片：如果数据报太长，发送ICMP差错报文。
  • 首部校验和，TCP和UDP、以太网已经校验。
  • 选项。
• v4到v6的迁移，两种双栈（dual-stack）方法。
  
  1. 接受结点和发送节点如果都是IPv6，则使用v6，否则使用IPv4。
  2. 将IPv4路由器集合作为隧道（tunneling），将IPv6数据报放入IPv4的数据字段。

路由选择

算法

LS算法

• 链路状态(Link State, LS）算法，是一种全局式路由选择算法。每个结点知道网络拓扑和链路费用，一般使用Dijkstra算法计算最低费用路径。
• 链路状态通过链路状态广播（link state broadcast）完成。
• 问题
  
  • 若链路费用依赖于链路负载，则每次运行LS算法时，下一条路由可能会在两个路由之间振荡。解决方法，使得并非所有路由器在同一时间运行LS。
  • 如果路由器保持相同周期运行LS，最终即使初始时刻一致也会同步。解决方法，每台路由器发送链路通告的时间随机化。

DV算法

• 距离向量（Distance-Vector, DV）算法，是一种分布式路由选择算法。每个结点知道到直接相连的邻居的费用、结点的距离向量（x->y的费用估计）、每个邻居的距离向量。
• 当直接相连的链路费用变化或者邻居的距离向量更新，使用Bellman-Ford方程更新距离向量。
  
  Dx(y)：从x到y的距离。v：邻居。
• DV算法费用减少的好消息传的快，费用增加的坏消息传的慢，甚至可能无穷计数。
• 两个直接相邻的邻居结点的无穷计数问题用毒性逆转（poisoned reverse）解决：如果z–>y–>x，z向y告知z到x的距离无穷大。

两种算法比较

• LS算法中，结点经广播和其他所有结点交流；DV算法中，结点只和直接相连的邻居交流。
• 报文复杂度：LS需要广播，报文复杂度大比DV大。
• 收敛速度：DV收敛慢，还可能出现选择环路、无穷计数等问题。
• 健壮性：DV中结点的不正确计算会扩散到整个网络。LS计算分离，有一定健壮性。

层次路由选择算法

• 将路由器组织为自治系统（Autonomous System, AS），每个AS**规模相对整体而言较小，而且可以管理自治**。

AS内的路由选择

RIP协议

• 路由选择信息协议（Routing Information Protocol, RIP），是一种距离向量协议，使用跳数作为费用的测度。
  
  • 跳：从源路由器到目的子网（包括目的子网）的最短路径经过的子网数量。
  • 一条路径最大费用为15。
• RIP使用RIP响应报文（RIP response message）更新路由选择信息，也称RIP通告（RIP advertisement）,大约30s交换一次。
• 每台路由器维护一张路由选择表（routing table），包括该路由器的距离向量和转发表。转发表包括目的子网、下一台路由器、到目的子网的跳数。
  
• RIP是一个运行在UDP使用520端口的应用层协议。例如，UNIX的路由器中，一个routed进程执行RIP，维护路由选择信息并和相邻路由器中的routed进程交换。

OSPF协议

• 开放最短路优先（Open Shortest Path First, OSPF），是一种链路状态协议，泛洪链路状态信息，使用Dijkstra最低费用路径算法。
• 优点
  
  1. 安全。使用鉴别，让受信任的路由器参与协议。
  2. 多条费用相同路径。多条路径费用相同时，使用多条路径分担流量。
  3. 多播。MOSPF支持多播。
  4. 支持层次结构。一个OSPF自治系统可分为多个区域，每个区域各自运行OSPF，区域边界路由器（area border router）负责向流向区域外的分组提供路由选择，主干（backbone）区域为区域之间的流量提供路由选择。

AS间的路由选择

• 边界网关协议（Broder Gateway Protocol, BGP）
  
  1. 从相邻AS获得子网可达性信息。
  2. 向本AS所有路由器传播这些可达性信息。
  3. 基于
  4. 可达性信息和AS策略，决定到达子网的路由。

广播和多播

广播

• 通过N次单播实现广播（broadcast routing）效率低。

实现方法

1. 无控制泛洪（flooding）。源节点向所有邻居结点发送副本，某结点接收副本之后向除了从其接收分组的邻居转发副本。但这样可能产生广播风暴（broadcast storm）。
2. 受控泛洪。
   
   1. 序号控制泛洪。将广播序号放入分组，每个结点维护已经收到复制转发的源地址和广播分组序号列表。接收广播分组时，如果该分组在序号列表中，丢弃分组；否则，向除来源之外的邻居转发。
   2. 反向路径转发（Reverse Path Forwarding, RPF）。路由器接收广播分组，仅当该分组的到达链路位于自己返回源的最短单播路径上，才向除来源之外的邻居转发。
3. 生成树广播。广播分组沿着生成树中的链路转发，可避免冗余广播。基于中心的方法构造生成树是，先定义一个中心结点。结点加入生成树时，单播加入树报文，报文经过的路径加入生成树。

多播

• 使用D类IP地址（1110开头，224-239）表示一个多播组（multicast group）。每台主机有唯一的单播IP，完全独立于所参与的多播组的地址。
• 因特网网络层多播组件：因特网组管理协议（IGMP）、多播路由选择协议。

IGMP

• 运行在主机和直接相连的路由器之间，通知路由器主机上运行的一个应用程序加入特定多播组。
• IGMP报文类似ICMP报文，分装在IP数据报中。
• 加入多播组
  
  1. 路由器通过向所有主机发送membership_query报文查询多播组集合，主机用membership_report响应。
  2. 主机也可直接发送report报文。
• 离开多播组
  
  1. 主机发送membership_leave报文。
  2. 当无主机响应给定组地址的membership_query报文时，则无主机在这个多播组。
     
     • 软状态：状态如果未被显示更新，则通过超时事件删除。

多播路由选择算法

• 确定一颗多播路由选择树，连接所有和属于该多播分组的主机相连的路由器。
• 树的构建方法
  
  1. 组共享的树。类似广播生成树，可以使用中心选择算法。
  2. 基于源的树。每个源使用RPF算法构造树，但是需要剪枝（pruning），以防下游大量不在多播组的路由器收到不需要的分组。
     
     • 一台路由器如果收到多播分组，但是无法加入多播组，向上游路由器发送剪枝报文。如果一台路由器从每个下游路由器收到剪枝报文，向上游发送剪枝报文。