Patent US5206856A successfully refreshed from Google Patents.
US5206856A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing of network traffic
Assignee: Nytell Software LLC
•
Filing: 1990-11-21
•
Granted: 1993-04-27
•
Expires: 2010-11-21
Abstract
Abstract A method is disclosed for configuring a network, composed of a plurality of nodes, to satisfy grade-of-service constraints such as traffic load and cost and, upon configuration, routing of service requests through admissible routes in the network in correspondence to the configuration topology. Both the configuration and routing are mutually dependent upon the selection of a set of integers which provide distinct sums over the integers in the set. The integers determine link interconnections between the nodes and the distinct sums are indicative of the admissible routes.
Inventors
- 👤 Fan R. K. Chung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 08:48
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
96 words
A method for physically implementing a directed network composed of a plurality n of nodes, with i and j representing an arbitrary pair of the nodes, the method comprising the steps of selecting a set X of k integers as determined by network grade-of-service constraints, wherein said set X is selected to produce distinct partial sums corresponding to all (j-i) (mod n) differences, i≠j, and interconnecting the network nodes with unidirectional links from node i to node j if and only if (j-i) (mod n)=x for some x in X as determined by said partial sums.
Claim 2
Independent Claim
96 words
A method for physically implementing a directed network composed of a plurality n of nodes, with i and j representing an arbitrary pair of the nodes, the method comprising the steps of selecting a set X of k integers as determined by network grade-of-service constraints, wherein said set X is selected to produce distinct partial sums corresponding to all (j-i) (mod n) differences, i≠j, and interconnecting the network nodes with unidirectional links from node i to node j if and only if (j-i) (mod n)=x for some x in X as determined by said partial sums.
Claim 3
Independent Claim
171 words
A method for transmitting a packet over a directed network composed of a plurality n of nodes, the packet originating in node s and destined for node r, the method comprising the steps of interconnecting network nodes with links according to the relationship: for each node pair i and j, i≠j, configuring the network with a unidirectional link from said i th to said j th node if and only if (j-i) (mod n)=x for some x in X, where X is a predefined set of k integers {x 1 , x 2 , . . . x k } having distinct partial sums as determined by network grade-of-service considerations, selecting admissible routes from s to r, s≠r, in correspondence to set-member sums x 1 +x 2 + . . . +x k +x m + . . . +x n equaling (r-s) (mod n), and transmitting the packet from node s to node r along a selected one of said admissible routes in correspondence to the (r-s) (mod n) difference.
Claim 4
Independent Claim
171 words
A method for transmitting a packet over a directed network composed of a plurality n of nodes, the packet originating in node s and destined for node r, the method comprising the steps of interconnecting network nodes with links according to the relationship: for each node pair i and j, i≠j, configuring the network with a unidirectional link from said i th to said j th node if and only if (j-i) (mod n)=x for some x in X, where X is a predefined set of k integers {x 1 , x 2 , . . . x k } having distinct partial sums as determined by network grade-of-service considerations, selecting admissible routes from s to r, s≠r, in correspondence to set-member sums x 1 +x 2 + . . . +x k +x m + . . . +x n equaling (r-s) (mod n), and transmitting the packet from node s to node r along a selected one of said admissible routes in correspondence to the (r-s) (mod n) difference.
Claim 5
Dependent Claim
30 words
The method as recited in claim 2 wherein said admissible routes are identified by referring to a look-up table stored in each of the nodes receiving the packet for processing.
Claim 6
Dependent Claim
121 words
The method as recited in claim 3 wherein the destination node r is embedded as packet information, the packet traverses an intermediate node t as the packet is transmitted from node s to node r and the method further comprises the steps of parsing the packet as it arrives at the intermediate node t as the packet traverses said selected one of said routes, in the intermediate node t, determining an intermediate difference (r-t) (mod n) and entering said look-up table assigned to the intermediate node with said intermediate difference to determine an intermediate route from the set of admissible routes associated with the intermediate node t, and forwarding the packet along said intermediate route in correspondence to said intermediate difference.
Claim 7
Dependent Claim
28 words
The method as recited in claim 2 wherein each of said admissible routes contains at least the largest set-member sum which is ≦(j-i) (mod n) for all i≠j.
Claim 8
Dependent Claim
57 words
The method as recited in claim 2 wherein said selected one of said routes, being associated with one of said set-member sums, is composed of selected links corresponding to distinct set integers in said associated set-member sum, and wherein said selected links may be traversed in any order corresponding to a permutation of said distinct set integers.
Claim 9
Independent Claim
129 words
A method for physically implementing an undirected network composed of a plurality n of nodes, with i and j representing an arbitrary pair of the nodes, the method comprising the steps of selecting a set X of k integers as determined by network grade-of-service constraints, wherein said set X is selected to produce distinct alternating partial sums having an even number of set integers corresponding to all (i-j) (mod n) differences, i≠j, and distinct partial sums having an odd number of set integers corresponding to all (i+j) (mod n) summations, i≠j, and interconnecting the network nodes with bidirectional links from node i to node j if and only if (j+i) (mod n)=x for some x in X as determined by said alternating partial sums and said distinct partial sums.
Claim 10
Independent Claim
129 words
A method for physically implementing an undirected network composed of a plurality n of nodes, with i and j representing an arbitrary pair of the nodes, the method comprising the steps of selecting a set X of k integers as determined by network grade-of-service constraints, wherein said set X is selected to produce distinct alternating partial sums having an even number of set integers corresponding to all (i-j) (mod n) differences, i≠j, and distinct partial sums having an odd number of set integers corresponding to all (i+j) (mod n) summations, i≠j, and interconnecting the network nodes with bidirectional links from node i to node j if and only if (j+i) (mod n)=x for some x in X as determined by said alternating partial sums and said distinct partial sums.
Claim 11
Independent Claim
219 words
A method for transmitting a packet over an undirected network composed of a plurality n of nodes, the packet originating in node s and destined for node r, the method comprising the steps of interconnecting network nodes with links according to the relationship: for each node pair i and j, i≠j, configuring the network with a bidirectional link from said i th to said j th node if and only if (i+j) (mod n)=x for some x in X, where X is a predefined set of k integers {x 1 , x 2 , . . . x k } having distinct partial summations with an odd number of terms and distinct partial differences with an even number of terms as determined by network grade-of-service considerations, selecting admissible routes from s to r, s≠r, in correspondence to even set sums x 1 -x 2 +x 3 -x 4 + . . . +x e equaling (s-r) (mod n), or odd set sums x 1 -x 2 +x 3 -x 4 + . . . -x 0 equaling (s+r) (mod n), and transmitting the packet from node s to node r along a selected one of said admissible routes in correspondence to the fewest number of links in either the (s-r) (mod n) difference or the (s+r) (mod n) summation.
Claim 12
Independent Claim
219 words
A method for transmitting a packet over an undirected network composed of a plurality n of nodes, the packet originating in node s and destined for node r, the method comprising the steps of interconnecting network nodes with links according to the relationship: for each node pair i and j, i≠j, configuring the network with a bidirectional link from said i th to said j th node if and only if (i+j) (mod n)=x for some x in X, where X is a predefined set of k integers {x 1 , x 2 , . . . x k } having distinct partial summations with an odd number of terms and distinct partial differences with an even number of terms as determined by network grade-of-service considerations, selecting admissible routes from s to r, s≠r, in correspondence to even set sums x 1 -x 2 +x 3 -x 4 + . . . +x e equaling (s-r) (mod n), or odd set sums x 1 -x 2 +x 3 -x 4 + . . . -x 0 equaling (s+r) (mod n), and transmitting the packet from node s to node r along a selected one of said admissible routes in correspondence to the fewest number of links in either the (s-r) (mod n) difference or the (s+r) (mod n) summation.
Claim 13
Dependent Claim
30 words
The method as recited in claim 8 wherein said admissible routes are identified by referring to a look-up map stored in each of the nodes receiving the packet for processing.
Claim 14
Dependent Claim
127 words
The method as recited in claim 9 wherein the destination node r is embedded as packet information the packet traverses an intermediate node t as the packet is transmitted from node s to node r and the method further comprises the steps of parsing the packet as it arrives at the intermediate node t as the packet traverses said selected one of said routes, in the intermediate node t, determining an intermediate difference (t-r) (mod n) and an intermediate summation (t+r) (mod n) and entering said look-up map assigned to the intermediate node t with said intermediate difference and said intermediate summation to determine an intermediate route from the set of admissible routes associated with the intermediate node t and forwarding the packet along said intermediate route.
Claim 15
Dependent Claim
57 words
The method as recited in claim 8 wherein said selected one of said routes, being associated with one of said set sums, is composed of selected links corresponding to distinct set integers in said associated set sum, and wherein said selected links may be traversed in any order corresponding to a permutation of said distinct set integers.
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) | 1996-04-26 | 1996-10-26 | 1997-04-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-04-26 | 2000-10-26 | 2001-04-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-04-26 | 2004-10-26 | 2005-04-27 | $7700.00 | Window Closed / Lapsed |