【作者】 徐建；

【导师】 李善平；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2004， 博士

【摘要】 TCP／IP网络提供的数据报传输是“Best Effort”服务。然而随着Internet商业化进程的加快，用户对服务质量有了新的需求。基于“Best Effort”服务原则在未来的许多年内将继续得到整个Internet社团支持这样一个假设，本文认为在适当Overprovisioning网络带宽的前提下，可以通过对带宽的公平分配来满足用户的需求；同时通过增加应用对网络环境的动态适应能力，使它们能够达到用户满意的程度。因此，本文在两个方面对TCP／IP网络中的公平性问题展开研究： 第一，网络如何对在其中流动的用户数据流提供保护和约束，使用户从网络接受的服务，不依赖于网络中其它用户的合作程度。第二，网络如何提供及时的，准确的关于网络使用状况的信息给用户，使他们有机会调整自身的网络使用行为，公平地获取所需资源。 针对数据传输过程中带宽分配存在的问题，以及目前的研究现状，提出了两种公平的带宽分配策略及算法，其主要内容如下： 1．MBLUE是一种面向数据流的活动队列管理算法，它的目标是平均公平性。MBLUE使用数据报丢弃的频率和队列空闲程度来管理网络拥塞；它只维护一个先进先出队列，以较少的数据流状态信息，在不同流之间公平地分配网络带宽。 MBLUE在ns2模拟试验中表现的性能证实了提高网络服务公平性两个重要原则的有效性，为用户公平的带宽分配研究奠定了基础。 2．基于用户公平性概念，本文提出了用户公平的带宽分配策略，并且设计了相关的算法UFQR。 网络资源分配的用户公平性意味着，不仅是用户的接入，而且包括传输中的带宽资源分配，都应该与用户所支付的费用相适应。 本文使用用户期望的服务满意度来表征一个用户对网络资源的使用情况。用户期望的服务满意度通过预约与实际使用的比值来表示，方便了数据报的标记以及网络核心在资源分配时的算法设计，使用户公平的带宽分配成为可能。 本文把用户期望的服务满意度作为主要的管理指标，设计了一种全新的活动队列管理算法UFQR，使拥塞时瓶颈连接处的带宽资源分配能够按照用户的预约体现出公平性，实现了对不同用户数据流的保护和约束。该算法在网络边缘根据用户数据的流速和在ISP处的预约，计算并标记每个数据报，在网络内部的路由上对数据报进行管理。UFQR“边缘—核心”的功能分布符合Internet端到端的设计原则，以较小的代价保证了公平性，并且整体上提高了网络的效率。 算法可以采用分阶段数据报标记和丢弃的方法，向用户及时准确地反馈网络的使用信息。对于适应性的用户数据流，源端的用户因此能够较早地接收拥塞信息，做出相应的调整，从而减少数据报的丢失:对于非适应性数据流，在标记阶段过后，使用数据报丢弃的方法，直接限制其通过，达到控制的目的。由于结合了用户的使用信息，网络的反馈对于不同的用户是有区别的:超过平均服务水平将得到负向的反馈，而低于平均服务水平的用户却是正向的反馈。这样，结合用户端到端的努力，使网络带宽资源在所有用户之间公平地配置. 本文对用户公平的带宽分配策略作了深入的理论分析，从网络资源定价的角度说明了该方法的合理性和均衡性。 本文通过nsZ模拟试验分析，证实了UFQR算法公平分配网络带宽的性能。在相同预约或不同预约两种情况下，对于用户的适应性或非适应性数据流，证实其带宽分配的公平性都保持在0.9以上，高于Diffsery能够达到的水平.更多还原

【Abstract】 TCP/IP networking provides only one service: Best Effort datagram delivery. However, with the development of, such as, commercialization and the diversity of application requirements, more concrete definition of quality of service is necessary. Traditional bandwidth allocation method and congestion control principle will not satisfy the changing demands.On the assumption that Internet society will continue to support the Best Effort service model in the future, the dissertation believes that most of applications, with appropriate bandwidth overprovisioning and some control over data flow, in addition with their abilities of adaptation to dynamic network conditions, will perform sufficiently well under moderate congestion levels. Therefore we conduct some research based on two principles:First, network must protect flows by enforcing restrictions on resource usage. Second, the network must provide feedbacks to users in time.The dissertation proposes two fair bandwidth allocation algorithms: MBLUE (Modified BLUE) and UFQR (User Fair Queuing with Reservation).1. MBLUE aims at average fairness. It uses packet loss and link utilization history as an estimator of congestion to detect incipient congestion, and to notify relative connections. MBLUE works with an FIFO queue without assumptions about queuing architecture. Through little state information of each flow MBLUE achieves fair bandwidth allocation among flows sharing the bottle-neck.Simulation results demonstrate the fairness of MBLUE. It also validates the effectiveness of two principle mentioned above.2. Based on the concept of user fairness, the dissertation proposes UFQR, which can allocate bandwidth among users according to their payments during congestion.For each packet at the edge of a network, UFQR inserts a label with user’s utility, which is the ratio of its real traffic into network and its reservation. It uses average queue length as the indicator of the severity of congestion, and uses utility as main index of packets dropping.A user, whose traffic is higher than the average service level, will receive negative feedbacks from UFQR during congestion, and be notified to reduce his packets sending; whereas a user whose traffic is lower than average, will receive positive feedbacks and be notified to increase his packets sending. If a user ignores negative feedbacks from network, packets out of his fair share will be dropped by UFQR. So with end-to-end efforts, the bandwidth is allocated fairly during congestion.The dissertation analyzes the scheme of user fair bandwidth allocation with game and pricing theory, and shows its rationality and equilibrium.Simulation results are presented to validate the performance of the algorithm under different scenarios.更多还原