Interconnection Network
互联网络用来保证不同设备之间连接和通信，例如多处理器之间的连接、处理器与内存之间的连接、I/O设备的通信等。根据网络连接的设备数量和距离，可以分为四类
- On-chip networks（OCNs）
- System/storage area networks (SANs)
- Local area networks (LANs)
- Wide area networks (WANs)
互联网络的重要问题有两个：
- Topology：网络拓扑结构，即如何构建整个网络
- Routing：路由，在给定图网络中如何确定一条信号传输路径
- Buffering and Flow Control：网络两个节点之间如何发送信息
Routing
routing就是一种算法，用来确定源和汇之间的路径。
按照路径确定的方式，可以分为三类算法：
- Deterministic：确定性算法，给定相同的源和汇，路径一定是相同的。
- Oblivious：给定相同的源和汇，不考虑网络状态，路径不同。
- Adaptive：给定相同的源和汇，结合网络状态选择一条路径。
在设计routing算法时，一个非常关键的问题是Deadlock，当多条路径形成一个环时，每条路径都在等待其他路径释放资源，则会形成死锁。
处理Deadlock的方法一般可以分为3类：
- 设计不存在Deadlock的routing算法
- 通过增加更多buffering避免Deadlock
- 对Deadlock进行检测并设置打破机制
考虑2维数组形式的网络结构，对于Deterministic算法，可以采用XY routing的方法，路径先只在X方法走，再走Y路径，或者设计一种规定，一定不走每个方向的转弯，即可避免成环。
Deterministic算法优点是非常简单。且能有效解决Deadlock，但容易造成网络拥塞，无法合理利用资源。Oblivious Routing的一个方法是随机选择一个中转点，先路由到中转点，再路由到目的地，这种随机化的方法可以平衡网络的负载，但同时会增加网络延迟，路由路径可能要绕一个大圈子。
Adaptive Routing可能根据当前负载的情况，当原路径阻塞时，自动调整为走其他端口，当然这需要注意livelock情况，即路由路径一直在网络中转圈，没有往目的地走。
Buffering and Flow Control
解决了路径问题，我们继续讨论网络中两个节点之间如何传输信息（message）。一条message一般分为多个packets进行传输，每个packet有一个header信息用来便于接收方还原成原信息。之所以要分为多个packet发送，是考虑到网络中的传输带宽限制，同时便于错误恢复，当一个包损坏时，只需要发送丢失的packet，而不需要发送整条信息，此外分割为不同的packet可以增加路由的灵活性，不同的packet走不同路径到达目的地。
“Flit” 是指 “flow control unit” 的缩写，它是数据在网络中传输时的最小单元。在某些网络中，特别是在一些高性能计算和通信系统中，数据包可以进一步分解为更小的单元，即 flits。
关于 flits 的一些关键特点：
- Flow Control Unit： Flit 是用于流量控制的基本单元，它负责在网络中控制数据的流动。
- 无附加头部： 根据你的描述，flits 通常不包含额外的头部信息，这与传统的网络数据包有所不同。这有助于减少每个单元的开销，提高网络的效率。
- 数据单元： Flit 包含实际的数据，是传输数据的最小单位。一个数据包可能由多个 flits 组成。
- 流量控制和拥塞管理： 使用 flits 作为流量控制的单元可以更精细地管理网络中的数据流，有助于防止拥塞和提高整体性能。
需要注意的是，使用 flits 的网络通常是在高性能计算或通信系统中，而在一般的互联网通信中，通常使用更大的数据包。 Flits 的使用在一些定制的、对性能有较高要求的环境中比较常见。(By ChatGPT)
在传输时，流量控制的方法有以下几种：
Circuit switching
Bufferless (Packet/flit based)
Store and forward (Packet based)
Virtual cut through (Packet based)
Wormhole (Flit based)
Circuit switching会为两个设备之间建立专用的通信路径，会提前分配好资源，这样就不需要buffering，也不存在不同路径之间的资源竞争，但效率较低，两个流之间无法共用同一连接。
使用Bufferless的方式packet不会在网络中缓存，如果发生冲突，可能导致丢包，就必须再重新发送丢失的包，不太适合一些负载较大的网络。
Store and forward方式在存储转发时会收集完整的数据包存储在缓存区，再进行发送。cut through则不需要完全接受整个数据包，可以提前发送，后续的片段跟着前面的片段走即可。可以看到cut through发送速度更快，但是store and forward可以更及时进行错误检测并传输已损坏的数据包，可靠性更好。
Wormhole Flow Control类似于cut through的方法，但不同是worm through以flit为单位进行数据传输。
Topology
bus
bus是最简单的拓扑结构，低成本，易实现，但缺点是不方便扩展大量节点，且容易拥塞。只有1条连接，跳转次数为1。
Point-to-point
点对点的网络对于$O(n)$个节点，需要$O(n^2)$条边，优点是不会发送资源竞争、速度快但缺点是高成本。跳转次数为1。
Ring
Ring共用2条线，最大跳转次数为$\frac{n}{2}$。
Crossbar
需要$O(n^2)$条边，最大跳转次数为$O(n)$。
2D-Mesh
2D-Torus
Fat-Tree
Hyper-cube
对于64个节点的网络，有如下规律：
