Warrens Ph.D Thesis

A Rate-Based Congestion Control Framework for
Connectionless Packet-Switched Networks

A thesis submitted to the
School of Computer Science
University College
University of New South Wales
Australian Defence Force Academy
for the degree of Doctor of Philosophy

By
Warren Keith Toomey
December 1997

Certificate of Originality
Abstract
Acknowledgments
Contents
1 Introduction
- 1.1 Connectionless Packet-switched Networks
- 1.2 Router Operation
- 1.3 Congestion in Connectionless Packet-switched Networks
- 1.4 Congestion Control Schemes
- 1.5 Factors Affecting Network Congestion
- 1.6 Scope of This Thesis
2 Existing Congestion Control Schemes
- 2.1 Jain's Congestion Survey
- 2.2 Traditional Control Schemes
- 2.3 Transmission Control Protocol
- 2.4 Network-based Congestion Control
- 2.5 Packet Discarding Mechanisms
- 2.6 Packet Queueing Mechanisms
- 2.7 Summary
3 Rate-Based Congestion Control Schemes
- 3.1 Introduction
- 3.2 Rate-Based Flow Control
- 3.3 Available Bit Rate Congestion Control in ATM Networks
- 3.4 Charney's Thesis
- 3.5 Theoretical Work
  - 3.5.1 Summary
- 3.6 Non-Service Degradation Control Schemes
- 3.7 Summary
4 A Rate-Based Framework for Congestion Control
- 4.1 Deficiencies and Remedies
- 4.2 A Rate-Based Framework: Design Considerations
- 4.3 Overview of the Framework
- 4.4 Network Layer Rate Measurement
- 4.5 Source Flow Control and Packet Admission Functions
- 4.6 Source Error Control Function
- 4.7 Destination Acknowledgment Function
- 4.8 Router Sustainable Rate Measurement Function
- 4.9 Router Packet Queueing Function
- 4.10 Router Packet Dropping Function
- 4.11 Router Congestion Avoidance
- 4.12 Router Congestion Recovery
- 4.13 Summary
5 TRUMP
- 5.1 Features of TRUMP
- 5.2 Connection Setup
- 5.3 Data Transmission
  - 5.3.1 Destination Operation
  - 5.3.2 Source Operation
- 5.4 Connection Teardown
- 5.5 Abnormal Connection Termination
  - 5.5.1 End-to-End Flow Control
- 5.6 Summary
6 RBCC - Measuring a Source's Sustainable Rate
- 6.1 Requirements of The Sustainable Rate Measurement Function
- 6.2 RBCC -- An Example Function
- 6.3 TRUMP/RBCC Operation
- 6.4 Summary
7 Comments on the Congestion Control Framework
- 7.1 The Framework as a Feedback System
- 7.2 What Constitutes a Traffic Flow?
- 7.3 What Congestion Fields are Required?
- 7.4 Transport and Network Layer Intercommunication
- 7.5 Complexity of RBCC
- 7.6 RBCC and Fair Share
- 7.7 Determination of Desired Rate
- 7.8 Bandwidth Reservation and Resource Monitoring
- 7.9 Acknowledgment Flow Problems
- 7.10 Packet Admission and Readmission
- 7.11 Summary
8 Implementing TRUMP/RBCC in the REAL Network Simulator
- 8.1 The REAL Simulator
- 8.2 Changes to the Simulator
- 8.3 Implementation of TRUMP
  - 8.3.1 TRUMP Destination Code
  - 8.3.2 TRUMP Source Code
- 8.4 Implementation of RBCC
- 8.5 Simulation of TCP in REAL
- 8.6 Measurements Obtained by The REAL Simulator
  - 8.6.1 Indicators of Network Congestion
  - 8.6.2 Other Indicators of Network Performance
- 8.7 Summary
9 Results of Simulating TRUMP and RBCC in REAL
- 9.1 Introduction
- 9.2 Description of Scenarios
  - 9.2.1 Scenario Variations
  - 9.2.2 Tabled Results
- 9.3 Scenario 1
- 9.4 Scenario 2
- 9.5 Scenario 2a
- 9.6 Scenario 3
- 9.7 Scenario 4
- 9.8 Scenario 5
- 9.9 Scenario 6
- 9.10 Scenario 7
- 9.11 Scenario 8
- 9.12 Scenario 9
- 9.13 Summary
10 Simulating Random Scenarios
- 10.1 Introduction
- 10.2 Scenario Generation
- 10.3 Abstracted Measurements
- 10.4 Highest Average Buffer Queue Length
- 10.5 Average Buffer Queue Length
- 10.6 Total Packets Lost
- 10.7 Highest Average Link Utilisation
- 10.8 Effective Bit Rate
- 10.9 End-to-end Variance
- 10.10 Inter-packet Spacing
- 10.11 ABT Caching Results
- 10.12 Summary of Results
11 Effect of Parameters on Framework Performance
- 11.1 Available Parameters
- 11.2 Measurements Made
- 11.3 Effect of Rate Quench Packets
- 11.4 Effect of Reverse ABT Updates
- 11.5 Effect of the Threshold, T
- 11.6 Effect of the Scaling Factor, $\alpha$
- 11.7 Effect of the Selective Acknowledgment Size
- 11.8 Effect of the Packet Dropping Function
- 11.9 Conclusion
- 11.10 Results with Recommended Parameters
12 Conclusion
- 12.1 Introduction
- 12.2 A New Rate-Based Control Framework
- 12.3 Framework Functions
- 12.4 Experimental Results
- 12.5 Future Work
- 12.6 Summary
A Glossary
B Verifying TRUMP with Spin
- B.1 Introduction to Spin
- B.2 The Promela Language
- B.3 Spin Verification Capabilities
- B.4 Implementing TRUMP in Promela
  - B.4.1 TRUMP's Promela Implementation
- B.5 TRUMP State Diagrams
  - B.5.1 TRUMP Sender State Diagram
  - B.5.2 TRUMP Receiver State Diagram
- B.6 Verification of TRUMP
- B.7 Summary
C TRUMP Protocol Headers
- C.1 Connection Setup
- C.2 Special Acknowledgment
- C.3 Data Transmission
- C.4 Data Acknowledgment
- C.5 Connection Termination
D Complexity of RBCC
- D.1 Introduction
- D.2 Estimation of Flows through a Router
- D.3 Size of RBCC Data Structures
- D.4 Packet Arrival for an Existing Flow
- D.5 Packet Arrival for a New Flow
- D.6 Removal of an Existing Flow
- D.7 Route Changes
- D.8 Summary
E REAL NetLanguage Files for Simulated Scenarios
- E.1 Scenario 1
- E.2 Scenario 2
- E.3 Scenario 3
- E.4 Scenario 4
- E.5 Scenario 5
- E.6 Scenario 6
- E.7 Scenario 7
- E.8 Scenario 8
F Theoretical Rate Calculation for Scenario 2
G Obtaining the REAL Simulator
References

Warren Toomey
8/28/1998