第三章、网络层

这章很重要！！要好好学尼

3.1介绍

网络层在主机和路由器实现，交换机无

网络层的关键功能

• 转发forwarding
• 路由routing（选路）

网络层分为

• 数据平面data plane

  • 本地的，每个路由都提供的功能
  • 决定如何将路由器输入端口的数据报转发到输出端口
  • 转发功能（通过判断到达数据报的头部就可以决定）

• 控制平面control plane

  • network-wide logic网络范围的逻辑

  • 决定数据报如何选择从哪个端口输出能到达目标主机

  • 两个控制平面实现方法

    • 传统路由算法（每个路由器配置自己的算法）eg.Dijkstra算法
    • software-defined networking (SDN)全网实现，将硬件软件网络软件化（数据平面与控制平面分离

网络服务模式Network service model

• 单个数据报（individual datagrams）的服务

  • 保证安全
  • 保证不太慢less than 40 msec delay

• 数据报流（a flow of datagrams）的服务

  • 有序的数据报传输
  • 保证最小流量带宽
  • 对数据包间距更改的限制

3.2虚拟电路（VC）和数据报电路网络

Virtual circuit and datagram networks

类似传输层服务，但服务面向host to host

• 网络只提供其中一种，所以没得选
• 实现在网络核心core（链路层为端口到端口）

虚拟电路网络（简写为VC）

• 提供网络层连接的服务

• 提供类似电路的服务

  • 呼叫设置，在数据流动之前对每个呼叫进行拆解（teardown）
  • 每个数据包都带有 VC 标识符（identifier）（不是目标主机地址）
  • source-dest路径上的每个路由器都为每个通过的连接维护（maintains）”状态”（建立连接后保持独享）
  • 链路，路由器资源（带宽、缓冲区）可以分配（allocated）给 VC

• VC实现

  • 包含

    • 从源到目标的路径
    • VC 编号，沿路径的每个链路对应一个编号，属于VC的数据包都带有（新的编号来自转发表）
    • 沿路径的路由器转发表（forwarding tables ）中的条目（Entries）

  • 信令（signaling）协议

    • used to setup, maintain teardown VC
    • 步骤：（包含端到端的状态，呼叫后预留）
    • 用在ATM, frame-relay, X.25
    • 现在不用了

• ATM适合，对时序要求很高，需保证服务，终端很笨（“dumb” end systems哑终端）

数据报网络

• 提供网络层无连接的服务
• 在网络层无建立连接
• 路由器：没有关于端到端连接的状态（无网络级连接概念）不维护端与端之间的通信，只管转
• 用目标主机地址转发的数据包（同一源-目标端的数据包可能有不同的路径）
• Internet适合，终端处理能力强，对信道要求不高，“弹性elastic”服务

3.3路由器

通用路由器体系结构

Input port functions

• destination-based forwarding: forward based only on destination IP address (traditional)

  • 最长前缀匹配Longest prefix matching ppt25

    • 通常使用三元内容可寻址存储器（ternary content addressable memories TCAMs）执行（content addressable: present address to TCAM: retrieve address in one clock cycle, regardless of table size）
    • Cisco Catalyst: can up ~1M routing table entries in TCAM

• generalized forwarding: forward based on any set of header field values

Input port queuing

• 线头阻塞Head-of-the-Line blocking (HOL) :队列前面的排队数据报阻止队列中的其他数据报向前移动

三种类型交换结构switching fabrics

（将数据包从输入缓冲区传输到适当的输出缓冲区）

• 交换速率：数据包从输入传输到输出的速率

  • 通常测量为输入/输出线速的倍数
  • N 个输入：开关速率 N 倍于线性速率

• Switching Via Memory

  • 在 CPU 直接控制下切换的传统计算机
    数据包复制到系统内存
    速度受内存带宽限制（每个数据报 2 个总线交叉点）

• Switching Via a Bus

  • 通过共享总线从输入端口存储器到输出端口存储器的数据报
  • 总线争用❗bus contention：开关速度受总线带宽限制
  • 所有端口共享总线，易冲突，并行效率低 但对普通接入足够

• Switching Via An Interconnection Network通过交叉线交换

  • 每两个都有唯一的对应，提高并行效率

Output Ports

• buffering缓冲

• Scheduling discipline 调度规则

  • Priority scheduling（优先调度） – who gets best performance, network neutrality（网络中立性）

Output port queueing

• how much buffering? P34

• Scheduling mechanisms调度机制

  • FIFO (first in first out) scheduling先进先出

    • discard policy丢弃策略

      • tail drop丢掉后到的: drop arriving packet
      • priority优先级: drop/remove on priority basis
      • random随机: drop/remove randomly
      • Round Robin (RR) scheduling轮询
      • Weighted Fair Queuing (WFQ):加权轮询

3.4 IP: Internet Protocol

