所謂混合區域網路是指在區域網路(LAN)中包含有線與無線的區域網路。當IEEE 802.11無線區域網路與乙太網路結合時即構成一個混合的區域網路，在這種情況下這兩種網路必須去共用同一個區域網路的頻寬。然而，當他們同時與外界建立TCP連線時，有線的電腦會得到大多數的頻寬，造成頻寬分配不公，這是因為TCP的流量控制機制受到”封包來回時間”(RTT)所影響。因此在共用區域網路上擁有較短RTT的電腦就可以竭盡所能的耗用頻寬，而需要較長RTT的電腦就有可能被影響。在無線網路傳輸機制上封包傳輸需要經過有線與無線的轉換，因此RTT會遠大於有線傳輸的時間。所以TCP流量控制機制在無線網路應用上效能就會非常容易受到有線傳輸的影響，造成無線網路傳輸不穩定與效能低落。
本論文提出一個新的機制稱為「動態公平頻寬分配排程器」DFQ。DFQ是運作於閘道器(Gateway)上的一個排程器(Scheduler)。它可以自動分辨區域網路上的電腦是屬於有線或者是無線的網路，並且根據不同的網路型態與每一台電腦的頻寬使用量來做動態頻寬分配。DFQ可以在不修改TCP通訊協定下，有效避免無線網路受到有線網路干擾，使無線網路運作更穩定。DFQ的機制已經在Linux作業系統中實做出來並且做了許多測試。實驗結果顯示在相同條件下沒有DFQ機制時無線網路效能會降到5%~25%，當使用DFQ後可以改善至40%~80%。此結果告訴我們DFQ是可行的，並且使得這兩種網路並存且結合得宜。

A hybrid local area network (LAN) is a LAN with wired and wireless hosts. When the IEEE 802.11 wireless LAN attached with the Ethernet LAN forms a hybrid LAN. In this situation they need to share the same LAN bandwidth. Nonetheless, when the wired hosts and the wireless hosts build TCP connection with out side Internet at the same time, the wired hosts always take the majority of bandwidth and bring about unfair bandwidth allocation. This problem is caused by the TCP flow control mechanism that is dominated by the round-trip time (RTT) property. Therefore the ones with shorter RTT tend to acquire bandwidth easier and exhaust the LAN bandwidth and the ones with longer RTT are affected easily. The RTT of wireless transmissions are much longer then that of wired transmissions because it needs transformation between wired and wireless network. Therefore the wireless TCP suffers a severe low performance problem on hybrid LAN.
This paper proposes a new scheme called “Dynamic Fair Queuing (DFQ)” that works on the gateway. DFQ can identify the host type which may be wire or wireless automatically without running signaling daemon on hosts and allocate bandwidth dynamically according to the host type and bandwidth usage of each host. It prevents the wired hosts from taking too much of LAN bandwidth and hence averts the unfairness or starvation of wireless connections and doesn’t have to modify the TCP protocol. The DFQ has been implemented and tested on Linux OS. Experiment results show that the wireless performance will drop down to 5%~25% if there is no DFQ and pull up to 40%~80% when DFQ is enabled at the same condition. These results proof that the DFQ is practicable and make wireless networks working with wired network seamless.

摘 要ii
Abstract iii
誌 謝iv
Table of Contents v
List of Figures vi
Chapter 1 Introduction 1
Chapter 2 Background 4
2.1 TCP OVERVIEW 4
2.2 TCP FLOW CONTROL 4
2.2.1 Sliding Window 5
2.2.2 Congestion Window 5
2.3 UNFAIRNESS PROBLEM 8
Chapter 3 DFQ Mechanism 12
3.1 DESIGN ALTERNATIVES 12
3.2 DFQ MECHANISM 14
3.3 POLICER ALGORITHM 15
3.3.1 Policer algorithm: Stage 1 16
3.3.1 Policer algorithm: Stage 2 18
Chapter 4 Implementation of DFQ 23
4.1 LINUX KERNEL NETWORK OVERVIEW 23
4.2 ADD QUEUE TO LINUX KERNEL 24
4.3 MANIPULATE THE DFQ 28
4.4 HOST TYPE IDENTIFICATION MECHANISM 29
4.4.1 Implementation of Host Type Identification mechanism 30
4.5 QUEUE TTL 31
Chapter 5 Experiment Result 33
5.1 EXPERIMENT PLATFORM 33
5.2 EXPERIMENT RESULT AND ANALYSIS 34
5.2.1 Transmit big size data (50Mbytes) 34
5.2.2 Transmit small size data (512kbytes) 39
Chapter 6 Relate works 42
6.1 HETEROGENEOUS NETWORKS MODEL 42
6.2 FAIR QUEUING ON WIRELESS NETWORKS 44
Chapter 7 Conclusion and Future Work 45
Bibliography 46

