Method of and system for physically distributed, logically shared, and data slice-synchronized shared memory switching

• US 20070121499A1
• Filed: 11/28/2005
• Published: 05/31/2007
• Est. Priority Date: 11/28/2005
• Status: Abandoned Application

• Current Assignee: QOS Logix, Inc.
• Original Assignee: QOS Logix, Inc.
• Inventors: Ray, Rajib, Eppling, John, Pal, Subhasis
• Application Number:
  US11/287,676
• Publication Number:
  US 20070121499A1
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos

Abstract

An improved data networking technique and apparatus using a novel physically distributed but logically shared and data-sliced synchronized shared memory switching datapath architecture integrated with a novel distributed data control path architecture to provide ideal output-buffered switching of data in networking systems, such as routers and switches, to support the increasing port densities and line rates with maximized network utilization and with per flow bit-rate latency and jitter guarantees, all while maintaining optimal throughput and quality of services under all data traffic scenarios, and with features of scalability in terms of number of data queues, ports and line rates, particularly for requirements ranging from network edge routers to the core of the network, thereby to eliminate both the need for the complication of centralized control for gathering system-wide information and for processing the same for egress traffic management functions and the need for a centralized scheduler, and eliminating also the need for buffering other than in the actual shared memory itself,—all with complete non-blocking data switching between ingress and egress ports, under all circumstances and scenarios.

Claims

1. A method of non-blocking output-buffered switching of time-successive lines of input data streams along a data path between N input and N output data ports provided with corresponding respective ingress and egress data line cards, and wherein each ingress data port line card receives L bits of data per second of an input data stream to be fed to M memory slices and written to the corresponding memory banks and ultimately read by the corresponding output port egress data line cards, the method comprising,

creating a physically distributed logically shared memory datapath architecture wherein each line card is associated with a corresponding memory bank, a memory controller and a traffic manager;

connecting each ingress line card to its corresponding memory bank and also to the memory bank of every other line card through an N×

M mesh, providing each input port ingress line card with data write access to all the M memory banks, and wherein each data link provides L/M bits per second path utilization;

connecting the M memory banks through an N×

M mesh to egress line cards of the corresponding output data ports, with each memory bank being connected not only to its corresponding output port but also to every other output port as well, providing each output port egress line card with data read access to all the M memory banks;

segmenting each of the successive lines of each input data stream at each ingress data line card into a row of M data segment slices along the line;

partitioning data queues for the memory banks into M physically distributed separate column slices of memory data storage locations or spaces, one corresponding to each data segment slice;

writing each such data segment slice of a line along the corresponding link of the ingress N×

M mesh into its corresponding memory bank column slice at the same predetermined corresponding storage location or space address in its respective corresponding memory bank column slices as the other data segment slices of the data line occupy in their respective memory bank column slice, whereby the writing-in and storage of the data line slices occurs in lockstep as a row across the M memory bank column slices; and

writing the data segment slices of the next successive data line into their corresponding memory bank column slices at the same queue storage location or space address thereof adjacent the storage location or space row address in that memory bank column slice of the corresponding data segment slice already written in from the preceding input data stream line.

2. The method of claim 1 wherein the data-slice writing into memory is effected simultaneously for the slices in each line, and the slice is controlled in size for load-balancing across the M memory banks.

3. The method of claim 2 wherein each of the data lines is caused to have the same line width.

4. The method of claim 3 wherein, in the event any line lacks sufficient data slices to satisfy this width, padding a line with dummy-padding slices sufficient to achieve the same line width and to enable said lockstep storage.

5. The method of claim 1 wherein the architecture of the distributed lockstep memory bank storage is operated to resemble the operation of a single logical FIFO per data queue of width spanning the M memory banks and with a write bandwidth of L bits/second.

6. The method of claim 1 wherein said architecture is integrated with a distributed data control path that enables the respective line cards to derive respective data queue pointers for en-queuing and de-queuing functions.

7. The method of claim 6 wherein, at the egress side of the distributed data control path, each traffic manager monitors its own read and write pointers to infer the status of the respective queues since the lines that comprise the queue span the M memory banks.

8. The method of claim 7 wherein there is provided monitoring of the read and write of the data slices at the corresponding memory bank to provide an architecture for inferring of the line count on the data slice that is current for a particular queue.

9. The method of claim 8 wherein the integrating of the distributed control path with the distributed shared memory architecture enables the traffic managers of the respective egress line cards to provide for quality of service in maintaining data allocations and bit-rate accuracy, and for each of re-distributing unused bandwidth for full output line-rate, and for adaptive bandwidth scaling.

