Search: onr:"swepub:oai:DiVA.org:uu-418562" >
Routing and schedul...
Routing and scheduling of network flows with deadlines and discrete capacity allocation
-
- Ahani, Ghafour (author)
- Uppsala universitet,Datalogi
-
- Wiatr, Pawel (author)
- Uppsala universitet,Datalogi
-
- Yuan, Di (author)
- Uppsala universitet,Datalogi
-
(creator_code:org_t)
- 2020-03-24
- 2020
- English.
-
In: Networks. - : WILEY. - 0028-3045 .- 1097-0037. ; 76:1, s. 54-74
- Related links:
-
http://arxiv.org/pdf...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Joint scheduling and routing of data flows with deadline constraints in communication networks has been attracting research interest. This type of problem distinguishes from conventional multicommodity flows due to the presence of the time dimension. In this paper, we address a flow routing and scheduling problem with delivery deadline, where the assignment of link capacity occurs in discrete units. Discrete capacity allocation is motivated by applications in communication systems, where it is common to have a base unit of capacity (e.g., wavelength channel in optical communications). We present and prove complexity results of the problem. Next, we give an optimization formulation based on a time slicing approach, which amounts to a discretization of the time into time slices to enable to formulate the deadline constraints. We then derive an effective reformulation of the problem, via which a column generation algorithm is developed. In addition, we propose a simple and fast max-flow-based algorithm. We use a number of networks and traffic scenarios to study various performance aspects of the algorithms.
Subject headings
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Kommunikationssystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Communication Systems (hsv//eng)
Keyword
- deadline
- discrete capacity allocation
- flow routing
- flow scheduling
- networks
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
-
Networks
(Search for host publication in LIBRIS)
To the university's database