High throughput message passing process using latency and reliability classes

• US 5,828,835 A
• Filed: 07/03/1996
• Issued: 10/27/1998
• Est. Priority Date: 05/10/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Arunkumar, Nagaraj, Srisuresh, Pyda, Mallory, Tracy D., Seaman, Michael J., Isfeld, Mark S., Mitchell, Bruce W.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US08/675,663
• Time in Patent Office: 846 Days
• Field of Search: 395/200.3, 395/200.1, 395/200.15, 395/680, 395/200.7, 395/800, 395/200.01, 395/200.02, 340/506, 370/463
• US Class Current: 709/200
• CPC Class Codes: G06F 13/387 for adaptation of different data processing systems to different peripheral devices, e.g. protocol converters for incompatible systems, open system
• CPC Class Codes: H04L 12/4604 LAN interconnection over a backbone network, e.g. Internet, Frame Relay
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5665 Interaction of ATM with other protocols
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/107 using shared medium
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9031 Wraparound memory, e.g. overrun or underrun detection
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9084 Reactions to storage capacity overflow
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

A communication technique for high volume connectionless-protocol, backbone communication links in distributed processing systems provides for control of latency and reliability of messages transmitted. The system provides for transmit list and receive list processes in the processors on the link. On the transmit side, a high priority command list and a normal priority command list are provided. In the message passing process, the command transmit function transmits commands across the backplane according to a queue priority rule that allows for control of transmit latency. Messages that require low latency are written into the high priority transmit list, while a majority of messages are written into the high throughput or normal priority transmit list. A receive filtering process in the receiving processor includes dispatch logic which dispatches messages either to a high priority receive list or a normal priority receive list. The filtering function also acts to drop messages received according to the amount of available buffer space in the receiving processor, as measured against watermarks based on reliability tags in message headers. The messages received are routed to either the high priority receive list or a normal priority receive list based on another control bit in the message headers. The receiving processor processes the messages in the receive queues according to a priority rule that allows for control of the latency between receipt of a message, and actual processing of the message by the receiving processor.

Claims

1. A method of transferring data on a communication medium from a source processor to a destination processor, the data including messages of a first transmit latency class and messages of a second transmit latency class, comprising:

queuing messages of the first transmit latency class in the source processor according to a first transmit priority rule in a first transmit queue;

queuing messages of the second transmit latency class in the source processor according to a second transmit priority rule in a second transmit queue; and

sending a particular message selected from the first and second transmit queues in the source processor according to a queue priority rule to the destination processor without establishing connection with the destination processor for the particular message in advance of sending the particular message.

2. The method of claim 1, wherein the queue priority rule provides for sending messages in the second transmit queue prior to sending any message in the first transmit queue, so long as a message resides in the second transmit queue.

3. The method of claim 1, wherein the first transmit priority rule comprises a first-in-first-out rule.

4. The method of claim 1, wherein the second transmit priority rule comprises a first-in-first-out rule.

5. The method of claim 1, wherein the step of queuing messages of the first transmit latency class includes:

storing commands in the first transmit queue, the commands identifying the messages to be transferred across the medium, wherein the step of sending includes executing the commands.

6. The method of claim 5, wherein messages of the first transmit latency class include one or more fragments of data, the fragments of data being stored in the source processor in identified locations, and the step of storing commands includes storing a command in the first transmit queue for each fragment of a message.

7. The method of claim 5, wherein the commands include:

pointers to memory locations in the source processor where the messages to be transferred are stored, and

destinations addresses for the messages to be transferred.

8. The method of claim 1, wherein messages of the first transmit latency class include one or more cells of data, the cells of data having a data length specified according to characteristics of the communication medium, and the step of sending includes segmentation of messages into cells.

9. The method of claim 1, wherein the messages include:

pointers to memory locations in the source processor where the messages to be transferred are stored, and

destinations addresses for the messages to be transferred.

10. The method of claim 1, including:

receiving at the destination processor messages addressed to the destination processor; and

storing the received messages in destination processor memory according to a receive priority rule, the receive priority rule providing for storing messages of a first reliability class if a first threshold amount of storage is available in destination processor memory, and storing messages of a second reliability class if a second threshold amount of storage is available in destination processor memory, wherein the first threshold is larger than the second threshold.

11. The method of claim 10, including:

providing a plurality of receive buffers in destination processor memory;

maintaining a list of free receive buffers; and

wherein the step of storing includes

loading at least a portion of a received message into a free receive buffer identified by the list of free receive buffers; and

wherein the receive priority rule includes dropping messages of the first reliability class if the list of free receive buffers indicates that less than the first threshold amount of storage is available in the receive buffers.

12. The method of claim 11, wherein the receive priority rule includes dropping messages of the second reliability class if the list of free receive buffers indicates that less than the second threshold amount of storage is available in the receive buffers.

13. The method of claim 12, wherein the receive priority rule includes dropping messages of a third reliability class, if the list of free receive buffers indicates that no storage is available in the receive buffers.

14. The method of claim 12, wherein the first receive priority rule comprises a first-in-first-out rule.

