Apparatus for and method of flow switching in a data communications network

• US 6,633,565 B1
• Filed: 06/29/1999
• Issued: 10/14/2003
• Est. Priority Date: 06/29/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Dosovitsky, Gennady, Yaron, Opher, Bronstein, Zvika
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/342,465
• Time in Patent Office: 1,568 Days
• Field of Search: 370/229, 370/230, 370/351, 370/352, 370/353, 370/355, 370/381, 370/389, 370/392, 370/397, 370/398, 370/399, 370/395.5, 711/108, 711/117, 711/118, 711/119, 711/122, 711/216
• US Class Current: 370/392
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

An apparatus and associated method for performing flow switching (tag switching) in a frame switching environment. The flow switching apparatus provides a mechanism whereby flows are identified and tags assigned to them. The identification and assignment of tags to flows is made Independently of other network entities and does not require communications with any other entities within the box itself or other entities in the network. The forwarding decisions are calculated once and stored in a cache or a look up table which can be accessed very quickly. The tag is used as an index into the cache or LUT such that if an entry is found in the cache or LUT for that particular tag, the forwarding decision does not have to be made again. This serves to greatly reduce the time to obtain a forwarding decision which is used by the switching fabric in steering the input frame to the appropriate output port(s). Multiple queues are used along with the cache to facilitate the forwarding of the frames. Frames that generate a cache miss are stored in a slow queue to await software processing. Once a forwarding decision is made, all the frames in the queue are switched at once. Frames that generate a hit are placed on a fast queue for expedited processing.

Claims

1. A method of switching data utilize tags for use in a network device, said method comprising the steps of:

providing a tag assignment cache for storing previously received flows and tags corresponding thereto;

determining a current flow from a header portion of a received frame and comparing said current flow with recently received flows stored in said tag assignment cache;

if a match is found, reading a tag from said tag assignment cache corresponding to said current flow, and if a match is not found randomly choosing a tag from a pool of unused tags and associating it with said current flow and storing said current flow and said tag in said tag assignment cache;

in the event no unused tags are available, selecting a tag for reuse and setting a new-tag-bit in the received frame only for the first frame of said current flow;

appending said tag to said received frame;

providing a tag forwarding cache for storing forwarding decisions and corresponding tags;

for each new flow received, calculating a forwarding decision and substitute header and storing the results of said forwarding decision, substitute header and the tag associated therewith in said tag forwarding cache;

for frames of a flow other than the first, retrieving a forwarding decision and substitute header from said tag forwarding cache based on the tag appended to said received frame;

applying said forwarding decision and substitute header to said received frame to produce an output frame; and

forwarding said output frame with said substitute header to the appropriate output port in accordance with the forwarding decision corresponding thereto.

2. The method according to claim 1, wherein said steps of identifying and assigning are performed independently of and without any communications required to other network entities.

3. The method according to claim 1, wherein said tag forwarding cache comprises:

a primary tag forwarding cache implemented in hardware; and

a secondary tag forwarding cache implemented in software adapted to operate at a slower speed than said primary tag forwarding cache.

4. The method according to claim 1, wherein each flow comprises the frame header or portions thereof that embody the criteria for identifying the particular flow.

5. The method according to claim 1, wherein said tag assignment cache comprises records containing fields representing a flow ID, flow description and tag assignment.

6. The method according to claim 1, wherein said tag forwarding cache comprises records containing fields representing a tag ID, forwarding data and substitute header.

7. The method according to claim 1, further comprising the step of providing a third cache adapted to store the results of forwarding decisions and their associated tags, said third cache having a number of entries at least equal to the aggregate sum capacity of said tag assignment cache associated with a plurality of input ports, and whereupon a miss in said tag forwarding cache causes said forwarding decision to be retrieved from said third cache upon a hit on said tag.

8. The method according to claim 1, further comprising the steps of:

storing incoming frames in one of a plurality of slow queues in the event a frame generates a miss on said tag forwarding cache requiring the calculation of a forwarding decision, each said slow queue associated with a separate tag; and

forwarding all frames within a slow queue at one time once a forwarding decision has been calculated for the flow corresponding to the frames.

10. The method according to claim 8, wherein said steps of identifying and assigning are performed independently of and without any communications required to other network entities.

9. A method of switching data utilizing tags for use in a network device, said method comprising the steps of:

providing a first cache for storing previously received flows and tags corresponding thereto;

identifying flows on an input port of said network device by comparing the flow corresponding to a received frame with the flows of a limited number of recently received flumes received by said input port;

