Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-08-31
2004-03-23
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000
Reexamination Certificate
active
06711170
ABSTRACT:
BACKGROUND OF THE INVENTION
A networking switch receives data packets from a number of ingress ports connected to the switch and provides the data packets to a number of egress ports connected to the switch. The switch determines the egress port to which the data packets are provided dependent on the destination address included in the data packet. A data packet received from an ingress port is stored in memory in the switch before being provided to the egress port.
The memory in the switch may be a common memory, in which all received data packets from all the ingress ports are stored, before being provided to the egress ports. A non-blocking switch allows all data received for all ingress ports to be provided to the egress ports. Non-blocking switches typically include a common memory in order to make the maximum amount of memory available to each of the ports.
The speed of a common memory switch is dependent on the memory bandwidth. The memory bandwidth is dependent on the memory access time, and the width of the memory, that is, the number of bytes accessed per memory access time. For example, if the common memory is 64 bytes wide and has an access time of 80 nanoseconds (ns), it takes 80 ns to write or read 64 bytes. If a ingress port connected to the switch is receiving data at 100 Megabits (M) bits per second, a bit is received every 10 ns, an 8-bit byte is received every 80 ns and 64 bytes are received every 5120 ns. After the 64 bytes of data are received, a write memory cycle is performed to write the 64 bytes in a single memory access to the 64 byte wide memory. The ingress port uses 80 ns of the memory bandwidth every 5120 ns to write the data received to memory; thus, a 64 byte wide memory with an access time of 80 ns can support 64 (5120 ns/80 ns) 100 M bits per second ports. With 64 ports connected to the switch each port cycle is 80 ns. An 80 ns port cycle provides one memory access per port cycle to each of the ports.
Increasing the memory bandwidth available in each port cycle, requires one or more of the following: decreasing the memory access time increasing the width of the memory (i.e. the number of bits read/written per memory cycle) or decreasing the number of ports. Increasing the width of the memory is limited by the minimum data packet size. Decreasing the memory access time is limited by the minimum memory access time for the memory.
Memory bandwidth may also be increased by interleaving memory banks for example, writing the first data packet to a first memory bank and a second data packet to a second data bank. However, interleaving data in a switch may result in blocking for example, if both port A and port B request access to the first memory bank at the same time. Blocking data transfers between the ingress port and the egress port may result in dropped packets; thus, it can not be used to increase memory bandwidth in a nonblocking switch.
SUMMARY OF THE INVENTION
A packet storage manager in a switch increases the memory bandwidth of a memory shared by ingress and egress ports connected to the switch. The packet storage manager performs both a write operation for one of the ingress ports and a read operation for one of the egress ports in a single port cycle where prior systems required successive read and write cycles. The write and read operations are performed concurrently to different memory in the memory in a single memory access cycle. The memory is physically divided into a number of banks. The number of banks is preferably two or four. The read and write operations are performed to different banks.
The packet storage manager includes read address logic, which selects a read address in memory for the read operation dependent on a port cycle, and write address logic which selects a write address for a write operation dependent on the read address selected by the read address logic. The write address selects the write address dependent on the read address, such that the read and write operations can be performed concurrently in a single memory access. The packet storage manager relies on a port queue for each egress port and a free list of addresses not stored in a port queue. From an incoming packet, the manager reads the network destination to determine an appropriate egress port or ports for which the packet is to be stored. The manager writes a packet segment into memory by removing a memory segment address from the free list, storing the segment address at the tail of each port queue to which the packet segment is directed and writing the packet segment to the location in memory specified by the segment address. Simultaneously, an address at the head of each port queue identifies the packet segment to be read by the manager.
The read address logic in the packet storage manager includes a port queue for each of the egress ports. The port queue stores the memory locations of data written to memory by each ingress port. Port queue select logic selects the port queue from which to remove a memory address dependent on the port cycle. Read select logic selects the memory location from which to read dependent on the memory address removed from the port queue.
The memory is physically divided into a number of banks. The number of banks are preferably two or four. The write address logic in the packet storage manager includes a bank free list for each of the banks. Each bank free list stores addresses of available locations in the bank of memory. Write select logic in the write address logic selects one of the bank free lists from which to remove a write address. The write select logic may select a bank free list so that sequential segments of a data packet are written to alternating odd and even banks of memory.
The write address logic may also include a bank free list counter for each bank. The bank free list counter stores a count of the available locations in the bank. The write select logic may select a bank free list dependent on the count in the bank free list counter. The concurrent read and write operations may be for the same port or may be to different ports.
REFERENCES:
patent: 5166674 (1992-11-01), Baum et al.
patent: 5463755 (1995-10-01), Dumarot et al.
patent: 6122274 (2000-09-01), Kumar
patent: 6137807 (2000-10-01), Rusu et al.
patent: 6222840 (2001-04-01), Walker et al.
patent: 0 700 187 (1996-06-01), None
patent: 0 828 403 (1998-11-01), None
Hamilton Brook Smith & Reynolds P.C.
Mosaid Technologies Inc.
Yao Kwang Bin
LandOfFree
Method and apparatus for an interleaved non-blocking packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for an interleaved non-blocking packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for an interleaved non-blocking packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192326