Dynamic routing for performance partitioning in a data processing network

• US 6,195,703 B1
• Filed: 06/24/1998
• Issued: 02/27/2001
• Est. Priority Date: 06/24/1998
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Blumenau, Steven M., Raz, Yoav
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US09/103,996
• Time in Patent Office: 979 Days
• Field of Search: 709/238, 709/231, 709/229, 709/226, 709/219, 709/105, 709/104, 714/4, 714/769, 714/770, 711/111, 711/113, 711/114, 711/150, 710/73, 370/352
• US Class Current: 709/238
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A data network includes a switch that links a number of host processors to shared resources such as network ports of a cached storage subsystem. The switch routes resource requests from its inputs to selected ones of its outputs in accordance with programmed routing information. The routing information is changed dynamically based on measured loading characteristics of requests from the switch inputs or the respective hosts, in order to reduce the probability of blocked paths. In a specific example, respective subsets of output ports of the switch are assigned to each respective input port, the loading of each input port of the switch is measured, and the respective subset of output ports assigned to each input port are repetitively changed, and the respective subset of an input port is changed in response to blocking of the output ports assigned to the input port. A respective subset is selected based on the measured loading characteristics and a priority assigned to the input port, in order to balance loading on the output ports. In another specific example, a respective subset of the output ports is assigned to each host, based on host loading characteristics and a respective priority assigned to each host.

Claims

1. A method of routing resource requests through a switch in a data processing network, said method comprising:

a) storing, in a memory, routing information defining respective outputs of the switch to which resource requests received at inputs of the switch should be routed;

b) in response to resource requests being received at the inputs of the switch, routing each resource request received at each input of the switch to an output of the switch by accessing the routing information in the memory to select a respective output of the switch to which said each resource request should be routed, and routing said each resource request to the selected output of the switch to which said each resource request should be routed; and

c) changing the routing information stored in the memory based on loading characteristics of the resource requests received at the switch inputs in order to balance loading of the resource requests upon the outputs of the switch.

2. The method as claimed in claim 1, wherein the routing information stored in the memory defines for each input of the switch a respective subset of outputs of the switch to which resource requests received at said each input of the switch should be routed, and the respective output of the switch to which said each resource request should be routed is selected by selecting one of the outputs in the respective subset of outputs of the switch for the input of the switch from which said each resource request is received.

3. The method as claimed in claim 2, wherein the routing information stored in the memory is based on respective priorities assigned to the switch inputs by including different numbers of the switch outputs in the respective subsets.

4. The method as claimed in claim 1, wherein the resource requests received at each of a plurality of the inputs of the switch originate from a plurality of sources, the routing information stored in the memory defines for each source a respective subset of outputs of the switch to which resource requests from said each source should be routed, and the respective output of the switch to which said each resource request should be routed is selected by selecting one of the outputs in the respective subset of outputs of the switch to which resource requests from said each source should be routed.

5. The method as claimed in claim 1, wherein the routing information stored in the memory is based on respective priorities assigned to the sources by including different numbers of the switch outputs in the respective subsets.

6. The method as claimed in claim 1, wherein the routing information stored in the memory defines a plurality of subsets of outputs of the switch, and wherein the respective output of the switch to which said each resource request should be routed is selected by selecting one of the subsets, and then selecting the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the selected subset.

7. The method as claimed in claim 6, wherein the respective output of the switch to which said each resource request should be routed is a not-busy switch output selected in round-robin fashion from the selected subset.

8. The method as claimed in claim 1, which includes measuring loading characteristics of the resource requests concurrently with the routing of the resource requests, and wherein the routing information is changed based on the measured loading characteristics.

9. The method as claimed in claim 8, wherein the loading characteristics of the resource requests are measured concurrently with the routing of the resource requests by measuring a frequency at which resource requests are received at each of the inputs of the switch.

10. The method as claimed in claim 8, wherein the measuring of the loading characteristics of the resource requests includes computing a modulus from a network address intercepted from the data network, and indexing a table with the modulus to locate an accumulator for accumulating an occurrence of the network address intercepted from the data network.

11. The method as claimed in claim 1, wherein the changing of the routing information is performed concurrently with the routing of resource requests thorough the switch.

12. The method as claimed in claim 11, wherein the routing information for a resource request received at an input of the switch is changed in response to blocking of the resource request received at the input of the switch.

13. The method as claimed in claim 11, wherein the routing information is changed repetitively as a background process with respect to the routing of the resource requests through the switch.

14. A method of routing storage access requests from host processors through a switch to a data storage subsystem, said switch having inputs coupled to the hosts to receive the storage access requests from the hosts, and said switch having outputs coupled to the data storage subsystem to transmit the storage access requests to the data storage subsystem, said method comprising:

