Impact of non-uniform traffic on the design of multi-hop regular virtual topologies for optical packet switching over arbitrary physical topologies

O. Komolafe, D.A. Harle, D. Cotter

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Different multiprocessor interconnection architectures, including the Manhattan Street Network (MSN), have attracted interests as optical packet switching infrastructures. This paper studies the deployment of such architectures as regular virtual topologies in arbitrary physical networks. The inputs to the virtual topology design problem are the physical topology, the traffic matrix and the regular topology. In this paper, this problem is both tackled directly and by decomposition into two subproblems. The first subproblem - dilation minimization - uses only the physical topology and the virtual topology as optimization inputs. Node placement optimization - the second subproblem - considers the traffic matrix and virtual topology as inputs. The solutions of these two subproblems are compared with each other and against the results obtained when the global problem is optimized directly (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the relative importance of the physical topology and traffic matrix when designing a regular virtual topology for optical packet switching. Regardless of the approach adopted, the problem is intractable, and hence, heuristics must be used to find (near) optimal solutions expeditiously. Five optimization heuristics, using different artificial intelligence (AI) techniques, are employed in this paper. The results obtained by the heuristics for the three alternative design approaches are compared under a variety of traffic scenarios. An important conclusion of this paper is that the traffic matrix plays a less significant role than is conventionally assumed, and only a marginal penalty is incurred by disregarding it in several of the traffic cases considered. In fact, it was found that it is possible to design the regular virtual topology without using the traffic matrix, and yet, the solution is close to optimal for a range of traffic scenarios and relatively immune to traffic fluctuations.
LanguageEnglish
Pages1248-1263
Number of pages15
JournalJournal of Lightwave Technology
Volume20
Issue number8
DOIs
Publication statusPublished - 2002

Fingerprint

packet switching
optical switching
traffic
topology
matrices
optimization
artificial intelligence
streets
penalties

Keywords

  • artificial intelligence
  • graph theory
  • multiprocessor interconnection networks
  • optical fibre networks
  • packet switching

Cite this

@article{e497444940714a449bfbc7a59d2dc881,
title = "Impact of non-uniform traffic on the design of multi-hop regular virtual topologies for optical packet switching over arbitrary physical topologies",
abstract = "Different multiprocessor interconnection architectures, including the Manhattan Street Network (MSN), have attracted interests as optical packet switching infrastructures. This paper studies the deployment of such architectures as regular virtual topologies in arbitrary physical networks. The inputs to the virtual topology design problem are the physical topology, the traffic matrix and the regular topology. In this paper, this problem is both tackled directly and by decomposition into two subproblems. The first subproblem - dilation minimization - uses only the physical topology and the virtual topology as optimization inputs. Node placement optimization - the second subproblem - considers the traffic matrix and virtual topology as inputs. The solutions of these two subproblems are compared with each other and against the results obtained when the global problem is optimized directly (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the relative importance of the physical topology and traffic matrix when designing a regular virtual topology for optical packet switching. Regardless of the approach adopted, the problem is intractable, and hence, heuristics must be used to find (near) optimal solutions expeditiously. Five optimization heuristics, using different artificial intelligence (AI) techniques, are employed in this paper. The results obtained by the heuristics for the three alternative design approaches are compared under a variety of traffic scenarios. An important conclusion of this paper is that the traffic matrix plays a less significant role than is conventionally assumed, and only a marginal penalty is incurred by disregarding it in several of the traffic cases considered. In fact, it was found that it is possible to design the regular virtual topology without using the traffic matrix, and yet, the solution is close to optimal for a range of traffic scenarios and relatively immune to traffic fluctuations.",
keywords = "artificial intelligence, graph theory, multiprocessor interconnection networks, optical fibre networks, packet switching",
author = "O. Komolafe and D.A. Harle and D. Cotter",
year = "2002",
doi = "10.1109/JLT.2002.800258",
language = "English",
volume = "20",
pages = "1248--1263",
journal = "Journal of Lightwave Technology",
issn = "0733-8724",
publisher = "Optical Society of America",
number = "8",

}

TY - JOUR

T1 - Impact of non-uniform traffic on the design of multi-hop regular virtual topologies for optical packet switching over arbitrary physical topologies

AU - Komolafe, O.

AU - Harle, D.A.

AU - Cotter, D.

PY - 2002

Y1 - 2002

N2 - Different multiprocessor interconnection architectures, including the Manhattan Street Network (MSN), have attracted interests as optical packet switching infrastructures. This paper studies the deployment of such architectures as regular virtual topologies in arbitrary physical networks. The inputs to the virtual topology design problem are the physical topology, the traffic matrix and the regular topology. In this paper, this problem is both tackled directly and by decomposition into two subproblems. The first subproblem - dilation minimization - uses only the physical topology and the virtual topology as optimization inputs. Node placement optimization - the second subproblem - considers the traffic matrix and virtual topology as inputs. The solutions of these two subproblems are compared with each other and against the results obtained when the global problem is optimized directly (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the relative importance of the physical topology and traffic matrix when designing a regular virtual topology for optical packet switching. Regardless of the approach adopted, the problem is intractable, and hence, heuristics must be used to find (near) optimal solutions expeditiously. Five optimization heuristics, using different artificial intelligence (AI) techniques, are employed in this paper. The results obtained by the heuristics for the three alternative design approaches are compared under a variety of traffic scenarios. An important conclusion of this paper is that the traffic matrix plays a less significant role than is conventionally assumed, and only a marginal penalty is incurred by disregarding it in several of the traffic cases considered. In fact, it was found that it is possible to design the regular virtual topology without using the traffic matrix, and yet, the solution is close to optimal for a range of traffic scenarios and relatively immune to traffic fluctuations.

AB - Different multiprocessor interconnection architectures, including the Manhattan Street Network (MSN), have attracted interests as optical packet switching infrastructures. This paper studies the deployment of such architectures as regular virtual topologies in arbitrary physical networks. The inputs to the virtual topology design problem are the physical topology, the traffic matrix and the regular topology. In this paper, this problem is both tackled directly and by decomposition into two subproblems. The first subproblem - dilation minimization - uses only the physical topology and the virtual topology as optimization inputs. Node placement optimization - the second subproblem - considers the traffic matrix and virtual topology as inputs. The solutions of these two subproblems are compared with each other and against the results obtained when the global problem is optimized directly (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the relative importance of the physical topology and traffic matrix when designing a regular virtual topology for optical packet switching. Regardless of the approach adopted, the problem is intractable, and hence, heuristics must be used to find (near) optimal solutions expeditiously. Five optimization heuristics, using different artificial intelligence (AI) techniques, are employed in this paper. The results obtained by the heuristics for the three alternative design approaches are compared under a variety of traffic scenarios. An important conclusion of this paper is that the traffic matrix plays a less significant role than is conventionally assumed, and only a marginal penalty is incurred by disregarding it in several of the traffic cases considered. In fact, it was found that it is possible to design the regular virtual topology without using the traffic matrix, and yet, the solution is close to optimal for a range of traffic scenarios and relatively immune to traffic fluctuations.

KW - artificial intelligence

KW - graph theory

KW - multiprocessor interconnection networks

KW - optical fibre networks

KW - packet switching

UR - http://dx.doi.org/10.1109/JLT.2002.800258

U2 - 10.1109/JLT.2002.800258

DO - 10.1109/JLT.2002.800258

M3 - Article

VL - 20

SP - 1248

EP - 1263

JO - Journal of Lightwave Technology

T2 - Journal of Lightwave Technology

JF - Journal of Lightwave Technology

SN - 0733-8724

IS - 8

ER -