文档介绍：延迟界限分析的轨迹方法The Trajectory Approach
Opt. Lecture 03
1
提纲
概述
轨迹法初探
参数定义
基本算法(所有节点都是FIFO调度)
轨迹法的简单应用
2
概述
轨迹法(Trajectory Approach)
用来计算分布式系统中端到端响应时间的确定性上界
用来计算网络化分布式系统中端到端通信的确定性上界
考虑偶发的数据流
但并不假设相应的到达曲线
3
概述(续)——网络演算 . 轨迹法
网络演算
网络演算是一种“整体性”(holistic)方法,每个节点上的最坏情况场景,考虑了流在前一个节点上造成的最大可能的抖动
用包络代替确切的到达曲线和服务曲线(缺点)
轨迹法
也是最坏情况分析,研究数据包在它的“轨迹”(各个节点所处的忙时间段)上经历的最坏场景
任意排队规则和到达规则
4
概述(续)
轨迹法的基本思想
对于流ti,流上的数据包m,计算在最后一个节点q的最晚开始时间Wi,tq
逆着m对节点访问的次序回溯,每次(在每个节点上)都识别忙时间段,以及忙时间段开始时的数据包,以这些数据包起始的忙时间段是最终可能影响m的延迟的因素。
强调:轨迹法也是一种最坏情况下的分析
当流的数目增加,保守性逐渐显现…(奇怪?)
5
轨迹法初探——参数定义
流量模型
流 ti ,i∈[1,n];流的固定路径 Pi (以节点顺序组成)
设流为偶发到达,每个流具有参数
Ti (最小到达间隔), Ji 抖动, Di相对截止期限
Cih (在节点h上的处理时间)
注:图片粘贴自参考文献[Martin 2006]
6
轨迹法初探——参数定义
路径模型
考虑ti受到其它流量tj的“干扰”
设如果且,则从Pi上任意节点离开的流量tj不会在返回该路径
复杂的参数记号
每个节点上的忙时间段的最前面的一个数据包f(h)
slowi,在路径Pi上被流ti访问的最慢的节点,即:
子路径上的节点
slowj,i ,在子路径Pj,i上,
7
轨迹法初探——FIFO调度基本算法
计算数据包m在节点q的最晚开始时间(the latest starting time)
节点q
q -1
节点1
m
m
m
t
8
轨迹法初探——FIFO调度基本算法
识别m在节点q处理的“忙时间段”(busy period)bpq,f(q)从节点q-1来的忙时间段的第一个数据包
节点q
q -1
节点1
m
m
m
t
f(q)
bpq
f(q)一定是从q-1来吗?从节点q上,仍然可能有多路复用输入!
这只是示教的例子,复杂情况还要定义p(q-1) ……
9
轨迹法初探——FIFO调度基本算法
f(q)在节点q-1上所在忙周期开始于f(q-1);
继续回溯,直到节点1。
节点q
q -1
节点1
m
m
m
t
f(q)
bpq
f(q)
f(q-1)
10