Network intermediate system with message passing architecture

Claims

What is claimed is:

1. An apparatus for transferring large amounts of input/output data among a plurality of processors having respective local memories, comprising:

a bus interconnecting the plurality of processors;

a plurality of bus interface devices, coupled to the bus and to corresponding processors in the plurality of processors, a first bus interface device in the plurality of bus interface devices which originates a transfer without first obtaining permission to transfer to a destination device including

a command list storing a list of commands which characterize transfers of data from local memory across the bus,

a bus data buffer which buffers data subject of a command being executed between local memory and the bus,

and a second bus interface device in the plurality of bus interface devices which receives a transfer including

a free buffer list storing pointers to free buffers in local memory into which data may be loaded from the bus,

a receive list storing pointers to buffers in local memory loaded with data from the bus, and

an inbound data buffer which buffers data subject of a transfer addressed to the second bus interface between the bus and free buffers in local memory.

2. The apparatus of claim 1, wherein the command list includes a first high priority command list and a second lower priority command list for managing latency of higher priority commands.

3. The apparatus of claim 1, wherein the first bus interface device includes control logic which manages data transfer into and out of the bus data buffer for messages, including data, identified by commands in the command list, to pack data to compose message transfer cells for messages, the message transfer cells including a portion of the data of the message, and to drive the message transfer cells on the bus in burst mode.

4. The apparatus of claim 3, wherein the second bus interface device includes control logic which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells from the bus, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

5. The apparatus of claim 4, wherein the receive list includes a first higher priority receive list and a second lower priority receive list for managing reliability and throughput of transfers.

6. The apparatus of claim 4, including logic which monitors the free list, a watermark parameter which indicates an amount of free buffer resources, and watermark logic which causes lower priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the watermark parameter.

7. The apparatus of claim 6, including a second watermark parameter indicating a smaller amount of free buffer resources, and second watermark logic which cause higher priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the second watermark parameter, to prevent overflow of the free buffer resources.

8. The apparatus of claim 3, wherein the plurality of processors have respective slot numbers on the bus, and the commands indicate a destination of a message using the slot number.

9. The apparatus of claim 8, wherein the second bus interface device includes control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells having the slot number of the local processor from the bus, assigning a message transfer cell to a channel for the message, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

10. The apparatus of claim 8, including at least a second bus interconnecting the plurality of processors, and the commands indicate a destination using a bus identifier and a slot number.

11. The apparatus of claim 1, wherein said bus comprises a high speed parallel bus.

12. The apparatus of claim 3, wherein the second bus interface device includes control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells having an identifier which maps to a channel number, and assigning message transfer cells to a channel in response to the identifier.

13. The apparatus of claim 12, wherein the first bus interface device supplies a single identifier to all message transfer cells which it transfers.

14. The apparatus of claim 13, wherein the plurality of processors have respective slot numbers on the bus, and the identifier comprises the slot number of the transferring device.

15. A bus interface which provides access to a bus for a local processor having local memory, comprising:

a command list storing a list of commands which characterize transfers of data from local memory across the bus,

a bus data buffer which buffers data subject of a command being executed between local memory and the bus,

a free buffer list storing pointers to free buffers in local memory into which data may be loaded from the bus,

an inbound data buffer which buffers data subject of a transfer addressed to the local processor between the bus and free buffers in local memory, and

a receive list storing pointers to buffers in local memory loaded with data from the bus.

16. The bus interface of claim 15, wherein the command list includes a first high priority command list and a second lower priority command list for managing latency of higher priority commands.

17. The bus interface of claim 15, including control logic which manages data transfer into and out of the bus data buffer for messages identified by commands in the command list to composes message transfer cells for messages, and drives the message transfer cells on the bus in burst mode without first obtaining permission to send to a destination on the bus.

18. The bus interface of claim 17, including control logic which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells from the bus, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

19. The bus interface of claim 18, wherein the receive list includes a first higher priority receive list and a second lower priority receive list for managing reliability and throughput of transfers.

20. The bus interface of claim 19, including logic which monitors the free list, a watermark parameter which indicates an amount of free buffer resources, and watermark logic which causes lower priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the watermark parameter.

21. The bus interface of claim 20, including a second watermark parameter indicating a smaller amount of free buffer resources, and second watermark logic which causes higher priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the second watermark parameter, to prevent overflow of the free buffer resources.

