Principles of backlog balancing for rate-based flow control and congestion control in ATM networks.

摘要

Flow control algorithms in data networks are resource sharing polices implemented in a distributed manner. With the advent of BISDN/ATM networks, a great challenge for flow control has been created by the large delay-bandwidth product and diversified highly bursty traffic services. The thesis addresses itself to this issue.A large number of flow control algorithms have been proposed in the literature. However, most of these studies are not directed towards developing a unified framework for achieving efficient bandwidth and buffer sharing with tolerable delay for each virtual circuit (VC) and yet to prevent network congestions simultaneously. As an attempt, we suggest the concept of backlog balancing, i.e., to ensure an even backlog distribution across the entire network all the time, and then investigate it for the flow control in ATM networks.A rate-based flow control algorithm (BBFC) is thus proposed in this thesis. The basic idea is to adjust the service rate of each node along a VC according to backlog discrepancies between it and its downstream node. The hand shaking procedure between any two consecutive nodes is carried out by a link-by-link binary feedback protocol, where one bit signal (0/1) is used to indicate the event of nodal buffer status changing from normal state into underflow or overflow state. Each node will adjust its service rate periodically using a linear projection model of the flow dynamics and feedback information. A fluid-flow analysis of a two-node model is performed for illustration. We then develop a service policy for BBFC. Its basic idea is to divide the link capacity among every VC based on their respective updated service rates.In contrast, we also develop a link-by-link rate-based flow control scheme (EASY) from the common feedback protocol, which enables each node to enforce the peak rate and agreed constant rate for a VC on receiving a corresponding feedback signal 0 or 1 from its downstream neighbor. We introduce a state-dependent weighted round robin service discipline (SD-WRR) for EASY, which assigns bandwidth to each VC mainly based on its buffer occupancy. We then validate BBFC and EASY by simulation. Previous works like GPS and FCVC are also compared.Since the rate updating algorithm of BBFC is always designed to reduce the backlog discrepancy between neighboring nodes, it is expected that a nearly even backlog distribution throughout the VC can be achieved in the long run time. Furthermore, if all VC's in the network agree to comply with the same set of rules, the maximum aggregate backlog at each node can be reduced and with that, the problem of network congestions could be alleviated or totally avoided, high throughput with tolerable delay can still be achieved, besides, the variations of end-end cell transfer delay per VC may be much reduced. Our claims about these are substantiated by simulation.Also remarked is that SD-WRR plus EASY can compete with BBFC in many aspects except for more nodal buffer requirement, and it would be another subject of interest for future research.