计算机网络 （2）

子网掩码

取值

• NetID，SubID 位全取1
• HostID位全取0

example

s	d
A网	255.0.0.0
B网	255.255.0.0
C网	255.255.255.0
借用3bit划分子网的B网	255.255.224.0

• 子网地址 + 子网掩码 -> 准确确定子网大小
• 目的ip地址 ： 172.32.1.112 （10101100 00100000 00000001 01110000）
• 子网掩码 ： 255.255.254.0 （11111111 11111111 11111110 00000000）
• 子网地址 ： （10101100 00100000 00000000 00000000）172.32.0.0 （子网掩码：255.255.254.0）
• 地址范围 ： 172.32.0.0 ~ 172.32.1.255
• 可分配地址范围 ： 172.32.0.1 ~ 172.32.1.254
• 广播地址 ： 172.32.1.255

CIDR

• netid + subid -> prefix 可以任意长度 / 提高ipv4地址空间分配效率 ， 提高路由效率 ，

路由聚合 （route aggregation）

• 最长前缀匹配优先

DHCP协议

• 硬编码 - 静态配置
• 动态主机配置协议 Dynamic Host Configuration Protocol
• 即插即用 ， 允许地址重用 ， 支持移动用户加入网络
• 主机广播 DHCP discover / DHCP服务器利用 DHCP offer 进行响应 / 主机请求IP地址 ： DHCP request / DHCP 服务器分配IP地址 ： DHCP ack

NAT 网络地址转换

• 替换 / 利用替换每个外出IP数据报
• 记录 / 存储到NAT转换表中
• 替换 / 进入内网IP数据报
• 争议 ： 路由器只处理第3层功能 / 违背端到端通信原则 / 地址短缺问题该由IPv6来解决
• NAT穿透问题 / 解决 ： 静态分配 ， 利用UPnP（Universal Plug and Play） IGD（Internet Gateway Device）

ICMP协议 互联网控制报文协议

• 差错报告 （5种）1.目的不可达 2.源抑制 （source quench） 3.超时/超期 4.参数问题 5.重定义 （redirect） / 网络探询 （2组） 1.Echo请求与Reply 2.时间戳请求与应答

Type	Code	description
0	0	回声应答（ping）
。。。	。。。	。。。
12	0	IP首部错误

• ICMP 报文格式
• ICMP差错报告报文数据封装
• ICMP的应用 ： Traceroute

IPv6

• 动机 ： 32位IPv4地址空间已分配殆尽 / 其他动机 ： 改进首部格式
• IPv6 数据报格式 ： 固定长度的 40 Byte 基本首部 / 不允许分片 / priority 优先级 / flow label 流标签 / next header 下一个首部
• checksum 校验和 - 彻底移除 / options - 允许 / ICMPv6 ： 新版ICMP
• 一般形式 ： 1080：0：FF：0：8：800:200C:417A
• 压缩形式 ： FF01:0:0:0:0:0:0:43 压缩-> FF01::43
• IPv4-嵌入形式
• 地址前缀 ： 2002:43c:476b::/48 (IPv6不再使用掩码)
• URLs
• IPv6 基本地址类型 - 1.unicast 单播 2.multicast 多播 3.anycast 任意播
• tunneling 隧道 ： IPv6数据报作为IPv4数据报的载荷进行封装，穿越IPv4网络

路由算法

• 网络抽象 ： 图
• 图抽象 ： Costs 费用
• 分类 ： 静态路由 vs 动态 / 全局信息 （LS） vs 分散 (DS)

链路状态路由算法

• Dijkstra 算法 1.计算从一个结点到达所有其他结点的最短路径 2.迭代 3.符号 ： c(x,y) D(v) p(v) N’

初始化：
  N'={u}
  for 所有结点 v
  if v 毗邻 u
    then D(v) = c(u, v)
  else D(v) = ∞

Loop
  找出不在 N' 中的 w , 满足 D(w) 最小
  将 w 加入 N'
  更新 w 的所有不在 N' 中的邻居 v 的 D(v) :
    D(v) = min( D(v), D(w) + c(w,v) )
until **所有结点在N'中

• 算法复杂性 ： n个结点 1.\(O(n^2)\) 2.更高效的 $O(nlogn)$
  • 存在 oscillations 震荡

Distance Vector 路由算法

• bellman-ford方程 （动态规划）
  • $d_x(y) = \underset{v}{min}{ c(x,v) + d_v(y) }$
• sssas