网络层

Mar 31st, 2020

• 在计算机网络中进行通讯的两个计算机之间可能要经过许多节点和链路,也可能要经过多个通过不同的路由器互连的通信子网。

• 网络层的任务就是要选择合适的路由，使发送站从传输层所传下来的分组能够正确无误的按照地址找到目的站，并交付给目的站的传输层。

  

网络层模型

• 网络层是 通信子网的最高层 ，对上层用户屏蔽了子网通信的细节，如子网类型、拓扑结构、子网数目，向上层提供一致的服务、统一的地址。

网络层的功能

• 基本功能 : 实现端到端的网络连接，屏蔽不同子网技术的差异，向上层提供一致的服务。

• 主要功能

  • 路由选择和转发

  • 通过网络连接在主机之间提供分组交换功能

  • 分组的分段与成块，差错控制、顺序化等

• 好处 : 最佳路径、隔离广播、提高性能及安全性

• 主要采用无连接方式、分组交换方式(IP传输方式)

广播风暴：通过发送广播影响广播域中的所有接收者损害他人利益。 如何对应广播风暴： 1. 数据链路层：VLAN的方式隔离广播 2. 网络层：通过路由器隔离广播

传输方式

• 大多数局域网的节点可以通过广播发出数据。(无连接)

• WAN中大多数采用point to point的方式，即点到点的方式。(无连接)

• Internet通信子网结构复杂(覆盖多个LAN、WAN)，经过多个节点、多个路径可达。

• 网络层向传输层提供的服务:面向连接 or 无连接?可靠交付应当由谁来负责?是网络还是端系统?

  • 电信派 : 主要采用面向连接的方式。可靠性可由低层实现(通信子层)，在分组交换中采用VC(Virtual Circuit)。

  • Internet派 : 终端(host)都是智能设备，可以处理差错问题。底层通信的出错率已很低，没有必要在底层处理差错问题。所以采用无连接的方式，把每个报文封装在单独的地址里，独立路由，可靠性由高层实现。

• Cerf and Kahn’s internetworking principles:

  • minimalism, autonomy - no internal changes required to interconnect networks

  • best effort service model

  • stateless routers

  • decentralized control

分组交换

虚电路服务

• 在传送数据之前，首先通过呼叫建立一条虚电路

• 所有分组沿同一条路径传送，并且按发出顺序到达目的地

• 类似电路交换

• 在 source-dest 路径上的路由器为每个报文(data flow)维护状态

• 建立连接之后，分组中只需要携带连接标识

• 可以在建立连接时协商参数、QoS、开销等

• 差错处理及流控可以由网络负责，也可以由用户主机负责

• 建立虚电路(Virtual Circuit)，以保证双方通信所需的一切网络资源。虚电路表示这只是一条逻辑上的连接。

  

数据报服务

因特网采用的设计思路

• 网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。

• 网络在发送分组时不需要先建立连接。每一个分组(即 IP 数据报)独立发送，与其前后的分组无关(不进行编号)。

• 网络层不提供服务质量的承诺。即所传送的分组可能出错、丢失、重复和失序(不按序到达终点)，当然也不保证分组传送的时限。差错由末端解决，如发送请求某个丢失的包。

• 由于传输网络不提供端到端的可靠传输服务， 这就使网络中的路由器可以做得较简单。

虚电路和数据报比较

	虚电路	数据报
是否需要先建立连接	需要	不需要
分组中的目的地址	VC标识	完整地址
路由器中的路由表	需要为每个虚电路保存一个路由表	只需要一个简单的路由表
选择传输路径	在VC建立时选路 所有分组路由相同	每个分组独立选路 路由可能不同
路由器故障带来的影响	所有经过该路由器的VC都将终止	几乎不受影响
拥塞控制	易于实现	很难实现
差错控制和流量控制	由子网负责	由主网负责

路由

经过一个中转站称为 “一跳”(hop) ，经过5个中转站称为5跳，总共经过6个广播域。

路由表

• 虚电路的路由表

  • 路由表在建立虚电路(虚呼叫)时确定。分组在传送时只需携带虚电路号，虚电路号只具有本地意义，根据虚电路建立顺序由各主机、各结点自主排序，入出口号不一定相同。

• 数据报的路由表

  • 每个分组都需要携带完整的目的地址。每个结点保存一个到网内其他结点的输出线选择表。

    

路由器

• 工作在OSI网络层中，实现下三层的转换，还具有中继器、网桥的功能，能够识别网络层协议、网络地址。它的主要功能如下:

  • 划分子网;

  • 进行信息隔离;

  • 提高网络安全性;

  • 具有路由选择最佳性;

  • 容错和访问控制。

问：路由器和交换机的区别是什么？ 答：路由器是网络层中的定义，可以隔离广播，屏蔽底部差异性；交换机是数据链路层的定义。

Internetwork

• Multiple incompatible LANs can be physically connected by specialized computers called routers

• The connected networks are called an internetwork

  • The “Internet” is one (very big & successful) example of an internetwork

Internet Protocol (IP)

Hour Glass Model 沙漏结构

可以看出IP一个协议撑起上面的各种协议又能屏蔽下面各种协议的差异。 上层的主要协议：TCP 和 UDP 下层的主要协议：Ethernet 和 PPP

- Everything over IP - IP over Everything

Internet的网络层结构

• 向上为传输层如 TCP、UDP 提供服务

• 向下屏蔽数据链路层

• 中间由路由表(routing table)和IP协议和ICMP协议组成

  • 其中路由表由 RIP, OSPF, BGP 等路由协议生成

  • IP 协议是核心

  • ICMP 是当IP出错的时候进行 error reporting

Internet 中的 IP

• IP协议是TCP/IP体系中两个最主要的协议之一。由于IP协议可以使互连起来的许多计算机网络能够进行通信，因此，TCP/IP体系中的网络层常常称为网际层(internet layer)。

• 网络互连依赖于与硬件地址无关的逻辑地址(IP地址)。

• Internet就是成千上万个IP子网通过路由器互连起来的国际性网络。

IP数据报

• 采用传统的硬件帧格式

  • 路由器要连接异构网络，而不同类型网络的帧格式不同(如:Ethernet、ppp、IEEE802.5等);

  • 路由器不能简单地格式化帧的头，因为两个网络可能使用不兼容的地址格式;而帧中的物理地址只作用在同一个网络中(一个广播域中)

• 必须采用统一的报文格式，即IP报文;并采用全球统一编址的、逻辑化的地址，即IP地址

  • 一个独立于底层硬件的报文格式。 即IP数据报(datagram)

    

IP 地址编址

• 当1981年9月第一次对 IP地址进行标准化时,IP地址采用32位比特进行全球唯一标识。

• 32-bit IP 地址 由以下两部分组成: 网络号(N)+主机号(H)

  
• 路由器利用IP地址来区别不同的网络，实现网络的互连和隔离，保持各个网络的独立性。

• 网络号和主机号合起来才构成一个完整的IP地址。同一个网络中的主机IP地址，其网络号必须相同。

• 网络号由网络号前缀组成，主机部分全为零。

• 给定网络号前缀的所有主机共享网络号前缀，而每台主机由唯一的主机号进行标识。

• 处于不同网络的主机必须具有不同的网络号前缀，但可以具有相同的主机号。

• IP 地址空间分为5类 : A类、B类、C类、D类、E类

• 各类具有不同的网络号前缀位数和主机号位数。

• 各类可分别表示不同大小的网络。

• 实际可供用户分配的只有A、B、C三类。

A类IP地址编址

• A类具有 8-bit 网络号前缀，其最高位置为0，其余7位为网络, 随后的 24-bit 为主机号。

• 最多可定义 2^7-2=126 个网络号(1~127)。

  • 网络号全0是保留地址，意思是 本网络

  • 网络号为127也是保留地址，作为本地软件 环回测试(loopback test) 本主机的进程之间的通信用。目的地址为环回地址的IP数据报永远不会出现在任何网络上，因为网络号为127的地址根本不是一个网络地址。

• 最多可定义 2^24-2=16,777,214 台主机。

  • 全0的主机号字段表示该IP地址是 本主机 所连接到的 单个网络地址 (e.g. 本主机连接到 5.6.7.8，则连接到的网络地址为 5.0.0.0)

  • 全1的主机号表示 所有的，因此全1的主机号表示该网络上的所有主机。

• IP地址 : N.H.H.H

B类IP地址编址

• B类网络号 具有 16-bit 网络号前缀，其最高两位置为10，其余 14-bit 为网络号，随后为16位的主机号。

• 最多可定义 2^14-1=16,383 个网络号(128~191)。

  • 前两位已经确定是01所以不可能出现全0或者全1的情况，但是实际上 128.0.0.0 是不可指派的，因而最小的可指派的网络号为 128.1.0.0 所以要减 1

• 最多可定义 2^16–2=65,534 台主机。

  • 同理A类地址，减2是为了扣除全0和全1的情况。

• IP地址 : N.N.H.H

C类IP地址编址

• C类具有 24-bit 网络号前缀，其中 3 个最高位置为110，其余 21-bit 为网络号, 随后为 8-bit 主机号。

• 最多可定义 2^21-1=2,097,152 个网络号(192~223)。

  • 同理B类地址，192.0.0.0 是不可指派的，最小的可指派网络地址为 192.1.0.0，所以要减1

