Patent Description:
A folded Clos topology combines a large number of small switches to create a much larger virtual switch. A Clos topology consists of two stages. An upper stage (aka spine), and a lower stage. Every switch in the lower stage is connected to every switch in the upper stage. The upper stage allows for information to be transported between switches of the lower stage. Folded Clos topology are one way to create large virtual switches from small switches, but there are also other ways, such as a butterfly network or a dragonfly network. The upper and/or lower stages of the network can be built from Clos topologies themselves, and can thus consist of several sub-stages. The Clos topology can also be said to be made of three stages when an access stage, which connects to a lower stage, is considered.

A Clos topology includes multiple stages of switches. A switch is a hardware device, which includes a number of ports, and interconnects stages of the Clos topology through the ports. The number of ports on the switch is also referred to as the switch radix. A spine switch, such as a switch in the upper stage, receives information from a switch in the lower stage and sends this information back to the appropriate switch in the lower stage. In this manner, the spine switch allows for the flow of information between switches of the lower stage. In a typical <NUM>-port switch in the lower stage, two ports are used to connect to the upper stage, while the other two ports are free, and can be connected to any network device, such as a host, in the access stage.

However, existing Clos topologies do not exploit the full radix of the switches in the lower stage. Existing switches allow for information received by any port on the switch to be sent to any other port on the switch, but switches in the lower stage only need to forward to a subset of their ports. More recent architectures such as flattened butterfly and dragonfly have emerged as alternative lower-cost architectures but suffer from performance issues and complexity in other areas such as oversubscription and manageability.

<NPL>), discloses a commercial 50Tbps Infiniband packet switch with <NUM> ports running 40Gbps per port enabled by <NUM>-channel full-duplex active optical cables with 10Gbps per channel per direction of optical I/O.

<CIT>) discloses a switch system wherein L groups of the line switch elements are connectable to cables that include L links such that each of the L links within a cable connect to a switch element of a respective one of the L groups. Fabric switch elements are connected such that a fabric switch element is connected to the line switch elements of one of the group of line switch elements.

One aspect of the technology provides a system including an upper stage consisting of a plurality of traditional switches, a lower stage consisting of one or more linecards, each of the linecards comprising a plurality of upper ports and a plurality of lower ports, a bottom-up switch, and a top-down switch, wherein all traffic moving from the lower stage to the upper stage is received by a bottom up switch and sent via the bottom up switch to the upper stage, and all traffic moving from the upper stage to the lower stage is received by a top-down switch and sent via the top-down switch to the lower stage.

Another aspect of the technology provides a linecard including a plurality of upper ports, a plurality of lower ports, a bottom-up switch, a top-down switch, first connections between the plurality of the lower ports, the bottom up switch, and the upper ports, second connections between the plurality of lower ports, the top-down switch, and the upper ports, and wherein all traffic received at a lower port is sent to the upper port via first connections, and all traffic received at an upper port is sent to a lower port via second connections.

Another aspect of the technology provides a linecard including a plurality of upper ports, a plurality of lower ports, a bottom-up switch, a top-down switch, first connections between the plurality of the lower ports, the bottom up switch, and the upper ports, second connections between the plurality of lower ports, the top-down switch, and the upper ports, wherein all traffic received at a lower port is sent to the upper port via first connections, and all traffic received at an upper port is sent to a lower port via second connections, configuring the line card to have an equal number of upper ports and lower ports, configuring the ports to be connected to the bottom-up switch and top-down switch of the linecard, configuring the ports of the bottom-up switch and the top-down switch to have separate connections or interfaces for incoming traffic and outgoing traffic, and using printed circuit boards, metallic wires, or optical wires to create the first connections and/or second connections.

Another aspect of the technology provides a method to create a folded Clos network, the method including providing an upper stage consisting of traditional switches, providing a lower stage consisting of one or more linecards, providing an access stage consisting of one or more access points, connecting the ports of the traditional switches with the ports of the linecards, connecting the ports of the access points with the ports of the linecards, wherein each of the one or more linecards comprises a plurality of upper ports and a plurality of lower ports, a bottom-up switch, and a top-down switch, measuring the network for network parameters, and optimizing the network for at least one metric based upon the measured network parameters.

