Designing a multi-hop regular virtual topology for ultrafast optical packet switching: node placement optimisation and/or dilation minimisation?

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

Research output: Contribution to conferencePaper

Abstract

This paper studies the design of multi-hop regular virtual topologies to facilitate optical packet switching in networks with arbitrary physical topologies. 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 tackled directly and also by decomposition into two sub-problems. The first sub-problem, dilation minimisation, uses only the physical topology and the virtual topology as optimisation inputs. The second sub-problem considers the traffic matrix and virtual topology as optimisation inputs. The solutions of these two sub-problems are compared with each other and against the results obtained when the global problem is optimised (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the key question of whether the physical topology or the traffic matrix is the more important parameter when designing a regular virtual topology for optical packet
switching. Regardless of the approach taken the problem is intractable and hence
heuristics must be used to find (near) optimal solutions in reasonable time. Five
different optimisation heuristics, using different artificial intelligence 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.
LanguageEnglish
Number of pages8
Publication statusPublished - 2001
Event2001 Networks and Optical Communications Conference (NOC) - , United Kingdom
Duration: 1 Jan 2001 → …

Conference

Conference2001 Networks and Optical Communications Conference (NOC)
CountryUnited Kingdom
Period1/01/01 → …

Fingerprint

Packet switching
Topology
Artificial intelligence
Decomposition

Keywords

  • combinatorial optimisation
  • regular virtual topology design
  • manhattan street network
  • combinatorial optimisation

Cite this

Komolafe, O., Harle, D. A., & Cotter, D. (2001). Designing a multi-hop regular virtual topology for ultrafast optical packet switching: node placement optimisation and/or dilation minimisation?. Paper presented at 2001 Networks and Optical Communications Conference (NOC) , United Kingdom.
Komolafe, O. ; Harle, D.A. ; Cotter, D. / Designing a multi-hop regular virtual topology for ultrafast optical packet switching : node placement optimisation and/or dilation minimisation?. Paper presented at 2001 Networks and Optical Communications Conference (NOC) , United Kingdom.8 p.
@conference{db3e9181f9b743159c519b4545bc88f7,
title = "Designing a multi-hop regular virtual topology for ultrafast optical packet switching: node placement optimisation and/or dilation minimisation?",
abstract = "This paper studies the design of multi-hop regular virtual topologies to facilitate optical packet switching in networks with arbitrary physical topologies. 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 tackled directly and also by decomposition into two sub-problems. The first sub-problem, dilation minimisation, uses only the physical topology and the virtual topology as optimisation inputs. The second sub-problem considers the traffic matrix and virtual topology as optimisation inputs. The solutions of these two sub-problems are compared with each other and against the results obtained when the global problem is optimised (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the key question of whether the physical topology or the traffic matrix is the more important parameter when designing a regular virtual topology for optical packetswitching. Regardless of the approach taken the problem is intractable and henceheuristics must be used to find (near) optimal solutions in reasonable time. Fivedifferent optimisation heuristics, using different artificial intelligence 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.",
keywords = "combinatorial optimisation , regular virtual topology design , manhattan street network, combinatorial optimisation",
author = "O. Komolafe and D.A. Harle and D. Cotter",
year = "2001",
language = "English",
note = "2001 Networks and Optical Communications Conference (NOC) ; Conference date: 01-01-2001",

}

Komolafe, O, Harle, DA & Cotter, D 2001, 'Designing a multi-hop regular virtual topology for ultrafast optical packet switching: node placement optimisation and/or dilation minimisation?' Paper presented at 2001 Networks and Optical Communications Conference (NOC) , United Kingdom, 1/01/01, .

Designing a multi-hop regular virtual topology for ultrafast optical packet switching : node placement optimisation and/or dilation minimisation? / Komolafe, O.; Harle, D.A.; Cotter, D.

2001. Paper presented at 2001 Networks and Optical Communications Conference (NOC) , United Kingdom.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Designing a multi-hop regular virtual topology for ultrafast optical packet switching

T2 - node placement optimisation and/or dilation minimisation?

AU - Komolafe, O.

AU - Harle, D.A.

AU - Cotter, D.

PY - 2001

Y1 - 2001

N2 - This paper studies the design of multi-hop regular virtual topologies to facilitate optical packet switching in networks with arbitrary physical topologies. 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 tackled directly and also by decomposition into two sub-problems. The first sub-problem, dilation minimisation, uses only the physical topology and the virtual topology as optimisation inputs. The second sub-problem considers the traffic matrix and virtual topology as optimisation inputs. The solutions of these two sub-problems are compared with each other and against the results obtained when the global problem is optimised (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the key question of whether the physical topology or the traffic matrix is the more important parameter when designing a regular virtual topology for optical packetswitching. Regardless of the approach taken the problem is intractable and henceheuristics must be used to find (near) optimal solutions in reasonable time. Fivedifferent optimisation heuristics, using different artificial intelligence 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.

AB - This paper studies the design of multi-hop regular virtual topologies to facilitate optical packet switching in networks with arbitrary physical topologies. 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 tackled directly and also by decomposition into two sub-problems. The first sub-problem, dilation minimisation, uses only the physical topology and the virtual topology as optimisation inputs. The second sub-problem considers the traffic matrix and virtual topology as optimisation inputs. The solutions of these two sub-problems are compared with each other and against the results obtained when the global problem is optimised (using all three possible input parameters) for a variety of traffic scenarios. This gives insight into the key question of whether the physical topology or the traffic matrix is the more important parameter when designing a regular virtual topology for optical packetswitching. Regardless of the approach taken the problem is intractable and henceheuristics must be used to find (near) optimal solutions in reasonable time. Fivedifferent optimisation heuristics, using different artificial intelligence 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.

KW - combinatorial optimisation

KW - regular virtual topology design

KW - manhattan street network

KW - combinatorial optimisation

M3 - Paper

ER -

Komolafe O, Harle DA, Cotter D. Designing a multi-hop regular virtual topology for ultrafast optical packet switching: node placement optimisation and/or dilation minimisation?. 2001. Paper presented at 2001 Networks and Optical Communications Conference (NOC) , United Kingdom.