Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1996-02-27
2001-03-13
Olms, Douglas W. (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S415000, C370S429000
Reexamination Certificate
active
06201807
ABSTRACT:
TECHNICAL FIELD
This invention relates to communications, networking and microprocessors.
BACKGROUND OF THE INVENTION
Modern day data communications is accomplished by transferring bits (0's and 1's) between two communicating devices. These bits are usually segmented into units called packets and routed through a communications network. The packets are routed through the network by switching devices (queue servers), which process the packets and send them along different communications pathways to their final destination.
Packets often line up at a queue server waiting to be serviced by the queue server in the same way that a line at a bank might develop in front of a teller. The line is referred to as a queue. The packets would be the people in the queue and the teller would be the switch or queue server. However not all packets are the same size. Often a shorter packet that could be quickly processed by the queue server waits in the queue while a longer packet is serviced. As a result, the communicating parties at the end are delayed until a large packet that has nothing to do with their particular communication, is processed. Ultimately many different parties that are communicating through the switch (or queue server) would be slowed down, while the queue server processes a large packet that has nothing to do with their respective communications sessions.
It would be advantageous to service smaller length packets, located behind larger packets in the queue, without waiting for the large packets to be fully processed. Attempts have been made to design simple architectures that solve this queuing problem. Software scheduling techniques have been devised which increase the equity in processing the packets by examining the entire queue of packets. However, it is difficult to devise a high-speed and memory-efficient hardware implementation of this method, as needed by Asynchronous Transfer Mode (ATM) switches, or high speed queue servers. At least one fast implementation was attempted in an ATM switch. However, the method required complex manipulations of the pointers that identified the different packets. As a result, these methods required multiple read and write commands to the memory of the switch, which in turn help to make method slow to implement. Therefore, it would be advantageous to develop a simple hardware technique for reducing queuing delays that could be performed in Real-Time.
SUMMARY OF THE INVENTION
A simple method and apparatus for reducing Real-Time queuing delays, in a queue server is presented. The disclosed method, enables high-speed Real-Time processing of a queue. For example, the present invention, requires only a single read/write command to memory per system cycle, enabling queue processing speeds of 100 Mega hertz and above. In the present invention, a queue of packets is presented at a queue server (e.g, a network switch). The queue server takes the queue into available memory space for processing. A true head pointer (a pointer that points to the first packet in the queue) points to the beginning of the queue, the pointer is stored in a true head register (a register that records the location of the beginning of the queue). The queue server starts to process the queue while a pseudo pointer (a pointer that moves down the queue and points to a short packet in the queue and which is stored in a pseudo head register) searches through the queue for small packets. When a small packet is found the pseudo pointer stops moving down the queue. A processing counter is incremented with each processing cycle (an amount of time for processing, e.g. one clock cycle of an ATM queue server) of the queue. When a threshold value of the counter is reached, if the long packet has not been completely processed, the location in the long packet is stored in a register or a memory location in the system. The short packet is then processed to completion, after which processing of the long packet resumes at the location where processing of the long packet stopped. Once processing of the long packet is completed the next packet in the queue is processed.
REFERENCES:
patent: 4872159 (1989-10-01), Hemmady et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5233606 (1993-08-01), Pashan et al.
patent: 5319753 (1994-06-01), MacKenna et al.
patent: 5528587 (1996-06-01), Galand et al.
patent: 5535201 (1996-07-01), Zheng
patent: 5742600 (1998-04-01), Nishihara
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5768273 (1998-06-01), Aznar et al.
patent: 5850395 (1998-12-01), Hauser et al.
patent: 5872769 (1999-02-01), Caldara et al.
patent: 5892762 (1999-04-01), Okuda et al.
Lucent Technologies
Olms Douglas W.
Sam Phirin
LandOfFree
Real-time hardware method and apparatus for reducing queue... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time hardware method and apparatus for reducing queue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time hardware method and apparatus for reducing queue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2454817