Adaptive bandwidth sharing

Details Adaptive bandwidth sharing Adaptive bandwidth sharing

1997-09-16

2001-03-20

Rao, Seema S. (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S232000, C370S236000, C370S252000, C370S468000, C370S522000

Reexamination Certificate

active

06205119

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to methods and apparatus for electronic communications, and particularly to a system and method for controlling traffic on a ring topology network.
2. Background Information
There is a rapidly increasing demand for very high performance shared access to distributed data, for multiprocessors, networked workstation clusters, distributed databases, etc. The objective is to satisfy this demand at the lowest long-term cost. To do that, a wide range of interconnect technologies are available. These include switch networks, busses, simple daisy-chain or ring connections and combinations of switch and ring topologies. In systems where there are a large number of nodes, a ring topology such as the Scalable Coherent Interface (SCI) has been well received.
SCI was developed by a number of high-performance-bus designers and system architects. The SCI protocol was designed to eliminate dependencies that can cause deadlocks, and to include simple mechanisms that assure fair allocation of resources and livelock avoidance. It was recognized that very soon microprocessor speeds would exceed the capability of any bus to support significant multiprocessing. The SCI protocol includes two fundamental design choices which make it especially adapted to high speed data communication between a large number of nodes.
The first design choice was to make signaling speed independent of the size of the system. Other bus protocols require a node to wait one entire bus cycle before sending the next signal. In contrast, an SCI node does not wait for each signal to propagate before transmitting the next signal. As a result, SCI signaling speed is independent of the size of the system. Each SCI communication is performed by sending packets, each packet containing an address, a command, and data as appropriate. Each packet is then either accepted and stored in the responders' queues or is discarded (if there is not sufficient space). An echo packet tells the requestor whether the Send packet can be discarded or that it was not accepted and must be retransmitted. A similar handshake occurs in response.
In the SCI protocol, echo packets provide a handshake that passes responsibility for a packet from one buffer to the next as the packet flows through the interconnect. All other SCI packets have a 16-byte header that contains address information and a command transaction identifier. Response packets also include status information. The size of any packet that may need to be stored in queues is some multiple of 16 bytes, thereby simplifying storage management at very high speeds. An echo packet is an 8-byte subset of the header. Thus, the echo is not a confirmation of the completion of the sub-action. Instead, requests are confirmed end-to-end by response packets.
The second SCI design choice was to use multiple signal paths (links) so that multiple independent transfers can take place concurrently. For higher performance, separate links can be used for each processor, memory, or I/O device.
One factor affecting communications performance in any network communication protocol is latency. Latency is the delay between a request for data and the receipt of the requested data. This delay is primarily due to signal propagation at the finite speed of light, but is augmented by both technology-dependent and implementation-dependent factors. Thus, as technology advances, latency remains almost the same, as it is dominated by its speed of light component. The cost of accessing information from a given distance, however, is measured in missed opportunities, which increase as technology advances. Higher processor clock frequency increases the amount of available resources wasted during any clock period. In addition, the amount of data that can be moved during the latency period increases with transmission bandwidth. The cost of latency is therefore increasingly significant, and while communication bandwidth increases with technology and becomes less expensive, latency, measured in processor clock cycles, becomes more expensive.
SCI attempts to reduce latency by running the links continuously, sending Idle symbols when no packets are being transmitted. In this way a receiver can remain perfectly synchronized at all times, ready for action. SCI packets do not need the prologue that is essential for Ethernet or similar networks. Idle symbols also carry information about the priorities of other nodes, as well as go-bits. Go-bits act like tokens, helping ensure fair use of the links (in order to avoid starvation or deadlock). An SCI node must, however, maintain dual queues in order to keep responses independent of requests. Without dual queues, excessive requests prevent the sending of responses, resulting in deadlock.
Since introduction of the SCI standard in 1994, there have been several papers published proposing improvements in the SCI architecture and protocols. For example, David Gustavson and Qiang Li describe a 2-bit priority scheme in “Local Area Multiprocessor: The Scalable Coherent Interface” (ftp://ftp.SCIzzL.com/u/SCIzzLdocs/WesconLAMP/optvSCCIzzLb.pdf 1995). In another article Dan Picker, Ronald Fellman and Paul Chau discuss an extension to the SCI flow control protocol (“An Extension to the SCI Flow Control Protocol for Increased Network Efficiency”,
IEEE/ACM Transaction on Networking,
February 1996). This activity reflects the fact that despite its revolutionary architecture and performance, there are limiting factors in the current SCI standard.
Contemporary efforts to improve SCI tend to be narrowly focused and threaten to proliferate new SCI-like standards, with each standard being crafted for a particular user community. Two examples of such proposed standards are outlined in the RT-SCI and Serial-Express proposals, described by David James and David Gustavson in “Draft Proposals for Real-Time Transactions on SCI”, and “Serial Express—A Scalable Gigabit Extension to Serial Bus”, IEEE Standards Department, draft .600, Apr. 8, 1996). Neither approach, however, adequately addresses the shortcomings of the current SCI bandwidth allocation protocol.
These problems can be overcome by replacing the “go-bits/Idle symbols” scheme with an adaptive bandwidth sharing algorithm as described below.
SUMMARY OF THE INVENTION
What is provided is a novel Adaptive Bandwidth Sharing (ABS) method. The system and method of the present invention overcomes the deficiencies of SCI bandwidth allocation scheme. ABS scales well, features good bandwidth scheduling, and has better resiliency and significantly better throughput than SCI.
One embodiment of the present invention comprises a method of controlling communications between nodes, including a source node, a target node and a plurality of intermediate nodes, wherein the nodes are interconnected in a network. The method comprises the steps of connecting the nodes via unidirectional links, and transmitting flow control information in each Send packet from a source node to a target node via a subset of the plurality of intermediate nodes. At any one or more of the subset of the plurality of intermediate nodes, bandwidth is requested by modifying the flow control information in the Send packet. Flow control information is transferred at the target node from the Send packet to an echo packet, and the echo packet is transmitted from the target node to the source node. At the source node, the rate of packet transmission is adjusted according to both the flow control information received in the first echo packet and the traffic at the source node.
In a further embodiment, the step of modifying flow control information comprises setting a request to share bit in the Send packet. In another embodiment, the request to share bit is incorporated in a traffic control field in the Send packet.
In a further embodiment a priority is also written to the traffic control field. In yet another embodiment the step of adjusting the rate of packet transmission comprises the steps of comparing the priority i

Affiliated with

Also associated with

Rating

Adaptive bandwidth sharing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adaptive bandwidth sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive bandwidth sharing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2492100