IP特点：

• IP 为遍历网络的数据报提供路由功能

• 每个数据报都有源地址和目标地址

• IP 确定数据报是否已到达其目标，或者是否必须转发数据报

  • 如果必须转发，IP 将确定下一跃点（next hop）

• IP 不提供可靠性保证

  • 不保证数据包一定能到达其指定的目的地

• IP 负责数据报(datagram)的拆分（fragmentation）

• 数据报不能超过(exceed)其所传输网络的最大大小

  • 这在创建时未知

• 太大的数据报必须分解为片段（fragments）

• 每个片段必须包含重新组合原始数据报所需的信息

  • 标有长度(length)和偏移量(offset)

• Workhorse 主力？

3.4.1.IPv4 datagram format

• 按位数分：

  • IPv4：32-bit* number

    • Written in （点分十进制）Dotted Decimal Notation:205.150.58.7
    • 4 billion different host addresses

  • IPv6：128-bit* number

    • Written in Hex Decimal Notation（十六进制）
      2001:0503:0C27:0000:0000:0000:0000:0000
    • 16 billion billion network addresses

• IP Fragmentation拆分 & Reassembly组装

  • 网络链路有❗MTU (max.transfer size) 最大传输大小-最大可能的链路级帧（不同链路有不同的MTUs）

  • “reassembled组装” only at final destination

  • IP header bits used to identify识别, order related fragments

  • 拆分计算

  • 检验是否有错

  • IP路由操作命令

    • winipcfg/(ipconfig)

      • 显示用户所在主机内部的IP协议的配置信息P51

    • . netstat

      • 主要功能：使用户了解到自己的主机是怎样与因特网相连的P53

3.4.2IPv4 addressing

• 从不同的层次看数据流动P56

• 1、IP Address Classes

  • 分配IP地址

    • 由于每个接口必须具有唯一的IP地址，因此必须有一个中央机构(central authority)来分配（assigning）号码

      • 这个中央机构为Internet Network Information Center, called the InterNIC.仅分配网络id，主机id的分配由系统管理员决定。
      • 交换机无IP
      • 主机典型有一个interface
      • 路由器典型的有多个interfaces

    • IP 地址的一些重要特点

      • 分两个等级的好处是：

        • IP地址管理机构在分配IP地址时只分配网络号，剩下的主机号由得到该网络号的单位自行分配，方便管理
        • 路由器仅根据目的主机所连接的网络号转发分组，无需考虑目的主机号（链路层来做），使路由表中的项目数大幅减少，减小路由表所占空间

      • IP地址标志一个主机（或路由器）和一条链路的接口（interface）

        • 多归属主机multihomed host（一个主机连接两个网络，有两个相应的IP地址（net-id））
        • 由于一个路由器至少应当连接到两个网络（这样它才能将 IP 数据报从一个网络转发到另一个网络），因此一个路由器至少应当有两个不同的 IP 地址。

      • 用转发器或网桥连接起来的若干个局域网仍为一个网络，因此这些局域网都具有同样的网络号 net-id。

      • 所有分配到网络号 net-id 的网络，范围很小的局域网，还是可能覆盖很大地理范围的广域网，都是平等的。

  • IP层转发分组的流程

    • 特定主机路由（为特定的目的主机指明一个路由，方便网络管理人员控制和测试网络/考虑安全问题）

    • 默认路由default route（网络只有很少的对外连接有用

      • 路由器采用默认路由以减少路由表所占用的空间和搜索路由表所用的时间

    • 注：

      • 当路由器收到待转发的数据报，不是将下一跳路由器的 IP 地址填入 IP 数据报，而是送交下层的网络接口软件。
      • IP 数据报的首部中没有地方可以用来指明“下一跳路由器的 IP 地址”
      • 网络接口软件使用 ARP 负责将下一跳路由器的 IP 地址转换成硬件地址，并将此硬件地址放在链路层的 MAC 帧的首部，然后根据这个硬件地址找到下一跳路由器。

    • (1) 从数据报的首部提取目的主机的 IP 地址 D, 得出目的网络地址为 N。

    • (2) 若网络 N 与此路由器直接相连，则把数据报直接交付目的主机 D；否则是间接交付，执行(3)。

    • (3) 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行(4)。

    • (4) 若路由表中有到达网络 N 的路由，则把数据报传送给路由表指明的下一跳路由器；否则，执行(5)。

    • (5) 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行(6)。

    • (6) 报告转发分组出错。

