拥塞控制的效率和公平性研究
摘要
随着Internet的不断发展,网络上出现了大量流媒体和组播流量。由于技术上存在难点,这些流量很多都没有采用拥塞控制机制。这大大加重了网络拥塞的可能性。针对这个问题,一方面应该保证即使存在不友好的流量,网络也依然能够高效的工作,避免拥塞;另一方面,也需要针对流媒体、组播等流量提出更有效和公平的拥塞控制方案,只有在这两方面都采取措施才能更有效的解决当前互联网的拥塞问题。
负载与队列高效结合的AQM(主动队列管理)算法LQC(Load Queue Control),从中间链路的角度降低了行为异常流造成网络拥塞的可能性。该算法有效的将负载与队列相结合,以预计队列达到满队列的时间为拥塞判断的依据对到达的数据包进行丢弃或者标记。通过模拟实验,验证该算法能有效的控制路由器的队列长度和保持较高的端到端吞吐率。
SMCC(Stream media Multicast Congestion Control)是一种新的流媒体组播拥塞控制算法,它从端到端的角度,更有效和更公平的处理流媒体组播的拥塞控制。针对流媒体组播拥塞控制上存在的可扩展性和TCP友好性等问题,将ECN(显示拥塞指示)和XCP算法的思想扩展到流媒体组播传输上,提出一种路由器辅助的分层流媒体组播拥塞控制算法。通过定义一个新的拥塞头部,发送端将发送速率和控制周期信息告知路由器,然后由路由器根据链路状况进行效率和公平性的计算,将吞吐率指示传达给接收端,接收端据此进行加入和退出分层的操作,调节链路上的传输流量。该算法通过路由器辅助的前馈系统,避免了反馈系统造成的可扩展性问题,同时高效和公平的利用了网络链路的带宽。仿真平台上进行的模拟实验表明,该算法具有较好的异构网络适应性和公平性。
The end-to-end congestion control mechanism plays an important role in guaranteeing the robustness of the Internet. But the efficiency of this mechanism rely on two preconditions, the network traffics are responsive and TCP-friendly. With the growth of Internet, there are more and more stream media and multicast traffics appear on the Internet. Because of the technical difficulty, most of them don’t use any congestion control mechanism. This situation raise the possibility of congestion occurs, and threaten the robustness. In this situation, on one hand, we should make the network itself can work effective in spite of there are abnormal traffics, on the other hand, we should propose more effective and more fair congestion control mechanism for those stream media and multicast traffics. Only the two sides work together, the Internet congestion problem can be solved effectively.
A novel AQM algorithm LQC (Load Queue Control) that uses both traffic load and queue length to indicate congestion degree was proposed in this paper to decrease the possibility of congestion occurring on the network aspect when there are abnormal traffics. In this algorithm, traffic load and queue length was effectively combined to indicate the congestion degree, and the incoming packet is dropped according the time in which the queue is supposed to be full. Through simulation on NS-2, the algorithm was proved can control the queue length effectively and keep the end-to-end throughput on a high level. On the end-to-end aspect, A novel stream media multicast congestion control algorithm SMCC(Stream media Multicast Congestion Control) was proposed in this paper to solve the congestion caused by the stream media multicast traffic. Aim to solve the scalability and TCP-friendly problem which most of the existing algorithm have, we extend the thought of ECN and XCP (a newly proposed protocol believed to be superior to TCP) to stream media multicast transport applications, propose a router-aided layered stream media multicast congestion control algorithm. By defining a new congestion header, sender tell the router the rate and control period information, then the router count the throughput indicator information according to the link status, set it to the congestion header and forward it to the receiver. Finally, the receivers decide to join or leave some layers by anglicizing the congestion header so as to react to the network status. Through router feed forward the throughput indicator to the receiver, this mechanism avoids the scalability problems caused by feed back system and uses the link bandwidth effectively and fairly. Simulation on NS-2 shows that the mechanism can fit heterogeneous network well and makes the multicast stream traffics share the bottleneck with TCP traffics more fairly.
负载与队列高效结合的AQM(主动队列管理)算法LQC(Load Queue Control),从中间链路的角度降低了行为异常流造成网络拥塞的可能性。该算法有效的将负载与队列相结合,以预计队列达到满队列的时间为拥塞判断的依据对到达的数据包进行丢弃或者标记。通过模拟实验,验证该算法能有效的控制路由器的队列长度和保持较高的端到端吞吐率。
SMCC(Stream media Multicast Congestion Control)是一种新的流媒体组播拥塞控制算法,它从端到端的角度,更有效和更公平的处理流媒体组播的拥塞控制。针对流媒体组播拥塞控制上存在的可扩展性和TCP友好性等问题,将ECN(显示拥塞指示)和XCP算法的思想扩展到流媒体组播传输上,提出一种路由器辅助的分层流媒体组播拥塞控制算法。通过定义一个新的拥塞头部,发送端将发送速率和控制周期信息告知路由器,然后由路由器根据链路状况进行效率和公平性的计算,将吞吐率指示传达给接收端,接收端据此进行加入和退出分层的操作,调节链路上的传输流量。该算法通过路由器辅助的前馈系统,避免了反馈系统造成的可扩展性问题,同时高效和公平的利用了网络链路的带宽。仿真平台上进行的模拟实验表明,该算法具有较好的异构网络适应性和公平性。
The end-to-end congestion control mechanism plays an important role in guaranteeing the robustness of the Internet. But the efficiency of this mechanism rely on two preconditions, the network traffics are responsive and TCP-friendly. With the growth of Internet, there are more and more stream media and multicast traffics appear on the Internet. Because of the technical difficulty, most of them don’t use any congestion control mechanism. This situation raise the possibility of congestion occurs, and threaten the robustness. In this situation, on one hand, we should make the network itself can work effective in spite of there are abnormal traffics, on the other hand, we should propose more effective and more fair congestion control mechanism for those stream media and multicast traffics. Only the two sides work together, the Internet congestion problem can be solved effectively.
A novel AQM algorithm LQC (Load Queue Control) that uses both traffic load and queue length to indicate congestion degree was proposed in this paper to decrease the possibility of congestion occurring on the network aspect when there are abnormal traffics. In this algorithm, traffic load and queue length was effectively combined to indicate the congestion degree, and the incoming packet is dropped according the time in which the queue is supposed to be full. Through simulation on NS-2, the algorithm was proved can control the queue length effectively and keep the end-to-end throughput on a high level. On the end-to-end aspect, A novel stream media multicast congestion control algorithm SMCC(Stream media Multicast Congestion Control) was proposed in this paper to solve the congestion caused by the stream media multicast traffic. Aim to solve the scalability and TCP-friendly problem which most of the existing algorithm have, we extend the thought of ECN and XCP (a newly proposed protocol believed to be superior to TCP) to stream media multicast transport applications, propose a router-aided layered stream media multicast congestion control algorithm. By defining a new congestion header, sender tell the router the rate and control period information, then the router count the throughput indicator information according to the link status, set it to the congestion header and forward it to the receiver. Finally, the receivers decide to join or leave some layers by anglicizing the congestion header so as to react to the network status. Through router feed forward the throughput indicator to the receiver, this mechanism avoids the scalability problems caused by feed back system and uses the link bandwidth effectively and fairly. Simulation on NS-2 shows that the mechanism can fit heterogeneous network well and makes the multicast stream traffics share the bottleneck with TCP traffics more fairly.
引文
[1] Floyd, S., Fall, K. Promoting the use of end-to-end congestion control in the Internet. IEEE/ACM Transactions on Networking, 1999, 7(4): 458-472
[2] McCanne, S., Jacobson, V., Vetterli, M. Receiver-driven layered multicast. Computer Communication Review, 1996, 26(4): 117-130
[3] Braden, B., Clark, D., Crowcroft, J., Davie, B., et al. Recommendations on Queue Management and Congestion Avoidance in the Internet. RFC 2309. 1998
[4] Postel, J. Transmission Control Protocol. RFC 793. 1981
[5] Jacobson, V. Congestion avoidance and control. Computer Communication Review, 1995, 25(1): 157-173
[6] Tanenbaum, A. S. Computer Networks. (4th). Prentice Hall, 2003
[7] Jain, R., Ramakrishnan, K. K. Congestion Avoidance in Computer Networks With a Connectionless Network Layer: Concepts, Goals and Methodology. in. Washington, DC, USA: IEEE, New York, NY, USA, 1988. 134-143
[8] Peterson, L. L., Davie, B. S. 计算机网络. (第 2 版). 叶新铭, 贾波 and 吴承勇等译. 北京: 机械工业出版社, 2001
[9] Shenker, S. Fundamental design issues for the future Internet. IEEE Journal on Selected Areas in Communications, 1995, 13(7): 1176-1188
[10] Jain, R. Congestion control in computer networks. in. Berkeley, CA, USA: Publ by ACM, New York, NY, USA, vol. 17, 1989. 216
[11] Chiu, D. -M., Jain, R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer Networks and ISDN Systems, 1989, 17(1): 1-14
[12] Jaffe, J. M. Bottleneck flow control. IEEE Transactions on Communications, 1981, CM-29(7): 954-962
[13] Kelly, F. P., Maulloo, A. K., Tan, D. K. H. Rate control for communication networks: Shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 1998, 49(3): 237-252
[14] 章淼, 吴建平, 林闯. 互联网端到端拥塞控制研究综述. 软件学报, 2002, 13(03): 354-363
[15] Floyd, S., Jacobson, V. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1993, 1(4): 397-413
[16] Wydrowski, B., Zukerman, M. GREEN: An active queue management algorithm for a self managed Internet. in. New York, NY: Institute of Electrical and Electronics Engineers Inc., vol. 4, 2002. 2368-2372
[17] Ott, T. J., Lakshman, T. V., Wong, L. H. SRED: Stabilized RED. Proceedings - IEEE INFOCOM. Vol. 3 of 3 JSR. 1999, 3: 1346-1355
[18] Lin, D., Morris, R. Dynamics of random early detection. Computer Communication Review, 1997, 27(4): 127-137
[19] Feng, W. C., Kandlur, D., Saha, D., Shin, K. G. BLUE: An alternative approach to active queue management. in. Port Jefferson, NY: 2001. 41-50
[20] Kunniyur, S., Srikant, R. Analysis and design of an Adaptive Virtual Queue (AVQ) algorithm for active Queue management. in. San Diego, CA: Association for Computing Machinery, vol. 31, 2001. 123-134
[21] Stevens, W. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001. 1997
[22] Floyd, S., Henderson, T. The NewReno Modification to TCP's Fast Recovery Algorithm. RFC 2582. 199
[23] Mathis, M., Mahdavi, J., Floyd, S., Romanow, A. TCP Selective Acknowledgment Options. RFC 2018. 1996
[24] Ramakrishnan, K. K., Jain, R. Binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer. Computer Communication Review, 1995, 25(1): 138-156
[25] Floyd, S. TCP and Explicit Congestion Notification. ACM Computer Communication Review, 1994, 24(5): 10-23
[26] Ramakrishnan, K., Floyd, S. A Proposal to add Explicit Congestion Notification (ECN) to IP. RFC 2481. 1999
[27] Katabi, D., Handley, M., Rohrs, C. Congestion control for high bandwidth-delayproduct networks in: SIGCOMM 2002. Pittsburgh, Pennsylvania, USA. : ACM Press, vol. 32, 2002. 89-102
[28] Xia, Y., Subramanian, L., Stoica, I., Kalyanaraman, S. One more bit is enough. ACM SIGCOMM Computer Communication Review, 2005, 35(4): 37-48
[29] Chung, J., Zhu, Y., Claypool, M., FairPlayer or FoulPlayer? - Head to Head Performance of RealPlayer Streaming Video Over UDP versus TCP, Technical 2002
[30] Rejaie, R., Handley, M., Estrin, D. RAP: An end-to-end rate-based congestion control mechanism for realtime streams in the Internet. Proceedings - IEEE INFOCOM. Vol. 3 of 3 JSR. 1999, 3: 1337-1345
[31] Rhee, I., Ozdemir, V., Yi, Y., TEAR: TCP emulation at receivers - flow control for multimedia streaming. Technical, 2000
[32] Dorgham, S., Henning, S. The loss-delay based adjustment algorithm: a TCP- friendly adaptations cheme. in: NOSSDAV. Cambridge, U K: 1998. 215-226
[33] Sisalem, D., Wolisz, A. LDA+: A TCP-friendly adaptation scheme for multimedia communication. in. New York, NY: 2000. 1619-1622
[34] Padhye, J., Firoiu, V., Towsley, D., Kurose, J. Modeling TCP throughput: a simple model and its empirical validation. Computer Communication Review, 1998, 28(4): 303-314
[35] Handley, M., Floyd, S., Padhye, J., Widmer, J. TCP Friendly Rate Control (TFRC): Protocol Specification. RFC 3448. 2003
[36] Deering, S. E., Cheriton, D. R. Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems, 1990, 8(2): 85-110
[37] Sahasrabuddhe, L. H., Mukherjee, B. Multicast routing algorithms and protocols: a tutorial. IEEE Network, 2000, 14(1): 90-102
[38] Mankin, A., Romanow, A., Bradner, S., Paxson, V. IETF Criteria for Evaluating Reliable Multicast Transport and Application Protocols. RFC 2357. 1998
[39] Erramilli, A., Singh, R. P. A reliable and efficient multicast protocol for broadband broadcast networks. in. Stowe, VT, USA: vol. 17, 1987. 343-352
[40] Bhattacharyya, S., Towsleys, D., Kurose, J. Loss path multiplicity problem in multicast congestion control. Proceedings - IEEE INFOCOM. 1999, 2: 856-863
[41] Kwon, M., Fahmy, S. A comparison of load-based and queue-based active queue management algorithms. in. Boston, MA, United States: The International Society for Optical Engineering, vol. 4866, 2002. 35-46
[42] Bitorika, A., Robin, M., Huggard, M., Goldrick, C. a. M., A Comparative Study of Active Queue Management Schemes. 2004. in submission. https: //www. cs. tcd. ie/Mathieu. Robin/
[43] UCB/LBNL/VINT groups, Network Simulator-2. http: //nsnam. isi. edu/nsnam/
[44] Feng, W., Kandlur, D. D., Saha, D., Shin, K. G. Stochastic fair blue: A queue management algorithm for enforcing fairness. in. Anchorage, AK: Institute of Electrical and Electronics Engineers Inc., vol. 3, 2001. 1520-1529
[45] Vicisano, L., Crowcroft, J., Rizzo, L. TCP-like congestion control for layered multicast data transfer. in. San Francisco, CA, USA: IEEE, Piscataway, NJ, USA, vol. 3, 1998. 996-1003
[2] McCanne, S., Jacobson, V., Vetterli, M. Receiver-driven layered multicast. Computer Communication Review, 1996, 26(4): 117-130
[3] Braden, B., Clark, D., Crowcroft, J., Davie, B., et al. Recommendations on Queue Management and Congestion Avoidance in the Internet. RFC 2309. 1998
[4] Postel, J. Transmission Control Protocol. RFC 793. 1981
[5] Jacobson, V. Congestion avoidance and control. Computer Communication Review, 1995, 25(1): 157-173
[6] Tanenbaum, A. S. Computer Networks. (4th). Prentice Hall, 2003
[7] Jain, R., Ramakrishnan, K. K. Congestion Avoidance in Computer Networks With a Connectionless Network Layer: Concepts, Goals and Methodology. in. Washington, DC, USA: IEEE, New York, NY, USA, 1988. 134-143
[8] Peterson, L. L., Davie, B. S. 计算机网络. (第 2 版). 叶新铭, 贾波 and 吴承勇等译. 北京: 机械工业出版社, 2001
[9] Shenker, S. Fundamental design issues for the future Internet. IEEE Journal on Selected Areas in Communications, 1995, 13(7): 1176-1188
[10] Jain, R. Congestion control in computer networks. in. Berkeley, CA, USA: Publ by ACM, New York, NY, USA, vol. 17, 1989. 216
[11] Chiu, D. -M., Jain, R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer Networks and ISDN Systems, 1989, 17(1): 1-14
[12] Jaffe, J. M. Bottleneck flow control. IEEE Transactions on Communications, 1981, CM-29(7): 954-962
[13] Kelly, F. P., Maulloo, A. K., Tan, D. K. H. Rate control for communication networks: Shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 1998, 49(3): 237-252
[14] 章淼, 吴建平, 林闯. 互联网端到端拥塞控制研究综述. 软件学报, 2002, 13(03): 354-363
[15] Floyd, S., Jacobson, V. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1993, 1(4): 397-413
[16] Wydrowski, B., Zukerman, M. GREEN: An active queue management algorithm for a self managed Internet. in. New York, NY: Institute of Electrical and Electronics Engineers Inc., vol. 4, 2002. 2368-2372
[17] Ott, T. J., Lakshman, T. V., Wong, L. H. SRED: Stabilized RED. Proceedings - IEEE INFOCOM. Vol. 3 of 3 JSR. 1999, 3: 1346-1355
[18] Lin, D., Morris, R. Dynamics of random early detection. Computer Communication Review, 1997, 27(4): 127-137
[19] Feng, W. C., Kandlur, D., Saha, D., Shin, K. G. BLUE: An alternative approach to active queue management. in. Port Jefferson, NY: 2001. 41-50
[20] Kunniyur, S., Srikant, R. Analysis and design of an Adaptive Virtual Queue (AVQ) algorithm for active Queue management. in. San Diego, CA: Association for Computing Machinery, vol. 31, 2001. 123-134
[21] Stevens, W. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms. RFC 2001. 1997
[22] Floyd, S., Henderson, T. The NewReno Modification to TCP's Fast Recovery Algorithm. RFC 2582. 199
[23] Mathis, M., Mahdavi, J., Floyd, S., Romanow, A. TCP Selective Acknowledgment Options. RFC 2018. 1996
[24] Ramakrishnan, K. K., Jain, R. Binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer. Computer Communication Review, 1995, 25(1): 138-156
[25] Floyd, S. TCP and Explicit Congestion Notification. ACM Computer Communication Review, 1994, 24(5): 10-23
[26] Ramakrishnan, K., Floyd, S. A Proposal to add Explicit Congestion Notification (ECN) to IP. RFC 2481. 1999
[27] Katabi, D., Handley, M., Rohrs, C. Congestion control for high bandwidth-delayproduct networks in: SIGCOMM 2002. Pittsburgh, Pennsylvania, USA. : ACM Press, vol. 32, 2002. 89-102
[28] Xia, Y., Subramanian, L., Stoica, I., Kalyanaraman, S. One more bit is enough. ACM SIGCOMM Computer Communication Review, 2005, 35(4): 37-48
[29] Chung, J., Zhu, Y., Claypool, M., FairPlayer or FoulPlayer? - Head to Head Performance of RealPlayer Streaming Video Over UDP versus TCP, Technical 2002
[30] Rejaie, R., Handley, M., Estrin, D. RAP: An end-to-end rate-based congestion control mechanism for realtime streams in the Internet. Proceedings - IEEE INFOCOM. Vol. 3 of 3 JSR. 1999, 3: 1337-1345
[31] Rhee, I., Ozdemir, V., Yi, Y., TEAR: TCP emulation at receivers - flow control for multimedia streaming. Technical, 2000
[32] Dorgham, S., Henning, S. The loss-delay based adjustment algorithm: a TCP- friendly adaptations cheme. in: NOSSDAV. Cambridge, U K: 1998. 215-226
[33] Sisalem, D., Wolisz, A. LDA+: A TCP-friendly adaptation scheme for multimedia communication. in. New York, NY: 2000. 1619-1622
[34] Padhye, J., Firoiu, V., Towsley, D., Kurose, J. Modeling TCP throughput: a simple model and its empirical validation. Computer Communication Review, 1998, 28(4): 303-314
[35] Handley, M., Floyd, S., Padhye, J., Widmer, J. TCP Friendly Rate Control (TFRC): Protocol Specification. RFC 3448. 2003
[36] Deering, S. E., Cheriton, D. R. Multicast routing in datagram internetworks and extended LANs. ACM Transactions on Computer Systems, 1990, 8(2): 85-110
[37] Sahasrabuddhe, L. H., Mukherjee, B. Multicast routing algorithms and protocols: a tutorial. IEEE Network, 2000, 14(1): 90-102
[38] Mankin, A., Romanow, A., Bradner, S., Paxson, V. IETF Criteria for Evaluating Reliable Multicast Transport and Application Protocols. RFC 2357. 1998
[39] Erramilli, A., Singh, R. P. A reliable and efficient multicast protocol for broadband broadcast networks. in. Stowe, VT, USA: vol. 17, 1987. 343-352
[40] Bhattacharyya, S., Towsleys, D., Kurose, J. Loss path multiplicity problem in multicast congestion control. Proceedings - IEEE INFOCOM. 1999, 2: 856-863
[41] Kwon, M., Fahmy, S. A comparison of load-based and queue-based active queue management algorithms. in. Boston, MA, United States: The International Society for Optical Engineering, vol. 4866, 2002. 35-46
[42] Bitorika, A., Robin, M., Huggard, M., Goldrick, C. a. M., A Comparative Study of Active Queue Management Schemes. 2004. in submission. https: //www. cs. tcd. ie/Mathieu. Robin/
[43] UCB/LBNL/VINT groups, Network Simulator-2. http: //nsnam. isi. edu/nsnam/
[44] Feng, W., Kandlur, D. D., Saha, D., Shin, K. G. Stochastic fair blue: A queue management algorithm for enforcing fairness. in. Anchorage, AK: Institute of Electrical and Electronics Engineers Inc., vol. 3, 2001. 1520-1529
[45] Vicisano, L., Crowcroft, J., Rizzo, L. TCP-like congestion control for layered multicast data transfer. in. San Francisco, CA, USA: IEEE, Piscataway, NJ, USA, vol. 3, 1998. 996-1003