第四章原则的运用

第四章原则的运用内容摘要：

某种方法计算出 f(a)，插入 a, f(a) 分析（续）  本例的包过滤问题：  计算与数据包 P关联的一组接收节点， P用三元组 源地址，源端口，目的端口 进行刻画  本例中， a=源地址，源端口，目的端口 ， f(a)=一组接收节点  更一般地， a可能包含 包头中的任何域  缓存多个包头域的时空开销很大：  关键字 很 宽， cache查找的时间开销 很 大  空间开销大， cache命中率低 分析（续）  能否仅缓存 1～ 2个唯一指示数据包 P 的包头域，而不是大量的包头域。  IPv6报头中有流标签域； IPv4中没有，但有一个 ToS域（可自定义）  流标识是全局的还是本地的。  为避免全局命名的标准化过程，最好使用本地命名的标识符 解决方案  源节点为每个流分配一个本地标识符，用 源节点，流标识符 二元组作为查找关键字。  源节点的应用程序向路由层请求一个流标识符，该应用发送的所有数据包都加上该流标识符（如放在 IPv4包头的 ToS域）。 解决方案（续）  应用数据包第一次到达路由器时：  路由器使用包头中的多个域对所有过滤器执行一个（较慢的）线性查找，确定一组接收节点  路由器将 源节点，流标识符 作为查找关键字，缓存与一组接收节点的映射关系  后续数据包到达时 :  路由器用 源节点，流标识符 查找缓存，获得一组接收节点 避免链路状态分组的分片  在使用链路状态路由时，  路由器必须 定期 发送一个包含所有邻居节点的链路状态分组（ LSP） ， LSP采用扩散法传输。  路由器使用分组 序号识别重复 及过时 的 LSP，并只使用最新的链路状态计算最小代价路由。  路由器可能有大量直接连接的主机邻居，使得 LSP远远超过大多数常见链路的 MTU。 （ 假定每个端节点使用 8个字节 ： 6个字节标识端节点， 2个字节表示代价） LSP分片传输的问题  如果对 LSP进行分片，存在以下问题：  每一跳传输 都要进行 LSP的分 片 和重组， 极大地增加了LSP的处理时间 和 传输时间。  无法 独立传输每个分片 ： 每个 LSP具有唯一的序号 ，如果 分片使用相同的序号， 则 后到的分片 会 被丢弃 ；如果使用不同的序号，序号大的分片会淘汰序号小的分片。  原因： 同一个路由器发布的同一时刻的链路状态必须放在同一个 LSP中传输。 问题  所有主机的信息必须放在同一个 LSP中传输吗。  如果不是， 能否 由 源 路由器 将 主机 信息分片， 分别 封装 成 独立的 LSP传输 ，以避免传输过程中分片。 （在空间上移动计算 P3c）  如果能够这么做，路由器 如何 识别 哪些 LSP分片属于同一个原始 LSP。 解决方案  修改链路状态路由协议 ：  允许任何一个路由器 拥有 多个伪路由器 ；  端节点集合在伪路由器间划分，每个伪路由器的 LSP可放 入 一个链路层帧中。 解决方案（续）  伪路由器概念 的实现：  令 每个 LSP携带一个 7字节的 ID（ 6字节路由器 ID + 1字节伪路由器 ID）  伪路由器 ID由拥有该伪路由器的实际路由器分配  具有相同路由器 ID（前 6个字节 ）的 LSP被 认为来 自同一个路由器  具有相同路由器 ID和序号的 LSP，其包含的链路状态信息是同一时刻由同一个路由器发布的 监督流量模式  为防止网络瞬间超载，有些协议限制应用的最大突发流量。 比如，在任何一个 T秒间隔内，源节点发送的数据量不能超过 B比特。  网络应当 有 监督 应用 流量 的措施 ，以抓住那些不遵守约定的应用。  假定路由器可以通过分类器将数据包划归到一个流， 路由器如何发现违约的流。 分析  简单的方法：  路由器使用一个周期为 T的定时器和一个计数器，在每个 测量 周期结束时，如果计 数 值超过 B，路由器就检测到一个违约 的流。  存在问题： 定时器只能监视某些时间段。  观察事实：  由于违约流可能在任何时刻启动，因此， 无论使用多少个定时器和计数器，都不能保证抓住所有的违约流。 分析（续）  能否只用一个定时器来抓住违约的流。 分析（续）  能否只用一个定时器来抓住违约的流。  一定要在 间隔 固定的时间 点上 启动 测量 过程吗。 分析（续）  能否只用一个定时器来抓住违约的流。  一定要在 间隔 固定的时间 点上 启动 测量 过程吗。  利用自由度（ P13） ：测量过程 不需要 在 固定 的时间点上启动 ，在连续的两个 测量 周期之间 允许 有空隙。 分析（续）  能否只用一个定时器来抓住违约的流。  一定要在 间隔 固定的时间 点上 启动 测量 过程吗。  利用自由度（ P13） ：测量过程 不需要 在 固定 的时间点上启动 ，在连续的两个 测量 周期之间 允许 有空隙。  如何选择测量周期之间的空隙。 分析（续）  能否只用一个定时器来抓住违约的流。  一定要在 间隔 固定的时间 点上 启动 测量 过程吗。  利用自由度（ P13） ：测量过程 不需要 在 固定 的时间点上启动 ，在连续的两个 测量 周期之间 允许 有空隙。  如何选择测量周期之间的空隙：考虑使用随机化方法（ P3a）。 解决方案  路由器使用一个 周期为 T 的 定时器和一个计数器。  在一个 监视 周期结束后， 若 计数器超过 B，抓到一个违约流。 此时， 设置一个标志，为定时器设置 [0, T]之间的一个随机数，启动定时器 ，插入一段空隙。  定时器超时后，清除标志和计数器，定时器复位 到 T，开始下一个监视周期。 找出资源使用大户  设备希望有一种简单的方法找到资源使用大户  最简单的方法是使用一个堆，但如果用户数量很大，在高速网络中不可接受  如果资源使用数量的数值很大，桶排序也不适用  假定不要。