[1].Fu-Ming Tsou, Hong-Bin Chiou, Zsehong Tasi, “WDFQ : An Efficient Traffic Scheduler with Fair Bandwidth Sharing for Wireless Multimedia Services “, IEICE TRANS. Communications JANUARY 2000
[2].Songwu Lu, Vaduvur Bharghavan, R. Srikant, “ Fair Scheduling in Wireless Packet Networks” IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 7 NO. 4, Auguest 1999
[3].Jian-Hao and Kwan L. Yeung,“FDA: A Novel Base Station Flow Control Scheme for TCP over Heterogeneous Networkings”, IEEE INFOCOM 2001
[4].H. Balakrishnan, S. Seshan, and R.H. Katz, “Improving Reliable Transport and Handoff Performance in Cellular Wireless Networks. ACM Wireless Networks,1(4)”, December 1995
[5].E. Ayanoglu, S. Paul, et.al, “A Link-Layer Protocol for Wireless Networks”, ACM/Baltzer Wireless Networks Journal, 1:47—60, February 1995
[6].IEEE 802.11 standard, http://standards.ieee.org/getieee802/802.11.html
[7].The Daedalus Project Home Page, http://daedalus.cs.berkeley.edu/
[8].W.R. Stevens. TCP/IP Illustrated, Volume 1. Addison-Wesley, Reading, MA, Nov 1994
[9].Linux Kernel Architecture, http://kernelnewbies.org/
[10].Werner Almesberger, “Linux Network Traffic Control --- Implementation Overview”, April 23, 1999
[11].S. Floyd, and V. Jacobson, “Link-sharing and resource management models for packets networks”, IEEE/ACM Trans, on Networking, vol.3, no.4, pp. 365-86, August 1995
[12].B. Teitelbaum and T. Hanss, “QoS Requirements for Internet2”, Internet 2 Workshop, May 1998
[13].Saravanan Radhakrishnan, “Linux --- Advanced Networking Overview Version1”, August 22, 1999
[14].Bert Hubert, Gregory Maxwell, “Linux Advanced Routing & Traffic Control Howto”, December 17, 2001
[15].Iproute2 Project, http://defiant.coinet.com/iproute2/
[16].Gowri Dhandapani, Anupama Sundaresan, “Netlink Sockets --- Overview”, September 13, 1999
[17].S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. ACM/IEEE Transactions on Networking, 1(4): 397-413, August 1993.
[18].The pttcp tool Home Page, http://www.cl.cam.ac.uk/Research/SRG/netos/netx/
[19].R. Caceres and L. Lftode, The effects of mobility on reliable transport protocols, in: Proceedings of the International Conference on Distributed Computing Systems, Poznan, Poland (IEEE Press, June 1994) pp. 12-20
[20].A. DeSimone, M. C. Chuah and O.-C. Yue, Throughput performance of transport-layer protocols over wireless lans, in: Proceedings of the Conference on Global Communications(GLOBECOM)(IEEE Press, 1993) pp. 542-549
[21].V. Jacobson, “Berkeley TCP evolution from 4.3 Tahoe to 4.3 Reno”, Proceedings of the 18th Internet Engineering Task Force, University of British Colombia, Vancouver, BC, Spet. 1990.
[22].T. Bonald, “Comparison of TCP Reno and TCP Vegas: Efficiency and Fairness”, In Proceedings of PERFORMANCE’99, Istanbul, Turkey, October 1999.
[23].Claudio Casetti, Saverio Mascolo, “TCP Westwood: Congestion Window Control Using Bandwidth Estimation”, IEEE 2001
[24].Pravin Bhagwat, Partha Bhattacharya, Arvind Krishna and Satish K. Tripathi, “Using channel state dependent packet scheduling to improve TCP throughput over wireless LANs”, Wireless Networks 3 (1997) 91-102
[25].Paramswaran Ramanathan, Prathima Agrawal, “Adapting Packet Fair Queueing Algorithms to Wireless Networks”. MOBICOM 98 Dallas Texas USA 1998