a) storing, in a memory, routing information defining respective outputs of the switch to which storage access requests received at inputs of the switch should be routed;

b) in response to storage access requests being received at the inputs of the switch, routing each storage access request received at each input of the switch to an output of the switch by accessing the routing information in the memory to select a respective output of the switch to which said each storage access request should be routed, and routing said each storage access request to the selected output of the switch to which said each storage access request should be routed; and

c) changing the routing information stored in the memory based on loading characteristics of the storage access requests received at the switch inputs in order to balance loading of the storage access requests upon the outputs of the switch.

15. The method as claimed in claim 14, wherein the routing information stored in the memory defines for each input of the switch a respective subset of outputs of the switch to which storage access requests received at said each input of the switch should be routed, and the respective output of the switch to which said each storage access request should be routed is selected by selecting one of the outputs in the respective subset of outputs of the switch for the input of the switch from which said each storage access request is received.

16. The method as claimed in claim 15, wherein the routing information stored in the memory is based on respective priorities assigned to the switch inputs by including different numbers of the switch outputs in the respective subsets.

17. The method as claimed in claim 14, wherein the routing information stored in the memory defines for each host processor a respective subset of outputs of the switch to which storage access requests from said each host processor should be routed, and the respective output of the switch to which said each storage access request should be routed is selected by selecting one of the outputs in the respective subset of outputs of the switch to which storage access requests from said each host processor should be routed.

18. The method as claimed in claim 17, wherein the routing information stored in the memory is based on respective priorities assigned to the hosts by including different numbers of the switch outputs in the respective subsets.

19. The method as claimed in claim 14, wherein the routing information stored in the memory defines a plurality of subsets of outputs of the switch, and wherein the respective output of the switch to which said each storage access request should be routed is selected by selecting one of the subsets, and then selecting the respective output of the switch to which said each storage access request should be routed by selecting one of the outputs in the selected subset.

20. The method as claimed in claim 19, wherein the respective output of the switch to which said each storage access request should be routed is a not-busy switch output selected in round-robin fashion from the selected subset.

21. The method as claimed in claim 14, which includes measuring loading characteristics of the storage access requests concurrently with the routing of the storage access requests, and wherein the routing information is changed based on the measured loading characteristics of the storage access requests.

22. The method as claimed in claim 21, wherein the loading characteristics of the storage access requests are measured concurrently with the routing of the storage access requests by measuring a frequency at which storage access requests are received at each of the inputs of the switch.

23. The method as claimed in claim 21, wherein the measuring of the loading characteristics of storage access requests includes computing a modulus from a network address intercepted from the data network, and indexing a table with the modulus to locate an accumulator for accumulating an occurrence of the network address intercepted from the data network.

24. The method as claimed in claim 14, wherein the changing of the routing information is performed concurrently with the routing of storage access requests thorough the switch.

25. The method as claimed in claim 24, wherein the routing information for a storage access request received at an input of the switch is changed in response to blocking of the storage access request received at the input of the switch.

26. The method as claimed in claim 24, wherein the routing information is changed repetitively as a background process with respect to the routing of the storage access requests through the switch.

27. A switch for routing resource requests in a data network, said switch comprising:

a plurality of inputs;

a plurality of outputs; and

a switch control computer programmed for routing the resource requests from the inputs to the outputs;

wherein the switch control computer includes memory storing routing information, said routing information defining respective outputs of the switch to which resource requests received at the inputs of the switch should be routed; and

wherein the switch control computer is programmed to respond to receipt of the resource requests at the inputs of the switch by routing each resource request received at each input of the switch to an output of the switch by accessing the routing information in the memory to select a respective output of the switch to which said each resource request should be routed, and to route said each resource request to the selected output of the switch to which said each resource request should be routed; and

wherein the switch control computer is further programmed to change the routing information stored in the memory based on loading characteristics of the resource requests received at the switch inputs in order to balance loading of the resource requests upon the outputs of the switch.

28. The switch as claimed in claim 27, wherein the routing information stored in the memory defines for each input of the switch a respective subset of outputs of the switch to which resource requests received at said each input of the switch should be routed, and wherein the switch control computer is programmed to select the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the respective subset of outputs of the switch for the input of the switch from which said each resource request is received.

29. The switch as claimed in claim 28, wherein the routing information stored in the memory includes different numbers of the switch outputs in the respective subsets so that the switch inputs have different respective priorities.

30. The switch as claimed in claim 27, wherein the switch control computer is programmed to route resource requests received at each of a plurality of the inputs of the switch from a plurality of sources, the routing information stored in the memory defines for each source a respective subset of outputs of the switch to which resource requests from said each source should be routed, and the switch control computer is programmed to select the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the respective subset of outputs of the switch to which resource requests from said each source should be routed.

