Process for fair and prioritized access to limited output buffers in a multi-port switch
First Claim
1. In a network comprising a plurality of ports interconnected by a shared transmission medium, wherein each port comprises a transmit FIFO buffer containing packets to be transmitted via the transmission medium and a receive FIFO buffer for receiving packets transmitted via the transmission medium, a method for locally determining at each port whether a packet transmitted via the transmission medium and addressed to the port will be accepted into the receive buffer at the port or rejected comprising the steps of:
- maintaining and storing current buffer status information at each port about the current capacity of the receive buffer at the port to receive packets via the transmission medium,determining and storing, under the control of a processor at each port, current packet status information characterizing one or more packets currently waiting at other ports for transmission to the port, said packet status information being determined locally at each port solely from packets which arrive at the port via the shared medium and which are accepted into the receive buffer or rejected,utilizing said processor at each port, locally determining at each port whether to accept or reject a packet currently arriving via the shared transmission medium in response to said buffer status information and said packet status information.
4 Assignments
0 Petitions
Accused Products
Abstract
A process for fairly allocating resources in a multiport packet switch is disclosed. Each port is connected to a station and comprises a transmit FIFO buffer and a receive FIFO buffer. The ports are connected by a broadcast transmission medium. A transmit buffer of a specific port gains access to the transmission medium when the port possesses a token which is passed from port to port in a round-robin fashion. When a port recognizes that a transmitted packet is addressed to it, the port uses a local processor to determine whether or not to accept the packet. The determination is based on (1) information in the packet header, e.g., priority and address of the transmitting port, (2) the status of the receive buffer (full or not), and (3) other locally recorded information regarding past history of the acceptance or rejection of packets from particular ports and of particular priority classes needed to achieve fairness among packets of the same class and priority among different classes. If the receiving port makes a determination to reject a packet, the receiving port issues a busy signal which is transmitted over the broadcast medium. When the transmitting port receives the busy signal, it aborts transmission of the packet and releases the token. If the receiving port decides to accept the packet, the packet is written into the receive buffer of the receiving port.
148 Citations
19 Claims
-
1. In a network comprising a plurality of ports interconnected by a shared transmission medium, wherein each port comprises a transmit FIFO buffer containing packets to be transmitted via the transmission medium and a receive FIFO buffer for receiving packets transmitted via the transmission medium, a method for locally determining at each port whether a packet transmitted via the transmission medium and addressed to the port will be accepted into the receive buffer at the port or rejected comprising the steps of:
-
maintaining and storing current buffer status information at each port about the current capacity of the receive buffer at the port to receive packets via the transmission medium, determining and storing, under the control of a processor at each port, current packet status information characterizing one or more packets currently waiting at other ports for transmission to the port, said packet status information being determined locally at each port solely from packets which arrive at the port via the shared medium and which are accepted into the receive buffer or rejected, utilizing said processor at each port, locally determining at each port whether to accept or reject a packet currently arriving via the shared transmission medium in response to said buffer status information and said packet status information. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. In a port connected to a plurality of other ports via a shared transmission medium and connected to a processing station via a link and comprising a receive buffer for receiving packets of a plurality of priority classes from other ports and for transmitting data of the packets to the processing station, wherein the transmission capacity of the shared medium is greater than the transmission capacity of the link, a method for accepting into the receive buffer or rejecting packets transmitted over the shared medium comprising
storing in a register means at the port buffer status information indicating whether or not the receive buffer is currently full, determining under the control of a processor located at said port packet status information about one or more packets waiting at one or more of said other ports for transmission to said port and storing said status information in said register means, said status information being determined solely from the history of acceptance and rejection of packets arriving at said port from particular other ports and belonging to particular priority classes, determining at said port under the control of said processor whether to accept or reject a packet currently arriving at said port utilizing said information stored in said register means and information contained in the packet header including priority class and transmitting port address.
Specification