Network Planning Algorithms in CATV Networks

Presentation on theme: "Network Planning Algorithms in CATV Networks"— Presentation transcript:

1 Network Planning Algorithms in CATV Networks
博士論文計劃 所長，各位老師好，我今天要報告的題目是、有線電視網路的設計與管理之研究。 Kuo-Wei Peng PhD. Student Department of Information Management National Taiwan University 6/20/2006

2 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

3 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

4 Introduction Overview Research Scope Research Background
1.首先介紹有線電視網路的技術與架構。 其次探討在有線電視網路上提供雙向服務，如Internet Access時，所面對的問題。 最後，我們從網路規劃與容量管理的角度，將相關研究逐一分類。 Introduction of CATV Communication Networks

5 Overview 有線電視網路已經廣泛使用在各個地區。 在有線電視網路上，提供雙向數位服務是可行的。 有線電視網路的優點：
高頻寬 高覆蓋率 易於擴充 有線電視網路適於作為資訊基礎建設中的一部份。

6 Overview 建構一個服務品質符合要求的有線電視網路是不容易的。 政府法規再加上各類新式服務的興起，這個工作變得更複雜而不易預測。
雙向服務的通訊品質如何滿足。 再加上網路成本的考量，這個問題變成了一個網路最佳化問題。

7 Overview 傳統的網路規劃方法，建構的網路品質有賴於網路規劃者的經驗
必須滿足所有通訊品質的限制 如何降低所需的成本 本論文的目標，在以最低的成本，建構符合服務品質要求的有線電視網路。

8 Research Scope 有線電視網路規劃問題的數學模型的建立 單層網路解題程序 多層網路解題程序 數學模型的建立 數學方程式的調整
對偶問題的轉換 單層網路解題程序 解題程序 相關參數的影響 解題過程中參數的設定與調整 多層網路解題程序 分群演算法 次層網路的頭端(下節點, drop points)的選擇演算法

9 Research Background CATV Communication Network Technology
Network Architecture Noise-funneling effect Traditional Network Planning Methods Research Methods Mathematical Programming Geometric Programming