searching for a matching flow in a said first cache and reading the tag corresponding thereto in the event of a cache hit, and randomly assigning a tag from a pool of unused tags and storing said tag and corresponding flow in said first cache in the event of a cache miss;

in the event unused tags are available, selecting a tag for reuse and setting a new-tag-bit in the received frame only for the first fame of said flow;

appending said tag to said received frame;

providing a second cache for storing forwarding decisions and corresponding tags;

for each new flow received, calculating a forwarding decision for the flow, and storing the results of said forwarding decision and the tag associated therewith in said second cache;

for frames of a flow other than the first, retrieving a forwarding decision from said second cache based on the tag appended to said received frame; and

forwarding the data frame to the appropriate output port in accordance with the forwarding decision corresponding thereto.

11. The method according to claim 9, wherein each flow comprises the frame header or portions thereof that embody the criteria for identifying the particular flow.

12. The method according to claim 9, wherein said first cache comprises records containing fields representing a flow ID, flow description and tag assignment.

13. The method according to claim 9, wherein said second cache comprises records containing fields representing a tag ID, forwarding data and substitute header.

14. The method according to claim 9, further comprising the step of providing a third cache adapt to store the results of forwarding decisions and their associated tags, said third cache having a number of entries at least equal to the aggregate sum capacity of said first caches in each of said plurality of input ports, and whereupon a miss in said second cache causes said forwarding decision to be retrieved from said third cache upon a bit on the tag.

15. The method according to claim 9, further comprising the steps of:

storing incoming frames in one of a plurality of slow queues in the event a frame generates a miss on said second cache requiring the calculation of a forwarding decision, each said slow queue associated with a separate tag; and

forwarding all frames within a slow queue at one time once a forwarding decision has been calculated for the flow corresponding to the frames.

16. A tag switching apparatus for use in a network device, comprising:

an I/O processor comprising a plurality of input ports, each input port comprising;

a first cache for storing tags and flows associated therewith;

a tag processor adapted to;

determine a current flow from a header portion of a received frame and compare said current flow with recently received flows stored in said tag assignment cache;

if a match is found, reading a tag from said tag assignment cache corresponding to said current flow;

if a match is not found randomly choosing a tag from a pool of unused taps and associating it with said current flow and storing said current flow and said tag in said tag assignment cache;

in the event no unused tags are available, selecting a tag for reuse and setting a new-tag-bit in the received frame only for the first frame of said current flow;

appending said tag to the received frame;

a controller comprising;

a second cache for storing forwarding decisions and corresponding tags;

a forwarding decision associated with a tag upon a miss in;

a header processor adapted to;

for each new flow received, calculate a forwarding decision for the flow associated with a tag and store the results of said forwarding decision and the tag associated therewith in said send cache, said header processor adapted; and

for frames of a flow other than the first, retrieve a forwarding decision from said second cache based on the tag appended to said received frame.

17. The apparatus according to claim 16, further comprising a switching fabric adapted to forward data frames to their appropriate output port in accordance with the forwarding decision corresponding thereto.

18. The apparatus according to claim 16, wherein said second cache comprises a cache implemented using hardware.

19. The apparatus according to claim 16, further comprising a third cache adapted to store the results of forwarding decisions and their associated tags, said third cache having a number of entries at least equal to the aggregate sum capacity of said fir caches in each of said plurality of input ports, and whereupon a miss in said second cache causes said forwarding decision to be retrieved from said third cache upon a hit on said tag.

20. The apparatus according to claim 16, wherein each flow comprises the frame header or portions thereof that embody the criteria for identifying the particular flow.

21. The apparatus according to claim 16, wherein said first cache comprises records containing fields representing a flow ID, now description and tag assignment.

22. The apparatus according to claim 16, wherein said second cache comprises records containing fields representing a tag ID, forwarding data and substitute header.

23. The apparatus according to claim 16, further comprising a plurality of slow queues for storing incoming frames in the event a frame generates a miss on said second cache requiring the calculation of a forwarding decision, each said slow queue associated with a separate tag, and once a forwarding decision has been calculated for the flow corresponding to the frames, all frames within a slow queue are forwarded at one time.

24. The apparatus according to claim 16, wherein said I/O processor and said controller are implemented in the same network entity.

25. The apparatus according to claim 16, wherein said I/O processor and said controller are implemented in separate and independent network entities.

26. The apparatus according to claim 16, wherein said header processor comprises means for forwarding based on a forwarding database lookup in the event of a miss on said second cache.

27. The apparatus according to claim 16, wherein said header processor comprises a third cache comprising tags and associated forwarding decisions which is checked in the event of a miss on said second cache, the forwarding decision being retrieved from said third cache and stored in said second cache in the event of a bit on said third cache.