Prioritized PVC management queues for improved frame processing capabilities

• US 6,144,669 A
• Filed: 12/12/1997
• Issued: 11/07/2000
• Est. Priority Date: 12/12/1997
• Status: Expired due to Term

• Current Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Original Assignee: Newbridge Networks Corporation (Nokia Corporation)
• Inventors: Williams, Stephen J., McEachern, William R., Manary, Troy W.
• Primary Examiner(s): RAO, SEEMA SRINIVAS
• Application Number:
  US08/989,689
• Time in Patent Office: 1,061 Days
• Field of Search: 370/229-231, 370/235-237, 370/248, 370/249, 370/351, 370/395, 370/396, 370/410, 370/412-419, 370/420, 370/400, 370/442-444, 370/465, 370/449, 370/384 , 370/401, 340/825.06, 340/825.07, 340/825.08, 340/825.5, 340/825.51
• US Class Current: 370/401
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/567 Frame Relay over ATM
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

There is provided a method and apparatus for the prioritization, multiple queuing and selective processing of PVC management frames by a Frame Relay message processing device. The device had an input port for receiving the messages. It also provides a number of message queues for storing and retrieving the received messages, each of the queues respectively corresponding to one of a number of response priority levels which vary from highest priority to lowest priority. Each of the response priority levels is assigned to a number of message classes associated with predetermined link management processes for communicating the status of message relay links among networking devices. The message processing device has a first processor for determining the message class associated with each of the received messages and for allocating each of the messages to a corresponding one of the queues based upon the response priority level assigned to the determined message class. A second processor is provided for retrieving each of the messages from the queues, and an output port is provided for dispatching the retrieved messages.

Claims

1. A method for processing link status messages in a networking device operative to communicate with another networking device in accordance with a communications protocol, the link status messages communicating the status of an associated message relay link between said networking devices, a first number of the link status messages each being associated with a predetermined response interval, wherein a failure to respond to a link status message within said predetermined response interval will result in the said associated message relay link being declared inoperative, said method comprising the steps of:

(a) determining whether link status messages received by the device belong to any one of a plurality of predetermined message classes, the message classes being associated with a response priority hierarchy comprised of a plurality of response priority levels which varies progressively from highest priority for a message class comprised of link status messages having relatively short predetermined response intervals to lowest priority for a message class comprised of link status messages having relatively long predetermined response intervals, and wherein each message class is respectively assigned one of said response priority levels of said hierarchy; and

b) storing the link status messages in a memory wherein messages of each said class may be separately retrieved from messages of the other said classes.

2. The method according to claim 1, wherein a second number of link status messages are not associated with any predetermined response interval and wherein a further message class is provided that is comprised of said link status messages having no predetermined response interval, the message class being assigned a response priority level of the hierarchy which is of yet lower priority than the lowest priority for the message class comprised of link status messages having relatively long predetermined response intervals.

3. The method according to claim 2, further comprising the step of retrieving the link status messages stored in said queues in a concurrent round robin manner.

4. The method according to claim 3, wherein the link status messages are retrieved from the queues according to the priority hierarchy, wherein one link status message is retrieved in succession from each queue in the order of the queue associated with said highest priority to the queue associated with said lowest priority.

5. The method according to claim 4, wherein said communications protocol is a Frame Relay standard and said link status messages are PVC management frames.

6. The method according to claim 5, wherein the message classes comprised of link status messages having predetermined response intervals are associated with synchronous link management processes and the message classes comprised of link status messages having no predetermined response interval are associated with asynchronous link management processes.

7. The method according to claim 6, wherein said synchronous link management processes comprise a heartbeat process and a full status process, and wherein said asynchronous link management processes comprise an update process.

8. The method according to claim 2, further comprising the step of retrieving link status messages stored in said queues in an exhaustive round robin manner.

9. The method according to claim 8, wherein the link status messages are retrieved from the queues according to the priority hierarchy, wherein all link status messages are exhaustively retrieved from each queue in succession according to the order of the queue associated with said highest priority to the queue associated with said lowest priority.

10. An apparatus for processing link status messages received from networking devices operative to communicate with each other in accordance with a communications protocol, the link status messages communicating the status of an associated message relay link between said networking devices, a first number of the link status messages each being associated with a predetermined response interval, wherein a failure to respond to a link status message within said predetermined response interval will result in the said associated message relay link being declared inoperative, the apparatus comprising:

(a) a first input port for receiving said link status messages;

(b) two message queues for storing and retrieving said received link status messages, each of said queues respectively corresponding to one of two response priority levels representing a highest priority and a lowest priority, each of the response priority levels being assigned to one of two messages classes;

the first message class being associated with link status messages having relatively short predetermined response intervals and the second message class being associated with link status messages having relatively long predetermined response intervals, and wherein said highest priority is assigned to said first message class and said lowest priority is assigned to said second message class;

(c) a first processor for determining the message class associated with each of said received link status messages, and for allocating each of said link status messages to a corresponding one of said queues based upon the response priority level assigned to said determined message class;

(d) a second processor for retrieving each of said link status messages from said queues; and

(e) a first output port for dispatching said retrieved link status messages.

11. The apparatus according to claim 10, wherein a second number of link status messages are not associated with any response interval and comprise a third message class, and wherein a third message queue is provided for storing and retrieving said received link status messages of said third message class, the third message queue corresponding to a third response priority level which represents a yet lower priority than the lowest priority of said two response priority levels.

12. The apparatus according to claim 11, wherein said message queues are first-in first-out queues, each queue having a head and a tail thereof, said received link status messages being stored at the tail of said queues and being retrieved at the head of said queues.

13. The apparatus according to claim 12, wherein said second processor retrieves link status messages stored in the queues in a concurrent round robin manner.

14. The apparatus according to claim 13, wherein the link status messages are retrieved from the queues one link status message successively from each queue in the order of the queue corresponding to said highest priority to the queue corresponding to said lowest priority.

15. The apparatus according to claim 12, wherein said second processor retrieves link status messages stored in the queues in an exhaustive round robin manner.

16. The apparatus according to claim 15, wherein the link status messages are retrieved from the queues with all link status messages being exhaustively retrieved from each queue in succession according to the order of the queue corresponding to said highest priority to the queue corresponding to said lowest priority.

17. The apparatus according to claim 16, wherein said communications protocol is a Frame Relay standard and said link status messages are PVC management frames.

18. The apparatus according to claim 17, wherein the message classes comprised of link status messages having predetermined response intervals are associated with synchronous link management processes and the message classes comprised of link status messages having no response interval are associated with asynchronous link management processes.

19. The apparatus according to claim 18, wherein said synchronous link management processes comprise a heartbeat process and a full status process, and wherein said asynchronous link management processes comprise an update process.

20. The apparatus according to claim 19, further comprising a multiport memory for locating said queues, said memory being shared by each of said first and second processors.

21. The apparatus according to claim 20, wherein the apparatus is an interworking device which is operative to receive PVC management frames both from a Frame Relay environment and from an ATM environment, the apparatus further comprising a second input port for receiving said frames and a second output port for dispatching said frames, the first and second input ports being dedicated respectively to receive said frames from said Frame Relay environment and from said ATM environment, the first and second output ports being dedicated respectively to dispatch said frames to said Frame Relay environment and to said ATM environment, the first processor determining said message class for frames received from each of said input ports, the second processor respectively dispatching frames generated in reply to said received frames to said first output port if said received frames were received by the interworking device from said Frame Relay environment and to said second output port if said received frames were received by the interworking device from said ATM environment.

22. A method for processing link status messages in a networking device operative to communicate with another networking device in accordance with a communications protocol, the link status messages communicating the status of an associated message relay link between said networking devices, a first number of the link status messages each being associated with a predetermined response interval, wherein a failure to respond to a link status message within said predetermined response interval will result in the said associated message relay link being declared inoperative, a second number of the link status messages each not being associated with any predetermined response interval, said method comprising the steps of:

(a) determining whether link status messages received by the device belong to any one of at least two message classes, the message classes each being associated with a corresponding priority level within a priority hierarchy which varies from highest priority to lowest priority, wherein the link status messages which are not associated with any response priority interval are assigned to the message class associated with the priority level of lowest priority; and

(b) storing the link status messages in a memory wherein link status messages of each said class may be separately retrieved from link status messages of the other said classes.

23. An apparatus for receiving, processing and replying to PVC management frames associated with a Frame Relay protocol environment and an ATM protocol environment, the apparatus comprising:

(a) a first input port for receiving the PVC management frames from the Frame Relay protocol environment;

(b) a second input port for receiving the PVC management frames from the ATM protocol environment;

(c) first and second message queues for storing and retrieving PVC management frames received from the Frame Relay protocol environment and the ATM protocol environment, the first and second message queues respectively corresponding to first and second response priority levels, the first priority level having highest priority and the second priority level having lowest priority, each of the response priority levels being respectively assigned to first and second message classes, said highest priority being assigned to the first message class and said lowest priority being assigned to the second message class, the first message class being associated with status enquiry frames and status frames received from the Frame Relay protocol environment, the second message class being associated with status enquiry frames and status frames received from the ATM protocol environment and with async/update frames received from the Frame Relay and ATM protocol environments;

(d) a first processor for determining whether each received PVC management frame belongs to the first message class or the second message class, and for allocating each PVC management frame to the first queue if it belongs to the first message class and to the second queue if it belongs to the second message class;

(e) a second processor for retrieving each PVC management frame from the queues in a concurrent round robin manner and for generating a reply thereto in the form of a response PVC management frame;

(f) a first output port for dispatching said response PVC management frame to the Frame Relay protocol environment if the response PVC management frame is generated in reply to a received PVC management frame associated with the Frame Relay protocol environment; and

(g) a second output port for dispatching said response PVC management frame to the ATM protocol environment if the response PVC management frame is generated in reply to a received PVC management frame associated with the ATM protocol environment.