10 CATV Communication Network Technology
有線電視網路的網路架構如圖1-1所示：基本上是一個tree-and-branch的結構。 在這個樹狀結構下，一般分成四段：headend(頭端）、trunk network、distribution network、drop line。 頭端提供訊號來源，在雙向環境中，例如提供internet access服務時，作為有線電視網路與網際網路的gateway，並提供存取控制的功能。 Trunk netowork提供長距離、且確保信號品質的傳輸服務，為了維持其信號品質，利用放大器等網路元件是必要的，但這也衍生出信號失真等相關問題。 在distribution network與drop line的部份，是網路系統的末端，負責將信號配送到用戶家中，這部份與trunk network相較，分支數目多是重要的特性，不過在雙向網路環境下也導致了noise funnelling effect，這部份我們後面還會在加以說明。 Figure The Network Structure of CATV Networks

11 Noise Funneling Effect
4.Media-access-control的設計，由於有線電視網路的用戶是共享同一條傳輸媒介，因此如何有秩序且有效率的讓所有的用戶共享傳輸媒介，對於系統的performance有很大的影響。這部份的研究相當多，我們在報告的第三部份有更詳細的說明。 5.Noise funnelling effect：什麼是~？看圖，當用戶端發送資料時，這些信號隨著樹狀結構的網路向頭端集中，當雜訊不斷的集中之後，系統頭端所觀察到的雜訊將會相當明顯，此一效應稱為Noise funnelling，這也是網路工程師在設計雙向服務時所必須考慮的問題。 Figure1-7. Noise-funnelling effect

12 CATV Network Planning --- Traditional Approaches
製圖 幹線系統設計 餽線系統設計 反向系統設計 一般有線電視公司在設計網路時，大致分為四個步驟：第一個步驟是製圖，先根據地形地物將服務區域當中，用戶與道路的位置，可能擺放機房的地點加以標示。 接著設計主幹系統，我們可以看下一張圖：

13 幹線系統設計 Figure 1-8. 頭端幹線系統 幹線系統的設計考慮從頭端出發，到每一個餽線系統之間，如何配置纜線與放大器等元件，以維持餽線系統所接收到的信號品質，是符合技術規範要求的。相關的參數計算，我們以上圖的放大器一為例，此一放大器的目的，在於回復信號經過2500英尺後的衰減，因此，如果信號從頭端到放大器一，在220/450Mhz的衰減值為10/20dB，則此放大器必須能將信號恢復，也就是讓信號回到29/32dB。

14 餽線系統設計 Figure 1-9 餽線系統的設計在於每個分接點的位準，必須落在規範的10-17dBmV之間，因此，設計者必須計算從幹線橋接器下來的信號在每個分接點是否符合要求，若否，則分接點必須要將位準降低，以上圖來說，tap 1的輸入訊號為36.2/39.5，為了讓輸出訊號合乎規範，tap 1的分接信號損失為23dB，所以輸出點的位準為13.2/16.5dBmV。

15 Concluding Remark It is difficult to design an CATV network systems
Intensive computational work. Number of possible solutions is very large. CAD tools for CATV network design To help designer to reduce the overhead of computational work. To track the signal quality and to make sure the end-to-end signal quality is feasible. Unable to suggest or create a good design of CATV system The quality of design is still relied on the experience and expertise of the designers.

16 Research Methods Mathematical Programming Geometric Programming Method
Steepest Descent Method Enhanced Steepest Descent Method Surrogate Functions Projection Method Integer Programming Linear Relaxation

17 Geometric Programming Method
Formulation of the Primal Problem

18 Geometric Programming Method
Formulation of the Dual Problem

19 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

20 Problem Formulation Mathematical Formulation of the CATV Network Planning Problem Reformulation of the original problem The Dual Problem

21 Mathematical Formulation and Network Optimization
Basic ideas: formulate the network and try to optimize it. 有相關學者嘗試以網路最佳化的方法，解決此一複雜的設計問題。基本的想法是，能否對有線電視網路設計，建立一個可解決的數學模式，並利用網路最佳化等數學方法，得到成本最低的網路設計。 Si為輸入的訊號， Ni為輸入的雜訊， S0為輸出訊號，而 N0則為輸出的雜訊。 Fi為該元件的雜訊參數， αi為纜線分割參數， Ai為纜線衰減參數

22 Performance Requirements
Performance requirements in downstream CNR (Carrier to Noise Ratio) ≧43dB X-MOD (Cross Modulation ) ≦-46dB CSO (Composite Second Order) ≦-53dB CTB (Composite Triple Beat) ≦-53dB 相關的信號要求包括了CNR、X-MOD、CSO、以及CTB，這些是設計的限制。

23 Problem Formulation Problem description Given : Determine:
downstream performance objectives upstream performance objectives specifications of network components cost structure of network components number and position of endusers terrain which networks will pass through and the associated cost Determine: routing allocation of network components operational parameters (e.g., gain of each amplifier) 此一問題是在給定所需的上下行信號要求、網路元件的規格以及成本、終端使用者的位置與數量、以及網路所可能經過的區域與相關成本， 找出網路的路徑規劃、網路元件的配置位置、以及運作的參數，如各個放大器的增益等。

24 Problem Formulation Features Nonlinear problems
Hard to solve directly by standard methods Some technique needed Problem Decomposition Stiner Tree Problem Network Optimization Geometric Programming Posynomial form Gradient-based Optimization 此一問題數學模式有謝鴻基、管志峰等人建立後，分析問題的特徵，發現此一問題是非線性規劃問題，用標準的數學規劃方法，如牛頓法，是很難直接解決的。因此，該研究利用了幾種數學技巧將問題逐一解決。首先是將原問題分割，將路徑規劃問題先利用其他方法解決，此一路徑規劃問題為stiner tree問題，作者利用二種stiner tree的演算法解決。 在剩下的的網路最佳化問題，經過適當的調整，發現原問題符合posynomial form，可以利用幾何規劃法將原問題的非線性限制解除，轉換成一個線性規劃問題。 經過轉換後的問題，利用線性規劃的最佳化方法，求得最佳解。

25 Reformulation of the CATV Network Design Problem
Surrogate Function Surrogate function of the objective function Surrogate functions of the constraints

26 Surrogate function of the objective function
Original objective function Surrogate function of the objective function

27 Surrogate functions of the constraints
Original Constraints for X-Mod Surrogate function for X-Mod

28 Surrogate functions of the constraints
Figure 2-2. SURROGATE FUNCTIONS OF X-MOD, CTB, AND CSO Figure 2-3. Comparison of functions for X-MOD

29 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

30 Single-Layered Solution Procedure and Computational Experiments
Analysis of Starting Points Analysis of Initial Step Size Analysis of Computing Time

31 Solution Procedure

32 The Penalty Function Where

33 Comparison of Gradient Methods
Figure 3-2. Comparison of Solution Quality

34 Analysis of Starting Points
Figure 3-7. Comparison of starting point: network example 3.

35 Analysis of Starting Points
Figure3-8. Comparison of starting point: data for network example 3

36 Analysis of Initial Step Size
Figure 3-7. Comparison of starting point: network example 3.

37 Analysis of Initial Step Size
Figure Comparison of initial step size: data for network example3

38 Analysis of Initial Step Size
Initial Step Size vs. Number of Nodes on Steiner Tree Constructed

39 Analysis of Initial Step Size
Initial Step Size vs. Penalty Parameter J

40 Adjustment Procedure for Initial Step Size and Penalty parameter J
Initial Step Size vs. Number of Nodes on Steiner Tree Constructed Set initial step size ss=10^-k: If #(tree)<2, k=2 Else If #(tree) < 7, k=3 Else if #(tree) < 25, k=4 Else k=6; Set J=1; X^2 == 0 Set J=10*J, k=k+1, Compute the optimal End

41 Analysis of Computing Time
Figure Number of Network Users versus Computing Time

42 Analysis of Computing Time
Figure Network Size versus Computing Time

43 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

44 Multi-Layered Solution Procedure and Computational Experiments
Adaptive Placement Algorithms for Drop Points Conclusion

45 Multi-layered Solution Procedure: Concept
Figure 階層式規劃：第一層

46 Multi-layered Solution Procedure: Concept (Cont.)
Figure 階層式規劃：第二層

47 Modified Agglomerative Hierarchical分群演算法
將所有網路使用者各自為一群，此時所有使用群的半 徑為0。 建立一距離矩陣，記錄所有使用群間的距離。 找到距離矩陣中，距離最近的二個使用群i與j。 計算i與j合併後的使用群半徑為R’，比較半徑R’與R。若R’>R，則程式結束。 若R’<R，則合併使用群i與j為使用群i’，並更新距離矩陣。 回到步驟3.

48 Network Example for Clustering
Figure 4-4. Network Example for Clustering

49 Network Example after Clustering
Figure 4-5. Network Example after Clustering

50 Adaptive Placement Algorithms for Drop Points
Figure 4-7. Different placement for drop points

51 Comparison of Network cost
Centroid Placement vs. Near-HE No one is good for all clusters Adaptive placement algorithm for drop points Globally adaptive placement algorithm Partially adaptive placement algorithm

52 Global Adaptive placement algorithm for drop points
步驟一：採用分群演算法，將所有節點分成多個使用 群。 步驟二：以重心為下一層的下節點，計算網路的總體 成本。 步驟三：考慮各個使用群，以不同選取策略計算網路 總體成本，選擇最低成本的選取策略為該使用群的下 節點。 步驟四：重複步驟三，直到所有使用群都被考慮過為 止。

53 Layer 1 network topology
Figure Layer 1 network topology for different placement of drop points

54 Partially Adaptive Placement algorithm
Partially Adaptive placement algorithm for drop points 步驟一：採用分群演算法，將所有節點分成多個使用群。 步驟二：以重心為下一層的下節點，計算網路的總體成本。 步驟三：選擇任一終端節點所代表的使用群，以不同選取策略計算網路總體成本，選擇最低成本的選取策略為該使用群的下節點。 步驟四：重複步驟三，直到所有第一層網路的終端節點都被考慮過為止。

55 Comparison Adaptive placement is better than both Centroid-based and NearHE-based placement. Global Adaptive algorithm is better than Partial Adaptive algorithm. However, it spends more time.

56 Conclusion Multi-layered solution procedure Clustering
To separate the large network into several small networks that can be solved by single-layered solution procedure. The placement of drop points Different placement algorithms for different total costs. Globally adaptive and Partially adaptive

57 Outline Introduction Problem Formulation
Single-Layered Solution Procedure and Computational Experiments Multi-Layered Solution Procedure and Computational Experiments Conclusion and Future Work 40 篇 references 有線電視網路的技術與網路架構介紹 傳統有線電視網路，轉型為雙向通訊網路的相關議題。 有線電視網路的網路規劃議題 傳統規劃有線電視網路的方法 如何以電腦輔助設計軟體提升傳統規劃方法 以網路最佳化的方法來尋找滿足品質要求的網路規劃解。 MAC層的設計 有線電視網路的特徵 如何共享upstream？ Minislot Allocation Problems MAC層之上的服務議題 TCP over CATV network 多媒體服務與服務品質的控制 系統復原問題，主要談的是ranging problem。 未來研究方向，整合過去的文獻，分析此一研究領域可能的研究方向。

58 Conclusion and Future Work
Mathematical Model Mathematical formulation for the CATV network planning problem is constructed. The mathematical formulation is re-formulated to conform the posynomial form. By applying the Geometric Programming Method, the dual problem is formulated. Single-layered solution procedure Gradient-based methods Steepest descent method Enhanced steepest descent method Initial value for dual variables Initial step size Adjustment procedure for Initial step size and penalty parameter J. Analysis of computing time

59 Conclusion and Future Work
Multi-layered solution procedure Clustering Modified agglomerative hierarchical clustering algorithm Placement of drop points Different placement strategy Adaptive placement algorithm Global adaptive Partial adaptive

60 Future Work Locally adjustment of network parameters may improve the total cost of networks. How to apply our work to CATV networks with more different constraints and cost structure Multimedia applications Network expansion problems Hybrid network elements Hybrid Fiber-Optical(HFC) network model Other possibility.

61 Q & A <Keep  and patient!>