License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.34
URN: urn:nbn:de:0030-drops-190713
URL: https://drops.dagstuhl.de/opus/volltexte/2023/19071/
Go to the corresponding LIPIcs Volume Portal


Talbot, Pierre ; Hu, Tingting ; Navet, Nicolas

Constraint Programming with External Worst-Case Traversal Time Analysis

pdf-format:
LIPIcs-CP-2023-34.pdf (3 MB)


Abstract

The allocation of software functions to processors under compute capacity and network links constraints is an important optimization problem in the field of embedded distributed systems. We present a hybrid approach to solve the allocation problem combining a constraint solver and a worst-case traversal time (WCTT) analysis that verifies the network timing constraints. The WCTT analysis is implemented as an industrial black-box program, which makes a tight integration with constraint solving challenging. We contribute to a new multi-objective constraint solving algorithm for integrating external under-approximating functions, such as the WCTT analysis, with constraint solving, and prove its correctness. We apply this new algorithm to the allocation problem in the context of automotive service-oriented architectures based on Ethernet networks, and provide a new dataset of realistic instances to evaluate our approach.

BibTeX - Entry

@InProceedings{talbot_et_al:LIPIcs.CP.2023.34,
  author =	{Talbot, Pierre and Hu, Tingting and Navet, Nicolas},
  title =	{{Constraint Programming with External Worst-Case Traversal Time Analysis}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19071},
  URN =		{urn:nbn:de:0030-drops-190713},
  doi =		{10.4230/LIPIcs.CP.2023.34},
  annote =	{Keywords: Constraint programming, external function, multi-objective optimization, network analysis, worst-case traversal time analysis, abstract interpretation}
}

Keywords: Constraint programming, external function, multi-objective optimization, network analysis, worst-case traversal time analysis, abstract interpretation
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023
Supplementary Material: Software: https://github.com/ptal/automotive-network-cp/tree/cp2023 archived at: https://archive.softwareheritage.org/swh:1:dir:e0fe246fdd3c6654293c9f5183cae7782b540d07


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI