Method and apparatus for achieving dynamic capacity and high availability in multi-stage data networks using adaptive flow-based routing

• US 7,724,670 B2
• Filed: 12/19/2008
• Issued: 05/25/2010
• Est. Priority Date: 08/05/2003
• Status: Active Grant

• Current Assignee: Dell Products LP (Dell Technologies Inc.)
• Original Assignee: Scalent Systems, Inc. (Dell Technologies Inc.)
• Inventors: Jaszewski, Gary Michael, Laursen, Andrew Leslie, Chan, Mei-Ying, Kumar, Siva V., Mathur, Saroop, Nilakantan, Chandrasekharan
• Primary Examiner(s): Ho; Duc C
• Application Number:
  US12/340,386
• Publication Number:
  US 20090097406A1
• Time in Patent Office: 522 Days
• Field of Search: None
• US Class Current: 370/235
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

Methods and systems for determining paths for flows within a multi-stage network made up of clusters of processing nodes. The flow paths may be determined without knowledge of whether or not packets of a particular flow will actually traverse specific ones of the clusters within the multi-stage network. In various implementations, the nodes of the multi-stage network may be coupled to one or more physical network switches through respective physical interfaces and a virtual connectivity grid superimposed thereon and configured through the use of a flow routing framework and system management framework to group the nodes into a number of clusters. The nodes of each cluster are configured to perform similar packet processing functions and the clusters are interconnected through virtual networks to which the nodes are communicatively coupled via virtual interfaces overlaid on top of the physical network interfaces.

Claims

1. A system comprising a virtual connectivity grid overlaid on a physical network in which nodes are coupled to one or more physical switches through respective physical interfaces, the virtual connectivity grid including virtual interfaces overlaid over the node physical interfaces so as to provide communicative coupling of the nodes to one or more virtual networks established within the virtual connectivity grid, the communicative coupling being established by virtual links arranged so as to emulate physical connections in a desired connectivity pattern, wherein the system is implemented using a plurality of stand-alone general purpose and/or special purpose computers having software stored therein as the nodes and local area network (LAN) switches that support virtual local area networks (VLANs) and jumbo frames as the one or more physical switches, the software comprises flow management software configured to cause the computers to adaptively route data flows through a multi-stage network defined by the virtual connectivity grid, and each stage of the multi-stage network comprises a cluster of similarly configured applications performing one or more network services.

2. The system of claim 1, wherein each of the nodes includes a flow management module configured to manipulate packets transmitted within the virtual connectivity grid by modifying information contained in the packets to reflect flow management decisions.

3. The system of claim 2, wherein the flow management decisions are made in a centralized fashion and on a flow-by-flow basis within the virtual connectivity grid at those of the nodes which are coupled to one or more external networks and which receive flows from the one or more external networks.

4. The system of claim 3, wherein the packets are manipulated by appending information specifying flow routing decisions.

5. The system of claim 3, wherein the packets are manipulated by replacing previously encoded information within the packet with new information specifying flow routing decisions.

6. The system of claim 3, wherein the packets are manipulated by adding network topology state information to the packets, the network topology state information reflecting the communicative coupling of the nodes.

7. The system of claim 3, wherein the packets are manipulated by adding authentication information.

8. The system of claim 3, wherein flow path decisions are mode without knowledge of which of the nodes a particular flow will actually traverse.

9. The system of claim 1, wherein at least one of the computers stores resource management and provisioning software and remaining ones of the computers store provisioning agent software that is configured to cause the remaining ones of the computer to adaptively provision a required capacity of one or more network services as driven by application demand, network performance or application response time.

10. The system of claim 9, wherein provisioning is performed via human interaction through a graphical user interface using icons that represent the nodes and the virtual interfaces and creating interconnections between them.

11. The system of claim 9, wherein provisioning is performed via human interaction through a programmatic interface using data records that provide attributes of the nodes and the virtual interfaces and specifying desired interconnections between them.

12. The system of claim 1, wherein the virtual connectivity grid is implemented using one or more blade servers, each blade of the blade servers being one of the nodes and storing software.

13. The system of claim 12, wherein the software comprises flow management software configured to cause processors of the blades to adaptively route data flows through a multi-stage network defined by the virtual connectivity grid and wherein each stage of the multi-stage network comprises a cluster of similarly configured applications performing one or more network services.

