计网笔记第四章

计网笔记

协议栈和segment，datagram结构

选路和转发

virtual circuit and datagram networks

虚拟电路和数据报网络

数据报网络提供网络层无连接服务
虚拟电路提供网络层连接服务

VC

1. 从始点到终点的一条path路径
2. path上的每个link都有个VC number
3. path上的路由上转发表的entries

属于VC的packet有一个VC number
VC number在每个link中可以改变

VC转发表

需要建立，维持，拆除VC连接
使用在ATM技术中，现在的互联网不用了

datagram network数据报网络

• 不需要再网络层建立固定的连接
• 依靠packet中的终点主机地址来转发

由于有4亿个ipv4地址，所以不可能路由的转发表填着确切的ip地址，而是填着ip地址范围

最长前缀匹配

当在转发表中寻找目标地址的条目，使用最长前缀匹配查找下一个link

路由器

1. 路由，管理控制层(软件)
2. 转发数据层(硬件)

输入端口

线路端接 -> 数据链路处理(协议，拆封) -> 查找，转发，排队

使用destip地址，根据转发表查找输出端口
如果到达的速率大于转发的速率就需要排队

交换结构

三种交换方式：

• 内存
• 总线
• 纵横式

内存

• packet被复制到系统内存
• 速度被内存的带宽bandwith限制

总线bus

• 交换速率被总线的带宽限制

纵横式

输出端口

排队(缓存管理) -> 数据链路处理(协议，封装) -> 线路端接

输出端口排队

• 如果通过路由器的到达速率大于输出端口的送出速率，那么就在输出端口的缓存区进行缓存
• 需要排队或者导致丢包因为缓存区大小有限

输入端口排队

输入缓存区溢出会导致排队时延或者丢包

线路前部阻塞HOL
一个输入队列的排队分组必须等待交换结构发送(即使输出端口是空闲的)，因为它被位于线路前部的另一个分组所阻塞。

ipv4数据报格式

ip数据报分片

MTU最大传输单元
并不是所有链路层协议都能承受相同长度的网络层协议分组，一个链路层帧能承载的最大数据量叫做最大传送单元

ip数据报分片

一个大的的ip数据报进入一个路由器，输出为多个小的ip数据报

例子：

MTU为4000字节，首部占20字节，即有效荷载为1480字节 flag = 1表示后面还有，flag = 0表示这是最后一个片
offset是表示插入数据开始与offset * 8字节

分片的ip数据报要等到终点主机之后才会被重新组装

ipv4编址

接口interface：主机或者路由和物理链路之间的连接，路由器一般都有多个接口，主机有一个或者多个接口(优先以太网和无线)

ip地址：subnet part + host part

subnet part高位 host part低位

子网

设备的接口的ip地址带有相同的subnet部分，物理上可以到达其他设备，而不需要中间路由器

子网掩码network mask

223.1.3.0/24表示从高位开始24位为network part，即223.1.3

数有多少个子网，例子：

所以一共是6个子网

划分网段，例子：
问题：将一个地址快200.23.16.0/20划分为长度相等的8个段

划分为的8个段因为长度相等，所以必须具有长度相等的host part，所以20位network part之后又2^3位作为不一样，进入network part，后面留着相同的位数作为host part

获取ip地址

DHCP动态主机设置协议

从服务器中动态地获取ip地址

DHCP server位于子网中，如果位于其他子网也需要它服务的话，需要交换机可以转发广播。

DHCP工作原理

1. 到达的客户发送广播DHCP发现报文(DHCP discover)
2. 服务器收到报文之后发送DHCP提供报文(DHCP offer)
3. 到达的客户从一个或者多个服务器中选择一个，发送DHCP请求报文
4. 服务器用DHCP ACK报文对DHCP请求报文进行相应。

DHCP不仅仅提供ip地址，还提供：

• 第一跳路由的地址
• DNS服务器的名字和ip地址
• 子网掩码

NAT网络地址转换

上图过程：

1. 主机10.0.0.1使用3345端口向外网ip地址为128.119.40.186的web服务器发送一个datagram
2. NAT路由器接收到这个datagram，为该数据包生成一个新的端口号5001，将datagram源ip改为其广域网一侧广域网ip地址138.76.29.7，将源端口改为5001。并在NAT转换表中增加这一表项，将修改之后的datagram转发出去
3. 当NAT路由器接收到web服务器的response datagram之后，跟目的ip地址和端口号找到NAT转换表中的子网ip地址和的端口号，并转发

ICMP: internet control message protocol网络控制信息协议

被主机或者路由器用来交流网络层的信息
* 错误提示：到达不了得主机，网络，端口，协议
* 两种信息类型：echo request/reply(使用ping)
建立在ip层上：ip数据报包裹着ICMP信息

Traceroute and ICMP

