交换与路由
多点到多点通信要解决两个不同层次的问题：交换负责节点内部从哪一个入口转到哪一个出口，追求快速；路由负责在全网拓扑中为源和目的选择路径，追求合适的路。
交换方式
电路交换在传输前先建立一条端到端专用电路。建立完成后时延小而稳定，中间节点不必存储、分析数据，能够透明传输；但呼叫建立过程较长，空闲时资源仍被独占，利用率不高，而且两端要采用相同的协议、格式和同步方式。
报文交换以完整报文为单位存储转发，不预先建立固定电路。链路可以被多条业务共享，也能在不同类型终端之间转换，但节点要等待整个报文到齐，缓存和时延都很大。
分组交换把报文切成长度较短、格式统一的分组，再逐跳存储转发。分组可以动态统计复用链路，适合突发数据，时延也比整份报文存储转发更小；代价是每个分组都带有附加信息，长报文需要合理分组，而且交换机要随时分析和处理分组。
交换单元
空分交换单元用空间上不同的交叉连接把输入接到输出。一个\(M\)入、\(N\)出的单级交叉开关需要\(MN\)个交叉点，结构直观但规模增长很快。以\(MN\)入、\(MN\)出的交换网络为例，单级实现需要\((MN)^2\)个开关；若第一级使用\(M\)个\(N\times N\)单元，第二级使用\(N\)个\(M\times M\)单元，则开关数降为
多级Clos网络正是用较小的交换单元级联来降低开关数，代价是控制更复杂，而且可能因内部出线竞争而阻塞。
时分交换单元把各输入数据先写入共享存储器，再按输出次序读出，本质上利用统计时分复用。交换结构通常由线路卡、交换网络和处理器组成：数据平面完成查表和高速转发，控制平面维护路由与交换状态。
路由模型与目标
把网络表示为带权图\(G=(V,E)\)，节点是路由器，边是链路，\(c(x,y)\)表示链路代价。代价可以取跳数、时延、拥塞程度或管理员配置的权重。路由算法要在效率、计算复杂度、稳定性、收敛速度和多路径能力之间折中。
生成树连接全部节点且没有环，任意两点之间只有一条路径，结构简单并适合广播；但它不会充分利用所有链路。最短路径则为每个源节点建立一棵最短路径树，使路径代价和最小：
路由算法给出计算规则，路由协议则规定各节点怎样交换信息并分布式地实现算法。
左图对比单级交叉开关和两级结构：分级后开关数由\((MN)^2\)降为\(MN(M+N)\)，但要接受更复杂的控制和内部阻塞。右图沿用课件的带权拓扑，彩色边是从\(u\)出发得到的最短路径树，节点旁的\(d\)给出累计路径代价。
生成树协议
生成树包含全部节点，任意两点之间只有一条路径，因而结构简单、没有环路并且便于广播；代价是部分链路不能被利用。生成树协议先选择ID最小的节点作为根，再让各节点寻找跳数最少的到根路径。节点通告可概括成三元组
节点不断向邻居广播自己认定的根和到根距离。收到更小的根ID时改认新根；根相同时，选择距离加一后更短的邻居路径。三元组的最后一项标明通告来自哪个节点。反复更新直至全网形成一棵无环生成树。
距离矢量路由
距离矢量算法只要求节点与邻居交换路由表。若\(x\)的邻居集合为\(N(x)\)，Bellman-Ford更新式为
节点周期性广播自己到所有目的节点的距离，根据邻居通告更新最小距离和下一跳。它所需局部信息少，实现简单，但坏消息逐站传播较慢；链路失效后，邻居之间可能互相把对方当成可达路径，形成路由环和“计数到无穷”问题。
RIP是典型距离矢量协议，以跳数为度量，每30秒通过UDP向邻居发送一次完整路由表，并把最大有效距离限制为15跳；16跳视为不可达，这也限制了计数到无穷的时间和网络规模。
链路状态路由
链路状态方法让每个节点生成描述直连链路的链路状态分组（LSP），通过洪泛把它无修改地传播到全网。各路由器因此得到相同的拓扑图，再独立运行Dijkstra算法。
以源节点\(u\)为例，令\(S\)为已经确定最短距离的节点集合，\(D(v)\)为当前暂定距离。初始化时，直连邻居的暂定距离取链路代价，非邻居取无穷大：
每轮选择\(S\)外\(D(w)\)最小的节点\(w\)加入\(S\)，再松弛它的相邻节点：
直到所有可达节点进入\(S\)，便得到以\(u\)为根的最短路径树和路由表。链路状态法收敛快、全局一致性好，但要存储拓扑并承担LSP洪泛和最短路计算开销。实际网络会降低不必要的刷新频率，用多播代替全网广播，并用时间戳、序列号以及分层分区来协调LSP刷新。
OSPF是典型链路状态协议。路由器把直连链路状态直接封装在IP中，而不是经TCP或UDP传送，并把变化洪泛到自治系统内的其他路由器。各路由器建立共同的拓扑数据库，再用Dijkstra算法计算转发表。OSPF还支持身份验证、多条等代价路径，以及自治系统内的分层区域结构。
距离矢量与链路状态的根本差异在于信息范围：前者只和邻居交换完整路由表，逐步学习距离；后者把链路状态变化传播到全网，各节点再本地计算。RIP算法简单、适合小规模网络，但周期刷新使收敛较慢；OSPF需要更多CPU、内存和洪泛开销，但采用触发式刷新，对拓扑变化反应更快。