分析 *链路代价是一个小整数,域内路由算法适 用的网络直径也不大,因此路径代价也是 个小整数 *小整数排序是否有高效的数据结构? *小规模问题采用特殊的数据结构(P14) *桶排序对于小整数比较有效,构造一个基于桶 排序的优先级队列
分析 链路代价是一个小整数，域内路由算法适 用的网络直径也不大，因此路径代价也是 一个小整数 小整数排序是否有高效的数据结构？ 小规模问题采用特殊的数据结构（P14）： 桶排序对于小整数比较有效，构造一个基于桶 排序的优先级队列
解决方案 *假定链路最大代价为 MaxLink Cost,网络直径为Dam,用 个长度为Dam* MaxLinkCost的数组C存放从0到 ( Diam *Max Cost1)所有可能的代价 若节点X的代价为p,将X存放在元素C[p]指向的链表中 *当节点X的代价从p变为p',将节点X从C[p指向的链表移入 Cp’指向的链表 CurrentMin Costs-- Diam· MaxLink Cost 5 BA D FIGURE 4.6 Using a priority queue based on bucket sorting to speed up Dijkstra,s algorithm
解决方案 假定链路最大代价为MaxLinkCost，网络直径为Diam，用 一个长度为Diam*MaxLinkCost的数组C存放从0到 (Diam*MaxLinkCost-1) 所有可能的代价 若节点X的代价为p，将X存放在元素C[p]指向的链表中 当节点X的代价从p变为p’，将节点X从C[p]指向的链表移入 C[p’]指向的链表
计算过程 初始化指针 CurrentMin为0(对应源节点S的代价) 在每一次迭代中, * Currentmin加1,直至到达一个非空桶,将该桶所指列表中 的所有节点加入最小路径树 *更新剩余节点的代价,移动这些节点到相应的桶中 *重复上一步,直至所有节点都加入到最小路径树中 *算法复杂度:ON+ Diam *MaxLink Cost),远低于ON|ogN) CurrentMin Costs --> Diam * MaxLink Cost Pick D next B A D FIGURE 4.6 Using a priority queue based on bucket sorting to speed up Dijkstra's algorithm
计算过程 初始化指针CurrentMin为0（对应源节点S的代价） 在每一次迭代中， CurrentMin加1，直至到达一个非空桶，将该桶所指列表中 的所有节点加入最小路径树 更新剩余节点的代价，移动这些节点到相应的桶中 重复上一步，直至所有节点都加入到最小路径树中 算法复杂度：O(N+Diam*MaxLinkCost)，远低于O(NlogN)
思考 *为什么采用桶排序优先级队列比较高效? *在 Dijstra算法中,所有节点按照代价从小到大 的顺序加入最小路径树 *下一个最小代价节点总是在 Currentmin之前, CurrentMin只需从当前位置往前走,而不需要 从第一个位置开始扫描 *进一步的改进: *在图示的例子中,如何在添加了节点C之后使 算法终止,而不是一直扫描到数组结束?
思考 为什么采用桶排序优先级队列比较高效？ 在Dijstra算法中，所有节点按照代价从小到大 的顺序加入最小路径树 下一个最小代价节点总是在CurrentMin之前， CurrentMin只需从当前位置往前走，而不需要 从第一个位置开始扫描 进一步的改进： 在图示的例子中，如何在添加了节点C之后使 算法终止，而不是一直扫描到数组结束？
4.4使用网桥硬件的以太网监视器 *将网桥改造成以太网流量监视器,统计每一对活跃节点A 与B之间的流量PAB *为每一对活跃节点A、B维护一个变量PA,每当监听到一个数据包 从A发往B,PA加1 *性能要求: *每个包的统计工作要在64微秒内完成,最耗时的操作是根据 <MACA,MACB>查找PAB 可以利用的硬件: *网桥有一个地址查找引擎,可查找与一个MAC地址相关联的状态 *查找引擎用 dlookup(XD)调用,X为48位的关键字,D为要查找的 数据库,返回与X相关联的状态 *如果数据库不超过64000个关键字,调用延迟为1.4微秒
4.4 使用网桥硬件的以太网监视器 将网桥改造成以太网流量监视器，统计每一对活跃节点A 与B之间的流量PA,B： 为每一对活跃节点A、B维护一个变量PA,B，每当监听到一个数据包 从A发往B，PA,B加1 性能要求： 每个包的统计工作要在64微秒内完成，最耗时的操作是根据 <MACA, MACB> 查找PA,B 可以利用的硬件： 网桥有一个地址查找引擎，可查找与一个MAC地址相关联的状态 查找引擎用lookup (X, D) 调用，X为48位的关键字，D为要查找的 数据库，返回与X相关联的状态 如果数据库不超过64000个关键字，调用延迟为1.4微秒