US5535213A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ring configurator for system interconnection using fully covered rings
Assignee: International Business Machines Corp
•
Filing: 1994-12-14
•
Granted: 1996-07-09
•
Expires: 2014-12-14
Abstract
Abstract A ring configurator for interconnection of data processing and communication systems uses fully covered rings. The ring configuration mechanism can be used to construct a set of covering rings preserving full connectivity for system interconnect. The mechanism can also be used for establishing the routing table for each interconnected system during the system initialization time. To generate a set of edge-disjoint rings, a rotational mechanism is used. The rings are considered stretching along a horizontal direction with nodes aligned in columns across all the rings. With a proper relabeling of the nodes, nodes appearing in the same column position of each ring can be obtained by a simple rotation of the nodes from the previous column of the rings. Once the rotational position is determined for each column, a set of N-1 edge-disjoint rings can be constructed. To find an extra ring so that when combined with the N-1 rings thus found the ring constraints are satisfied, a node reduction technique is invoked. The procedure can be repeated until a set of N edge-disjoint rings satisfying the constraints are found.
Inventors
- 👤 Shien-Tai Pan
- 👤 Ting Cheng
- 👤 Christos J. Georgiou
- 👤 George W. Nation
- 👤 Chung-Sheng Li
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 22:06
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L12/00; H04L12/28; H04L12/46; H04L12/4637
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
84 words
A ring configurator method for interconnection of nodes by edges in a network wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: storing at each node information defining the number of nodes and the number of edges on each node in the network; and generating at each node a consistent set of routing tables for routing said data packets within said network only when said tables are required to configure or reconfigure the network.
Claim 2
Dependent Claim
84 words
A ring configurator method for interconnection of nodes by edges in a network wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: storing at each node information defining the number of nodes and the number of edges on each node in the network; and generating at each node a consistent set of routing tables for routing said data packets within said network only when said tables are required to configure or reconfigure the network.
Claim 3
Dependent Claim
64 words
The ring configurator method recited in claim 1 wherein said step of generating including decomposing the fully connected network into rings, assuming a fully connected network, to meet the following three constraints: a. the rings are edge-disjoint, b. the union of the rings covers a fully connected graph of the network, and c. no two distinct rings go through the same set of nodes.
Claim 4
Dependent Claim
59 words
The ring configurator method recited in claim 2 further comprising the step of selecting a subset which is composed of (N-1)×R edges (where N is the number of nodes and R is the number of selected rings) is less than N×E edges (where 2E is the number of edges on each node and E<N-1 for satisfying the non-saturated condition.
Claim 5
Dependent Claim
36 words
The ring configurator method recited in claim 1 wherein the step of decomposing meets the constraint that there are exactly N-1 nodes in each ring, where N is the total number of nodes in the graph.
Claim 6
Independent Claim
124 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes, the number of edges on each node and a unique identification number to each node in the network; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 7
Independent Claim
124 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes, the number of edges on each node and a unique identification number to each node in the network; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 8
Dependent Claim
95 words
The method for adaptively configuring a network as recited in claim 5 wherein the network is reconfigured upon a change in the number of nodes and edges in the network, further comprising the steps of: sending an interrupt to each node in the network; supplying each node in the network with a new number of nodes and edges on each node in the network; and reinitializing the network by running said program at each node of the network to generate a new consistent set of routing tables for routing said data packets within said network.
Claim 9
Independent Claim
141 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network, wherein said information defining the number of nodes and the number of edges on each node in the network is stored at each node; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 10
Independent Claim
141 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network, wherein said information defining the number of nodes and the number of edges on each node in the network is stored at each node; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 11
Independent Claim
150 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network, wherein said information defining the number of nodes and the number of edges on each node in the network is supplied to each of said nodes from a central source at network initialization; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 12
Independent Claim
150 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network, wherein said information defining the number of nodes and the number of edges on each node in the network is supplied to each of said nodes from a central source at network initialization; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 13
Independent Claim
191 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network, said program including the steps of searching for increments by which nodes in the network may be rotated to define a plurality of rings in said network, checking rings in the network derived by the increments to determine if one less than a total number of rings when removed from the network leaves a single complete ring, if a single complete ring is left, storing the increments, otherwise repeating the searching and checking steps; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
Claim 14
Independent Claim
191 words
A method for adaptively configuring a network composed of a plurality of nodes interconnected by a plurality of edges wherein data packets are transmitted from an origination node to a destination node, said method comprising the steps of: supplying to each node in the network information defining the number of nodes and the number of edges on each node in the network; at network initialization, running a program at each node of the network to generate a consistent set of routing tables for routing said data packets within said network, said program including the steps of searching for increments by which nodes in the network may be rotated to define a plurality of rings in said network, checking rings in the network derived by the increments to determine if one less than a total number of rings when removed from the network leaves a single complete ring, if a single complete ring is left, storing the increments, otherwise repeating the searching and checking steps; and storing at each node information from the generation of said routing tables from which routing decisions can be made for data packets received at the node.
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) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |