Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Trade-offs between load and degree in virtual path layouts

Dessmark, Anders LU ; Lingas, Andrzej LU and Pelc, Andrzej (2003) In Parallel Processing Letters 13(3). p.485-496
Abstract
We study virtual path layouts in ATM networks. Packets are routed along virtual paths in the network by maintaining a routing field whose subfields determine intermediate destinations of the packet, i.e., the endpoints of virtual paths on its way to the final destination. Most of the research on virtual path layouts has focused on tradeoffs between load (i.e., the maximum number of virtual paths passing through a link) and the hop number of the layout (i.e., the maximum number of virtual paths needed to travel between any two nodes).



There is however another important limitation on construction of layouts, resulting from technological properties of switches situated at nodes. This bound is the degree of the layout (i.e.,... (More)
We study virtual path layouts in ATM networks. Packets are routed along virtual paths in the network by maintaining a routing field whose subfields determine intermediate destinations of the packet, i.e., the endpoints of virtual paths on its way to the final destination. Most of the research on virtual path layouts has focused on tradeoffs between load (i.e., the maximum number of virtual paths passing through a link) and the hop number of the layout (i.e., the maximum number of virtual paths needed to travel between any two nodes).



There is however another important limitation on construction of layouts, resulting from technological properties of switches situated at nodes. This bound is the degree of the layout (i.e., the maximum number of virtual paths with a common endpoint). In this paper we study relations between these three parameters of virtual path layouts, for the all-to-all problem. For any integer h, we show tradeoffs between load and degree of h-hop layouts in the ring and in the mesh by establishing upper and lower bounds on these parameters. Our bounds on the degree of an h-hop layout of given load are asymptotically tight and the bounds on the load of an h-hop layout of given degree are asymptotically tight for constant h. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Parallel Processing Letters
volume
13
issue
3
pages
485 - 496
publisher
World Scientific Publishing
external identifiers
  • scopus:0348158215
ISSN
1793-642X
DOI
10.1142/S0129626403001446
language
English
LU publication?
yes
id
746acfe9-f4af-4401-bb31-fa1ad03584d3 (old id 631627)
date added to LUP
2016-04-01 11:38:03
date last changed
2022-02-18 02:34:30
@article{746acfe9-f4af-4401-bb31-fa1ad03584d3,
  abstract     = {{We study virtual path layouts in ATM networks. Packets are routed along virtual paths in the network by maintaining a routing field whose subfields determine intermediate destinations of the packet, i.e., the endpoints of virtual paths on its way to the final destination. Most of the research on virtual path layouts has focused on tradeoffs between load (i.e., the maximum number of virtual paths passing through a link) and the hop number of the layout (i.e., the maximum number of virtual paths needed to travel between any two nodes).<br/><br>
<br/><br>
There is however another important limitation on construction of layouts, resulting from technological properties of switches situated at nodes. This bound is the degree of the layout (i.e., the maximum number of virtual paths with a common endpoint). In this paper we study relations between these three parameters of virtual path layouts, for the all-to-all problem. For any integer h, we show tradeoffs between load and degree of h-hop layouts in the ring and in the mesh by establishing upper and lower bounds on these parameters. Our bounds on the degree of an h-hop layout of given load are asymptotically tight and the bounds on the load of an h-hop layout of given degree are asymptotically tight for constant h.}},
  author       = {{Dessmark, Anders and Lingas, Andrzej and Pelc, Andrzej}},
  issn         = {{1793-642X}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{485--496}},
  publisher    = {{World Scientific Publishing}},
  series       = {{Parallel Processing Letters}},
  title        = {{Trade-offs between load and degree in virtual path layouts}},
  url          = {{http://dx.doi.org/10.1142/S0129626403001446}},
  doi          = {{10.1142/S0129626403001446}},
  volume       = {{13}},
  year         = {{2003}},
}