Bit clearing mechanism for an empty list

Details Bit clearing mechanism for an empty list Bit clearing mechanism for an empty list

2001-05-22

2004-01-13

Kizou, Hassan (Department: 2667)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S235000, C370S429000, C709S234000

Reexamination Certificate

active

06678278

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to network switches generally and to their apparatus for managing packet memory in particular.
BACKGROUND OF THE INVENTION
A network switch creates a network among a plurality of end nodes, such as workstations, and other network switches connected thereto. Each end node is connected to one port of the network. The ports also serve to connect network switches together.
Each end node sends packets of data to the network switch which the switch then routes either to another of the end nodes connected thereto or to a network switch to which the destination end node is connected. In the latter case, the receiving network switch routes the packet to the destination end node.
Each network switch has to temporarily store the packets of data which it receives from the units (end node or network switch) connected to it while the switch determines how, when and through which port to retransmit the packets. Each packet can be transmitted to only one destination address (a “unicast” packet) or to more than one unit (a “multicast” or “broadcast” packet). For multicast and broadcast packets, tie switch typically stores the packet only once and transmits multiple copies of the packet to some (multicast) or all (broadcast) of its ports. Once the packet has been transmitted to all of its destinations, it can be removed from the memory or written over.
It is common that some ports are more active than others. Thus, some ports receive most of the packets while other ports receive few of the packets. Therefore, the busier ports have longer backlogs than the other ports. To effectively operate, the network switch must actively manage the memory in which the packets are stored, noting which packets are to be shipped to which ports and which portions of memory are currently available. One common method for managing the memory is to provide a fixed buffer per port.
SUMMARY OF THE PRESENT INVENTION
It is an object of the present invention to provide improved apparatus and method for managing the memory in which the incoming packets are stored.
There is therefore provided, in accordance with a preferred embodiment of the present invention, apparatus including an empty list, a storage buffer and apparatus for updating the storage buffer and empty list. The empty list includes a multiplicity of single bit buffers. The storage buffer includes a multiplicity of contiguous buffers, wherein each single bit buffer is associated with one of the contiguous buffers. The state of the bit of a single bit buffer indicates the empty or full state of the associated contiguous buffer and the address of a contiguous buffer is a simple function of the address or number of its associated single bit buffer. The updating apparatus stores data in and removes data from the contiguous buffers and correspondingly updates the states of the associated single bits buffers.
The method of the present invention associates the empty list with the storage buffer such that the address of each contiguous buffer is a simple function of the address or number of its associated single bit buffer and the state of the bit of a single bit buffer indicates the empty or fill state of the associated contiguous buffer. The method also stores data in and removes data from the contiguous buffers and correspondingly updates the states of the associated single bits buffers.
Additionally, in accordance with a preferred embodiment of the present invention, the contiguous buffers are large enough to store at least a packet of data. The contiguous buffers also can store multicast bits which, when set, indicate through which port the data stored in the contiguous buffer has to be transmitted.
Finally, in accordance with a preferred embodiment of the present invention, the memory management unit includes a bit clearing unit which considers a group of single bit buffers at a time. Per group of buffers, the bit clearing unit determines if any bits stored in the group of single bit buffers remain set during a predetermined length period T (the set state of a single bit indicates the full state of the associated contiguous buffer). Alternatively, the bit clearing unit keeps a running sum of the number of single bit buffers that remained set during period T, and compares the running sum to a predetermined threshold of maximum allowed set single bit buffers.


REFERENCES:
patent: 4464713 (1984-08-01), Benhase et al.
patent: 4663706 (1987-05-01), Allen et al.
patent: 4992935 (1991-02-01), Comerford et al.
patent: 4996663 (1991-02-01), Nemes
patent: 5032987 (1991-07-01), Broder et al.
patent: 5043981 (1991-08-01), Firoozmand et al.
patent: 5101348 (1992-03-01), Arrowood et al.
patent: 5129085 (1992-07-01), Yamasaki
patent: 5222064 (1993-06-01), Sagawa
patent: 5241536 (1993-08-01), Grimble et al.
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5287499 (1994-02-01), Nemes
patent: 5412805 (1995-05-01), Jordan, II et al.
patent: 5440552 (1995-08-01), Sugita
patent: 5521913 (1996-05-01), Gridley
patent: 5574944 (1996-11-01), Stager
patent: 5581757 (1996-12-01), Maxey
patent: 5632021 (1997-05-01), Jennings et al.
patent: 5633858 (1997-05-01), Chang et al.
patent: 5634138 (1997-05-01), Ananthan et al.
patent: 5649141 (1997-07-01), Yamazaki
patent: 5668809 (1997-09-01), Rostoker et al.
patent: 5671357 (1997-09-01), Humblet et al.
patent: 5715395 (1998-02-01), Brabson et al.
patent: 5724529 (1998-03-01), Smith et al.
patent: 5734824 (1998-03-01), Choi
patent: 5740468 (1998-04-01), Hirose
patent: 5754791 (1998-05-01), Dahlgren et al.
patent: 5761431 (1998-06-01), Gross et al.
patent: 5764996 (1998-06-01), Armstrong et al.
patent: 5781549 (1998-07-01), Dai
patent: 5784373 (1998-07-01), Satake et al.
patent: 5913042 (1999-06-01), Shemla et al.
patent: 5923660 (1999-07-01), Shemla et al.
patent: 6240065 (2001-05-01), Medina et al.
Dr. Dobb's Journal, “Essential Books on Algorithms and Data Structures”, CD-ROM Library, Section 9.3.1 and 9.3.4, 1995.
Ralston and Reilly, Encyclopedia of Computer Science (Third Edition), pp. 1185-1191, 1995.
Tanenbaum, A.S. ed. “File Systems,” Chapter 5 InOperating Systems: Design and Implementation. Prentice-Hall International, Inc., Englewood Cliffs, NJ, 1987, pp. 302-304.

Affiliated with

Also associated with

Rating

Bit clearing mechanism for an empty list does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bit clearing mechanism for an empty list, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit clearing mechanism for an empty list will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3194691