대역폭, 전송 지연 곱을 적용한 노드 게인 스코어에 기반한 최대 힙 오버레이 멀티캐스트 트리 구성 방안 = Max-Heap Overlay Multicast Scheme Based on Bandwidth-Latency-Products’ Node Gain Scores

다국어 초록 (Multilingual Abstract)

The Node Gain Scores (NGSs), used as a basis for shaping the max-heap overlay, are arbitrarily determined by the respective bandwidth-latency-products. Constructing a max-heap-form overlay tree governed by the magnitudes of individual Node Gain Scores (NGSs), each earned as a synergy of the discrepancy ratio of the bandwidth requested with respect to the estimated available bandwidth, and the latency discrepancy ratio between the nodes and the source node, plays a great role in reducing a vital induced packet loss caused by, otherwise, the schemes which do not consider these parameters on placing the nodes on the overlay trees.
It is, here in this work, proposed that each node to be positioned according to the NGS it earns from a function governed by the four main influencing parameters - the estimated available bandwidth, Ba; the individual node's requested bandwidth, Br; the proposed node latency to its prospective parent, Lp; and the suggested best latency as advised by the source node, Lb. The NGS of each node is pre-calculated as an integrated measure from a fraction of the bandwidth discrepancy ratio (BDR) and that of the latency discrepancy ratio (LDR) with the weights of α and β=(C-α), respectively, and with arbitrary chosen α ranging between 0 and C, that is 0 ≤ α ≤ C, and β = C - to α make sure that the NGS values, used as node IDs, maintain a good possibility of uniqueness and a good balance between the BDR and the LDR - whichever is the most critical factor and vice versa.
The constant C is, hence, chosen depending on the expected unique Node_IDs desired. A max-heap-form tree is constructed with an assumption that all the nodes possess, as it must practically be, NGS less than the source node. To maintain a sense of load balance, the children of each level's siblings are evenly distributed such that a node can not accept a second child, and so on, until all its siblings able to do so, have already acquired the same number of children, and that is so logically done from left to right in a conceptual overlay tree.
The records of the pair-wise approximate available bandwidths as measured by a pathChirp scheme at individual nodes are maintained and the evaluation measures as compared to other schemes like BASE, TBCP, and HMTP have been conducted.
The failure of the constant, variable, and instantaneous bit rates (CBR, VBR, IBR) approaches under the paradigm of the traditional TCP/UDP mechanism have discouraged to be used due to the verified dynamicity of such mechanisms. When a moderate sized overlay multicasting group is under worst case consideration, this new scheme seems to generally perform better in terms of trade-off between packet delivery ratio which means a reduced packet loss; the maximum link stress; the acceptable control overhead; and the reasonable end-to-end delays.

국문 초록 (Abstract)

노드 게인 스코어(NGSs: Node Gain Scores)는 최대힙 오버레이 구성을 위한 기초가 되며 각 대역폭과 전송 지연의 곱에 의해 결정된다. 즉, 노드 게인 스코어는 예상 가용 대역폭과 노드 에서 요청한 대역폭간의 비율과 소스 노드와 일반 노드들간의 전송 지연에 의해 결정된다. 최대 힙 형식의 오버레이 트리의 구성은 각각의 노드 게인 스코어의 크기에 의존하며 이를 고려하지 않는 다른 방식에 의해 노드를 배치할 경우 발생할 순 있는 패킷의 손실을 줄이는데 큰 역할을 한다.
본 논문에서는 각각의 노드들을 네 종류의 주요 변수에 의존하는 노드 게인 스코어에 의해 배치하는 방안을 제안하였으며 그 변수는 다음과 같다.
- 예상 가용 대역폭 Ba; 개별 노드의 요청 대역폭 Br; 부모 노드에 대한 노드의 전송 지연 Lp; 소스 노드가 권장하는 최상의 전송 지연 Lb. 개별 노드의 노드 게인 스코어 값은 BDR (Bandwidth Discrepancy Ratio)와 가중치 α 와 β=(C-α) 를 이용하는 LDR (Latency Discrepancy Ratio)을 결합하여 미리 계산되며 α 는 0 과 C 사이의 임의의 값을 가진다. 더불어 노드 게인 스코어 값은 가장 큰 영향을 미치는 BDR과 LDR값이 적절히 반영되도록 하여 유일한 값을 가지도록 유지되며 따라서 노드의 ID로 사용된다.
상수 C는 유일한 노드 ID를 보장할 수 있도록 설정한다. 최대 힙 형식 트리에서 모든 노드들의 노드 게인 스코어 값은 소스 노드의 노드 게인 스코어 보다 작은 값을 가지고 있다는 가정을 이용하여 구성된다. 그리고 트리 각 레벨의 Sibling 노드들은 out-degree의 여유가 있는 경우 동일한 수의 자식 노드들을 가지도록 자식노드들의 위치를 정하여 트리의 부하 균형을 유지한다.
개별 노드에서 pathChirp을 이용하여 측정한 가용 대역폭의 기록들을 유지하고 BASE/TBCP/HMTP 와 같은 다른 시스템과의 비교를 통하여 성능 평가를 실시하였다.
전통적인 TCP/UDP환경에서 CBR(Constant Bit Ratio), VBR(Variable Bit Ratio)와 IBR(Instantaneous Bit Ratio)를 이용한 대역폭의 측정은 위 방안들의 역동성(Dynamicity)로 인해 원하는 결과의 도출이 쉽지 않다. 적당한 크기의 오버레이 멀티캐스트 그룹이 최악의 상태에 있을 경우 제안한 기법은 패킷 전달율(Packet Delivery Ratio), 최대 링크 부하(Maximum Link Stress), 제어 오버헤드(Control Overhead)와 전송 지연(End-to-End Delay) 측면에서 다른 방안에 비해 더 잘 동작하는 것을 보여준다.

