Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-26
2004-04-20
Nguyen, Steven H. D (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S429000
Reexamination Certificate
active
06724768
ABSTRACT:
TECHNICAL FIELD
The present invention relates to forwarding of communications packets by a network multiplexer between separate communications network media coupled through the network multiplexer, and, in particular, to a method and system for guaranteeing maximum communications packet transit delays during communications packet forwarding by the network multiplexer.
BACKGROUND OF THE INVENTION
Bridges, switches, and routers are all examples of network multiplexers. A network multiplexer forwards communications packets received from one communications network medium via a network multiplexer port to one or more destination communications media via one or more destination network multiplexer ports. Communications packets received by a network multiplexer are stored in memory of the network multiplexer and then forwarded to the destination ports. Message descriptors referencing the stored communications packet are placed into a transmit queue associated with each destination port. Many networking hardware and protocol standards, such as ethernet, require that a communications packet received by a network multiplexer be transmitted by the network multiplexer within some maximum transit delay period. In the case of the ethernet, the maximum transit delay is four seconds, but transit delays of not more than one second are recommended.
A problem in network multiplexers is that transmit queues can back up due to delays in transmitting queued packets by the transceiver associated with a port. For example, in the ethernet environment, a transmitter is required to wait for periods of increasing lengths following detection of packet collisions on the ethernet. It is often the case that the transceiver of a port associated with the transmit queue, following a back off or other transmission delay, cannot possibly transmit the remaining queued packets on the transmit queue within the maximum allowable transit delay for the most recently queued communications packets. Therefore, a method is required for identifying and discarding such stale packets from transmit queues. Currently-available methods include time stamps and local transmit timers within ports, but the former method may be expensive in terms of memory usage, and the latter method is unreliable. Therefore, network multiplexer designers, architects, and manufacturers have recognized the need for a memory-efficient and reliable method for ensuring that communications packets that cannot be forwarded in sufficient time to meet the maximum transmit delays are discarded.
SUMMARY OF THE INVENTION
The present invention provides a method and system for recognizing communications packets within a network multiplexer that cannot be forwarded to an appropriate network medium within a specified maximum transit delay time, so that these stale communications packets may be subsequently discarded. In the method and system of the present invention, a single flag bit is included in each message descriptor or queue entry in a transmit queue. When a message descriptor is initially placed into the queue, the flag bit is initially set to zero. A global system clock periodically awakens a transmit queue monitoring function that examines each entry queue in each transmit queue, setting each flag bit having the value “0” to “1” and discarding each queue entry, or message descriptor, having a flag bit already set to “1.” By this method, communications packets are not transmitted by the network multiplexer when they cannot reach their intended destination within a maximum transmit delay specified for the network medium through which the sending device is connected. By using only a single bit per queue entry, very little memory is used to implement the present invention.
REFERENCES:
patent: 5751951 (1998-05-01), Osborne et al.
patent: 5951706 (1999-09-01), Benner
patent: 5996019 (1999-11-01), Hauser et al.
patent: 6031842 (2000-02-01), Trevitt et al.
patent: 6144640 (2000-11-01), Simpson et al.
patent: 6256315 (2001-07-01), Barbas et al.
patent: 6292490 (2001-09-01), Gratacap et al.
patent: 6405258 (2002-06-01), Erimli et al.
patent: 6556579 (2003-04-01), Lindeborg et al.
Duong Duc
Hewlett--Packard Development Company, L.P.
Nguyen Steven H. D
LandOfFree
Method and system for enforcing maximum transit delay 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 Method and system for enforcing maximum transit delay in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for enforcing maximum transit delay in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239581