NDLI: Bounds on the greedy routing algorithm for array networks

Please wait, while we are loading the content...

An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract)

A comparison of parallel algorithms for connected components

Improved bounds for routing and sorting on multi-dimensional meshes

2d-bubblesorting in average time O(√N lg N)*

Parallel sorting by over partitioning

Efficient compilation of high-level data parallel algorithms

SIMD instruction cache

Improved parity-declustered layouts for disk arrays

Scheduling trees using FIFO queues: a control-memory tradeoff

Studying overheads in massively parallel MIN/MAX-tree evaluation

List ranking and list scan on the Cray C-90

Dynamic parallel tree contraction (extended abstract)

Experiences with parallel N-body simulation

Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks

AT2 bounds for a class of VLSI problems and string matching

An Ω(√ log log n) lower bound for routing in optical networks

Programming DEC-Alpha based multiprocessors the easy way (extended abstract)

Diffracting trees (preliminary version)

On testing cache-coherent shared memories

Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?

Scheduling parallelizable tasks to minimize average response time

Job scheduling in rings

An analysis of diffusive load-balancing

Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract)

Efficient low-contention parallel algorithms

Constructive deterministic PRAM simulation on a mesh-connected computer

An optical simulation of shared memory

Construction of the mesh and the torus tolerating a large number of faults

O(log2 n) time efficient parallel factorization of dense, sparse separable, and banded matrices

How much can we speedup Gaussian elimination with pivoting?

Efficient algorithms for all-to-all communications in multi-port message-passing systems

An architecture for optimal all-to-all personalized communication

Communication efficient matrix multiplication on hypercubes

A model for multi-grained parallelism (extended abstract)

Increasing network bandwidth on meshes

Bounds on the greedy routing algorithm for array networks

Minimal adaptive routing on the mesh with bounded queue size

Segment router: a novel router design for parallel computers

Bounds on the greedy routing algorithm for array networks

Content Provider	ACM Digital Library
Author	Mitzenmacher, Michael
Abstract	We extend previous work on greedy routing for array networks by providing bounds on the average delay and the average number of packets in the system. We analyze the dynamic routing problem, where packets are generated at each node according to a Poisson process. Each packet is sent to a destination chosen uniformly at random. Packets are routed greedily, first moving to the correct column and then to the correct row. Packets require unit time to travel across a directed edge between nodes; only a single packet can cross an edge at any given time, and packets waiting for an edge are buffered. Our bounds are based on comparisons with computationally more simple queueing networks, and the methods used are generally applicable to other network systems. A primary contribution of the paper is a new lower bound technique that also improves on the previous lower bounds by Stamoulis and Tsitsiklis for heavily loaded hypercube networks. [11] On heavily loaded array networks, our lower and upper bounds differ by only a small constant factor.We further examine extensions of the problem where our methods prove useful. For example, we consider variations where edges can have different transmission rates or the destination distribution is non-uniform. In particular, we study to what extent optimally configured array networks outperform the standard array network.
Starting Page	346
Ending Page	353
Page Count	8
File Format	PDF
ISBN	0897916719
DOI	10.1145/181014.181446
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-08-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bounds on the Greedy Routing Algorithm for Array Networks

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

Improved asymptotic bounds on critical transmission radius for greedy forward routing in wireless ad hoc networks

Research on the routing algorithm based greedy multicast algorithm

Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks

Empirically Identifying the Best Greedy Algorithm for Covering Array Generation

Robot Task Allocation based on Greedy-Face-Greedy Algorithm

Swarm intelligence based energy saving greedy routing algorithm for wireless sensor networks

Bounds on the greedy routing algorithm for array networks

Similar Documents

Bounds on the Greedy Routing Algorithm for Array Networks

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

Bounds on the Greedy Routing Algorithm for Array Networks (1994)

Improved asymptotic bounds on critical transmission radius for greedy forward routing in wireless ad hoc networks

Research on the routing algorithm based greedy multicast algorithm

Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks

Empirically Identifying the Best Greedy Algorithm for Covering Array Generation

Robot Task Allocation based on Greedy-Face-Greedy Algorithm

Swarm intelligence based energy saving greedy routing algorithm for wireless sensor networks

Bounds on the greedy routing algorithm for array networks