• 2、IP Subnet Addressing

  • 本地IP地址组成

    • network ID
    • subnet ID
    • host ID

  • （1）Subnets and Subnet Masks子网和子网掩码

    • (IP Address) AND (Subnet mask) = Net Address

      -

      • eg.不同的子网掩码得出❗相同的网络地址。
        但不同的掩码的效果是不同的。 所以子网掩码是一个很重要的属性

    • 子网掩码是一个重要属性

      • 路由器在和相邻路由器交换路由信息时，必须把自己所在网络（或子网）的子网掩码告诉相邻路由器
      • 路由器的路由表中的每一个项目，除了要给出目的网络地址外，还必须同时给出该网络的子网掩码

  • （2）Subnetting子网划分

    • a.借多少位（上图为判断类别参考）

      • 可以借的范围

        • 网络地址类别

          • C 类：8 个主机位
          • B 类：16 个主机位
          • A 类：24 个主机位

        • 至少借两位：2^2-2=2个子网（全0和全1不用，所以减2）（子网和广播地址）

      • 知道需要多少个子网和主机

        • Host Bits = Bits Borrowed + Bits Left
        • x为需要的子网数量
        • x为需要的主机数量

      • 计算出结果

      • ❗注：形如192.168.15.0/26（C类）类型的网址/后的数字表示借多少位C类为24+借的位数，示例为借了2位

        • C类为24~32
        • B类为16~32
        • A类为8~32

    • b.子网掩码subnet mask是什么

      • 对应的网络号也都赋值为1，借的位数（子网号）都赋值为1，对应（correspond）的主机号都赋值为0（预留出来的不用的主机），为子网掩码

        • eg.一个C类网络IP：210.93.45.0，借3位（11111111.11111111.11111111.11100000）的
          子网掩码为255.255.255.224

    • c.magic number or multiplier?

      • magic number=256-子网掩码点分后的最后一个非零数（Last Non-Zero Octet）
      • magic number可视为划分后每个子网的主机数量（包含广播和主机的，也就是没-2的时候的）（自己理解的，非官方）
      • eg. Last Non-Zero Octet为224，例子中子网的migic number为256-224=32
      • Last Non-Zero Octet表格（可计算得到）

    • d.子网地址是什么

      • 子网地址（主机号全为0的）：相较未被划分的IP地址（点分十进制）只改变借用位置部分的数（C类为最后一个，B类为倒数第二个，A类为倒数第三个）=第几个子网*magic number。
        子网地址加上主机号就是子网地址（自己总结，非官方）

  • （3）Logical AND Operation逻辑与操作

    • 设备使用 AND 计算（computation）来确定每个 IP 地址的子网标识符（the subnet identifier ）。
    • 如果本地 IP 地址的子网标识符与要与之通信的 IP 地址的子网标识符相同，则数据包将发送到本地子网上。
    • 如果子网标识符不同，则数据包将发送到默认网关（default gateway ）或本地路由器，以路由到远程子网。

  • 划分子网后分组如何转发？ PPT 131-136

    • (1) 从收到的分组的首部提取目的IP地址D。

    • (2) 先用各网络的子网掩码和D逐比特相“与”，看是否和相应的网络地址匹配。若匹配，则将分组直接交付。否则就是间接交付，执行(3)。

      • 相较上面的分组转发算法多了和D逐比特相“与”

    • (3) 若路由表中有目的地址为D的特定主机路由，则将分组传送给指明的下一跳路由器；否则，执行(4)。

    • (4) 对路由表中的每一行的子网掩码和D逐比特相“与”，若其结果与该行的目的网络地址匹配，则将分组传送给该行指明的下一跳路由器；否则，执行(5)

      • 相较上面的分组转发算法多了和D逐比特相“与”

    • (5) 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认路由器；否则，执行(6)。

    • (6) 报告转发分组出错。

  • 得到一个IP地址的方式

    • hard-coded硬编码 by system admin系统管理员 in a file

      • 好处：固定
      • 缺点：可能发生冲突

    • DHCP: Dynamic Host Configuration Protocol: dynamically get address from as server
      动态从服务器获取（即插即用plug-and-play）

      • 目标：允许主机在加入网络时从网络服务器动态获取其 IP 地址

        • 可以在使用中的地址上续订其租约（renew its lease ）
        • 允许重复使用地址（仅在连接/“打开”时保留地址）
        • 支持想要加入网络的移动用户

      • 获取步骤

        • 主机广播”DHCP discover（DHCP发现报文）”消息 [可选]
        • DHCP 服务器响应”DHCP offer（DHCP应答报文）”消息 [可选]
        • 主机请求 IP 地址：DHCP request（DHCP请求报文）”消息
        • DHCP 服务器发送地址：”DHCP ack（DHCP确认报文）” 消息

      • 不仅可以返回子网上分配(allocated)的IP地址

        • 客户端的第一跃点路由器的地址
        • DNS 服务器的名称和 IP 地址
        • 网络掩码（指示地址的网络与主机部分）

      • ISP从ICANN（ Internet Corporation for Assigned Names and Numbers）获取地址块

        • 分配地址
        • 管理 DNS
        • 分配域名，解决争议(resolves disputes)

