5th International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

Routing and Scheduling Connections in Networks that Support Advance Reservations

Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.1109/BROADNETS.2008.4769139,
    author={Emmanouel Varvarigos and Vasileios Sourlas and Konstantinos Christodoulopoulos},
    title={Routing and Scheduling Connections in Networks that Support Advance Reservations},
    proceedings={5th International ICST Conference on Broadband Communications, Networks, and Systems},
    publisher={IEEE},
    proceedings_a={BROADNETS},
    year={2010},
    month={5},
    keywords={Multicost routing and scheduling advance reservation Quality of Service capacity utilization profiles Optical Burst Switching},
    doi={10.1109/BROADNETS.2008.4769139}
}
  • Emmanouel Varvarigos
    Vasileios Sourlas
    Konstantinos Christodoulopoulos
    Year: 2010
    Routing and Scheduling Connections in Networks that Support Advance Reservations
    BROADNETS
    IEEE
    DOI: 10.1109/BROADNETS.2008.4769139
Emmanouel Varvarigos1,2,*, Vasileios Sourlas3,*, Konstantinos Christodoulopoulos1,2,*
  • 1: Department of Computer Engineering and Informatics, University of Patras, Greece,
  • 2: Research Academic Computer Technology Institute, Patra, Greece
  • 3: Department of Computer and Communication Engineering, University of Thessaly, Greece
*Contact email: manos@ceid.upatras.gr, vsourlas@inf.uth.gr, kchristodou@ceid.upatras.gr

Abstract

A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start so as to minimize the reception time at the destination, or some other QoS requirement. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated candidate paths, from which the optimal path can be found. By appropriately pruning the set of candidate paths using path pseudo-domination relationships, we also find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial time algorithms have performance that it is very close to that of the optimal algorithm.

Keywords
Multicost routing and scheduling advance reservation Quality of Service capacity utilization profiles Optical Burst Switching
Published
2010-05-16
Publisher
IEEE
Modified
2010-05-16
http://dx.doi.org/10.1109/BROADNETS.2008.4769139
Copyright © 2008–2024 IEEE