Electrical computers and digital processing systems: multicomput – Multicomputer data transferring via shared memory
Reexamination Certificate
1998-10-05
2001-05-08
Vu, Viet D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Multicomputer data transferring via shared memory
C709S232000, C709S238000
Reexamination Certificate
active
06230191
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to switching devices for networks such as local area networks (LANs) and, more particularly to a method regulating the amount of buffer memory each port will consume in a shared memory switching device.
BACKGROUND OF THE INVENTION
A local area network (LAN) is a system for directly connecting multiple computers so that they can directly exchange information with each other. LANs are considered local because they are designed to connect computers over a small area, such as an office, a building, or a small campus. LANs are considered systems because they are made up of several components, such as cables, repeaters, switches, routers, network interfaces, nodes (computers), and communication protocols. Ethernet is one such protocol. Information is communicated through a LAN in frames transported within data packets. (“Frame” and “data packet,” while technically different, are often used interchangeably to describe data carrying the information.)
A LAN switch (or, more generally, a packet switch) is generally defined as a multi-port device that transfers data between its different ports based on the destination addresses and/or other information found in the individual packets it receives. Switches can be used to segment LANs, connect different LANs, or extend the collision diameter of LANs. Switches are of particular importance to Ethernet-based LANs because of their ability to increase network diameter. Additional background information on packet switches can be found in a number of references such as
Fast Ethernet
(1997) by L. Quinn et al.,
Computer Networks
(3rd Ed. 1996) by A. Tannenbaum, and
High
-
Speed Networking with LAN Switches
(1997) by G. Held, all of which are incorporated herein by reference.
There are three common switching architectures used in packet switches for forwarding frames from one port to another: crosspoint (also known as crossbar) matrix, shared bus, and shared memory. A crossbar matrix essentially creates a very transient “circuit” between ports for the duration of a frame (or subset of a frame) exchange. There is an electronic switch located at each crossbar in the matrix between every matrix input and output. A switch controller establishes a direct connection within the switch between two ports, based on the destination address and/or other information within a data packet acquired by the packet's entry port. The packet is then forwarded directly from the entry port (also referred to as the sending port) to an exit port (also referred to as a destination port).
A shared-bus architecture uses a common bus as the exchange mechanism for data packets between ports. Each port (or small group of ports) has its own memory, both for input and output queues, depending on the design.
A shared memory architecture uses a single common buffer memory as the exchange mechanism for frames between ports. All ports access the shared memory via a shared memory bus. An arbitration mechanism, such as time division multiplexing, controls port access to the memory, assuring each entry port a chance to store data that it receives within memory where the exit port can then access it. The buffer memory temporarily stores data packets while routing decisions and re-transmission takes place. Typically, buffer memory is allocated to each port on an as-needed basis from a central pool of buffers, with each allocated buffer returning to the pool when it is no longer needed.
Normal network traffic flow into each port of a switch, however, is bursty in nature, requiring significant amounts of buffer memory for short periods of time but requiring little or no memory at other times. This characteristic makes it desirable to allow any switch port to acquire as much available shared memory as needed. But an unmanaged “take all you need,” or “first come, first served” memory allocation scheme can lead to unregulated overflow of memory usage. This scheme can result in sporadic discards or chaotic generation of flow control messages on several branches of the network as incoming traffic has nowhere to be stored.
An objective of the invention, therefore, is to flow control or discard incoming traffic on only those ports that are consuming excessive amounts of buffer memory and leave unaffected the traffic flow between non-offending ports. More particularly, an objective of the invention is to provide a simple, cost-effective method for regulating the buffer memory requested by a port in a shared memory switching device.
SUMMARY OF THE INVENTION
A method of regulating buffer memory in accordance with the invention includes determining a limit number of buffers that a port may use from the number of available buffers in memory and the number of buffers in memory currently in use by the port. The limit number and number of buffers in memory currently in use by the port are then compared, and the comparison is used to determine whether a buffer request by the port will be granted.
In one aspect of the invention, determining the limit number may include combining the number of available buffers in memory, the number of buffers in memory currently in use by the port, and a port allocation factor to obtain the limit number of buffers. In another aspect of the invention, the combining step comprises adding the number of available buffers in memory with the number of buffers in memory currently in use by the port to obtain a sum and applying the port allocation factor to the sum such as by multiplying the two together.
Other aspects of the invention include the following. The comparison may be used to prevent the buffer request if the number of buffers currently in use by the port is greater than or equal to the limit number. The port allocation factor may be independently set for each port. The steps of the method may be repeated periodically. The steps of the method may be taken concurrently by multiple ports.
Apparatus within a switching device that practices the method in accordance with the invention is also disclosed. The apparatus may be located within each port to allow the ports to self-regulate their buffer requests.
The invention may be used to regulate the maximum amount of buffer memory that any port in a shared memory switching device may be allocated. An upper limit is derived with the method of the invention for buffering incoming traffic, beyond which the port initiates flow control or discards the incoming traffic. The allocation factor provides a means to give certain ports access to more memory than others, thereby giving these ports higher significance over other ports and reducing the likelihood that their incoming traffic will be interrupted because of a lack of buffer memory.
Other features and advantages of the invention will become apparent from the following description of an illustrative embodiment and the accompanying drawings.
REFERENCES:
patent: 5438567 (1995-08-01), Ikeda
patent: 5812525 (1998-09-01), Teraslinna
patent: 5838681 (1998-11-01), Bonomi et al.
patent: 5838922 (1998-11-01), Galand et al.
patent: 6009078 (1999-12-01), Sato
patent: 6021132 (2000-02-01), Muller et al.
“Switching Basics,”High-Speed Networking with LAN Switches, by Gilbert Held, chapter 2, pp. 33-61 (1997).
“Frame Switching, Routing, and Protocols,”Fast Ethernet, by Liam B. Quinn and Richard G. Russell, chapter 7, pp. 109-147 (1997).
“Switched Ethernet and Fast Ethernet Standards,”Switched and Fast Ethernet: How It Works and How to Use It, by Robert Breyer and Sean Riley, chapter 3, pp. 41-78 (1995).
Alcatel Internetworking (PE), Inc.
Alcatel Internetworking, Inc.
Reader Scot A.
Vu Viet D.
LandOfFree
Method and apparatus for regulating the amount of buffer... 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 apparatus for regulating the amount of buffer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for regulating the amount of buffer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476292