Routing and scheduling of network flows with deadlines and discrete capacity allocation

(creator_code:org_t)

Related links:: http://arxiv.org/pdf...; show more...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

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.

About the subject

ENGINEERING AND TECHNOLOGY: ENGINEERING AND ...; and Electrical Engin ...; and Communication Sy ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.