14. The system of claim 12, wherein at least one of the blades stores resource management and provisioning software and remaining ones of the blades store provisioning agent software that is configured to cause processors of the remaining ones of the blades to adaptively provision a required capacity of one or more network services as driven by application demand, network performance or application response time.

15. The system of claim 14, wherein provisioning is performed via human interaction through a graphical user interface using icons that represent the nodes and the virtual interfaces and creating interconnections between them.

16. The system of claim 14, wherein provisioning is performed via human interaction through a programmatic interface using data records that provide attributes of the nodes and the virtual interfaces and specifying desired interconnections between them.

17. The system of claim 1 wherein the virtual connectivity grid is implemented using one or more blade servers and one or more stand-alone general purpose and/or special purpose computers as the nodes and one or more local area network (LAN) switches that support virtual local area networks (VLANs) and jumbo frames, external to the blade servers, as the one or more physical switches.

18. The system of claim 17, wherein each of the blades and the computers stores flow management software configured to cause processors of the blades and the computers to adaptively route data flows through a multi-stage network defined by the virtual connectivity grid and wherein each stage of the multi-stage network comprises a cluster of similarly configured applications performing one or more network services.

19. The system of claim 17, wherein at least one of the computers or the blades stores resource management and provisioning software and remaining ones of the computers and/or the blades store provisioning agent software that is configured to cause the remaining ones of the computers and/or processors of the blades to adaptively provision a required capacity of one or more network services as driven by application demand, network performance or application response time.

20. The system of claim 17, wherein provisioning is performed via human interaction through a graphical user interface using icons that represent the nodes and the virtual interfaces creating interconnections between them.

21. The system of claim 17, wherein provisioning is performed via human interaction through a programmatic interface using data records that provide attributes of the nodes and the virtual interfaces and specifying desired interconnections between them.

22. A method, comprising establishing a virtual connectivity grid configured to permit arbitrary interconnections among a first number of computer systems within a computer network, each of the computer systems being communicatively coupled to respective ports of one or more physical network switching devices, through a second number of virtual links that emulate physical network connectivity mechanisms as a result of configurations of one or more virtual networks (VLANs) overlaid on ports of the physical network switching devices wherein at least one of the virtual links emulates, in a fully switched environment, a switch that provides multi-access, broadcast capable connectivity to a plurality of the computer systems while providing unicast traffic isolation.

23. The method of claim 22, wherein at least one of the virtual links emulates, in a fully switched environment, a cable that provides point-to-point connectivity between two of the computer systems.

24. The method of claim 23, wherein the point-to-point connectivity is unidirectional.

25. The method of claim 23, wherein the point-to-point connectivity is bidirectional.

26. The method of claim 22, wherein at least one of the virtual links emulates, in a fully switched environment, a cable that provides point-to-multipoint connectivity between a root one of the computer systems and a plurality of leaf ones of the computer systems.

27. The method of claim 26, wherein the point-to-multipoint connectivity is unidirectional.

28. The method of claim 27, wherein the point-to-multipoint connectivity is bidirectional.

29. The method of claim 22, wherein at least one of the virtual links emulates, in a fully switched environment, a hub that provides multi-access, broadcast capable connectivity to a plurality of the computer systems, each operating in either a promiscuous or non-promiscuous mode.

30. The method of claim 22, wherein at least one of the virtual links emulates a transparently bridged connection between a network external to the virtual connectivity grid and a plurality of the computer systems, the bridged connection providing data patch transparency for interactions between devices within the network external to the virtual connectivity grid and the plurality of the computer systems.

31. The method of claim 22, wherein prior to transmission across at least one of the virtual links a packet is modified so as to have its original header information contained therein appended to an end of the packet.

32. The method of claim 31, wherein prior to transmission across the at least one of the virtual links the packet is further modified so as to have new header information substituted for the original header information.

33. The method of claim 32, wherein the new header information includes flow path decision information for the packet within the virtual connectivity grid.

34. The method of claim 31, wherein authentication information is appended to the packet, the authentication information serving to identify which of the computer systems is transmitting the packet.

35. The method of claim 22, wherein upon reception at one of the computer systems a packet has its original header information restored with original header information for the packet that is appended to an end of the packet.