Method and apparatus for coordinating access to an output of a routing device in a packet switching network

• US 5,892,766 A
• Filed: 02/22/1996
• Issued: 04/06/1999
• Est. Priority Date: 02/22/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Wicki, Thomas Martin, Larson, Jeffrey Dale, Mu, Albert
• Primary Examiner(s): VU, HUY DUY
• Application Number:
  US08/603,880
• Time in Patent Office: 1,139 Days
• Field of Search: 370/413, 370/414, 370/416, 370/418, 370/235, 370/236, 370/429, 370/428, 370/400, 370/401, 370/230, 370/252, 395/200.63, 395/200.64, 395/200.68, 395/877, 340/825.5, 340/825.51
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Arbitration apparatus and method coordinate access to an output of a routing device in a packet switching network. Access to the output is granted to requests having the highest priority in a current arbitration cycle. For requests having the same priority, access is granted to the first of such requests received. Before granting a request, the arbitration apparatus ensures a receiving input buffer has sufficient space for a data packet, as well as any higher priority traffic.

Claims

1. A method for coordinating access to an output of a first routing device in a packet switching network, wherein a data packet granted access to the output is transmitted to a receiving input buffer of a second routing device, the method comprising the steps of:

receiving at least one request from a data packet to access the output;

selecting a request, the request having a priority level;

receiving an indication of the capacity of the receiving input buffer;

determining from the capacity of the receiving input buffer a minimum priority level the selected request must have to be granted;

determining whether the priority level of the selected request is at least as high as the minimum priority level;

in response to determining that the priority level of the selected request is at least as high as the minimum priority level, granting the selected request; and

in response to determining that the priority level of the selected request is not as high as the minimum priority level, not granting the selected request.

10. The method of claim 1, wherein, in response to the input buffer having capacity to receive only one data packet, the minimum priority level is determined to be the highest priority level which can be assigned to a data packet.

2. An apparatus for coordinating access to an output of a first routing device in a packet switching network, wherein a data packet granted access to the output is transmitted to a receiving input buffer of a second routing device, the apparatus comprising:

a memory device for receiving and storing a request to access the output; and

a controller coupled to the memory device and configured to select a request to be granted, the selected request having a priority level;

receive an indication of a minimum priority level the selected request must have to be granted;

determine whether the priority level of the selected request is at least as high as the minimum priority level; and

grant the selected request in response to the priority level of the selected request being at least as high as the minimum priority level.

3. The apparatus of claim 2, wherein a data packet granted access to the output is transmitted to a receiving input buffer in a second routing device and wherein the minimum priority level is a number of priority levels lower than a highest priority level, the number of priority levels lower being equal to one less than a maximum number of data packets the receiving input buffer has capacity to receive.

4. A method for coordinating access to an output of a routing device in a packet switching network, the method comprising the steps of:

receiving at least one request from a data packet to access the output;

selecting a request to be granted, the selected request having a priority level;

receiving an indication of a minimum priority level the selected request must have to be granted;

determining whether the priority level of the selected request is at least as high as the minimum priority level; and

granting the selected request in response to the priority level of the selected request being at least as high as the minimum priority level.

5. The method of claim 4, wherein a data packet granted access to the output is transmitted to a receiving input buffer in a second routing device and wherein the minimum priority level is a number of priority levels lower than a highest priority level, the number of priority levels lower being equal to one less than a maximum number of data packets the receiving input buffer has capacity to receive.

6. A method for coordinating access to an output of a routing device in a packet switching network, wherein the routing device includes a flow control receiver unit and an arbiter and wherein a data packet granted access to the output is transmitted to a receiving input buffer in a second routing device having a flow control transmitter unit, the method comprising the steps of:

receiving at the arbiter at least one request from a data packet to access the output;

selecting at the arbiter a request to be granted, the request having a priority level;

determining at the flow control transmitter unit a maximum number of data packets the receiving input buffer has capacity to receive;

transmitting a first signal from the flow control transmitter unit to the flow control receiver unit, the first signal indicative of the maximum number of data packets the receiving input buffer has capacity to receive;

receiving the first signal at the flow control receiver unit;

in response to receiving the first signal and in response to the first signal indicating that the receiving input buffer has capacity to receive at least one data packet, generating at the flow control receiver unit a second signal indicating a minimum priority level required for a request to be granted;

sending the second signal from the flow control receiver unit to the arbiter;

in response to receiving the second signal, determining whether the priority of the selected request is at least as high as the minimum priority level required for a request to be granted; and

in response to determining that the priority of the selected request is at least as high as the minimum priority level required for a request to be granted, granting the request.

7. The method of claim 6, wherein the minimum priority level is a number of priority levels lower than a highest priority level, the number of priority levels lower being equal to one less than the maximum number of data packet the receiving input buffer has capacity to receive.

8. A routing device for routing data packets through a packet switching network, the routing device comprising:

an arbiter coupled to an output of the routing device, for receiving at least one request to access the output and for selecting a request to be granted access to the output;

a flow control receiver unit coupled to the arbiter for receiving an indication of the capacity of a destination routing device and for sending to the arbiter an indication, based on the capacity of the destination routing device, of a minimum priority level the request must have to be granted;

a receiving input buffer coupled to the output and an input of the routing device, for receiving a data packet; and

a flow control transmitter unit coupled to the receiving input buffer, for generating a signal indicative of a number of data packets the receiving input buffer has capacity to receive.

9. A method for coordinating access to an output of a routing devices with an arbiter having a plurality of memory devices and a controller, the method comprising the steps of:

receiving at least one request to access the output at one of the plurality of memory devices;

in response to receiving at least one request, storing information in each of the plurality of memory devices, the information in each of the plurality of memory devices receiving a request being an indication that a request has been received and the information in each of the plurality of memory devices not receiving a request being an indication that a request has not been received;

receiving the information stored in each of the plurality of memory devices at the controller, the information being received at the controller in an order stored by the plurality of memory devices and all information stored concurrently by the plurality of memory devices being received concurrently at the controller; and

selecting a request to be granted at the controller from the received information.