Packet messaging method and apparatus

• US 7,310,339 B1
• Filed: 03/24/2000
• Issued: 12/18/2007
• Est. Priority Date: 03/31/1999
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Powers, Simon Julian, Hinds, Michael R
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): NG, CHRISTINE Y
• Application Number:
  US09/914,601
• Time in Patent Office: 2,825 Days
• Field of Search: 370/352, 370/389, 370/392, 370/394, 370/461, 370/462, 370/412
• US Class Current: 370/394
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

Each packet message in a sequence of packet messages is sent with an associated packet message priority label in accordance with a predetermined cyclic sequence of such labels. These priority labels each represent one of a plurality of priority levels and the position of each label in the cyclic sequence is such that number of consecutive lower priority labels between that label and the nearest label of equal or higher priority is substantially maximized. In this way, if packet messages are dropped from the sequence due to congestion on a priority basis, the packet messaging method and apparatus according to the invention ensure that, as far as possible, regular update packet messages are still received from all packet message sources.

Claims

1. A packet message source comprising:

means arranged to include a respective packet message payload in each packet message of a sequence of packet messages;

means arranged to associate a priority label with each successive packet message in said sequence in accordance with a predetermined cyclic sequence of such labels;

said priority labels each representing one of a plurality of priority levels and the positions of the labels in the cyclic sequence being controlled to maximize the number of consecutive labels having a lower priority than a nearest other label in the sequence of equal or higher priority with a label of a given priority occurring only once in each cycle; and

means arranged to send such packet messages.

2. A packet message source as claimed in claim 1, wherein said packet message source has an associated dynamic state and said respective packet message payload comprises a source state update message.

3. A packet message source as claimed in claim 1 further comprising:

means arranged to associate a time-to-live label with each packet message.

4. A packet message source as claimed in claim 1 further comprising:

means arranged to associate a packet message source identity with each packet message; and

means arranged to associate a packet message payload type setting with each packet message.

5. A packet messaging system comprising:

a plurality of packet message sources according to claim 1; and

a communications link interface;

said communications link interface comprising;

an input port for receiving packet messages from said plurality of packet message sources;

means arranged to read a priority label associated with each received packet message;

a queue for queuing received packet messages in descending order of their associated priority labels; and

an output port for sending each packet message at the head of said queue onto a communications link.

6. A packet messaging system according to claim 5 wherein a packet message source having means arranged to associate a time-to-live label with each packet message, and said communications link interface further comprising:

means arranged to read a packet message time-to-live label associated with each received packet message;

means arranged to associate with each respective packet message an indication of the period of time that packet message has been queued; and

means arranged to discard each packet message whose associated indication indicates that that packet message has been queued for a period of time longer than the associated packet message time-to-live label.

7. A packet messaging system according to claim 5 wherein a packet message source having means arranged to associate a time-to-live label with each packet message, and said communications link interface further comprising:

a clock; and

means arranged to replace the packet message time-to-live label associated with each packet message with an adjusted time-to-live label resulting from the addition of the value of the time-to-live label read from the packet message and the local time at which the packet was received;

and in which the means arranged to associate an indication of a period of time with each packet message, associates with at least one packet message, the result of said adjusted time-to-live read from each said packet message minus the local time at which said packet message arrived such that the means arranged to discard each packet message are so arranged to discard a packet message if said associated sum is less than or equal to zero.

8. A packet messaging system according to claim 5 wherein a packet message source includes means arranged to associate a packet message source identity with each packet message and means arranged to associate a packet message payload type setting with each packet message, and said communications link interface further comprising:

means arranged to read a packet message source identity from each received packet message;

means arranged to read a packet message payload type setting associated with each received packet message;

means arranged to test the packet message queue for a queued packet message with an associated source identity matching that of the received packet message;

means arranged to read the priority label associated with the matching queued packet message;

means arranged to sort into the queue on the basis of priority label a packet message replacing the matched received and queued packet messages, having the associated source identity of the matched received and queued packet messages, the payload of the received packet message and whichever of the associated priority label of the matched received and queued packet message represents the higher priority.

9. A packet messaging system comprising:

a plurality of packet message sources each comprising;

means arranged to include a respective packet message payload in each packet message of a sequence of packet messages; and

means arranged to send such packet messages; and

a communications link interface comprising;

an input port for receiving packet messages from said plurality of packet message sources;

means arranged to read a priority label associated with each received packet message;

a queue for queuing packet messages in descending order of respective allocated priority labels;

successive packets, considered in said sequence at each one of said plurality of packet message sources, having been allocated said priority labels in accordance with a predetermined cyclic sequence of such labels;

said priority labels each representing one of a plurality of priority levels and the positions of the labels in the cyclic sequence being controlled to maximize the number of consecutive labels having a lower priority than a nearest other label in the sequence of equal or higher priority with a label of a given priority occurring only once in each cycle; and

an output port for sending each packet message at the head of said queue onto a communications link.

10. A method of packet messaging comprising:

including a respective packet message payload in each packet message of a sequence of packet messages;

associating a priority label with each successive packet message of said sequence in accordance with a predetermined cyclic sequence of such labels;

said priority labels each representing one of a plurality of priority levels and the positions of the labels in the cyclic sequence being controlled to maximize the number of consecutive labels having a lower priority than a nearest other label in the sequence of equal or higher priority with a label of a given priority occurring only once in each cycle; and

sending such packet messages.

12. A computer readable storage medium, said medium embodying computer readable code for reading into a computer and executable by said computer to perform the method of claim 10.

11. A method of operating a packet messaging system including a plurality of packet message sources and a communications link interface, said method comprising:

allocating successive packets, considered in their original sequence at each one of the packet message sources, priority labels in accordance with a predetermined cyclic sequence of such labels;

said priority labels each representing one of a plurality of priority levels and the positions of the labels in the cyclic sequence being controlled to maximize the number of consecutive labels having a lower priority than a nearest other label in the sequence of equal or higher priority with a label of a given priority occurring only once in each cycle;

queuing said packet messages in a queue in descending order of respective allocated priority labels at said communications link interface; and

sending each packet message at the head of said queue onto a communications link.