HK1227195B - Method to route packets in a distributed direct interconnect network - Google Patents

Description

Method for routing packets in a distributed direct interconnection network

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is related to PCT patent application number PCT/CA2014/000652, filed on August 29, 2014, entitled “Method and Apparatus to Manage the Direct Interconnect Switch Wiring and Growth in Computer Networks,” the disclosure of which is incorporated herein by reference.

Technical Field

The present invention relates to computer networks for interconnecting servers in data centers and cloud data centers. In particular, the present invention relates to methods for routing packets in direct interconnect networks implemented on torus or high-radix topologies such as "dragonfly" wiring structures.

Background Art

The term data center (DC) generally refers to a facility used to house large computer systems (often contained in racks housing the equipment) and their associated components, all interconnected by extensive structured cabling. Cloud data center (CDC) is a term used to refer to large, often redundant facilities that similarly store the data of an entity.

A network switch is a computer networking device that links network devices for communication/processing purposes. In other words, a switch is a telecommunications device capable of receiving messages from any device connected to it and sending them to a specific device to which the message will be relayed. A network switch is also commonly referred to as a multi-port bridge that processes and routes data. Here, "port" refers to the interface (the outlet for the cable or plug) between the switch and the computer/server/CPU to which it is attached.

Today, DCs and CDCs typically use a set of Layer 2 switches to implement data center networking. Layer 2 switches process and route data at Layer 2 (the Data Link Layer), which is the protocol layer that transmits data between nodes (e.g., servers) on the same local area network or between adjacent nodes in a wide area network. However, a key issue to be addressed is how to build a high-capacity computer network that can carry very large aggregate bandwidth (thousands of terabytes) with a very large number of ports (thousands), requires minimal structure and space (i.e., minimizes the need for large rooms to house a large number of cabinets with card racks), is easily scalable, and can help minimize power consumption.

Conventional network topology implementations are based on completely independent switches organized in a hierarchical tree structure, as shown in Figure 1 . Core switch 2 is a very high-speed, low-port-count switch with very large switching capacity. Layer 2 is implemented using aggregation switches 4 (medium-capacity switches with a large number of ports), while Layer 3 is implemented using lower-speed, large-port-count (e.g., 40/48), low-capacity edge switches 6. Edge switches are typically Layer 2, while aggregation ports are Layer 2 and/or Layer 3, and core switches are typically Layer 3. In the example provided, this implementation provides any server 8 to any server connectivity over a maximum of six hops (three hops up to core switch 2 and three hops down to destination server 8). Such hierarchical structures are also typically replicated for redundancy and reliability purposes. For example, referring to Figure 1 , without replication, if the rightmost edge switch 6 fails, there would be no connectivity to the rightmost server 8. At the very least, core switch 2 is replicated, as a failure of core switch 2 would result in a total data center connectivity failure. For obvious reasons, this approach has significant limitations in addressing the challenges of future CDCs. For example, because each switch is completely self-contained, this adds complexity, significant floor space utilization, complex cabling that is prone to human error, and manual switch configuration/provisioning, as well as increased energy costs.