22. The bus interface of claim 17, wherein the second bus interface device includes control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells having an identifier which maps to a channel number, and assigning message transtar cells to a channel in response to the identifier.

23. The bus interface of claim 22, wherein the first bus interface device supplies a single identifier to all message transfer cells which it transfers.

24. The bus interface of claim 23, wherein the plurality of processors have respective slot numbers on the bus, and the identifier comprises the slot number of the transferring device.

25. The bus interface of claim 15, wherein users of the bus have respective slot numbers on the bus, and the commands indicate a destination of a message using the slot number.

26. The bus interface of claim 25, including control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells having the slot number of the local processor from the bus, assigning a message transfer cell to a channel for the message, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

27. The bus interface of claim 15, wherein said bus comprises a high speed parallel bus.

28. The bus interface of claim 15, wherein the command list includes a first high priority command list and a second lower priority command list for managing latency of higher priority commands, and the receive list includes a first higher priority receive list and a second lower priority receive list for managing reliability and throughput of transfers, and further including:

transfer control logic which manages data transfer into and out of the bus data buffer for messages identified by commands in the command list to composes message transfer cells for messages, and drives the message transfer cells on the bus in burst mode without first obtaining permission to send to a destination on the bus; and

receive control logic which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells from the bus, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

29. An apparatus for transferring large amounts of input/output data among a plurality of processors having respective local memories, comprising:

a bus interconnecting the plurality of processors;

a plurality of bus interface devices, coupled to the bus and to corresponding processors in the plurality of processors, including a first bus interface device in the plurality of bus interface devices which originates a transfer; and a second bus interface device in the plurality of bus interface devices which receives a transfer, the second bus interface device, including

a free buffer list storing pointers to free buffers in local memory into which data may be loaded from the bus,

a receive list storing pointers to buffers in local memory loaded with data from the bus, including a first high priority receive list and a second lower priority receive list, and

logic which monitors the free buffer list which causes lower priority messages to be dropped to prevent overflow of the free buffer resources.

30. The apparatus of claim 29, wherein the logic which monitors the free list includes a watermark parameter which indicates an amount of free buffer resources, and watermark logic which causes lower priority messages to be dropped when the free list indicates that free buffer resources in local memory, fall below the watermark parameter.

31. The apparatus of claim 30, including a second watermark parameter indicating a smaller amount of free buffer resources, and second watermark logic which causes higher priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the second watermark parameter, to prevent overflow of the free buffer resources.

32. The apparatus of claim 29, wherein the second bus interface includes:

an inbound data buffer which buffers data subject of a transfer addressed to the its local processor between the bus and free buffers in local memory.

33. The apparatus of claim 29, wherein the plurality of processors have respective slot numbers on the bus, and the second bus interface receives transfers on the bus carrying the slot number of the local processor.

34. The apparatus of claim 29, wherein the second bus interface device includes control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of cells having an identifier which maps to a channel, assigning a cell to a channel in response to the identifier, loading free buffers in local memory from the inbound buffer with cells, and updating the receive list.

35. The apparatus of claim 29, wherein said bus comprises a high speed parallel bus.

36. A network traffic management system, comprising:

a bus:

a plurality of processors, each including local memory, at least one network interface, a bus interface coupled to the bus, and resources for managing the at least one network interface and the bus interface; the bus interface including

a command list storing a list of commands which characterize transfers of data from local memory across the bus,

a bus data buffer which buffers data subject of a command being executed between local memory and the bus,

a free buffer list storing pointers to free buffers in local memory into which data may be loaded from the bus,

an inbound data buffer which buffers data subject of a transfer addressed to the second processor between the bus and free buffers in local memory, and

a receive list storing pointers to buffers in local memory loaded with data from the bus.

37. The network traffic management system of claim 36, wherein the command list includes a first high priority command list and a second lower priority command list for managing latency of higher priority commands.

38. The network traffic management system of claim 36, including control logic which manages data transfer into and out of the bus data buffer for messages identified by commands in the command list to composes message transfer cells for messages, and drives the message transfer cells on the bus in burst mode without first obtaining permission to transfer to a destination on the bus.

39. The network traffic management system of claim 38, including control logic which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells from the bus, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

40. The network traffic management system of claim 39, wherein the receive list includes a first higher priority receive list and a second lower priority receive list for managing reliability and throughput of transfers.

