US6101550A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and structure for interrupt polling signal bandwidth allocation in universal serial bus (USB) system
Assignee: Oracle America Inc
•
Filing: 1997-03-10
•
Granted: 2000-08-08
•
Expires: 2017-03-10
Abstract
Abstract A Universal Serial Bus (USB) controller includes an allocation unit configured to allocate bandwidths to a plurality of nodes in a polling list, each node being capable of storing at least one descriptor representing a respective polling signal. The nodes are arranged in a binary tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node. The allocation unit is configured to store variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof. It assigns a new device to a node such that a maximum value of P+S for the nodes at each level is minimized. The allocation unit adds a descriptor representing a new polling signal to a node in a specified level which has a minimum value of P+S. After adding a descriptor to a node, the allocation unit alters values of S for the node and all predecessor nodes thereof by adding the bandwidth of the new polling signal represented by the descriptor to the values of S, and alters values of P for successor nodes thereof in accordance with the bandwidth of the polling signal represented by the descriptor.
Inventors
- 👤 J. Steven Zucker
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:21
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/20; G06F13/24
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
199 words
A computer system, comprising: a computer; at least one peripheral unit; a signal bus connecting the computer to the at least one peripheral unit; and a controller configured to send periodic polling signals to the at least one peripheral unit, each polling signal having a specified bandwidth, the controller including; an allocation unit configured to allocate bandwidths to a plurality of nodes in a polling list, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the allocation unit being configured to store variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and the allocation unit being configured to allocate bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 2
Dependent Claim
199 words
A computer system, comprising: a computer; at least one peripheral unit; a signal bus connecting the computer to the at least one peripheral unit; and a controller configured to send periodic polling signals to the at least one peripheral unit, each polling signal having a specified bandwidth, the controller including; an allocation unit configured to allocate bandwidths to a plurality of nodes in a polling list, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the allocation unit being configured to store variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and the allocation unit being configured to allocate bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 3
Dependent Claim
36 words
A system as in claim 1, in which the allocation unit is configured to add a descriptor representing a new polling signal to a node in a specified level which has a minimum value of P+S.
Claim 4
Dependent Claim
51 words
A system as in claim 2, in which the allocation unit is configured to, after adding a descriptor to a node, alter values of S for the node and all predecessor nodes thereof by adding a bandwidth of the new polling signal represented by the descriptor to the values of S.
Claim 5
Dependent Claim
42 words
A system as in claim 2, in which the allocation unit is configured to, after adding a descriptor to a node, alter values of P for successor nodes thereof in accordance with the bandwidth of the polling signal represented by the descriptor.
Claim 6
Dependent Claim
38 words
A system as in claim 1, in which: the tree structure is a binary tree structure; and each level provides a polling signal period which is two times longer than a polling signal period of a successor level.
Claim 7
Dependent Claim
25 words
A system as in claim 1, in which: the signal bus is a Universal Serial Bus (USB); and the polling signals are interrupt polling signals.
Claim 8
Dependent Claim
155 words
A bandwidth allocation system configured to allocate bandwidths to a plurality of nodes in a polling list for a Universal Serial Bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the system comprising: a storage configured to store variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and an allocation unit configured to allocate bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 9
Dependent Claim
155 words
A bandwidth allocation system configured to allocate bandwidths to a plurality of nodes in a polling list for a Universal Serial Bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the system comprising: a storage configured to store variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and an allocation unit configured to allocate bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 10
Dependent Claim
36 words
A system as in claim 7, in which the allocation unit is configured to add a descriptor representing a new polling signal to a node in a specified level which has a minimum value of P+S.
Claim 11
Dependent Claim
50 words
A system as in claim 8, in which the allocation unit is configured to, after adding a descriptor to a node, alter values of S for the node and all predecessor nodes thereof by adding a bandwidth of the polling signal represented by the descriptor to the values of S.
Claim 12
Dependent Claim
42 words
A system as in claim 8, in which the allocation unit is configured to, after adding a descriptor to a node, alter values of P for successor nodes thereof in accordance with the bandwidth of the polling signal represented by the descriptor.
Claim 13
Dependent Claim
38 words
A system as in claim 7, in which: the tree structure is a binary tree structure; and each level provides a polling signal period which is two times longer than a polling signal period of a successor level.
Claim 14
Dependent Claim
15 words
A system as in claim 7, in which the polling signals are interrupt polling signals.
Claim 15
Dependent Claim
149 words
A computer implemented method for allocating bandwidths to a plurality of nodes in a polling list for a signal bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the method comprising the steps of: (a) storing variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and (b) allocating bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 16
Dependent Claim
149 words
A computer implemented method for allocating bandwidths to a plurality of nodes in a polling list for a signal bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the method comprising the steps of: (a) storing variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and (b) allocating bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 17
Dependent Claim
33 words
A method as in claim 13, in which step (b) comprises adding a descriptor representing a new polling signal to a node in a specified level which has a minimum value of P+S.
Claim 18
Dependent Claim
48 words
A method as in claim 14, in which step (b) further comprises, after adding a descriptor to a node, altering values of S for the node and all predecessor nodes thereof by adding a bandwidth of the polling signal represented by the descriptor to the values of S.
Claim 19
Dependent Claim
40 words
A method as in claim 14, in which step (b) further comprises, after adding a descriptor to a node, altering values of P for successor nodes thereof in accordance with the bandwidth of the polling signal represented by the descriptor.
Claim 20
Dependent Claim
38 words
A method as in claim 13, in which: the tree structure is a binary tree structure; and each level provides a polling signal period which is two times longer than a polling signal period of a successor level.
Claim 21
Dependent Claim
25 words
A method as in claim 13, in which: the signal bus is a Universal Serial Bus (USB); and the polling signals are interrupt polling signals.
Claim 22
Dependent Claim
159 words
A digital data storage structure which stores a computer program for allocating bandwidths to a plurality of nodes in a polling list for a signal bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the computer program including instructions for performing the steps of: (a) storing variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and (b) allocating bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 23
Dependent Claim
159 words
A digital data storage structure which stores a computer program for allocating bandwidths to a plurality of nodes in a polling list for a signal bus, each node being capable of storing at least one descriptor representing a respective polling signal; the nodes being arranged in a tree structure having a plurality of leaf nodes, a root node, and at least one level of intermediate nodes which are successor nodes for the leaf nodes and predecessor nodes for the root node; the computer program including instructions for performing the steps of: (a) storing variables P and S for each node, where P is a maximum bandwidth of polling signals entering a node from predecessor nodes, and S is a sum of bandwidths of polling signals represented by descriptors stored in the node and all successor nodes thereof; and (b) allocating bandwidths to the nodes such that a maximum value of P+S for the nodes at each level is minimized.
Claim 24
Dependent Claim
33 words
A structure as in claim 19, in which step (b) comprises adding a descriptor representing a new polling signal to a node in a specified level which has a minimum value of P+S.
Claim 25
Dependent Claim
48 words
A structure as in claim 20, in which step (b) further comprises, after adding a descriptor to a node, altering values of S for the node and all predecessor nodes thereof by adding a bandwidth of the polling signal represented by the descriptor to the values of S.
Claim 26
Dependent Claim
40 words
A structure as in claim 20, in which step (b) further comprises, after adding a descriptor to a node, altering values of P for successor nodes thereof in accordance with the bandwidth of the polling signal represented by the descriptor.
Claim 27
Dependent Claim
38 words
A structure as in claim 19, in which: the tree structure is a binary tree structure; and each level provides a polling signal period which is two times longer than a polling signal period of a successor level.
Claim 28
Dependent Claim
25 words
A structure as in claim 19, in which: the signal bus is a Universal Serial Bus (USB); and the polling signals are interrupt polling signals.
Claim 29
Dependent Claim
16 words
A structure as in claim 19, comprising an electronic memory configured to store the computer program.
Claim 30
Dependent Claim
19 words
A structure as in claim 19, comprising at least one digital recording medium configured to store the computer program.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-08 | 2004-02-07 | 2004-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-08 | 2008-02-07 | 2008-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-08 | 2012-02-07 | 2012-08-08 | $7700.00 | Window Closed / Lapsed |