Multiplex communications – Channel assignment techniques – Polling
Reexamination Certificate
1998-09-23
2002-01-08
Ton, Dang (Department: 2732)
Multiplex communications
Channel assignment techniques
Polling
Reexamination Certificate
active
06337865
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to managing communication within a multi-node network, and, more particularly, to a method and apparatus for managing data transfer in such a network to assure that contending nodes with access to the network can transfer data to other nodes over the network.
BACKGROUND
Existing communication systems include a plurality of data processing nodes interconnected via a communication network. Typically arbitration is required for a node to gain access to the network for data transfer with other nodes. After winning the arbitration, an originator node establishes a virtual point-to-point connection with a target node. The originator node then transmits buffer credit tokens to the target node over the network, signaling the target node to transfer data packets to available buffers in the originator node over the network. Credit tokens sent from that originator node are only absorbed by the intended target node.
In arbitration-less networks, such as arbitration-less ring or tree type interconnect topology networks, an originator node does not establish a virtual point-to-point blocking connection with a target node. Therefore, data transfer management is necessary to assure that each target node with access to the network receives credit tokens from an originator node to transfer data to that originator node. Otherwise, as described below, one or more contending target nodes within the network can “starve”.
FIG. 1
illustrates a block diagram of an example prior art multi-node communication system
10
comprising nodes
15
,
20
,
25
,
30
,
35
,
40
,
45
and
50
interconnected via a ring network
55
. The nodes
15
,
20
,
25
,
30
,
35
and
40
can comprise target storage devices such as disk drives, and the nodes
45
and
50
can comprise originator host systems including host adaptors.
In an example data transfer scenario, the originator node
45
establishes a connection with the target nodes
15
,
25
and
35
. Once it has available buffer space to receive data, the originator node
45
transmits credit tokens over the network
55
signaling the connected target nodes
15
,
25
and
35
to transfer data packets to the node
45
. The nodes
15
,
25
and
35
can only send data packets to the node
45
if they receive credit tokens from the node
45
. The node
45
is unaware of which one of the nodes
15
,
25
or
35
absorbs the transmitted credit tokens from the network
55
. However, since the nodes
35
and
25
are closer in sequence to the node
45
in the network
55
, they can absorb all of the transmitted credit tokens and transfer data to the node
45
depending on the number of data packets they need to transfer to the node
45
. Therefore, the node
45
cannot guarantee that the target node
15
will receive any credit tokens. As such, the nodes
35
and
25
can continue absorbing credit tokens from the node
45
and starve the node
15
downstream.
Conventional communication management methods attempt to solve this problem by utilizing anti-starvation methods. One such method is based on an addressable buffer credit scheme in which an originating node places a target node address in each credit token such that only that intended target node can use the credit token. The originating node reserves available data buffers therein for such target nodes. Though in this scheme each target node is guaranteed a credit token over time, and, therefore, the right to transfer data to the originating node, some target nodes with credit tokens may not have any data to transfer immediately. As such, target nodes without any credit tokens and waiting to transfer cumulated data, must idle while available data buffers in the originating node remain reserved and unused. As a result, communication systems implementing the addressable buffer credit scheme suffer from slow response time and are wasteful of resources. Further, such communication systems are unsuitable for real-time applications where target nodes with real-time need to transfer data require fair opportunity to transfer data promptly.
One solution to the above problem can include providing each originating node with additional buffer space. However, such additional buffer space is costly to obtain and consumes precious physical space within the nodes. Yet, another disadvantage of the addressable buffer credit scheme is that since an originating node reserves buffer space for target nodes down stream from the originating node, the reserved buffer space in the originating node remains unused while credit tokens intended for the target nodes make their way through the network traffic to signal the target nodes to transfer data to the originating node. And, buffer credit distribution involves high processing and space overhead for proper data transfer management.
There is, therefore, a need for a method and apparatus for managing data transfer in multi-node communication systems to assure that contending nodes in the communication system have fair opportunity to transfer data to other nodes over the network. There is also a need for such a method and apparatus to be simple, efficient and provide the nodes with timely opportunity to transfer data over the network.
SUMMARY
The present invention satisfies these needs. In one embodiment, the present invention provides a method for transferring data between nodes of a multi-node communication system, including at least one originator node and a plurality of target nodes interconnected via a network. The method provides target nodes with fair opportunity to transfer data to originator nodes over the network. The originator node initiates data transfer by establishing a connection with one or more target nodes. The originator and the target nodes then cooperate as described below to provide the target nodes with fair opportunity to transfer data to the originator node.
After establishing connections with the target nodes, the originator node signals target nodes to transfer data by generating and transmitting credit tokens over the network. Before a target node can transfer data to the originator node, it must receive and absorb at least one credit token from the originator. All credit tokens transmitted by the originator node and not absorbed by the target nodes return back to the originator node over the network. Each originator node has two states of operation. In the first state of operation, the originator node generates a first type of credit token. And, in the second state of operation, the originator node generates a second type of credit token. The originator node changes from one state to another upon an originator toggle condition being satisfied. Similarly, each target node has two states of operation. In the first state of operation the target node can only absorb the first type of credit token from a desired originator node. And, in the second state of operation, the target node can only absorb the second type of credit token from a desired originator node. Each target nodes changes from one state to another upon satisfaction of a target toggle condition. As such, each target node is provided with buffer credit tokens up to its quota in a rotating manner.
Each target node can have a different quota for the number of credit tokens the target node may absorb from an originator node. The target toggle condition for each target node can comprise the node's credit token count reaching the node's quota of credit tokens that it can absorb from that originator node. Alternatively, the target toggle condition for each target node can comprise a credit token being absorbed by the target node from that originator node. If a target node does not absorb a received credit token, it can re-transmit the credit token over the network. For each target node, if the credit token count is greater than zero, the target node can transmit an available data packet to the originator node and decrement the count by one. The originator toggle condition can comprise receiving a previously transmitted credit token back from
Rege Satish
Seto Pak-Lung
Maxtor Corporation
Sigmond David M.
Ton Dang
LandOfFree
Fair buffer credit distribution flow control does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair buffer credit distribution flow control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair buffer credit distribution flow control will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823056