Method and system to control the communication of data between a plurality of inteconnect devices

• US 20040225734A1
• Filed: 05/07/2003
• Published: 11/11/2004
• Est. Priority Date: 05/07/2003
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Schober, Richard L., Reeve, Rick, Vajjhala, Prasad
• Application Number:
  US10/431,975
• Publication Number:
  US 20040225734A1
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/358 Infiniband Switches

Abstract

A method and system of communicating data between a plurality of interconnect devices are described. The method includes allocating a sequence number associated with each grant authorizing a source interconnect device to communicate the data to a destination interconnect device. The sequence number of a queued grant is then with a reference sequence number and, in response to the comparison, the data is communicated. In one embodiment, the sequence number is a grant sequence number that defines a sequence in which each grant is to be executed in response to a comparison with a reference transmit sequence number.

Claims

1. A method of communicating data between a plurality of interconnect devices, the method including:

allocating a sequence number associated with each grant authorizing a source interconnect device to communicate the data to a destination interconnect device;

comparing the sequence number of a queued grant with a reference sequence number; and

communicating the data in response to the comparison.

2. The method of claim 1, wherein the sequence number is a grant sequence number and the data is in the form of a data packet, the method including:

allocating a grant sequence number to each grant, the grant sequence number defining a sequence in which each grant is to be executed;

comparing the grant sequence number of a queued grant with a reference transmit sequence number; and

executing the grant in response to the comparison thereby to communicate the data.

3. The method of claim 2, which includes comparing at each interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

4. The method of claim 3, which includes allocating at an arbiter a sequence of grant sequence numbers for each particular interconnect device, the grant sequence numbers being uniquely associated with each particular interconnect device and defining the order in which other interconnect devices communicate the data packet to the particular interconnect device.

5. The method of claim 4, which includes incrementing the reference transmit sequence number associated with the particular interconnect device at all other interconnect devices when the data packet has been communicated to the particular interconnect device.

6. The method of claim 4, which includes refraining from issuing further grant sequence numbers when a predetermined maximum number of grants remain unexecuted.

7. The method of claim 2, wherein the grant sequence numbers and the transmit sequence numbers are n-bit binary values.

8. The method of claim 2, wherein the interconnect devices are input/output ports forming part of a switch, the method including communicating the data packets through the switch when executing the grant.

9. The method of claim 1, wherein the sequence number is a grant sequence number and the data is in the form of a data packet, the method including:

allocating a grant sequence number to each grant, the grant sequence number defining a sequence in which the data packet associated with each grant is to be moved into a pre-fetch buffer;

comparing the grant sequence number of a queued grant with a reference pre-fetch sequence number; and

moving the data packet into the pre-fetch buffer in response to the comparison.

10. The method of claim 9, which includes comparing at each interconnect device the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the pre-fetch sequence number of a grant associated with the next data packet to be communicated from the interconnect device.

11. The method of claim 10, which includes allocating at an arbiter a sequence of grant sequence numbers for each particular interconnect device, the grant sequence numbers being uniquely associated with each particular interconnect device and defining the order in which data packets are moved into the pre-fetch buffer for communication dependent upon the grant sequence number.

12. The method of claim 11, which includes incrementing the reference pre-fetch sequence number associated with the particular interconnect device at all other interconnect devices when the data packet has been moved to the pre-fetch buffer.

13. The method of claim 9, wherein the grant sequence numbers and the pre-fetch sequence numbers are n-bit binary values.

14. A method of controlling the communication of data from an interconnect device, the method including:

receiving a grant authorizing the communication of the data;

extracting a grant sequence number from the grant;

comparing the grant sequence number with a reference transmit sequence number; and

communicating the data in response to the comparison.

15. The method of claim 14, wherein the data is in the form of data packets and the method includes comparing at the interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

16. The method of claim 15, which includes storing at the interconnect device a reference transmit sequence number for each of a plurality of associated interconnect devices, each reference transmit sequence number being uniquely associated with a particular associated interconnect device and defining the order in which the interconnect device communicates data packets to the associated interconnect devices.

17. The method of claim 16, which includes communicating a reference transmit increment signal to the associated interconnect devices while the data packet is communicated by the particular interconnect device.

18. The method of claim 17, which includes incrementing the reference transmit sequence number for each of the plurality of associated interconnect devices in response to the reference transmit increment signals.

19. The method of claim 14, wherein the grant sequence numbers are n-bit binary values.

20. The method of claim 14, wherein the interconnect device is an input/output port forming part of a switch.

21. The method of claim 14, which includes:

receiving a grant sequence number associated with a grant authorizing the interconnect device to communicate a data packet to one of associated interconnect devices, the grant sequence number defining a sequence in which a data packet associated with each grant is to be moved into a pre-fetch buffer of the interconnect device;

comparing the grant sequence number of the grant with a reference pre-fetch sequence number; and

moving the data packet into the pre-fetch buffer in response to the comparison.

22. The method of claim 21, which includes comparing at the interconnect device the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the grant sequence number of the next grant to be executed.

