Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-11-05
2003-10-21
Dharia, Rupal (Department: 2189)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S113000, C710S119000
Reexamination Certificate
active
06636914
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to bus management. In particular, the present invention relates to an arbitration and fairness protocol on a serial bus system.
2. The Prior Art
Background
Modern electronic equipment has greatly enhanced the quality of our lives. However, as the use of such equipment has increased, so has the need to connect equipment purchased from different manufacturers. For example, while a computer and a digital camera may each be useful when used alone, the ability to connect the digital camera to the computer and exchange information between the two makes the combination even more useful. Therefore, a need was apparent for a serial bus standard that would allow for the connection and communication between such devices.
The IEEE 1394-1995 standard was developed to satisfy this need. This standard revolutionized the consumer electronics industry by providing a serial bus management system that featured high speeds and the ability to “hot” connect equipment to the bus; that is, the ability to connect equipment without first turning off the existing connected equipment. Since its adoption, the IEEE 1394-1995 standard has begun to see acceptance in the marketplace with many major electronics and computer manufacturers providing IEEE 1394 connections on equipment that they sell.
However, as technologies improved, the need to update the IEEE 1394 standard became apparent. Two new standards are being proposed at the time of the filing of this application, herein referred to as the proposed IEEE 1394a, or P1394a standard, and the proposed IEEE 1394b, or P1394b standard. Improvements such as higher speeds and longer connection paths will be provided.
Arbitration in IEEE 1394-1995
One area that has been improved is in the way that bus arbitration takes place on the bus. Arbitration is the process by which a device desiring to send data over the bus gains control of the bus in order to transfer the data.
FIG. 1
shows a prior art example of a typical data stream 100 during arbitration on a IEEE 1394-1995 compliant bus. In
FIG. 1
, data flow is generally from left to right on the page.
According to the IEEE 1394-1995 standard, the bus is required to remain idle for some predetermined time prior to arbitration. This period is known as either the arbitration reset gap or the subaction gap, as represented by packet
102
. After this gap
102
, an arbitration request
104
(“arb”) may be sent by the device wishing to send data over the bus. If arbitration is granted, then data packet
10
may be sent. After some idle time represented by packet
108
, an acknowledgment packet
110
(“ack”) is sent by the receiving device, and the bus is returned to idle in packet
112
.
FIG. 2
shows an example of prior art tree and root arrangement of node on an IEEE 1394-1995 compliant bus. As is appreciated by one skilled in the art, on a bus compliant with the IEEE 1394-1995 standard, when devices are connected together, a Tree-ID process takes place that results in one node being designated as the root, and all others being designated as branch and leaf nodes developing from the root node. Accordingly, in
FIG. 2
, node #
4
has been designated the root node, and nodes #
0
, #
1
and #
2
are leaf nodes, and node #
3
is a branch node. As is known by one skilled in the art, nodes #
1
and #
2
are referred to as “child” nodes of the “parent” node #
3
, and nodes #
0
and #
3
are referred to as the “child” nodes of the “parent” node #
4
.
FIGS. 3A through 3D
shows a prior art example of how the packets shown in
FIG. 1
might propagate in the tree arrangement shown in
FIG. 2
during a request for arbitration.
FIG. 3A
shows nodes #
1
and #
2
requesting arbitration at the same time. As is known by one skilled in the art, nodes along the path to the root arbitrate with their respective parents, while the root node makes the final decision. Therefore, a parent node will pass along a request to its parent, while denying access to its other children. Accordingly,
FIG. 3B
shows node #
3
passing along node #
2
's request to the root node #
4
, while node #
3
denies access to its other child node #
1
. Likewise, root node #
4
has received node #
0
's request, and denies access to node #
3
.
In
FIG. 3C
, root node #
4
will acknowledge node #
0
's first-received request by sending a grant to node #
0
. Node #
0
will then withdraw its request.
In
FIG. 3D
, nodes #
2
and #
3
will withdraw their requests, having both received denies. Thus, node #
0
has now won arbitration, and may begin sending data over the bus.
As is appreciated by one skilled in the art, the process shown in
FIGS. 3A-3D
has certain drawbacks. First, since in the IEEE 1394-1995 standard packet transmission between nodes is not full duplex (unlike arbitration signals, which are full duplex), packet transmission between nodes may only occur in one direction at a time. This limitation results in the fact that arbitration requests may not be communicated while data packets are being transmitted.
More importantly for the purposes of the present invention, the process shown in
FIGS. 3A-3D
demonstrates that for node #
2
to arbitrate for control of the bus, its request must be routed through node #
3
to be decided by root node #
4
and travel back down again to be received. Furthermore, as mentioned above, the arbitration process as carried out in the IEEE 1394-1995 standard requires that some period of idle bus (either an arbitration reset or subaction gap) occur before arbitration can begin again. As is appreciated by one skilled in the art, the larger the tree grows, the longer the path the farthest leaf node's request must travel, and the slower the entire process gets. Finally, while an arbitration reset or subaction gap is occurring, no data may be sent, resulting in inefficiencies.
Fairness in IEEE 1394-1995
The IEEE 1394-1995 standard also includes a concept known as fairness. Fairness is a procedure whereby all nodes that wish to gain control of the bus get at least one shot to arbitrate within a given period.
FIG. 4
shows an example of the prior art fairness procedure. In
FIG. 4
, nodes A, B, and C all wish to arbitrate within time period
400
. This time period is known as a fairness interval. For each node A, B, and C, a waveform representing the node's respective arbitration_enable flag is shown along a time axis. As is known by one skilled in the art, in order for an arbitration fairness period to begin, the bus must be idle for an arbitration reset gap. On
FIG. 4
, this period is show between time marker
402
and time marker
404
.
As is known by one skilled in the art, after the arbitration reset gap is over, the arbitration_enable flag is set for nodes A, B, and C at time marker
404
. This is indicated in
FIG. 4
by the waveforms labeled node A, B, and C each going high at time marker
404
. According to the IEEE 1394-1995 standard, a node's arbitration_enable flag will remain high until the node has won arbitration of the bus, then the arbitration enable flag will be reset low.
This process is shown in
FIG. 4
first with node A. At time marker
404
, node A begins to arbitrate, and at time marker
406
, node A wins arbitration. Accordingly, node A's arbitration_enable flag is reset low, and node A is allowed to transmit data on the bus. When node A has finished transmitting, the bus goes idle at time maker
408
and after a shorter period of idle (the subaction gap) all nodes with their arbitration_enable flag set are permitted to arbitrate for the bus at time marker
410
. In the case illustrated, node B wins arbitration at time marker
412
, has its arbitration_enable flag reset low, and By transmits data. Finally, the bus goes idle for a subaction gap once again, and since no other node is arbitrating, node C wins arbitration at time marker
414
, has its arbitration_enable f
Apple Computer Inc.
Dharia Rupal
Sierra Patent Group Ltd.
LandOfFree
Method and apparatus for arbitration and fairness on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for arbitration and fairness on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for arbitration and fairness on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172747