Cross-bar switch employing a multiple entry point FIFO

• US 7,184,446 B2
• Filed: 12/21/2001
• Issued: 02/27/2007
• Est. Priority Date: 07/06/2001
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Rashid, Abbas, Zaidi, Nazar
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): MOORE JR, MICHAEL J
• Application Number:
  US10/036,622
• Publication Number:
  US 20030043829A1
• Time in Patent Office: 1,894 Days
• Field of Search: 370411-419, 370/428
• US Class Current: 370/424
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/102 using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3018 Input queuing

Abstract

A cross-bar switch includes a set of input ports for receiving data packets and a set of sink ports coupled to the input ports to accept and forward the data packets. Each sink port includes a multiple entry point FIFO with multiple data inputs for receiving data packets. In one implementation, the multiple entry point FIFO includes a FIFO storage buffer and request logic coupling the multiple entry point FIFO'"'"'s data inputs to the FIFO storage buffer. The multiple entry point FIFO concurrently maintains separate pointers into the FIFO storage buffer for each data packet being received on the multiple entry point FIFO'"'"'s data inputs.

Claims

1. An apparatus comprising:

set of input ports;

a FIFO storage buffer;

request logic coupling said set of input ports to said FIFO storage buffer;

a memory in communication with said request logic, wherein said memory concurrently maintains a plurality of pointers, wherein each pointer in said plurality of pointers corresponds to a different location in said FIFO storage buffer for storing data from an input port in said set of input ports, wherein the request logic simultaneously writes data to the FIFO storage buffer for at least two of the input ports;

a set of data rings in communication with said set of input ports;

a ring interface coupled to said set of data rings to accent data from a plurality of sources and supoly said data on a plurality of outputs, said FIFO storage buffer in communication with said ring interface to receive and store said data from said ring interface; and

an output port coupled to said FIFO storage buffer to receive data from said FIFO storage buffer and transmit said data from said FIFO storage buffer on a communications link.

2. The apparatus of claim 1, wherein said memory includes:

a first entry that maintains a pointer corresponding to a first location in said FIFO storage buffer for storing a first set of data from an input port in said set of input ports; and

a second entry that maintains a pointer corresponding to a second location in said FIFO storage buffer for storing a second set of data from an input port in said set of input ports.

3. The apparatus of claim 2, wherein said memory includes:

a third entry that maintains a pointer corresponding to a third location in said FIFO storage buffer for storing a third set of data from on input port in said set of input ports; and

a fourth entry that maintains a pointer corresponding to a fourth location in said FIFO storage buffer for storing a fourth set of data from an input port in said set of input ports.

4. The apparatus of claim 1, wherein said memory maintains a data identifier for each pointer in said plurality of pointers.

5. The apparatus of claim 4, wherein each data identifier identifies a data source.

6. The apparatus of claim 1, wherein said memory is a content addressable memory.

7. The apparatus of claim 1, wherein said request logic and said storage buffer are included in a multiple port memory.

8. An apparatus comprising:

set of input ports;

a FIFO storage buffer;

request logic coupling said set of input ports to said FIFO storage buffer, wherein the request logic simultaneously writes data to the FIFO storage buffer for at least two of the input ports;

a memory in communication with said request logic, wherein said memory concurrently maintains a plurality of pointers, wherein each pointer in said plurality of pointers corresponds to a different location in said FIFO storage buffer for storing data from an input port in said set of input ports;

a set of data rings in communication with said set of input ports,

a ring interface coupled to said set of data rings, said FIFO storage buffer in communication with said ring interface to receive and store said data from said ring interface; and

an output port coupled to said FIFO storage buffer to receive data from said FIFO storage buffer and transmit said data from said FIFO storage buffer on a communications link,

wherein said memory maintains a data identifier for each pointer in said plurality of pointers, wherein each data identifier identifies a data source, and

wherein said memory includes;

a first entry that maintains a pointer corresponding to a first location in said FIFO storage buffer for storing a first set of data from an input port in said set of input ports, and

a second entry that maintains a pointer corresponding to a second location in said FIFO storage buffer for storing a second set of data from an input port in said set of input ports.

9. The apparatus of claim 8, wherein said memory includes:

a third entry that maintains a pointer corresponding to a third location in said FIFO storage buffer for storing a third set of data from an input port in said set of input ports; and

