# 路由器
路由器是网络层设备，基于网络层数据报中的首部字段值做出转发决定



# 转发
路由器有多个输入端口和输出端口，输入的数据报经过转发结构进入特定的输出端口

## 基于目的地的转发
IP地址有32位，假定路由器有四个输出端口，所有的$2^{32}$个目的地都应当唯一地对应于某一个端口，最终会形成这样一张表

| 目的地范围 | 端口 |
| :---: | :---: |
| 11001000 00010111 00010000 00000000~11001000 00010111 00010111 1111111 | 0 |
| 11001000 00010111 00011000 00000000~11001000 00010111 00011000 1111111 | 1 |
| 11001000 00010111 00011001 00000000~11001000 00010111 00011111 1111111 | 2 |
| 其他 | 3 |

实际上只需要使用前缀匹配即可，即像这样

| 前缀 | 端口 |
| :--- | :---: |
| 11001000 00010111 00010 | 0 |
| 11001000 00010111 00011000  | 1 |
| 11001000 00010111 00011 | 2 |
| 其他 | 3 |

如果存在多个匹配，则使用**最长前缀匹配规则**，将数据包转发到最长匹配前缀对应的端口

## 交换结构
交换结构有三种实现方式：经内存交换，经总线交换，经互联网络交换

- **经内存交换**：数据包拷贝到系统内存中进行交换，由CPU控制，每个数据包需要穿过系统内存两次，交换速度受限于系统内存
  
  在现代路由器中，目的地址的查找和数据包的存储是由输入线路卡处理的，输出端口从指定内存地址读取数据包，而不经过CPU，像共享内存的多处理器
  
- **经总线交换**：输入端口为分组指定一个端口，然后经一个共享总线传递到所有端口，只有指定的端口收到分组后才保存它

  这样不需要经过CPU，但是同一时刻只有一个分组能被转发，因为总线是共享的
  
- **经互联网络交换**：如纵横式交换机，只要目的端口不同，分组可以被并行转发，是非阻塞的

# 排队

## 输入排队
如果交换结构不够快，那么输入端口将出现排队。输入排队会带来问题
- 队头阻塞(HOL)：队头的分组会阻塞其后面所有分组的转发
- 丢包：输入队列溢出时会导致丢包

当交换结构的速率能达到所有输入端口的速率和时，就不会出现输入排队

## 输出排队
多个输入端口同时向一个输出端口发送时，会在输出端口形成排队，这样的排队是不可避免的

当输出队列满时，出现丢包。虽然增大输出队列能缓解丢包，但是更大的输出队列意味着更大的延迟，延迟太大的包终究会被重传，丢就丢了。因而输出队列并不是越长越好

## 分组丢弃
当队列满时，丢弃分组可以有以下的策略
- 弃尾：丢弃后到的分组
- 按照优先级：丢弃低优先级分组
- 随机：随机挑选一个幸运分组丢弃

还可以在队列满之前就开始丢弃分组，称为**主动队列管理**。一种策略是RED(Ramdom Early Detection 随机早检测)，它的策略是这样的：

- 路由器维护每个端口上的输出队列平均长度，按照下面的公式更新
  $$
  Len=(1-\alpha)\times Len+\alpha\times SampleLen
  $$
  
- 当平均长度达到较小阈值时，按照概率$p$丢弃后到的分组
  
  分组队列越长，距离上一次丢弃时间越长，$p$越大
  
- 当平均长度达到最大阈值时，丢弃到达的每一个分组

这与TCP的拥塞控制计是配合的

## 调度策略
调度即输出端口从队列中选择要发送更多分组，它有三种策略：先进先出，优先权排队，加权公平排队

- **先进先出**：先到的分组先被传输
- **优先权排队**：优先传输优先级高的分组，相同优先级的分组先进先出。在**非抢占式优先权排队**下，分组一旦开始传输就不能中断
- **加权公平排队(WFQ)**：将到达的分组分类，每个类别具有独立的队列，并具有一个权值，按照权值循环地选择某个分类进行传输，应保证每个分类都能分到其权值的带宽。这样各个权值的分组都有机会进行传输，权值高的分组传输的机会更多