15. The method of claim 12, wherein the second receive priority rule comprises a first-in-first-out rule.

16. The method of claim 1, including:

providing in the source processor, a code in messages being transmitted which indicates one of first and second reliability classes;

receiving at the destination processor messages addressed to the destination processor; and

storing the received messages in destination processor memory according to a receive priority rule, the receive priority rule providing for storing messages of the first reliability class if a first threshold amount of storage is available in destination processor memory, and storing messages of the second reliability class if a second threshold amount of storage is available in destination processor memory, wherein the first threshold is larger than the second threshold.

17. The method of claim 1, including:

providing in the source processor, a code in messages being transmitted which indicates one of first and second receive latency classes;

receiving messages in a destination processor;

queuing messages of the first receive latency class for handling at the destination processor according to a first receive priority rule in a first receive queue;

queuing messages of the second receive latency class for handling at the destination processor according to a second receive priority rule in a second receive queue; and

processing messages in the first and second receive queues at the destination processor according to a receive queue priority rule.

18. The method of claim 17, wherein the receive queue priority rule provides for processing messages in the second receive queue prior to processing any message in the first receive queue, so long as a message resides in the second receive queue.

19. The method of claim 1, wherein the communication medium comprises a bus, and the step of sending includes transferring messages across the bus in a burst mode transfer.

20. The method of claim 1, wherein the communications medium comprises a local area network.

21. The method of claim 1, wherein the communications medium comprises a wide area network.

22. The method of claim 1, wherein there are a plurality of types of messages, and wherein said first transmit queue has a limited size, and wherein said step of queuing messages of the first transmit latency class includes dropping messages of a first type, if less than a first threshold number of entries is available in the first transmit queue.

23. A method of transferring data on a communication medium from a source processor to a destination processor, the data including messages of a first reliability class and messages of a second reliability class, comprising:

providing in the source processor, a code in messages being transmitted which indicates one of the first and second reliability classes;

sending a particular message from the source processor to the destination processor without establishing connection with the destination processor for the particular message in advance of sending the particular message;

receiving at the destination processor messages addressed to the destination processor; and

storing the received messages in destination processor memory according to a receive priority rule, the receive priority rule providing for storing messages of the first reliability class if a first threshold amount of storage is available in destination processor memory, and storing messages of the second reliability class if a second threshold amount of storage is available in destination processor memory, wherein the first threshold is larger than the second threshold.

24. The method of claim 23, including:

providing in the source processor, a code in messages being transmitted which indicates one of a first and second receive latency classes;

receiving messages in a destination processor;

queuing messages of the first receive latency class for handling at the destination processor according to a first receive priority rule in a first receive queue;

queuing messages of the second receive latency class for handling at the destination processor according to a second receive priority rule in a second receive queue; and

processing messages in the first and second receive queues at the destination processor according to a receive queue priority rule.

25. The method of claim 24, wherein the receive queue priority rule provides for processing messages in the second receive queue prior to processing any message in the first receive queue, so long as a message resides in the second receive queue.

26. The method of claim 24, wherein the first receive priority rule comprises a first-in-first-out rule.

27. The method of claim 24, wherein the second receive priority rule comprises a first-in-first-out rule.

28. The method of claim 23, wherein the communication medium comprises a bus, and the step of sending includes transferring messages across the bus in a burst mode transfer.

29. The method of claim 23, wherein the communications medium comprises a local area network.

30. The method of claim 23, wherein the communications medium comprises a wide area network.

31. The method of claim 23, including:

providing a plurality of receive buffers in destination processor memory;

maintaining a list of free receive buffers available for the step of storing;

and wherein the receive priority rule includes dropping messages of the first reliability class if the list of free receive buffers indicates that less than the first threshold amount of storage is available in the receive buffers.

32. The method of claim 31, wherein the receive priority rule includes dropping messages of the second reliability class if the list of free receive buffers indicates that less than the second threshold amount of storage is available in the receive buffers.

33. The method of claim 32, wherein the data includes messages of a third reliability class, and the receive priority rule includes dropping messages of a third reliability class if no free receive buffers are available in the receive buffers.

34. A method of transferring data on a communication medium from a source processor to a destination processor, the data including messages of a first latency class and messages of a second latency class, comprising:

providing in the source processor, a code in messages being transmitted which indicates one of a first and second receive latency classes;

sending a particular message from the source processor to the destination processor without establishing connection with the destination processor for the particular message in advance of sending the particular message;

receiving at the destination processor messages addressed to the destination processor;

queuing messages of the first receive latency class for handling at the destination processor according to a first receive priority rule in a first receive queue;

queuing messages of the second receive latency class for handling at the destination processor according to a second receive priority rule in a second receive queue; and

processing messages in the first and second receive queues at the destination processor according to a receive queue priority rule.

35. The method of claim 34, wherein the receive queue priority rule provides for processing messages in the second receive queue prior to processing any message in the first receive queue, so long as a message resides in the second receive queue.

36. The method of claim 34, wherein the first receive priority rule comprises a first-in-first-out rule.

37. The method of claim 34, wherein the second receive priority rule comprises a first-in-first-out rule.