41. The network traffic management system of claim 39, including logic which monitors the free list, a watermark parameter which indicates an amount of free buffer resources, and watermark logic which causes lower priority messages to be dropped when the flee list indicates that free buffer resources in local memory fall below the watermark parameter.

42. The network traffic management system of claim 41, including a second watermark parameter indicating a smaller amount of free buffer resources, and second watermark logic which causes higher priority messages to be dropped when the free list indicates that free buffer resources in local memory fall below the second watermark parameter, to prevent overflow of the free buffer resources.

43. The network traffic management system of claim 38, wherein users of the bus have respective slot numbers on the bus, and the commands indicate a destination of a message using the slot number.

44. The network traffic management system of claim 43, including control logic with a plurality of channels which manages data transfer into and out of the inbound buffer, including receiving burst transfers of message transfer cells having the slot number of the local processor from the bus, assigning a message transfer cell to a channel for the message, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

45. The network traffic management system of claim 43, including at least a second bus interconnecting the plurality of processors, and the commands indicate a destination using a bus identifier and a slot number.

46. The network traffic management system of claim 45, wherein said bus and said second bus comprise a high speed parallel buses.

47. The network traffic management system of claim 36, wherein said bus comprises a high speed parallel bus.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to the processing systems which handle large amounts of input/output data, such as network intermediate systems. More particularly, the present invention relates to a message passing architecture for a high volume network router system.

2. Description of Related Art

A network router is a system which allows a plurality of local area networks to communicate with one another, even when such networks are operating under different protocols. The router will have an interface to each of the networks using its resources. Users of the respective networks address packets to the router in order to transmit packets to other networks coupled to the router. When a network router is connected to a large number of networks, the possibility that a very large volume of data will be flowing through the router at a given time is quite high.

In the system known as NetBuilder II, manufactured by 3Com Corporation in Santa Clara, Calif., the assignee of the present application, a plurality of input/output modules are connected to a high speed parallel bus. Each of the input/output modules is connected to one or more local area networks, and forwards packets received across the high speed bus to a shared memory resource. A central routing processor routes the packets from the shared memory resource to the appropriate destination across the same high speed bus.

Although this architecture provides very high throughput rates for today's local area networks, future local area network designs are transmitting much higher volumes of data, and in many environments it is desirable to connect more and more local area networks to a single router. Thus, the throughput capabilities of the router in the prior art designs may be a limiting factor in the design.

For instance, one standard local area network known as Ethernet, today operates at 10 Mbits per second. Future Ethernet designs are planned which will operate at 100 Mbits per second. Also, high speed protocols, such as FDDI and the asynchronous transfer mode (ATM), have very high data rates.

In systems managing a large volume of input/output data, such as a network router, there are a number of design issues of importance. Particularly when there are a number of interfaces using shared resources, resource contention must be addressed. Contention for the resources causes problems with message latency, reliability, fairness, and robustness of service guarantees.

Latency refers to the delay between the time that a service is requested and actual initiation of that service request. Throughput is closely linked to latency. In general, with bursty traffic, such as encountered in network intermediate systems, higher throughput causes a higher variance in latencies, or at least higher peak latencies. Guarantees of low latency for transfers are most easily provided if the desired throughput is relatively low.

Also, reliability is an important factor in such systems. The reliability of data transfers is always relative, but can be made as reliable as the hardware on which it is running if the source of the transfers can be flow controlled. However, the cost of providing guaranteed delivery can be quite high. Further, general robustness principals require that each layer that requires reliability provide its own guarantees.

Fairness in the context of high volume I/O processors includes the notion of supporting different qualities of service as well as reasonably allocating services between peers. The types of fairness include providing equal shares, or at least a guaranteed percentage of share to each user of the resource by a fair queuing scheme. Also, fairness includes guaranteed progress, which could be designed to meet all feasible receive rates, or to provide a prioritized service system. Also, a fairness system can operate in an environment which provides a probably fair result, but no guarantee of fairness is assured, such as might be encountered in a system which randomly discards transfers when stressful situations are encountered.

Finally, such a system must be robust. Excessive traffic loads may adversely affect other well-behaved traffic in the interconnected networks, including high priority transfers within the device. Thus, in a network intermediate system environment, protection must be considered against misbehaving protocols which cause excessive traffic, network transients; natural excess traffic loads, which must be handled gracefully; and misbehaving hardware which causes retransmissions or otherwise effectively reduces the bandwidth of the system.

