Patent ID: 7315517

Claim:
A method for routing calls in an optical network comprising an n-dimensional, virtual or nonvirtual, binary hypercube of 2 n nodes, wherein n is an integer 2 or greater; wherein one or zero calls originate from each node; wherein calls originating from different nodes may be the same or different; wherein each node may be identified by a unique n-bit binary label; wherein each node is connected to n other nodes; wherein the labels of any two directly connected nodes differ in one, and only one bit; said method comprising routing calls over paths between the nodes in accordance with a special broadcast tree associated with each node; wherein the special broadcast tree for each node has the same structure relative to its source node, wherein the source node is the node with which the special broadcast tree is associated; and wherein the special broadcast tree for any given source node, satisfies each of the following criteria: (a) the special broadcast tree comprises a plurality B of major subtrees, wherein each major subtree is associated with one node that is directly connected to the source node; and wherein each major subtree defines a set of paths for delivering a call to a proper subset of the nodes in the hypercube; and wherein no more than one directly connected pair of nodes within the same major subtree differs at the same bit position of their respective labels; (b) each node other than the source node, is contained in at least one major subtree; (c) the number of major subtrees B is greater than or equal to B n , wherein B n = ( n k - 1 ) + ⌈ ( 2 n - 1 ) - [ ( n k - 1 ) ⁢ ( n - k + 2 ) + ( ⁢ ∑ i = 1 k - 2 ⁢ ⁢ ( n i ) ) ] n - k + 1 ⌉ wherein k is the smallest integer such that ( n k ) ⁢ ( n - k + 1 ) + ∑ i = 1 k - 1 ⁢ ⁢ ( n i ) ≥ 2 n - 1 and (d) each of the B major subtrees uses a different wavelength to carry calls from the source node to all nodes contained in the major subtree; and wherein all paths within a given major subtree use the same wavelength; and wherein all nodes within the special broadcast tree receive the same call from the source node; whereby: none of the calls in the network blocks any other call in the network.