The technology generally relates to a system that provides the ability to double the non-blocking throughput of a folded Clos topology. This is achieved by replacing a conventional switch used in a Clos topology with a new linecard which consists of two switch chips that each forward information uni-directionally. The present technology provides a method, system, and apparatus to create a topology including a multi-stage arrangement of independent switches. This topology is be used in various networks, such as data centers, wide area networks (WANs), or local area networks (LANs). The topology addresses an arrangement of switches and linecards in a network, as well as an arrangement of the switches with respect to one another and other network components.

According to an example, a novel multi-stage folded Clos network and a linecard for use in a network is disclosed. The Clos network can consist of three stages, an access stage, a lower stage, and an upper stage. The access stage and the upper stage can include a plurality of switches or conventional access points. The lower stage can include a plurality of linecards. Each linecard can be made of two switch chips, each of which are connected to the ports of the linecard, and contain the same number of ports. Each switch chip can forward information in only one direction and one is used to send direction from the access stage to the upper stage, and the other from the upper stage to the access stage. The lower stage can consist of a number of sub-stages, each sub-stage can be entirely of either conventional switches or linecards. Accordingly, compared to a conventional Clos network, the provided network can increase the throughput by any power of <NUM> by replacing the conventional switches used in the lower stage or sub-stages with linecards.

According to an example, a folded Clos network or folded Clos topology combines a number of small switches to create a much larger virtual switch. A virtual switch is one that is equivalent to a physical switch with a given number of input and output ports. Every stage of a Clos topology is made of switches. A switch is a hardware device - which consists of a number of ports - and interconnects stages of the Clos topology through the ports. The number of ports on the switch is also referred to as the switch radix. A switch in the upper stage or spine receives information from a switch in the lower stage and sends this information back to the appropriate switch in the lower stage. In this manner, a switch in the upper stage allows for the flow of information between switches of the lower stage. In a typical <NUM>-port switch in the lower stage, two ports are used to connect to the upper stage, while the other two ports are free, and can be connected to any network device, such as a host. While these principles are discussed on a <NUM>-port switch, the same principle apply when the switches have a larger number of switches, such as for example, an <NUM>-port, <NUM>-port, or <NUM> port switch.

However, existing Clos topologies do not exploit the full radix of the switches in the lower stage. Existing switches allow for information received by any port on the switch to be sent to any other port on the switch, but switches in the lower stage only need to forward to a subset of their ports.

The technology provides a technique and a device which can accomplish doubling the throughput of the Clos topology by replacing existing switches in the lower stage with <NUM>-port linecards. The new linecard or chassis switch can be made of two two-port switch chips, one of which can be used to forward information from free ports to the upper stage while the other can be used to forward information from the upper stage to free ports. If all conventional switches in the lower stage are replaced with such new linecards, the maximum amount of information which can be sent through the Clos topology can be doubled. A key feature of the technology is that other than replacement of conventional switches to linecards, other aspects of the network do not need to be modified to achieve this increased throughput. The technology also provides techniques and devices to replace existing switches with any number of ports, such as a k-port switch, with a linecard with the same number of ports, such as a k-port linecard.

A non-blocking network is one in which the input nodes and output nodes of the network are connected in such a manner that any combination of input and output nodes can communicate with one another at their respective port speeds, when particular conditions are met. Port speed is a measure of how fast information can be transmitted or received by a port interface. A folded Clos topology can always be configured to be non-blocking when particular conditions are met, making it a suitable topology for network applications involving multiple devices which request and/or send information from one another. However, the throughput of the non-blocking Clos topology is limited by the number of switches comprising the network.

