Contents

• 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.3.1 Sliding Window Flow Control
    • 2.3.2 Sliding Window Congestion Control
    • 2.3.3 Retransmission Timer Deficiencies
    • 2.3.4 TCP Vegas
    • 2.3.5 Summary
  • 2.4 Network-based Congestion Control
    • 2.4.1 ICMP Source Quench
    • 2.4.2 The Dec Bit Mechanism
    • 2.4.3 The Q-Bit Mechanism
    • 2.4.4 Summary
  • 2.5 Packet Discarding Mechanisms
    • 2.5.1 Random Drop
    • 2.5.2 Random Early Detection
    • 2.5.3 Summary
  • 2.6 Packet Queueing Mechanisms
    • 2.6.1 Nagle's Fair Switching
    • 2.6.2 Fair Queueing
    • 2.6.3 Summary
  • 2.7 Summary
• 3 Rate-Based Congestion Control Schemes
  • 3.1 Introduction
  • 3.2 Rate-Based Flow Control
    • 3.2.1 NETBLT
    • 3.2.2 XTP
    • 3.2.3 VMTP
    • 3.2.4 Summary
  • 3.3 Available Bit Rate Congestion Control in ATM Networks
    • 3.3.1 BECN
    • 3.3.2 PRCA
    • 3.3.3 EPRCA
    • 3.3.4 Summary
  • 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.1.1 End-to-End Control Mechanisms
    • 4.1.2 Congestion Detection Schemes
    • 4.1.3 Router Procedures
    • 4.1.4 Packet Admission Mechanisms
  • 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.1.1 Implicit and Explicit Connection Setup and Teardown
    • 5.1.2 Connection Identifiers
    • 5.1.3 Selective Retransmission
    • 5.1.4 Qualities of Service
    • 5.1.5 Dynamic Fragmentation and MTU
    • 5.1.6 Flow Control and Throughput
    • 5.1.7 Unacknowledged Data
    • 5.1.8 Integration with Traditional and New Communication Systems
    • 5.1.9 Security
  • 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.2.1 The Allocated Bandwidth Table
    • 6.2.2 Deciding to Update the ABTs
    • 6.2.3 Updating the ABTs
    • 6.2.4 Updating the Packet's Congestion Fields
  • 6.3 TRUMP/RBCC Operation
    • 6.3.1 Source Transmission
    • 6.3.2 Packet Reception by the Destination
    • 6.3.3 Packet Reception by the Source
    • 6.3.4 Flow Termination
    • 6.3.5 Abnormal Loss of a Traffic Flow
    • 6.3.6 Congestion Avoidance
  • 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.3.1 Transmission Sequence Numbers
    • 9.3.2 Router Queue Lengths
    • 9.3.3 Round-Trip Times
  • 9.4 Scenario 2
    • 9.4.1 Optimum Rates for Scenario 2
    • 9.4.2 Transmission Sequence Numbers
    • 9.4.3 Packet Loss
    • 9.4.4 Router Queue Lengths
    • 9.4.5 End-to-End Delays
    • 9.4.6 Link Utilisations
    • 9.4.7 Predicted and Measured TRUMP Transmission Rates
    • 9.4.8 Evaluation of Comparison Results
  • 9.5 Scenario 2a
  • 9.6 Scenario 3
    • 9.6.1 Transmission Sequence Numbers
    • 9.6.2 Router Queue Lengths
    • 9.6.3 Link Utilisations
    • 9.6.4 End-to-End & Round-trip Times
    • 9.6.5 TRUMP Transmission Rates
  • 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.2.1 Executability
    • B.2.2 Data Types
    • B.2.3 Processes
    • B.2.4 Atomic Sequences
    • B.2.5 Message Channels
    • B.2.6 Control Flow
    • B.2.7 Promela Verification Support
  • 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.6.1 No Features Enabled
    • B.6.2 Selective Acknowledgments
    • B.6.3 Receiver Errors
    • B.6.4 Implicit Connection Setup
    • B.6.5 Packet Losses
    • B.6.6 Packet Reordering
  • 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