Routing of network traffic
AssigneeBell Communications Research, Inc.
InventorFan R. K. Chung
Life of this patent
Estimating the term…
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.
Claims11
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.noteq.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.
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.noteq.j, configuring the network with a unidirectional link from said i.sup.th to said j.sup.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.sub.1, x.sub.2, . . . x.sub.k } having distinct partial sums as determined by network grade-of-service considerations,
- selecting admissible routes from s to r, s.noteq.r, in correspondence to set-member sums x.sub.1 +x.sub.2 + . . . +x.sub.k +x.sub.m + . . . +x.sub.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.
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.noteq.j, and distinct partial sums having an odd number of set integers corresponding to all (i+j) (mod n) summations, i.noteq.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.
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.noteq.j, configuring the network with a bidirectional link from said i.sup.th to said j.sup.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.sub.1, x.sub.2, . . . x.sub.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.noteq.r, in correspondence to even set sums x.sub.1 -x.sub.2 +x.sub.3 -x.sub.4 + . . . +x.sub.e equaling (s-r) (mod n), or odd set sums x.sub.1 -x.sub.2 +x.sub.3 -x.sub.4 + . . . -x.sub.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.
Dependencies are inferred from the claim text.