3.4.3.Slowing IP Address Depletion

IP地址耗尽速度变慢

• 可变长度子网掩码Variable Length Subnet masks可变长度子网掩码VLSM

  • 将子网再次划分
  • 组成：network/subset/ VLSM subset /Host

• 无类域间路由Classless Interdomain Routing

  • Classless InterDomain Routing（CIDR）

    • 任意长度的地址的子网部分
    • 地址格式：a.b.c.d/x，其中 x 是地址子网部分的 # 位，例子中的子网的所有地址的23位前缀都是一样的

  • 路由聚合(route aggregation)

    • 一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为路由聚合，它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由。

    • 路由聚合也称为构成超网(supernetting)。

      • 前缀长度不超过 23 位的 CIDR 地址块都包含了多个 C 类地址。
      • 这些 C 类地址合起来就构成了超网。
      • CIDR 地址块中的地址数一定是 2 的整数次幂。
      • 网络前缀越短，其地址块所包含的地址数就越多。而在三级结构的IP地址中，划分子网是使网络前缀变长。

    • CIDR 虽然不使用子网了，但仍然使用“掩码”这一名词（但不叫子网掩码）。

    • 对于 /20 地址块，它的掩码是 20 个连续的 1。 斜线记法中的数字就是掩码中1的个数。

  • CIDR记法的其它形式

    • 10.0.0.0/10 可简写为 10/10，也就是把点分十进制中低位连续的 0 省略。

      -

    • 网络前缀的后面加一个星号 * 的表示方法，此方法可实现路由聚合

      • 如 00001010 00*，在星号 * 之前是网络前缀，而星号 * 表示 IP 地址中的主机号，可以是任意值。
        

      • eg.
        
        - 层次编址允许高效的路由信息通告:
        - 使用单个网络前缀通告多个网络的能力称为地址聚合或路由聚合或路由摘要
        - 其他路由器路由转发分组时,使用最长前缀匹配法则,找到正确路由。
        

  • 匹配/寻找方式

    • 选择两个匹配的地址中更具体的一个，即选择最长前缀的地址。

• 网络地址转换NAT：Network Address Translation

  • 动机：就外部世界而言，本地网络仅使用一个IP地址

    • ISP 不需要的地址范围：所有设备只需一个 IP 地址
    • 可以在不通知外界的情况下更改本地网络中设备的地址
    • 可以更改ISP，而无需更改本地网络中设备的地址
    • 本地网络内的设备无法明确寻址，外部世界可见（安全加分项）。

  • 实现：NAT 路由器必须

    • 传出数据报(outgoing datagrams)：将每个传出数据报的（源 IP 地址、端口号(port #)）替换为（NAT IP 地址、新端口 #）远程客户端/服务器将使用（NAT IP 地址、新端口 #）作为目标地址进行响应。
    • 记住（在 NAT 转换表中）每个（源 IP 地址、端口号）到（NAT IP 地址、新端口号）转换对
    • 传入数据报：将每个传入数据报的 dest 字段中的（NAT IP 地址、新端口号）替换为存储在 NAT 表中的相应（源 IP 地址、端口号）

  • 16 位端口号字段：

    • 60，000 个同时(simultaneous)连接，单个 LAN 端地址！

  • NAT是有争议的：

    • 路由器最多只能处理第 3 层

    • 违反端到端参数

      • 应用程序设计人员必须考虑NAT的可能性，例如，P2P应用程序

    • 地址短缺应该由IPv6解决

3.4.4.IPv6

• 初始动机：可以完全分配 32 位地址空间。

• 其他动机：

  • 标头（header）格式有助于加快处理（processing）/转发（forwarding）速度
  • 标头更改以方便（facilitate） QoS

• IPv6 数据报格式：固定长度 40 字节标头

  • 不允许拆分（fragmentation）

• 数据报格式

  • version:4bits（值为6“0110”）表示IPV6的报文
  • 有效载荷长度（Payload Length）：16 bit，以字节为单位的 IPv6 载荷长度，也就是 IPv6 报文基本头以后部分的长度（包括所有扩展头部分）。
  • Priority: 8bits,identify priority among datagrams in flow确定流中数据报的优先级
  • Flow Label:20bits, identify datagrams in same “flow.” 标识同一”流”中的数据报(concept of“flow” not well defined).
  • Next header: 8bits下一个头部字段用来标识当前报头（或者扩展报头）的下一个头部类型，占8位。每种扩展报头都有其对应的值。
  • Hop Limit：8bits,ttl(time to live)

• 过渡Transition From IPv4 To IPv6

  • 不能同时升级，有成本考虑

  • 采用隧道形式，将IPV6的报文伪装成IPV4的报文

3.5路由算法

Routing algorithms

路由、转发之间的相互作用（Interplay）

路由协议目标

• 通过路由器网络确定从发送主机到接收主机的”良好”路径（等效于路由）

  • 路径：路由器数据包序列将从给定的初始源主机遍历到给定的最终目标主机
  • “好”：最小”成本”，”最快”，”最不拥挤”

路由算法

• 抽象图

  • Graph: G = (N,E)图是由节点和边构成的
  • N = set of routers = { u, v, w, x, y, z }节点的集合
  • E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }边的集合