10. The method of claim 1 wherein each queue of the physically distributed column slices is unified across the M memory slices in the sense that the addressing of all the data segment slices of a queue is identical across all the memory bank column slices for the same line.

11. The method of claim 4 wherein the padded data written into memory ensures that the state of a queue is identical for all M memory slices, with read and write pointers derived from the respective line cards being identical across all the M memory slices.

12. The method of claim 6 wherein the ingress side of the distributed control path maintains write pointers for the queues dedicated to that input port, and in the form of an array index by the queue number.

13. The method of claim 12 wherein a write pointer is read from the array based on the queue number and then incremented by the total line count of data transfer, and then written back to the array within a time of minimum data transfer adapted to keep up with L bits/second.

14. The method of claim 1 wherein each output port is provided with a queue per input port per class of service, thereby eliminating any requirement for a queue to have more than L bits/second of write bandwidth, and thereby enabling delivery of ideal quality of service in terms of bandwidth with low latency and jitter.

15. The method of claim 6 wherein the memory bank is partitioned into multiple memory column slices with each memory slice containing all of the columns from each corresponding queue and receiving corresponding multiple data streams from different input ports.

16. The method of claim 15 wherein read and write pointers for a single queue are matched across all the M memory slices and corresponding multiple memory column slices, with the multiple data streams being written at the same time, and with each of the multiple queues operating independently of one another.

17. The method of claim 16 wherein at the output ports, each memory slice reads thereto up to N data slices, one for each of the corresponding output ports during each time-successive output data line, with corresponding multiple data slices, one for each of the multiple queues, being read out to their respective output ports.

18. The method of claim 16 wherein, as the data from the multiple queues is read out of memory, each output port is supplied with the necessary data to maintain line rate on its output.

19. The method of claim 1 wherein, in the non-blocking write datapath from the input ports into the shared memory bank slices, the non-blocking is effected regardless of the input data traffic rate and output port destination, providing a nominal, close to zero, latency on the write path into the shared memory banks.

20. The method of claim 6, wherein in the non-blocking read data path from the shared memory slices to the output ports, the non-blocking is effected regardless of data traffic queue rates up to L bits/second per port and independently of the input data packet rate.

21. The method of claim 20 wherein contention between the N output ports is eliminated by providing each output port with equal read access from each memory slice, guaranteeing L/M bits/second from each memory slice for an aggregate bandwidth of L bits/second.

22. The method of claim 8 wherein the inferring of the line count on the data slice provides a non-blocking inferred control path that permits the traffic manager to infer the read and write pointer of the corresponding queue at the egress to provide ideal QOS.

23. The method of claim 1 wherein a non-blocking matrix of the two-element memory stage for the memory banks is provided to guarantee a non-blocking write path from the N input ports and a non-blocking read path from the N output ports.

24. The method of claim 23 wherein the two-element memory stage is formed of an SRAM memory element enabling temporary data storage therein that builds blocks of data on a per queue basis, and a relatively low speed DRAM memory element for providing primary data packet buffer memory.

25. The method of claim 1 wherein for J read and write accesses of size D data bits every T nanoseconds, and a requirement to transmit or receive P data bits every T nanoseconds, a matrix memory organization of (N×

N)/(J/2 ×

J/2) memory banks is pointed on each of the memory slices, providing a bandwidth of each link of L bits/second divided by the number M of memory slices, where M is defined as P/D.

26. The method of claim 25 wherein the memory organization can be varied by changing the number of memory banks on a single memory slice, trading-off additional links and memory slices.

27. The method of claim 25 wherein the number of ingress links, egress links and memory banks per memory slice are balanced to achieve the desired card real estate, backplane connectivity and implementation.

28. The method of claim 27 wherein such balancing is achieved by removing rows and respective output ports from the N×

N matrix to reduce the number of memory banks per memory slice, while increasing the number of memory slices and ingress links and maintaining the number of egress links.

29. The method of claim 27 wherein such balancing is achieved by removing columns and respective ingress ports from the N×

N matrix to reduce the number of memory banks per memory slice, increasing the number of memory slices and egress links while maintaining the number of ingress links.

30. The method of claim 4 wherein link bandwidth is not consumed by dummy-padding slices through the placing of the first data slice of the current incoming data line on the link adjacent to the link used by the last data slice of the previous data line, such that the data slices have been rotated within a line.

31. The method of claim 30 wherein a control bit is embedded with the starting data slice to indicate to the egress how to rotate the data slices back to the original order within a line, and a second control bit is embedded with each data slice to indicate if a dummy-padding slice is required for the subsequent line.

