第四讲：网络路由
给每次数据传输确定一个端到端的路径，通常是找到两点之间的最小代价路径，保存在路由器的转发表FIB中
基于分布式计算
网络模型用无向图表示，节点是网络设备（路由器），节点间链路是带权重的边，权重即链路开销，可以是延迟、拥塞程度、花销等等
目标是找到两点之间的最小代价转发路径
对于一个单一节点来说，到其他节点的最短路径会构成一个树
路由计算的方法包括集中式方法和分布式方法
集中式方法适用于小规模网络，集中收集拓扑信息，使用最短路径算法计算，并下发给各个节点
分布式方法适用范围更广，包括距离向量算法DV和链路状态算法LS
距离向量算法
基本思想是任何时刻节点都保存到目的节点的已知最优路径开销和下一跳节点，如果不可达则开销用∞表示
初始化只有到相邻节点的开销和下一跳信息
然后转发给邻居节点，邻居收到后计算对比选择更优的开销，并更新自己的路由转发表
本质上是一个分布式的bellman-ford最短路径算法
网络拓扑发生变化时节点检测到相邻链路带宽发生变化，更新自己的转发表并通知邻居
但是存在问题：节点开销增大时会造成更新一直迭代（因为都倾向于选小的，但是小的这时候已经不存在了，相当于选择保留了过时的信息）。开销增大的时候要过很久网络才能稳定下来，在这个过程中会存在路由环路。称为count-to-infinity
解决方法：水平分割和反向抑制
水平分割的方法是节点A不向节点B通告经过节点B的路径（告诉人家干啥啊……人家自己清楚的很），需要等待超时才能稳定（因为A没主动告诉人家B）
反向抑制的方法是节点A告诉节点B“我到C是不可达的，你不要试图经过我到C”（不需要等待超时，是主动告知的）
RIP
路由状态协议，最早的IP路由协议，特点是每一跳的开销都是1，最大跳数小于16
初始化是问邻居节点要当前的路由表副本，周期性是每30秒向邻居节点发自己的路由表副本，触发性是当自己的表发生变化的时候立即通告邻居
链路状态算法
基本思想是每个节点都获得整个网络的完整拓扑，各节点广播扩散拓扑关系，每个节点单独计算到其他节点的最短路径
获得完整网络拓扑的方法
创建链路状态LSP，包括该LSP的节点标识ID（标记这是谁的LSP），邻居节点和对应开销，还有序列号和生存周期
扩散的时候发给邻居，邻居收到以后，如果发现之前没有保存过这个ID的LSP，就存一份，如果之前存过但是新的序列号更大（更新），就存一份，然后更新，继续向外扩散，构成可靠泛洪
最短路径计算
dij算法，在未访问节点中选择离已访问节点最大的那个，最终生成的是一棵最短路径树
LS算法可能存在瞬时环路
RIP改进：OSPF
开放最短路径算法
链路开销可以自定义，比RIP收敛速度更快，适应范围更广
更大规模网络中
区域内每个节点单独计算，区域间节点只知道到其他区域的路由路径，先发到边界路由器再说，别的不管
所以区域间的路径可能不是最短路径（没事
距离向量DV和链路状态LS的对比
消息数目方面，DV是相邻节点之间交换信息，LS是所有节点之间都需要交换信息（可靠泛洪方式交换）
空间开销方面，DV只保存邻居节点，小；LS保存区域网内所有节点，大
收敛速度方面，DV慢，LS快
可扩展性方面，DV差，LS好
路由环路方面，DV会存在count-to-infinity路由环路；LS可能存在瞬时环路
路由协议方面，DV有RIP，BGP；LS有OSPF，IS-IS
域间路由
自治系统AS
单一实体管辖的路由器集合
内部使用内部网关协议和度量标准转发数据包，对外使用外部网关协议将数据包路由到其他AS
每个AS都有自己的标识
不能把域内路由协议直接应用到域间路由协议，因为域内的是性能为导向的，全网同一目标；域间的是策略为导向的，不同的AS目标不同
域间路由的难点：不同AS的度量指标不同，扩展性差，一个AS的错误配置可能导致下游好多AS故障
选距离向量的话，收敛慢，还会有路由环路
选链路状态的话，每个系统度量指标不一样，可能有环路，状态数据库太大，而且还会把自己的路由策略暴露给其他人
BGP边际网关协议
使用的是路径向量而不是距离向量，携带了整个路径的信息
AS在收到通告之后，检查自己在不在这个路径里头，如果在的话就直接扔了，如果不在再把自己加到路径里面，然后通告
这样避免形成环路，而且指标也不需要做全局统一
多连接AS可以：不帮别人转发、全帮别人转发、看情况帮一部分人转发不帮一部分人转发
路由消息交换可以使用TCP，简化了路由协议设计，不需要等着别人的确认，不需要定时更新，连接断开前一直有效，可以批量更新，但是链路负载很高的时候路由协议性能会受影响
路由更新消息包括撤销路由、路径属性、网络层可达信息，同一消息中通告的所有前缀都有相同的路径属性
内部BGP和外部BGP(iBGP和eBGP)
一个AS中的边界网关路由器之间建立连接，学习路由，称为iBGP，这个东西不能再通告其他节点（可能会引起路由环路）
不同AS中的边界网关路由器之间建立连接，学习路由，成为eBGP，这个东西可以通告给其他节点
总结
提供了分层的路由机制（AS内和AS间），有一定可扩展性，是策略决定的路由
路径向量机制（带路径的距离向量）可以快速检测环路，避免暴露自己的策略给其他AS
路由到移动主机
移动主机的ip经常变，但是服务器不知道，还是坚持把东西发到原来的ip，而ip协议假设了主机位置不变，我按照ip发过去了那就是收到了
但是移动用户希望能够不感知到在不同网络的切换，数据传输过程中也不更换ip地址（不然我啥也收不到了）
如果尝试通告新ip地址（告诉对方我变了，让他把数据发到新地址），但这样会有安全问题，攻击者可以冒充移动端发送通告，进行中间人攻击
IP地址的两个职责：标识符（标记我是谁）和定位符（怎么通过路由找到我）
解决方法：假设主机有一个永久的ip地址，称为本机地址，作为identifier，和移动前的网络有相同前缀；移动到新网络后获得一个新的Ip，作为locator，两个地址共存，locater负责接收数据，identifier负责解复用数据
构成
主要包括移动主机、本地代理、外地代理、转交地址和对端主机
移动主机：有一个分配的永久的ip地址，叫本地地址
本地代理：位于移动主机的本地网络，维护本地地址到转交地址的映射
外地代理：在本地代理和移动主机之间转发数据，周期性向外通告，提供转交地址
转交地址：标识移动主机的位置，通常是外地代理的地址，当移动主机加入时，由外地代理提供给本地代理
对端主机：服务器
发送过程
-
本地代理截取目标为移动主机的数据
数据肯定会先到本地代理所在的网络，本地代理模拟移动主机收取数据
-
本地代理把这些数据发给外地代理
本地代理使用转交地址将数据封装，发给外地代理，外地代理剥离封装的IP头，获取原始数据
-
外地代理把数据发给移动主机
外地代理查询原始数据的IP地址，通过MAC地址发送给移动主机
移动端加入过程
告诉外地代理我想加→外地代理向本地代理申请映射，本地代理说可→外地代理告诉移动主机说可→完成
移动主机注册信息
mobility binding table记录移动主机的本地地址和外地代理的转交地址，由本地代理维护；visitor list记录移动主机的本地地址、本地代理的地址、移动主机的MAC地址，由外地代理维护
存在的问题
**三角路由：**绕路问题，因为数据包都是对端主机→本地代理→外地代理→移动端 或 移动端→外地代理→本地代理→对端主机，但有时候移动主机到对端主机比到本地代理还近，绕路了。解决方法是由本地代理告知对端主机，移动端对应的转交地址，让对端主机和外地代理直接通信（跳过本地代理）。
**单点失效：**本地代理坏了就无了。解决方法是多HA机制
主机一直动，频繁向HA注册：解决方法是多个HA协同构成HA组
安全问题balabala
基于拓扑编址的路由机制（联系DCN）
因为编址必须基于拓扑结构，所以可扩展性好，但是拓扑不是静止不变的，所以地址不能永久标识主机身份
主要问题还是那个，IP地址混合了网络地址+主机标识，但主机移动之后IP会发生变化，但网络应用在连接过程中IP又不能变化
扁平化标识
扁平化名字：使用DHT分布式哈希表代替DNS，但还是需要使用基于层次化地址的路由
扁平化地址：避免将名字翻译成地址
ROFL
设计目标：基于扁平化标识的可扩展路由
设计思路：基于DHT/Chord路由，维护到后继节点、指取节点的源路由，使得不需要聚合就可以提供可扩展的网络路由
本质上是一个全局的扁平标识到节点的映射和查找
使用的技术手段：
一致性hash
把一组文件存储到N个节点上，考虑节点的离开和新节点的加入
使用大型稀疏标识空间（比如128位），构成环形：
把文件按名字均匀hash到标识空间，为object_id，把节点也均匀hash到标识空间，为node_id
对于object_id，顺时针遍历，遇到第一个node_id，就把它存到这个节点里
节点加入时后一个节点的内容移到新结点中，节点离开时里面存的东西往后移一个节点
Chord
只支持一种操作：给一个名字，查询独赢的存储节点
分布式、去中心化的名字到节点的查询服务，考虑了节点的离开和加入，能够快速对应名字和节点
可应用于扁平化路由、P2P文件存储定位
所有节点通过后继结点指针形成环形单链表，给定key值，从任一节点开始依次遍历查找节点是否存储key值，只能保证正确但不能保证效率，最坏情况下要找遍历所有N个节点
加速查找：所有节点维护一个指取表，从任一节点开始遍历，如果节点中存储相应key值就结束查找，否则在指取表中找包含对应object_id的区间，跳转到相应的后继节点查找
特性：可证明的正确性和性能，每个节点只需要维护到少数几个节点的路由信息，通过向其他节点发送消息进行迭代/递归查找，当节点加入或离开时更新路由信息
总结
基于扁平化标识而非层次化地址
利用chord技术实现可扩展性较好的路由机制
在新型网络传输范式中有较大优势
需要实现新的标识空间，难以直接替换现有IP架构