• 路由算法：查找成本最低的路径的算法

• 分类

  • 全局式Global

    • 所有路由器都有完整的拓扑结构，链路成本信息
    • “链接状态（link-state）”算法

  • 分布式decentralized

    • 路由器知道物理连接的邻居，与邻居的链路成本
    • 迭代（iterative）计算过程，与邻居交换信息（info）
    • “距离矢量(distance vector)”算法

  • 静态Static

    • 路由随时间缓慢变化

  • 动态dynamic

    • 路线变化更快

      • 定期(periodic)更新
      • 响应链路成本变化

link state链路状态路由算法Dijkstra’s algorithm

• 网络拓扑topology，链路花销为所有节点都知道

  • 通过”链路状态广播(link state broadcast)”完成accomplished
  • 所有节点都具有相同的信息

• 计算从一个节点（”源sorce”）到所有其他节点的最低成本路径

  • 为该节点提供转发表

• 迭代：在 k 次迭代之后，知道到 k 个 dest 的最小成本路径。

• • c(x,y): link cost from node x to y; = ∞ if not direct neighbors
  • D(v): current value of cost of path from source to dest. v
  • p(v): predecessor node along path from source to v
  • N’: set of nodes whose least cost path definitively known

• 算法复杂度：n 个节点

  • 每次迭代：需要检查所有节点，w，不在N

  • n(n+1)/2 comparisons: O(n2)

  • 可实现更高效的实现：O（nlogn）

  • 可能的振荡：

    • 例如，刚算出走这个节点，下次迭代就是另一个结点更近

distance vector距离向量算法（分布式decentralized）

• Bellman-Ford equation方程 (dynamic programming动态规划)

• Dx(y) = estimate of least cost from x to y
  Distance vector: Dx = [Dx(y): y є N ]
  Node x knows cost to each neighbor v: c(x,v)
  Node x maintains Dx = [Dx(y): y є N ]
  Node x also maintains its neighbors’ distance vectors
  For each neighbor v, x maintains Dv = [Dv(y): y є N ]

• 基本思想：

  • 每个节点定期向邻居发送自己的距离矢量估计值
  • 当节点 x 从邻居处收到新的 DV 估计值时，它将使用 B-F 等式更新自己的 DV：
  • 在次要的自然条件下，估计值 Dx（y） 收敛到实际最小成本 dx（y）

• 迭代iterative：

  • 本地链路成本更改
  • 来自邻居的 DV 更新消息

• 分散式distributed：

  • 每个节点仅在其 DV 更改时通知邻居

    • 然后，如有必要，邻居会通知邻居

• 链接成本变化：

  • 节点检测到本地链路开销变化
  • 更新路线信息，重新计算距离矢量
  • 如果 DV 发生变化，通知邻居
  • 好消息传播的快，坏消息传播缓慢 - “数到无穷大”的问题！

Comparison of LS and DV algorithms

• Message complexity消息复杂性

  • LS: with n nodes, E links, O(nE) msgs sent

  • DV: exchange between neighbors only

    • convergence time varies收敛时间不定

• Speed of Convergence收敛速度

  • LS: O(n2) algorithm requires O(nE) msgs

    • may have oscillations 可能有振荡，但是不易产生路由环路

  • DV: convergence time varies

    • may be routing loops可能是路由环路
    • count-to-infinity problem数到无穷大问题

• Robustness: what happens if router malfunctions?鲁棒性（强壮与健壮，系统在异常情况下的生存能力）

  • LS:

    • 节点可以公布（advertise ）不正确的链接（link）开销
    • 每个节点仅计算（computes ）自己的表

  • DV:

    • 节点可以公布（advertise ）不正确的路径（path ）开销

    • 每个节点的表都被其他表使用

      • error propagate thru network错误通过网络传播

3.6 Routing in the Internet

Hierarchical routing层次路由

• 由于规模大不能存储所有目标
  行政自主权（administrative autonomy）
  两个问题产生层次路由