31. The switch as claimed in claim 30, wherein the routing information stored in the memory includes different numbers of the switch outputs in the respective subsets so that the sources have different respective priorities.

32. The switch as claimed in claim 27, wherein the routing information stored in the memory defines a plurality of subsets of outputs of the switch, and wherein the switch control computer is programmed to select the respective output of the switch to which said each resource request should be routed by selecting one of the subsets, and then selecting the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the selected subset.

33. The switch as claimed in claim 32, wherein the switch control computer is programmed to select the respective output of the switch to which said each resource request should be routed by selecting, in a round-robin fashion, a not-busy switch output from the selected subset.

34. The switch as claimed in claim 27, wherein the switch control computer is programmed to measure loading characteristics of the resource requests concurrently with the routing of the resource requests, and wherein the switch control computer is programmed to change the routing information based on the measured loading characteristics.

35. The switch as claimed in claim 34, wherein the switch control computer is programmed to measure the loading characteristics of the resource requests concurrently with the routing of the resource requests by measuring a frequency at which resource requests are received at each of the inputs of the switch.

36. The switch as claimed in claim 34, wherein the switch control computer is programmed to measure the loading characteristics of the resource requests by computing a modulus from a network address decoded from each resource request, and indexing a table with the modulus to locate an accumulator for accumulating an occurrence of the network address decoded from each resource request.

37. The switch as claimed in claim 27, wherein the switch control computer is programmed to change the routing information concurrently with the routing of resource requests thorough the switch.

38. The switch as claimed in claim 37, wherein the switch control computer is programmed to respond to blocking of a resource request received at an the inputs of the switch by changing the routing information for the blocked resource request.

39. The switch as claimed in claim 37, wherein the switch control computer is programmed to change the routing information repetitively as a background process with respect to the routing of the resource requests through the switch.

40. A program storage device containing a program for a switch for routing resource requests in a data network according to routing information stored in a memory, said routing information defining respective outputs of the switch to which resource requests received at the inputs of the switch should be routed;

said program being executable by the switch for responding to receipt of the resource requests at the inputs of the switch by routing each resource request received at each input of the switch to an output of the switch by accessing the routing information in the memory to select a respective output of the switch to which said each resource request should be routed, and to route said each resource request to the selected output of the switch to which said each resource request should be routed; and

wherein the program is further executable by the switch to change the routing information stored in the memory based on loading characteristics of the resource requests received at the switch inputs in order to balance loading of the resource requests upon the outputs of the switch.

41. The program storage device as claimed in claim 40, wherein the routing information stored in the memory defines for each input of the switch a respective subset of outputs of the switch to which resource requests received at said each input of the switch should be routed, and wherein the program is executable by the switch for selecting the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the respective subset of outputs of the switch for the input of the switch from which said each resource request is received.

42. The program storage device as claimed in claim 41, wherein the program is executable by the switch for including in the routing information different numbers of the switch outputs in the respective subsets so that the switch inputs have different respective assigned priorities.

43. The program storage device as claimed in claim 40, wherein the program is executable by the switch for routing resource requests received at each of a plurality of the inputs of the switch from a plurality of sources, the routing information stored in the memory defines for each source a respective subset of outputs of the switch to which resource requests from said each source should be routed, and the program is executable by the switch for selecting the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the respective subset of outputs of the switch to which resource requests from said each source should be routed.

44. The program storage device as claimed in claim 43, wherein the program is executable by the switch for including in the routing information different numbers of the switch outputs in the respective subsets so that the sources have different respective assigned priorities.

45. The program storage device as claimed in claim 40, wherein the routing information stored in the memory defines a plurality of subsets of outputs of the switch, and wherein the program is executable by the switch for selecting the respective output of the switch to which said each resource request should be routed by selecting one of the subsets, and then selecting the respective output of the switch to which said each resource request should be routed by selecting one of the outputs in the selected subset.

46. The program storage device as claimed in claim 45, wherein the program is executable by the switch for selecting the respective output of the switch to which said each resource request should be routed by selecting, in a round-robin fashion, a not-busy switch output from the selected subset.

47. The program storage device as claimed in claim 40, wherein the program is executable by the switch for measure loading characteristics of the resource requests concurrently with the routing of the resource requests, and wherein the program is executable by the switch for changing the routing information based on the measured loading characteristics.

48. The program storage device as claimed in claim 47, wherein the program is executable by the switch for measuring the loading characteristics of the resource requests concurrently with the routing of the resource requests by measuring a frequency at which resource requests are received at each of the inputs of the switch.

49. The program storage device as claimed in claim 47, wherein the program is executable by the switch for measuring the loading characteristics of the resource requests by computing a modulus from a network address decoded from each resource request, and indexing a table with the modulus to locate an accumulator for accumulating an occurrence of the network address decoded from each resource request.