23. The method of claim 22, in which an arbiter allocates a sequence of grant sequence numbers for all interconnect devices, the grant sequence numbers being uniquely associated with each particular interconnect device and defining the order in which data packets are moved into the pre-fetch buffer for communication dependent upon the grant sequence number.

24. The method of claim 23, which includes communicating a reference pre-fetch increment signal to the associated interconnect devices when the data packet has been moved into the pre-fetch buffer.

25. The method of claim 23, which includes incrementing the reference pre-fetch sequence number for each of the plurality of associated interconnect devices in response to the reference pre-fetch increment signals.

26. The method of claim 21, wherein the grant sequence numbers and pre-fetch sequence numbers are n-bit binary values.

27. A method of managing the execution of grants issued to a plurality of interconnect devices, the method including:

receiving a grant request from an interconnect device to communicate data to a destination interface device;

selectively allocating a grant sequence number to the grant, the grant sequence number defining when the grant is to be executed; and

communicating the grant sequence number to the interconnect device.

28. The method of claim 27, wherein the grant sequence number is included within the grant communicated to the interconnect device.

29. The method of claim 27, which includes allocating at an arbiter a sequence of grant sequence numbers for each particular interconnect device, the grant sequence numbers being uniquely associated with each particular interconnect device when functioning as a destination interconnect device and defining the order in which other interconnect devices communicate data in the form of data packets to the destination interconnect device.

30. The method of claim 27, which includes refraining from issuing further grant sequence numbers when a predetermined maximum number of grants remain unexecuted.

31. The method of claim 30, which includes monitoring when a grant is executed and decrementing the outstanding grants counter in response to the execution of a grant.

32. The method of claim 27, wherein the grant sequence numbers are n-bit binary values.

33. A machine-readable medium embodying a sequence of instructions that, when executed by a machine, cause the machine to execute a method of communicating data between a plurality of interconnect devices, method including:

allocating a sequence number associated with each grant authorizing a source interconnect device to communicate the data to a destination interconnect device;

comparing the sequence number of a queued grant with a reference sequence number; and

communicating the data in response to the comparison.

34. The machine-readable medium of claim 33, wherein the sequence number is a grant sequence number and the data is in the form of a data packet, the method including:

allocating a grant sequence number to each grant, the grant sequence number defining a sequence in which each grant is to be executed;

comparing the grant sequence number of a queued grant with a reference transmit sequence number; and

executing the grant in response to the comparison thereby to communicate the data.

35. The machine-readable medium of claim 34, wherein the method includes comparing at each interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

36. The machine-readable medium of claim 35, wherein the method includes:

allocating a grant sequence number to each grant, the grant sequence number defining a sequence in which the data packet associated with each grant is to be moved into a pre-fetch buffer;

comparing the grant sequence number of a queued grant with a reference pre-fetch sequence number; and

moving the data packet into the pre-fetch buffer in response to the comparison.

37. The machine-readable medium of claim 36, wherein the method includes comparing at each interconnect device the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the pre-fetch sequence number of a grant associated with the next data packet to be communicated from the interconnect device.

38. A machine-readable medium embodying a sequence of instructions that, when executed by a machine, cause the machine to execute a method of controlling the communication of data from an interconnect device, the method including:

receiving a grant authorizing the communication of the data;

extracting a grant sequence number from the grant;

comparing the grant sequence number with a reference transmit sequence number; and

communicating the data in response to the comparison.

39. The machine-readable medium of claim 38 wherein the data is in the form of data packets and the method includes comparing at the interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

40. The machine-readable medium of claim 38, which includes storing at the interconnect device a reference transmit sequence number for each of a plurality of associated interconnect devices, each reference transmit sequence number being uniquely associated with a particular associated interconnect device and defining the order in which the interconnect device communicates data packets to the associated interconnect devices.

41. The machine-readable medium of claim 40, which includes communicating a reference transmit increment signal to the associated interconnect devices while the data packet is communicated by the particular interconnect device.

42. The machine-readable medium of claim 38, in which the method includes:

receiving a grant sequence number associated with a grant authorizing the interconnect device to communicate a data packet to one of associated interconnect devices, the grant sequence number defining a sequence in which a data packet associated with each grant is to be moved into a pre-fetch buffer of the interconnect device;

comparing the grant sequence number of the grant with a reference pre-fetch sequence number; and

moving the data packet into the pre-fetch buffer in response to the comparison.

43. The machine-readable medium of claim 42, in which the method includes comparing at the interconnect device the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the grant sequence number of the next grant to be executed.

44. The machine-readable medium of claim 43, in which the method includes communicating a reference pre-fetch increment signal to the associated interconnect devices when the data packet has been moved into the pre-fetch buffer.

45. The machine-readable medium of claim 43, in which the method includes incrementing the reference pre-fetch sequence number for each of the plurality of associated interconnect devices in response to an associated pre-fetch input signal.

46. A machine-readable medium embodying a sequence of instructions that, when executed by a machine, cause the machine to execute a method of managing the execution of grants issued to a plurality of interconnect devices, the method including:

receiving a grant request from an interconnect device to communicate data to a destination interface device;