• 将路由器聚合到称为“autonomous systems”（AS）的区域（也称为”domains”）中

  • 自治系统 (Autonomous System)

    自治系统 AS 的定义：在单一的技术管理下的一组路由器，而这些路由器使用一种 AS 内部的路由选择协议和共同的度量以确定分组在该 AS 内的路由，同时还使用一种 AS 之间的路由选择协议用以确定分组在 AS之间的路由。
    现在对自治系统 AS 的定义是强调下面的事实：尽管一个 AS 使用了多种内部路由选择协议和度量，但重要的是一个 AS 对其他 AS 表现出的是一个单一的和一致的路由选择策略。

  • intra-AS routing
    AS 内路由

    • 也称为内部网关协议 （interior gateway protocols ，IGP）

      • 最常见的 AS 内路由协议：

        • RIP：Routing Information Protocol路由信息协议
        • OSPF：开放最短路径优先Open Shortest Path First（IS-IS协议（本质为OSPF）与OSPF基本相同）
        • IGRP：内部网关路由协议:Interior Gateway Routing Protocol （思科专有数十年，直到2016年）

    • 在同一AS（”网络”）中，主机、路由器之间路由

    • AS 中的所有路由器必须运行相同的域内（intra-domain）协议

    • 不同 AS 中的路由器可以运行不同的域内路由协议

    • 网关路由器（gateway router）：在其自身 AS 的”边缘”，具有到其他 AS 中的路由器的链接

  • inter-AS routing
    AS 间路由

    • 在 AS 之间路由
    • 网关（gateways）执行域间路由（以及域内路由）

  • 总结：为什么Intra-, Inter-AS routing 不同

    • policy:

      • inter-AS（AS间路由）: 管理员希望控制其流量如何路由，谁通过其网络路由。
      • intra-AS（AS内路由）: 单个管理员，因此不需要策略决策

    • scale:

      • 分层路由可以节省表的大小，减少更新流量（traffic）

    • performance:

      • intra-AS: 专注于性能
      • inter-AS: 政策可能支配性能

  • Interconnected ASes互连的 AS

    • 转发表由 AS 内intra-AS和 AS 间inter-AS 路由算法配置

    • AS 内部路由设置内部目标（internal dests）的转发表的条目entries

    • AS 间和 AS 内设置外部目标的转发表的条目entries

      • Inter-AS tasks(AS间任务)：
        1.了解哪些目标主机可通过邻接的AS访问
        2.并将这些可访问信息传播到此AS中的所有路由器(AS内协议执行)。以便知道有任务时传给哪个
        eg.P208

  • Hot potato routing：将数据包发送到两个路由器中最近的一个

• 有关路由选择协议的几个基本概念

  • 1. 理想的路由算法

    算法必须是正确的和完整的。
    算法在计算上应简单。
    算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。
    算法应具有稳定性。
    算法应是公平的。
    算法应是最佳的。

  • 2.关于“最佳路由”

    不存在一种绝对的最佳路由算法。
    所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
    实际的路由选择算法，应尽可能接近于理想的算法。
    路由选择是个非常复杂的问题
    它是网络中的所有结点共同协调工作的结果。
    路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。

  • 3.从路由算法的自适应性考虑

    • 静态路由选择策略——即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。
    • 动态路由选择策略——即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。

  • 4.分层次的路由选择协议

    因特网采用分层次的路由选择协议。
    因特网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。
    许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到因特网上。

  • 5.因特网有两大类路由选择协议

    • 内部网关协议 IGP (Interior Gateway Protocol) 即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。
    • 外部网关协议EGP (External Gateway Protocol) 若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议 EGP。在外部网关协议中目前使用最多的是 BGP-4。

RIP路由选择信息协议

• 1. 工作原理

  • 路由信息协议 RIP 是内部网关协议 IGP中最先得到广泛使用的协议。

  • RIP 是一种分布式的基于距离向量的路由选择协议。

  • RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。

  • “距离”的定义

    从一路由器到直接连接的网络的距离定义为 1。
    从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。
    RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。
    这里的“距离”实际上指的是“最短距离”，
    RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。
    RIP 允许一条路径最多只能包含 15 个路由器。
    “距离”的最大值为16 时即相当于不可达。可见 RIP 只适用于小型互联网。
    RIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。

  • 三个要点：

    • 仅和相邻路由器交换信息。
    • 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
    • 按固定的时间间隔交换路由信息，例如，每隔 30 秒。

  • 路由表的建立

    • 路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。
    • 以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。
    • 经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。
    • RIP 协议的收敛(convergence)过程较快，即在自治系统中所有的结点都得到正确的路由选择信息的过程。
• 2. 距离向量算法

  -

  • 路由器之间交换信息

    • RIP协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。
    • 虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。

• RIP 协议的优缺点

  • RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。（好消息传播得快，而坏消息传播得慢）
  • RIP 协议最大的优点就是实现简单，开销较小。
  • RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。
  • 路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。

OSPF （Open Shortest Path First）首先打开最短路径

