| 摘要: | 隨著物聯網技術的不斷發展，實時通訊應用領域的資料傳輸需求不斷增長。為了應對不同等級資料之間的大量傳輸，越來越多的應用需要實時監控、傳輸和控制數據。在實時通訊系統中，確定性網路延遲、抖動和有效帶寬分配成為必要的要求。為此，IEEE 802.1 TSN 工作組制定了一系列標準，通過時間同步、流量整形、優先級控制等功能實現確定性的實時通訊。
為確保實時流傳輸的確定性，適用的排程方法至關重要。許多研究針對高優先級的控制資料流（control data traffics, CDT）提出了排程算法，隨著路由的重要性不斷提升，相應的研究也開始提出聯合排程與路由的算法。然而，考慮到AVB流的研究相對較少，僅考慮CDT流可能會導致音視訊流（Audio and Video Bridging, AVB）的傳輸延遲增加，無法滿足其實時需求。在真實的應用場景中，各種優先級的資料流都需要在網路上進行傳輸，因此需要考慮更多優先級的資料流。
本研究將AVB流納入考慮，混合了路徑選擇和排程計算，設計了基於基因演算法（Genetic Algorithm, GA）的聯合排程與路由算法與基於禁忌搜尋法（Tabu Search,TS）的聯合排程與路由算法。根據輸入的拓撲和流集合，可以計算出適合的排程和路由方案。本研究的優化目標是最小化AVB 流的最壞情況延遲（worst-case delay），以同時滿足所有流的實時需求並減少AVB 流的延遲。;With the development of IoT technology, there has been a significant increase in the demand for real-time data transmission in various application domains. To handle the large volume of transmission among different levels of data, more and more applications require real-time monitoring, transmission, and control of data. Consequently, the requirements for deterministic network latency, jitter, and efficient bandwidth allocation in real-time communication systems have also increased. The IEEE 802.1 TSN working group has developed a series of standards to achieve deterministic real-time communication through functionalities such as time synchronization, traffic shaping, and priority control.
An appropriate scheduling method is indispensable to ensure the determinism of real-time flow transmission. Many studies have proposed scheduling algorithms for high-priority Control Data Traffics (CDT), and with the increasing importance of routing, subsequent research has also proposed algorithms for joint scheduling and routing. However, there are relatively fewer studies that consider AVB flows. By solely considering CDT flows, the transmission delay of AVB flows may increase, resulting in the inability to meet their real-time requirements. In real-world application scenarios, it is necessary to transmit data flows of various priorities on the network, thus requiring consideration of flows with multiple priority levels.
This study takes into account AVB flows and designs two methods based on a combination of genetic algorithms and tabu search. These methods incorporate both path selection and scheduling calculations and can determine suitable scheduling and routing solutions based on the input topology and flow set. The optimization objective of this study is to minimize the worst-case delay of AVB flows while simultaneously meeting the real-time requirements of all flows. |
