Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-09
2004-01-13
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06678277
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital electronic communication, and in particular to packet type communication using ingress buffers and egress buffers.
BACKGROUND OF THE INVENTION
Digital communication, especially computer networks, often have a large number of users sending out many packets in many different directions, at random times. Individual users are also usually limited on the amount of messages they can receive within a given time period. In a packet communication system, a packet can be received from a sender, pass through various interconnections before reaching a receiver, and then the receiver can be busy receiving a different data packet. If the receiver is unable to receive the packet, the packet is dropped or discarded. Upper level protocols will recognize that the packet was not received, and try to resend a packet. This increases the time required for one user to send the message to another user, and unnecessarily increases the activity in a communication system. This discarding of packets does not only occur between absolute end users, but can occur in any network device which has a plurality of inputs communicating with a plurality of outputs.
In order to minimize the resending of packets, to minimize the activity caused by one message, and to maximize the number of messages that can be sent across a communication network, buffers are used to receive packets at random arrival times, and deliver the packets at an average rate. The receivers of the packets are then design to process packets at the average rate.
Unfortunately it is difficult to determine the average rate. Also providing a buffer large enough to handle a worse case scenario may be very expensive and may be underutilize for a majority of the time. Therefore, a buffer size is chosen based on economical considerations. Buffers therefore occasionally will overflow and data packets will be lost.
SUMMARY AND OBJECTS OF THE INVENTION
It is a primary object of the present invention to reduce the increase in communication activity due to overflowing of buffers. The present invention accomplishes this objective by providing a plurality of Buffer Management (BM) modules or chips, which communicate with each other through an interconnect. The BM modules receive packets from other parts of the network or external circuitry. These incoming packets are stored in an ingress pool. Data packets that a BM module receives from the interconnect are stored in an egress pool. The BM module takes the packets from the ingress pool and sends the packet across the interconnect to one of the other BM modules. A BM module receives the packet from the interconnect and stores it in the egress pool. A BM module takes packets from the egress pool and transmits it to another part of the network or associated circuitry.
The ingress pool is divided in a plurality of ingress queues. Each egress pool is divided into a plurality of egress queues, where each egress queue is associated or corresponds to a different part of the computer network or associated circuitry. Each of the ingress queues in each BM module corresponds to one of the egress queues in the remaining BM modules. In particular, each BM module has an ingress queue for each of all of the egress queues in the other BM modules. Therefore the number of ingress queues in a BM module is equal to a number of the egress queues in all of the remaining BM modules.
The BM modules can only remove packets from an egress queue when the associated computer network or circuitry is able to receive the packet. The BM modules include an ingress arbiter to determine when packets can be removed from an ingress queue and transmitted to the interconnect. The ingress arbiter also determines which ingress queue will supply a packet to the interconnect.
In order to more efficiently operate this system, each BM module keeps track of the state of its egress queues. This status information is shared among all of the BM modules, and is read by the ingress arbiter. When the ingress arbiter has an opportunity to send a packet to the interconnect, it selects a packet from one of the ingress queues. The present invention can use many different types of arbitration which select one choice from a plurality of choices. However, the present invention limits the choices to only those ingress queues whose corresponding egress queues are not full. The choices available to the arbiter algorithm therefore change depending on the latest information on the status of the egress queues.
In a preferred embodiment, an ingress array is provided which has a plurality of bits. Each of the bits represent either a blocked or open state of one of the egress queues. An open state of an egress queue indicates that the egress queue is not completely full, and can accept data packets. A blocked state of the egress queue indicates that the egress queue is full and cannot accept any more data packets. This ingress array is transmitted from one BM module to another in a circular sequential manner. When a BM module receives an ingress array, it stores the ingress array in the BM module, and the ingress arbiter consults the stored ingress array each time a packet is to be sent from an ingress queue to the interconnect. The BM module updates the bits in the ingress array which correspond to its own egress queues, and then the ingress array is transmitted to the next BM module. This occurs continuously from BM module to BM module so that the status of the egress queues is continually updated in each of the BM modules.
In a particularly preferred embodiment, the bits of the ingress array are sent sequentially with each of the BM modules substantially receiving and transmitting a portion of the ingress array substantially simultaneously. This reduces the amount of bandwidth needed to communicate egress queue status information and causes the status information to be continually updated in each of the BM modules at a sufficient rate.
Because the ingress arbiter of the present invention bases its packet selection dependent upon egress queue status, the number of discarded packets can be minimized, and the use of the interconnect can be maximized. This provides for a very efficient transfer of data through the system, without requiring excessively large and expensive buffer memories.
REFERENCES:
patent: 5367520 (1994-11-01), Cordell
patent: 5530902 (1996-06-01), McRoberts et al.
patent: 5818842 (1998-10-01), Burwell et al.
patent: 5968167 (1999-10-01), Whittaker et al.
Li, S.; Chen, J.-G; Ansari, N., Fair queuing for input-buffered switches with back pressure, Jun. 22-24, 1998, IEEE International Conference, pp. 252-259.*
Badran, H. F; Mouftah, H. T., Input-Output buffered ATM switches with delayed back pressure mechanisms, Sep. 14-17, 1993, IEEE Canadian Conference Electrical and Computer Engineering, vol. 2, pp. 771-774.*
Iliadis, I.; Denzel, W. E., Performance of packet switches with input and output queuing, Apr. 1990, IEEE CNF, vol. 2, pp. 747-753.
Descoteaux Kenneth Gerard
Siman-Tov Benny
Wils Joris Johannes Maria
3Com Corporation
Jones Prenell
McGlew and Tuttle , P.C.
Pham Chi
LandOfFree
Efficient means to provide back pressure without head of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient means to provide back pressure without head of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient means to provide back pressure without head of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3185834