Ring interface and ring network bus flow control system

• US 6,496,516 B1
• Filed: 12/07/1998
• Issued: 12/17/2002
• Est. Priority Date: 12/07/1998
• Status: Expired due to Term

• Current Assignee: Pmc-Sierra Limited (Microchip Technology Incorporated)
• Original Assignee: Pmc-Sierra Limited (Microchip Technology Incorporated)
• Inventors: Radhakrishnan, Sivakumar, Dabecki, Stephen
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Sam, Phirin
• Application Number:
  US09/206,697
• Time in Patent Office: 1,471 Days
• Field of Search: 370/460, 370/395.71, 370/401, 370/406, 370/412, 370/413, 370/415, 370/417, 370/419, 370/420, 370/424, 370/428, 370/447, 370/452, 370/459, 370/461, 370/462, 370/497
• US Class Current: 370/460
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank

Abstract

A ring interface is coupled to a current node in a ring network having a plurality of nodes and corresponding ring interface for each of said nodes. The ring interface includes a ring input port operative to conduct upstream message packets from a previous node to the ring interface, a ring output port operative to conduct message packets to a next node of the ring network, and a bypass queue operative to buffer message packets. A receive queue buffers message packets before passing them on to the current node. An address filter is coupled to the ring input port to receive the upstream message packets, read their destination addresses and pass them to the bypass queue if the addresses correspond to another node and pass them to the receive queue if their addresses are that of the current node. A transmit queue buffers message packets from the current node and a bypass-transmit queue arbiter is coupled to outputs of the bypass queue and the transmit queue and is operative to select message packets from one of the bypass queue and the transmit queue in accordance with predetermined selection criterion and transmits the selected message packets to the ring output port.

Claims

1. A communications network controller, for use as a node of a packet-based unidirectional ring network having a plurality of. nodes, comprising:

(a) a ring input port operative to conduct received message packets and control characters from a previous upstream node to said controller;

(b) a ring output port operative to conduct transmitted message packets and control characters to a next downstream node of said controller;

(c) a bypass queue operative to buffer message packets being passed from said ring input port to said ring output port;

(d) a receive queue operative to buffer message packets being passed from said ring input port to said controller;

(e) an address filter coupled to said ring input port, said receive queue and said bypass queue, and operative to read the destination addresses of message packets received from said ring input port and passing said message packets to said bypass queue if said message packets are not destined for said controller and passing said message packets to said receive queue if said message packets are destined for said controller;

(f) a transmit queue operative to buffer message packets to be sent to said ring output port by said controller;

(g) a queue arbiter coupled to said bypass queue, said ring output port and said transmit queue and operative to select message packets from one of said bypass queue and said transmit queue for transfer to said ring output port in accordance with predetermined selection criterion;

(h) DATA characters that are transmitted on said ring output port, operative to carry message data to be sent, and received from said ring input port, operative to carry message data to be received;

(i) IDLE and BUSY control characters that transmitted on said ring outputs port and received from said ring input port, operative to indicate flow control status of said ring network; and

(j) a flow state manipulator coupled to said queue arbiter and operative to process said IDLE and BUSY control characters received from said ring input port, determine said flow control status of said ring network, communicate said flow control status to said queue arbiter and generate said IDLE and BUSY control characters to be transmitted on said ring output port,

wherein said flow state manipulator;

causes (NOT BUSY,IDLE), (NOT BUSY,DATA), (BUSY,IDLE) and (BUSY,DATA) symbol pairs corresponding to (node has no data to transmit and is not attempting to flow control an upstream node), (node is beginning a transmitted message and is not attempting to flow control an upstream node), (node is not currently transmitting but is attempting to flow control an upstream node) and (node is beginning a transmitted message and is attempting to flow control an upstream node), respectively, and

interprets (NOT BUSY,IDLE), (NOT BUSY,DATA), (BUSY,IDLE) and (BUSY,DATA) symbol pairs as (node has no data to transmit and is not attempting to flow control an upstream node), (node is beginning a transmitted message and is not attempting to flow control an upstream node), (node is not currently transmitting but is attempting to flow control an upstream node) and (node is beginning a transmitted message and is attempting to flow control an upstream node), respectively.

2. A controller according to claim 1, wherein said DATA, BUSY and IDLE characters are encoded using an 8B/10B code.

3. A controller according to claim 1, wherein said DATA, BUSY and IDLE characters are encoded in the form of binary-coded symbols with a delimiter signal being used to distinguish between said DATA, BUSY and IDLE characters.

4. A controller according to claim 3, wherein if said transmit queue is disabled from transmitting but has message packets to transmit, and said bypass queue is empty, said bypass queue bursts through “

b”

packets with a BUSY delimiter continuously and then sends a NOT BUSY symbol.

5. A controller according to claim 1, wherein a node with a message at a head of its transmission queue that has waited a flow control initiate time T without an opportunity to be transmitted may send a (BUSY,IDLE) or (BUSY,DATA) symbol pair and, in response to receiving a (BUSY,IDLE) or (BUSY,DATA) symbol pair, each of said other nodes in said ring network cease transmission.

6. A controller according to claim 1, wherein in response to said bypass queue being empty, said queue arbiter does one of transmit no message packets and transmit a message packet from said transmit queue in accordance with an arbitration algorithm.

7. A controller according to claim 1, wherein in response to said bypass queue not being empty, said queue arbiter does one of transmit bypass message packets from said bypass message queue and transmit message packets from said transmit queue.

8. A controller according to claim 1, wherein BUSY symbols are sent downstream through with message packets from said bypass queue in response to said controller being in a flow control state to relay flow control on information downstream and prevent downstream nodes from transmitting.

9. A controller according to claim 1, wherein said transmit queue is disabled in response to a NOT BUSY symbol being received at said ring input port.

10. A controller according to claim 1, wherein said controller is reset to a flow control off state in response to said ring input port receiving a NOT BUSY symbol.

11. A controller according to claim 1, wherein said transmit queue is permitted to transmit upon a number of message packets in said bypass queue falling below a predetermined threshold but said transmit queue is disabled upon the number of message packets in said bypass queue reaching a predetermined threshold.

12. A controller according to claim 1, including an adaptive priority queue servicer/controller which dynamically adjusts the bandwidth allocation between said bypass queue and said transit queue based on a number of message packets in said bypass queue and congestion in said ring network.

13. A controller according to claim 12, wherein said priority queue servicer/controller allocates output bandwidth based on a set of pre-programmed weights.

14. A controller according to claim 13, wherein a pre-programmed weight of said transmit queue increases as a number of message packets in said bypass queue decreases and said priority queue servicer/controller is disabled upon a number of message packets in said bypass queue reaching a pre-established threshold.

15. A controller according to claim 13, wherein discrete weights are applied when the number of message packets stored in said bypass queue fall within discrete ranges and then the number of message packets reaches an upper limit and falls below a lower limit said priority queue servicer/controlled is disabled.

16. A controller according to claim 13, wherein the weight is increased and decreased in a non-linear fashion.