• 最多可定义 2^8–2=254 台主机。

  • 同理A类地址，减2是为了扣除全0和全1的情况。

• IP地址 : N.N.N.H

D类IP地址编址

• D类最高的前4为置为 1110 ，用于多广播(224~239)

• 224.0.0.0~239.255.255.255

• 举例:

  • 224.0.0.1 LAN的所有系统

  • 224.0.0.2 LAN的所有路由器

  • 224.0.0.5 LAN的所有OSPF路由器

E类IP地址编址

• E类地址的最高前5位置为 11110 (240~255)

• 留作试验或未来的特殊使用

• 240.0.0.0~255.255.255.254

保留地址(不能分配)

• 在A至C类IP地址中，有若干地址有专门的用途或特殊意义，不能分配给主机。具体如下:

  • 网络地址 : 即主机号为全0，代表一个网络 例如 : 129.1.0.0，12.0.0.0

  • 广播地址 : 即主机号为全1，代表一个广播域 例如 : 129.1.255.255，12.255.255.255

  • 自 检 地 址 ( loopback address ) : 127.H.H.H (127.0.0.1)

一般不使用的特殊IP地址

网络号	主机号	源地址使用	目的地址使用	代表的意思
0	0	可以	不可以	在本网络上的本主机
0	host-id	可以	不可以	本网络上的某台主机 host-id
全1	全1	不可以	可以	只在本网络上进行广播(各路由器均不转发)
net-id	全1	不可以	可以	对net-id上的所有主机进行广播
127	非全0或全1的任何数	可以	可以	用于本地软件环回测试

127.0.0.1和0.0.0.0地址的区别 See Reference

专用地址与全球地址

• 问题 : 在内部使用的本地地址就有可能和互联网中某个 IP 地址重合，这样就会出现地址的二义性问题。

• 解决 : RFC1918指明了一些专用地址(private address)。专用(私有)地址只能用作本地地址而不能用作全球地址。在互联网中的所有路由器，对目的地址是专用地址的数据报一律不进行转发。

• 好处 : 解决IPv地址不够的问题，安全性提高。

私有地址(专用地址)

RFC1919规定:以下地址不能上Internet，只能作为内部地址或私有地址:

• A类(1个广播域) : 10.0.0.0~10.255.255.255

• B类(16个广播域) : 172.16.0.0~172.31.255.255

• C类(256的广播域) : 192.168.0.0~192.168.255.255

• 在组建内部网时，应考虑这条规定

注意：可以使用的网络号要排除全0和全1，如A类可以使用的网络号为： 10.0.0.1~10.255.255.254

IP 地址的特点

• 分等级地址结构。IP地址分为网络部分和主机部分，是某种意义上的 “分等级”。

  1. IP地址管理机构在分配IP地址时只分配网络号，而剩下的主机号则由得到该网络号的单位自行分配。这样就方便了 IP 地址的管理。

  2. 路由器仅根据目的主机所连接的网络号来转发分组(而不考虑目的主机号)，这样就可以使路由表中的项目数大幅度减少，从而减小了路由表所占的存储空间。

• IP地址与子网掩码确定了网络号及对应的广播域，一个路由器接口对应一个网络号

  • 当一个主机同时连接到两个网络上时，该主机就必须同时具有两个相应的 IP 地址，其网络号 net-id 必须是不同的。这种主机称为多归属主机(multihomed host)。

  • 由于一个路由器至少应当连接到两个网络(这样它才能将 IP 数据报从一个网络转发到另一个网络)，因此一个路由器至少有两个不同的 IP 地址。

• 按照Internet的观点，用switch (bridge)、hub(repeater)连接起来的若干个局域网仍为一个网络。因此，这些局域网都具有同样的网络号。

• 在IP地址中，所有分配到网络号的网络，不管是局域网还是广域网都是平等的。

• IP地址有时也可用来指明一个网络的地址，host-id 全零(即网络号)。

IP通讯的环境

大体有以下四种环境： 1. 通过同一根电缆直接连通(或广域网中虚电路点对点连接)。 2. 由中继器(hub)隔离。 3. 通过switch(bridge)隔离。 4. 通过路由器(相连的两个广播域必不相同)隔离。

前三种情况都属于在同一个网络(同一个广播域)，网络号必须相同。而对于路由器来说，路由器有几个口，就有几个网络号，一个网络号就是一个广播域(能够直接到达的)。 路由器只转发IP报文，而隔离广播消息。

IP 编址

• 一个有多个网络连接的计算机(常见为路由器)必须为每个连接分配一个IP地址。

• IP地址除了标识一台特定的主机外，还标识一台主机与一个网络的连接。

注：两个路由器直接相连的接口处，可指明也可不指明IP 地址。如指明 IP 地址，则这一段连线就构成了一种只包含一段线路的特殊“网络” ，指明可以方便检查出现的问题。现在常不指明 IP 地址。

IP 编址的问题

• 编码死板：C类地址能容纳的主机太少，B类地址容纳的主机又太多，能否折中？

• 解决方式：

  • Subnetting —— 子网化

  • Classless InterDomain Routing (CIDR) 无类网络

    • ABC是classful网络 —— 分类的

子网划分

• 子网编址是组织内部的系统管理者对网址的进一步划分。

• 只有本地路由器知道有多个物理网络，而且知道如何选择路由;对其他自治系 统的路由器来说，好象只存在一个物理网络。

• 与由两级组成的网络号不同, 子网由三级组成。

  • 两级网络号：网络号前缀+主机号

  • 三级网络号：网络号前缀+子网号+主机号

划分子网的基本思路

• 从主机号借用若干个位作为子网号 subnet-id，而主机号 host-id 也就相应减少了若干个位。

• 网络号=网络号+子网号

• IP地址::={<网络号>,<子网号>,<主机号>}

• 凡是从其他网络发送给本单位某个主机的 IP 数据报，仍然是根据 IP 数据报的目的网络号 net-id，先找到连接在本单位网络上的路由器。

• 然后此路由器在收到 IP 数据报后，再按目的网络号 net-id 和子网号 subnet-id 找到目的子网。

• 最后就将 IP 数据报直接交付目的主机。

子网掩码(subnet mask)

• 32位，4个字节，用带点的十进制表示。如255.255.255.0

• 二进制表示法中，“1”表示网络bit，“0”表示主机bit。

• 连续的掩码要求左边全为1，右边全为0。

• 它的作用是:将大网划分成若干小网，便于管理，具体划分由管理员分配。

• 每台设备都支持掩码。

• 路由是根据网络号加子网号来进行判断。

子网掩码默认值

• 子网掩码中“1”的长度就是网络号的长度。

• A类:缺省为255.0.0.0，前缀表示法，例如: 100.5.1.1/8，表示前8位为网络号+子网号

• B类:缺省为255.255.0.0，前缀表示法，例如: 130.5.1.1/16，表示前8位为网络号+子网号

• C类:缺省为255.255.255.0，前缀表示法，例如: 200.20.20.2/24，表示前8位为网络号+子网号

• 其中前缀也叫子网掩码长度，即左边“1”的个数。

• 在缺省状态下，同一类地址的主机如果网络号相同，这些主机都在同一广播域上。

举例： 128.10.0.0/19 划分子网方式： 首先，他是一个B类地址，网络号为前16位 128.10 其次/19表示前19位作为网络号+子网号码，说明有3位子网号 则8个子网分别为： 000_00000 - 0 - 128.10.0.0/19 001_00000 - 32 - 128.10.32.0/19 010_00000 - 64 - 128.10.64.0/19 011_00000 - 96 - 128.10.96.0/19 100_00000 - 128 - 128.10.128.0/19 101_00000 - 160 - 128.10.160.0/19 110_00000 - 192 - 128.10.192.0/19 111_00000 - 224 - 128.10.224.0/19

描述地址的时候一定要带上后面的 /xx，这是前缀表示法 十进制表示法的/19为 255.255.224.0

子网划分的作用

• 提高安全性。将网络由一个广播域变成多个广播域。

• 可提高网络的性能。

• 便于管理，节省IP地址。

• 为了减少网络地址数目可使多个物理 网络共享同一IP地址前缀。

• 对外可以聚合成一个网络号。

例题：

已知:某台路由器点对点WAN接口的IP地址为202.112.110.33/30 求: 该接口所对应的网络号，广播号，如果该主机为路由器，对方路由器接口的地址

解:

• 对IP地址和子网掩码进行逻辑与运算，可得网络号为202.112.110.32

• 取主机bit为全1，可得广播号为 202.112.110.35

• 所以，对方的IP为202.112.110.34，因为全0和全1都不能用

地址分配举例

地址分配的问题

• 如果网络前缀之内的所有子网掩码一致，这样会存在浪费、效率等问题

• 如:一个C类地址202.112.120.0/24 需划分5个子网，主机数分别为60， 60，60，30，30，如何划分?

答：

• 202.112.120.0/26 (60台主机)

• 202.112.120.64/26 (60台主机)

• 202.112.120.128/26 (60台主机)

• 202.112.120.192/26

  • 202.112.120.192/27 (30台主机)

  • 202.112.120.224/27 (30台主机)

• 注：此题不严谨，30台主机+1个路由器的IP+网络地址的全0广播号+广播地址的全1主机号=至少33个IP

可变长掩码VLSM