<FIG> illustrates an example of a three stage folded Clos network, such as Clos network <NUM>. <FIG> illustrates a Clos network with three stages: an upper stage <NUM>, a lower stage <NUM>, and an access stage <NUM>. The upper stage <NUM> can have connections (which are illustrated but not numbered in <FIG>) with lower stage <NUM> and similarly, the lower stage <NUM> can have connections with the access stage <NUM>. An upper stage, such as the upper stage <NUM>, can include one or more switches, such as switch <NUM> and switch <NUM>. Although only two switches are depicted in <FIG>, the upper stage <NUM> can be made of any finite number of switches. First switch <NUM> can further contain a number of first ports, such as port <NUM>, and port <NUM>. Similarly, second switch <NUM> can contain a number of second ports, such as port <NUM>. The switches making up the upper stage <NUM> can contain as many ports as needed to connect with the switches of the lower stage <NUM>. Lower stage <NUM> can include a number of switches, such as switch <NUM> and switch <NUM>. Lower stage <NUM> can be made from any multitude of switches. Switch <NUM> can further include several ports, some interfacing with upper stage <NUM>, and others interfacing with lower stage <NUM>. For example, port <NUM> can interface with upper stage <NUM> by connecting with switch <NUM>. Other ports can interface with other switches of upper stage <NUM>, allowing for every switch of the middle stage to interface with the upper stage <NUM>. Similarly, port <NUM> can interface with access stage <NUM> by connecting with access point <NUM>. Thus, any access point can connect with any other access point through the Clos network. For example, access point <NUM> can connect with access point <NUM> through a path routed through access point <NUM> to switch <NUM>, switch <NUM> to switch <NUM>, switch <NUM> to switch <NUM>, and switch <NUM> to access point <NUM>. Links between stages <NUM>, <NUM>, and <NUM> can be made one or combination of multiple suitable technologies. For example, printed circuit boards, metallic wires, or optical wires can be used to interlink the various stages. Although the switches are depicted with <NUM> upper ports and <NUM> lower ports, the switches can contain any number of ports. The switches also allow for information received by any port of the switch to be sent to any other port of the switch, but switches in the lower stage only need to forward to a subset of their ports.

<FIG> is another illustration of a folded Clos topology which illustrates a subset of the set of paths that data flowing through the topology can take. Illustrated in <FIG> is Clos network <NUM>. In <FIG> upper stage <NUM>, the lower stage <NUM>, and the access stage <NUM> are connected as illustrated in <FIG>, but these intra-connections have been omitted in the figure for clarity.

One path that data can take is the path illustrated with a loop, such as a path originating in switch <NUM> of the upper stage <NUM>, through port <NUM> of switch <NUM>, into port <NUM> of switch <NUM>, through port <NUM> of switch <NUM>, and into port <NUM> of switch <NUM> of the upper stage <NUM>. Similarly, another path can originate at access point <NUM> of access stage <NUM>, move to the middle stage <NUM> through port <NUM> of switch <NUM>, through port <NUM> of switch <NUM>, and back to access point <NUM> of access stage <NUM>. Other similar paths can exist - between switches of the upper stage, such as switch <NUM> of upper stage <NUM>, and switches of the middle stage, such as switch <NUM> of middle stage <NUM> - and between access points in the access stage, such as access point <NUM> and switches of the middle stage, such as switch <NUM> of the middle stage <NUM>. These paths can occur because of the structure of the switch <NUM>. However, in practical applications, these paths are not needed as data coming from one point does not need to go back to the same point. By removing the possibility of these paths, the non-blocking throughput, that is the amount of information that can simultaneously be sent through the folded Clos topology, can be increased.

<FIG> illustrates a device, particularly a linecard <NUM>, according to one aspect of the current technology. Linecard <NUM> can contain for example, four ports, such as port <NUM>, port <NUM>, port <NUM>, and port <NUM>. Ports <NUM>-<NUM>, can in a manner similar to the ports <NUM>-<NUM> discussed above, be connected to various stages of a network, such as a Clos network, with for example some of the ports being connected to an upper stage of a network while other ports are connected to an access stage. For example, port <NUM> and port <NUM> can be connected to the upper stage of a network while port <NUM> and port <NUM> are connected to an access stage of a network. Ports <NUM>-<NUM> can for example be bidirectional ports, that is, the ports <NUM>-<NUM> can both receive and send information to the respective stages to which they are connected. For example, port <NUM> can both receive information from and send information to an upper stage. Ports <NUM>-<NUM>, and in turn the linecard <NUM>, can further be configured to be connected with one another to only allow information received by a port connected to one stage to send information to ports connected to another stage. For example, port <NUM>, which can be connected to an access stage can only send information it receives from the access stage to port <NUM> and port <NUM>, which are connected to an upper stage. Similarly, each port can be configured to forward information only to the ports which are not connected to the same stage as the port itself.