• 介绍

  • “开放”：公开可用

  • 使用link-state算法

    • 链路状态数据包分发（dissemination）
    • 每个节点的拓扑图
    • 使用Dijkstra算法的路由计算

  • 路由器将 OSPF 链路状态通告扩散（floods）到整个 AS 中的所有其他路由器

    • 直接通过 IP（而不是 TCP 或 UDP）在 OSPF 消息中传输

      OSPF 不用 UDP 而是直接用 IP 数据报传送。
      OSPF 构成的数据报很短。这样做可减少路由信息的通信量。
      数据报很短的另一好处是可以不必将长的数据报分片传送。分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。

    • 链接状态：对于每个附加（attached）的链接

  • IS-IS 路由协议：几乎与 OSPF 相同

• 高级功能”advanced” features

  • 安全性security：所有 OSPF 消息都经过身份验证（authenticated）（以防止恶意入侵（malicious intrusion））

  • 允许多个相同成本的路径（RIP 中只有一个路径）

  • 对于每个链路，针对不同 TOS 的多个成本指标（例如，卫星链路成本设置为“low”以实现”尽力而为ToS”，”high”用于实时 ToS）

  • 集成的integrated，支持单播和多播uni- and multi-cast：

    • Multicast OSPF （MOSPF） 使用与 OSPF 相同的拓扑数据库

  • 大型域中的hierarchical OSPF。

    -

    • 两级层次结构two-level hierarchy：局部区域local area、骨干网backbone。

      • 链接状态广告仅在区域内
      • 每个节点都有详细的区域拓扑;只知道方向(最短路径)到网的其他区域。

    • 区域边界路由器area border routers：

      • “汇总”到自己区域内网络的距离，通告给其他区域边界路由器。

    • 骨干路由器backbone routers：运行仅限于骨干网的 OSPF 路由。

    • 边界路由器boundary routers：连接到其他 AS（自治系统）。

• 三个要点

  • 向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。

  • 发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。

    • “链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。

  • 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

• 其他特点

  • OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。
  • 由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多。
  • OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。

• 指定的路由器(designated router) ？？？

  • 多点接入的局域网采用了指定的路由器的方法，使广播的信息量大大减少。
  • 指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

Internet inter-AS ：BGP routing（Border Gateway Protocol）实际的域间路由协议

• BGP为每个AS提供了一种方法:

  • eBGP:向邻居as获取子网可达性信息
  • iBGP:向所有as内部路由器传播可达性信息。
  • 根据可达性信息和策略确定到其他网络的“良好”路由

• 允许子网将它的存在通告给Internet的其他部分:“我在这里“

• BGP session：两个 BGP 路由器（”peer”）通过半永久性(semi-permanent) TCP 连接交换 BGP 消息：

  • 发布到不同目的网络前缀的路径（BGP 是”path vector”协议）

• 路径属性和 BGP 路由

  • 播发的前缀(advertised prefix)包括 BGP 属性

    • 前缀 + 属性 = “路由”（prefix + attributes = “route”）

  • 两个重要属性：

    • AS-PATH：前缀advertisement经过的AS列表
    • NEXT-HOP：指定到达下一跳AS的域内AS路由器

  • 基于策略的路由Policy-based routing：

    • 网关接收路由通告使用导入策略来接受/拒绝路径
    • AS 策略还确定是否将路径通告到其他相邻的 AS

• BGP路径通告

  • 网关路由器可以了解到目的地的多个路径

    • AS1 网关路由器 1c 从 2a 学习路径 AS2、AS3、X
    • AS1 网关路由器 1c 从 3a 学习路径 AS3，X
    • AS1 网关路由器 1c 根据策略选择路径 AS3、X，并通过 iBGP 在 AS1 中通告路径

• BGP 报文（message）

  • 通过 TCP 连接在对等方之间交换的 BGP 报文

  • 报文类型：

    • OPEN：打开与远程 BGP 对等体的 TCP 连接，并对要发送的 BGP 对等体进行身份验证authenticates
    • UPDATE：公布新路径（或撤回旧路径）
    • KEEPALIVE：在没有UPDATE的情况下保持连接活跃;还 ACK 打开请求
    • NOTIFICATION：报告以前的消息中的错误;也用于关闭连接

• 路由器可以了解到目标 AS 的多个路由，根据以下条件选择路由：

  • 本地首选项值属性(local preference value attribute)：策略决策(policy decision)
  • 最短的 AS 路径shortest AS-PATH
  • 最近的下一跳路由器(closest NEXT-HOP router)：热土豆路由hot potato routing
  • 其他标准additional criteria

• BGP协议的特点

  • BGP 协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。
  • 每一个自治系统中 BGP 发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。
  • BGP 支持 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。
  • 在BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销方面都有好处。

3.7 广播路由和多播路由

Broadcast and multicast routing

IP多播

• 多播可明显地减少网络中资源的消耗

• IP多播特点（只在局域网内使用）：

  • (1) 多播使用组地址—— IP 使用 D 类地址支持多播。多播地址只能用于目的地址，而不能用于源地址。
  • (2) 永久组地址——由因特网号码指派管理局 IANA 负责指派。
  • (3) 动态的组成员
  • (4) 使用硬件进行多播

