计网笔记_网络层

计网笔记_网络层

五月 17, 2022

5.1网络层设计问题

5.2路由算法

路由算法的职责

  1. 负责决定一个到来的包应该被传输到哪条输出线路
    如果子网内部使用数据报文，自从最好的路由上次被改变之后，对于每个数据包这个决定必须重新做。
    如果子网用的是虚拟电路，路由决定会被做出仅当一个新的虚拟电路被建立之后。在这之后，数据包只是follow之前已经被建立的路由
  2. 转发&路由

路由算法的目标

  1. 正确
  2. 简单
  3. 健壮性
  4. 稳定性（抖动的问题）
  5. 公平性
  6. 最优性
    1. 最小化包时延
    2. 最大化网络通量

路由算法的分类

  1. static（静态的）
    路由选择不会根据当前的拓扑和流量改变
    线路断了也不会改变
    就是路由器启动的时候下载到路由器里面的

    拓扑的变化：
    加/减一条线路，

  2. adaptive 适应性的
    随着 拓扑结构的变化，通常也包括traffic的变化 改变路由。
    由于考虑traffic比较复杂，所以现在学的一般只考虑拓扑结构的变化。
    拓扑结构的变化就是指的这个图上任何一个节点或者边发生变化，其他节点都能感受到。

最优化原则

最优化
如果J在I->K的最短路径上，显然，J->K的最短路径也是同样的route

sink tree

从所有的源到某个特定的的目的地的最优化的路由形成了一个根节点是目的地的树。
不含任何loop，所以每个包会被在有限跳内传输
routing 算法的目标：

  • 针对所有的router发现并使用sink tree
  • 不用的router针对现有的拓扑结构可能有不同的理解，或者掌握的信息不一样
    sinktree

最短路径路由（Shortest Path Router）

  1. 建立一个有向带权图
  2. 权值的方法：
    1. 几跳就是几
    2. 地理上的千米距离
    3. 排队和传输时延，决定于时间
    4. 一个关于距离，带宽，平均traffic，交流开销，等等的函数
  3. Dijkstra算法（已知拓扑，计算是容易的，难的是构造拓扑）

Flooding 路由算法

  1. 不需要网络拓扑信息
  2. 每个路由器将收到的包发往除了输入端口之外的所有线路

可能遇到的问题：
产生超级超级多的包

措施：

  1. 每个包的头有一个hop counter，每转发一次，计数器减一，计数器减小到0的时候，就discard
  2. 源在每个包里面放一个sequence number，每个router记录收到的最大的seq，来判断那些包已经收到过了
  3. 选择性的flooding
    1. 每个router记录收到的数据item，在数据库里面
    2. 每个item有一个版本号
    3. 只有新的data item才会被flooded

特征：

  1. 所有可能的路线都会被尝试
    1. 非常滴鲁棒，适合用于部队内部通信这样的。
  2. 至少一个包会采用最小
  3. 所有的节点都会被访问到

Distance Vector Routing：DV算法

又叫贝尔曼·福特算法

  1. 每个router维护一个表
    1. 到每个目的地的已知最好的距离
      1. 这里的distance可能是hops的数目，时延ms，etc.
    2. 使用哪条line
  2. 这个表会不断的通过跟邻居交换信息来update
    1. 发送routing信息（distance，destination）
      1. 周期性的发送
      2. 当表改变的时候
    2. 接受routing信息
      1. 如果收到了一个更好的route，就更新
      2. refresh已经存在的routes（有个时戳，对应下面那个times out）
    3. 如果某个item times out 了，就删除这一项

例子1：
E1

A I H K四列都是J收到的的邻居发的distance vector

下面那个大括号是J到几个邻居的最新距离。
假如要计算J到D的距离
那就是看D->X->J的最短距离，X是J的几个邻居
X=A:40+8
X=I:27+10
X=H:8+12
X=K:24+6

例子2：

有时候无穷大认为是16

E2
E2-1
E2-2
E2-3
E2-4
E2-5

可以发现，当网络规模不是特别大的时候，路由算法会收敛，也就是会稳定下来。