The configuration discussed in the paragraph above can be created, for example, through the use of two-port switch chips, such as switch chip <NUM> and switch chip <NUM>. Switch chip <NUM> can contain, for example, two ports, port <NUM> and port <NUM>. Similarly, switch chip <NUM> can contain, for example two ports, port <NUM> and port <NUM>. In an example, switch chip <NUM> can be configured to receive information flowing upwards through a network (that is, information flowing from an access stage to an upper stage received by either port connected to an access stage, such as port <NUM> and port <NUM>) and send this received information upwards (that is, send the information received to a port connected to the upper stage such as port <NUM> and port <NUM>). For example, switch chip <NUM> can receive this upwards flowing information from port <NUM> or port <NUM> at port <NUM> and port <NUM> respectively. Switch chip <NUM> can for example, after receiving this information at either port <NUM> or port <NUM> forward this information to port <NUM> or port <NUM> respectively. Once received at port <NUM> or port <NUM>, the information can then be forward onwards to the upper stage.

Similarly, switch chip <NUM> can be configured to receive information flowing downwards through a network (that is, information flowing from an upper stage to an access stage received by either port connected to the upper stage, such as port <NUM> and port <NUM>) and send this received information downwards (that is, send the information received to a port connected to the access stage, such as port <NUM> and port <NUM>). For example, switch chip <NUM> can receive information flowing downwards from port <NUM> and port <NUM> at port <NUM> and port <NUM> respectively. Switch chip <NUM> can for example, after receiving this information at either port <NUM> or port <NUM>, forward this downwards flowing information to port <NUM> or port <NUM> respectively.

Switch chips <NUM> and <NUM> can also be described as unidirectional forwarding switches, that is, they only receive and forward information in one direction. Switch <NUM> and switch <NUM> can also thus be described as "bottom-up" and "top-down" switches, respectively as they receive information from a bottom/lower stage or upper stage respectively, and forward the information up or down through the stages of the network. Thus, linecard <NUM> allows for information to be received and sent without information being looped back to the same stage from which the information was received as was the case illustrated in <FIG>. Linecard <NUM> does not allow for connections between ports connecting to the same stage of the Clos topology, such as between port <NUM> and port <NUM>, and between port <NUM> and port <NUM>. As further explained below, this configuration allows for the radix of linecard <NUM> to be double that of switch <NUM>.

As illustrated in <FIG>, the configuration above can be achieved, for example, by physically connecting wires from the port of the linecard, such as linecard <NUM>, to the ports of the switch chips, such as switch chip <NUM> or switch chip <NUM>. Incoming traffic wires can be connected to different linecard ports than the outgoing traffic wires. This can be achieved, for example, if a switch chip has in its ports different electrical wires, socket connections, for traffic that is incoming to the switch chip and traffic that is outgoing from the switch chip. In another example, the same result can be achieved by configuring the switch chip to either receive or send traffic using software. In yet another example, the switch chip and its wires can be patterned onto a printed circuit board in a manner that differentiates the incoming and outgoing traffic.

<FIG> illustrates a representation of some of the data connections within a network according to one aspect of the current technology, network <NUM>. <FIG> illustrates the equivalent network achieved by replacing a prior art switch, such as switch <NUM>, with a linecard of the present disclosure, such as linecard <NUM>. Network <NUM> can be made of an upper stage <NUM>, lower stage <NUM>, and an access stage <NUM>. Similar to the stages in network <NUM>, the upper stage <NUM> can consist of a number of switches, and the access stage <NUM> can be made of a number of access points, such as access point <NUM>. The lower stage <NUM> can be made of a number of line switches, such as line switch <NUM>. Components of stages <NUM>, <NUM>, and <NUM> contain ports to receive and send information which are not illustrated in <FIG>. Although not illustrated in <FIG> links exist between every switch of the upper stage <NUM> and the linecards of the lower stage <NUM>. Although linecard <NUM> is depicted as two separate components, linecard <NUM> is one component which can be, for example, similar to linecard <NUM> illustrated in <FIG>, and is illustrated as a bifurcated switch to show the equivalent number of non-blocking connections. Compared to a Clos network known in the prior art, such as network <NUM>, network <NUM> illustrates twice the number of data connections which can simultaneously be utilized in the network. For example, linecard <NUM> has <NUM> connections to the upper stage as compared to switch <NUM> of network <NUM>, which only has <NUM> connections. Each linecard in lower stage <NUM> similarly has double the number of connections when compared to a switch in lower stage <NUM>.

