Greedy pebbling for proof space compression

International Journal on Software Tools for Technology Transfer - Automated reasoning tools for the verification and synthesis of software often produce proofs to allow independent certification of...     

Two dynamic programming algorithms for which interpreted pebbling helps

We consider extensions of one-person and two-person pebble games that take into account the types of the gates of the circuits on which the games are played. A simple relationship is established between the extended games and the corresponding original games. This is useful in showing that the extended games allow more efficient pebbling than the original games on certain natural circuits for problems such as context-free language recognition and transitive closure of directed graphs.     

Bandwidth packing

We model a server that allocates varying amounts of bandwidth to “customers” during service. Customers could be computer jobs with demands for storage bandwidth or they could be calls with demands for transmission bandwidth on a network link. Service times are constants, each normalized to 1 time unit, and the system operates in discrete time, with packing (scheduling) decisions made only at integer times. Demands for bandwidths are for fractions of the total available and are limited to the discrete set {1/k, 2/k, …, 1} wherek is a given parameter. More than one customer can be served at a time, but the total bandwidth allocated to the customers in service must be at most the total available. Customers arrive ink flows and join a queue. Thejth flow has rate λ _j and contains just those customers with bandwidth demandsj/k. We study the performance of the two packing algorithms First Fit and Best Fit, both allocating bandwidth by a greedy rule, the first scanning the queue in arrival order and the second scanning the queue in decreasing order of bandwidth demand. We determine necessary and sufficient conditions for stability of the system under the two packing rules. The average total bandwidth demand of the arrivals in a time slot must be less than 1 for stability under any packing rule, i.e., the condition $$\rho {\text{ : = }}\sum\limits_i {\lambda i\left( {i/k} \right)} {\text{< 1}}$$ must hold. We prove that if the arrival rates λ₁, …, λ _k?1 are symmetric, i.e., λ _i =λ _k?i for alli, 1 ≤i ≤k ? 1, theρ<1 is also sufficient for stability under both rules. Our Best Fit result strengthens an earlier result confined to Poisson flows and equal rates λ₁=…=λ _{k ? 1}, and does so using a far simper proof. Our First Fit result is completely new. The work here extends earlier results on bandwidth packing in multimedia communication systems, on storage allocation in computer systems, and on message transmission along slotted communication channels. It is not surprising thatρ<1 is sufficient under Best Fit, since in a congested system, Best Fit tends to serve two complementary (matched) customers in each time slot, with bandwidth demands beingi/k and (k ? i)/k for somei, 1 ≤i ≤k ? 1. It is not so obvious, however, thatρ<1 is also sufficient under First Fit. Interestingly, when the system becomes congested, First Fit exhibits a “self-organizing” property whereby an ordering of the queue by time of arrival becomes approximately the same as an ordering by decreasing bandwidth demand.     

Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.     

基于RED的带宽分配算法

实现带宽资源的分配对于QoS控制来说是非常重要的。常见的带宽分配算法如WFQ、DRR等分组调度算法存在着诸如计算复杂度高、需在路由器进行每流状态的管理等不足。该文在前人的基础上,提出了一种基于RED的带宽分配算法,避免了上述问题,从而提高了算法的可扩展性。     

一种带宽和能量约束的QoS路由协议

现有服务质量(QoS)路由协议一旦选定源节点到目的节点的路径,满足要求的特定业务流将一直从这条路径上传送数据包,直到该路径断链。针对该问题,提出一种基于带宽和能量约束的QoS路由协议——BERP。该协议以典型的AODV协议为基础,修改了以带宽为指标的基于AODV的QoS路由协议的路由发现和维护机制。仿真结果证明,网络中节点的能量消耗比较均衡,延长了网络存活时间。     

BitTorrent带宽模型研究

对BitTorrent（BT）网络中的Peer行为进行了细致的分析,并建立了相关的文件片段模型、感兴趣与阻塞模型,对Peer对邻居Peer的感兴趣概率、被邻居Peer及Seed阻塞的概率以及选择上传Peer的概率进行了分析。利用这些模型及概率表达式,推导出BT的带宽模型。     

一种端到端可用带宽的测量方法

重点研究了网络端到端可用带宽的测量方法,分析了IGI和PTR算法的原理和局限性,将算法从单跳模式扩展到多跳网络,利用延时变更的概念,分析了探针包序列间隔变化与背罱流量的关系,以此估计背罱流量,并运用“相等区间”的方法确定最佳测量点,提高了可用带宽测量的准确性。     

Approximating the Bandwidth of Caterpillars

A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time . This result generalizes to trees, planar graphs, and any family of graphs with treewidth .     

带宽整合技术的研究与应用

通信网络中带宽整合的基本原理及其实现机制。分析了网络协议栈不同层带宽整合方案的应用价值。     

基于服务质量水平的带宽分层自适应

自适应服务质量技术能有效地适应随时间变化的网络环境.提出了基于服务质量水平max-mi n公平的带宽分层自适应模型.此模型建立在应用层和网络层自适应控制的机制上.网络层利 用资源探测协议来实现基于服务质量水平max-min公平的带宽分配,而应用层实现特定于应 用的自适应服务.     

一种基于多主体的网络带宽分配方案

本文介绍了一种基于多主体在多个用户和网络供应商之间进行自动并实时地进行交互协商达成带宽分配的方案。在此基础上，借鉴近年来对多主体间协作机制的研究，进一步提出了具体的设计方法以及实现的技术细节。最后，探讨了这一方案在应用上的适用特点和局限性。     

HSDPA,更高效地利用带宽

随着范围广泛的全新高速数据服务的不断涌现,人们对用户体验的更高追求导致了对更高带宽的需求,在移动通信领域更是如此。高速下行分组接入(HSDPA)技术是现有W-CDMA系统高成本效益的升级,可以提供媲美当今无线局域网的性能,同时拥有移动性和无所不在的覆盖能力所带来的额外优势     

Internet带宽分配的公平性研究

依据带宽分配的公平性原则可以实现网络资源的合理分配和利用，从而提高网络的服务质量。根据一广域网模型，介绍了带宽分配的最大－最小公平性和比例公平性，并采用效用函数方法设计了一种带宽分配的最优速率迭代算法。     

Bandwidth compression of noisy images

The effect of additive noise on Discrete Fourier Transform of pictorial data (2DFT) must be considered in several important problems such as filtering, enhancement and bandwidth compression. This paper investigates the statistical properties of the corrupted 2DFT coefficients, and the error involved in reconstruction when a subset of these coefficients is employed for the purpose. The latter being often the case, the present analysis provides a rational basis for frequency selection and filter specification. Application of an F-test quantifies the reliability of filtering or bandwidth compression.     

DiffServ网络的拥塞控制和带宽保证

该文对DiffServ网络的拥塞控制和带宽保证的机制进行了分析和综述,包括TCP拥塞控制机制和路由器缓冲管理算法RED及RIO。研究表明DiffServ网络的拥塞控制和带宽保证的影响因素包括RTT、TCP/UDP相互作用等,解决方案包括对TCP拥塞控制机制的改进和对路由器流量调节器的改进。     

多种网络带宽测量算法及其比较

网络环境的复杂性造成测量网络带宽面临巨大困难。文章对现有的网络带宽测量算法进行了分类介绍,并对各种算法优缺点从滤波算法、时间分辨率、对网络交通影响、隐藏瓶颈、链接的多通道识别、可用带宽测量、带宽变化适用性的角度进行了比较。     

Bandwidth Selection and Reconstruction Quality in Point-Based Surfaces

We investigate the influence of bandwidth selection in the reconstruction quality of point-based surfaces. While the problem has received relatively little attention in the literature, we show that appropriate selection plays a significant role in the quality of reconstructed surfaces. We show how to compute optimal bandwidths for one class of moving least-squares surfaces by formulating the polynomial fitting step as a kernel regression problem for both noiseless and noisy data. In the context of Levin's projection, we also discuss the implications of the two-step projection for bandwidth selection. We show experimental comparisons of our method, which outperforms heuristically chosen functions and weights previously proposed. We also show the influence of bandwidth on the reconstruction quality of different formulations of point-based surfaces. We provide, to the best of our knowledge, the first quantitative comparisons between different MLS surface formulations and their optimal bandwidths. Using these experiments, we investigate the choice of effective bandwidths for these alternative formulations. We conclude with a discussion of how to effectively compare the different MLS formulations in the literature.     

复合流式媒体的同步与带宽自适应的研究

提出了一种在客户端进行同步控制的方案，采用基于流内同步的流间同步方法，可以实现多个流媒体的同步播放，并且能够对信道带宽变化作出反应，根据多个流媒体之间的优先级关系自动调整各个流媒体的比特率，保证整体播放质量。