一个问题：
Count-to-infinity
计数到无穷
cti
（a）是正常的时候，从无到收敛的过程
（b）是稳定之后，A出现故障的时候，由于A故障了，所以B只能从C得到到A的距离，然后依次这样，一直扩散扩散，形成环路，而实际上A已经不能到达了。直到到达无穷（16）的时候，会认为不可达了。通过这个例子可以知道网络的规模不能太大。

另一个关于这个问题的说明：
初始：
初始
若干时间之后：
若干时间之后：

RIP:set infinity to 16
这个RIP是routing information protocol

可能出现的其他情况：
其他

一个09考研的例子 没题目，好像是让写出路由
例

  • diatance vector routing
    • RIP协议
    • CIsco EIGRP协议
  • 一些问题：
    • 当X告诉Y它有一条路，Y不知道自己是不是在这条路里面
    • 通过rumor构建路由
  • Path Vector Routing PV算法

中文名叫 链路状态路由选择算法
LS算法：
每个路由器都要干下面这些事儿：

  1. 发现它的neighbors，学到他们的网络地址，就是通过打招呼找到的。（A跟B说hi~这样）
  2. 按照统一的度量标准设置到自己邻居的distance或者cost
  3. 建立一个链路状态数据包(LSP:Link-state Packet)，显示它“学”到的所有信息
  4. 把这个包发给所有的路由器，用flooding扩散
  5. 计算到除自己以外每个router的距离

从邻居那里学一些信息

  1. HELLO包
    广播网络broadcast network：使用广播报文
    不是广播网络的：发unicast HELLO
  2. 邻居发一个reply告诉它自己是谁
    Names (Route IDs) must be globally unique
  3. 简化拓扑
    When two or more routers are connected by a LAN or other multi-access network

Artificial Node

伪节点
wjd
这个N可以是A也可以是C，也可以是F，任选一个。假如选了A，那么A内部就可以有两个邻接矩阵。

  • The cost to each of its neighbors
  • The cost to reach neighbors can be set automatically
  • Configured by the network operator
  • Make the cost inversely proportional to the bandwidth of the link

构造链路状态数据包

LSP

啥时候构造 LSP：

  1. 周期性的构造
  2. 当“大事情”发生的时候构造一下
    就比如是一个line或者neighbor going down了/come back up了，或者显著的改变性质了

分发LSP

懒得翻译了
distribute

关于LSP

  • sequence number
    • 新的LSP：向所有人转发
    • 复制的LSP：discard
    • 小于目前收到的最大的序列号：认为是废旧的
    • 如果一个router down（关掉）了，然后又restart（重启）了，（这样可能导致版本低了）就拒绝（旧版本的）
    • 如果序号wrap（回绕）了，具体的协议中是2^32次方个数，基本上用不完，可能需要100多年才能回绕
    • 受损：因为是可靠传输，所以会重传
  • age
    • 指的是LSP的存活时间
    • 应用状态/解决的问题
      • 如果路由器关了
      • 如果路由器改变了它的routerid

LSP flooding 算法的精巧/改进之处

sdf

计算新的Route

当一个router收集到了一整套的LSP，它就可以建立整个图了
然后运行迪杰斯特拉算法，算最短路径
计算结果就被扔到routing table里面

一个例子

图1
图2

LSR的例子

了解即可
例子

Hierarchical Routing 分层次的路由

简化路由表的例子：
简化路由表
就是把几个离得近的路由器划分成一个小组，然后抽象成原本的一个点

5.3 Congestion Control 算法

congestion：拥塞
出现拥塞的原因：太多的traffic被提供，网络性能剧烈下降
yongsai
次要因素：突发流量与缓冲队列(太长/太短)
慢CPU忙于维护操作，转发操作太慢导致线路容量浪费
弄很长的内存可行吗？不能完全解决了，因为排的队比较长，时间太长，超时了，数据就无效了。

拥塞控制和流量控制的区别

拥塞控制是一个全局的问题
流量控制是2个站点之间的问题，是通过一些反馈信息减缓发送端的发送速度，从而使发送端的速度与接收端的接收或者处理速度相适配。

拥塞控制的方法

approach

