Method and apparatus for distributing network traffic processing on a multiprocessor computer

• US 6,389,468 B1
• Filed: 03/01/1999
• Issued: 05/14/2002
• Est. Priority Date: 03/01/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Muller, Shimon, Gentry, Denton E. Jr.
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): FIELDS, KENNETH WAYNE
• Application Number:
  US09/259,445
• Time in Patent Office: 1,170 Days
• Field of Search: 709/224, 709/249, 709/250, 709/226, 709/229, 709/235
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A system and method are provided for distributing or sharing the processing of network traffic (e.g., through a protocol stack on a host computer system) received at a multiprocessor computer system. A packet formatted according to one or more communication protocols is received from a network entity at a network interface circuit of a multiprocessor computer. A header portion of the packet is parsed to retrieve information stored in one or more protocol headers, such as source and destination identifiers or a virtual communication connection identifier. In one embodiment, a source identifier and a destination identifier are combined to form a flow key that is subjected to a hash function. The modulus of the result of the hash function over the number of processors in the multiprocessor computer is then calculated. In another embodiment a modulus operation is performed on the packet'"'"'s virtual communication connection identifier. The result of the modulus operation identifies a processor to which the packet is submitted for processing.

Claims

1. A method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, comprising:

receiving a first packet at a network interface of a multiprocessor computer;

retrieving from said first packet an identifier of a source of said first packet;

retrieving from said first packet an identifier of a destination of said first packet;

combining said source identifier and said destination identifier to form a first flow index for identifying a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet; and

submitting said first packet for processing by said first processor.

2. The method of claim 1, further comprising:

receiving a second packet of said first communication flow at said network interface;

associating said first processor identifier with said second packet; and

submitting said second packet from said network interface for processing by said first processor.

3. The method of claim 1, further comprising:

receiving a second packet at said network interface;

producing a second flow index to identify a second communication flow comprising said second packet;

generating from said second flow index an identifier of a second processor of said plurality of processors;

associating said second processor identifier with said second packet; and

submitting said second packet for processing by said second processor.

4. The method of claim 3, wherein said producing a second flow index comprises retrieving a virtual connection identifier from said second packet.

5. The method of claim 1, wherein said generating from said first flow index an identifier of a first processor comprises:

hashing said first flow index to produce a hash value;

identifying a number of processors among which network traffic processing is to be distributed; and

calculating a modulus of said hash value over said number of processors.

6. The method of claim 5, wherein said identifying comprises retrieving a value representing said number of processors from a programmable storage device.

7. The method of claim 1, wherein said generating from said first flow index an identifier of a first processor comprises:

identifying a number of processors among which network traffic processing is to be distributed; and

calculating a modulus of said first flow index over said number of processors.

8. The method of claim 1, wherein said submitting comprises:

storing said first packet in a first memory of said multiprocessor computer; and

storing said first processor identifier in a second memory.

9. The method of claim 8, wherein said submitting further comprises issuing an alert to said multiprocessor computer to notify said multiprocessor computer of said storage of said first packet.

10. The method of claim 1, further comprising searching a flow database for said first flow index, wherein said flow database comprises a collection of flow indexes.

11. The method of claim 10, wherein said searching comprises if said first flow index is not found in said flow database, storing said first flow index in said flow database.

12. The method of claim 10, wherein said searching comprises if said first flow index is found in said flow database, updating an entry in said flow database associated with said first flow index.

13. The method of claim 1, further comprising storing said first flow index in a flow database comprising flow indexes of communication flows involving entities operating on the multiprocessor computer.

14. A method of distributing the load of processing packets received from a network among multiple processors in a multiprocessor computer, comprising:

receiving a first packet at a network interface of a multiprocessor host computer;

receiving a second packet at said network interface;

retrieving a source identifier and a destination identifier from said first packet;

combining said source identifier and said destination identifier to form a first flow key;

creating a second flow key to identify a second communication flow comprising said second packet;

generating an identifier of a first processor from said first flow key;

generating an identifier of a second processor from said second flow key;

submitting said first packet to said first processor; and

submitting said second packet to said second processor.

15. The method of claim 14, wherein each of said receiving, creating and generating are performed on said network interface.

16. The method of claim 14, wherein said retrieving comprises extracting one or more fields from a protocol header of said first packet, said protocol being one of a set of pre-selected protocols.

17. The method of claim 14, wherein said creating a second flow key comprises extracting a virtual connection identifier from said second packet.

18. The method of claim 14, wherein said generating an identifier of a first processor comprises:

performing a hashing function on said first flow key to produce a hash value; and

performing a modulus function on said hash value.

19. The method of claim 14, wherein said generating an identifier of a first processor comprises performing a modulus function on said first flow key.

20. A multiprocessor computer for receiving and processing packets from a network, comprising:

a plurality of processors; and

a network interface configured to receive packets from a network and submit said packets to said plurality of processors, said network interface comprising;

a flow identifier configured to;

retrieve a source identifier and a destination identifier from a packet; and

combine said source identifier and said destination identifier to form a flow key for identifying a flow comprising said packet; and

a load distributor configured to generate, from said flow key, an identifier of a processor of said plurality of said processors for processing said packet;

wherein said load distributor generates a first identifier of a first processor for a first set of packets in a first flow and generates a second identifier of a second processor for a second set of packets in a second flow.