<FIG> illustrates an example of information flowing through a network of the present technology, network <NUM>. Network <NUM> contains an upper stage, such as upper stage <NUM>, made of upper switches, such as such as switch <NUM> and switch <NUM>, which can be for example <NUM> port switches; a lower stage, such as lower stage <NUM>, made only of linecards, such as linecards <NUM> and <NUM>; and an access stage, such as access stage <NUM> made of access points, such as access point <NUM> and <NUM>. Further, a plurality of bidirectional ports are illustrated in <FIG>, such as ports <NUM>-<NUM>, ports <NUM>-<NUM>, and ports <NUM>, <NUM>, <NUM>, and <NUM>. Illustrated in a dotted line with an 'x' is a path that information traveling from upper switch <NUM> to access point <NUM> cannot take through linecard <NUM>. Similarly illustrated in a dotted line with an 'x' is a path that information travelling from an access point <NUM> to switch <NUM> cannot take through linecard <NUM>. Replacing conventional switches with linecards of the present technology prevents these paths from ever being taken, and allows for the throughput of information through the network to be doubled.

<FIG> illustrates an example of a linecard of the current technology. As illustrated in <FIG>, the linecard can consist of a plurality of ports (not labeled), which can to other stages in a network, such as an access stage and an upper stage. All ports receiving information from a first stage, such as an access stage and sending it to a second stage, such as an upper stage, can be connected to a switch chip, such as switch chip <NUM> (labeled S1). Similarly, all ports receiving information from a second stage, such as an upper stage and sending it to a first stage, such as an access stage, can be connected to a second switch chip, such as switch chip <NUM> (labeled S2). Switch chips <NUM> and <NUM> can contain, for example, the number of ports to which they are connected. Also illustrated in <FIG> are exemplary flows of information through switch chips <NUM> and <NUM>.

Although <FIG> illustrates an <NUM> port linecard, with <NUM> ports connecting to a first stage of a network, and <NUM> ports connecting to a second stage of a network, and switch chips with <NUM> ports each, the configuration of the linecard can be modified to accommodate any number of ports. The results above can be generalized. In a general case, n-port switches in the lower stage can be replaced with 2n-port linecards. The 2n-port linecard can be made of a set of switch chips, S1 and S2, wherein each switch chip is an n-port switch. In this manner, the throughput of each Clos-topology can be improved by up to a factor of <NUM> by replacing all n-port switches in the lower stage with 2n-port linecards.

The lower stage of the Clos network can include additional sub-stages. For example, multiple additional stages can be connected with one another, in pairs, to create the lower stage of the Clos network. When the lower stage consists of additional sub-stages, the conventional switches in the sub-stages can be replaced entirely with linecards. In the case where each sub-stage has the same number of switches, by replacing the switches with linecards in, for example, the above-described manner, the throughput of the network can be increased by a factor of <NUM>R, where R is the number of sub-stages wherein a conventional switch is replaced with a linecard. In the case where each sub-stage has a different number of switches, the throughput of the network will also be increased by a factor of <NUM>R, where R is the number of sub-stages wherein a conventional switch is replaced with a linecard.

In another example, n-port switches in the lower stage can be replaced with n-port linecards, where the n-port refers to the number of ports of the linecard or switch. The n-port linecard can be made of a set of switch chips, such as switch chips S1 and S2, wherein each switch chip has n/<NUM> ports. In this manner, the throughput of each Clos-topology can be improved by a factor of <NUM> by replacing all n-port switches in a lower stage with n-port linecards.

In another example, only some of the sub-stages can be made of line cards while other stages can be made of conventional switches. By replacing the switches with linecards in the above-described manner, the throughput of the network can be increased by a factor of 2R, where R is the number of sub-stages made of line cards.

