Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

Dah-Ming Chiu, Raj Jain, 1989, Computer Networks and ISDN Systems

About this paper

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

English
Tiếng Việt

New Address: Raj Jain, Washington University in Saint Louis, jain@cse.wustl.edu, http://www.cse.wustl.edu/~jain

Abstract. Congestion avoidance mechanisms allow a network to operate in the optimal region of low delay and high throughput, thereby, preventing the network from becoming congested. This is different from the traditional congestion control mechanisms that allow the network to recover from the congested state of high delay and low throughput. Both congestion avoidance and congestion control mechanisms are basically resource management problems. They can be formulated as system control problems in which the system senses its state and feeds this back to its users who adjust their controls.

The key component of any congestion avoidance scheme is the algorithm (or control function) used by the users to increase or decrease their load (window or rate). We abstractly characterize a wide class of such increase/decrease algorithms and compare them using several different performance metrics. They key metrics are efficiency, fairness, convergence time, and size of oscillations.

It is shown that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for convergence to an efficient and fair state regardless of the starting state of the network. This is the algorithm finally chosen for implementation in the congestion avoidance scheme recommended for Digital Networking Architecture and OSI Transport Class 4 Networks.

Keywords. Computer Network, Network Performance, Resource Management, Congestion Control, Congestion Avoidance, Flow Control, Fairness.

Phân tích các thuật toán Tăng và Giảm để Tránh Tắc nghẽn trong Mạng Máy tính

Dah-Ming CHIU và Raj JAIN

Digital Equipment Corporation, 550 King Street (LKG1-2/A19),

Littleton, MA 01460-1289, U.S.A.

Địa chỉ mới: Raj Jain, Washington University in Saint Louis,

jain@cse.wustl.edu, http://www.cse.wustl.edu/~jain

Tóm tắt. Các cơ chế tránh tắc nghẽn cho phép một mạng hoạt động trong vùng tối ưu có độ trễ thấp và thông lượng cao, do đó ngăn mạng trở nên tắc nghẽn. Điều này khác với các cơ chế điều khiển tắc nghẽn truyền thống, cho phép mạng khôi phục từ trạng thái tắc nghẽn có độ trễ cao và thông lượng thấp. Cả cơ chế tránh tắc nghẽn và cơ chế điều khiển tắc nghẽn về cơ bản đều là các bài toán quản lý tài nguyên. Chúng có thể được xây dựng dưới dạng các bài toán điều khiển hệ thống, trong đó hệ thống cảm nhận trạng thái của nó và phản hồi trạng thái này đến những người dùng, những người điều chỉnh các điều khiển của họ.

Thành phần chính của bất kỳ lược đồ tránh tắc nghẽn nào là thuật toán (hoặc hàm điều khiển) được người dùng sử dụng để tăng hoặc giảm tải của họ (cửa sổ hoặc tốc độ). Chúng tôi mô tả một cách trừu tượng một lớp rộng các thuật toán tăng/giảm như vậy và so sánh chúng bằng cách sử dụng một số chỉ số hiệu năng khác nhau. Các chỉ số chính là hiệu quả, tính công bằng, thời gian hội tụ và kích thước của dao động.

Chỉ ra rằng một thuật toán tăng cộng và giảm nhân đơn giản thỏa mãn các điều kiện đủ để hội tụ đến một trạng thái hiệu quả và công bằng bất kể trạng thái khởi đầu của mạng. Đây là thuật toán cuối cùng được chọn để triển khai trong lược đồ tránh tắc nghẽn được khuyến nghị cho Digital Networking Architecture và OSI Transport Class 4 Networks.

Từ khóa.

1 Introduction

This section is missing here.

2 Feasible Linear Controls

This section is missing here.

3 Optimizing the Control Schemes

This section is missing here.

4 **Nonlinear Controls**

This section is missing here.

5 Practical Considerations

This section is missing here.

6 Summary of Results

This section is missing here.

Acknowledgments

This section is missing here.

References

  1. D.P. Bertsekas, Distributed Asynchronous Computation of Fixed Points, Mathematical Programming 27 (1983) 107–120.
  2. E. Gafni and D. Bertsekas, Dynamic Control of Session Input Rates in Communication Networks, in: Proc. MILCOM '82, Boston, MA, MIT Technical Report LIDS-P-1228, 1982.
  3. H. Hayden, Voice Flow Control in Integrated Packet Networks, MIT, M.S. Thesis, MIT Technical Report LIDS-TH-1152, 1981.
  4. ISO 8073: Information Processing Systems — Open Systems Interconnection — Connection Oriented Transport Protocol Specification, International Organization for Standardization, Ref. no. ISO 8073-1986 (E)), 1986.
  5. J.M. Jaffe, Bottleneck Flow Control, IEEE Transactions on Communications 29 (7) (1981) 954–962.
  6. R. Jain, D.M. Chiu and W. Hawe. A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems, Technical Report, Digital Equipment Corporation, DEC-TR-301, 1984.
  7. R. Jain and K.K. Ramakrishnan, Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals and Methodology, in: Proc. Computer Networking Symposium, Washington, DC (1988) 134–143.
  8. R. Jain, K.K. Ramakrishnan and D.M. Chiu, Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Technical Report DEC-TR-506, Digital Equipment Corporation, 1987. Also in: C. Partridge, ed., Innovations in Internetworking (Artech House, Norwood, MA, 1988) 140–156.
  9. J. Mosely, Asynchronous Distributed Flow Control Algorithms, MIT, Ph.D. Thesis, MIT Technical Report LIDS-TH-1415, 1984.
  10. K.K. Ramakrishnan, D.M. Chiu and R. Jain, Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part IV-A Selective Binary Feedback Scheme for General Topologies, Technical Report DEC-TR-509, Digital Equipment Corporation, 1987.
  11. K.K. Ramakrishnan and R. Jain, A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer, in: Proc. ACM SIGCOMM'88 (1988).
  12. B.A. Sanders, An Incentive Compatible Flow Control Algorithm for Fair Rate Allocation in Computer/Communication Networks, 6th International Conference on Distributed Computing Systems, Cambridge, MA (1986).

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.