50. The program storage device as claimed in claim 40, wherein the program is executable by the switch for changing the routing information concurrently with the routing of resource requests thorough the switch.

51. The program storage device as claimed in claim 50, wherein the program is executable by the switch for responding to blocking of a resource request received at an input of the switch by changing the routing information for the blocked resource request.

52. The program storage device as claimed in claim 50, wherein the program is executable by the switch for changing the routing information repetitively as a background process with respect to the routing of the resource requests through the switch.

53. A storage network comprising, in combination:

a cached storage subsystem including a plurality of storage devices, a cache memory linked to the storage devices for filling the cache with data from the storage devices, and a plurality of port adapters providing storage ports for access to the cache memory; and

a switch having a plurality of inputs for receiving data access requests from a plurality of hosts, and a plurality of outputs linked to the storage ports for selectively routing data access requests from the inputs of the switch to the storage ports;

wherein the storage network includes a memory containing routing information, said routing information defining respective outputs of the switch to which storage access requests received at the inputs of the switch should be routed;

said switch being programmed to respond to receipt of the storage access requests at the inputs of the switch by routing each storage access request received at each input of the switch to a selected output of the switch by accessing the routing information in the memory to select an output of the switch to which said each storage access request should be routed, and to route said each storage access request to the selected output of the switch to which said each storage access request should be routed; and

wherein the storage network includes a processor programmed to change the routing information in the memory based on loading characteristics of the storage access requests in order to balance loading of the storage access requests.

54. The storage network as claimed in claim 53, wherein the processor is a switch control computer of the switch, and the memory is memory of the switch control computer.

55. The storage network as claimed in claim 53, wherein the switch includes a switch control computer for routing the storage access requests received at the switch inputs to the switch outputs, and said processor is a processor of a digital computer that is separate from the switch and that is programmed for monitoring host activity with respect to the storage network.

56. The storage network as claimed in claim 53, wherein the routing information stored in the memory defines for each input of the switch a respective subset of switch outputs to which storage access requests received at said each input of the switch should be routed, and wherein the switch is programmed to select the respective output of the switch to which said each storage access request should be routed by selecting one of the outputs in the respective subset of outputs of the switch for the input of the switch from which said each storage access request is received.

57. The storage network as claimed in claim 56, wherein the processor is programmed for including in the routing information different numbers of the switch outputs in the respective subsets so that the switch inputs have different respective assigned priorities.

58. The storage network as claimed in claim 53, wherein the routing information stored in the memory defines for each host a respective subset of outputs of the switch to which storage access requests from said each host should be routed, and the switch is programmed for selecting the respective output of the switch to which said each storage access request should be routed by selecting one of the outputs in the respective subset of outputs of the switch to which storage access requests from said each host should be routed.

59. The storage network as claimed in claim 58, wherein the processor is programmed for including in the routing information different numbers of the switch outputs in the respective subsets so that the hosts have different respective assigned priorities.

60. The storage network as claimed in claim 53, wherein the routing information stored in the memory defines a plurality of subsets of outputs of the switch, and wherein the switch is programmed for selecting the respective output of the switch to which said each storage access request should be routed by selecting one of the subsets, and then selecting the respective output of the switch to which said each storage access request should be routed by selecting one of the outputs in the selected subset.

61. The storage network as claimed in claim 60, wherein the switch is programmed for selecting the respective output of the switch to which said each storage access request should be routed by selecting, in a round-robin fashion, a not-busy switch output from the selected subset.

62. The storage network as claimed in claim 53, wherein the processor is programmed for measure loading characteristics of the storage access requests concurrently with the routing of the storage access requests, and wherein the processor is programmed for changing the routing information based on the measured loading characteristics.

63. The storage network as claimed in claim 62, wherein the processor is programmed for measuring the loading characteristics of the storage access requests concurrently with the routing of the storage access requests by measuring a frequency at which storage access requests are received at each of the inputs of the switch.

64. The storage network as claimed in claim 62, wherein the processor is executable by the switch for measuring the loading characteristics of the storage access requests concurrently with the routing of the storage access requests by computing a modulus from a network address decoded from each storage access request, and indexing a table with the modulus to locate an accumulator for accumulating an occurrence of the network address decoded from each storage access request.

65. The storage network as claimed in claim 53, wherein the processor is executable by the switch for changing the routing information concurrently with the routing of storage access requests thorough the switch.

66. The storage network as claimed in claim 65, wherein the processor is programmed for responding to blocking of a storage access request received at one of the inputs of the switch by changing the routing information for the blocked storage access request.

67. The storage network as claimed in claim 65, wherein the processor is programmed for changing the routing information repetitively as a background process with respect to the routing of the storage access requests through the switch.