1. 源主机发送一系列的UDP segment到dest
   
   • 第一个设置TTL = 1
   • 第二个设置TTL = 2，一次类推
2. 当第n个datagram到达第n个路由器
   
   • 路由器抛弃datagram
   • 路由器发送ICMP message(type 11, code 0就是11 0 TTL expired类型的ICMP信息)
   • ICMP message包括了路由器的名字和ip地址
3. 当ICMP message到达，源主机记录RTTs

停止的标准(ping停止)

• UDP segment最终到达目标主机
• 目标主机返回了ICMP信息"端口不可到达type 3,code 3"
• 源主机自己停止了

ipv6

• 固定长度的40位header
• 不可以分片

ipv6 datagram形式：

中文版：

ipv6和ipv4相比

• 不可以分片和重新组装
• 没有首部校验和了，因为传输层TCP/UDP和数据链路层已经有校验操作了，所以ip的网络层的校验属于多余
• 没有选项部分

互联网怎么同时处理同时有ipv4和ipv6的路由器：

隧道技术：ipv6的datagram在ipv4形式的datagram中以payload(payload有效负载)的形式来存储
外面是ipv4的header，ipv4的source dest addr，隧道两边(就是外面)的路由器是根据这个外面的ipv4 source dest addr来router，ipv6是包裹在里面。

隧道技术效果：

期中考试分界线

路由算法

路由器的选路和转发

• 路由算法决定end-end-path，找到最小cost的路径
• 本地转发表决定路由器上的本地转发

路由器知道的信息

global

所有路由器都有全局的拓扑和link cost，成为link state

decentralized

路由器是只知道连着哪个邻居，通向邻居的link cost以及邻居告诉它的，成为distance vector

路由器的稳定与否
静态：

• 路由器长时间改变很缓慢

动态：

• 路由器非常频繁地改变

  • 周期性更新
  • 对link cost做出反应

Dijsktra’s Algorithm

例子

distance vector距离向量算法

表示：
dx(y)x到y整条路径的最小cost

x到y的路径的cost等于它先到邻居的cost加上邻居到y的最小cost

Bellman-Ford例子：

要点：
Dx(y)是x到y的最小cost估计，N中每个节点都需要估计自己到y节点的最小cost。

每个节点中有一个距离向量
Dx = [Dx(y): y є N ]
这个距离向量包含着这个节点到N中所有节点最小cost的估计

而对于每个节点的邻居节点，也是这样：
Dv = [Dv(y): y є N ]

在距离向量算法下，每个节点需要维护的信息有：

• 这个节点到邻居节点的cost
• 这个节点到N中每个节点的预计最小cost，也就是距离向量
• 这个节点邻居的距离向量

算法：

1. 每段时间按之后，每个节点把自己的距离向量副本发送给自己的邻居
2. 当每个节点接收到邻居发送过来的距离向量，拿这个距离向量更新自己的DV，使用BF公式

DV算法例子：

LS和DV比较

• LS需要知道达到所有节点的cost，因此需要洪泛，但是DV不需要
• LS的时间复杂度是O(N^2)，时间复杂度比DV更高
-

自治系统内部路由选择协议intra-AS routing protocols

三种：

• RIP
• OSPF
• IGRP

RIP

• 最大15跳
• 每30秒使用RIP相应报文来交换一次距离向量
• 响应报文包含多达25个目的子网的列表

从路由器A到各个子网的跳数：

RIP例子：
路由器D的路由表

OSPF

• 使用link state算法，使用Dijkstra算法Dijkstra 算法来路由计算
• 安全，只有受信任的路由器可以参与OSPF算法

BGP

• 外部BGP会话eBGP：两个AS之间的BGP会话(实质上是TCP连接)
• 内部BGP会话iBGP:AS内部不同路由器之间的BGP会话

Broadcast routing广播转发

从packet从源路由器转发到所有节点

source duplication源复制

in-network duplication网络中复制

• 泛洪：当节点接受到广播的packet，把复copy发送给所有的邻居
• 控制泛洪：节点只广播它之前没有向邻居广播过的packet
  
  • 通过packet id记录
  • 相反路径转发RPF
• 覆盖树：沿着覆盖树走
  
  • 首先构建覆盖树
  • 节点只沿着覆盖树转发copy

构建生成树spanning tree：
任何节点都不会受到冗余的packet

1. 先选择一个center node中心点
2. 每个其他点发送单播加入树报文给中心点，这个报文被转发知道它到达一个属于生成树的节点或者中心点
3. 加入树报文经过的路径定义了这个节点到中心点之间的生成树分支
4. 生成生成树之后，节点只沿着生成树转发副本

Multicast routing: problem statement

不是所有的路由器对广播感兴趣，所以构建特定的树

RPF例子

第四章很重要，最好自己学习一下，老师说的，对以后工作会有帮助