<FIG> illustrates a method <NUM> according to aspects of the technology. According to this method, a non-blocking Clos topology network can be created which can increase the non-blocking throughput of the network as compared to a network created from conventional switches. The network is any type of network, such as a data center, a LAN, or a WAN, or even a multi-stage processing chip. While various operations of the method are illustrated and described in a particular order, it should be understood that they do not have to be performed in this order. Rather, various operations arehandled in a different order or simultaneously, and operations are also added or omitted unless otherwise stated.

Method <NUM> begins at block <NUM>. In block <NUM>, an access stage can be provided. The access stage can consist of access points. Access points can be any suitable device. In block <NUM>, an upper stage can be provided. The upper stage, such as upper stage <NUM>, can be made of conventional switches. In block <NUM>, a lower stage can be provided, which is made of linecards, such as linecard <NUM>. The linecards in this stage can have as many ports as necessary based on the overall configuration of the network. This can be repeated as needed to create a lower stage that consists of multiple sub-stages. In block <NUM>, the various stages of the network can be linked by connecting the ports making up the various stages with any suitable technology. For example, Ethernet wires or other optical wires can be used to connect the ports of the switches, devices, and linecards comprising the network. In block <NUM>, the network can be further optimized based on any given parameter. Any suitable parameter can be chosen, such as the latency of the network.

In other examples, information can be obtained concerning the network, and based on the obtained information, aspects of the network can be optimized. For example, a particular path can be identified within the network. Optimization can be based on, for example, linear or non-linear optimization methods, including but not limited to Dijkstra's algorithm, machine algorithms, gradient methods, dynamic programming, integer programming, or generalized iterative scaling. Information used to optimize a parameter of the system can constitute for example, historic data about the system, or simulated demands on the system. For example, the throughput, latency, or number of connections available to a particular path within the topology is optimized. For example, only some conventional switches are replaced with linecards based on the historic data about the system to increase the throughput between start and end points within a network.

The above-described aspects of the technology are advantageous in increasing the bandwidth and throughput within a network. For example, the throughput of the network can be increased by any power of <NUM>. Another key feature of the technology is that other than replacement of conventional switches to linecards, other aspects of the network do not need to be modified to achieve this increased throughput. Thus, upgrades within existing networks can be made without modifying the manner in which a user of the network interacts or interfaces with the network.

It should be understood that the examples herein are merely illustrative. For example, it should be understood that the described system and method is implemented over any network, such as the Internet, or any private network connected through a router. For example, the network is a virtual private network operating over the Internet, a local area network, or a wide area network. Additionally, it should be understood that numerous other modifications may be made to the illustrative examples.

Claim 1:
A system (<NUM>, <NUM>) comprising:
an upper stage (<NUM>), the upper stage comprising one or more upper stage switches (<NUM>, <NUM>);
a lower stage (<NUM>) comprising one or more linecards (<NUM>), each of the one or more linecards comprising:
a plurality of bidirectional upper ports (<NUM>, <NUM>);
a plurality of bidirectional lower ports (<NUM>, <NUM>);
a unidirectional bottom-up forwarding switch (<NUM>) comprising a plurality of first ports (<NUM>, <NUM>); and
a unidirectional top-down forwarding switch (<NUM>) comprising a plurality of second ports (<NUM>, <NUM>);
an access stage (<NUM>) comprising a plurality of access points (<NUM>, <NUM>);
wherein traffic moving from the access stage to the upper stage is received at the plurality of bidirectional lower ports (<NUM>, <NUM>), sent to a first port (<NUM>, <NUM>) of the unidirectional bottom-up forwarding switch (<NUM>) and from that port of the unidirectional bottom-up forwarding switch (<NUM>) the traffic is sent to the upper stage via a bidirectional upper port (<NUM>, <NUM>), and traffic moving from the upper stage to the access stage is received at the plurality of bidirectional upper ports (<NUM>, <NUM>), sent to a second port (<NUM>, <NUM>) of the unidirectional top-down forwarding switch (<NUM>) and from that port of the unidirectional top-down forwarding switch (<NUM>) the traffic is sent to the access stage via a bidirectional lower port (<NUM>, <NUM>), wherein each of the one or more linecards (<NUM>) is configured to receive and forward traffic only between ports connecting different stages of the system.