路由器

# 一位数值比较器
一位数值比较器比较两个一位二进制数的大小，自然1比0大，如果它们相等，则输出为相等



它的真值表如下

![image.png](/static/img/208729c1a5acc97769b1c8bf4cb6e274.image.webp)

进而得到逻辑表达式
$$
F_{A>B}=A\bar{B},\quad F_{A<B}=\bar{A}B,\quad F_{A=B}=\bar{A}\bar{B}+AB
$$

由此给出逻辑图
<center>
    <img src="/static/img/9396abd5857ddacb3db9835ceeb78594.image.webp" width=50%>
</center>

# 多位数值比较器
较为简单的情形是两位数，先将两位数分别比较，然后最终的结果遵循
- 两个比较器都输出相等，那么相等
- 高位$A>B$或是高位相等，低位$A>B$则$A>B$
- 高位$A<B$或是高位相等，低位$A<B$则$A<B$

这样就能给出逻辑图
<center>
    <img src="/static/img/0e0c1059ff90c6de7ee772d155aaf4af.image.webp" width=70%>
</center>

用这种方式就能构造更多位的数值比较器，只不过电路的复杂度会上升，因为需要用到更多位的与门非门

一个简单的办法是利用串联的方式扩展，如下图

![image.png](/static/img/201a858c551ab9e482f4cba2db8b5584.image.webp)

不过这样比较慢，因为每一级都需要等待上一级完成比较才能给出结果。另一种方式是并联，就像这样

![image.png](/static/img/ddf078c14e2635e4ef08cbff3814eaae.image.webp)

当一级比较器给出等于的结果时，大于和小于信号都为0，就相等了

数值比较器

# 半加器
半加器完成两个一位二进制数的加法，给出它们的加法结果和进位，不考虑更低位的进位



它的真值表是这样的，其中的$C$是进位，$S$是该位的结果

![image.png](/static/img/4a365173c6ee77c103922d59e1100115.image.webp)

可以写出其逻辑表达式
$$
S=\bar{A}B+A\bar{B},\quad C=AB
$$

它实际上就是异或和与，可以给出它的逻辑图

![image.png](/static/img/8b17a17f6c281830cea5d9f28591703c.image.webp)

# 全加器
相比于半加器，全加器需要考虑更低位的进位，这可以用两个半加器实现，即先计算两个加数的加法，在计算结果与低位进位的加法，只要两个加法有一个出现了进位，进位的结果就是1（毕竟不可能都进位）。逻辑图就是这样子

![image.png](/static/img/28fdf03c7fa52ccf815d542067633ed1.image.webp)

其真值表为

![image.png](/static/img/3f4200f64555e99ea634ac29c2b2c0bd.image.webp)

# 多位数加法器
多位数加法可以采取串行的方式，将多个全加器串联起来

![image.png](/static/img/ce28a5f952da944d278021b5195e3fd5.image.webp)

不过这样后面的加法需要等待前面完成计算后才能给出结果。如果想加快计算，需要采取**超前进位**的方式。鉴于全加器的逻辑表达式
$$
S_i=A_i\oplus B_i\oplus C_{i-1},\quad C_i=A_iB_i+(A_i\oplus B_i)C_{i-1}
$$

如果定义中间变量（就是半加器的计算结果）,它们与进位信号无关
$$
G_i=A_iB_i,\quad P_i=A_i\oplus B_i
$$

那么全加器的结果就写为了
$$
S_i=P_i\oplus C_{i-1},\quad C_i=G_i+P_iC_{i-1}
$$

那么可以递归地消去所有的$C$，将它们都用$G_i,P_i$表示得到
$$
\begin{aligned}
C_0&=G_0+P_0C_{-1}\\
C_1&=G_1+P_1G_0+P_1P_0C_{-1}\\
C_2&=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_{-1}\\
C_3&=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_{-1}
\end{aligned}
$$

