Electrical computers and digital data processing systems: input/ – Input/output data processing – Flow controlling
Reexamination Certificate
2000-12-21
2004-06-15
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Flow controlling
C710S033000, C710S041000, C709S209000, C709S233000, C709S232000, C714S776000, C370S231000, C370S232000, C370S233000, C370S285000, C370S395410
Reexamination Certificate
active
06751684
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the allocation of communication bandwidth to a plurality of devices coupled to a communication medium and, more particularly, to a fair bandwidth allocation scheme applicable to devices interconnected in daisy-chain fashion via a plurality of point-to-point communication links.
2. Background of the Related Art
This section is intended to introduce the reader to various aspects of art which may be related to various aspects of the present invention which are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Many computer systems generally have been designed around a shared bus architecture, in which one or more host processors and a host memory are coupled to a shared host bus. Transactions between processors and accesses to memory all occur on the shared bus. Such computer systems typically include an input/output (I/O) subsystem which is coupled to the shared host bus via an I/O bridge which manages information transfer between the I/O subsystem and the devices coupled to the shared host bus. Many I/O subsystems also generally follow a shared bus architecture, in which a plurality of I/O or peripheral devices are coupled to a shared I/O bus. The I/O subsystem may include several branches of shared I/O buses interconnected via additional I/O bridges.
Such shared bus architectures have several advantages. For example, because the bus is shared, each of the devices coupled to the shared bus is aware of all transactions occurring on the bus. Thus, transaction ordering and memory coherency is easily managed. Further, arbitration among devices requesting access to the shared bus can be simply managed by a central arbiter coupled to the bus. For example, the central arbiter may implement an allocation algorithm to ensure that each device is fairly allocated bus bandwidth according to a predetermined priority scheme. Such a priority algorithm may be a “round-robin” algorithm that provides equal bandwidth to each of the devices requesting access to the shared bus.
Shared buses, however, also have several disadvantages. For example, the multiple attach points of the devices coupled to the shared bus produce signal reflections at high signal frequencies which reduce signal integrity. As a result, signal frequencies on the bus are generally kept relatively low to maintain signal integrity at an acceptable level. The relatively low signal frequencies reduce signal bandwidth, limiting the performance of devices attached to the bus. Further, the multiple devices attached to the shared bus present a relatively large electrical capacitance to devices driving signals on the bus, thus limiting the speed of the bus. The speed of the bus also is limited by the length of the bus, the amount of branching on the bus, and the need to allow turnaround cycles on the bus. Accordingly, attaining very high bus speeds (e.g., 500 MHz and greater) is difficult in more complex shared bus systems.
The problems associated with the speed performance of a shared bus system may be addressed by implementing the bus as a packet-based bidirectional communication link comprising a plurality of sets of unidirectional point-to-point links. Each set of unidirectional links interconnects two devices such that multiple devices can be connected in daisy-chain fashion. In such an I/O subsystem, a daisy chain of I/O devices can be connected to the host subsystem through a host bridge. The host bridge is connected to the first device in the daisy chain via a set of unidirectional links. The first device functions as a forwarding device (i.e., a repeater) to relay packets received from the host bridge to the next device, and so on down the chain of devices. Similarly, each device can forward packets received from other devices up the chain to the host bridge. In addition to forwarding packets, each device also can issue its own packets into the stream of forwarded packets.
Although the daisy-chain architecture addresses the speed issues associated with a shared bus, special care should be taken in implementing the bus as a series of point-to-point links to ensure that features available in shared bus architectures also are available in the daisy-chain architecture. For example, in a shared bus system, only one device at a time can drive communication packets onto the bus. Thus, transaction ordering is controlled by the order in which the device issuing the packet gains access to the bus. In the shared bus system, all devices can view all transactions on the bus, and thus the devices can be configured to agree upon ordering. In the daisy-chain configuration, however, transactions directed from a first device to a second device cannot be viewed by any other device that is not positioned between the first and second devices in the chain. Accordingly, a transaction management and control scheme should be provided to ensure the appropriate ordering of transactions in the daisy-chained I/O subsystem. For example, to ensure ordering in a daisy-chain system, direct peer-to-peer communications may be prohibited. Instead, all packets may be forced to travel through a common entity (e.g., a host bridge at one end of the chain), which assumes control of ordering issues.
In addition to ordering issues, the daisy-chain architecture offers challenges in ensuring fair allocation of bus bandwidth to the devices connected to the daisy chain. As discussed above, in the shared bus system, bandwidth typically is allocated by a central arbiter coupled to the shared bus. The central arbiter implements an allocation algorithm that balances available bandwidth among devices which are currently requesting access to the bus. In the daisy-chain environment, however, it is not possible to provide a central arbiter and, thus, bus arbitration is distributed among all the devices connected in the chain. Further, if the ordering scheme dictates that all packets should be routed through a bridge device, then devices both forward packets received from other devices and insert locally generated packets onto one of the point-to-point links in a direction toward the bridge device. In a system implementing such an ordering scheme, the allocation of bandwidth must take into account the number of local packets a particular device may insert relative to the number of received packets the device forwards. The ratio of inserted packets to forwarded packets is referred to as the “insertion rate” of a particular device. Because the devices are connected in a daisy chain, the ratio of local packets to forwarded packets at any one device may vary considerably depending on the device's position in the chain.
In the daisy-chain environment, each device sees a transmit bandwidth determined by flow control from the next device in the chain. However, each device is left to independently determine its own insertion rate within its transmit bandwidth. That is, each device independently allocates its transmit bandwidth between received packets the device is forwarding and locally generated packets the device is inserting in a stream of packets on a particular point-to-point link. If each device is allowed to insert packets at will, such an allocation scheme ultimately leads to marked and unpredictable imbalances in bandwidth allocation among the devices, as well as potential stalls of requests issued by devices. The imbalances can be particularly pronounced in systems having a large number of daisy-chained devices.
The problems of the distributed allocation scheme may be addressed by implementing a static insertion rate allocation scheme. That is, each device may be assigned a fixed insertion rate based on preconceived assumptions about device communication patterns. However, such an a priori allocat
Hummel Mark D.
Owen Jonathan M.
Gaffin Jeffrey
LaRiviere Grubman & Payne, LLP
Patel Niketa
LandOfFree
System and method of allocating bandwidth to a plurality of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method of allocating bandwidth to a plurality of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method of allocating bandwidth to a plurality of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364078