CSE_lecture17:network-ip

Network Layer: All about routing

IP协议的传输是尽力而为(best-effort)的，因此是可以丢包的

与之对应的是guaranteed-delivery network，需要一个缓存队列，但会导致延时，进而导致超时重发。需要由上层来实现

这一层有network_send和network_handle，后者可能处理，也可能转发

路由有很多网口，实现了跨子网之间的访问，其中路由表记录了子网和网口的对应关系，而路由器与路由器之间的路由表会进行合并，从而进行多个子网之间的通信

control-plane控制了数据的流动，如随时更新路由表或确定路由算法，重点在于正确性；data-plane则用于快速查表，重点在于性能

路由器往往有两个硬件，即CPU和NPU，前者用于处理control-plane，后者用于快速实现data-plane，如使用大的cache

routing

路由的目标为能找到任意起点和终点之间的路径，且这条路径是最快的（时间上的，金钱上的）

难点在于分布式路由的实现，分为三步：

• HELLO protocol: 节点向邻居打招呼，获得邻居的信息
• advertisements: 获得可达节点的信息
• minimum-cost: 根据已知路由确定最小成本路由

两种类型的routing protocol:

• link-state: 一个节点的advertisement包括它的邻居和到达这些邻居的成本，通过泛洪(flooding)将到达邻居的成本发给所有节点，最后通过Dijkstra最短路径算法进行整合
• distance-vector: 只给邻居告诉它已知的所有节点的成本，使用Bellman-Ford算法进行整合

注意到link-state的路由只记录其选择的邻居，而不是完整的路径

link-state的容错性好且收敛快，但缺点在于网络建立初期，flooding的网络开销极大，因此只适用于规模较小的自组织网络

相较于link-state在flooding时发送的都是同一信息，distance-vector的邻居节点消化完信息后，会发送新的认知信息，从而让原来的节点更新自己的路由表，并再次发送认知信息（可能停不下来，即持续更新）

distance-vector不能一开始就得到最优解，其容错性要差些，因此failure handling是其缺点，如problem of INFINITY

因此advertisement里面不应当包含A->B的路径

distance-vector的优点在于低开销，缺点在于收敛时间长且与路径长度有关，还有infinity问题，因此也只适用于小型网络

scale the routing

三种扩大规模的方法：

• hierarchy of routing: 即划分region，将多个节点抽象成一个点
• path-vector routing: advertisement将包含完整的path信息
• topological addressing: 将多个地址合并在一起，使路由表变小，如18.0.0.0到18.0.0.255的所有地址压缩成18.0.0.0/24，即前24位都相同

而跨region应当使用BGP，是一种path-vector protocol

path-vector将整个path记录下来，有助于检查有无环，防止出现INFINITY问题，还能顺便进行access policy，即检查不能去的节点，最后扩大了规模，收敛时间下降。缺点在于advertisement变大

当graph变化时，即某个节点go down，path-vector只需要检查path里面有没有这个节点，修改受到影响的节点即可

特性	内部网关协议（IGP）	外部网关协议（EGP）
范围	自治系统（AS）内部	自治系统（AS）之间
主要目标	找到最佳路径；快速收敛	应用路由策略；控制路径传播
典型协议	OSPF、IS-IS、RIP、EIGRP	BGP（当前唯一使用的 EGP）
关注点	速度、效率、网络拓扑	策略、可达性、AS 路径
规模	管理数百到数千条路由	管理全球互联网（数十万条路由）