那么就可以实现**超前进位产生电路**
<center>
    <img src="/static/img/e4d6ff6bc7c2db0fc8df33d9dd0f71b9.image.webp" width=50%>
</center>

这样只需要再进行一次异或就能得到结果，得到超前进位加法器
<center>
    <img src="/static/img/f391d7b41777d6714f7f517074a80bbe.image.webp" width=50%>
</center>

整个电路的延迟为4级门延迟。不过这样做的代价是电路变得复杂（要实现非常多的异或），因而可以将多个超前进位加法器串联起来（层次化串行进位扩展连接）

![image.png](/static/img/fef9458a39ff981f3e318799b85e69fb.image.webp)

但是这样会慢，于是可以照猫画虎进行二级超前进位（层次化超前进位扩展连接）

![image.png](/static/img/59ebe4683e8f63bde31024633c618b86.image.webp)

第二级超前进位产生电路与第一级相同，其中
$$
g_i=P_3P_2P_1P_0,\quad g_i=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0
$$
上式中的$G,P$是加法器内部的传输变量。这样完成16位数的加法只需要经过8级门延迟

# 减法
可以使用补码实现减法。$n$位二进制数的补码与原码的关系为
$$
\text{补码}=2^n-\text{原码}
$$
它可以用反码得到
$$
\text{补码}=\text{反码}+1
$$
这样就能实现减法
$$
A-B=A+B_{\text{反}}+1-2^n
$$
对于减去$2^n$的运算，如果前面的加法正好进位了，进位就正好是$2^n$，进位之外的结果就是正确的；如果没有进位，计算结果应是真实结果的补码，因为若是希望得到不考虑符号位的原码，则有
$$
-\text{真实值的原码}=\text{计算结果}-2^n
$$
这就需要一个求补电路将补码转换为原码，这可以用另一个加法器实现。总的来说，电路图为

![image.png](/static/img/eeda35796c549627e60680f8e11aa1c6.image.webp)

上半部分是减法电路，下半部分是求补电路，最后的输出是原码

加法器

# 数据选择器

数据选择器有**数据输入端**和**地址输入端**，根据地址将某个数据输入端上的信号接到输出上



# 二选一数据选择器与其扩展

二选一数据选择器在两个数据输入中选择一个输出，记数据输入为$D_0,D_1$，地址输入为$S$，则其输出的逻辑函数式可以写为
$$
Y=\bar{S}D_0+SD_1
$$
真值表为
<center>
    <img src="/static/img/d7fd00b650d5b038db3f63c15069e59e.image.webp" width=50%>
</center>

依此给出其逻辑电路，逻辑符号简化为右侧

![image.png](/static/img/0423b65712250bd85e960b7d1d89c17b.image.webp)

可以用三个二选一数据选择器扩展为一个四选二数据选择器，想法是用一个数据选择选择两个数据选择器中的一个，再由下一级的数据选择器选择数据

![image.png](/static/img/3856ae876860ba507ca57119898abcbd.image.webp)

其真值表如下

![image.png](/static/img/ca6a56e5c0c7c663ef330880ddbbf285.image.webp)

也可以使用译码器和与门或门构成数据选择器，如下面的四选一数据选择器

![image.png](/static/img/bc44e7a089c5c16694f58c4854cdb450.image.webp)

译码器通过控制与门的输出进而选择数据

# 数据选择器实现逻辑函数

任意的逻辑函数都可以写为最小项求和的形式，如
$$
L=\bar{A}B+A\bar{B}
$$
就可以用数据选择器实现为
<center>
    <img src="/static/img/0a399f5b5a44b1134d35fa22429860cc.image.webp" width=30%>
</center>

不过在变量数目增加的时候数据选择器的线数会指数增加，这不好。不过数据选择器的数据不是非得接0或是1，也可以接逻辑函数，如
$$
L=A\bar{C}+BC
$$
它就可以用四选一数据选择器实现为
<center>
    <img src="/static/img/d7c87cfa0ba75798d0d5819dad78aaa1.image.webp" width=30%>