32. The method of claim 31 wherein, when a dummy-padding slice is to be written to memory based on the current data slice, said control bit indicates that a dummy-padding slice is required at the subsequent memory slice address and with no requirement of increased link bandwidth.

33. The method of claim 1 wherein the write pointers reside on the memory slice, insuring that physical addresses are never sent on the N×

M ingress or egress meshes.

34. The method of claim 33 wherein a minimal queue identifier is transmitted with each data slice to store the data slice into the appropriate location address in the memory slice, while only referencing the queues of the respective current ingress port.

35. The method of claim 24 wherein, when the two-element memory stage is transferring a relatively slow wide block transfer from the SRAM to the DRAM, data slices are accordingly written to the SRAM at a location address based on a minimal queue identifier, permitting address generation to reside on the memory controller and not on the input ports and obviating a high address look-up rate on the controller.

36. The method of claim 35 wherein, when N=M, said memory controller does not require knowledge of the physical address until said transferring of a block of data from the SRAM to the DRAM.

37. The method of claim 36 wherein the SRAM is selected as QDR SRAM and the DRAM is selected as RLDRAM.

38. The method of claim 8 wherein the traffic manager of each output port derives inferred write pointers by monitoring the memory controller for writing to its own queues based on the current state of the read and write pointers, and deriving inferred read pointers by monitoring the memory controller for read operations to its own queues.

39. The method of claim 9 wherein in the egress data path of each output port, the egress traffic manager is integrated into the egress data path through the inferred control architecture, enqueuing of data from the corresponding memory slice to the egress traffic manager and scheduling the same while managing the bandwidth, request generation and reading from memory, and then updating the corresponding originating input port.

40. The method of claim 39 wherein during said enqueuing of data from each egress traffic manager from its own memory slice, each egress traffic manager infers from the ingress and egress data path activity on its own corresponding memory slice, the state of its queues across the M memory banks.

41. The method of claim 40 wherein said egress traffic manager, while enqueuing, monitors an interface to the corresponding memory controller for queue identifiers representing write operations for its queues, and counting and accumulating the number of write operations to each of its queues, thereby calculating the corresponding line counts and write pointers.

42. The method of claim 41 wherein the egress traffic manager residing on each memory slice provides QOS to its corresponding output port by determining precisely when and how much data should be dequeued from each of its queues, basing such determining on a scheduling algorithm, a bandwidth management algorithm and the latest information of the state of the queues of each egress traffic manager.

43. The method of claim 40 wherein output port time slots are determined by read request from the corresponding egress traffic manager, and upon the granting of read access to an output port, processing the corresponding read requests, and thereupon transmitting the data slices to the corresponding output port.

44. The method of claim 43 wherein there is embedding of a continuation count for determining the number of further data slices necessary to read in order to reach the end of a current data packet, thereby allowing each egress traffic manager to dequeue data on the boundaries of the data packet to its corresponding output port.

45. The method of claim 43 wherein each ingress traffic manager monitors read operations to its dedicated queues to infer the state of its read pointers, enabling deriving the line count or depth of all queues dedicated to it based on corresponding write pointers and inferred read pointers, and using said depth to determine when to write or drop an incoming data packet to memory.

46. The method of claim 1 wherein, as additional line cards are provided to add to the aggregate memory bandwidth and storage thereof, redistributing the data slices equally amongst all memory slices, utilizing the memory bandwidth and storage of the new memory slices, and reducing the bandwidth to the active memory slices, thereby freeing up memory bandwidth to accommodate data slices from new line cards, such that the aggregate read and write bandwidth to each memory slice is 2×

L bits/second, when N=M.

47. The method of claim 46 wherein the queue size, physical location and newly added queues are reconfigured, with hot swapping that supports line cards being removed or inserted without loss of data or disruption of service to data traffic on the active line cards, by the ingress side embedding a control flag with the current data slice, which indicates to the egress side that the ingress side will switch over to a new system configuration at a predetermined address location in the corresponding queue, and to also switch over to the new system configuration when reading from the same address.

48. The method of claim 1 wherein a crosspoint switch is interposed between the links that comprises the N×

M ingress and egress meshes to provide connectivity flexibility.

49. The method of claim 1 wherein a time division multiplexer switch is substituted for the N×

M ingress and egress meshes and interposed between the input and output ports, providing programmable connectivity between memory slices and the traffic manager while reducing the number of physical links.

