Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-06-08
2003-09-09
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S389000
Reexamination Certificate
active
06618371
ABSTRACT:
BACKGROUND
A switching network typically is made of input ports and output ports that are interconnected by switches and wires, as described in, for example, U.S. Pat. No. 5,521,591 (incorporated by reference herein in its entirety). As described in column 1, lines 17-19 of U.S. Pat. No. 5,521,591, each wire in the network serves as a conduit for transmitting a message from one of its ends to the other of its ends. The term wire (or connection) includes any means for communicating data between switches, such as electrical wires, parallel groups of wires, optical fibers, multiplexed channels over single wires, or free space radio or optical communication paths. A switch (shown in FIG. 1 of U.S. Pat. No. 5,521,591 and attached hereto as
FIG. 1
) is an atomic unit that resembles a switching network in function (i.e., a switch has input ports
1
A and
1
B and output ports
1
C and
1
D, and connects the input ports to the output ports in any desired pattern).
A switching network may route any kind of digital or analog data including voice or video signals. In some networks, the routing is accomplished by setting of switches so that input ports become directly coupled to output ports (e.g., in a telephone network). In other networks, the inputs ports do not become directly coupled to the output ports. Instead, the messages are routed as packets through the network in steps. Typical examples of networks in which switching networks are used include telephone networks, data networks, computer networks, and interconnection networks in parallel data processing systems.
A butterfly network
2
(shown in FIG. 5 of U.S. Pat. No. 5,521,591 and attached hereto as
FIG. 2
) is a common example of a switching network. Network
2
is referred to as a butterfly network because the connections between nodes form a pattern resembling a butterfly. A butterfly network has the same number of inputs as it has outputs. The inputs are connected to the outputs via a set of switches organized into successive levels of switches. An N-input, N-output butterfly network has log
2
N+1 (hereinafter log
2
will be referred to as 1 g) levels of switches, each level having N 2×2 switches. Each switch
3
in the butterfly
2
has a distinct reference label <L,r> where L is its level, and r is its row. In an N-input butterfly, the level L is an integer between 0 and 1 gN, and the row r is a 1 gN-bit binary number. The inputs and outputs reside on levels 0 and 1 gN, respectively. For L<1 gN, a switch labeled <L,r> is connected to switches <L+1,r> and <L+1,r
(L)
> and, where r
(L)
denotes r with the Lth bit complemented.
U.S. Pat. No. 5,521,591 also teaches that “a butterfly contains just one path from each input port to each output port” (in column 8, lines 39-42), and suggests a “multibutterfly contains many paths from each input to each output port” (column 8, lines 42-43). Regarding such a multibutterfly, U.S. Pat. No. 5,521,591 states (column 8, lines 43-46) “[i]ndeed, there is still just one logical (up-down) path from any input to any output, but this logical path can be realized as any one of several physical paths.”
SUMMARY OF INVENTION
In a butterfly network in accordance with the invention, a number of switches are set to provide two paths that are independent of each other (also called “node disjoint paths”), a first path from a first switch to a second switch, and a second path from the same first switch to a third switch. The switches to be set (from among a number of levels of switches in the butterfly network) are identified by performing a number of predetermined operations depending on locations of the first switch, the second switch and the third switch relative to one another.
Specifically, the to-be-set switches are identified by: starting with a switch at the end of a path (e.g. the first switch) as a preceding switch, changing a level number (e.g. incrementing the level number) of the preceding switch, and changing a bit of the row number of the preceding switch (e.g. replacing with a corresponding bit (or its inverse) from the row number of the other path end switch), thereby to identify a next switch in the path. The just-described two acts of changing are repeated, with the just-identified next switch as the preceding switch, until the other end of the path is reached. During the repetition, if a boundary of the butterfly network is reached (e.g. the last level is reached), direction of the path is reversed (e.g. by decrementing the level number), and the repetition is continued.
The two paths that are identified can be used to transfer information (also referred to as “traffic”) through the butterfly network. In one embodiment, the two paths are used to redundantly route traffic from a source switch to a destination switch, for load balancing or for fault tolerance. Specifically, if, in addition to the just-described two paths, the second switch and the third switch are directly coupled (also referred to as “connected”) to one another in the butterfly network (with just a connection and no intervening switches), then the two paths and the connection form a “ring.” Any two of the three switches in such a ring can be used as source and destination switches for routing the traffic through either or both paths in the ring. For example, initially a source switch is designated as the first switch, a destination switch is designated as the second switch, and any switch connected to the second switch is designated as the third switch. Thereafter, the two paths (from the first switch to the second and third switches) are identified, thereby to identify redundant routes between the source and destination switches.
If the second and third switches are not directly connected, but coupled through one or more switches (also called “intervening switches”) in the butterfly network, then two paths and connections between the intervening switches form a ring that is used as described above. Irrespective of whether the second and third switches are coupled to each other, the same traffic can be multicast, from the first switch (source switch) over the first path and over the second path to each of the second switch and the third switch (both of which act as destination switches).
REFERENCES:
patent: 4706240 (1987-11-01), Payne, III
patent: 4845736 (1989-07-01), Posner et al.
patent: 4933936 (1990-06-01), Rasmussen et al.
patent: 5040173 (1991-08-01), Richards
patent: 5153843 (1992-10-01), Batcher
patent: 5251097 (1993-10-01), Simmons et al.
patent: 5253359 (1993-10-01), Spix et al.
patent: 5361363 (1994-11-01), Wells et al.
patent: 5504743 (1996-04-01), Drefenstedt
patent: 5521591 (1996-05-01), Arora et al.
patent: 5566342 (1996-10-01), Denneau et al.
patent: 5689661 (1997-11-01), Hayashi et al.
patent: 5842207 (1998-11-01), Fujiwara et al.
patent: 5940367 (1999-08-01), Antonov
patent: 6205532 (2001-03-01), Carvey et al.
patent: 6370145 (2002-04-01), Dally et al.
“On the bisection width and expansion of butterfly networks” Bornstein, C.; Litman, A.; Maggs, B.M.; Sitaraman, R.K.; Yatzkar, T. Parallel Processing Symposium, 1998. IPPS/SPDP 1998.*
“Embedding complete binary trees into butterfly networks” Gupta, A.K.; Hambrusch, S.E. Computers, IEEE Transactions on , vol.: 40 Issue: 7 , Jul. 1991, pp.: 853-863.*
F. Thomas Leighton, “Introduction To Parallel Algorithms And Architectures: Arrays, Trees, Hypercubes,” Section 3.5.4,Randomized O(log N)-Step Sorting Algorithms, 1992, pp. 693-696.
F. Thomas Leighton, “Introduction to Parallel Algorithms And Architectures: Arrays, Trees, Hypercubes,” Section 3.7.4,Application to Integer Multiplication, 1992, pp. 729-741.
F. Thomas Leighton, “Introduction To Parallel Algorithms And Architectures: Arrays, Trees, Hypercubes,” Section 3.2,The Butterfly, Cube Connected-Cycles, and Bene{haeck over (s)} Network, 1992, pp. 439-472.
F. Thomas Leighton, “Introduction To Parallel Algorithms And Architectures: Arrays, Trees, Hypercubes,” Section 3.4,Packet-Routing Algorithms, 1992, pp. 511-546.
F. Thomas Leighton, “Introd
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Kizou Hassan
Odland David
LandOfFree
Butterfly network with switches set for two node disjoint... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Butterfly network with switches set for two node disjoint..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Butterfly network with switches set for two node disjoint... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3023348