UNIVERSITI PUTRA MALAYSIA

SEYED DAWOOD SAJJADI TORSHIZI

FK 2013 31

AN ADAPTIVE RATE ALLOCATION SYSTEM TO MITIGATE FAIRNESS ISSUES IN Wi-Fi MESH NETWORKS

© COPYRIG

HT UPMAN ADAPTIVE RATE ALLOCATION SYSTEM TO

MITIGATE FAIRNESS ISSUES IN Wi-Fi MESHNETWORKS

By

SEYED DAWOOD SAJJADI TORSHIZI

Thesis Submitted to the School of Graduate Studies, Universiti PutraMalaysia, in Fulfilment of the Requirements for the Degree of

Master of Science

October 2013

© COPYRIG

HT UPM

DEDICATIONS

This thesis is dedicated to:

My dearest wife, Maryam, for her whole-hearted and substantial support

And

My caring and devoted parents for their unconditional love and support

© COPYRIG

HT UPM

Abstract of thesis presented to the Senate of Universiti Putra Malaysia infulfillment of the requirement for the degree of Master of Science

AN ADAPTIVE RATE ALLOCATION SYSTEM TO MITIGATEFAIRNESS ISSUES IN Wi-Fi MESH NETWORKS

BY

SEYED DAWOOD SAJJADI TORSHIZI

October 2013

Chair: Fazirulhisyam Hashim, Ph.D.

Faculty: Engineering

Wireless Mesh Network (WMN) is a high potential networking technology thatis equipped with self-healing and self-organized capabilities. In addition to beingwidely used in the traditional applications of ad-hoc networks, WMNs are under-going rapid commercialization in many other scenarios such as broadband homeand community networking, high-speed metropolitan area networks, and enter-prise networking. To this date, a rich surge of researches involving deploymentswith thorough solutions have been conducted on WMNs. However, fair distribu-tion of network resources, especially the available bandwidth among mesh stationsis still one of the open issues for research. In WMNs, stations which are morehops away from the gateway generally suffer from higher throughput degradationand hence higher delay. Moreover, current fairness issues among simultaneous up-link and downlink flows of WLANs aggravate starvation dilemma in access layer ofWMNs. These incidents are mainly due to the unpredictable nature of IEEE 802.11protocol and its operation in contention mode. In this dissertation, a thoroughsolution based on a messaging framework and adaptive rate allocation mechanismis proposed to alleviate current fairness issues of WMNs. The proposed frameworkconsists of two main components. The first one is a lightweight messaging systemand the second one is an adaptive fair rate allocation algorithm. It is important tonote that the presented solution is independent from MAC and underlying layers.Thus, this property distinguishes it from many other related works on addressingfairness problems in WMNs. Furthermore, the ability of traffic control over UDPand TCP streams, supporting multi-radio mesh routers and restriction of internalgreedy traffic within WMNs can be regarded as the main advantages of the offered

ii

© COPYRIG

HT UPM

solution in comparison to the earlier works. The consistency of presented resultsfrom the algorithm simulation and real-life test-bed experiments substantiates theefficiency of proposed architecture in terms of achieving higher end-to-end through-put and fairness improvement more than 94% in some of the conducted scenarios.Furthermore, in the existence of any malicious activity such as UDP food or DoS(Denial of Service) attacks by mesh stations, it is feasible to block abusive usersthrough definition of appropriate policies by the offered system. This capabilityenhances the stability of any communication platform which is working based onthe presented solution to control and addressing users’ demands.

iii

© COPYRIG

HT UPM

Abstrak tesis yang dikemukakan kepada Senat Universiti Putra Malaysia sebagaimemenuhi keperluan untuk ijazah Master Sains

PENYESUAIAN KADAR SISTEM PERUNTUKAN UNTUKMENGURANGKAN ISU ADIL DALAM Wi-Fi MESH NETWORKS

Oleh

SEYED DAWOOD SAJJADI TORSHIZI

Oktober 2013

Pengerusi: Fazirulhisyam Hashim, Ph.D.

Fakulti: Kejuruteraan