117. The apparatus of claim 116 wherein the egress traffic manager residing on each memory slice provides QOS to its corresponding output port through means for determining precisely when and how much data should be dequeued from each of its queues, basing such determining on a scheduling algorithm, a bandwidth management algorithm and the latest information of the state of the queues of each egress traffic manager.

118. The apparatus of claim 115 wherein output port time slots are determined by read request from the corresponding egress traffic manager, with means operable upon the granting of read access to an output port, for processing the corresponding read requests, and thereupon transmitting the data slices to the corresponding output port.

119. The apparatus of claim 118 wherein there is provided means for embedding a continuation count for determining the number of further data slices necessary to read, in order to reach the end of a current data packet, thereby allowing each egress traffic manager to dequeue data on packet boundaries to its corresponding egress port.

120. The apparatus of claim 118 wherein each ingress traffic manager is provided with means for monitoring read operations to its dedicated queues to infer the state of its read pointers, means for deriving the line counts or depth of all queues dedicated to it based on corresponding write pointers and inferred read pointers, and means for using said depth to determine when to write or drop an incoming data packet to memory.

127. The method of claim 1 wherein multicasting is effected by dedicating a queue for multicasting per input port per multicast group to enable the queue-to-be-multicast to be written by a single input port and read by 1 to N output ports, thereby enabling N input ports to multicast the incoming data traffic to the N output ports while maintaining the input line rate of L bits/sec, and similarly enabling N output ports to multicast up to the output line rate of L bits/sec.

128. The method of claim 8 wherein, in multicast operation with multicast queues, the line count is only decremented after all output ports have read a line from the queue, thereby achieving per multicast queue line count coherency across all input ports and respective traffic managers.

129. The method of claim 8 wherein, with unicast queues with a single input and output port respective writing and reading queues, the inferred read and write pointers or line counts determine the fullness of a queue for the purpose of either admitting or dropping an incoming data packet, either to increment the corresponding line count when writing to a queue, or for a read operation to the same queue in order to decrement the corresponding line count.

130. The method of claim 1 wherein the ingress line card, the egress line card and the memory slice reside on the same line card.

50. A method of non-blocking output-buffered switching of time-successive lines of input data streams along a data path between N input and N output data ports provided with corresponding respective ingress and egress data line cards, and wherein each ingress data port line card receives L bits of data per second of an input data stream to be fed to M memory slices and written to corresponding memory banks and ultimately read by corresponding output port egress data line cards, the method comprising, providing a non-blocking matrix of two-element memory stages for the memory banks to guarantee a non-blocking data write path from the N input ports and a non-blocking data read path from the N output ports, wherein the memory stages comprise a combined SRAM memory element enabling temporary data storage therein that builds blocks of data on a per queue basis, and a relatively low speed DRAM main memory element for providing main data packet buffer memory.

51. The method of claim 50 wherein the SRAM element provides fast random access capability required to provide said non-blocking matrix, while the DRAM element provides the queue depth capability to absorb data including during bursts or times of oversubscribed traffic.

52. The method of claim 51 wherein the SRAM element performs a data cache function, always directly accessed by the connected ingress and egress ports, which do not directly access the DRAM element, such that the cache always stores the head of each data queue for the connected egress ports to read from, and the tail of each queue for the connected ingress ports to which to write.

53. The method of claim 52 wherein the SRAM cache is partitioned into queues that correspond to queues maintained in the DRAM memory such that said cache and a memory management controller are seamlessly transferring blocks of data between the SRAM-based cache and the DRAM-based main memory, while guaranteeing the connected egress and ingress ports their respective read and write accesses to the corresponding queues every data transfer interval.

54. The method of claim 53 wherein the cache comprises a QDR SRAM-based cache partitioned into primary and secondary regions and with each queue assigned a ring buffer in each region.

55. The method of claim 54 wherein each queue may operate in two modes;

a “

combined-cache mode”

wherein data is written and read in a single ring buffer by the corresponding ingress and egress ports, respectively; and

a “

split-cache mode”

wherein one ring buffer functions as an egress-cache, and the other ring buffer operates as an ingress-cache.

56. The method of claim 55 wherein, in the “

combined-cache mode”

, the egress port reads from the head of a queue, and the corresponding ingress port writes to the tail of the queue, with said head and tail contained within a single ring buffer.

57. The method of claim 55 wherein, in the “

split-cache mode”

, said egress-cache is read by the corresponding egress port, and written by a memory controller to transfer blocks of data from the DRAM-based memory, while said ingress-cache is written by the corresponding ingress port and read by the memory controller for block transfers to the DRAM-based memory, with the head and tail of the queue stored in the two separate ring buffers.