从左往右：
网络供给增加
流量感知路由
许可证的控制
流量的限制/调节
Load shedding 甩负荷

Traffic-aware Routing

有一些危险：
routing 表可能会剧烈的震荡，当两部分之间有两条类似的线路时

Admission Control 准入控制

在虚电路中广泛被使用
如果网络拥塞了，就不让建立新的虚电路
traffic的描述：通过rate和shape来描述
shape有两种：leaky bucket，token bucket

Traffic Throttling 流量限制

当即将发生拥塞的时候，网络告诉sender节流。
（有趣的是这里的“网络”指的是路由器，能“告诉”的只有路由器了）

  • 路由器需要决定什么时候拥塞正在迫近，理想情况下是在拥塞到来之前就判定
  • 一般根据下面这些来判定：
    • 输出线路的利用率
    • 队列的长度
    • 现在丢包的数量
    • 算平均值的方法：
      EWMA：Exponentially Weighted Moving Average
      $$d_{new}=\alpha d_{old}+(1-\alpha)s$$
      上式中,s是当前的量，阿尔法是一个系数，一般取0.8
  • 路由器需要周期性的向导致拥塞的sender发送反馈信息
    • Choke packets
    • ECN
    • Hop-by-Hop backpressure

Choke packets 抑制分组

路由器选择一个在拥塞线路上发送的分组（拥塞分组），然后给源发送一个choke packet
（internet source quech message），让源端降速的一个消息

ECN（Explicit Congestion Notification）

显式的拥塞通知
（其实上面那个也算显式的）

  • 路由器对每个packet加tag，来标记它沿途有拥塞
  • 当网络传输这个packet的时候，destination可以发现这个标记的拥塞，然后在回复的时候告诉sender（有另外一个可以打tag的bit位，reply的时候给打上）
  • sender就像之前一样，节流了。

图示

隐式的拥塞通知

当一个包经过了拥塞，就丢掉它，这样sender就会超时，而且本身网络的错误是比较少的，这样sender就会节流。

Hop-by-Hop Choke Packets

没听

问题：
解决：

它可以很快的把流量降下来

Loading Shedding

当router已经满了，就扔掉它们

Polices：

  • Wine&Milk
    • 对应File transfer和multimedia
  • 需要senders的配合
  • 包的优先级
    • 视频压缩算法，重要的包打上tag，尽量保重点
    • 允许主机超过协议说好的带宽，但是超出的部分标上比较低的优先级

RED（random early detection）
随机早期检测

  • 在网络情况没有变成没有希望的时候就开始扔包
  • router如何让source知道出现了问题呢？
    • 发一个choke包
    • 丢掉选出来的包
  • sources 降低发送速率

ECN&RED

  • RED 在剩余缓存空间到达临界值（不一定满）的时候就开始扔包，而ECN只在路由器的buffer满了的时候才会丢包。
  • ECN 是通常更愿意选择的, 它显示的产生一个拥塞信号 rather than as a loss; 当主机不能接收显示的信号时，RED 就派上用场了。

5.4 QOS

  • Reliability
  • Delay
  • Jitter 抖动
  • Bandwidth

一些应用对上述几个标准的要求：
需求

Traffic Shaping

需要解决的问题：
主机发送的数据包是不规律的，对网络不友好，可能产生拥塞

SLA:服务等级的约定（Service Level Agreement）
Between the user and the subnet

  • The user: traffic shaping reduces congestion and helps carrier live up to its promise
  • The carrier: traffic policing
    (CAR: Committed Access Rate)

Traffic shaping：

  • Regulate the average rate and burstiness of data transmission, smooth out the traffic

Traffic Policing：

  • Monitoring a traffic flow
  • Packets in excess of the agreed pattern might be dropped or marked as having lower priority

The Bucket Algorithm

桶

leaky bucket

桶里面攒的是数据，固定速率，平缓的发送，减少拥塞的机会。

token bucket

桶里面攒的不是数据，而是一堆令牌。相当于是有段时间没发送，然后攒了一堆令牌，然后突然有大量数据一下来了，就可以一下子发挺多。

token bucket algorithm

