隨著網際網路(Internet)的發展，各種基於網路的通訊、服務等日益普及，網路傳輸的效率成為一項重要的議題。網路編碼(network coding)為近來相當具有價值的一個研究主題，其主要研究範疇為可應用於網路傳輸之資料編碼理論，適當地將網路編碼應用於資料傳輸中，將有助於使效率最佳化。本論文提出了封包遺失率調整式網路編碼機制(loss-rate sensitive coding, LRC)，並將此機制應用於傳輸層，目的為使頻寬資源能夠最有效地應用。目前最常被使用的傳輸層協定分別為傳輸控制協定(transmission control protocol, TCP)與使用者資料封包協定(user datagram protocol, UDP)，傳輸控制協定(TCP)可以確保資料的完整性，常應用於各種需要可靠傳輸的場合，其使用的機制為重送遺失的資料封包。現行傳輸控制協定(TCP)的傳送機制，將造成額外的頻寬浪費，本論文提出之封包遺失率調整式網路編碼機制(LRC)將可用於改善此現象。使用者資料封包協定(UDP)多應用於允許部分封包遺失的傳輸，多媒體串流為代表應用之一，封包遺失率調整式網路編碼機制(LRC)可用於提升多媒體串流中關鍵影格(keyframe)的傳輸正確率，進而達到較好的串流資料品質。本論文針對上述兩大應用場景，提出兼具相容性與實作可行性的解決方案。

Communications and services over the Internet are gradually playing an important role in our daily life today. As a result, the efficiency of network has became an important issue. Network coding is an application field in coding theory. It is aimed to optimize network efficiency and has received much research attention in recent years. This thesis proposed the loss-rate sensitive coding, LRC, and showed its applications in transport layer. Transmission control protocol, TCP, and user datagram protocol, UDP, are two popular transport layer protocol today.TCP can provide reliable data transmission. It guarantees the completeness of data by retransmitting lost segments. But it also wastes bandwidth resources by its communication overhead in some conditions. With LRC scheme, the communication overhead can be minimized. UDP is usually applied on the transmission which tolerates some packets loss. Media streaming is one of typical application of UDP.
LRC scheme can help improve the deliver rate of keyframes, which will make the quality of streaming data better. Based on the two application scenario above, this thesis proposed implementable and compatible solutions with LRC.

Contents
Chinese Abstract . . . I
English Abstract . . . II
Contents . . . III
List of Figures . . . VI
List of Tables . . . VIII
1 Introduction . . . 1
1.1 Network Coding . . . 2
1.2 Transmission Control Protocol . . . 3
1.3 Media Streams . . . 5
1.4 Challenges . . . 6
2 Related Works . . . 7
2.1 Network Coding . . . 7
2.2 TCP Congestion Control Mechanism Review . . . 8
2.3 TCP Selective Acknowledgment . . . 9
2.4 Keyframe Scheme in Media Streams . . . 10
2.5 Keyframe Redundancy . . . 11
2.6 Packet Loss Models . . . 11
3 Loss-rate Sensitive Network Coding . . . 13
3.1 Transmission Model . . . 13
3.2 De nitions and Notations . . . 14
3.3 Coding Bu er . . . 14
3.4 Normal Transmission . . . 17
3.5 Recovery of Lost Data Blocks . . . 18
3.6 Coding Coe cient . . . 19
3.7 Encoding Procedure . . . 20
3.8 Decoding Procedure . . . 21
4 TCP/LRC Mechanism . . . 23
4.1 Segment Format . . . 23
4.2 Connection Establishment . . . 24
4.3 Sender Procedures . . . 26
4.4 Receiver Procedures . . . 28
4.5 Congestion Control . . . 30
5 LRC Streaming Framework . . . 32
5.1 Overview . . . 32
5.2 Data Format . . . 33
5.3 Procedure of Stream Source . . . 35
5.4 Procedure of Playback Peer . . . 36
6 Performance Evaluation . . . 39
6.1 TCP/LRC . . . 39
6.2 LRC streaming framework . . . 43
7 Conclusions . . . 46
7.1 Coding Scheme . . . 46
7.2 Transmission Control Mechanism . . . 47
7.3 Media Streams . . .  47
7.4 Future Works . . . 48
Bibliography . . . 49
Appendix A: An E cient Transmission Control Mechanism with Loss-rate Driven Network Coding . . . 52
Appendix B: Loss-rate Driven Network Coding for Key-frame Redundancy in Media Streams . . . 63

List of Figures
1.1 Increase of TCP Congestion Window . . . 4
2.1 The Gilbert-Elliot Bit-error-rate Model . . . 9
2.2 The frame sequence of MPEG video stream . . . 10
3.1 State diagram of proposed LRC mechanism . . . 14
3.2 Both sender and receiver have a cyclic queue with same size, when transmitting under normal condition, the access pointers of two cyclic queue should move at the same rate . . . 19
3.3 When data block loss occurs, the position access pointer will be incompatible, and there may be out-of-ordered blocks in receiver's queue . . . 19
3.4 The amount of lost blocks recovered by coded blocks, performing decode operations can get the original blocks . . . 20
4.1 TCP/LRC Procedures in Sender Side . . . 28
4.2 TCP/LRC Procedures in Receiver Side . . . 30
4.3 Flow Chart of TCP/LRC Transmission Signal Module . . . 31
5.1 State Based Model for Determination of Frame Loss Reason . . . 38
6.1 Comparison of the exact transmitted segments with the bit error rate increased after each round . . . 41
6.2 Comparison of TCP/LRC and TCP/NC by the amount of transmitted data, in bytes . . . 42
6.3 Comparison of TCP/NC and TCP Reno by the amount of transmitted data, in bytes . . . 43
6.4 Comparison of TCP/LRC and TCP Reno by the amount of transmitted data, in bytes . . . 43
6.5 Comparison of TCP/LRC and TCP/NC by the amount of coded segments . . . 44
6.6 Simulation results of LRC streaming framework . . . 45