58. The method of claim 57 wherein the head of the queue is contained in the egress-cache, and the tail is contained in the ingress-cache, with the intermediate queue data stored in the DRAM-based main memory.

59. The method of claim 55 wherein, upon the advent of an oversubscribed queue resulting in a ring buffer fill-up, the memory controller effects switching the mode of the oversubscribed queue from combined-cache mode operation to the split-cache operation, enabling a second ring buffer to allow the corresponding ingress port to write the next incoming data directly to it in a seamless manner, and similarly upon the advent of an undersubscribed queue resulting in a ring buffer running dry, the memory controller effects switching the mode of the undersubscribed queue from split-cache mode operation to the combined-cache operation, disabling the first ring buffer to allow the corresponding egress port to read data directly from the second ring buffer in a seamless manner.

60. The method of claim 55 wherein the memory controller transfers blocks of data from the ingress-cache to the main memory to prevent the corresponding ring buffer from overflowing, and similarly transferring blocks of data from the main memory to the egress-cache to prevent the corresponding ring buffer from running dry.

61. The method of claim 55 wherein during queue operation in the split-cache mode, the memory controller transfers blocks of data in and out of the DRAM main memory to prevent starving corresponding egress ports and to prevent the corresponding ingress ports from prematurely dropping data.

62. The method of claim 61 wherein there is the providing of TDM algorithms to guarantee fairness between ingress ports competing for block transfers to the main memory for their queues that are operating in split-cache mode, and between the corresponding egress ports competing for block transfers from the main memory, and with regard to worst-case queue scenarios.

63. The method of claim 55 wherein the dynamic use of the cache memory space allows each queue independently to operate in either combined or split-cache mode, providing a seamless switchover therebetween without interruption of service to the ingress and egress ports.

100. The apparatus of claim 51 wherein for J read and J write accesses of size D data bits every T nanoseconds, and a requirement to transmit or receive P data bits every T nanoseconds, a matrix memory organization of (N×

N)/(J/2×

J/2) memory banks is pointed on each of the memory slices, providing a bandwidth of each link of L bits/second divided by the number M of memory slices, where M is defined as P/D.

101. The apparatus of claim 100 wherein the memory organization is variable by changing the number of memory banks on a single memory slice, trading-off additional links and memory slices.

102. The apparatus of claim 100 wherein means is provided for balancing the number of ingress lanes, egress links and memory banks per memory slice to achieve the desired card real estate, backplane connectivity and implementation.

103. The apparatus of claim 100 wherein such balancing is achieved by means for removing rows and respective output ports from the N×

N matrix to reduce the number of memory banks per memory slice, while increasing the number of memory slices and ingress links and maintaining the number of egress links.

104. The apparatus of claim 100 wherein such balancing is achieved by means for removing columns and respective ingress ports from the N×

N matrix to reduce the number of memory banks per memory slice, thereby increasing the number of memory slices and egress links while maintaining the number of ingress links.

131. The method of claim 63 wherein when a queue switches from combined cache mode to split-cache mode, the egress cache is full of data and the ingress cache is empty, which guarantees data for the connected egress port and available storage for the connected ingress port, in regard to the worst-case queue scenarios.

64. Apparatus for non-blocking output-buffered switching of time-successive lines of input data streams along a data path between N input and N output data ports provided with corresponding respective ingress and egress data line cards, and wherein each ingress data port line card receives L bits of data per second of an input data stream to be fed to M memory slices and written to the corresponding memory banks and ultimately read by the corresponding output port egress data line cards, the apparatus having, in combination,

a physically distributed logically shared memory datapath of architecture wherein each line card is associated with a corresponding memory bank, a memory controller and a traffic manager, and wherein each ingress line card is connected to its corresponding memory bank and also to the memory bank of every other line card through an N×

M mesh, providing each input port ingress line card with data write access to all the M memory banks, and wherein each data link provides L/M bits per second path utilization;

a further N×

M mesh connecting the M memory banks to egress line cards of the corresponding output data ports, with each memory bank being connected not only to its corresponding output port but also to every other output port as well, providing each output port egress line card with data read access to all the M memory banks;

means for segmenting each of the successive lines of each input data stream at each ingress data line card into a row of M data segment slices along the line;

means for partitioning data queues for the memory banks into M physically distributed separate column slices of memory data storage locations or spaces, one corresponding to each data segment slice;

means for writing each such data segment slice of a line along the corresponding link of the ingress N×

M mesh into its corresponding memory bank column slice and at the same predetermined corresponding storage location or space address in its respective corresponding memory bank column slice as the other data segment slices of the data line occupy in their respective memory bank column slice, whereby the writing-in and storage of the data line slices occurs in lockstep as a row across the M memory bank column slices; and

