時效性網路下具AVB感知的排程與路由方法之設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：47

、訪客IP：3.133.148.130

姓名

劉允成(Yun-Cheng Liu) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

時效性網路下具AVB感知的排程與路由方法之設計
(AVB-aware Scheduling and Routing Schemes in Time-Sensitive Networks)

相關論文

★ 非結構同儕網路上以特徵相似度為基準之搜尋方法	★ 以階層式叢集聲譽為基礎之行動同儕網路拓撲架構
★ 線上RSS新聞資料流中主題性事件監測機制之設計與實作	★ 耐延遲網路下具密度感知的路由方法
★ 整合P2P與UPnP內容分享服務之家用多媒體閘道器：設計與實作	★ 家庭網路下簡易無縫式串流影音播放服務之設計與實作
★ 耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計	★ BitTorrent P2P 檔案系統下載端網路資源之可調式配置方法與效能實測
★ 耐延遲網路中利用訊息編碼重組條件之資料傳播機制	★ 耐延遲網路中基於人類移動模式之路由機制
★ 車載網路中以資料匯集技術改善傳輸效能之封包傳送機制	★ 適用於交叉路口環境之車輛叢集方法
★ 車載網路下結合路側單元輔助之訊息廣播機制	★ 耐延遲網路下以靜態中繼節點（暫存盒）最佳化訊息傳遞效能之研究
★ 耐延遲網路下以動態叢集感知建構之訊息傳遞機制	★ 跨裝置影音匯流平台之設計與實作

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著物聯網技術的不斷發展，實時通訊應用領域的資料傳輸需求不斷增長。為了應對不同等級資料之間的大量傳輸，越來越多的應用需要實時監控、傳輸和控制數據。在實時通訊系統中，確定性網路延遲、抖動和有效帶寬分配成為必要的要求。為此，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.

關鍵字(中)

★ 時效性網路
★ 排程
★ 路徑分配
★ 基因演算法
★ 禁忌搜尋法

關鍵字(英)

論文目次

摘要 i
Abstract ii
致謝 iii
圖目錄 v
表目錄 vii
1 簡介 1
1.1 前言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 研究背景及文獻探討 4
2.1 時效性網路機制簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 時間感知整流器(Time-Aware Shaper, TAS) . . . . . . . . . . . . . 6
2.1.2 基於信用的整流器(Credit-based Shaper, CBS) . . . . . . . . . . . 8
2.2 相關文獻探討. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 路由問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 排程問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 聯合排程與路由問題. . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 系統架構 14
3.1 時效性網路架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 問題定義. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 排程限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 方法設計 19
4.1 基於基因演算法之路由與排程計算. . . . . . . . . . . . . . . . . . . . . . 19
4.1.1 染色體編碼. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.2 初始族群. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.3 適應值計算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.4 選擇. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1.5 交叉. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.6 突變. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 排程方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.1 傳輸偏移. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.2 壓縮. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 基於禁忌搜尋法之路由與排程計算. . . . . . . . . . . . . . . . . . . . . . 45
4.3.1 起始解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.2 鄰域搜尋. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.3 路徑分配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 實驗結果與分析 52
5.1 實驗環境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2 實驗結果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.1 延遲比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.2 收斂比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 結論與未來展望 64
參考文獻 65

參考文獻

[1] F. Consortium, “Flexray communications system protocol specification version 3.0.1,” 2010.
[2] ISO, “Iso 11898-2:2003,” 2003.
[3] E. Tovar and F. Vasques, “Real-time fieldbus communications using profibus networks,” IEEE transactions on Industrial Electronics, vol. 46, no. 6, pp. 1241–1251,
1999.
[4] IEEE, “Ieee 802.1 time-sensitive networking task group.” [Online]. Available: https://www.ieee802.org/1/pages/tsn.html
[5] ——, “Ieee 802.1qbv - enhancements for scheduled traffic.” [Online]. Available: https://www.ieee802.org/1/pages/802.1bv.html
[6] S. S. Craciunas, R. S. Oliver, M. Chmelík, and W. Steiner, “Scheduling real-time communication in ieee 802.1 qbv time sensitive networks,” in Proceedings of the 24th
International Conference on Real-Time Networks and Systems, 2016, pp. 183–192.
[7] N. G. Nayak, F. Dürr, and K. Rothermel, “Routing algorithms for ieee802. 1qbv networks,” ACM Sigbed Review, vol. 15, no. 3, pp. 13–18, 2018.
[8] A. C. T. dos Santos, B. Schneider, and V. Nigam, “Tsnsched: Automated schedule generation for time sensitive networking,” in 2019 Formal Methods in Computer Aided Design (FMCAD). IEEE, 2019, pp. 69–77.
[9] E. Schweissguth, P. Danielis, D. Timmermann, H. Parzyjegla, and G. Mühl, “Ilpbased joint routing and scheduling for time-triggered networks,” in Proceedings of he 25th International Conference on Real-Time Networks and Systems, 2017, pp. 8–17.
[10] Q. Yu and M. Gu, “Adaptive group routing and scheduling in multicast time-sensitive networks,” IEEE Access, vol. 8, pp. 37 855–37 865, 2020.
[11] J. Falk, F. Dürr, and K. Rothermel, “Exploring practical limitations of joint routing and scheduling for tsn with ilp,” in 2018 IEEE 24th International Conference on
Embedded and Real-Time Computing Systems and Applications (RTCSA). IEEE, 2018, pp. 136–146.
[12] A. Arestova, K.-S. J. Hielscher, and R. German, “Design of a hybrid genetic algorithm for time-sensitive networking,” in Measurement, Modelling and Evaluation of Computing Systems: 20th International GI/ITG Conference, MMB 2020, Saarbrücken, Germany, March 16–18, 2020, Proceedings 20. Springer, 2020, pp. 99–117.
[13] A. A. Atallah, G. B. Hamad, and O. A. Mohamed, “Routing and scheduling of time-triggered traffic in time-sensitive networks,” IEEE Transactions on Industrial Informatics, vol. 16, no. 7, pp. 4525–4534, 2019.
[14] V. Gavriluţ, L. Zhao, M. L. Raagaard, and P. Pop, “Avb-aware routing and scheduling of time-triggered traffic for tsn,” Ieee Access, vol. 6, pp. 75 229–75 243, 2018.
[15] IEEE, “Ieee 802.1qav - forwarding and queuing enhancements for time-sensitive streams.” [Online]. Available: https://www.ieee802.org/1/pages/802.1av.html
[16] M. A. Ojewale and P. M. Yomsi, “Routing heuristics for load-balanced transmission in tsn-based networks,” ACM Sigbed Review, vol. 16, no. 4, pp. 20–25, 2020.
[17] Z. Pang, X. Huang, Z. Li, S. Zhang, Y. Xu, H. Wan, and X. Zhao, “Flow scheduling for conflict-free network updates in time-sensitive software-defined networks,” IEEE
Transactions on Industrial Informatics, vol. 17, no. 3, pp. 1668–1678, 2020.
[18] F. Dürr and N. G. Nayak, “No-wait packet scheduling for ieee time-sensitive networks (tsn),” in Proceedings of the 24th International Conference on Real-Time Networks
and Systems, 2016, pp. 203–212.
[19] L. Xu, Q. Xu, J. Tu, J. Zhang, Y. Zhang, C. Chen, and X. Guan, “Learning-based scalable scheduling and routing co-design with stream similarity partitioning for timesensitive
networking,” IEEE Internet of Things Journal, vol. 9, no. 15, pp. 13 353– 13 363, 2022.
[20] D. Yang, K. Gong, J. Ren, W. Zhang, W. Wu, and H. Zhang, “Tc-flow: Chain flow scheduling for advanced industrial applications in time-sensitive networks,” IEEE
Network, vol. 36, no. 2, pp. 16–24, 2022.
[21] N. Reusch, S. S. Craciunas, and P. Pop, “Dependability-aware routing and scheduling for time-sensitive networking,” IET Cyber-Physical Systems: Theory & Applications, vol. 7, no. 3, pp. 124–146, 2022.
[22] S. Bhattacharjee, K. Alexandris, E. Hansen, P. Pop, and T. Bauschert, “Latencyaware function placement, routing, and scheduling in tsn-based industrial networks,” in ICC 2022-IEEE International Conference on Communications. IEEE, 2022, pp. 4248–4254.
[23] S. Mirjalili and S. Mirjalili, “Genetic algorithm,” Evolutionary Algorithms and Neural Networks: Theory and Applications, pp. 43–55, 2019.
[24] H.-J. Kim, K.-C. Lee, M.-H. Kim, and S. Lee, “Optimal scheduling of time-sensitive networks for automotive ethernet based on genetic algorithm,” Electronics, vol. 11,
no. 6, p. 926, 2022.
[25] T. Park, S. Samii, and K. G. Shin, “Design optimization of frame preemption in realtime switched ethernet,” in 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2019, pp. 420–425.
[26] V. Gavrilut, B. Zarrin, P. Pop, and S. Samii, “Fault-tolerant topology and routing synthesis for ieee time-sensitive networking,” in Proceedings of the 25th International Conference on Real-Time Networks and Systems, 2017, pp. 267–276.
[27] M. Nawaz, E. E. Enscore Jr, and I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, vol. 11, no. 1, pp. 91–95, 1983.
[28] A. Berisa, L. Zhao, S. S. Craciunas, M. Ashjaei, S. Mubeen, M. Daneshtalab, and M. Sjödin, “Avb-aware routing and scheduling for critical traffic in time-sensitive
networks with preemption,” in Proceedings of the 30th International Conference on Real-Time Networks and Systems, 2022, pp. 207–218.
[29] L. G. Valiant, “The complexity of enumeration and reliability problems,” siam Journal on Computing, vol. 8, no. 3, pp. 410–421, 1979.
[30] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of operations research, vol. 1, no. 2, pp. 117–129, 1976.
[31] D. Maxim and Y.-Q. Song, “Delay analysis of avb traffic in time-sensitive networks (tsn),” in Proceedings of the 25th International Conference on Real-Time Networks
and Systems, 2017, pp. 18–27.
[32] F. Glover and M. Laguna, Tabu search. Springer, 1998.
[33] L. Zhao, P. Pop, Z. Zheng, and Q. Li, “Timing analysis of avb traffic in tsn networks using network calculus,” in 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 2018, pp. 25–36.
[34] A. F. Gad, “Pygad: An intuitive genetic algorithm python library,” arXiv preprint arXiv:2106.06158, 2021.
[35] IEEE, “Ieee 802.1ba - audio video bridging (avb) systems.” [Online]. Available:
https://www.ieee802.org/1/pages/802.1ba.html

指導教授

胡誌麟

審核日期

2023-8-14

推文