几张图
这个图里面，每行是一组。
最后一组，令牌桶的容量是0，所以就相当于是漏桶。

几个关键参数：

S：burst length ，单位是sec，突发时间
B：，单位是byte，令牌桶的容量
R：，byte/sec，令牌到达的速度

最大的output速度：M ，单位是byte/sec

$$
B+RS=MS
$$
$$
S=B/(M-R)
$$

举个例子：
例子

另一个例子：

突发速率为10Mbps的一台主机通过一个令牌桶进行流量调整。令牌桶的令牌到达速率为2Mbps，令牌桶的初始容量为8Mb。请问该主机以10Mbps速率可以传输多长时间？

相当于求S
$$
S=B/(M-R)=1*8Mbits/(10-2)=1s
$$

Packet Scheduling 分组调度

简单了解即可\

算法：

  • FIFO，（FCFS），tail drop 先来先服务（out）
  • RED，讲过，随机早期检测，隐式的拥塞控制，扔包。
  • FQ:fair queue，公平队列

Round-robin Fair Queueing

循环调度
就轮着拿包，问题在于数据包的大小不一样，包小的就吃亏了。

WFQ: Weighted Fair Queueing

WFQ

还有一种叫PQ：优先级队列
优先级高的先发送。

5.5 Internetworking

网络不同在哪？

differ

不同的网络进行互联：

  1. 用一种设备，转换一种网络到另一种网络，适用于网络种类比较少的情况
  2. 在不同网络的上面加一个层次，在这一层进行转换，是目前ip网络选择的方案
    俩人弄的这个，搞到了图灵奖：Vinton Cerf, Robert Kahn 1974, Turing Award 2004

不同网络是如何进行互联的呢？

图片

网桥&路由器

Tunneling隧道

tunneling
vpn就是这个道理。

互联网络的路由

路由器看作顶点，网络看作路由。
内部网关协议 LS,DV
外部网关协议 PV

MTU 最大传输单元

maximum transmission unit

数据包分段

MTU是一个网络内部允许（用户）传输的最大尺寸

Fragmentation 分片

来了个大的数据包我就切成小的碎片。

  1. 透明transparent分片，网络里的透明就是看不见的意思，简单来说，透明分片就是进入一个网络的时候切片，出去的时候再组装回去。
    但透明分片太复杂了，因为每次都得这么倒腾一回，而且每个数据包都必须到达同一个路由器出口。
    Recombination occurs at the exit gateway (ATM)
  2. 非透明nontransparent分片，避免在任何一个路由器上重新组合。每个小分段都被当做一个完整的数据包来对待，只有到了目标主机才进行组合。
    Recombination occurs only at the destination host (IP)
    但是这个的问题在于，任何一个碎片丢了，目的端主机就装不回去了。

IP协议是这么干的
IP 分组命名
头的中间那个东西是一个序号标识，就代表我这一个分段里，对应到原始包里，第一个字节前面有多少字节，拿（b）举例，I字节前面有8个字节，所以写8.

path MTU discovering的策略

就是不断尝试，找到这一条路由能发送的最大的MTU，就是向下兼容，找到最小的口。
path

5.6 The Network Layer in the Internet

其实就是ip
这里谈的就是不同网络进行互联里面的第二个

10大通用设计原则（RFC文档）

由重要到不重要
原则

IPV4协议

（各个字段的作用/含义是要掌握的）

字段

图片1

图片2

下面是一些option的功能：
一些option

ip地址

dizhi

地址分为5类，其中ABC三种是给用户设备用的，其余的是特定的地址，不是给用户用的。
A B C:unioncast，
D：分组转发，multicast
E: broadcast

一些特殊的地址：
special

全0：本机地址，我不知道我自己的地址，就全写0，一段时间之后，网上的服务器会给分配一个地址
network 全0：本网络的地址
全1：本地网络的广播
network+全1：远程的某个网络的广播
127+其他的任何东西：比如127.0.0.1，指的是本机的地址。
查看本地的ip路由表：netstat -rn
还有一共ipconfig 忘了是干啥的了。
本地的计算机还是有路由表的。

prefix:前缀