means for writing the data segment slices of the next successive data line into their corresponding memory bank column slices at the same queue storage location or space address thereof adjacent the storage location or space row address in that memory bank column slice of the corresponding data segment slice already written in from the preceding input data stream line.

65. The apparatus of claim 64 wherein means is provided for writing the data-slice into memory simultaneously for the slices in each line, and the slice is controlled in size for load-balancing across the memory banks.

66. The apparatus of claim 65 wherein each of the data lines is adjusted to have the same line width.

67. The apparatus of claim 66 wherein, in the event any line lacks sufficient data slices to satisfy this width, means is provided for padding a line with dummy-padding slices sufficient to achieve the same line width and to enable said lockstep storage.

68. The apparatus of claim 64 wherein means is provided for operating the architecture of the distributed lockstep memory bank storage to resemble the operation of a single logical FIFO per data queue of width spanning the M memory banks and with a write bandwidth of L bits/second.

69. The apparatus of claim 64 wherein means is provided for integrating said architecture with a distributed data control path architecture that enables the respective line cards to derive respective data queue pointers for enqueuing and dequeuing functions without a separate control path or centralized scheduler.

70. The apparatus of claim 69 wherein, at the egress side of the distributed data control path, each traffic manager is provided with means for monitoring its own read and write pointers to infer the status of the respective queues, with the lines that comprise the queue spanning the M memory banks.

71. The apparatus of claim 70 wherein the read and write of the data slices is monitored at the corresponding memory controller to permit inferring of line count on the data slice that is current for a particular queue.

72. The apparatus of claim 71 wherein the means for the integrating of the distributed control path with the distributed shared memory architecture enables the traffic managers of the respective egress line cards to provide for quality of service in maintaining data allocations and bit-rate accuracy, and for each of re-distributing unused bandwidth for full output line-rate, and for adaptive bandwidth scaling.

73. The apparatus of claim 64 wherein each queue, though physically distributed, is unified through addressing all the data segment slices of a queue identically across all the M memory bank column slices for the same line.

74. The apparatus of claim 67 wherein the padded data written by the padding means into memory ensure that the state of a queue is identical for all memory slices, with read and write pointers derived from the respective line cards being identical across all the memory slices.

75. The apparatus of claim 74 wherein the ingress side of the distributed control path maintains write pointers for the queues dedicated to that input port, and in the form of an array indexed by queue number.

76. The apparatus of claim 75 wherein means is provided for reading a write pointer from the array based on the queue number and then incremented by the total line count of data transfer, and then written back to the array within a time of minimum data transfer adapted to keep up with L bits/second.

77. The apparatus of claim 64 wherein each output port is provided with a queue per input port per class of service, thereby eliminating any requirement for a queue to have more than L bits/second of write bandwidth, and thereby enabling delivery of ideal quality of service in terms of bandwidth with low latency and jitter.

78. The apparatus of claim 69 wherein the memory bank is partitioned into multiple memory column slices with each memory slice containing all of the columns from each queue and receiving corresponding multiple data streams from different input ports.

79. The apparatus of claim 78 wherein read and write pointers for a single queue are matched across all the M memory slices and corresponding multiple memory column slices, with the multiple data streams being written at the same time and with each of the multiple queues operating independently of one another.

80. The apparatus of claim 79 wherein at the egress ports, means is provided for enabling each memory slice to read up to N data slices, one to each of corresponding output ports during each time-successive output data line, with corresponding multiple data slices, one for each of the multiple queues, being read out to their respective output ports.

81. The apparatus of claim 79 wherein, as the data from the multiple queues is read out of memory, means is provided to supply each output port with the necessary data to maintain line rate on its output.

82. The apparatus of claim 64 wherein, in the non-blocking write data path from the input port into the shared memory bank slices, means is provided for effecting the non-blocking regardless of the input data traffic rate and output port destination, providing a nominal, close to zero, latency on the write path into the shared memory banks.

83. The apparatus of claim 64, wherein in the non-blocking read data path from the shared memory slices to the output ports, means is provided for effecting non-blocking regardless of data traffic queue rates up to L bits/second per port and independent of the input data packet rate.

84. The apparatus of claim 83 wherein means is provided for eliminating contention between the N output ports by providing each output port with equal read access from each memory slice, guaranteeing L/M bits/second from each memory slice for an aggregate bandwidth of L bits/second.

