基于ODN的并行優化算法

摘 要：隨著光纖入戶政策的持續推進，海量光纖使用在接入網中，它們被用來連接端局光配線架和ODN光交接箱上的光纖端口。由于施工標識的混亂和模糊，光纖端口的連接關系難以知曉，造成大量光纖廢棄，， 無法實現精確的線纜資源管理，通過加入一種 基于ODN并行的優化算法，模擬出ODN中的ODF之間光纖對應關系，設置并行度并行進行多線程的計算，來達到時間復雜度的減少，算法的目的卻在于能夠有效的減少ODN中端口配對的時間復雜度。借助 c#語言進行編程仿真分析，仿真結果表明所提算法可以有效提高端口對應的效率。

關鍵詞：ODN 并行計算;c#

0引言

隨著科學技術的快速發展以及互聯網技術的普及，近年來，我國眾多企業為提升自身的市場核心競爭力，紛紛開展了機房資源的整合工作，致力于構建安全可靠的網絡結構，實現服務質量的提升以及成本的控制管理[1]統計數據顯示，通常運營商超過30%的光纖由于標識混亂、無法辨識造成資源沉淀無法使用，只能重新投資鋪設，造成大量資源浪費。除了資源沉淀外，運營商還面臨著光纖網絡業務開通和管理的難題，比如，運維部門接到訂單，派出施工人員到遠端進行施工，但到現場才發現光纖已經分配完畢;對于局端是否需要擴容，運營商也只能采取定期巡查的模式，耗費大量人力物力。[2]

ODN（光分配網 絡）是 基于 xPON（無 源 光 網絡）設備的 FTTH（光纖到戶）光纜網絡，其作用是在 OLT（光線路終端）和 ONU（光網絡單元）之間提供傳輸通道。根據國內FTTH 建設技術方案，OLT一般放 在 局 端，而 ONU 放 在 用 戶 端，因 此 OLT、ODN 和 ONU 這3部分組成了 FTTH 系統。從功能上分，ODN 由饋線光纜、配線光纜、入戶線光纜和光纖終端4個子系統組成。從產品形態上分，ODN可分為線纜類、光分配架（箱）類和分光與連接器類。由于 ODN 產品進入門檻較低，生產 ODN 產品的廠家達到數百家。同時 ODN 產品種類繁多，生產工藝與技術難易程度不同，造成市場上充斥著大量不合格產品，因此 ODN 產品質量控制尤為重要[3]FFTH投資和建設規模越來越大，也由此帶來了很多問題。其中最重要的一個問題是接入網光配線網絡（ODN）布線管理問題。具體問題概括為以下幾個方面：（1）隨著市場的需求不斷擴大，運營商在普及FFTH期間鋪設了海量的光纖光纜和設備，但由于缺乏規范統一的規劃，人工操作資源準確率低，盲目擴容，導致大量資源被閑置，很多有效資源難以發揮作用，建網的成本一直居高不下。（2）業務發放流程復雜，缺乏競爭力，開通慢，自行連接無校驗，返工率高，客戶滿意度難提升，難以有效支撐市場拓展。（3）資源數據人工維護，信息不匹配，刷新慢，錯誤率高;故障定位耗時長、效率低，難以支持精確化拓展。傳統光纖、網元設備管理主要通過給每個連接點貼紙質標簽來實現端口識別和路由管理。但FFTH網絡中節點數量龐大，大量的節點端口標簽依靠人工錄入、查找、標記、抄錄和盤點。運營商網絡資源管理系統數據通過人工錄入、修改。這些資源信息不僅錯誤率高，而且效率低下;工單派發、站點定位、資源歸檔等管理工作很難管控，統一高效;運維依賴客戶投訴，被動運維。這些問題導致了每年各大運營企業將近10%的投資用于ODN維護管理，花了大量人力物力卻帶來了數量龐大的錯誤光纖連接記錄和很低的光纖利用率。綜上所述，ODN網絡業務開通流程復雜，端口利用率低，管理難度大，在如今大發展FFTH的時期，運營商對高效穩定、方便管理維護的ODN網絡需求十分迫切，ODN的變革變成了當務之急，智能ODN也是未來必然的發展趨勢。[4]