However, many attempts have been made to improve switching scalability, reliability, capacity, and latency in data centers. For example, efforts have been made to implement more complex switching solutions by using a unified control plane (e.g., the QFabic system switches from Juniper Networks; see, for example, http://www.juniper.net/us/en/productservices/switching/qfabric-system/), but such systems still use and maintain a traditional hierarchical architecture. Furthermore, given the exponential increase in the number of system users and the data to be stored, accessed, and processed, processing power has become the most important factor when determining the performance requirements of computer network systems. While server performance has continued to improve, a single server is no longer powerful enough to meet the needs. This is why the use of parallel processing has become crucial. As a result, in many cases, up to 80% of traffic flows, what was once a predominantly North American traffic flow has now become primarily an East-West traffic flow. Despite this shift in traffic flows, network architecture has not yet evolved to be optimal for this model. Therefore, it is still the topology of the communication network (which interconnects the compute nodes (servers)) that determines the speed of interaction between CPUs during parallel processing communications.

This need for increased east-west business communications has led to the creation of newer, flatter network architectures (e.g., ring-shaped/ring networks). A ring interconnect system is a network topology for connecting network nodes (servers) in a meshed manner in a parallel computer system. A ring topology can have nodes arranged in 2, 3, or more (N) dimensions that can be virtualized as an array, wherein processors/servers are connected to their nearest neighbor processors/servers, and wherein processors/servers on opposite edges of the array are connected. In this way, each node has 2N connections in an N-dimensional ring configuration (Figure 2 provides an example of a 3-D ring interconnect). Because each node in the ring topology is connected to an adjacent node via a short cable line, there is low network latency during parallel processing. In fact, the ring topology provides access to any node (server) with a minimum number of hops. For example, a four-dimensional ring implementing a 3x 3x 3x4 structure (108 nodes) requires an average of 2.5 hops to provide connectivity from any point to any point. Figure 4 provides an example of a 6x 6 2-D ring, showing the minimum number of hops required to turn from a corner node 1.6 to all other 35 nodes. As shown, the number of hops required to reach any destination from node 1.6 can be plotted as a bell curve with a peak at 3 hops (10 nodes) and tails typically at 5 hops (4 nodes) and 1 hop (4 nodes), respectively.

Unfortunately, large ring network embodiments have not yet been practical for commercial deployment of DC or CDC because large embodiments may take months to build, cabling may be complex (2N connections for each node), and they may be costly and cumbersome to modify when expansion is necessary. However, in situations where the need for processing power has outweighed commercial disadvantages, the implementation of ring topologies in supercomputers has been very successful. In this regard, IBM's Blue Gene supercomputer provides an example of a 3-D ring interconnect network, where 64 cabinets house 65,536 nodes (131,072 CPUs) to provide petaflops of processing power (see illustrated FIG3 ), while Fuji's PRIMEHPC FX10 supercomputer system is an example of a 6-D ring interconnect housed in 1,024 racks comprising 98,304 nodes. Although the above examples deal with ring topologies, they are equally applicable to other flat network topologies.

The present invention more specifically deals with the important problem of data packet traversal and routing from node to node in a ring or high-radix network structure. In this regard, it is the routing that determines the actual path that a packet of data takes in a network from a source to a destination. For the purposes of this article, latency refers to the time it takes for a packet to reach its destination in a network, and is typically measured from when the header arrives at the input of the source node to when it arrives at the input of the destination node. Hop count refers to the number of links or nodes traversed (passed through) between the source and the destination, and represents an approximate value for determining latency. Throughput is the rate of data accepted by each input port/node of the network measured in bits/second (bits/sec).

A useful goal when routing is to distribute traffic evenly among nodes (load balancing) to avoid the development of hotspots (areas of paths or nodes where usage/demand exceeds a desired or acceptable threshold) and to minimize contention (when two or more nodes attempt to send messages or packets on the same wire or path at the same time), thereby improving network latency and throughput. The route chosen for this purpose affects the number of hops from node to node and, if routing is not optimized, can potentially even affect energy consumption.

The topology of network operation also undoubtedly affects delay, because topology affects the average minimum hop count and distance between nodes. For example, in a ring, there are not only several paths that a packet can take in order to reach a destination (that is, in a ring with "path diversity"), but also multiple minimum length paths between any source and destination pair. As an example, FIG5 shows an example of three minimum routes (3 hops) that a packet can take in order to turn from node S 11 to node D 12 in a 2-D ring grid, while also showing a longer fourth route of 5 hops. The path calculation performed by routing is essentially performed only based on topology - source routing is dynamically based on packet source-destination pairs on a hop-by-hop basis.

Routing methodologies that exploit path diversity offer better fault tolerance and load balancing within the network. However, routing methodologies do not always achieve this goal and can generally be categorized into three categories: deterministic, agnostic, and adaptive. Deterministic routing refers to the fact that the route between a given pair of nodes is determined in advance, regardless of the current state of the network (i.e., regardless of network traffic). Dimension-ordered routing (DOR) is an example of deterministic routing, in which all messages from node A to node B will always traverse the same path. Specifically, messages traverse dimension by dimension (X-Y routing), reaching a ordinate that matches their destination in one dimension before switching to the next. As an example, Figure 6 can be used to illustrate DOR, in which a packet first travels along the first dimension (X) as far as required from nodes 1 to 5 to 9, followed by traveling along the second dimension (Y) to destination node 10. While such routing is generally easy to implement and deadlock-free (deadlock is a situation where an infinite loop exists along the path from source to destination), it does not exploit path diversity and therefore suffers from poor load balancing.

"Oblivious" routing algorithms are those in which routing decisions are made randomly, regardless of the current state of the network (deterministic routing is a subset of oblivious routing). While this means that oblivious routing may be simple to implement, it may not be adaptable to traffic and network conditions. An example of a well-known oblivious routing approach is the Valiant algorithm (known to those skilled in the art). In this approach, a packet sent from node A to node B is first sent from A to a randomly selected intermediate node X (one hop), and then from X to B. Referring again to Figure 6, the Valiant algorithm can randomly select node 2 as an intermediate node from source node 1 to destination node 10, meaning that the path 1-2-3-7-11-10, for example, can be used for routing purposes. This generally randomizes any traffic pattern, and because all patterns appear to be uniformly random, the network load is very balanced. In fact, the Valiant algorithm has been recognized as being able to generally balance the load for any traffic pattern on almost any topology. However, one problem is that valiant routing is often non-minimal (a minimal route is a path requiring the minimum number of hops between a source and a destination), which often results in a significant increase in hop count, which further increases network latency and can potentially increase energy consumption. However, there are exceptions, such as in networks with minimal congestion. Non-minimal routing can significantly increase latency and potentially increase power consumption as additional nodes are traversed; on the other hand, in networks experiencing congestion, non-minimal routing can actually help avoid nodes or hotspots and thereby actually result in lower latency.

If minimal routing is desired or necessary, the Valiant algorithm can be modified to limit its random decisions to minimal routing/shortest paths by specifying that intermediate nodes must be within a minimal quadrant. As an example, referring to Figure 6, the minimal quadrant for node 1 (with a destination of node 10) would contain nodes 2, 5, and 0, and would result in a common hop count of 3.

The Valiant algorithm provides some level of randomization of path selection that will reduce the likelihood of hotspot development. However, there is another difficulty that affects these efficiencies - Valiant routing is only deadlock-free when used in conjunction with DOR routing, which by itself fails in terms of load balancing and hotspot avoidance.

Adaptive routing algorithms are those in which routing decisions are based on the state of the network or network traffic. They typically involve flow control mechanisms, and in this regard, buffer occupancy is often used. Adaptive routing can use global node information (which is cost-effective), or it can use information from only local nodes, including, for example, queue occupancy for measuring network congestion. The problem with using information from local nodes alone is that this can sometimes lead to suboptimal choices. Adaptive routing can also be limited to minimum paths, or it can be fully adaptive (i.e., without restrictions on taking the shortest path) by using non-minimum paths with the potential for livelock (i.e., a situation similar to deadlock where packets do not reach their destination; often the result of a lack of resources). This can sometimes be overcome by allowing a certain number of misroutes per packet and by giving higher priority to packets that have been misrouted many times. Another problem with adaptive routing is that it can cause problems with preserving the order of data packets - packets need to arrive at their destination in the same order, or else you need to implement a packet reordering mechanism.

Finally, it is important to mention that routing can be implemented through a source table or a local table. With a source table, the entire route is specified at the source and can be embedded in the packet header. This minimizes latency because the route does not have to be looked up at each node or routed hop by hop. The source table can also specify multiple routes per destination to manage failures and improve load balancing when routes are randomly selected (i.e., independent routes). With a local node table, on the other hand, a smaller routing table is used. However, the next step a packet will take is determined at each node, and this increases per-hop latency.

The present invention seeks to overcome the deficiencies in the prior art and to improve upon known methods of routing packets in ring or high radix network topologies.

Summary of the Invention

In one aspect, the present invention provides a novel method for routing data packets over a ring mesh or high radix topology to provide low latency, increased throughput, and avoid hot spots and deadlocks.

In yet another aspect, the present invention provides a method for achieving traffic decorrelation (randomization), increased efficiency in bandwidth allocation, load balancing and traffic engineering in a ring mesh or high radix structure.

In one embodiment, the present invention provides a computer-implemented method for routing packets from a source node to a destination node in a directly interconnected network, the method comprising the steps of: discovering all nodes in a network topology and all output ports on each node; including the nodes and output ports discovered in the network topology in a topology database to allow the nodes and ports to be included in a shortest path routing calculation; computing the shortest path from each output port on each node to every other node in the network topology based on those nodes and output ports contained in the topology database; generating a source routing database at each node containing the shortest paths from each output port on each node to every other node in the network topology ... an output port to all other nodes in the network topology; receiving packets at the source node; sending the received packets to the output port of the source node in a round-robin or weighted round-robin manner, whereby each of the received packets is thereafter segmented into flits at the output port of the source node and distributed along a plurality of shortest paths from the output port on the source node to the destination node, such that the packets are thereby distributed along a plurality of alternative routes in the network topology; and reassembling and reordering the packets at the destination node so that the packets conform to their original form and order.

In another embodiment, the present invention provides a method of routing packets in which flits are forwarded to a destination node using wormhole switching.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the present invention will now be described by way of example with reference to the accompanying drawings, in which:

FIG1 is a high-level diagram of a conventional data center network embodiment;

FIG2 is a diagram of a 3-dimensional ring interconnect with 8 nodes;

FIG3 is a diagram showing the hierarchy of an IBM BlueGene processing unit employing a ring architecture;

Figure 4 is a high-level diagram of 36 nodes in a 6 x 6 2-D folded ring showing the minimum number of hops required to reach any of the 35 nodes starting from a corner node (1.6);

FIG5 is a diagram of a 4 x 4 2-D ring embodiment showing several routes starting from node S to node D on each port (x+, x-, y+, y-) of node S;

FIG6 is a diagram of a simple network topology used to help illustrate how various routing algorithms can route packets from node to node;

7 is a high-level diagram of a high-speed network interface card with all ports of a system according to the present invention;

FIG8 is a high-level diagram of a host network interface (HNI) card showing key functional blocks of a system according to the present invention;

FIG9 is a high-level view of the packet segmentation required to achieve packet delivery across a ring mesh;

FIG10 shows a diagram of the routes and hop counts starting from each port on node S (2.4) to each port on node D (5.2) in a 36-node 2-D ring structure;

FIG11 shows a high-level diagram of presentation software components TD, SR, WS, FC according to the present invention;

FIG12 shows a flow chart of a process of packet segmentation according to the present invention;

Figure 13 shows the pseudo code for implementing flit generation through group segmentation;

FIG14 shows a flow chart of the processing steps for preparing source routing from each port according to the present invention;

FIG15 shows a pseudo code for implementing path calculation according to the present invention;

FIG16 shows a format of a source routing table generated by path calculation according to the present invention;

FIG17 shows a flow chart of the process of transmitting a "flick" on each port according to the present invention;

FIG18 shows a wormhole exchange process for transmitting "flicks" on each port according to the present invention;

FIG19 shows pseudo code for implementing a flitter transfer as described in the flowchart of FIG17 in accordance with the present invention;

FIG20 shows a flow chart for discovering nodes or links that trigger a topology discovery process for topology update;

FIG21 shows a flowchart for describing a topology database update;

FIG22 is a flowchart showing a process of node and/or link failure detection and recovery and a process of topology update; and

FIG23 shows pseudo code for implementing link and/or node failure detection according to the present invention;

DETAILED DESCRIPTION

The present invention utilizes a ring mesh or high-radix cabling to implement a direct interconnect switch for data center applications. Specifically, the present invention is particularly useful with the ring system described in related PCT patent application No. PCT/CA2014/000652, filed on August 29, 2014, entitled "Method and Apparatus to Manage the Direct Interconnect Switch Wiring and Growth in Computer Networks," the disclosure of which is incorporated herein by reference. Such an architecture can provide high-performance network interconnects with tens of thousands of servers within a single switch domain.

The software that controls the switch follows the software-defined networking model. The switch control plane (switch OS) preferably runs on a separate server, but interacts closely with the distributed processing running on each PCIe card. Referring to Figure 11, key software components include topology discovery (TD), packet routing (SR) across the topology, wormhole switching (WS), flow control (FC) mechanisms, and switch state monitoring and switch management. The TD component is responsible for essentially discovering the presence (or absence) of nodes in the ring mesh (and thereby allowing possible paths to be updated based on node presence); the SR component is responsible for source route calculation (all paths available from each port of the source node to any destination node); the WS component is responsible for micro-slice manipulation across the ring based on the path vector, which is included in the micro-slice header with minimum latency (through model at each node); the FC component is responsible for ring link utilization and controlling messages to the source in order to regulate traffic through an input queuing mechanism; the switch state monitoring component is responsible for traffic balancing, traffic rerouting under failure conditions, and support for switch growth; and the switch management component is responsible for maintaining a complete image of the switch, including all interconnected servers, all interconnected I/O links to the outside world, and connectivity status.

The present invention is primarily directed to the novel topology discovery (TD component) and routing protocol (SR component) of the present invention - particularly useful for implementing key functionality on the novel switch architecture disclosed in PCT Patent Application No. PCT/CA2014/000652. While conventional implementations of routing data packets through a ring structure make the implicit assumption that traffic is randomly distributed across destination nodes, practical embodiments have demonstrated switch failures in the presence of single source/single destination continuous packet flows at maximum capacity due to the development of hotspots that propagate across the ring and have the ability to completely disable the ability to transmit packets across the ring mesh. The present invention therefore more specifically refers to routing optimization and implementation for directly interconnected network topologies such as rings and high-radix networks in order to address performance issues and hotspot development for any type of traffic, whether large flows from any source to any destination (highly correlated) or traffic to randomly distributed destinations (typical of Internet traffic). In contrast to known methods of routing packets in a ring as previously described above, the present invention describes a method of discovering and updating all nodes in a topology, and a method of routing packets to each destination node, wherein the shortest path is calculated at each node on each output port (e.g., x+, x-, y+, y-, z+, z-, w+, and w-), and whereby packets are distributed along the paths from each output port in a round-robin or weighted round-robin manner (i.e., facilitating multiple alternative paths) to increase bandwidth and traffic distribution and thereby avoid hot spots. A flow control (FC) mechanism is used to change the output port selection for packet routing from a simple round-robin sequential selection of source node output ports (i.e., port x+ first, next x-, then y+, y-, z+, z-, w+, and w-) to a weighted round-robin in which links identified as busy by FC are skipped, or the traffic on those ports is reduced to a low percentage (e.g., 10%) of the maximum link capacity.

Data packet reordering is implemented at the node destination. Such an approach can particularly leverage the novel approach to node (server) discovery discussed in PCT Patent Application No. PCT/CA2014/000652 and further discussed herein. The present invention thus addresses the problem of packet routing optimization for directly interconnected network topologies such as ring or high-radix networks, in order to address performance issues and hotspot development for any type of traffic, whether it is large flows from any source to any destination (highly correlated) or traffic to randomly distributed destinations (typical Internet traffic).

7 shows a high-level block diagram of a high-speed network interface card 10 having all of the following ports: I/O ports 13 (N-S interface) for accessing the outside world, 4D ring interconnect ports 14, PCIe ports 15 for accessing computer servers, and controls 19. Those skilled in the art will appreciate that the present invention can work with HNI cards having fewer or more ports and in association with other ring or high-radix topologies, such as, for example, a "dragonfly."

FIG8 illustrates a high-level block diagram of an HNI card 10 of a system according to the present invention using key functional blocks, including a processor 31 with RAM 37 and ROM 38, a switch block 32, a physical interface device 36, a ring interconnect port 14, I/O ports 13, and a PCIe port 15. The physical implementation of this embodiment is based on a multi-core processor with attached memory and a PHY device for implementing the ring interconnect. The switching function is implemented in software using the processor's hardware acceleration capabilities to support multiple queue manipulation. Those skilled in the art will appreciate that the present invention will also work with different physical implementations (i.e., when the switching function is accelerated using an FPGA or ASIC), or that the processor need not reside on the same card as the card used for the switching function.

FIG10 shows a simple 2D ring wiring diagram for use in illustrating packet routing according to the present invention. As shown, the structure is a folded 2D ring in which the length of each connection is equal throughout. Each node in this diagram represents a server interconnected via a PCIe switch card (as described above) housed in the server. The diagram shows the shortest maximally disjoint paths (with no common links or nodes) from a port of a source node S (2.4) to a destination node D (5.2) in each dimension (x+, x-, y+, y-), as calculated at the source node S. In this regard, FIG10 shows three calculated paths and routing vectors as having a minimum hop count of 5 hops (from (S)2.4: (x+, x+, x+, y-, y-); from (S)2.4: (y-, y-, x+, x+, x+); and from (S)2.4: (x-, x-, y-, y-, x-), whereas another path is calculated as having a non-minimum hop count of 7 hops (from (S)2.4: (y+, y+, y+, x+, x+, x+, y+)). Assuming that there is a large amount of traffic between the source node S and the D node, the packets/micro-slices will be sent to the destination node in a round-robin manner or a weighted round-robin manner along the path from each output port of the source node S on the shortest path starting from each output port of the source node S to the node D, thereby using multiple paths to increase bandwidth on the one hand. And distribute the traffic to avoid hotspot development (weighted round-robin selection of output ports at the source node will increase the number of packets along a particular path). A second alternative route can also be calculated and stored at each node, whereby, in addition to the first hop, the route provides an alternative, separate path to help overcome network congestion and hotspots when necessary in the event of a link or node failure. This method distributes traffic across a ring or high cardinality network for load balancing purposes, but can introduce packet reordering. For example, because the path starting on y+ (Figure 10) is 2 hops longer than the minimum path (5 hops), all packets sent on this path will arrive with additional delays that may create packet reordering problems. According to the present invention, the packets must therefore be reordered at the destination node. This is within the skill of those skilled in the art.

Referring to Figure 9, which shows a high-level view of packet segmentation, it is important to note that packets traversing a directly interconnected ring or high cardinality are segmented into smaller sized packets (microslices) during routing. Packet segmentation is required across the ring mesh in order to avoid "line end blocking" (a common situation in packet networks that use common resources (links and buffers)). The size of the microslice is determined by the type of traffic in order to minimize overhead, and actual values range between 64 bytes and 512 bytes. It is important to note that the present invention is capable of handling Ethernet packets, Infiniband packets, PCIe streams, or NVMe transactions, etc. The microslices across the ring structure carry traffic transparently. The external interface I/O port 13 is specific to the type of traffic and terminates the user traffic, thereby transparently transmitting the data across the ring to the destination PCIe port 15 via the "microslice". It is important to note that the present invention is capable of handling Ethernet packets that cross the ring (via Ethernet microslices). The key advantage of this article is the variable size of the microslices, because the microslices of Ethernet packets have a packet demarcation mechanism. Therefore, the flit size is variable from 64 bytes (minimum Ethernet packet size) to 512 bytes (payload and header). If the packet is larger than 512 bytes, the system will segment the original packet into 512-byte fragments: head flit, body flit, and tail flit.

Figure 12 provides a flow chart illustrating a method for packet segmentation. Upon receiving a new packet from the host (i.e., PCIe interface) (step 402), the HNI processor extracts the header to allow the processor to analyze the packet's destination (step 404) and routing path. At this stage, the packet enters a segmentation loop. A byte counter is initialized (step 412) and the End of Packet (EOP) analyzer (step 405) detects the EOP, and if the counter is less than or equal to 476 bytes (i.e., the payload is less than or equal to 476 bytes), the packet is sent to the Flit Generator (step 407), the Header Generator (step 408), and the Priority Decision Block (step 409). The flit is then inserted into the assigned egress queue (step 410) for transmission to the next hop on the ring mesh, and we note whether a new packet has been received (402). The byte counter is incremented after each individual flit (step 411), the packet segment is sent to the flit generator (step 407) and the process follows the steps described above until the last flit in the packet arrives and is sent. As a key observation, a flit on a ring link is preferably 512 bytes (476 bytes of payload and 36 bytes of header) followed by 8 "idle" bytes. If the packet is shorter than 476 bytes, then the flit (usually the tail flit) will have less than 512 bytes and the "idle" bytes will be used to complete the packet demarcation. Figure 13 provides pseudo code to implement flit generation through packet segmentation.

At the destination, the flits are assembled into packets by stripping off the ring header and using a "byte count" for the offset of the flits in the original packet. Those skilled in the art will know that a per-source packet queue is implemented for the destination node, creating an ordered list of packet segments, and releasing the packets once they are fully assembled in the original order. Figure 14 shows a flow chart presenting a route calculation according to the present invention. The present invention also provides pseudocode at Figure 15 for calculating all paths (source routes) from the source node to any destination node that are maximally disjoint (without common links and nodes) on each output port of the source node. As soon as an update is detected (i.e., whenever a node has been added/detected or there is a critical problem/failure associated with it), the topology update function 412 (which finds active servers/nodes and their active ports) will start the route/path calculation (414). As described in step 419 (finding the first destination node in the topology list) followed by steps 420 and 421 (searching all destination nodes in the topology list), the shortest path will be calculated using the Dijkstra algorithm between the current node from the topology and each destination node (step 415) according to the present invention. In step 422, all path costs affected by step 417 are reset to their initial values. The calculated shortest path from the source to the destination will be stored in the source routing database and will be removed from the further shortest path calculations (in order to provide disjoint paths) (417) by increasing the costs on all links belonging to the stored path to infinity - this will have the practical effect of removing nodes and links from the topology database to force them to no longer be used for disjoint path selection purposes. This process continues until all output ports will be used and all possible paths between the source node and the destination node are stored in the database. The results are then summarized in the output routing table (418) as a routing vector for each node, where routing will start with the shortest path first. The shortest path calculation itself can be implemented using Dijkstra's algorithm (a well-known method used in routing protocol implementations). What is particularly novel in this invention is that the shortest path is determined at each output port and used accordingly.

Figure 16 presents the format of the routing output table. Each route has a list/vector of attached numbers representing the number of hops for a particular path and the output ports to be selected on each hop. In particular, Figure 16 presents an example snapshot of the output table for a route in a 4-D ring (8x8x8x8) with 8 ports (x+, x-, y+, y-, z+, z-, w+, and w-) from source node number 1000 to destination node 0 (the use of node 1000 and node 0 is for illustrative purposes only). It should be noted that the first output selection in the group of 8 routes (i.e., x+, y+, z+, w+, x-, y-, z-, and w-) in the first group of 8 routes corresponds, for example, to each output port of the source node. The 8 paths are completely disjoint and have different lengths: 5 hops, 7 hops, or 9 hops. The most important feature is the path distribution across the ring that enables traffic distribution and predictable performance. The second group of 8 paths in Figure 16 represents a second alternative for the routing path. This method can calculate many alternative routes, but the distance (number of hops) will become increasingly larger. Due to practical reasons, this method can typically only store the first options of 8 different paths as needed.

FIG. 17 shows a flow chart representing the steps used in packet switching according to the present invention.

As new packets are pushed into the output queues, the packet forwarding state machine initiates forwarding across the ring. In this regard, the output port "k" in question (ports 1 through 8, i.e., the output ports discussed above: x+, y+, z+, w+, x-, y-, z-, and w-) is used to forward flits following a wormhole model (as shown in FIG18 ): the head flits and subsequent flits, incremented (body flits), are forwarded along the same path from port k until the end of the packet (tail flits) is reached as shown in FIG17 . Once the end of the packet is reached, a counter k is incremented to indicate the next output port and the next packet with the next packet identifier (designated as the next in-order packet) is forwarded on a flite-by-flit basis across the ring using this wormhole switching model. Once the end of the packet is detected, the port number is incremented again (i.e., k=k+1) and the next packet is forwarded, and so on. This embodiment distributes packets originating from a node across all of the node's output ports 14 in a round-robin model in order to decorrelate long data flows with specific destinations and avoid the development of "hot spots" in the ring mesh. Those skilled in the art will appreciate that this distribution method can be modified as needed to improve performance for different types of traffic distribution, as necessary. For example, one can replace the round-robin method with a weighted round-robin method or any other user-defined method. The method of the present invention has been found to perform better than Valiant's independent distribution and is very consistent and predictable in terms of results. This is very significant from a network performance perspective. FIG19 shows pseudo code for implementing the flits delivery as described and shown in the flow chart at FIG17 .

Figure 20 shows a flowchart of a method for presenting topology discovery according to the present invention. As noted above, the topology discovery component (TD) is important for essentially discovering the presence (or absence) of nodes (and node ports) in a ring mesh, which can then be used in the above route distribution. In this regard, TD allows the novel network of the present invention, as particularly disclosed in PCT patent application number PCT/CA2014/000652, to be scaled in a simplified and efficient manner. TD is based on the "Hello" protocol and the database exchange protocol. In particular, a "Hello" message is sent and received on each node and each port. Once the message is received as a "Hello" and the node ID in the "Hello" packet is verified by the management framework, the local node information is updated to indicate the availability of new links to the neighbors. The collection of node information is maintained in a neighbor database on each node and synchronized with the neighbors via the database exchange protocol. Each node sends its changes to the neighbor database to the neighbor node, thereby gradually propagating the entire topology. After a specific timeout, if a change to the neighbor database occurs, a function call is generated for path calculation. The "Hello" message exchange from neighbor to neighbor continues forever at defined time intervals in order to detect changes in the topology.

FIG. 21 shows a flow chart presenting DB exchange updates for topology discovery according to the present invention.

This essentially involves the TD component being responsible for maintaining a complete image of the switch in each node, including all interconnected servers and input/output links and connectivity status.

FIG22 provides a flow chart showing how the system of the present invention discovers node/link failure detection and the process of rerouting to avoid the node that has failed. As a link failure is detected 602, the pass-through block is programmed so that the business going to the link that has failed is rerouted to the CPU 603. The business source is notified to send business 604 to avoid the link that has failed. This triggers a topology update event 605.

As link recovery is detected 606 , the pass-through block is programmed so that traffic destined for the CPU due to the failed link is rerouted back to the same link 607 .

The traffic source is informed to send traffic in the same manner as before the link failure 608. This triggers a topology update event 609. A similar process will occur in the case of a link cut. Figure 23 provides pseudo code for link/node failure detection and recovery.

One embodiment of the present invention is a method for new node insertion. In order to insert a node, the wiring interconnecting the existing nodes is interrupted (link cut). As the ring wiring interruption is detected 602, the service rerouting API is called 604. The link cost is set to infinity and the topology is updated (the shortest (lower cost) path is calculated for all switch nodes). This defines the route that will be used to control the flow of packets to reach any destination. The new node insertion triggers neighbor discovery. The management software checks the new node ID and compares it with the provided database. If the node is valid, the software starts the process of topology update and route calculation. The management database will be updated with the new node and the node status will be set to active.

While specific embodiments of the present invention have been described, it will be apparent to those skilled in the art that changes and modifications of the embodiments may be made within the scope of the following claims.

Claims (2)

1. A computer-implemented method for routing packets from a source node to a destination node in a directly interconnected network, the method comprising the following steps: Discover all nodes and all output ports on each node in the network topology; The nodes and output ports found in the network topology are included in the topology database so that the nodes and ports can be included in the shortest path route calculation; The shortest path from each output port on each node to each other node in the network topology is calculated based on the nodes and output ports contained in the topology database. A source routing database is generated on each node, which contains the shortest paths from each output port on each node to all other nodes in the network topology; Receive packets at the source node; The received packets are sent to the output port of the source node in a round-robin or weighted round-robin manner, whereby each of the received packets is subsequently segmented into smaller packets at the output port of the source node and distributed along multiple shortest paths from the output port of the source node to the destination node, such that the packets are distributed along multiple alternative routes in the network topology; and At the destination node, the packets are reorganized and reordered so that they conform to their original form and order. 2. The computer-implemented method of claim 1, wherein the smaller packets are forwarded to the destination node using wormhole switching.