List of Tables
3.1 Terms in LRC Description . . . 15
3.2 Notations in LRC Description . . . 16
4.1 TCP Segment Header . . . 25
4.2 Flags in TCP Segment Header . . . 26
5.1 User Datagram Structure . . . 33
5.2 User Datagram with Additional Fields for LRC Streaming Framework . . . 34
5.3 Path-status Metrics . . . 35
6.1 TCP/LRC Simulation Setting Pro les . . . 41

[1] Rudolf Ahlswede, N. Cai, S. Y. Li, and R. W. Yeung: Network information flow, IEEE Transactions on Information Theory, 46, 1204-1216 (2000)
[2] Jingyun Feng, Zhi Liu, and Yusheng Ji: Wireless channel loss analysis - a case study using WiFi-Direct, IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), 244-249 (2014)
[3] Christos Gkantsidis, and P.R. Rodriguez: Network coding for large scale content distribution, 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE (INFOCOM), vol. 4, 2235-2245
(2005)
[4] Yansi Cao, Jun Wu, and Yan Ma, Key-Frame Redundancy Transmitting Algorithm for Streaming Media Transmission, IEEE 12th International Conference on Computer and Information Technology (CIT), 931-935, 2012
[5] Yi-Cheng Chan, and Ya-Yi Hu, Adaptive Network Coding Scheme for TCP over Wireless Sensor Networks, International Journal of Computers, Communications and Control 8.6, 800-811 (2013)
[6] Gerhard Hasslinger, and Oliver Hohlfeld: The Gilbert-Elliott Model for Packet Loss in Real Time Services on the Internet, Measuring, Modelling and Evaluation of Computer and Communication Systems (MMB), 14th GI/ITG Confer-ence, 1-15 (2008)
[7] Yu-Hsuan Ho, Wei-Ren Chen, and Chia-Wen Lin, A rate-constrained key-frame extraction scheme for channel-aware video streaming, International Conference on Image Processing (ICIP'04), 2004
[8] Jon Postel, RFC793, Transmission Control Protocol (1981)
[9] Sachin Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft: XORs in the air: practical wireless network coding, IEEE/ACM Trans. Netw. 16: 3, 497-510 (2008)
[10] Oliver Hohlfeld: Stochastic packet loss model to evaluate QoE impairments, PIK-Praxis der Informationsverarbeitung und Kommunikation, 32: 1, 53-56
(2009)
[11] MinJi Kim, T. Klein, E. Soljanin, J. Barros, and M. Medard: Modeling Network Coded TCP: Analysis of Throughput and Energy Cost, arXiv preprint
arXiv:1208.3212 (2012)
[12] MinJi Kim, M. Medard, and J. o. Barros: Modeling network coded TCP throughput: A simple model and its validation, Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and
Tools, 131-140 (2011)
[13] Shuo-Yen Robert Li, R. W. Yeung, and N. Cai: Linear network coding, IEEE Transactions on Information Theory, 49, 371-381 (2003)
[14] Matt Mathis, J. Mahdavi, S. Floyd, and A. Romanow, RFC 2018, TCP Selective Acknowledgment Options (1996)
[15] K. Ramakrishnan, S. Floyd, and D. Black, RFC3168, The addition of explicit congestion noti cation (ECN) to IP (2001)
[16] Neil Spring, D. Wetherall, and D. Ely, RFC3540, Robust Explicit Congestion Noti cation (ECN) Signaling with Nonces (2003)
[17] William Stallings, Handbook of computer communications standards, Vol. 1: the open systems interconnection (OSI) model and OSI-related standards,
Macmillan Publishing Co., Inc. (1987)
[18] Jay Kumar Sundararajan, S. Jakubczak, M. Medard, M. Mitzenmacher, and J. Barros: Interfacing network coding with TCP: an implementation, arXiv preprint arXiv:0908.1564 (2009)
[19] Jay Kumar Sundararajan, D. Shah, M. Medard, S. Jakubczak, M. Mitzenmacher, and J. Barros: Network coding meets TCP: Theory and implementation, Proceedings of the IEEE, 99: 3, 490-512 (2011)
[20] Jay Kumar Sundararajan, D. Shah, M. Medard, M. Mitzenmacher, and J. Barros: Network coding meets TCP, IEEE INFOCOM, 280-288 (2009)
[21] Yasuhiro Yamasaki, Hideyuki Shimonishi, and Tutomu Murase: Statistical estimation of TCP packet loss rate from sampled ACK packets, IEEE Global Telecommunications Conference, GLOBECOM, Vol. 1, 276-280 (2005)
[22] Zhen Zhang: Linear Network Error Correction Codes in Packet Networks, IEEE Transactions on Information Theory, 54, 209-218 (2008)