• VLSM (variable length subnet mask)

• 当 IP 网络子网划分时，具有多个不同的子网掩码时，由于网络前缀具有不同的长度而被称为可变长掩码子网。

• 有效提高IP地址的资源利用率。

• VLSM 允许内部地址空间进行递归划分，这样可以通过最高程度的聚合(route aggregation)以降低路由信息量。

可变长掩码VLSM分配例子：

• 由HQ连接到ABC的闪电⚡️形状的线段表示以太网，而以太网的点对点连接采用的是PPP协议，协议只要求网络中有4个IP号=连接双方+网络地址+广播地址，所以在PPP协议中能经常看到子网掩码是30的情况。

IPv6

• IP 是互联网的核心协议。

• 互联网经过几十年的飞速发展，到2011年2月，IPv4 的 32 位地址已经耗尽。

• ISP 已经不能再申请到新的 IP 地址块了。

• 我国在2014-2015年也逐步停止了向新用户和应用分配 IPv4 地址。

• 解决 IP 地址耗尽的根本措施就是采用具有更大地址空间的新版本的 IP，即 IPv6。

Header

• IPv6 Header (40 Bytes)

  
• IPv4 Header (20 Bytes)

  
• Comparison

  

Notations of IPv6 Addresses

• 128 bit is represented as :

  • 冒分十六进制表示法

  • 8 integers (16-bit) separated by colons

    • each integer is represented by 4 hex digits

  • Example:

    • FEDC:BA98:7654:3210:FEDC:BA98:7664:3210

Simplifications

• Skip leading zeros

  • Example:1080:0000:0000:0000:0008:0800:200 C:417A

  • is reduced to: 1080:0:0:0:8:800:200C:417A

• A set of consecutive nulls is replaced by ::

  • (at most one :: inside an address)

  • the above address is reduced to :

    • 1080::8:800:200C:417A

IPv6的主要改进

• 更大的地址空间 : 16字节，128位

• 首部的简化 : 只有7个固定域，撤消了有关分段的域和校验和域，以便更快地处理分组，提高路由器的吞吐量，缩短延时

• 更好地支持选项 : 选项是有次序的，以便路由器可简单地跳过与它无关的选项，加快分组的处理速度

• 增强了安全性 : 认证和隐私是关键特征

• 更加关注服务质量 : 以支持Internet上日益增长的多媒体应用

IPv6优点

• IPv6使用更小的路由表，使得路由器转发速度更快

• IPv6增加了组播支持以及对流的控制，对多媒体应用很有利，对服务质量(QoS)控制也很有利。

• IPv6加入了对自动配置的支持，对DHCP协议的改进和扩展，使得网络的管理更加方便和快捷。

• IPv6具有更高的安全性，用户可以对网络层的数据进行加密并对IP报文进行校验。

• IPv6具有更好的扩容能力。如果新的技术或应用需要时，IPV6允许协议进行扩充。

• IPv6具有更好的头部格式，就简化和加速了路由选择过程，提高了效率。

从 IPv4 向 IPv6 过渡

• 向 IPv6 过渡只能采用逐步演进的办法，同时，还必须使新安装的 IPv6 系统能够向后兼容:IPv6 系统必须能够接收和转发 IPv4 分组，并且能够为 IPv4 分组选择路由。

• 两种向 IPv6 过渡的策略:

  • 使用双协议栈

    • 双协议栈(dual stack)是指在完全过渡到IPv6之前，使一部分主机(或路由器)装有两个协议栈，一个 IPv4 和一个 IPv6。

    • 双协议栈的主机(或路由器)记为IPv6/IPv4，表明它同时具有两种 IP 地址 : 一个 IPv6 地址和一个 IPv4 地址。

    • 双协议栈主机在和IPv6主机通信时是采用IPv6地址，而和 IPv4 主机通信时就采用 IPv4 地址。

    • 根据DNS返回的地址类型可以确定使用IPv4地址还是 IPv6 地址。

    • 
    • 由上图可以看出，双协议栈会损失部分信息，如流标号，只能保证传输的连通性

  • 使用隧道技术

    • 在 IPv6 数据报要进入IPv4网络时，把 IPv6 数据报封装成为 IPv4 数据报，整个的 IPv6 数据报变成了 IPv4 数据报的数据部分。

    • 当 IPv4 数据报离开 IPv4 网络中的隧道时，再把数据部分(即原来的 IPv6 数据报)交给主机的 IPv6 协议栈。

    • IPv4的协议字段设置为41，表示IPv6数据报

    • 

因特网上数据泄漏的风险

1. 数据在到达终点之前要经过许多路由器，明文传输的报文很容易在路由器上被查看和修改 2. 监听者可以在其中任一段链路上监听数据 3. 逐段加密不能防范在路由器上查看报文，因为路由器需要解密报文选择路由信息，然后再重新加密发送 4. 恶意的ISP可以修改通道的终点到一台假冒的网关

路由(Routing)

路由选择算法

• 每条路由表项均含有网络地址(网络号)和32bit的掩码 (十进制表示/斜线法表示)。

• 当一个分组到来时, 首先找出其目的地址。

• 路由表进行扫寻, 将目的地址与每个表项的 掩码进行逻辑与运算，并与每个表项的网络地址进行比较，得出最佳匹配。

  if ((Mask[i]&D) == Destination[i]) 
  forwarding to NextHop[i]

必须要配置缺省路由，防止路由表找不到下一跳时报文传输被中断。

Windows下的网关(Gateway)就是路由器地址。

路由器工作原理

路由器根据自己的路由表进行转发。

无类域间路由选择(CIDR)

CIDR: Classless Inter-Domain Routing

• 有类 IP (Classful IP Address)路由的不足:

  • A、B、C类地址空间面临近期耗尽

  • 全球网络路由表的快速增大(网络+子网)

  • 32-bit IPv4 地址空间的最后耗竭

  • 地址分配不够灵活，效率不高

• CIDR支持有利于全球网络路由系统的两大重要特性:

  • 消除A类、B类、C类地址分配的传统做法，这样可以促使IPv4地址空间的分配更加高效。

  • 支持路由聚合，可以凭简单的路由表项 代表成千上万个传统有类路由的地址空间。

• IPv4地址空间的高效分配:

  • 用概括性的“网络前缀”思想取代传统的有类地址思想。

  • 网络前缀决定网络号和主机号之间的分界点。

  • 比用有类地址进行的8-bit, 16-bit 或24-bit网络号划分更能适应任意规模的网络。

  • 具有相同前缀长度的所有前缀代表相同数量的地址空间。

  • 例如, a/20 代表具有 20 bit的前缀长度，12 bit主机号，可支持分配2^12 (4096)个主机 地址。又称“斜线记法或表示法” (slash notation)。

• 路由表项最小化:

  • 一条简单的路由表项可以指定在许多独立的网络地址中如何进行路由选择。

  • 将世界划分为4个区域，并将一部分 C 类地址空间分配给这些区域。

    • 194.0.0.0 – 195.255.255.255/7 -> 欧洲区域

    • 198.0.0.0 – 199.255.255.255 -> 北美区域

    • 200.0.0.0 – 201.255.255.255 -> 中美和南美区域

    • 202.0.0.0 – 203.255.255.255 -> 亚太区域

  • 剑桥大学 (2048) 194.24.0.0 – 194.24.7.255

  • 牛津大学 (4096) 194.24.16.0 – 194.24.31.255

  • 爱丁堡大学 (1024) 194.24.8.0 – 194.24.11.255

e.g. B类地址通过路由聚合(Routing Aggregation)对外宣称C类地址，减少外界对内部的转发的难度。

Supernet 超网

• 超网的作用是聚合路由。其具体做法如下:

  • 将子网掩码中的一些位“1”改为“0”，做与子网掩码相反的过程，就能定义属于超网的地址范围。

  • 采用CIDR技术，将Net id中的某些1改为0

  • 一个超网就是一个广播域(网络号相同)

  • 202.112.128.50，202.11.219.10用HUB能连通吗?如何能连通(最大前缀)?

    • 202本来是C类地址，前24位都是网络号，但是可以使用子网掩码255.128.0.0或/9来实现连通，因为两个地址的最长公共前缀是九位

路由聚合问题

路由聚合规则

• 聚合地址块数必须是2^N (N＝1、2、 ……)

• 地址块必须是连续的地址块

• 开始地址必须能被地址数N整除(包括0)

• 地址分配也要符合聚合规则

最长前缀匹配

• 查找路由表时可能有多个匹配结果，如何确定哪条最佳路径?

• 应当从匹配结果中选择具有最长网络前缀的路由(longest-prefix matching)

• 网络前缀越长，其地址块就越小，路由就越具体(more specific)

小结

• 划分子网将一个大网划分为几个小网络。

• 划分子网是IP编址的层次结构中增加一个中间级。

• 掩码运算是从IP地址中提取网络号的过程。

• VLSM中一个路由可用多个不同的子网掩码。

• Supernet是将几个网络合并成一个网络。

• CIDR可以有效分配地址和减少路由表项。

练习