</center>

还可以进一步使用二选一数据选择器实现
<center>
    <img src="/static/img/0896cafb3a61c4867c049512a3ee121a.image.webp" width=30%>
</center>

这样的逻辑表达式是利用**香农展开定理**得到的

:::info{title="香农展开定理"}
任何一个逻辑函数$f(X_1,X_2,\cdots,X_n)$都可以被分解为
$$
f(X_1,X_2,\cdots,X_n)=\bar{X_1}\cdot f(0,X_2,\cdots,X_n)+X_1f(1,X_2,\cdots,X_n)
$$
:::

那么逻辑函数$L=A\bar{C}+BC$用香农展开定理对$A$展开得到
$$
L=\bar{A}(BC)+A(B+\bar{C})
$$

不过用$C$展开会更加简单
$$
L=\bar{C}(A)+C(B)
$$

实际使用时应当选择最简单的展开方式

# 查找表LUT
LUT是一个以真值表形式实现的逻辑函数，3输入的LUT可以这样由数据选择器实现

![image.png](/static/img/ed6fb3741dd0f5b7078a73506e53000b.image.webp)

LUT是构成FPGA的基本单元

# 移位器
移位器是能将一串二进制数进行左移或者右移操作的逻辑器件

## 基本移位器
4位基本移位器的功能表如下

![image.png](/static/img/32fd572e483e186a7ad56e31c43f7066.image.webp)

它可以由数据选择器实现

![image.png](/static/img/de84e9d2b352a4f7fe452ad5af2c0236.image.webp)

每一个数据选择器根据输入选择输出左边的数据还是自己的数据或是右边的数据

## 桶型移位器
桶型移位器不接受左边输入与右边输入，而是采取循环移位，并且可以移动任意多位。4位桶型移位器的功能表是这样的

![image.png](/static/img/aaed6af29cfb772cefba3974a7c9545b.image.webp)

它可以由数据选择器实现

![image.png](/static/img/1483712710592503ec89ae2bf0826fa5.image.webp)

每个数据选择器根据移位的不同选择某一位进行输出，因而$n$位桶型移位器需要$n$个$n$选1数据选择器

数据选择器

# 译码器
译码器可分为两种类型，
- 二进制译码器：一种是将一系列代码转换成与之一一对应的有效信号
- 代码变换器：将一种代码转换成另一种代码



# 2线-4线译码器

2线-4线译码器接受两个输入，有四个输出，另有一个使能信号。0有效的情况下，其功能表如下

![image.png](/static/img/d4d44c3a4fbb7b726dc393be9b87c5e8.image.webp)

它的逻辑图与符号如下

![image.png](/static/img/859ae7f93f5f0f9c1be68ef81f3b0e51.image.webp)

# 3线-8线译码器

3线-8线译码器的功能表如下

![image.png](/static/img/2b675306453c8302cc7791f8496e1961.image.webp)

它除了三个输入还有三个使能端$E_1,E_2,E_3$，其中$E_3$是1有效，$E_1,E_2$是0有效。其符号如下
<center>
    <img src="/static/img/62a9a668cf9578a75b9e12e672b7f232.image.webp" width=50%>
</center>

可以利用3线-8线译码器扩展为更多线的译码器，如5线-32线译码器，它的真值表是这样的

![image.png](/static/img/b2f202a45f22ac4c4c8da7b3bda9f0dc.image.webp)

它应由4个3线-8线译码器构成，另外有一片2线-4线译码器决定哪一个3线-8线译码器被激活，它的逻辑图可以画出如下

![image.png](/static/img/22847753f00d04120abc41c9d5b04afd.image.webp)

# 数据分配器

数据分配器可以利用使能端接收二进制脉冲，进而在地址线上输出该信号，就像这样

![image.png](/static/img/7e804cb1de44a81b9e75ad6f2ea3f14f.image.webp)