selectively allocating a grant sequence number to the grant that defines when the grant is to be executed; and

communicating the grant sequence number to the interconnect device.

47. The machine-readable medium of claim 46, wherein the grant sequence number is included within the grant communicated to the interconnect device.

48. The machine-readable medium of claim 46, in which the method includes allocating at an arbiter a sequence of grant sequence numbers for each particular interconnect device, the grant sequence numbers being uniquely associated with each particular interconnect device when functioning as a destination interconnect device and defining the order in which other interconnect devices communicate data in the form of data packets to the destination interconnect device.

49. The machine-readable medium of claim 46, in which the method includes refraining from issuing further grant sequence numbers when a predetermined maximum number of grants remain unexecuted.

50. A system for communicating data between a plurality of interconnect devices, system including:

an arbiter to allocate a sequence number associated with each grant authorizing a source interconnect device to communicate the data to a destination interconnect device;

a comparator to compare the sequence number of a queued grant with a reference sequence number; and

a data transmission module to communicate the data in response to the comparison.

51. The system of claim 50, wherein the sequence number is a grant sequence number and the data is in the form of a data packet, and wherein:

the arbiter allocates a grant sequence number to each grant, the grant sequence number defining a sequence in which each grant is to be executed;

the comparator compares the grant sequence number of a queued grant with a reference transmit sequence number; and

the data transmission module executes the grant in response to the comparison thereby to communicate the data.

52. The system of claim 51, wherein the comparator compares at each interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

53. The system of claim 50, wherein the sequence number is a grant sequence number and the data is in the form of a data packet, and wherein:

the arbiter allocates a grant sequence number to each grant, the grant sequence number defining a sequence in which the data packet associated with each grant is to be moved into a pre-fetch buffer;

the comparator compares the grant sequence number of a queued grant with a reference pre-fetch sequence number; and

the data transmission module moves the data packet into the pre-fetch buffer in response to the comparison.

54. The system of claim 53, wherein the comparator compares at each interconnect device the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the grant sequence number of a grant associated with the next data packet to be communicated from the interconnect device.

55. An interconnect device, which includes:

a grant module to receive a grant authorizing the communication of data received by the interconnect to an associated interconnect device;

a processor to extract a grant sequence number from the grant and to compare the grant sequence number with a reference transmit sequence number; and

a data transmission module to communicate the data in response to the comparison.

56. The interconnect device of claim 55, wherein the data is in the form of data packets and the processor compares at the interconnect device the grant sequence number of the next queued grant with the reference transmit sequence number that identifies the grant sequence number of the next grant to be executed.

57. The interconnect device of claim 56, which includes a buffer to store a reference transmit sequence number for each of a plurality of associated interconnect devices, each reference transmit sequence number being uniquely associated with a particular associated interconnect device and defining the order in which the interconnect device communicates data packets to the associated interconnect devices.

58. The interconnect device of claim 57, which communicates a reference transmit increment signal to the associated interconnect devices while the data packet is communicated by the particular interconnect device.

59. The interconnect device of claim 57, which includes memory for storing a grant sequence number associated with a grant authorizing the interconnect device to communicate a data packet to one of associated interconnect devices, the grant sequence number defining a sequence in which a data packet associated with each grant is to be moved into a pre-fetch buffer of the interconnect device, the processor comparing the grant sequence number of the grant with a reference pre-fetch sequence number and moving the data packet into the pre-fetch buffer in response to the comparison.

60. The interconnect device of claim 59, in which the processor compares the grant sequence number of the next queued grant with the reference pre-fetch sequence number that identifies the grant sequence number of the next grant to be executed.

61. The interconnect device of claim 60, in which the data transmission module communicates a reference pre-fetch increment signal to the associated interconnect devices when the data packet has been moved into the pre-fetch buffer.

62. The interconnect of claim 60, in which the processor increments the reference pre-fetch sequence number for each of the plurality of associated interconnect devices in response to an associated pre-fetch input signal.

63. An arbiter for managing the execution of grants issued to a plurality of interconnect devices, the arbiter including a grant allocator:

to receive a grant request from an interconnect device to communicate data to a destination interface device;

to selectively allocate a grant sequence number to the grant that defines when the grant is to be executed; and

to communicate the grant sequence number to the interconnect device.

64. The arbiter of claim 63, wherein the grant sequence number is included within the grant communicated to the interconnect device.

65. The arbiter of claim 63, in which the allocator allocates a sequence of grant sequence numbers for each particular interconnect device, the grant sequence numbers being uniquely associated with each particular interconnect device when functioning as a destination interconnect device and defining the order in which other interconnect devices communicate data in the form of data packets to the destination interconnect device.

66. The arbiter of claim 65, in which the allocator refrains from issuing further grant sequence numbers when a predetermined maximum number of grants remain unexecuted.

67. A system for communicating data between a plurality of interconnect devices, system including:

means for allocating a sequence number associated with each grant authorizing a source interconnect device to communicate the data to a destination interconnect device;

means for comparing the sequence number of a queued grant with a reference sequence number; and

means for communicating the data in response to the comparison.