목차 (Table of Contents)

• Chapter 1. Introduction = 3
• 1.1 General Introduction and Background = 3
• 1.2 Divisions of Multicast Routing Trees Algorithms = 7
• 1.3 Overview and Reason for Overlay Multicast = 8
• 1.4 Why Max-Heap Overlay Form? = 9
• Chapter 2. Related Works = 14
• 2.1 Preamble = 14
• 2.2 Bandwidth Dependent Overlay Multicast Scheme = 14
• 2.2.1 Summary of the BASE Scheme = 16
• 2.2.2 Fundamentals and Data Structure in BASE = 17
• 2.2.3 Group Join and Tree Maintenance in BASE = 18
• 2.2.4 Performance Evaluation, Comparison & Conclusion = 20
• 2.3 Available Bandwidth Estimation Tools = 22
• 2.3.1 pathChirp Bandwidth Estimator = 22
• 2.3.2 Spatio-Temporal Available Bandwidth (STAB) Estimator = 28
• 2.4 Overlay Multicast Induced Packet Loss = 30
• Chapter 3. Preliminary, Research Approach & Methodology = 32
• 3.1 The Problem Statement = 32
• 3.2 Constant, Variable and Instantaneous Bit Rates’ Approaches = 33
• 3.2.1 Introduction = 33
• 3.2.2 Function of Network Simulator = 37
• 3.2.3 CBR, VBR, and IBR = 38
• 3.2.3.1 Constant Bit Rate (CBR) = 38
• 3.2.3.2 Variable Bit Rate (VBR) = 39
• 3.2.3.3 Constant Bit Rate vs. Variable Bit Rate = 39
• 3.2.3.4 Instantaneous Bit Rate (IBR) = 40
• 3.2.4 Simulation Topology for CBR, VBR, IBR = 40
• 3.2.5 TCP Dynamics = 41
• 3.2.6 Simulation Results = 44
• 3.2.6.1 Slow Start Phase and the Congestion Avoidance Phase = 44
• 3.2.6.2 Steady State Phase = 45
• 3.2.6.3 TCP Dynamics = 45
• 3.2.6.4 Instantaneous Received Bit Rates = 46
• 3.2.7 Conclusion = 47
• 3.3 Selected Approach to the Problem = 48
• Chapter 4. Bandwidth-Latency-Product Measures (BLPMS) = 51
• 4.1 Introduction = 51
• 4.1.1 BLPM Scheme Overview = 51
• 4.1.2 Related Works = 54
• 4.1.2.1 Preamble = 54
• 4.1.2.2 Available bandwidth based overlays = 56
• 4.1.2.3 Fundamental Max-Min-Heap/Rate Overlays = 58
• 4.2 Bandwidth-Latency-Product Formulation and Interpretation = 59
• Chapter 5. NGS-Based Max-Heap Overlay Multicast Scheme = 66
• 5.1 Limitations of Bandwidth-Only-Based Scheme = 66
• 5.2 The Proposed NGS Scheme = 66
• 5.3 Node Gain Score (NGS) Function = 67
• 5.4 Logical Member Positioning in NGSs Based Overlay = 69
• 5.4.1 Max-Heap Form Overlay Tree Construction = 69
• 5.4.2 Overlay Membership Based on NGSs = 71
• Chapter 6. Performance Evaluation = 76
• 6.1 Simulation Setup = 76
• 6.2 Simulation Results and Inference = 76
• Chapter 7. Conclusion, Discussion and Possible Future Direction = 89
• 7.1 Conclusion = 89
• 7.2 Discussion = 89
• 7.3 Possible Future Direction = 90
• References = 91
• (국문초록) = 104
• Acknowledgements = 106