基于ODN的并行優(yōu)化算法

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

關(guān)鍵詞：ODN 并行計算;c#

0引言

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

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

因此本文基于智能ODN下，提出一種odf之間光纖對應(yīng)關(guān)系的并行優(yōu)化算法，能夠有效的減少端口之間對應(yīng)的計算復(fù)雜度。

1算法思想和設(shè)計

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

ODF11∈ODF21? ? ? ?ODF12∈ODF22

時間復(fù)雜度是衡量算法執(zhí)行效率的一種標(biāo)準(zhǔn)。但是，時間復(fù)雜度不等于性能。即便在不降低時間復(fù)雜度的情況下，也可以通過一些優(yōu)化手段，提升代碼的執(zhí)行效率。即便是像10%、20%這樣微小的性能提升，也是非?？捎^的。算法的目的就是為了提高代碼執(zhí)行效率。當(dāng)算法無法再繼續(xù)優(yōu)化的情況下，我們可以通過并行計算來進(jìn)行優(yōu)化進(jìn)一步提高執(zhí)行效率。

為了利用并行計算求解一個計算問題，通?；谝韵驴紤]：1.將計算任務(wù)分解成多個子任務(wù)，有助于同時解決;2.在同一時間，由不同的執(zhí)行部件可同時執(zhí)行多個子任務(wù);3.多計算資源下解決問題的耗時要少于單個計算資源下的耗時。

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

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

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

查詢相同端口的連接

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

2、創(chuàng)建兩個連接集合odf1Conn odf2Conn

3、For 一個以以最大線程數(shù)為5的進(jìn)行多線程對odf1Conn的集合中每一個端口進(jìn)行查找

4、End For

5、定義一個i∈odf1集合

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

7、For 一個以以最大線程數(shù)為5的進(jìn)行多線程對odf2Conn的集合中每一個端口進(jìn)行查找

8、End For

9、定義一個j∈odf2集合

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

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

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

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

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

算法4-5 行進(jìn)行多線程計算循環(huán)，并判斷odf1Conn的端口是否打開

算法6-7 行進(jìn)行多線程計算循環(huán)，并判斷odf2Conn的端口是否打開

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

算法10行 返回rst計算結(jié)果

2算法驗(yàn)證

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

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

3結(jié)束語

本文研究了基于ODN的配線架中端口對應(yīng)效率過低難以準(zhǔn)確統(tǒng)計， 無法實(shí)現(xiàn)精確的線纜資源管理的問題，提出一種基于并行計算的優(yōu)化算法，通過模擬仿真能得到優(yōu)化前后配對指定端口數(shù)所花費(fèi)的時間進(jìn)行比較。結(jié)果表明基于ODN的并行優(yōu)化算法能夠有效的減少ODN中端口配對的時間復(fù)雜度。本文提出的算法對未來機(jī)房改善的研究具有一定的借鑒作用。

參考文獻(xiàn)：

[1] 穆樂. 構(gòu)建節(jié)能高效的通信機(jī)房管理模式[J]. 中國新通信， 2019， 21（04）：18.

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

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

[4] 張衛(wèi)斌， 關(guān)映雪. 智慧融入管道 中興通訊eODN成功破解無源光網(wǎng)絡(luò)發(fā)展困局[J]. 通信世界， 2012（17）：55.

作者簡介：

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