Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-05-10
2003-07-29
Portka, Gary J (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C370S412000, C370S429000, C710S055000
Reexamination Certificate
active
06601150
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication networks, and, more particularly, to maintaining packet order in a packet processing system in which packets may become available for processing out of order.
BACKGROUND OF THE INVENTION
In today's information age, communication devices, such as computers and computer peripherals, are often internetworked over a data communication network. Within the data communication network, packets of data are processed by a number of interconnected communication controllers, such as Asynchronous Transfer Mode (ATM) communication controllers or Internet routers. A packet received over an ingress interface of the communication controller is routed by the communication controller to an egress interface. Since a typical communication controller supports multiple ingress and egress interfaces, the packet must be processed by a packet processor in order to determine the appropriate egress interface for the packet.
One key differentiator between various communication controllers is packet throughput, which is typically characterized by the number of packets per second that the communication controller can process. The packet throughput of a communication controller is determined by a number of factors, not the least of which is the internal data path architecture of the communication controller. Thus, an internal data path architecture that expedites the processing of packets is valuable, and therefore desirable.
Furthermore, certain data communication network configurations require that the routed packets be forwarded in the same order in which they were received Thus, an internal data path architecture that maintains packet order is valuable, and therefore desirable.
Consequently, an internal data path architecture that expedites the processing of packets while maintaining packet order is valuable, and therefore desirable.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, a memory manager coordinates access to a packet memory so that packets are written into the packet memory in first-in-first-out order, processed by a packet processor in an order-independent fashion, and read from the packet memory in first-in-first-out order.
In accordance with another aspect of the invention, the memory manager maintains a START indicator and a VALID indicator for each memory block in the packet memory. Packets are written in a number of successive memory blocks, and the START indicator corresponding to the first memory block of the number of successive memory blocks is set to indicate that the packet is available for processing. The packets are processed by a packet processor. When the packet processor completes the processing of a particular packet, the VALID indicator corresponding to the first memory block associated with that packet is set to indicate that the packet is ready to be forwarded. The packet may become ready to be It forwarded out of order. However, the packets are forwarded in first-in-first-out order by processing the packets in first-in-first-out order and only forwarding a particular packet if the VALID indicator corresponding to the first memory block associated with that packet is set to indicate that the packet is ready to be forwarded. Thus, a packet is not forwarded unless and until all previous packets have been forwarded, even if the packet is ready to be forwarded before one or more previous packets.
In a preferred embodiment of the present invention, the memory manager is operably coupled to coordinate access to the packet memory by a packet writer, a packet processor, and a packet reader. The memory manager includes status indicator memory including a START indicator and a VALID indicator for each of the plurality of memory blocks in the packet memory, packet writer interface logic operably coupled to set the START indicator corresponding to a first memory block associated with each packet stored in the packet memory by the packet writer, packet processor interface logic operably coupled to set the VALID indicator corresponding to a first memory block associated with each packet stored in the packet memory that is ready to be forwarded by the packet processor, and packet reader interface logic operably coupled to monitor the VALID indicator corresponding to a first memory block associated with a first packet to be forwarded and produce an output signal upon detecting that the VALID indicator is set to indicate that said first packet is ready to be forwarded by the packet reader. The memory manager clears the START and VALID indicators when the end of the packet is read from the packet memory.
REFERENCES:
patent: 5802055 (1998-09-01), Krein et al.
patent: 6067300 (2000-05-01), Baumert
patent: 6101192 (2000-08-01), Wakeland
patent: 6147996 (2000-11-01), Laor et al.
patent: 6282203 (2001-08-01), Yeom et al.
patent: 6295295 (2001-09-01), Wicklund
Angle Richard
Ladwig Geoffrey B.
Scheinbart Marvin
Gorecki John C.
Nortel Networks Limited
Portka Gary J
LandOfFree
Memory management technique for maintaining packet order in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management technique for maintaining packet order in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management technique for maintaining packet order in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056670