因此本文基于智能ODN下，提出一種odf之間光纖對應關系的并行優化算法，能夠有效的減少端口之間對應的計算復雜度。

1算法思想和設計

圖1是電信局內機房光分配架（箱）類ODN的光纖連接方式，光分配架（箱）類ODN（光分配網 絡）在 OLT（光線路終端）和 ONU（光網絡單元）之間提供傳輸通道，通過代碼模擬出它們之間端口對應關系。1和2的端口相連。ODF11，ODF12和ODF21，ODF22的端口采用光纖相連。端口的連接情況未知，1和2的端口外連交換機。交換機上行端口連到PC端，PC端通過軟件找出1和2中端口連接情況。ODF11某號端口與和ODF21某號端口用某條線相連，ODF12某號端口與和ODF22某號端口用某條線相連。

ODF11∈ODF21? ? ? ?ODF12∈ODF22

時間復雜度是衡量算法執行效率的一種標準。但是，時間復雜度不等于性能。即便在不降低時間復雜度的情況下，也可以通過一些優化手段，提升代碼的執行效率。即便是像10%、20%這樣微小的性能提升，也是非常可觀的。算法的目的就是為了提高代碼執行效率。當算法無法再繼續優化的情況下，我們可以通過并行計算來進行優化進一步提高執行效率。

為了利用并行計算求解一個計算問題，通常基于以下考慮：1.將計算任務分解成多個子任務，有助于同時解決;2.在同一時間，由不同的執行部件可同時執行多個子任務;3.多計算資源下解決問題的耗時要少于單個計算資源下的耗時。

從概念上來說，進程是操作系統資源分配的基本單位，而線程是任務調度和執行的基本單位，在操作系統中能同時運行多個進程（程序）;而在同一個進程（程序）中有多個線程同時執行（通過CPU調度，在每個時間片中只有一個線程執行）自然我們也能理解一個進程至少包含一個線程。但是也不是可以隨便的開線程，每一個線程默認情況下都會占用1M的棧空間（對于普通應用程序來說），在32位的Windows平臺下可以給一個用戶進程使用的程序最大在2G，那么也就是說在程序中使用的線程不能超過2000個，在實際測試中可以發現一般來說開1930左右個線程就會收到內存不足的異常，其實這個數量是絕對夠用的，即使復雜的visual studio2013程序一般也只用了50個不到的線程。在一個進程中開啟多個線程以后，我們就可以讓一個程序能夠同一間隙能夠相對多個事情，比如可以一邊接受用戶響應一邊進行一些基本的計算。在以前處理器還處于單核的時期，也就是說在同一時間內，處理器只能單獨做一件事情。那么怎么實現之前說的多個線程同時執行呢。其實這個同時只是表面上的同時，實際上多個線程依次占用的是處理器的若干個時間片，線程輪流使用處理器資源，由于這個時間間隙非常短暫，在一個長的時間看來這個這個間隙幾乎可以忽視似乎是幾個線程同時得到了執行。并行計算不是一個很新的概念，其實它就是通過多線程把同一個任務分割成多個子任務進行并行計算的過程。我們需要手動分割單任務所依賴的算法和數據結構，放到不同的線程中去，然后通過線程同步的方法來統一匯總和處理這些線程的執行結果。之所以會需要并行計算是因為隨著我們電腦的CPU不緊緊是升級頻率而是更加側重于核心橫向擴展，我們的程序也就達不到隨著CPU Scale-out而Scale-up的能力，因此，需要調整程序的邏輯使得一段原本完整的任務也分割成多個片段同時執行，這樣就可以充分利用到多核心的優勢從而提供程序的性能。

但是線程之間切換需要時間，我們開兩個線程執行兩個任務有可能會比一個單線程執行還要慢，其實即使對于單核的處理器都不一定，因為在實際的應用中我們的任務往往不可能從完完全全一直占用處理器資源，有很多時候我們需要等待IO響應或用戶的響應，如果只是一個線程做事情的話處理器就會空閑。對于現在多核處理器來說，在同一時刻理論上可以在每一個處理器上都并行執行指令，多線程來提高運算速度就是我們可以利用的一個好方法。當然也不是說一個任務要執行20秒，我們在雙核的機器上并行執行這個任務只需要10秒了，那是因為很多時候這個任務很難劃分成兩個分支來并行執行，如果每個指令都要依靠上個指令的執行結果，那么這樣的操作很難在多個處理器上并行執行。但是，我們可以這樣想，至少如果有兩個這樣任務的話，我們就可以完全利用多個處理器的優勢來并行執行了。