38. The method of claim 34, wherein the communication medium comprises a bus, and the step of sending includes transferring messages across the bus in a burst mode transfer.

39. The method of claim 34, wherein the communications medium comprises a local area network.

40. The method of claim 34, wherein the communications medium comprises a wide area network.

41. In a system including a plurality of processors, processors in the plurality having one or more input/output ports coupled to data networks, a method of transferring a plurality of types of messages on a communication medium among the plurality of processors, comprising:

receiving a frame of data from an input/output port on a source processor;

executing a frame transfer process on the source processor to route the frame of data to a destination processor in the plurality of processors, the frame transfer process including generating control and data transfer messages to be transferred among the plurality of processors;

classifying the control and data transfer messages in the source processor according to a transmit latency class and a receive reliability class;

queuing, in response to the frame transfer process, messages of a first transmit latency class in a source processor according to a first transmit priority rule in a first transmit queue;

queuing, in response to the frame transfer process, messages of a second transmit latency class in the source processor according to a second transmit priority rule in a second transmit queue;

sending specific messages selected from the first and second transmit queues in the source processor according to a queue priority rule to the destination processor without establishing that the destination processor has available resources to receive a specific message in advance of sending the specific message;

receiving at the destination processor messages addressed to the destination processor;

determining at the destination processor the reliability class of received messages;

storing the received messages in destination processor memory according to a receive priority rule, the receive priority rule providing for dropping messages of a first reliability class if less than a first threshold amount of storage is available in destination processor memory; and

executing a process in the destination processor using the stored messages.

42. The method of claim 41, including:

providing a plurality of receive buffers in destination processor memory;

maintaining a list of free receive buffers available for the step of storing;

and wherein the receive priority rule includes dropping messages of the and wherein the receive priority rule includes dropping messages of the first reliability class if the list of free receive buffers indicates that less than the first threshold amount of storage is available in the receive buffers.

43. The method of claim 41, wherein the step of storing received messages includes dropping messages of a second reliability class if less than a second threshold amount of storage is available in destination processor memory.

44. The method of claim 41, wherein the step of queuing messages of the first type includes:

storing commands the first transmit queue, the commands identifying the messages to be transferred across the medium, wherein the step of sending includes executing the commands.

45. The method of claim 44, wherein at least some data transfer messages include one or more fragments of data, the fragments of data being stored in the source processor in identified locations, and the step of storing commands includes storing a command in the first transmit queue for each fragment of a message.

46. The method of claim 45, wherein the commands include:

pointers to memory locations in the source processor where the messages to be transferred are stored, and

destinations addresses for the messages to be transferred.

47. The method of claim 45, wherein the communication medium comprises a bus, and the step of sending includes transferring messages of the first type across the bus in a burst mode transfer.

48. The method of claim 41, including:

providing in the source processor, a code in messages being transmitted which indicates one of a plurality of receive latency classes;

queuing messages of a first receive latency class for handling at the destination processor according to a first receive priority rule in a first receive queue;

queuing messages of a second receive latency class for handling at the destination processor according to a second receive priority rule in a second receive queue; and

processing messages in the first and second receive queues at the destination processor according to a receive queue priority rule.

49. The method of claim 48, wherein the receive queue priority rule provides for processing messages in the second receive queue prior to processing any message in the first receive queue, so long as a message resides in the second receive queue.

50. The method of claim 49, wherein the first receive priority rule comprises a first-in-first-out rule.

51. The method of claim 49, wherein the second receive priority rule comprises a first-in-first-out rule.

52. The method of claim 41, wherein the communication medium comprises a bus, and the step of sending includes transferring messages across the bus in a burst mode transfer.

53. The method of claim 41, wherein the communications medium comprises a local area network.

54. The method of claim 41, wherein the communications medium comprises a wide area network.

55. The method of claim 41, wherein there are a plurality of types of messages, and wherein said first transmit queue has a limited size, and wherein said step of queuing messages of the first transmit latency class includes dropping messages of a first type, if less than a first threshold number of entries is available in the first transmit queue.

56. A method of transferring data on a communication medium from a source processor to a destination processor, the data including messages of a first transmit latency class and messages of a second transmit latency class, comprising:

queuing messages of the first transmit latency class in the source processor according to a first transmit priority rule in a first transmit queue;

queuing messages of the second transmit latency lass in the source processor according to a second transmit priority rule in a second transmit queue; and

sending a particular message selected from the first and second transmit queues in the source processor according to a queue priority rule to the destination processor without establishing connection with the destination processor for the particular message in advance of sending the particular message;

receiving at the destination processor messages addressed to the destination processor; and

storing the received messages in destination processor memory according to a receive priority rule, the receive priority rule providing for storing messages of a first reliability class if a first threshold amount of storage is available in destination processor memory, and storing messages of a second reliability class if a second threshold amount of storage is available in destination processor memory, wherein the first threshold is larger than the second threshold, and wherein the receive priority rule includes dropping messages of the second reliability class if than the second threshold amount of storage is available in the destination processor memory.

57. The method of claim 56, wherein the receive priority rule includes dropping messages of a third reliability class, if no storage available in the destination processor memory.