Accordingly, it is desirable to provide a high volume input/output processing system which effectively deals with the issues of latency, throughput, reliability, fairness, and robustness.

SUMMARY OF THE INVENTION

The present invention provides a system that allows for transferring large amounts of input/output data among a plurality of processors, such as a network intermediate system or router. The apparatus includes a bus interconnecting the plurality of processors with a plurality of bus interface devices connected to the bus and to corresponding processors. The bus interface device which originates a transfer without obtaining permission from the destination device, includes a command list storing a list of commands which characterize transfers of data from local memory across the bus and a packing buffer which buffers the data subject of the command being executed between local memory and the bus. A bus interface device which receives a transfer includes a free buffer list storing pointers to free buffers in local memory into which the data may be loaded from the bus, a receive list storing pointers to buffers in local memory loaded with data from the bus, and an inbound data buffer which buffers data subject of a transfer addressed to the receiving processor between the bus and the free buffers in the local memory. By eliminating the requirement to obtain permission from the destination device, such as normally done by a handshake protocol or the like, bus performance is greatly improved. However, the system must be able to tolerate occasional lost messages on the bus.

According to one aspect of the invention, the command list includes at least a first high priority command list and a second lower priority command list so that the apparatus may manage latency of the higher priority commands according to a latency class for the command.

According to another aspect of the invention, the commands stored in the command list identify messages to be transferred across the bus. The bus interface device of the originating processor includes control logic which manages data transfer into and out of the packing buffer for messages identified by the commands in the command list to compose message transfer cells for the messages, and to drive the message transfer cells on the bus in a burst mode. The bus interface which receives the transfer includes control logic which manages data transtar into and out of the inbound buffer, including receiving burst transfers of message transtar cells from the bus, loading free buffers in local memory from the inbound buffer with message transfer cells, and updating the receive list.

Also, according to another aspect of the invention, the receive list includes a first higher priority receive list and a second lower priority receive list for reliability, latency, and throughput management by the receiving station. The system also may include logic which monitors the free list so that lower priority messages may be dropped to prevent overflow of free buffer resources. The logic which monitors the free list includes a first watermark parameter which indicates an amount of free buffer resources, and watermark logic which signals the processor coupled to the receiving interface when the free list indicates that free buffer resources in the local memory fall below the first watermark parameter. Thus, messages may be selectively dropped from the receive list in the event that an overflow condition is threatened, based on message type. Also, a second watermark parameter may be included which indicates a second level in the amount of free buffer resources. Second watermark logic signals the local processor when the free list indicates that free buffer resources in the local memory fall below the second watermark parameter, so that messages having a second tier of priority may be dropped to prevent overflow of the free buffer resources.

In yet another aspect of the present invention, message transfer cells of a given message are allocated to a logical channel in the receiving processor to manage reconstruction of the received message in the receiving processor. For instance, each of the processors on the bus may have a respective slot number or other identifier. The commands indicate the source and destination of messages on the bus using the slot number. Thus, the receiving interfaces may assign incoming messages to a logical channel based on the originating slot number and the receiving slot number.

According to yet another aspect of the present invention, there may be a plurality of high speed parallel buses interconnecting the processors. In this aspect, messages transferred on one of the buses are identified by the sending processor, the bus on which they are sent, and the receiving processor.

Using the higher and lower priority command lists, commands are classified into a first latency class which characterizes transfers of data from local memory across the bus which require lower latency, and a second latency class which characterizes transfers of data from local memory across the bus which tolerate longer latency. Logic managing the data transfers across the bus loads the command list with new commands according to the latency class of the command.

As mentioned above, the preferred system provides a network traffic management device in which the plurality of processors each include at least one network interface, other processing elements such as a compression engine, and resources for managing the network interface and the bus interface.

Using this system, a network traffic management system is provided with managed resource contention, plural latency classes, and very high throughput. Also, message delivery is provided with LAN-like reliability, where very few messages might be lost. Also, fairness may be managed by the processors using the system by managing the command lists and receive lists as suits the needs of a particular implementation.

The design of the present invention provides separate queuing and resource management on both the sending and receiving sides for messages requiring reliability, so that such messages are not dropped in favor of data traffic of lower importance. The design provides for multiple levels of reliability guarantees, using buffer occupancy watermarks in order to give extra reliability to critical messages which provides robustness in the event that the destination falls behind and is unable to accept