根據上述的模型約束和理論基礎，本文提出一種并行計算的算法，目的是有效的調高端口之間查找到的效率，偽代碼如下：

查詢相同端口的連接

1、初始化一個rst集合，用于存儲連接信息

2、創建兩個連接集合odf1Conn odf2Conn

3、For 一個以以最大線程數為5的進行多線程對odf1Conn的集合中每一個端口進行查找

4、End For

5、定義一個i∈odf1集合

6、讓指定的odf1[i] 滿足 odf1[1] 的端口屬于打開狀態，即odf1[i] 不等于-1

7、For 一個以以最大線程數為5的進行多線程對odf2Conn的集合中每一個端口進行查找

8、End For

9、定義一個j∈odf2集合

10、讓指定的odf2[j] 滿足 odf2[j] 的端口屬于打開狀態，即odf2[j] 不等于-1

11、在計算過程中如果odf1[i] 等于odf2[j]，則滿足條件

12、將滿足條件的結果以i，j，odf2[j] 的字符串形式添加到rst集合中

13、計算完成后，返回rst集合

算法1-3 行進行初始化，對返回集合rst和連接集合odf1Conn，odf2Conn進行初始化

算法4-5 行進行多線程計算循環，并判斷odf1Conn的端口是否打開

算法6-7 行進行多線程計算循環，并判斷odf2Conn的端口是否打開

算法8-9 行進行在判斷如果odf1[i] 等于odf2[j]，則滿足條件，并將計算結果添加到rst集合中去

算法10行 返回rst計算結果

2算法驗證

這個是任意生產的的一次結果，圖表示兩組od11，odf21 中odf11 的第一號端口和odf21 的第46 號端口通過第80號線相連，odf11 的第3號端口和odf21 的第138 號端口通過第137號線相連。正常是計算是N*N，并行計算之后， 變成了N*N/m*n，mn 就是并行度，指令或數據并行執行的最大數目，提高并行度的一個顯著優點就是可以最大限度地利用計算資源或存儲資源。設置每個設備有144個端口，能連接成功的最大端口數是程序里面的變量，我們可以通過改變能連接成功的最大端口數來來對比并行計算前后時間復雜度之間的變化，因而體現并行計算是否能夠有效的減少端口之間對應的計算復雜度，是否能加入實踐的可行性。

從圖看出優化后所用的時間復雜度的優越性隨著最大端口數的增加而增加，優化前后所花費的時間差也隨著端口數量的增加而增加，在最大端口數為4的情況下優化的效果并不是很明顯，但是隨著最大端口是的逐漸提高，并行計算的優越性逐漸體現出來，理論上不考慮到進程間的相互影響運行環境等影響下，并行計算后的運行速度可以達到之前的5倍。

3結束語

本文研究了基于ODN的配線架中端口對應效率過低難以準確統計， 無法實現精確的線纜資源管理的問題，提出一種基于并行計算的優化算法，通過模擬仿真能得到優化前后配對指定端口數所花費的時間進行比較。結果表明基于ODN的并行優化算法能夠有效的減少ODN中端口配對的時間復雜度。本文提出的算法對未來機房改善的研究具有一定的借鑒作用。

參考文獻：

[1] 穆樂. 構建節能高效的通信機房管理模式[J]. 中國新通信， 2019， 21（04）：18.

[2] 呂劍鋒. Sman ODN基于RFID推動光網智能化[J]. 通信世界， 2012（24）：34-34.

[3] 魏忠誠， 張希， 陳璽，等. ODN產品質量控制探討[J]. 光通信研究， 2013（06）：28-31.

[4] 張衛斌， 關映雪. 智慧融入管道 中興通訊eODN成功破解無源光網絡發展困局[J]. 通信世界， 2012（17）：55.

作者簡介：

王宇飛（1996-）男，漢，江蘇省南京市，學歷：在讀碩士，研究方向：光通信.