检索结果-内蒙古大学图书馆

30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Patt-Shamir, Boaz Teplitsky, Marat Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

ISBN: (纸本)9781450307192

We consider the model of fully connected networks, where in each round each node can send an O(log n)-bit message to each other node (this is the CONGEST model with diameter 1). It is known that in this model, min-weight spanning trees can be found in O(log log n) rounds. In this paper we show that distributed sorting, where each node has at most n items, can be done in time O(log log n) as well. It is also shown that selection can be done in O(1) time. (Using a concurrent result by Lenzen and Wattenhofer, the complexity of sorting is further reduced to constant.) Our algorithms are randomized, and the stated complexity bounds hold with high probability.

关键词： network algorithms communication complexity distributed sorting CONGEST model

来源：评论

学校读者我要写书评

暂无评论

Guest editorial

引用

Journal of Communications 2011年第9期6卷 657-659页

作者： Zhai, Fan Matta, Ibrahim Rouskas, George Texas Instruments United States Boston University United States North Carolina State University United States

来源：评论

学校读者我要写书评

暂无评论

Dynamic computations in ever-changing networks 11

Dynamic computations in ever-changing networks

引用

Proceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems

作者： Idit Keidar Technion Haifa Israel

ISBN: (纸本)9781450309462

This talk focuses on dynamic computations (sometimes called live, on-going, continuous, or stabilizing), which continuously adapt their output to reflect input and network topology changes. Three specific examples are discussed: continuous weighted matching, live monitoring, and peer sampling (also called gossip-based membership). Such computations are of interest in ever-changing networks, where the network topology itself (nodes and links) constantly changes, as do the inputs to the computation, e.g., sensor reads. Everchanging networks occur in many settings nowadays, including ad-hoc, vehicular, and sensor networks, social networks, and clouds spanning multiple data-centers.

关键词： average aggregation network algorithms dynamic systems peer sampling weighted matching group membership

来源：评论

学校读者我要写书评

暂无评论

About Minimum Cost Flow Problem in networks with Node Capacities

About Minimum Cost Flow Problem in Networks with Node Capaci...

引用

13th WSEAS International Conference on Computers

作者： Ciupala, Laura Univ Transilvania Brasov Dept Comp Sci Iuliu Maniu St 50 Brasov Romania

In this paper, we describe and solve the problem of establishing a minimum cost flow in networks with node capacities. We show that this problem, which has several applications, can be reduced to a standard minimum co... 详细信息

ISBN: (纸本)9789604740994

关键词： network flow network algorithms Minimum cost flow problem

来源：评论

学校读者我要写书评

暂无评论

Why Locally-Fair Maximal Flows in Client-Server networks Perform Well

Why Locally-Fair Maximal Flows in Client-Server Networks Per...

引用

15th Annual International Conference on Computing and Combinatorics (COCOON 2009)

作者： Berman, Kenneth A. Yoshikawa, Chad Univ Cincinnati Dept Comp Sci Cincinnati OH 45221 USA

ISBN: (纸本)9783642028816

Maximal flows reach at least a 1/2 approximation of the maximum flow in client-server networks. By adding only I additional time round to any distributed maximal flow algorithm we show how this 1/2-approximation can be improved on bounded-degree networks. We call these modified maximal flows 'locally fair' since there is a measure of fairness prescribed to each client and server in the network. Let N = (U, V, E, b) represent a client-server network with clients U, servers V, network links E, and node capacities b, where we assume that each capacity is at least one unit. Let d(u) denote the b-weighted degree of any node u is an element of U boolean OR V, Delta = max{d(u)vertical bar u is an element of U} and delta = min{d(v)vertical bar v is an element of V}. We show that a locally-fair maximal flow f achieves an approximation to the maximum flow of min{1, Delta(2)-delta/2 Delta(2)-delta Delta-Delta} and this result is sharp for any given integers delta and Delta. This results are of practical importance since local-fairness loosely models the steady-state behavior of TCP/IP and these types of degree-bounds often occur naturally (or are easy to enforce) in real client-server systems.

关键词： Distributed Flow algorithms Oblivious Routing network algorithms Maximal Flow

来源：评论

学校读者我要写书评

暂无评论

Ternary CAM power and delay model: Extensions and uses

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2008年第5期16卷 554-564页

作者： Agrawal, Banit Sherwood, Timothy Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

Applications in computer networks often require high throughput access to large data structures for lookup and classification. While advanced algorithms exist to speed these search primitives on network processors and even custom application-specific integrated circuits (ASICs), achieving tight bounds on worst case performance with standard memories often requires a very careful analysis of all possible access patterns. An alternative, and often times more simple solution, is possible if a ternary CAM (TCAM) is used to perform a fully parallel search across the entire data set. Unfortunately, this parallelism means that large portions of the chip are switching during each cycle, causing large amounts of power to be consumed. While researchers at all levels of design (from algorithms to circuits) have begun to explore new ways of managing the power consumption, quantifying design alternatives is difficult due to a lack of available models. In this paper, we examine the structure of a modern TCAM and present a simple, yet accurate, power and delay model. We present techniques to estimate the dynamic power consumption and leakage power of a TCAM structure and validate the model using a combination of industrial TCAM datasheets and prior published works. Such a model is a critical first step in bridging the intellectual divide between circuit-level and algorithm-level optimizations. To demonstrate the utility of our model, we present an extensive analysis of the model by varying various architectural parameters and describe how our model can be easily extended to handle several circuit optimizations in the TCAM structure. In addition, we present a comparative study of SRAM and TCAM energy consumption to directly quantify the many design options which will be very useful for network designers to explore various power management schemes.