某网络IP地址为192.168.5.0/24，采用定长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数、每个子网的最大可分配地址个数分别是( ）。 A.32,8 B.32,6 C.8,32 D.8,30

• 根据 255.255.255.248 得到子网掩码为 /29，又因为192是C类地址所以29-24=5位剩余给子网地址，则 2^5=32

• 剩下主机位只有3位所以2^3-1-1=6个可分配地址(除去网络地址和广播地址）

某主机IP为180.80.77.55，子网掩码为255.255.252.0，若该主机向其所在子网发 送广播分组，则目的地址为( ）。 A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.255

• IP逻辑与子网掩码得到 180.80.01001100.0

• 子网掩码前缀表示是 /22 所以将最后10位改成1即是广播地址，选D

路由器收到3个分组，其目的IP分别是： 205.16.37.44 205.16.42.56 205.17.33.76 哪个分组属于超网205.16.32.0/21 ？

• 首先确定C类地址本来是24位网络号，现在超网的21位网络号则说明有3位可以用来分到同一组，2^3=8，所以同一超网的网络号为：205.16.32.0~205.16.39.255

• 所以答案为第一个

网际层的 IP 协议及配套协议

数据封装流程

IP报文格式

IP报文头部

• 版本(version)：表示是IPV4还是IPV6

• 首部长度(head len.)：标记头部的长度，缺省时20字节，有时可能有特殊的字段加入，如timestamp

• 标志(flag) 占 3 位，目前只有前两位有意义。

  • 标志字段的最低位是 MF (More Fragment)。

  • MF = 1 表示后面 “还有分片” 。MF = 0 表示最后一个分片。

  • 标志字段中间的一位是 DF (Don't Fragment) 。

  • 只有当 DF = 0 时才允许分片。

  • 之所以要分片是因为数据太大每个帧装不下

    • 分片发生在路由器中，根据MTU(Max Fragment Size.) 进行分片，不同的数据链路层的MTU可能不同

    • 分片的聚合只发生在最后的目的地址上，中间转发的路由器不进行任何的聚合

    • 目的地址接收到分片后根据 标识 和 片偏移 进行整合。

• 片偏移(12 位)指出：

  • 较长的分组在分片后某片在原分组中的相对位置。

  • 片偏移以 8个字节 为偏移单位(注意不是8位）。

• 生存时间(8 位)记为 TTL (Time To Live)

  • 数据报在网络中可通过的路由器数的最大值。

  • 防止因为找不到路由而变成了“太空垃圾”

举个例子： 当前数据链路层的MTU为1500B则说明出去首部长度的20B之外还可以承载1480B的data，因此4000B的长度的data可以拆分为3个部分：

• 第一个分片设置 fragflag=1 说明后面还有分片，没有偏移量

• 第二个分片设置 fragflag=1 说明后面还有分片，因为前面已经传输了1480B的数据所以 1480B/8B = 185

• 第三个分片设置 fragflag=0 说明是最后一个分片，偏移量是 1480*2/8=370

• 从网络层角度看，多了 (n-1)*20B

同理：

地址解析协议(ARP)

• 方式：通过逻辑地址广播呼叫，让符合者应答物理地址

• IP地址 通过ARP 获得物理地址

• 物理地址 通过RARP 获得IP地址

• 不管网络层使用的是什么协议传送数据帧时，最终还是必须使用硬件地址。

• 每一个主机都有一个 ARP 高速缓存(ARP cache)

  • 命令：arp –a 查看 /-d 删除指定主机 /-s 设置静态主机

• 当主机 A 欲向本局域网上的某个主机 B 发送IP 数据报时，就先在其 ARP 高速缓存中查看有无主机 B 的 IP 地址。如有，就可查出其对应的硬件地址，再将此硬件地址写入 MAC 帧，然后通过局域网将该 MAC 帧发往此硬件地址。

• 如没有，就广播

  • 所以如果经过n个路由器才找到目的地址的时候，需要使用n+1次的ARP，每个路由器分别广播

ARP 运作过程：

ARP安全性

• ARP欺骗攻击——仿冒网关/欺骗网关/欺骗主机/ARP泛洪

  • 攻击者发送伪造的网关ARP报文，欺骗同网段内的其它主机。

  • 主机访问网关的流量，被重定向到一个错误的MAC地址，导致该用户无法正常访问外网。

    

IP路由选择表样例

写出R2的路由表：

ICMP

• IP协议是TCP/IP协议使用的传输机制，它是一种不可靠的、无连接的数据报协议，IP协议不提供检验或跟踪机制。

• ICMP希望对IP包无法传输时提供报告，这些差错报告帮助发送方了解为什么无法传递，网络发生了什么问题，确定应用程序后续操作。

• ICMP像一个更高层的协议使用IP(ICMP消息被封装在IP数据报中）。实际上，ICMP是IP的一个组成部分，同属于网络层，而且用IP进行传输和路由。

ICMP特点

• ICMP不能用来报告ICMP消息的错误，这样就避免了无限循环。当ICMP查询消息时通过发送ICMP来响应。

• 对于被分段的数据报，ICMP消息只发送关于第一个分段中的错误。

• 响应具有一个广播或组播目的地址的数据报时，永远不会发送ICMP消息。

• 响应一个没有源主机IP地址的数据报时永远不会发送ICMP消息。

• 总的来说，源地址不能为0、一个回送地址、一个广播地址或者一个组播地址。这些是为了防止过去允许ICMP差错报文对广播分组相应所带来的广播风暴。

ICMP 数据格式

• ICMP报文有一个8字节的首部和一个可变长度的数据部分。

• 前4个字节对所有的类型都是共同的

  • 第一个8比特字段是ICMP的类型，它定义了报文的类型。代码字段指明了发送此特定报文类型的原因。

  • 最后一个共同的字段是检验和字段。首部的其余部分对每一种报文类型都是特定的。

• Sample ICMP Messages

  • Source Quench: Please slow down! I just dropped one of your datagrams.

  • Time Exceeded: Time to live field in one of your packets became zero.” or “Reassembly timer expired at the destination.

  • Fragmentation Required: Datagram was longer than MTU and “No Fragment bit” was set.

Ping

• Ping (Packet Internet Groper): Used to test

  • destination reachability

  • compute round trip time

  • count the # of hops to destination

  • may provide record route option.

• Sample output:

  • Reply from 164.107.144.3: 48 bytes in 47 msec. TTL: 253

Ping-of-death (Ping攻击)

• IP报文最大可达 65535 bytes

• 有些系统(如Win95)能够发送大于65535 bytes数据的ICMP报文

• 该报文在传输过程中被分成了多个片段

• 在目的端被重组后将超过IP报的最大尺寸

• 常常导致接受方覆盖掉内部的数据结构，从而导致整个系统崩溃

Smurf Attack

攻击者伪造受害者的IP向一个广播地址发出Ping请求，同一个广播域下的所有主机回复Ping请求导致受害者被大量响应淹没(Smurf)。

Traceroute

• Traceroute: Exploit TTL and ICMP

  • Send the packet with time-to-live = 1 (hop)

  • The first router discards the packet and sends an ICMP “time-to-live exceeded message”

  • Send the packet with time-to-live = 2 (hops) etc…

  • Does not use optional features like record route

• 从1开始分别设置TTL去传输，看到第几个中转发生错误

Problems with ICMP

• Often abused by hackers

  • Ping can be used to “scan” a network.

    • 通过ping和traceroute可以侦察网络的拓扑结构

  • Timestamp reply

    • used to identify unix machines

  • Address Mask requests

    • Building detailed network maps

  • Redirect

    • Hacker can cause your network to redirect its traffic to some other host

总结

• ICMP is the control sibling of IP

• ICMP is used by IP and uses IP as network layer protocol

• ICMP is used for ping, traceroute, and path MTU discovery.

路由协议

• 网络层(网络互连）特点

  • 经过许多节点和链路(无法广播问题）

  • 经过不同通信子网 (不同寻址问题）

  • 通讯双方可能要经过多条路径(路由选择问题）

路由定义

• 路由作用: 完全依靠路标, 找到一条最佳路径(路径最短、速度最快、安全可靠、开销最小等)

• Routing is the process of generating the routing table and forwarding a packet from one location to another.

• Routers forward traffic to a logical destination in a computer network.

• Routers perform two major functions:

  • Routing

    • Learning the logical topology of the network

  • Switching

    • Forwarding packets from an inbound interface to an outbound interface

• Routing Goal

  • determine “good” path (sequence of routers) through network from source to dest.

• 路由协议的核心就是路由算法，即需要何种算法来获得路由表中的各路由表项。

• The Internet consists of Autonomous Systems interconnected with each other

• Two-level routing (Hierarchical):

  • Intra-AS: administrator is responsible for choice (AS内部)：RIP，OSPF

  • Inter-AS: unique standard - BGP

  • Example:

路由器工作原理:

路由协议分类

从路由算法能否随网络通信量或拓扑 自适应地进行调整变化来划分，可分两大类：

• 静态路由(非自适应路由选择）

  • 简单、开销小，但不能及时适应网络状态的变化。

• 动态路由 (自适应路由选择）

  • 能较好的适应网络状态的变化，但实现起来较为复杂，开销比较大。

静态路由(Static Routing)

要给中间的Router分配左右侧各一个地址，并设置左侧的主机的默认网关为E0口的IP，右侧的主机的默认网关为E1口的IP，这样在请求外界的网络的时候才不会因为没有MAC丢弃报文，会被送到默认网关。

动态路由(Automatic Routing)

• Used by IP routers

• Requires special software (Routing Daemon 路由守护进程routed)

• Each router communicates with neighbors

• Pass routing information

• Use route propagation protocol

Dynamic Routing Model：

Dynamic Routing Methods

• Distance vector: At every node, set up distance signposts to destination nodes (a vector)

  • Setup this by looking for neighbors’ signposts.

• Link state routing: Get map of network (in terms of link states) and calculate best route locally

Distance Vector routing

• "Vector" of distances (signposts) to each How to find distances ?

  • Distance to local network is 0. (Cisco 规定距离为0，教材和华为规定用1)

  • Look in neighbors’ distance vectors, and add link cost to

    reach the neighbor

  • Find which direction yields minimum distance to particular

    destination. Turn signpost that way.

  • Keep checking if neighbors change their signposts and

    modify local vector if necessary.

  • Called the "Bellman-Ford algorithm"

    • 设X是结点 A 到 B 的最短路径上的一个结点。

    • 若把路径 A→B 拆成两段路径 A→X 和 X→B，则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。(可以反证）

• Idea: At node i, for destination j:

• Find neighbor/next-hop x that minimizes the sum

  • D(i,j) = C(i,x) + D(x,j)

D-V基本思想： 1. 每个路由器周期性的广播路由报文 2. 报文中含有(V, D)序偶组成，V--网络号Vector，D--距离Distance 3. 每个路由器收到路由报文后，依据(V, D)序偶，按照最短路径原则更新自己的路由表

路由刷新过程

路由器Ri收到Rj的路由报文(Vj ，Dj) 1. Ri路由表中没有Vj，则增加一项，(Vi=Vj，Di=Dj+1） 2. 已有，如果Dj+1 < Di，则Ri修改自己的表项，其中Vi不变，而Di=Dj +1。如果Dj+1 = Di ，nexthop=Rj (也有路由器厂商采用先入为主，即不变)。否则不变。 3. Ri 去往某目的地的路径经过Rj ，而Rj去往目的地的路径发生了变化： 1. 如果Rj 的V-D 表中不再包含去往Vi 的路径(断了)则Ri中相应的表项需删除。(timeout) 2. 如果Rj 去往目的地的距离发生了变化，则Ri 需修改自己的表项，Vi 不变，Di =Dj +1。(Dj为变化后的距离)

举个例子：

Router initial start up (Cold Starts)

• Initial network discovery

  • 一开始的时候加入所有直接与路由器相连的主机，距离为0(或者1)

• Router checks update for new information

  • 如果有新的主机IP则加入到路由表中

• Router convergence is reached when

  • 网络中所有路由的路由表中的网络信息都相同

• Routers continue to exchange routing information

  • 如果没有新的信息加入则路由收敛

  • Convergence must be reached before a network is considered completely operable

• Speed of achieving convergence consists of 2 interdependent categories：

  • Speed of broadcasting routing information

    • RIP协议每30s检索一次，时间太长

  • Speed of calculating routes

    • 计算时间很快忽略不计

RIP ( Routing Information Protocol)

• RFC 1058 and 1723

• Included in BSD UNIX in 1982

• Distance vector algorithm

• Distance metric: number of hops (max = 15 hops)

  • 早期认为路由最多经过15个，所以hops号为16被设置为路由不通

  • e.g. 35、某自治系统采用RIP协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量中包含信息＜net1，16＞，则可能得出的结论是( ）

    • 答案：R1不能进过R2到达net1

• Distance vectors: exchanged every 30 sec via RIP Response Message (also called "RIP advertisement")

• 封装在 UDP 报文中, 端口号为 520 。

路由协议运行流程

• 初始化：启动路由守护进程，它先判断启动了哪些接口，并在每个接口上发送一个请求报文要求其它路由器发送完整路由表；

• 接收请求：路由器将完整的路由表发送给请求者；

• 接收到响应：使响应生效, 更新路由表；

• 定期路由更新：每过30秒所有路由器会将完整路由表发送给相邻路由表；

• 触发更新：每当一条路由的度量发生变化时，发送那些发生变化的表项。

  • 弥补定期更新造成的缓慢等待时间

RIP定时器

• 更新定时器/组播定期更新时间 (update timer)

  • Rate (in seconds) at which updates are sent. The range is from 5 to 4,294,967,295. The default is 30 seconds.

  • 设置路由器发送更新信息的速度

  • 默认值为30秒

• 无效定时器/失效时间 (invalid timer)

  • Interval of time (in seconds) after which a route is declared invalid; it should be at least three times the value of the update argument. A route becomes invalid when no updates refresh the route. The route then enters into a holddown state where it is marked as inaccessible and advertised as unreachable. However, the route is still used to forward packets. The range is from 1 to 4,294,967,295. The default is 180 seconds.

  • 得不到更新的路径经过多少秒后将被认为是无效的

  • 默认值为180秒

• 保持定时器/死亡时间 (holddown timer)

  • Interval (in seconds) during which routing information regarding better paths is suppressed; it should be at least three times the value of the update argument. A route enters into a holddown state when an update packet is received that indicates that the route is unreachable. The route is marked as inaccessible and advertised as unreachable. However, the route is still used to forward packets. When holddown expires, routes advertised by other sources are accepted and the route is no longer inaccessible. The range is from 0 to 4,294,967,295. The default is 180 seconds.

  • 指明在多少秒之内拒绝接受更好的路由信息。

  • 默认值为180秒

• 刷新定时器/刷新时间 (flush timer)

  • Amount of time (in seconds) that must pass before the route is removed from the routing table; the interval specified should be greater than the sum of the invalid argument plus the holddown argument. If it is less than this sum, the proper holddown interval cannot elapse, which results in a new route being accepted before the holddown interval expires. The range is from 1 to 4,294,967,295. The default is 240 seconds.

  • 设置路径从路由表中删除必须等待的时间。

  • 默认值为240秒

RIP

Routing Information Protocol

RIPv1

命令字：1 请求；2 响应。 一个报文最多25条路由。 通常把命令域设为1，然后广播整个路由表。 AFI:地址族标志指明使用的地址族，用于支持多种不同协议的路由信息。IP的AFI=2，如为0xFFFF，则剩下的部分为认证信息(RIPv2)。

RIPv2

• Provides:

  • VLSM、CIDR support 可变长掩码和无类网络

  • Authentication

  • Multicasting (地址为：224.0.0.0)

  • Tags to support EGP/BGP routes

• Uses reserved fields in RIPv1 header.

  
• 如果在Address Family 中的数据为FFFF,则整个报文为认证(authentication)报文。

• 路由标记：可带 AS 号，使RIP能够从 EGP/BGP routes. 中接受信息。

RIP problems

• Counting-to-infinity problem (无穷计数/循环计数):

  • Simple configuration A->B->C. If C fails, B needs to update and thinks there is a route through A. A needs to update and thinks there is a route thru B.

  • No clear solution, except to set “infinity” to be small (e.g. 16 in RIP)

• Slow convergence after topology change (30s update一次导致收敛很慢):

  • Due to count to infinity problem

  • Information propagates every 30s

• Black-holes(黑客攻击告知一个假的路由地址使得信息都向假地址发送，没有返回响应):

  • If one node goes broken and advertises route of zero to several networks, all nodes immediately point to it.

• Broadcasts consume non-router resources (在RIPv1中采用广播的方式，在RIPv2中用组播缓解了这种消耗)

• Metric: hop count <=15 hop is not the best metric (收到hop的最大值的限制只能构建小型网络)

• No load balance 没有流量均衡/负载均衡

Properties of Distance Vector Algorithm

• Good news propagate fast (A、B之间恢复链路)

  • 
• Bad news propagate slowly: the count-to-infinity problem (A、B之间中断)

  • 

解决方法

• 水平分割 (split horizons)

  • 路由器不向收到某条路由到来的方向回传此路由。

  • 失败情况：如下图:

    • 
    • 开始时，A和B到D的距离都为2，C到D的距离为1。

    • 假设CD线路断了， C发现直达D的线路断了，于是C很快认定D不可达了。

    • 使用水平分割，A和B都不能到达D。

    • 但是，A认为B有一条通向D长度为2的路径，通过B经过3个结点可到达D。

    • 类似，B也这样认为。于是两个结点每交换一次信息，到达D的距离就增加1，直至加大无穷。

• 毒性逆转 (poison reverse)

  • 把跳数设为16(不可达）并把这条路径告诉邻居路由器。

• 保持定时器 (hold down timer)

  • 某路径删除后一定时间内拒绝接收新的路由信息。

• 触发更新 (Triggered Update)

  • 当某个路径的度量改变了，路由器立即发出更新信息。

RIP Summary

• Routing within an autonomous system (IGP)

• Unreliable transport (uses UDP)

• Broadcast or multicast delivery

• Can propagate a default route (书4-55，画出路由表，注意缺省路由)

• Implemented by Unix program routed

• DV protocol with hop count as metric

  • Infinity value is 16 hops; limits network size

  • Includes split horizon with poison reverse

• Routers send vectors every 30 seconds

  • With triggered updates for link failures

  • Time-out in 180 seconds to detect failures

• RIPv1 specified in RFC1058

  • www.ietf.org/rfc/rfc1058.txt

• RIPv2 (adds authentication etc.) in RFC1388

  • www.ietf.org/rfc/rfc1388.txt

Example

某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加的一条路由(目的网络，子网掩码，下一跳)是 A.192.168.2.0， 255.255.255.128， 192.168.1.1 B.192.168.2.0， 255.255.255.0， 192.168.1.1 C.192.168.2.0， 255.255.255.128， 192.168.1.2 D.192.168.2.0， 255.255.255.0， 192.168.1.2

虽然在下方的两个host都是 /25，但是因为最后一段一个是0一个是128，所以为了聚合的话设置的路由的子网掩码只能是两者的逻辑与的最长前缀个数，即/24，所以选D

L-S 算法(Link-State Routing Algorithm)

• 简单步骤:

  • 发现邻居结点，并学习它们的网络地址。

  • 测量到每个邻居结点的延迟或开销。

  • 将所有学习到的内容封装成一个分组。

  • 将这个分组用泛洪法发送给所有其它路由器。

  • 生成一个网络拓扑图。

  • 利用Dijkstra算法计算最小生成树，从而得到该节点（树根）到其它路由器的最短路径。

• 最小生成树

  • 带权连通图中,总的权值之和最小的带权生成树为最小生成树。最小生成树也称最小代价生成树，或最小花费生成树。

  • 只能利用图中的边来构造最小生成树；

  • 只能使用、且仅能使用图中的n-1条边来连接图中的n个顶点；

  • 不能使用图中产生回路的边。

L-S路由建立过程

1. 每台路由器了解其自身的链路（即与其直连的网络）

2. 每台路由器负责“问候（hello）”直连网络中的相邻路由器

3. 每台路由器创建一个链路状态数据包（LSP），其中包含与该路由器直连的每条链路的状态

   • 创建链路状态数据包

     • 路由器使用 Hello 协议 来发现其链路上的所有邻居

     • 路由器一旦建立了相邻关系，即可创建链路状态数据包 (LSPs)

     • 包含与该链路相关的链路状态信息

4. 每台路由器将LSA(Link-State Advertisement) 泛洪(Flooding) 到所有邻居，然后邻居将收到的所有LSA存储到数据库中

   • 链路状态数据库 (link-state database)

     • 由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。

     • 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。

     • OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。

     • OSPF 的更新过程收敛得快是其重要优点。

   • 链路状态数据库泛洪到邻居

     • 泛洪：收到报文后立刻发给所有邻居

     • 路由器一旦接收到来自相邻路由器的LSP，立即将该 LSP 从除接收该 LSP 的接口以外的所有接口发出

     • 链路状态路由协议则在泛洪完成后再计算 SPF 算法

     • LSP 中还包含其它信息（例如序列号和过期信息），以帮助管理泛洪过程

5. 每台路由器使用数据库构建一个完整的拓扑图并以自己为根计算通向每个目的网络的最佳路径

L-S路由协议

• 链路状态路由协议中，直连的路由器之间建立邻接关系，互相“交流”链路信息，来“画”出完整的网络结构

  

L-S路由协议数据库类型

• 邻居列表

  • 列出每台路由器全部已经建立邻接关系的邻居路由器

• 链路状态数据库（LSDB）

  • 列出网络中其他路由器的信息，由此显示了全网的网络拓扑结构

• 路由表

  • 列出通过SPF算法计算出的到达每个相连网络的最佳路径

    

    

Dijkstra’s algorithm

核心：由当前的连边的最短边向外进行结点的拓展 Example: 1. 初始化A连通BCD 2. D向外的边DE最短连通E 3. E向外的边EC使得AD+DE+EC比AC短故更新A与C之间的举例 4. E向外的边EF最短连通F 5. 整个图的结点都连通得到A到任意结点的最短路，算法结束

OSPF (了解)

概念：

• OSPF英文全称Open Shortest Path First

• OSPF是一种链路状态路由协议，使用基于带宽的度量值。

• OSPF采用SPF算法计算路由，从算法上保证了无路由环路。

• OSPF通过邻居关系维护路由，避免了定期更新对带宽的消耗。

• OSPF路由更新效率高，网络收敛快，适用于大中型网络。

• OSPF报文封装于IP，协议号89，组播地址224.0.0.5与224.0.0.6。

Advanced Features:

• Security: all OSPF messages authenticated, TCP connections used

• Multiple same-cost paths allowed (only one path in RIP)

• Allow each link to have different costs for different TOS (Type of Service) IP Packets

  • E.g, high-bandwidth satellite link configured to have a low cost for non-time-critical traffic and have a high cost for delay-sensitive traffic

  • Can compute different routes for each type of traffic

• Integrated unicast and multicast support:

  • Multicast OSPF (MOSPF, RFC 1584) provides simple extensions to OSPF to provide for multicast routing

• Support for hierarchy within a single AS

  • Hierarchical OSPF

  • Two-level hierarchy: local area, backbone(主干网：都是Area 0)

    • 
    • An AS is configured into areas, each area runs its own OSPF link-state routing algorithm

    • One area in AS is configured to be the backbone area, job is to route traffic between other areas in the AS

  • Four types of OSPF routers(结合上图):

    • Internal routers: in non-backbone areas and only perform intra-AS routing

    • Area border routers(区域边界路由): belong to both an area and the backbone, route packets to outside the area

    • Backbone routers: perform routing within the backbone but are not area border routers

    • Boundary routers: connect to other ASs, exchange routing information with routers in other ASs

路由表的计算：

• 路由器根据它所在的区域数据库，计算到域内各网络的路由 （SPT）

• 路由器要根据ABR向本域散发的域外LSA来计算到本AS内的其他各区域子网的可达性信息

  • 本路由器到本AS内目的网络的距离 = 本路由器到ABR的距离 + ABR到目的网络的距离

• 路由器根据与之邻接的ABR送来的ASBR掌握的本AS外LSA来计算到本AS外各网络的可达性

  • 本路由器到本AS外目的网络的距离 = 本路由器到ASBR的距离 + ASBR到目的网络的距离

OSPF in IP Packets

• OSPF is a link-state routing protocol

  • Relies on IP packets for delivery of routing information

  • Uses protocol number 89

OSPF五类报文

• Type 1，Hello分组，用来发现和维持邻站的可达性

  • 每两个相邻的路由器10秒钟交换Hello报文，若40秒没收到Hello报文，该相邻Router不可达

  • Hello报文包含的字段：

    • Router ID

    • Hello/dead intervals *

    • Neighbors

    • Area-ID *

    • Router priority

    • DR IP address

    • BDR IP address

    • Authentication password *

    • Stub area flag *

    • 其中带有 * 的是需要邻居之间相互匹配的

• Type 2，Database Description， 向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息

• Type 3，Link State Request， 向对方请求发送某些链路状态项目的详细信息

• Type 4，Link State Update，用Flooding向全网更新链路状态

• Type 5，Link State Acknowledgement，对链路更新分组的确认

Example

• 对于RIP而言只计算途中路由器的数量不考虑带宽等实际传输过程所以选择cost=10的两台交换机的路径

• 对于OSPF这种基于带宽的道路选择而言则根据实际的cost选择三个交换机总cost=7的路径

Algorithm Comparison

Distance-Vector	Link-State
路由器向邻居传送自己的路由表；	路由器向邻居传送自己直接连接的网络；
路由器通过邻居的路由表发现新的网络，并填写到自己的路由表中；	通过转发过来的各个路由器的LSA报文，发现新的路由器和新的网络；
通过将前面路由器给出的距离，再累加自己的这段距离，得到判断最佳路径的依据；	各个路由器根据自己的数据库（全网拓扑图），以自己为根节点各自推算最佳路径
不管网络是否有拓朴变化，都是等待定时时间到才发路由广播。收敛速度慢；	一旦收到别人的LSA报文，就立即转发给其它路由器，收敛速度快；
对于路由循环等问题，依靠被动的跳数、水平分割、抑制定时等技术解决。	不会出现循环路由。

Routing in the Internet

• 互联网的规模非常大，如果让路由器知道所有的网络，那么路由表会非常庞大，处理起来非常费时间。

• 每个国家、组织、单位都独立管理自己的网络，不愿外界了解自己的内部布局及管理细节，更不愿意绕路。

• The Internet consists of Autonomous Systems (自治系统) interconnected with each other

• Two-level routing (Hierarchical):

  • Intra-AS: administrator is responsible for choice (AS内部)：RIP，OSPF

  • Inter-AS: unique standard - BGP

EGP (External Gateway Protocol)

• 不同AS为什么不能用IGP,原因：

  • Internet规模太大，使Inter-AS路由选择非常困难

  • AS内部的路由协议各自定义，千差万别

  • 当一条路径通过几个不同 AS 时，要想对这样的路径计算出有意义的代价是不太可能的。

  • 比较合理的做法是在 AS 之间交换“可达性”信息。

  • Inter-AS路由选择必须考虑有关策略。例如：我国国内的站点互访不应经过国外兜圈子

IGP与EGP的区别

• Context：运行在不同的路由环境下

  • IGP 感兴趣的是路由信息的创建和交换

  • EGP 感兴趣的是网络的可达性信息

• Connectivity：

  • IGP网络彼此间通过物理方式连接在一起，路由表建立在直接连接和相邻连接之上。

  • EGP信息通过对等方进行交换，路由建立在AS之上。

• Choice：

  • IGP支持路由度量，允许Router选择最佳路径。

  • EGP不支持路由度量，采用路由策略对通信行为进行管理。

AS number 自治系统编号

• AS = set of routers and networks under the same administration

  • No theoretical limit to the size of the AS

  • All parts within an AS remain connected.

  • AS is identified by a 16-bit AS number

  • IANA（互联网代码分配机构）分配：1~65536，其中64512~65535为”private”

  • At least one border router per AS

    • This router also collects reachability information (“external routes”) and diffuses it internally and vice versa.

• AS types:

  • Stub AS => only single connection to one other AS => it carries only local traffic.

  • Multihomed AS: Connected to multiple AS, but does not allow transit traffic

  • Transit AS: carries transit traffic under policy restrictions

• Traffic types:

  • Local = traffic originating or terminating at AS.

  • Transit = non-local traffic

• The Internet is split into Autonomous Systems (AS’s)

  • Examples of AS’s: Stanford (32), HP (71), MCI Worldcom (17373)

  • Try: whois –h whois.arin.net ASN “MCI Worldcom”

• Within an AS, the administrator chooses an Interior Gateway Protocol (IGP)

  • Examples of IGPs: RIP (rfc 1058), OSPF (rfc 1247).

• Between AS’s, the Internet uses an Exterior Gateway Protocol (EGP)

  • AS’s today use the Border Gateway Protocol, BGP-4 (rfc 1771)

Intra-AS and Inter-AS routing

When Should Use BGP

• Dual- or multi-homed 一个网络号多个连接端口到不同的AS

• Providing partial or full Internet routing to a downstream customer 对于有转发需求的downstream数据要提供路由信息

• Anytime the AS path information is required 当有AS路径的请求的时候要使用

  BGP Is Not Needed

• if singularly homed 只有单个端口连接自己的AS

• if not providing downstream routing 自己是末端(stub)不需要提供路由信息，如北航在教育网中属于末端

• Use a default route! 使用缺省路由的时候不需要BGP，因为不需要定向，直接发送给默认

Nontransit vs. Transit ASes

Transit 可穿过的，表示可以通过其到达其他地址 Nontransit 不可穿过的，表示不能通过其到达其他地址，只能提供信息

Inter-Domain Routing

路由策略特点

• 不影响分组的目标地址，它影响用于到达目标的路径。

• 不允许数据流采用与AS所选择路由不同的路径发往另一个AS

• 仅仅影响数据流怎样到达AS，不影响AS内部路由

• 可以实现任何于跳与跳范式相联系的规则

• 有很多路由规则：有路径优先（跳数）、优先权最高优先、内部路由优先于外部路由等等

BGP协议

• BGP是一种外部网关协议（EGP），与OSPF、RIP等IGP，其着眼点不在于发现和计算路由，而在于控制路由的传播和选择最佳路由。

• BGP使用TCP作为其传输层协议（监听端口号为179），提高了协议的可靠性。

• 路由更新时，BGP只发送更新的路由，大大减少了BGP传播路由所占用的带宽

• BGP是一种距离矢量路由协议，从设计上避免了环路的发生。

• BGP提供了丰富的路由策略，能够对路由实现灵活的过滤和选择。

• BGP所交换的网络可达性的信息就是要到达某个网络所要经过的一系列 AS。

• 每个AS至少有一个发言人(Speaker)

BGP协议特点

• BGP 协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。

• 每一个自治系统中 BGP 发言人（或边界路由器）的数目较少，使得自治系统之间的路由选择不致过分复杂。

• Path vector protocol

  • Each BGP router broadcasts to neighbors (peers) entire path (i.e, sequence of ASs) to a destination AS, but not the cost to destination

  • 直接发送路径，不是发送路径的代价

BGP Peer

• BGP speaker(发言人)叫做BGP peer，每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“ BGP 发言人”。

• 由BGP负责的内容分为 eBGP peer 和 iBGP peer，分别是外部和内部BGP peer。

• eBGP peer是负责不同的AS之间的传输，iBGP peer负责相同的AS内部的传输。

• 一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是BGP 边界路由器，但也可以不是 BGP 边界路由器。

  • Note: eBGP Peers normally should be directly connected.

  • Note: iBGP Peers don’t have to be directly connected.

    

BGP 交换路由信息

• 一个 BGP 发言人与其他自治系统中的 BGP发言人要交换路由信息，就要先建立 TCP连接，然后在此连接上交换 BGP 报文以建立 BGP 会话(session)，利用 BGP 会话交换路由信息。

• 使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。

• 使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站或对等站。

• BGP前提：IP要通达。

  

  

  

BGP peer 配置

iBGP

eBGP

BGP-4 共使用四种报文

因为BGP采用的是可靠的TCP协议所以有请求状态的需求，所以有不同的报文格式来实现可靠性：

• 打开(OPEN)报文，用来与相邻的另一个BGP发言人建立关系。

• 更新(UPDATE)报文，用来发送某一路由的信息，以及列出要撤消的多条路由。

• 保活(KEEPALIVE)报文，用来确认打开报文和周期性地证实邻站关系。

• 通知(NOTIFICATION)报文，用来发送检测到的差错。

• 在 RFC 2918 中增加了 ROUTE-REFRESH 报文，用来请求对等端重新通告。

BGP 报文具有通用的首部

BGP封装到TCP中，TCP再封装到IP中：

BGP运行过程

• 建立AS间的拓扑图。该拓扑图是通过各AS的BGP路由器交换路由信息获得的。

• 各AS通过邻居关系连接在一起，各个AS之间的链路构成了所谓的树。

• BGP按距离 — 矢量算法计算最短路径。

• BGP保留到每一个目的站的完整路由。

  

Path attributes and BGP routes

• Advertised prefix includes BGP attributes

  • prefix + attributes = "route"

  • prefix is CIDR/mask e.g. Prefix: 138.16.64/22

• Two important attributes:

  • AS-PATH: contains ASs through which prefix advertisement has passed: e.g., AS 67, AS 17

    • AS-Path的建立与选择最短路：
    • AS-PATH中不允许成环：
    • 网络传输通常按照AS-PATH给定的路线：
  • NEXT-HOP: indicates specific internal-AS router to next-hop AS. (may be multiple links from current AS to next-hop-AS)

• gateway router receiving route advertisement uses import policy to accept/decline

  • e.g., never route through AS x

  • policy-based routing : router may learn about more than 1 route to destination AS, selects route based on:

    1. local preference value attribute: policy decision 优先级

    2. shortest AS-PATH

    3. closest NEXT-HOP router: hot potato routing

    4. additional criteria 人工可以继续设置

       

单路由器多协议

EGP和IGP共用

当前网络路由器架构

IPv6

引入背景

• IP 是互联网的核心协议。

• 互联网经过几十年的飞速发展，到2011年2月，IPv4 的 32 位地址已经耗尽。

• ISP 已经不能再申请到新的 IP 地址块了。

• 我国在2014-2015年也逐步停止了向新用户和应用分配 IPv4 地址。

• 解决 IP 地址耗尽的根本措施就是采用具有更大地址空间的新版本的 IP，即 IPv6。

IPv4报文头部

IPv6报文头部

IPv4 和 IPv6 对比

IPv6 128 bit 地址表示方法

冒分十六进制表示法 举个例子：FEDC:BA98:7654:3210:FEDC:BA98:7664:3210 每一位都是16进制，所以每一位相当于4位，一共分成8段，每段4个十六进制，一共是 484=128 bit

简化表示方法 由于当前IPv6地址冗余，所以大部分位数是0，这时候可以进行缺省表示： Skip leading zeros 跳过相邻的0，细分为两种情况： 1. 段内跳0 e.g. From: 1080:0000:0000:0000:0008:0800:200C:417A To: 1080:0:0:0:8:800:200C:417A 2. 段间跳0使用 :: e.g. From: 1080:0000:0000:0000:0008:0800:200C:417A To: 1080::8:800:200C:417A

IPv6的改进

• 更大的地址空间：16字节，128位

• 首部的 简化：只有7个固定域，撤消了有关分段的域和校验和域，以便更快地处理分组，提高路由器的吞吐量，缩短延时

• 更好地支持选项：选项是有次序的，以便路由器可简单地跳过与它无关的选项，加快分组的处理速度

• 增强了安全性：认证和隐私是关键特征

• 更加关注服务质量：以支持Internet上日益增长的多媒体应用

IPv6的优点

• IPv6使用更小的路由表，使得路由器转发速度更快。

• IPv6增加了组播支持以及对流的控制，对多媒体应用很有利，对服务质量（QoS）控制也很有利。

• IPv6加入了对自动配置的支持，对DHCP协议的改进和扩展，使得网络的管理更加方便和快捷。

• IPv6具有更高的安全性，用户可以对网络层的数据进行加密并对IP报文进行校验。

• IPv6具有更好的扩容能力。如果新的技术或应用需要时，IPV6允许协议进行扩充。

• IPv6具有更好的头部格式，就简化和加速了路由选择过程，提高了效率。

从 IPv4 向 IPv6 过渡

向 IPv6 过渡只能采用逐步演进的办法，同时，还必须使新安装的 IPv6 系统能够向后兼容：IPv6 系统必须能够接收和转发 IPv4 分组，并且能够为 IPv4 分组选择路由 接下来介绍两种技术：

使用双协议栈

• 双协议栈(dual stack)是指在完全过渡到 IPv6 之前，使一部分主机（或路由器）装有两个协议栈，一个 IPv4 和一个 IPv6。

• 双协议栈的主机（或路由器）记为 IPv6/IPv4，表明它同时具有两种 IP 地址：一个 IPv6 地址和一个IPv4 地址。

• 双协议栈主机在和 IPv6 主机通信时是采用 IPv6 地址，而和 IPv4 主机通信时就采用 IPv4 地址。

• 根据 DNS 返回的地址类型可以确定使用 IPv4 地址还是 IPv6 地址。

  

使用隧道技术

• 在 IPv6 数据报要进入IPv4网络时，把 IPv6 数据报封装成为 IPv4 数据报，整个的 IPv6 数据报变成了 IPv4 数据报的数据部分。

• 当 IPv4 数据报离开 IPv4 网络中的隧道时，再把数据部分（即原来的 IPv6 数据报）交给主机的 IPv6 协议栈。

• IPv4 的协议字段设置为41，表示IPv6数据报.

  

虚拟专用网 VPN

因特网上数据泄漏的风险

1. 数据在到达终点之前要经过许多路由器，明文传输的报文很容易在路由器上被查看和修改

2. 监听者可以在其中任一段链路上监听数据

3. 逐段加密不能防范在路由器上查看报文，因为路由器需要解密报文选择路由信息，然后再重新加密发送

4. 恶意的ISP可以修改通道的终点到一台假冒的网关

VPN引入背景

• VPN是企业网在因特网等公共网络上的延伸。

• 由于 IP 地址的紧缺，一个机构能够申请到的IP地址数往往远小于本机构所拥有的主机数。

• 考虑到机构内部使用的计算机就可以由本机构自行分配其 IP 地址。

• 互联网并不安全，一个机构内也并不需要把所有的主机接入到外部的互联网。

VPN 技术

• VPN(Virtual Private Network)是指依靠ISP，在公共网络中建立专用数据网络的技术。

• 在VPN中，任意两个节点之间的连接并没有端到端物理链路，而是利用公众网的资源动态组成的。

  

VPN的基本原理

• 采用隧道技术

• 数据包以密文形式在网上传输

内联网 intranet 和外联网

• 它们都是基于 TCP/IP 协议的

• 由部门 A 和 B 的内部网络所构成的虚拟专用网VPN 又称为内联网 (intranet)，表示部门 A 和 B 都是在同一个机构的内部。

• 一个机构和某些外部机构共同建立的虚拟专用网VPN 又称为外联网 (extranet)。

远程接入 VPN

• 远程接入 VPN (remote access VPN)可以满足外部流动员工访问公司网络的需求。

• 在外地工作的员工拨号接入互联网，而驻留在员工 PC 机中的 VPN 软件可在员工的 PC 机和公司的主机之间建立 VPN 隧道，因而外地员工与公司通信的内容是保密的，员工们感到好像就是使用公司内部的本地网络。

网络地址转换 NAT

问题背景

• 问题：地址稀缺，在专用网上使用专用地址的主机如何与互联网上的主机通信（并不需要加密）？

• 解决：

  1. 再申请一些全球 IP 地址。但这在很多情况下是不容易做到的。

  2. 采用网络地址转换 NAT。这是目前使用得最多的方法。

NAT 路由器

• 网络地址转换 NAT (Network Address Translation) 方法于1994年提出。

• 需要在专用网连接到互联网的路由器上安装 NAT 软件。装有 NAT 软件的路由器叫作NAT路由器，它至少有一个有效的外部全球IP地址。

• 所有使用本地地址的主机在和外界通信时，都要在 NAT 路由器上将其本地地址转换成全球 IP 地址，才能和互联网连接。

  

网络地址转换的过程

• 内部主机 A 用本地地址 IPA 和互联网上主机 B 通信所发送的数据报必须经过 NAT 路由器。

• NAT 路由器将数据报的源地址 IPA 转换成全球地址 IPG，并把转换结果记录到NAT地址转换表中，目的地址 IPB 保持不变，然后发送到互联网。

• NAT 路由器收到主机 B 发回的数据报时，知道数据报中的源地址是 IPB 而目的地址是 IPG。

• 根据 NAT 转换表，NAT 路由器将目的地址 IPG 转换为IPA，转发给最终的内部主机 A。

• 可以看出，在内部主机与外部主机通信时，在NAT路由器上发生了两次地址转换：

  • 离开专用网时：替换源地址，将内部地址替换为全球地址；

  • 进入专用网时：替换目的地址，将全球地址替换为内部地址；

  • e.g. NAT地址转换表：

    • 
• 当 NAT 路由器具有 n 个全球 IP 地址时，专用网内最多可以同时有 n 台主机接入到互联网。这样就可以使专用网内较多数量的主机，轮流使用 NAT 路由器有限数量的全球 IP 地址。

• 通过 NAT 路由器的通信必须由专用网内的主机发起。专用网内部的主机不能充当服务器用，因为互联网上的客户无法请求专用网内的服务器提供服务。

网络地址与端口号转换 NAPT

• 为了更加有效地利用 NAT 路由器上的全球IP地址，现在常用的 NAT 转换表把运输层的端口号也利用上。这样，就可以使多个拥有本地地址的主机，共用一个 NAT 路由器上的全球 IP 地址，因而可以同时和互联网上的不同主机进行通信。

• 使用端口号的 NAT 叫作网络地址与端口号转换 NAPT (Network Address and Port Translation)，而不使用端口号的 NAT 就叫作传统的 NAT(traditional NAT)。

• e.g. NATP 端口转换表：

  • 

防火墙Firewall

• 定义：防火墙（Firewall）指隔离在内部网络和外部网络之间的一道防御系统，它能挡住来自外部网络的攻击和入侵，保障内部网络的安全。

• 相关概念：

  • 外部网络（外网） ：防火墙之外的网络，一般为internet，默认为风险区域；

  • 内部网络（内网） ：防火墙之内的网络，一般为局域网，默认为安全区域；

  • 非军事化区（DMZ） ：为了配置管理方便，内网中需要向外网提供服务的服务器，如WWW、FTP、SMTP、DNS等，往往放在internet与内部网络之间一个单独的网段，这个网段便是非军事化区。

  • 

ACL

概述

• ACL（Access Control List），利用ACL可以对经过路由器的数据包按照设定的规则进行过滤，使数据包有选择的通过路由器，起到防火墙的作用。

• 访问控制列表(ACL)由一组规则组成，在规则中定义允许或拒绝通过路由器的条件。

• ACL过滤的依据主要包括源地址、目的地址、上层协议等。

• ACL一般只在以下路由器上配置（Unix、linux系统）

ACL的工作过程

• 访问控制列表(ACL) 由多个规则组成。每条语句给出一个条件和处理方式（通过或拒绝）。

• 路由器对收到的数据包按照规则进行检查，当遇到相匹配的条件时，就按照指定的处理方式进行处理。

• ACL中各规则书次序非常重要，如果一个数据包和某判断语句的条件相匹配时，该数据包的匹配过程就结束了，剩下的条件语句被忽略。

• 一台路由器中可定义多个ACL，每个ACL使用一个表号。

• 一个访问控制列表(ACL)可由多条语句组成，每条ACL语句的形式为：

  • Router(config)# access-list 表号 处理方式 条件

  • 处理方式：取值有permit（允许）和deny（拒绝）两种。当数据包与该语句的条件相匹配时，用给定的处理方式进行处理。

  • 条件：每条ACL语句只能定义一个条件。

  • e.g.

    • access-list 1 permit 10.0.0.0 0.255.255.255 允许10...*为源地址的包进入

    • access-list 1 deny 20.0.0.0 0.255.255.255 拒绝20...*为源地址的包进入

应用ACL

• 如果只是定义了ACL，它还不会起到任何作用，必须把ACL应用到一个接口上才能起作用。

• 应用ACL：

  • Router(config)# interface 接口号

  • Router(config-if)# ip access-group 表号 [in | out]

  • in：表示在数据包进入此接口时使用ACL进行过滤。

  • out：表示在数据包离开此接口时使用ACL进行过滤。

• 通常，使用出站接口检查的数据包数量较少，效率要高一些。

通配符掩码

• 在ACL语句中，当使用地址作为条件时，它的一般格式为：

  • 地址 通配符掩码。

• 通配符掩码决定了地址中的哪些位需要精确匹配，哪些为不需要匹配。

• 通配符掩码是一个32位数，采用点分十进制方式书写。匹配时，“0”表示检查的位，“1”表示不检查的位。

• 如：192.168.1.1 0.0.255.255

  • 表示检查前16位，忽略后16位，所以这个条件表示的地址是 192.168..。

• 通配符掩码也叫“反掩码”

IP trouble shooting

• 物理链接 （80%以上问题所在）

• Ipconfig, 查看IP、缺省网关配置，能看到状态

• Nslookup（是否为域名问题）

  • 
• Ping –t （长时间ping）

• 看路由表 route print，或netstat –nr，show IP route

• Tracert(Unix)，traceroute(Windows)

• 截帧工具(WireShark, Charles)

• 路由仿真(Cisco)

Reference

1. 127.0.0.1和0.0.0.0地址的区别

2. Raddit | Why RIP doesn't delete a route as soon as it becomes invalid?

3. Cicso | timers basic