a fourth entry that maintains a pointer corresponding to a fourth location in said FIFO storage buffer for storing a fourth set of data from an input port in said set of input ports.

10. The apparatus of claim 8, wherein said memory is a content addressable memory.

11. The apparatus of claim 8, wherein said request logic and said storage buffer are included in a multiple port memory.

12. A sink port for a cross-bar switch, said sink port comprising:

a multiple entry point FIFO having a plurality of data inputs in communication with a set of input ports to simultaneously accept and store data for at least two of the input ports;

a ring interface coupled to a set of data rings in communication with said set of input ports to accept the data, said multiple entry point FIFO in communication with said ring interface to receive and store said data from said ring interface; and

an output port coupled to said multiple entry point FIFO to receive said data from said multiple entry point FIFO and transmit said data on a communications link.

13. The sink port of claim 12, wherein said multiple entry point FIFO includes:

a FIFO storage buffer;

request logic coupling said set of input ports to said FIFO storage buffer, wherein the request logic simultaneously writes data to the FIFO storage buffer for at least two of the input ports; and

a memory in communication with said request logic, wherein said memory concurrently maintains a plurality of pointers, wherein each pointer in said plurality of pointers corresponds to a different location in said FIFO storage buffer for storing data from an input port in said set of input ports.

14. The sink port of claim 13, wherein said memory includes:

a first entry that maintains a pointer corresponding to a first location in said FIFO storage buffer for storing a first set of data from an input port in said set of input ports; and

a second entry that maintains a pointer corresponding to a second location in said FIFO storage buffer for storing a second set of data from an input port in said set of input ports.

15. The sink port of claim 14, wherein said memory includes:

a third entry that maintains a pointer corresponding to a third location in said FIFO storage buffer for storing a third set of data from an input port in said set of input ports; and

a fourth entry that maintains a pointer corresponding to a fourth location in said FIFO storage buffer for storing a fourth set of data from an input port in said set of input ports.

16. The sink port of claim 13 wherein said memory maintains a data identifier for each pointer in said plurality of pointers.

17. The sink port of claim 16, wherein each data identifier identifies a data source.

18. The sink port of claim 13, wherein said memory is a content addressable memory.

19. The sink port of claim 13, wherein said request logic and said storage buffer are included in a multiple port memory.

20. A cross-bar switch comprising:

a set of input ports to receive data packets;

a set of sink ports in communication with said set of input ports to accept and forward said data packets, wherein a first sink port in said set of sink ports includes a multiple entry point FIFO having a plurality of data inputs that simultaneously store data from data packets accepted by said first sink port for at least two of the input ports; and

a set of data rings in communication with said set of input ports and said set of sink ports,

wherein said first sink port includes;

a ring interface coupled to said set of data rings to accept data from a plurality of sources and supply said data on a plurality of outputs,

said multiple entry point FIFO in communication with said plurality of outputs on said ring interface to receive and store said data from said ring interface; and

an output port coupled to said multiple entry point FIFO to receive data from said multiple entry point FIFO and transmit said data from said multiple entry point FIFO on a communications link.

21. The cross-bar switch of claim 20, wherein said multiple entry point FIFO includes:

a FIFO storage buffer;

request logic coupling said set of input ports to said FIFO storage buffer, wherein the request logic simultaneously writes data to the FIFO storage buffer for at least two of the input ports; and

a memory in communication with said request logic, wherein said memory concurrently maintains a plurality of pointers, wherein each pointer in said plurality of pointers corresponds to a different location in said FIFO storage buffer for storing data from an input port in said set of input ports.

22. The cross-bay switch of claim 21, wherein said memory includes:

a first entry that maintains a pointer corresponding to a first location in said FIFO storage buffer for storing a first set of data from an input pot in said set of input ports; and

a second entry that maintains a pointer corresponding to a first location in said FIFO storage buffer for storing a second set of data from an input port in said set of input ports.

23. The cross-bar switch of claim 22, wherein said memory includes:

a third entry that maintains a pointer corresponding to a third location in said FIFO storage buffer for storing a third set of data from an input port in said set of input port in said set of input ports; and

a fourth entry that maintains a pointer corresponding to a fourth location in said FIFO storage buffer for storing a fourth set of data from an input port in said set of input ports.

