对一种快速双重指数模算法的复杂度研究

最近提出了一种采用标准符号数二进制码(canonic signed-digit binary representation,CSDBR)来计算AXBY(modN)的快速双重指数模算法.该算法声明当指数的长度为k时,该算法平均仅需要1.306k次模乘.由于已知的此类算法至少需要1.503k次模乘,该算法具有明显的性能优势.然而,无论是该算法的提出者还是其他研究者均没有给出正确的复杂度分析.本文通过利用马尔科夫链模型对该算法进行正式的复杂度研究并进行一定规模的统计实验后证实,实际上该算法平均需要1.556k次模乘.这项研究的意义在于揭示到目前为止,基于标准符号数位码的双重指数模算法的最高性能仍然无法降低到1.5k次模乘以下.     

无线自组网中多速率敏感单播路由

针对多速率环境下按需路由协议,提出了基于延迟转发路由请求包的多速率敏感单播路由协议BDRMAU.其基本思想是中间节点根据路由请求包的发送者和本节点之间链路的传输速率,优先调度来自高传输速率链路发出的路由请求包来执行转发动作,因此,候选路由尽可能多地包含高传输速率链路,通过充分利用物理层多速率能力来提高网络吞吐量.模拟实验表明,BDRMAU较传统的协议能够较大地提高了网络吞吐量.     

基于网络编码的P2P内容分发性能分析

基于网络编码(network coding,NC)的网络通信,其中间节点首先对来自源节点的信包进行编码,然后再转发,目标节点通过反编码得到源节点的原始信息.大量的理论结果表明,网络编码可以提高整个网络的吞吐量和稳定性.为了研究网络编码在P2P(peer to peer)网络中的优越性,设计并实现了一个基于稀疏线性编码技术的P2P内容分发系统.实验结果表明,基于网络编码的系统在平均下载时间、总分发时间、整体吞吐量等几个方面都优于无编码的内容分发系统.     

有通信冲突的异构系统上的任务调度

在新的系统模型上，提出了一个任务调度算法．该系统模型考虑了通信冲突，即在任何时刻，一个处理器只能接收一条消息，发送一条消息．新的算法包括异构系统中任务优先级的高效排序和基于任务复制的处理器分配两部分．随机产生的任务图和一个具体应用的任务图进行调度试验的结果表明，该算法比已有调度算法的性能有了显著的提高．     

802.11多速率无线局域网中的竞争窗口控制算法

针对此类网络的饱和吞吐量模型,分析了速率调整无法降低帧冲突的原因以及发送节点的尝试发送帧概率对网络性能的影响.基于发送节点的尝试发送帧概率和竞争窗口大小之间的关系,提出了一个802.11多速率无线局域网中控制竞争窗口的方法,该方法通过估计局域网中的平均连续空闲时隙数来控制竞争窗口,因此能够主动减少由于节点数量大造成的帧冲突,从而提高网络性能.模拟实验表明,在802.11多速率无线局域网中,竞争窗口控制算法的引入可以在已有的速率调整算法的基础上使网络性能大大提高,获得更好的吞吐量和公平性.     

k-集合链域交的森林表示及求解

k个集合S1,S2 ,… ,Sk的链域交是由所有满足以下条件的k元组 (s1,s2 ,… ,sk)组成的集合 :e( 1)i si-si 1 e( 2 )i ,其中sk ∈Sk,si ∈Si,0 e( 1)i e( 2 )i 是常数( 1 i k - 1 ) .已知的求链域交的算法采用k元组表示k集合的链域交 ,其最坏情况时间复杂度为Ω(k∏ki=1ni) ,其中ni=｜Si｜ ,1 i k .本文采用森林表示k集合的链域交 ,并基于这种表示方法提出了一个求链域交的串行算法 .该算法的最坏情况时间复杂度为Ω( ∑k-1i=1nini 1) ,极大地改进了已知的结果 .     

未知网络中可分负载的分布式调度

针对未知网络参数的异构网络系统,提出了一个基于探测技术的多阶段负载调度策略.该策略首先将整个负载分成一些子负载,每个阶段将一个子负载分配给各个处理器.在不知道网络性能参数或网络性能随时间动态变化的情况下,从子负载中分出一小部分负载作为探测片段来探测网络的当前性能参数,作为调度的基础.实验结果表明,该算法的优越性明显.在同样的调度时间复杂度下,其调度结果较已有算法最好时可以缩短调度时间超过20%,平均缩短调度时间约15%.     

TCP在数据包随机延迟网络中的性能分析

TCP数据包在网络传输中发生错误有两种形式:丢包与延迟.已有的成果大多只对TCP在丢包网络中的性能进行了建模,缺少对TCP在随机延迟网络中的建模问题的研究,为此提出了一个TCP在随机延迟网络中的性能分析模型.首先给出并证明了判断数据包流是否为正序的充要条件;然后利用该条件得出数据包流正序出现的概率;最后根据模型分析了TCP在随机延迟网络中的性能.实验结果表明,所得出的数据包流在发生随机延迟后正序的概率与实验网络基本吻合,所提出的模型与不考虑延迟的模型相比,对TCP最大拥塞窗口均值的预测误差降低了43%,对其网络吞吐量性能的预测误差降低47%.