85. The apparatus of claim 71 wherein means for the inferring of the line count on the data slice provides a non-blocking inferred control path that permits the traffic manager at the egress to provide ideal QOS.

86. The apparatus of claim 64 wherein a non-blocking matrix of two-element memory stages for the memory banks is provided to guarantee a non-blocking write path from the N input ports and a non-blocking read path from the N output ports.

87. The apparatus of claim 86 wherein the two-element memory stages are formed of an SRAM memory element enabling temporary data storage therein that builds blocks of data on a per queue basis, and a relatively low speed DRAM memory element for providing primary data packet buffer memory.

88. The apparatus of claim 87 wherein the SRAM element performs a data cache function, always directly accessed by the connected ingress and egress ports but without directly accessing the DRAM element, such that the cache always stores the head of each data queue for the connected egress ports to read from, and the tail of each queue for the connected ingress ports to which to write.

89. The apparatus of claim 88 wherein the SRAM cache is partitioned into queues that correspond to queues maintained in the DRAM memory such that said cache and a memory management controller are seamlessly transferring blocks of data between the SRAM-based cache and the DRAM-based main memory, while guaranteeing the connected egress and ingress ports their respective read and write accesses to the corresponding queues every data transfer interval.

90. The apparatus of claim 89 wherein the cache comprises a QDR SRAM-based cache partitioned into primary and secondary regions and with each queue assigned a ring buffer in each region.

91. The apparatus of claim 90 wherein each queue may operate in two modes;

a “

combined-cache mode”

wherein data is written and read in a single ring buffer by the corresponding ingress and egress ports, respectively; and

a “

split-cache mode”

wherein one ring buffer functions as an egress-cache, and the other ring buffer operates as an ingress-cache.

92. The apparatus of claim 91 wherein, in the “

combined-cache mode”

, the egress port reads from the head of a queue, and the corresponding ingress port writes to the tail of the queue, with said head and tail contained within a single ring buffer.

93. The apparatus of claim 91 wherein, in the “

split-cache mode”

, said egress-cache is read by the corresponding egress port, and written by a memory controller to transfer blocks of data from the DRAM-based memory, while said ingress-cache is written by the corresponding ingress port and read by the memory controller for block transfers to the DRAM-based memory, with the head and tail of the queue stored in the two separate ring buffers.

94. The apparatus of claim 93 wherein the head of the queue is contained in the egress-cache, and the tail is contained in the ingress-cache, with the intermediate queue data stored in the DRAM-based main memory.

95. The apparatus of claim 91 wherein, upon the advent of an oversubscribed queue resulting in a ring buffer fill-up, the memory controller effects switching the mode of the oversubscribed queue from combined-cache mode operation to the split-cache operation, enabling a second ring buffer to allow the corresponding ingress port to write the next incoming data directly to it in a seamless manner, and similarly upon the advent of an undersubscribed queue resulting in a ring buffer running dry, the memory controller effects switching the mode of the undersubscribed queue from split-cache mode operation to the combined-cache operation, disabling the first ring buffer to allow the corresponding egress port to read data directly from the second ring buffer in a seamless manner.

96. The apparatus of claim 91 wherein the memory controller transfers blocks of data from the ingress-cache to the main memory to prevent the corresponding ring buffer from overflowing, and similarly transferring blocks of data from the main memory to the egress-cache to prevent the corresponding ring buffer from running dry.

97. The apparatus of claim 91 wherein during queue operation in the split-cache mode, the memory controller transfers blocks of data in and out of the DRAM main memory to prevent starving corresponding egress ports and to prevent the corresponding ingress ports from prematurely dropping data.

98. The apparatus of claim 97 wherein a TDM algorithm is provided to guarantee fairness between ingress ports competing for block transfers to the main memory for their queues that are operating in split-cache mode, and between the corresponding egress ports competing for block transfers from the main memory, and with regard to worst-case queue scenarios.

99. The apparatus of claim 91 wherein the dynamic use of the cache memory space allows each queue independently to operate in either combined or split-cache mode, providing a seamless switchover therebetween without interruption of service to the ingress and egress ports.

105. The apparatus of claim 67 wherein means is provided to ensure that link bandwidth is not consumed by dummy-padding slices through placing the first data slice of the current incoming data line on the link adjacent to the link used by the last data slice of the previous data line such that the data slices have been rotated within a line.

106. The apparatus of claim 105 wherein a control bit is embedded with the starting data slice to indicate to the egress how to rotate the data slices back to the original order within a line, and a second control bit is embedded with each data slice to indicate if a dummy-padding slice is required for the subsequent line.

