EP0094180A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Dual-count, round-robin distributed arbitration technique for serial buses
Assignee: Digital Equipment Corp
•
Filing: 1983-04-28
•
Granted: —
•
Expires: 2003-04-28
Abstract
Abstract An arbitration technique for controlling access to a bit-serial bus (12) by multiple nodes 2(a)-2(n) in a data processing network (1 Upon detection of no carrier on the bus (step 56), a node desiring access to the bus waits a predetermined number of quiet slots (steps 60,64) each slot being a predetermined interval. If that period elapses without another node's carrier being detected (step 64), the node desiring access is permitted to transmit (steps 64, 68). For each node, two such delay interval possibilities are provided, one high slot count (and, hence, low priority) and one low slot count (and, hence, high priority). The delay interval selection for a node is switched from time to time on a round-robin basis, so that all nodes get equal average priority. The high value of the delay interval is N + M + slots, where N is the node number and M is the maximum number of nodes allowed on the bus; the low value is N+ 1 slots. Initially, each node uses the former value. Upon unsuccessful contention for the bus, the delay interval selection used next by the node depends on the number (LW) of the node which last won access to the bus. Upon detecting a carrier while waiting for access to the bus (i. e., losing arbitration to a higher priority node), the node which is waiting for the bus compares the number of the node (LW) which started transmitting with node number (N) (step 58). If LW was less than N, the node waiting for access uses a new waiting time of N+1 slots the next time the delay interval begins (step 62A); if greater than the node number, the dew delay interval value is N+M+1 slots (step 628). Provision is made for a multiple path bus wherein much common receiver circuitry is used for the paths. In that situation, if a node's receiver is busy on an alternate path when the node's delay interval expires, the node's delay interval is restarted with a waiting time of M slots assigned to the node.
Inventors
- 👤 William D. Strecker
- 👤 John E. Buzynski
- 👤 David Thompson
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 13:44
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/40; H04L12/40143; G; G06; G06F; G06F13/00; G06F13/14; G06F13/36; G06F13/368; G06F13/374; H04L12/407
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
83 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus (12), the improvement comprising arbitration means for controlling access to the bus by ascribing to each node a priority value and permitting access by that node which is requesting access and which has the highest priority value, and wherein the arbitration means assigns priority values such that under conditions of substantial demand for bus access, the average of the priority values is the same for each node.
Claim 2
Dependent Claim
83 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus (12), the improvement comprising arbitration means for controlling access to the bus by ascribing to each node a priority value and permitting access by that node which is requesting access and which has the highest priority value, and wherein the arbitration means assigns priority values such that under conditions of substantial demand for bus access, the average of the priority values is the same for each node.
Claim 3
Dependent Claim
115 words
In a network (12) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus 12, the improvement comprising arbitration means 18, 21, 22, 23, 25 for controlling access to the bus such that under conditions of light demand for the bus, each node contends separately for access and the node which transmits first without producing a collision with a transmission from another node is the one which gains access, whereas under conditions of substantial demand for the bus, access is controlled such that all nodes desiring bus access at a given instant are allowed to access the bus once, in controlled fashion, before any node gets to access the bus a second time.
Claim 4
Dependent Claim
115 words
In a network (12) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus 12, the improvement comprising arbitration means 18, 21, 22, 23, 25 for controlling access to the bus such that under conditions of light demand for the bus, each node contends separately for access and the node which transmits first without producing a collision with a transmission from another node is the one which gains access, whereas under conditions of substantial demand for the bus, access is controlled such that all nodes desiring bus access at a given instant are allowed to access the bus once, in controlled fashion, before any node gets to access the bus a second time.
Claim 5
Dependent Claim
213 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus (12), each node [2(a)-2(n)] including apparatus for controlling access to the bus comprising: A. carrier detector means 164 for detecting the presence or absence of transmission signals on the bus; B. arbitration counter means (22) responsive to the carrier detector means for counting the passage of time slots of predetermined duration, commencing with detection of an absence of transmission signals on the bus; C. means (18) for providing to the arbitration counter means an arbitration count value (AC V ) having one of two possible values, a relatively low value and a relatively high value; D. control means (18, 21) responsive to the carrier detector means, for inhibiting the arbitration counter means from counting upon detection of the presence of a transmission signal on the bus; E. the arbitration counter means (22) being adapted to compare the number of elapsed time slots with the arbitration count value and upon finding the number of elapsed time slots equal to the ACV for the node, providing a signal for enabling the node to begin transmitting on the bus; and F. means (18) responsive to the inhibiting of the arbitration counter for providing to the arbitration counter a new ACV.
Claim 6
Dependent Claim
213 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n)] via a bit-serial bus (12), each node [2(a)-2(n)] including apparatus for controlling access to the bus comprising: A. carrier detector means 164 for detecting the presence or absence of transmission signals on the bus; B. arbitration counter means (22) responsive to the carrier detector means for counting the passage of time slots of predetermined duration, commencing with detection of an absence of transmission signals on the bus; C. means (18) for providing to the arbitration counter means an arbitration count value (AC V ) having one of two possible values, a relatively low value and a relatively high value; D. control means (18, 21) responsive to the carrier detector means, for inhibiting the arbitration counter means from counting upon detection of the presence of a transmission signal on the bus; E. the arbitration counter means (22) being adapted to compare the number of elapsed time slots with the arbitration count value and upon finding the number of elapsed time slots equal to the ACV for the node, providing a signal for enabling the node to begin transmitting on the bus; and F. means (18) responsive to the inhibiting of the arbitration counter for providing to the arbitration counter a new ACV.
Claim 7
Dependent Claim
30 words
The apparatus of claim 3 wherein each node is assigned a unique node number, N, and both of the available AC V 's are a function of the node number.
Claim 8
Dependent Claim
29 words
The apparatus of claim 4 wherein there are a maximum of M nodes allowed in the network and the two possible ACV's for each node are N+l and N+M+1.
Claim 9
Dependent Claim
23 words
The apparatus of claim 5 wherein when a node desires to transmit, the means for providing an ACV initially selects the ACV N+M+1.
Claim 10
Independent Claim
65 words
The apparatus of any of claims 4 - 6 wherein the means responsive to the inhibiting of the arbitration counter includes i. means (18, 25) for determining the number (LW) of the node whose transmission signal caused the inhibiting, ii. means (18) for comparing N to LW, and iii. means (18) for choosing the new ACV as a function of the results of the comparison.
Claim 11
Dependent Claim
44 words
The apparatus of claim 7 wherein the means for choosing the new AC V sets the new ACV to the relatively low value if LW was less than N and to the relatively high value if LW was greater than or equal to N.
Claim 12
Dependent Claim
275 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n) via a bit-serial bus 12, a method for controlling access to the bus by said nodes, comprising the steps of: A. assigning to each node an arbitration count value (ACV), said AC V being the number of time slots of predetermined length during which the bus must be inactive prior to the node being allowed to begin transmitting on the bus; B. each node being identified by a node number; C. when a node desires to transmit, initializing its arbitration count value to a first, relatively high value Fig. (3-54); and D. each node which desires to transmit monitoring the bus for the transmit carrier of other nodes while counting the number of time slots the bus is inactive (Fig. 3-56) and i. upon detecting another node's carrier prior to expiration of a number of time slots equal to the node's ACV, a. determining whether the node number (LW) of the node whose carrier was detected, was greater or less than the node number, N, of the node which desires to transmit (Fig. 3-58), b. if LW was less than N, setting to a relatively low value the AC V of the node desiring to transmit (Fig. 3-62A), c. if LW was greater than or equal to N, setting to a relatively high value the ACV of the node desiring to transmit, and d. reentering step D. hereof (Fig. 3-62B), and ii. upon counting out a number of time slots equal to the node's ACV without detecting another node's carrier, allowing the node which desires to transmit to do so Fig. 3-60, 64).
Claim 13
Dependent Claim
275 words
In a network (1) for interconnecting a plurality of computer nodes [2(a)-2(n) via a bit-serial bus 12, a method for controlling access to the bus by said nodes, comprising the steps of: A. assigning to each node an arbitration count value (ACV), said AC V being the number of time slots of predetermined length during which the bus must be inactive prior to the node being allowed to begin transmitting on the bus; B. each node being identified by a node number; C. when a node desires to transmit, initializing its arbitration count value to a first, relatively high value Fig. (3-54); and D. each node which desires to transmit monitoring the bus for the transmit carrier of other nodes while counting the number of time slots the bus is inactive (Fig. 3-56) and i. upon detecting another node's carrier prior to expiration of a number of time slots equal to the node's ACV, a. determining whether the node number (LW) of the node whose carrier was detected, was greater or less than the node number, N, of the node which desires to transmit (Fig. 3-58), b. if LW was less than N, setting to a relatively low value the AC V of the node desiring to transmit (Fig. 3-62A), c. if LW was greater than or equal to N, setting to a relatively high value the ACV of the node desiring to transmit, and d. reentering step D. hereof (Fig. 3-62B), and ii. upon counting out a number of time slots equal to the node's ACV without detecting another node's carrier, allowing the node which desires to transmit to do so Fig. 3-60, 64).
Claim 14
Dependent Claim
15 words
The method of claim 9 wherein the relativlely low value of the ACV is N+l.
Claim 15
Dependent Claim
28 words
The method of claim 9 or claim 1-0 wherein the relatively high value of the ACV is N+M+1, M being the maximum number of nodes in the network.
Claim 16
Dependent Claim
90 words
The method of claim 9 wherein, to accommodate the use of multiple bus paths and shared receiver hardware for communicating thereover, upon counting out a number of time slots equal to the node's ACV without detecting another node's carrier, the node which desires to transmit is allowed to do so only if the shared receiver hardware is not engaged on another bus path (Fig. 3-6); and if the shared receiver hardware is so engaged, setting the AC V to equal the maximum number of nodes in the network (Fig. 3-72).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.