• IP多播需要两种协议

  • 为了使路由器知道多播组成员的信息，需要利用网际组管理协议 IGMP (Internet Group Management Protocol)。

    • IGMP 的本地使用范围

      • IGMP 并非在因特网范围内对所有多播组成员进行管理的协议。
      • IGMP 不知道 IP 多播组包含的成员数，也不知道这些成员都分布在哪些网络上。
      • IGMP 协议是让连接在本地局域网上的多播路由器知道本局域网上是否有主机（严格讲，是主机上的某个进程）参加或退出了某个多播组。

  • 连接在局域网上的多播路由器还必须和因特网上的其他多播路由器协同工作，以便把多播数据报用最小代价传送给所有的组成员。这就需要使用多播路由选择协议。

3.8 ICMP: Internet Control Message Protocol网络控制消息协议

用于主机和路由器之间的网络级信息通信

• 错误报告error reporting:不可达的主机，网络，端口，协议
• Echo请求/应答(由ping使用)

网络层”高于“IP:

• IP数据报中携带的ICMP消息

ICMP报文:类型、代码加导致错误的IP数据报的前8个字节

-

Traceroute and ICMP

• Source发送一系列 UDP 段

  • 首先具有 TTL =1
  • 第二个有 TTL=2，依此类推。
  • 不太可能的端口号

• 当第 n 个数据报到达第 n 个路由器时：

  • 路由器丢弃数据报并发送到源 ICMP 消息（类型 11，代码 0）
  • 消息包括路由器和IP地址的名称

• 当 ICMP 消息到达时，Source计算 RTT

• Traceroute 会执行此操作 3 次

• 停止标准（criterion）

  • UDP 段最终到达目标主机
  • 目标返回 ICMP”主机无法访问”数据包（类型 3，代码 3）
  • 当源获得此 ICMP 时，将停止。

ICMP的实用程序

• （1）.Ping

  • 主要功能： PING用来测试两个主机之间的连通性。PING使用了ICMP回送请求与回送回答报文。PING是应用层直接使用网络层ICMP的例子，它没有通过运输层的 TCP或UDP。

  • 使用格式：ping [-t] [-a] [-n count] [-l size]

  • 参数介绍：

    -t 让用户所在的主机不断向目标主机发送数据
    -a 以IP地址格式来显示目标主机的网络地址
    -n count 指定要ping多少次，具体次数由后面的count来指定
    -l size 指定发送到目标主机的数据包的大小

  • ping命令的其他技巧：

    在一般情况下还可以通过ping对方让对方返回给你的TTL值大小，粗略的判断目标主机的系统类型是Windows系列还是UNIX/Linux系列，一般情况下Windows系列的系统返回的TTL值在100-130之间，而UNIX/Linux系列的系统返回的TTL值在240-255之间，当然TTL的值在对方的主机里是可以修改的，Windows系列的系统可以通过修改注册表以下键值实现： [HKEY_LOCAL_MACHINE＼SYSTEM＼CurrentControlSet＼Services＼Tcpip＼Parameters] "DefaultTTL"=dword:000000ff 255---FF ，128---80，64----40，32----20
    

• （2）.tracert

  • 使用格式：tracert [-d] [-h maximum_hops] [-j host_list] [-w timeout]

  • 参数介绍：

    • -d 不解析目标主机的名字
    • -h maximum_hops 指定搜索到目标地址的最大跳跃数
    • -j host_list 按照主机列表中的地址释放源路由
    • -w timeout 指定超时时间间隔，程序默认的时间单位是毫秒

  • 主要功能：判定数据包到达目的主机所经过的路径、显示数据包经过的中继节点清单和到达时间。

3.9 Network management and SNMP

network management：什么是网络管理？

“Network management includes the deployment, integration and coordination of the hardware, software, and human elements to monitor, test, poll, configure, analyze, evaluate, and control the network and element resources to meet the real-time, operational performance, and Quality of Service requirements at a reasonable cost.”
“网络管理包括（包含）硬件、软件和（对象）人员元素的部署、集成和协调，以（目的）监控、测试、轮询、配置、分析、评估和控制网络和元素资源，以（达到目标）合理的成本满足实时、运营性能和服务质量要求

Infrastructure for network management网络管理基础架构

• 受管设备包含受管对象，其数据被收集到管理信息库 Management Information Base （MIB） 中

SNMP protocol

• 传达 MIB 信息的两种方式，命令：

  -

​ 因为知识点很多，这部分的笔记最开始是用思维导图记的，但是图片都不能导出，xmind格式的到百度网盘自行下载或者联系我私发叭，笔记效果如下（也不是那么好看，建议还是看PPT或者自己整理效率较高，我的笔记整理效果稍稍欠缺）：