Rangkaian JejaringWayarles (WMN) adalah rangkaian teknologi berpotensi tinggiyang dilengkapi dengan keupayaan pemulihan dan keupayaan mengatur sendiri.Selain digunakan secara meluas dalam aplikasi tradisional seperti rangkaian ad-hoc, WMNs juga dikomersilkan dengan pesat dalam pelbagai senario yang lainseperti rangkaian jalur lebar, rangkaian komuniti, rangkaian kelajuan tinggi dikawasan metropolitan, dan rangkaian untuk kegunaan perusahaan. Sehingga masakini, banyak kajian yang melibatkan pelaksanaan dan penyelesaian yang menyelu-ruh telah dijalankan ke atas WMN. Walaubagaimanapun, pengagihan yang adilterhadap sumber rangkaian, terutamanya jalur lebar yang sedia ada di kalanganstesen jaringan masih menjadi salah satu isu terbuka untuk penyelidikan. DalamWMN, stesen yang lebih jauh daripada laluan get biasanya akan mengalami ke-merosotan truput yang lebih tinggi dan juga kelewatan yang lebih tinggi. Se-lain itu, isu-isu kesamarataan di kalangan aliran pautan naik dan pautan turunyang berlaku secara serentak dalam WLAN memburukkan lagi dilema kebulu-ran di lapisan akses WMNs. Kejadian ini adalah disebabkan oleh sifat protocolIEEE 802.11 yang tidak menentu dan cara kendaliannya masih lagi dalam perde-batan. Dalam kajian ini, beberapa penyelesaian berdasarkan rangka kerja mesejdan mekanisma penyesuaian peruntukan kadar telah dicadangkan untuk mengu-rangkan isu kesamarataan semasa WMNs. Rangka kerja yang dicadangkan terdiridaripada dua komponen utama. Komponen pertama adalah sistem pesanan ringandan yang kedua ialah algoritma penyesuaian kadar kesamarataan. Adalah pentinguntuk diberi perhatian bahawa penyelesaian yang diutarakan adalah bebas dari-pada lapisan MAC dan lapisan dasar. Justeru, kaedah ini berbeza daripada kaedah

iv

© COPYRIG

HT UPM

lain yang digunakan untuk menangani masalah kesamarataan dalam WMNs. Se-lain itu, keupayaan kawalan trafik ke atas UDP dan aliran TCP, sokongan multiradio dan sekatan trafik terhadap sifat tamak dalaman WMNs boleh dianggapsebagai kelebihan utama penyelesaian yang ditawarkan berbanding dengan kajianyang terdahulu. Hasil yang konsisten daripada simulasi algoritma dan eksperimen-ujian sebenar mengesahkan kecekapan seni bina yang dicadangkan dalam rangkamencapai pemprosesan akhir-ke-akhir yang lebih tinggi dan peningkatan kesama-rataan lebih daripada 94% dalam beberapa senario yang telah dijalankan. Tam-bahan pula, kewujudan apa-apa aktiviti berbahaya seperti UDP makanan atauDoS (Penafian Perkhidmatan) serangan oleh stesen jaringan, boleh disekat den-gan menyekat pengguna kesat melalui definisi polisi yang sewajarnya oleh sistemyang ditawarkan. Keupayaan ini meningkatkan kestabilan platform mana-manakomunikasi yang bekerja berdasarkan penyelesaian yang dikemukakan untuk men-gawal dan memenuhi permintaan pengguna.

v

© COPYRIG

HT UPM

ACKNOWLEDGEMENTS

I would like to express my deepest gratitude to my supervisors, Dr. FazirulhisyamHashim and Dr. Kae Hsiang Kwong for their generous support and great encour-agement to conduct this research as well as their valuable comments to enhancethe quality of the dissertation.

Also, I am very grateful to Dr. Khairulmizam Samsudin as the other memberof my supervisory committee for his help and support to achieve my researchdissertation. Furthermore, I would like to appreciate Dr. David Chieng due to hisgreat cooperation and assistance during my research and thesis writing.

vi

© COPYRIG

HT UPM

I certify that a Thesis Examination Committee has met on 4 October 2013 to con-duct the final examination of Seyed Dawood Sajjadi Torshizi on his thesis entitled“AN ADAPTIVE RATE ALLOCATION SYSTEM TO MITIGATE FAIRNESSISSUES IN Wi-Fi MESH NETWORKS” in accordance with the Universities andUniversity Colleges Act 1971 and the Constitution of the Universiti Putra Malaysia[P.U.(A) 106] 15 March 1998. The Committee recommends that the student beawarded the Master of Science.

Members of the Thesis Examination Committee were as follows:

Abd. Rahman bin Ramli, PhDAssociate ProfessorFaculty of EngineeringUniversiti Putra Malaysia(Chairman)

Borhanuddin bin Mohd Ali, PhDProfessorFaculty of EngineeringUniversiti Putra Malaysia(Internal Examiner)

Mohd Fadlee bin A Rasid, PhDAssociate ProfessorFaculty of EngineeringUniversiti Putra Malaysia(Internal Examiner)

Mohd Yusoff bin Alias, PhDAssociate ProfessorMultimedia UniversityMalaysia(External Examiner)