107. The apparatus of claim 106 wherein, when a dummy-padding slice is to be written to memory based on the current data slice, means is provided such that said control bit indicates that a dummy-padding slice is required at the subsequent memory slice address with no requirement of increased bandwidth.

108. The apparatus of claim 64 wherein the write pointers reside on the memory slice, insuring that physical addresses are never sent on the N×

M ingress or egress meshes.

109. The apparatus of claim 108 wherein means is provided for generating a minimal queue identifier to be transmitted with each data slice to store the data slice into the appropriate location address in the memory slice, while only referencing the queues of the respective current ingress port.

110. The apparatus of claim 87 wherein, when the two-element memory stage is transferring a relatively slow wide block transfer from the SRAM to the DRAM, means is provided for writing data slices accordingly to the SRAM at a location address based on a minimal queue identifier, permitting address generation to reside on the memory controller and not on the input ports and obviating the need for a high address look-up rate on the controller.

111. The apparatus of claim 110 wherein, when N=M, means is provided whereby said memory controller does not require knowledge of the physical address until said transferring of line data from the SRAM to the DRAM.

112. The apparatus of claim 111 wherein the SRAM is selected as QDR SRAM and the DRAM is selected as a RLDRAM.

113. The apparatus of claim 71 wherein the traffic manager of each egress port derives inferred write pointers by monitoring the memory controller for writing to its own queues based on the current state of the read and write pointers, and derives inferred read pointers by monitoring the memory controller for read operations to its own queues.

114. The apparatus of claim 72 wherein means is provided for integrating the egress traffic manager of each output port into the egress data path through the inferred control architecture, and means for enqueuing data from the corresponding memory slice to the egress traffic manager and scheduling the same while managing the bandwidth, request generation and reading from memory and then updating the corresponding originating input port.

115. The apparatus of claim 114 wherein during said enqueuing of data from each egress traffic manager from its own memory slice, each egress traffic manager infers from the ingress and egress data path activity on its own corresponding memory slice the state of its queues across the memory banks.

116. The apparatus of claim 115 wherein means is provided at the egress traffic manager to monitor an interface to the corresponding memory controller for queue identifiers representing write operations for its queues, and means for counting and accumulating the number of write operations to each of its queues, thereby calculating the corresponding line counts and write pointers.

121. The apparatus of claim 64 wherein, as additional line cards are provided to add to the aggregate memory bandwidth and storage thereof, means is provided for redistributing the data slices equally amongst all memory slices, utilizing the memory bandwidth and storage of the new memory slices, and reducing bandwidth to the active memory slices, thereby freeing up memory bandwidth to accommodate data slices from new line cards, such that the aggregate read and write bandwidth to each memory slice is 2×

L bits/second, when N=M.

122. The apparatus of claim 121 wherein means is provided for reconfiguring the queue size and the physical location and newly added queues with hot swapping facility that supports line cards being removed or inserted without loss of data or disruption of service to data traffic on the active line cards, by the ingress side embedding a control flag with the current data slice, which indicates to the egress side that the ingress side will switch over to a new system configuration at a predetermined address location in the corresponding queue, and to also switch over to the new system configuration when reading from the same address.

123. The apparatus of claim 64 wherein a crosspoint switch is interposed between the links that comprise the N×

M ingress and egress meshes to provide connectivity flexibility.

124. The apparatus of claim 64 wherein a time division multiplexer switch is substituted for the N×

M ingress and egress meshes and interposed between the input and output ports providing programmable connectivity between memory slices on the traffic managers while reducing the number of physical links.

126. The apparatus of claim 64 wherein multicasting is provided through means for dedicating a queue to be written by a single input port and read by 1 to N output ports, thereby enabling N input ports to multicast the incoming data traffic to the N output ports while maintaining the input line rate of L bits/sec, and similarly enabling N output ports to multicast up to the output line rate of L bits/sec.

125. An apparatus for non-blocking output-buffered switching of time-successive lines of input data streams along a data path between N ingress and N egress data ports provided with corresponding respective ingress and egress data line cards, and wherein each ingress data port line card receives L bits of data per second of an input data stream to be fed to M memory slices and written to the corresponding memory banks and ultimately read by the corresponding output port egress data line cards, the apparatus having, in combination, a non-blocking matrix of two-element memory stages for the memory banks to guarantee a non-blocking data write path from the N ingress ports and a non-blocking data read path from the N egress ports, wherein the memory stages comprise a combined SRAM memory element enabling temporary data storage therein that builds blocks of data on a per queue basis, and a relatively low speed DRAM main memory element for providing primary data packet buffer memory.