Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming
Time-Sensitive Networking (TSN) is an in-development technology that enables predictability over Ethernet or wireless networks. Network interfaces compliant with the IEEE 802.1Qbv standard provide different queues/gates on each bridge egress port. In this way, a global network schedule can be set by...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10630823/ |
| _version_ | 1826872159061934080 |
|---|---|
| author | Alitzel Galilea Torres-Macias Juan Segarra Flor Jose Luis Briz Velasco Antonio Ramirez-Trevino Hector Blanco-Alcaine |
| author_facet | Alitzel Galilea Torres-Macias Juan Segarra Flor Jose Luis Briz Velasco Antonio Ramirez-Trevino Hector Blanco-Alcaine |
| author_sort | Alitzel Galilea Torres-Macias |
| collection | DOAJ |
| description | Time-Sensitive Networking (TSN) is an in-development technology that enables predictability over Ethernet or wireless networks. Network interfaces compliant with the IEEE 802.1Qbv standard provide different queues/gates on each bridge egress port. In this way, a global network schedule can be set by defining the opening and closing times (Gate Control List, GCL) for each gate. In this paper, we propose a new method to schedule GCLs by dividing the problem into several subproblems. We use Weighted Fair Queuing (WFQ) to set the ordering of frames, and then generate an Integer Linear Programming (ILP) model to optimize the TSN scenario. Next, we assign gates to the scheduled windows, trying to ensure frame isolation whenever possible. Our results show that we can schedule GCLs around 2 times faster than previous studies and up to 5.5 orders of magnitude faster if we choose to obtain any valid solution instead of the optimal one. In addition, we are able to schedule systems with utilization up to 85%, whereas previous papers reach 65%. Moreover, our approach does not need to predefine the number of windows or gates, as required by other methods. |
| first_indexed | 2025-02-16T23:51:59Z |
| format | Article |
| id | doaj.art-f95f9970a7ff431eac2d23bbdd946f1f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2025-02-16T23:51:59Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-f95f9970a7ff431eac2d23bbdd946f1f2025-01-15T00:01:18ZengIEEEIEEE Access2169-35362024-01-011211123911125010.1109/ACCESS.2024.344082810630823Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear ProgrammingAlitzel Galilea Torres-Macias0https://orcid.org/0009-0009-6122-1484Juan Segarra Flor1https://orcid.org/0000-0003-1550-735XJose Luis Briz Velasco2https://orcid.org/0000-0001-5940-9837Antonio Ramirez-Trevino3https://orcid.org/0000-0003-3028-3446Hector Blanco-Alcaine4https://orcid.org/0009-0006-7261-8215CINVESTAV Unidad Guadalajara, Zapopan, MexicoDepartamento de Informática e Ingeniería de Sistemas, Universidad de Zaragoza, Zaragoza, SpainDepartamento de Informática e Ingeniería de Sistemas, Universidad de Zaragoza, Zaragoza, SpainCINVESTAV Unidad Guadalajara, Zapopan, MexicoIntel Deutschland GmbH, Neubiberg, GermanyTime-Sensitive Networking (TSN) is an in-development technology that enables predictability over Ethernet or wireless networks. Network interfaces compliant with the IEEE 802.1Qbv standard provide different queues/gates on each bridge egress port. In this way, a global network schedule can be set by defining the opening and closing times (Gate Control List, GCL) for each gate. In this paper, we propose a new method to schedule GCLs by dividing the problem into several subproblems. We use Weighted Fair Queuing (WFQ) to set the ordering of frames, and then generate an Integer Linear Programming (ILP) model to optimize the TSN scenario. Next, we assign gates to the scheduled windows, trying to ensure frame isolation whenever possible. Our results show that we can schedule GCLs around 2 times faster than previous studies and up to 5.5 orders of magnitude faster if we choose to obtain any valid solution instead of the optimal one. In addition, we are able to schedule systems with utilization up to 85%, whereas previous papers reach 65%. Moreover, our approach does not need to predefine the number of windows or gates, as required by other methods.https://ieeexplore.ieee.org/document/10630823/802.1QbvdelayGCLILPjitterreal-time |
| spellingShingle | Alitzel Galilea Torres-Macias Juan Segarra Flor Jose Luis Briz Velasco Antonio Ramirez-Trevino Hector Blanco-Alcaine Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming IEEE Access 802.1Qbv delay GCL ILP jitter real-time |
| title | Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming |
| title_full | Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming |
| title_fullStr | Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming |
| title_full_unstemmed | Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming |
| title_short | Fast IEEE802.1Qbv Gate Scheduling Through Integer Linear Programming |
| title_sort | fast ieee802 1qbv gate scheduling through integer linear programming |
| topic | 802.1Qbv delay GCL ILP jitter real-time |
| url | https://ieeexplore.ieee.org/document/10630823/ |
| work_keys_str_mv | AT alitzelgalileatorresmacias fastieee8021qbvgateschedulingthroughintegerlinearprogramming AT juansegarraflor fastieee8021qbvgateschedulingthroughintegerlinearprogramming AT joseluisbrizvelasco fastieee8021qbvgateschedulingthroughintegerlinearprogramming AT antonioramireztrevino fastieee8021qbvgateschedulingthroughintegerlinearprogramming AT hectorblancoalcaine fastieee8021qbvgateschedulingthroughintegerlinearprogramming |