问题 *功能需求: *调度器每次从VC状态表中选择一个就绪的VC, 发送一个信元,并将其cred减1 *简单的方法: *调度器依次检查状态表,寻找一个就绪的VC *如果有许多未就绪的VC,顺序查找很低效 问题: *调度器如何避免检查未就绪的VC?
问题 功能需求： 调度器每次从VC状态表中选择一个就绪的VC， 发送一个信元，并将其credit减1 简单的方法： 调度器依次检查状态表，寻找一个就绪的VC 如果有许多未就绪的VC，顺序查找很低效 问题： 调度器如何避免检查未就绪的VC？
分析 *为避免检查未就绪的V,可将所有就绪的vC抽出 来组织在一起,供调度器查找 Head List of active VCs with credits FIGURE 4.4 Maintaining a list of eligible VCs to speed up the scheduler main loop
分析 为避免检查未就绪的VC，可将所有就绪的VC抽出 来组织在一起，供调度器查找
解决方案 *运用P12(增加额外的状态): *除VC状态表外,再维护一个就绪vC列表 *就绪VC表的维护: *每次从列表头部取一个VC服务(发送一个信元) *若VC在服务后变为不活跃(没有信元或cedt为 0),将其从列表中删除,否则添加到列表尾 部 *当一个VC从未就绪变为就绪时,将其添加到列 表尾部
解决方案 运用P12（增加额外的状态）： 除VC状态表外，再维护一个就绪VC列表 就绪VC表的维护： 每次从列表头部取一个VC服务（发送一个信元） 若VC在服务后变为不活跃（没有信元或credit为 0），将其从列表中删除，否则添加到列表尾 部 当一个VC从未就绪变为就绪时，将其添加到列 表尾部
43使用 Dijkstra算法计算路由 *在带权拓扑图上,计算从源节点到其它节点的最 小路径树,链路上的代价通常是一个小整数 *从源节点开始,每一轮迭代都从当前未包含在最 小路径树的节点中选择一个代价最小的加入树中 5 Q8○ Pick d ne 3,2⊙ Source FIGURE 4.5 In Dijkstra's algorithm, the source S builds a shortest-path tree rooted at S. At each stage. the closest node not in the tree is added to the tree
4.3 使用Dijkstra算法计算路由 在带权拓扑图上，计算从源节点到其它节点的最 小路径树，链路上的代价通常是一个小整数 从源节点开始，每一轮迭代都从当前未包含在最 小路径树的节点中选择一个代价最小的加入树中
问题 *算法的要求: *每一次迭代,都要在一个节点集合中寻找一个最小代 价节点,迭代次数等于网络中的节点个数N *在一个动态变化的集合中维护最小元素的标准数据结 构为一个优先级队列 *通用的方法: *通用的、性能最好的优先级队列(如堆),找到最小 单元的代价为o(ogN),整个运行时间为O(NogN) 问题 *如果N很大,如何加速路由的计算?
问题 算法的要求： 每一次迭代，都要在一个节点集合中寻找一个最小代 价节点，迭代次数等于网络中的节点个数N 在一个动态变化的集合中维护最小元素的标准数据结 构为一个优先级队列 通用的方法： 通用的、性能最好的优先级队列（如堆），找到最小 单元的代价为O(logN)，整个运行时间为O(NlogN)。 问题： 如果N很大，如何加速路由的计算？