.png){kind=icon}
.png){kind=icon}
Return
Efficient bufferless packet switching on trees and leveled networks
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2007.06.005.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In bufferless networks the packets cannot be buffered while they are in transit; thus, once injected, the packets have to move constantly. Bufferless networks are interesting because they model optical networks. The objective of this work is to demonstrate that efficient bufferless packet switching is achievable in particular, interesting network topologies. We consider the tree and leveled network topologies, which represent a wide class of network configurations. On these networks, we study many-to-one batch problems where each node is the source of at most one packet, and the destination of an arbitrary number of packets. Each packet is to follow a preselected path from the source to the destination. Let T* be the optimal delivery time for the packets. We have the following results: For trees, we present two bufferless algorithms: (i) a deterministic algorithm with delivery time O(delta . T* . log n), and (ii) a randomized algorithm with delivery time O(T* . log(2) n); where, delta is the maximum node degree, and n is the number of nodes. Both algorithms are distributed in the sense that packet forwarding decisionsare made locally at the nodes. For leveled networks, we present two algorithms: (i) a centralized algorithm with delivery time O (T* . log n), and (ii) a distributed algorithm with delivery time O (T* . log(2)n), where n is the number of nodes. The first algorithm is centralized in the sense that all decisions are madeby a single node. The distributed algorithm simulates the centralized one; the cost of this simulation isan extra logarithmic factor. Our bufferless algorithms are near-optimal, and they improve on previous results for trees and leveled networks by multiple logarithmic factors. (C) 2007 Elsevier Inc. All rights reserved.
Keywords:
routing algorithms
packet scheduling
hot-potato routing
congestion
dilation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available