Kavli Affiliate: Feng Wang
| First 5 Authors: Peng Wang, Suman Sourav, Binbin Chen, Hongyan Li, Feng Wang
| Summary:
Time-Triggered Communication is a key technology for many safety-critical
systems, with applications spanning the areas of aerospace and industrial
control. Such communication relies on time-triggered flows, with each flow
consisting of periodic packets originating from a source and destined for a
destination node. Each packet needs to reach its destination before its
deadline. Different flows can have different cycle lengths. To achieve assured
transmission of time-triggered flows, existing efforts constrain the packets of
a flow to be cyclically transmitted along the same path. Under such Fixed
Cyclic Scheduling (FCS), reservation for flows with different cycle lengths can
become incompatible over a shared link, limiting the total number of admissible
flows. Considering the cycle lengths of different flows, a hyper-cycle has
length equal to their least common multiple (LCM). It determines the time
duration over which the scheduling compatibility of the different flows can be
checked. In this work, we propose a more flexible schedule scheme called the
Hypercycle-level Flexible Schedule (HFS) scheme, where a flow’s resource
reservation can change across cycles within a hypercycle. HFS can significantly
increase the number of admitted flows by providing more scheduling options
while remaining perfectly compatible with existing Time-Triggered Ethernet
system. We show that, theoretically the possible capacity gain provided by HFS
over FCS can be unbounded. We formulate the joint pathfinding and scheduling
problem under HFS as an ILP problem which we prove to be NP-Hard. To solve HFS
efficiently, we further propose a least-load-first heuristic (HFS-LLF), solving
HFS as a sequence of shortest path problems. Extensive study shows that HFS
admits up to 6 times the number of flows achieved by FCS. Moreover, our
proposed HFS-LLF can run 104 times faster than solving HFS using a generic
solver.
| Search Query: ArXiv Query: search_query=au:”Feng Wang”&id_list=&start=0&max_results=3