21. The multiprocessor computer of claim 20, said network interface further comprising:

a flow database for storing one or more flow keys, and

a flow database manager for managing said flow database.

22. The multiprocessor computer of claim 20, said network interface further comprising:

a first data structure for storing said first set of packets; and

a second data structure for storing said first processor identifier.

23. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of distributing the processing of network traffic among multiple processors, the method comprising:

receiving a first packet at a network interface of a multiprocessor computer;

retrieving from said first packet an identifier of a source of said first packet;

retrieving from said first packet an identifier of a destination of said first packet;

combining said source identifier and said destination identifier to form a first flow index for identifying a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet; and

submitting said first packet for processing by said first processor.

24. A method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

hashing said first flow index to produce a hash value;

identifying a number of processors among which network traffic processing is to be distributed;

calculating a modulus of said hash value over said number of processors wherein said modulus corresponds to an identifier of a first processor;

associating said first processor identifier with said first packet; and

submitting said first packet for processing by said first processor.

25. The method of claim 24, wherein said identifying comprises retrieving a value representing said number of processors from a programmable storage device.

26. The method of claim 24, wherein said producing a first flow index comprises:

retrieving from said first packet an identifier of a source of said first packet; and

retrieving from said first packet an identifier of a destination of said first packet.

27. The method of claim 26, wherein said producing a first flow index further comprises combining said source identifier and said destination identifier.

28. The method of claim 24, wherein said producing a first flow index comprises retrieving a virtual connection identifier from said first packet.

29. The method of claim 24, wherein said submitting comprises:

storing said first packet in a first memory of said multiprocessor computer; and

storing said first processor identifier in a second memory.

30. The method of claim 29, wherein said submitting further comprises issuing an alert to said multiprocessor computer to notify said multiprocessor computer of said storage of said first packet.

31. The method of claim 24, further comprising searching a flow database for said first flow index, wherein said flow database comprises a collection of flow indexes.

32. The method of claim 31, wherein said searching comprises:

if said first flow index is not found in said flow database, storing said first flow index in said flow database; and

if said first flow index is found in said flow database, updating an entry in said flow database associated with said first flow index.

33. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, the method comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

hashing said first flow index to produce a hash value;

identifying a number of processors among which network traffic processing is to be distributed;

calculating a modulus of said hash value over said number of processors wherein said modulus corresponds to an identifier of a first processor;

associating said first processor identifier with said first packet; and

submitting said first packet for processing by said first processor.

34. A method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet;

storing said first packet in a first memory of said multiprocessor computer;

storing said first processor identifier in a second memory; and

issuing an alert to said multiprocessor computer to notify said multiprocessor computer of said storage of said first packet.

35. The method of claim 34, wherein said producing a first flow index comprises:

retrieving from said first packet an identifier of a source of said first packet; and

retrieving from said first packet an identifier of a destination of said first packet.

36. The method of claim 35, wherein said producing a first flow index further comprises combining said source identifier and said destination identifier.

37. The method of claim 34, wherein said producing a first flow index comprises retrieving a virtual connection identifier from said first packet.

38. The method of claim 34, further comprising searching a flow database for said first flow index, wherein said flow database comprises a collection of flow indexes.

39. The method of claim 38, wherein said searching comprises:

if said first flow index is not found in said flow database, storing said first flow index in said flow database; and

if said first flow index is found in said flow database, updating an entry in said flow database associated with said first flow index.

40. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, the method comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet;

storing said first packet in a first memory of said multiprocessor computer;

storing said first processor identifier in a second memory; and

issuing an alert to said multiprocessor computer to notify said multiprocessor computer of said storage of said first packet.

41. A method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet;

submitting said first packet for processing by said first processor;

searching a flow database for said first flow index, said flow database comprising a collection of flow indexes; and

if said first flow index is not found in said flow database, storing said first flow index in said flow database.

42. The method of claim 41, further comprising:

if said first flow index is found in said flow database, updating an entry in said flow database associated with said first flow index.

43. The method of claim 41, wherein said producing a first flow index comprises:

retrieving from said first packet an identifier of a source of said first packet; and

retrieving from said first packet an identifier of a destination of said first packet.

44. The method of claim 43, wherein said producing a first flow index further comprises combining said source identifier and said destination identifier.

45. The method of claim 41, wherein said producing a first flow index comprises retrieving a virtual connection identifier from said first packet.

46. The method of claim 41, wherein said generating from said first flow index an identifier of a first processor comprises:

hashing said first flow index to produce a hash value;

identifying a number of processors among which network traffic processing is to be distributed; and

calculating a modulus of said hash value over said number of processors.

47. The method of claim 46, wherein said identifying comprises retrieving a value representing said number of processors from a programmable storage device.

48. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of distributing network traffic processing among a plurality of processors in a multiprocessor computer, the method comprising:

receiving a first packet at a network interface of a multiprocessor computer;

producing a first flow index to identify a first communication flow comprising said first packet;

generating from said first flow index an identifier of a first processor of a plurality of processors of said multiprocessor computer;

associating said first processor identifier with said first packet;

submitting said first packet for processing by said first processor;

searching a flow database for said first flow index, said flow database comprising a collection of flow indexes; and

if said first flow index is not found in said flow database, storing said first flow index in said flow database.