NORITAH OMAR, PhDAssociate Professor and Deputy DeanSchool of Graduate StudiesUniversiti Putra Malaysia

Date: 19 December 2013

vii

© COPYRIG

HT UPM

This thesis was submitted to the Senate of Universiti Putra Malaysia and has beenaccepted as fulfilment of the requirement for the degree of Master of Science.

The members of the Supervisory Committee were as follows:

Fazirulhisyam Hashim, PhDSenior LecturerFaculty of EngineeringUniversiti Putra Malaysia(Chairperson)

Khairulmizam Samsudin, PhDSenior LecturerFaculty of EngineeringUniversiti Putra Malaysia(Member)

Kae Hsiang Kwong, PhDSenior Staff ResearcherWireless Communication ClusterMIMOS Berhad(Member)

BUJANG BIN KIM HUAT, PhDProfessor and DeanSchool of Graduate StudiesUniversiti Putra Malaysia

Date:

viii

© COPYRIG

HT UPM

DECLARATION

I declare that the thesis is my original work except for quotations and citationswhich have been duly acknowledged. I also declare that it has not been previ-ously, and is not concurrently, submitted for any other degree at Universiti PutraMalaysia or at any other institution.

SEYED DAWOOD SAJJADI TORSHIZI

Date: 4 October 2013

ix

© COPYRIG

HT UPM

TABLE OF CONTENTS

Page

ABSTRACT ii

ABSTRAK iv

ACKNOWLEDGEMENTS vi

APPROVAL vii

DECLARATION ix

LIST OF TABLES xii

LIST OF FIGURES xiv

LIST OF ABBREVIATIONS xvii

CHAPTER

1 INTRODUCTION 11.1 Background 11.2 Problem statement 31.3 Aims and objectives 31.4 Scope of research 41.5 Study module 51.6 Thesis organization 5

2 LITERATURE REVIEW 72.1 Introduction 72.2 Review of prevalent Wi-Fi technologies 72.3 Principles in WMN design 8

2.3.1 Multi-Radio Multi-Hop WMNs 92.3.2 Channel assignment in WMNs 102.3.3 Prominent routing mechanisms in mesh networks 12

2.4 Fairness issues in WLANs 132.4.1 Starvation problems for end-users in WLAN 132.4.2 Multi-Hop dilemma 152.4.3 Proposed solutions for multi-hop mesh networks 15

2.5 Summary 18

3 METHODOLOGY 203.1 Introduction 203.2 Wi-Fi Multi-hop chain model 213.3 System model 263.4 Offered algorithm 283.5 System architecture 31

3.5.1 Messaging system 32

x

© COPYRIG

HT UPM

3.5.2 MR structure 333.5.3 Rate control mechanism 34

3.6 Experimental setup 363.7 Conducted scenarios and simulated results 38

3.7.1 Scenario 1: UDP uplink traffic for a fixed offered load 403.7.2 Scenario 2: TCP uplink traffic for all stations 413.7.3 Scenario 3: UDP downlink traffic for a fixed offered load 423.7.4 Scenario 4: TCP downlink traffic for all stations 433.7.5 Scenario 5: UDP uplink traffic for several offered load values 433.7.6 Scenario 6: Dynamic rate allocation for UDP uplink streams 443.7.7 Scenario 7: Dynamic rate allocation for TCP and UDP streams 463.7.8 Scenario 8: HTTP and UDP contention in backhaul layer 483.7.9 Scenario 9: Restriction of internal greedy flows 493.7.10 Scenario 10: TCP/UDP traffic for uplink/downlink flows 51

3.8 Summary 53

4 RESULTS AND DISCUSSIONS 554.1 Introduction 554.2 Scenario 1: UDP uplink traffic for fixed offered load 554.3 Scenario 2: TCP uplink traffic for all stations 584.4 Scenario 3: UDP downlink traffic for a fixed offered load 604.5 Scenario 4: TCP downlink traffic for all stations 634.6 Scenario 5: UDP uplink traffic for several offered load values. 654.7 Scenario 6: Dynamic rate allocation for UDP uplink streams 684.8 Scenario 7: Dynamic rate allocation for TCP and UDP streams 704.9 Scenario 8: HTTP and UDP contention in backhaul layer 724.10 Scenario 9: Restriction of greedy flows in single station 754.11 Scenario 10: TCP/UDP traffic for uplink/downlink flows 774.12 Achievements 794.13 Summary 80

5 CONCLUSION AND FUTURE WORKS 835.1 Conclusion 835.2 Thesis contributions 835.3 Recommendations for future works 84

REFERENCES/BIBLIOGRAPHY 86

APPENDICES 92

BIODATA OF STUDENT 92

LIST OF PUBLICATIONS 93

xi