两种表示方法，表示网络号的位数

  1. 128.208.0.0/24 (prefix length)
    代表前24位是网络号
  2. 128.208.0.0/255.255.255.0 (netmask)这个东西就叫掩码
    也代表前24位是网络号，具体实现是做与运算
    tup

两种方法的对应关系：
关系

子网划分

有点像指令地址的划分，但又不是平均分的。
它是先一分为2，然后把其中一份再一分为2…..这样，根据$log_2(需要的地址数目)向上取整$，来决定怎么划分。
就是一个学校有一个网络号，然后拿出几个bit来标记分给不同的院系来使用。
这样的

一个例子

就有点像切西瓜这样，先切一半，然后对其中一半再切。
由于全0全1基本不用，所以一般可用地址的数目要-2。
比如 8位，$2^8$个不同的数，但是只有$2^8-2$个有效地址。
然后可用的地址范围，拿这道题里面的LAN1来说，写1~95是不对的，因为划分范围是7位数的地址，满足大于95，它不一定是连续的，可以这一个用了，下一个不用这样，地址范围是$2^7-2$，然后写可用范围就是

$$
192.168.1.1~192.168.1.126
$$

CIDR——无类域间路由（子网划分的逆）

Route aggregation：路由聚合

多条路由汇聚成一条路由，跟子网划分是完全相反的一个过程。使得路由表长度减少。

而且还比子网划分要简单，就找出来这几个路由的前面多少位是一样的就行了（

聚合

但是一个问题是，右边的那几个地址没完全用完，如果不幸出现了下图状况：

状况

就本来应该去san francisco 的就被发到lodon去了。
所以路由器匹配的一个基本原则就是“Longest matching prefix routing”最长前缀匹配原则。

路由表

一个array包括[IP address, netmask, outgoing line, Next hop]

扫描路由表：

  1. netmask 掩码和目的地址做与运算，然后到表里匹配。
  2. 很可能多个都匹配，原则是最长匹配（longest mask）

09年一个题
09年一个题

根据已知路由表进行路由选择：

route选择

NAT(Network address translation)

是为了解决ip地址不够用的速战速决的一个临时方法。
nat
nat2

IPV6

128位地址，换算成16字节，可以说是永远用不完了。
IPV6的固定头：
ipv6头
头
解释

没有checksum字段了。没有protocol字段了。

虽然头部精简了很多，但是地址太长了。
IPV6还有扩展头，ppt134
这样

IPV6的地址：
IPV4是点分16进制，IPV6叫冒分16进制表示法，两个字节一组，分8组。
j
下面是3种简化的表示方法。
最后那个是v4地址转换成v6地址的方法，前面全0

Internet 控制协议

ICMP (Internet Control Message Protocol)

互联网控制消息协议
封装在IP packet里面
当路由器处理一个数据报出现了意外，可以通过ICMP向源端报告有关事件
1

这里的回显ECHO和回显应答其实就是ping。所以ping是通过ICMP工作的。

关于Trace route

ARP Address Resolution Protocol

地址解析协议
需要ARP的原因：


路由表，直接交付与间接交付

这里是IPi是ip地址，Ei是mac地址

一个形象的例子：

一些优化：

找到目的地址之后还会放在缓存里保存一段时间。设置超时时间或者让每台新加入的机器广播他的映射关系。

ARP 代理：

这个是为了解决早期一些机器的网络掩码不能改变，导致的问题

DHCP (Dynamic Host Configuration Protocol)

动态主机配置协议

差不多是完成主机配置初始化这样一个工作，然后是自动完成的。

关键词：计算机初始接入网络没有IP地址，广播DISCOVER 报文，DHCP 转播助手(relay agent) ，DHCP服务器，IP租赁

OSPF (Open Shortest Path First)

开放最短路径优先，是一个普遍使用的 域内路由算法/内部网关路由协议 （interior gateway protocol），开放指的是开源。

AS（autonomous system）独立网络/自治系统

这个图上的(a)给出的就是一个AS

这个图中LAN是虚拟的节点，是从周边的三个路由器中抽象出来的。
工作方式：