24. The cross-bar switch of claim 21, wherein said memory maintains a data identifier for each pointer in said plurality of pointers.

25. The cross-bar switch of claim 24, wherein each data identifier identifies a data source.

26. The cross-bar switch of claim 21, wherein said memory is a content addressable memory.

27. The cross-bar switch of claim 21, wherein said request logic and said storage buffer are included in a multiple port memory.

28. The cross-bar switch of claim 20, wherein each sink port in said set of sink port includes:

a multiple entry point FIFO having a plurality of data inputs.

29. The cross-bar switch of claim 20, wherein said multiple entry point FIFO includes a data input for each data ring in said set of data rings.

30. A cross-bar switch comprising:

a set of input ports to receive data packets;

a set of sink ports in communication with said set of input ports to accent and forward said data packets, wherein a first sink port in said set of sink ports includes a multiple entry point FIFO having a plurality of data inputs that simultaneously store data from data packets accepted by said first sink port for at least two of the input ports,

a set of data rings in communication with said set of input ports and said set of sink ports,

wherein said first sink port snoops data packets on each data ring in said set of data rings and determines whether to accept a first data packet based on a set of criteria, wherein said set of criteria includes;

said first sink port having sufficient storage space for storing said first data packet,

said first sink port supporting a destination targeted by said first data packet, and

a total number of packets being received by said first sink port not exceeding a predetermined number of packets.

31. A method for a sink port in a cross-bar switch to collect data in a FIFO, said method comprising the steps of:

(a) accepting data from a first data packet, wherein said data accepted in said step (a) is a subset of said first data packet;

(b) storing said data from said first data packet in said FIFO;

(c) accepting data from a second data packet at substantially the same time as the data from the first data packet, wherein said data accepted in said step (c) is a subset of said second data packet; and

(d) storing said data from said second data packet in said FIFO at substantially the same time as the data from the first data packet,

wherein accepting in said steps (a) and (c) includes snooping data packets on each data ring in a set of data rings and determining whether to accept the first data packet and the second data packet based on a set of criteria, wherein said set of criteria includes said sink port having sufficient storage space for storing said first data packet, said sink port supporting a destination targeted by said first data packet and a total number of packets being received by said sink port not exceeding a predetermined number of packets.

32. The method of claim 31, wherein said first data packet originates from a first source and said second data packet originated from a second source.

33. The method of claim 31, further including the steps of:

(e) determining that said data accepted in said step (a) includes a first line of said first data packet;

(f) allocating a first location in said FIFO for storing data from said first data packet;

(g) determining that said data accepted in said step (c) includes a first line of said second data packet; and

(h) allocating a second location in said FIFO for storing data from said second data packet.

34. The method of claim 33, wherein said step (f) includes the steps of:

(1) creating a first pointer to said first location; and

(2) creating a first tag identifying said first data packet.

35. The method of claim 34, wherein said step (h) includes the steps of:

(1) creating a second pointer to said second locations; and

(2) creating a second tag identifying said second data packet.

36. The method of claim 35, wherein said first tag identifies a source if said first data packet and said second tag identifies a source of said second data packet.

37. The method of claim 33, further including the steps of:

(j) accepting additional data for said first data packet;

(k) determining that said additional data accepted in said step (j) does not include a first line of said first data packet;

(l) identifying a position in said first location in said FIFO for storing said additional data from said first data packet;

(m) accepting additional data for said second data packet;

(n) determining that said additional data accepted in said step (m) does not include a first line of said second data packet; and

(o) identifying a position in said second location in said FIFO for storing said additional data from said second data packet.

38. The method of claim 37,

wherein said step (1) includes the step of:

(1) retrieving a pointer to said position in said first location, and wherein said step (o) includes the step of;

(2) retrieving a pointer to said position in said second location.

39. The method of claim 33, further including the steps of:

(p) accepting additional data for said first data packet;

(q) determining that said additional data accepted in said step (p) includes a last line of said first data packet;

(r) purging a pointer to a position in said first location in said FIFO;

(s) accepting additional data for said second data packet;

(t) determining that said additional data accepted in said step (r) includes a last line of said second data packet; and

(u) purging a pointer to a position in said second location in said FIFO.