关键词： content addressable memory (CAM) delay dynamic leakage model network algorithms power router SRAM ternary CAM (TCAM)

来源：评论

学校读者我要写书评

暂无评论

About preflow algorithms for the minimum flow problem

引用

WSEAS Transactions on Computer Research 2008年第1期3卷 35-42页

作者： Ciupala, Laura Ciurea, Eleonor Department of Computer Science University Transilvania of Brasov Iuliu Maniu Street 50 Brasov Romania

In this paper, we describe the highest-label preflow algorithm for minimum flow. This algorithm is a special implementation of the generic preflow algorithm developed by Ciurea and Ciupala in [8], obtained by imposing in the generic preflow algorithm the rule that the algorithm must always select an active node with the highest distance label. Our new algorithm runs in O(n 2m1/2) time, which is substantially better than the running time of the generic preflow algorithm, that is O(n2m). Moreover, the highest-label preflow algorithm is the fastest polynomial algorithm for minimum flow problem.

关键词： Minimum flow problem network algorithms network flow Scaling technique

来源：评论

学校读者我要写书评

暂无评论

Time geography for ad-hoc shared-ride trip planning in mobile geosensor networks

引用

ISPRS JOURNAL OF PHOTOGRAMMETRY AND REMOTE SENSING 2007年第5期62卷 366-381页

作者： Raubal, Martin Winter, Stephan Tessmann, Sven Gaisbauer, Christian Univ Calif Santa Barbara Dept Geog Santa Barbara CA 93106 USA Univ Melbourne Dept Geomat Melbourne Vic 3010 Australia Univ Munster Inst Geoinformat D-48149 Munster Germany DLR DFD D-82234 Wessling Germany

Ad-hoc shared-ride trip planning in an urban environment is a complex task within a non-deterministic transportation network. Mobile geosensor networks provide the technical environment for realizing ad-hoc shared-ride trip planning: network nodes are autonomous agents that interact locally by ad-hoc short-range communication and arrange for shared rides. In a mobile geosensor network, communication costs are critical because of constraints regarding bandwidth, available energy, and memory. This paper introduces spatio-temporal concepts from time geography, which can be employed during the planning process to significantly reduce communication costs. We will integrate network-based algorithms and different wayfinding strategies to assist both shared-ride clients and hosts in finding optimal travel assignments. Multi-agent geosimulation in a real street network is used to demonstrate the applicability of the approach and quantitatively confirm the theoretically foreseen reduction in communication costs. (C) 2007 International Society for Photogrammetry and Remote Sensing, Inc. (ISPRS). Published by Elsevier B.V. All rights reserved.

关键词： trip planning mobile geosensor networks time geography network algorithms agent-based simulation

来源：评论

学校读者我要写书评

暂无评论

Distributed verification of minimum spanning trees

引用

DISTRIBUTED COMPUTING 2007年第4期20卷 253-266页

作者： Korman, Amos Kutten, Shay Technion Israel Inst Technol Informat Syst Grp IL-32000 Haifa Israel Technion Israel Inst Technol IE&M IL-32000 Haifa Israel

The problem of verifying a Minimum Spanning Tree (MST) was introduced by Tarjan in a sequential setting. Given a graph and a tree that spans it, the algorithm is required to check whether this tree is an MST. This paper investigates the problem in the distributed setting, where the input is given in a distributed manner, i.e., every node "knows" which of its own emanating edges belong to the tree. Informally, the distributed MST verification problem is the following. Label the vertices of the graph in such a way that for every node, given (its own state and label and) the labels of its neighbors only, the node can detect whether these edges are indeed its MST edges. In this paper, we present such a verification scheme with a maximum label size of 0 (log n log W), where n is the number of nodes and W is the largest weight of an edge. We also give a matching lower bound of ohm (log n log W) (as long as W > (log n) (1+is an element of) for some fixed is an element of > 0). Both our bounds improve previously known bounds for the problem. For the related problem of tree sensitivity also presented by Tarjan, our method yields rather efficient schemes for both the distributed and the sequential settings.

关键词： network algorithms graph property verification labeling schemes minimum spanning tree proof labeling schemes self stabilization

来源：评论

学校读者我要写书评

暂无评论

Modeling TCAM power for next generation network devices

Modeling TCAM power for next generation network devices

引用

IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS 2006)

作者： Agrawal, Banit Sherwood, Timothy Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

ISBN: (纸本)1424401860

Applications in Computer networks often require high throughput access to large data structures for lookup and classification. Many advanced algorithms exist to speed these search primitives on network processors, general purpose machines, and even custom ASICs. However supporting these applications with standard memories requires very careful analysis of access patterns, and achieving worst case performance can be quite difficult and complex. A simple solution is often possible if a Ternary CAM is used to perform a fully parallel search across the entire data set. Unfortunately, this parallelism means that large portions of the chip are switching during each cycle, causing large amounts of power to be consumed. While researchers have begun to explore new ways of managing the power consumption, quantifying design alternatives is difficult due to a lack of available models. In this paper we examine the structure inside a modern TCAM and present a simple, yet accurate, power model. We present techniques to estimate the dynamic power consumption of a large TCAM. We validate the model using industrial TCAM datasheets and prior published works. We present an extensive analysis of the model by varying various architectural parameters. We also describe how new network algorithms have the potential to address the growing problem of power management in next-generation network devices.

关键词： CAM ternary CAM TCAM SRAM power modeling router network algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：