由于OSPF对于规模比较大的网络效率极低，所以需要对区域进行划分。

OSPF Routers

5 Types of OSPF Messages

OSPF是使用IP报文承载传送的，IP是不可靠的，尽力而为的报文，丢了就丢了，所以OSPF需要自己确认。RIP（路由信息协议，好像是那个会计数到无穷的）采用的是UDP数据，是不可靠的。

BGP (Border Gateway Protocol)

边界网关协议，是一种外部网关路由协议，或者说是域间路由算法
底层是TCP connection


word table

Datagram n.【电脑】数据电报
optimality 最优性
optimal 最理想的，最佳的
adaptive a.适应的，适合的
estimate 估计，估价，判断，看法
datagram 数据报文
anew 重新，再
virtual circuits 虚拟电路
contradict v.矛盾，抵触
metric 公制的，米制的，度量标准
artificial adj. 人造的, 人工的, 假的
duplicate n. 完全一样的东西, 复制品adj. 完全一样的, 复制的
obsolete adj. 老式的；废弃的
router down：路由器关闭了，再重启可能造成版本低
Refinements n. 精致, 高尚, 精巧
Hierarchical adj. 分等级的，分层次的
Congestion 拥挤，拥塞
preventive adj. 预防的,防止的
reactive adj. 反应的
leaky adj. 漏的；有漏洞的
imminent adj. 迫近的；即将来临的
throttle 节流n&v
utilization n. 利用
jitter 抖动
Round-robin 循环调度
flat 平坦的，平的
prefix 前缀
circumstances 情况，条件
out of order 次序颠倒，无次序的
hypothesis 假说，假设
hierarchy n. 等级制度
clusters 丛，簇
vicinity 临近，附近
consecutive a.连续的
aggregate vt. 总计达…vt. & vi. (使)聚集
NIC 网卡 Network Interface Card
ISP一般指网络业务提供商 Internet Service Provider

  1. 5.1网络层设计问题
  2. 5.2路由算法
    1. 路由算法的职责
    2. 路由算法的目标
    3. 路由算法的分类
    4. 最优化原则
    5. sink tree
    6. 最短路径路由（Shortest Path Router）
    7. Flooding 路由算法
    8. Distance Vector Routing：DV算法
    9. Link State Routing ：LS算法
      1. 从邻居那里学一些信息
      2. Artificial Node
      3. 设置 Link Cost
      4. 构造链路状态数据包
      5. 分发LSP
      6. 关于LSP
      7. LSP flooding 算法的精巧/改进之处
      8. 计算新的Route
      9. LSR的例子
    10. Hierarchical Routing 分层次的路由
  3. 5.3 Congestion Control 算法
    1. 拥塞控制和流量控制的区别
    2. 拥塞控制的方法
    3. Traffic-aware Routing
    4. Admission Control 准入控制
    5. Traffic Throttling 流量限制
      1. Choke packets 抑制分组
      2. ECN（Explicit Congestion Notification）
      3. 隐式的拥塞通知
      4. Hop-by-Hop Choke Packets
    6. Loading Shedding
  4. 5.4 QOS
    1. Traffic Shaping
    2. The Bucket Algorithm
      1. leaky bucket
      2. token bucket
      3. Packet Scheduling 分组调度
  5. 5.5 Internetworking
    1. 网络不同在哪？
    2. 不同网络是如何进行互联的呢？
    3. Tunneling隧道
    4. 互联网络的路由
    5. MTU 最大传输单元
      1. path MTU discovering的策略
  6. 5.6 The Network Layer in the Internet
    1. 10大通用设计原则（RFC文档）
    2. IPV4协议
    3. ip地址
      1. prefix:前缀
      2. 子网划分
      3. CIDR——无类域间路由（子网划分的逆）
    4. 路由表
  7. NAT(Network address translation)
  8. IPV6
  9. Internet 控制协议
    1. ICMP (Internet Control Message Protocol)
    2. ARP Address Resolution Protocol
    3. DHCP (Dynamic Host Configuration Protocol)
  10. OSPF (Open Shortest Path First)
  11. BGP (Border Gateway Protocol)
  12. word table