Router with routing processors and methods for virtualization

• US 7,362,702 B2
• Filed: 10/29/2002
• Issued: 04/22/2008
• Est. Priority Date: 10/18/2001
• Status: Expired due to Fees

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: QLogic Corporation (Marvell Technology Group Limited)
• Inventors: Edmonds, Tracy, Joeng, Wayland, Peterson, Eric Russell, Terrell, William C., Kodama, Jean, Muliadi, Harun, Hill, Rexford, Chan, Norman, Nishimura, Michael, How, Stephen
• Primary Examiner(s): Jagannathan; Melanie
• Application Number:
  US10/284,273
• Publication Number:
  US 20030189930A1
• Time in Patent Office: 2,002 Days
• Field of Search: None
• US Class Current: 370/230
• 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 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A router for use in a network includes a scalable architecture and performs methods for implementing quality of service on a logical unit behind a network port; and for implementing storage virtualization. The architecture includes a managing processor, a supervising processor; and a plurality of routing processors coupled to a fabric. The managing processor has an in-band link to a routing processor. A routing processor receives a frame from the network, determines by parsing the frame, the protocol and logical unit number, and routes the frame to a queue according to a traffic class associated with the logical unit number in routing information prepared for the processors. An arbitration scheme empties the queue in accordance with a deficit round robin technique. If a routing processor detects the frame'"'"'s destination is a virtual entity, and so is part of a virtual transaction, the router conducts a nonvirtual transaction in concert with the virtual transaction. The nonvirtual transaction accomplishes the intent of the virtual transaction but operates on an actual network port, for example, a storage device.

Claims

1. A method performed by a router for routing virtual and non-virtual frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, the method performed by each routing processor of the plurality, the method comprising:

(a) a step for receiving a frame from the network;

(b) a step for preparing a flow lookup in accordance with at least a portion of the frame;

(c) a step for obtaining from a memory circuit a first result of the flow lookup and if the flow look up is incomplete, the frame is passed to a supervising processor that specifies a route or discards the frame;

(d) a step for preparing a second lookup in accordance with the first result and if a sub flow flag is set;

(e) a step for obtaining from the memory circuit a second result of the second lookup;

(f) a step for determining if a context for the frame is available at a location other than where the frame is received;

(g) a step for building a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame;

(h) a step for marking the forward frame for handling by the other processor;

(i) a step for determining if a context for the frame is available at the processor receiving the frame and if the context is unavailable at the received location or another location as determined in step (f), then building a context for routing the frame; and

(j) a step for routing the frame to the network in accordance with at least a portion of the second result.

2. The method of claim 1 wherein the flow lookup comprises indicia of a source identifier, a destination identifier, and a protocol identifier each in accordance with a respective field of the frame.

3. The method of claim 1 wherein the flow lookup comprises a flow identifier;

and the step for preparing a second lookup is performed in accordance with the flow identifier.

4. The method of claim 3 wherein the flow identifier corresponds to a transaction identifier of the frame.

5. The method of claim 1 wherein the second lookup comprises at least one of a subflow lookup and a virtual flow lookup.

6. The method of claim 1 wherein the step for routing further comprises:

a step for selecting a queue in accordance with the second result; and

a step for enqueueing at least the payload of the frame into the queue.

7. The method of claim 6 wherein the router further comprises a fabric for communication among the plurality of routine processors and the step for routing further comprises a step for communicating the frame via the fabric prior to performing the step for enqueueing.

8. The method of claim 6 wherein the router further comprises a fabric for communication among the plurality of routing processors and the step for routing further comprises a step for communicating the frame via the fabric after performing the step for enqueueing.

9. The method of claim 1 wherein:

the first result comprises a flag; and

if the flag is not asserted, (1) the step for preparing the second lookup, the step for obtaining the second result, and the step for routing are omitted; and

(2 ) the method further comprises a step for routing the frame in accordance with a portion of the first result.

10. The method of claim 1 wherein the portion of the second result comprises a resource identifier.

11. The method of claim 1 wherein the portion of the second result comprises an identifier of a queue corresponding to at least one of a resource identifier and a policy value.

12. The method of claim 11 wherein:

the portion of the second result comprises a policy value; and

the step for routing further comprises;

a step for preparing a header comprising indicia of the policy value;

a step for selecting a first queue in accordance with the policy value;

a step for placing an entry comprising a payload of the frame and the header into the first queue;

a step for transmitting the entry via a fabric;

a step for receiving the entry from the fabric;

a step for enqueueing a payload of the received entry into a second queue in accordance with the indicia of the policy value of the header; and

a step for routing to the network the payload of the received entry.

13. A method performed by a router for routing virtual and non-virtual frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, the method performed by each routing processor comprising:

(a) a step for receiving a first frame from the network;

(b) a step for parsing the first frame to determine a transaction identifier and a resource identifier;

(c) a step for receiving a second frame after the first frame has been routed to the network;

(d) astep for parsing the second frame to determine the transaction identifier;

(e) a step for preparing a flow lookup in accordance with the transaction identifier;

(f) a step for obtaining from a memory circuit a first result of the flow lookup and if the flow look up is incomplete, the frame is passed to a supervising processor that specifies a route or discards the frame;

(g) a step for preparing a subflow lookup in accordance with the first result if a subflow flag is set;

(h) a step for obtaining from the memory circuit a second result of the subflow lookup, the second result comprising the resource identifier;

(i) a step for determining if a context for the frame is available at a location other than where the frame is received;

(j) a step for building a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame;

(k) a step for marking the forward frame for handling by the other processor;

(l) a step for determining if a context for the frame is available at the processor receiving the frame and if the context is unavailable at the received location or another location as determined in step (i), then building a context for routing the frame; and

(m) a step for routing to the network at least the payload of the second frame in accordance with the resource identifier of the second result.

14. The method of claim 13 wherein the step for routing comprises:

a step for selecting a queue in accordance with the resource identifier of the second result; and

a step for enqueueing at least the payload of the second frame into the queue.

15. A method performed by a router for routing virtual and non-virtual frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, the method performed by each routing processor or comprising:

(a) a step for receiving a first frame from the network;

(b) a step for parsing the first frame to determine a transaction identifier and a resource identifier;

(c) a step for storing the resource identifier in association with the transaction identifier;

(d) a step for receiving a second frame after the first frame has been routed to the network;

(e) a step for parsing the second frame to determine the transaction identifier;

a step for recalling the resource identifier in accordance with the transaction identifier;

the step for recalling comprising;

(ei) a step for preparing a flow lookup in accordance with at least a portion of the second frame;

(eii) a step for obtaining from a memory circuit a first result of the flow lookup and if the flow look up is incomplete, the frame is passed to a supervising processor that specifies a route or discards the frame;

(eiii) a step for preparing a second lookup in accordance with the first result and if a sub-flow flag is set; and

(eiv) a step for obtaining from the memory circuit a second result of the second lookup, the second result comprising the recalled resource identifier;

(f) a step for determining if a context for the frame is available at a location other than where the frame is received;

(g) a step for building a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame;

(h) a step for marking the forward frame for handling by the other processor;

(i) a step for determining if a context for the frame is available at the processor receiving the frame and if the context is unavailable at the received location or another location as determined in step (f), then building a context for routing the frame; and

a step for routing to the network the second frame in accordance with the recalled resource identifier.

16. The method of claim 15 wherein:

the method further comprises a step for recalling a policy value in accordance with the resource identifier; and

the step for routing is for routing in further accordance with the recalled policy value.

17. The method of claim 15 wherein the step for routing further comprises:

a step for selecting a queue in accordance with the second result; and

a step for enqueueing at least a payload of the second frame into the queue.

18. The method of claim 17 wherein the router further comprises a fabric for communication among the plurality of routing processors and the step for routing further comprises communication of the second frame via the fabric prior to performing the step for enqueueing.

19. The method of claim 17 wherein the router further comprises a fabric for communication among the plurality of routing processors and the step for routing further comprises communication of the second frame via the fabric after performing the step for enqueueing.

20. A method performed by a router for routing virtual and non-virtual frames in a network, the router comprising a parser for preparing lookups, a memory circuit having routing information, a submitter for arbitrating among a plurality of queues to submit a lookup to the memory circuit, a frame processor for analyzing results of lookups, the method comprising:

(a) a step for parsing a frame received from the network;

a step for enqueueing into a first queue to the submitter a first lookup in accordance with a field value of the frame;

(b) a step for passing to the frame processor a first result of the first lookup to be analyzed (c) a step for enqueueing into a second queue to the submitter a second lookup in accordance with a result of analysis;

(d) a step for recirculating an entry enqueued into the second queue to delay routing; and

a step for routing at least a payload of the frame in accordance with a second result of the second lookup;

wherein the router determines if a context for the frame is available at a location other than where the frame is received; and

builds a forward frame, based on the first result and the second result, for processing b another processor at the other location where the context is a available for the frame; and

the frame is marked as a forward frame for handling by the other processor.

21. A router for routing virtual and non-virtual frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, each routing processor comprising:

means for receiving a frame from the network;

means for preparing a flow lookup in accordance with at least a portion of the frame;

means for obtaining from a means for storing a first result of the flow lookup;

means for preparing a second lookup in accordance with the first result;

means for obtaining from the means for storing a second result of the second lookup; and

means for routing the frame to the network in accordance with at least a portion of the second result;

wherein the router determines if a context for the frame is available at a location other than where the frame is received; and

builds a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame; and

the frame is marked as a forward frame for handling by the other processor.

22. The router of claim 21 wherein the flow hookup comprises indicia of a source identifier, a destination identifier, and a protocol identifier each in accordance with a respective field of the frame.

23. The router of claim 21 wherein the flow hookup comprises a flow identifier;

and the means for preparing a second lookup prepares the second lookup in accordance with the flow identifier.

24. The router of claim 23 wherein the flow identifier corresponds to a transaction identifier of the frame.

25. The router of claim 21 wherein the second lookup comprises at least one of a subflow lookup and a virtual flow lookup.

26. The router of claim 21 wherein the means for routing further comprises:

means for selecting a queue in accordance with the second result; and

means for enqueueing at least the payload of the frame into the queue.

27. The router of claim 26, wherein:

the router further comprises means for communicating among the plurality of routing processors; and

the means for routing routes the frame to another routing processor via the means for communicating prior to enqueueing the payload of the frame into the queue.

28. The router of claim 26 wherein:

the router further comprises means for communicating among the plurality of routing processors; and

the means for routing routes the frame to another routing processor via the means for communicating after enqueueing the payload of the frame into the queue.

29. The router of claim 21 wherein:

the first result comprises a flag; and

if the flag is not asserted, the frame is routed in accordance with a portion of the first result.

30. The router of claim 21 wherein the portion of the second result comprises a resource identifier.

31. The router of claim 21 wherein the portion of the second result comprises an identifier of a queue corresponding to at least one of a resource identifier and a policy value.

32. The router of claim 31 wherein:

the portion of the second result comprises a policy value; and

the means for routing further comprises;

means for preparing a header comprising indicia of the policy value;

means for selecting a first queue in accordance with the policy value;

means for placing an entry comprising a payload of the frame and the header into the first queue;

means for transmitting the entry via a means for communicating among the plurality of routing processors;

means for receiving the entry from the means for communicating;

means for enqueueing a payload of the received entry into a second queue in accordance with the indicia of the policy value of the header; and

means for routing to the network the payload of the received entry.

33. A router for routine frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, each routing processor comprising:

means for receiving a first frame from the network;

means for parsing the first frame to determine a transaction identifier and a resource identifier;

means for receiving a second frame after the first frame has been routed to the network;

means for parsing the second frame to determine the transaction identifier;

means for preparing a flow lookup in accordance with the transaction identifier;

means for obtaining from a memory circuit a first result of the flow lookup;

means for preparing a subflow lookup in accordance with the first result;

means for obtaining from the memory circuit a second result of the subflow lookup, the second result comprising the resource identifier; and

means for routing to the network at least the payload of the second frame in accordance with the resource identifier of the second result;

wherein the router determines if a context for the frame is available at a location other than where the frame is received; and

builds a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame; and

the frame is marked as a forward frame for handling by the other processor.

34. The router of claim 33 wherein the means for routing comprises:

means for selecting a queue in accordance with the resource identifier of the second result; and

means for enqueueing at least the payload of the second frame into the queue.

35. A router for routing frames in a network, the router comprising a plurality of routing processors, each routing processor for receiving frames from the network, and for routing frames to the network, each routing processor comprising:

means for receiving a first frame from the network;

means for parsing the first frame to determine a transaction identifier and a resource identifier;

means for storing the resource identifier in association with the transaction identifier;

means for receiving a second frame after the first frame has been routed to the network;

means for parsing the second frame to determine the transaction identifier;

means for recalling the resource identifier in accordance with the transaction identifier;

wherein the means for recalling further comprises;

means for preparing a flow lookup in accordance with at least a portion of the second frame;

means for obtaining from a memory circuit a first result of the flow lookup;

means for preparing a second lookup in accordance with the first result; and

means for obtaining from the memory circuit a second result of the second lookup, the second result comprising the recalled resource identifier; and

the router determines if a context for the frame is available at a location other than where the frame is received; and

builds a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame; and

the frame is marked as a forward frame for handling by the other processor; and

means for routing to the network the second frame in accordance with the recalled resource identifier.

36. The router of claim 35 wherein:

the router further comprises means for recalling a policy value in accordance with the resource identifier; and

the means for routing is for routing in further accordance with the recalled policy value.

37. The router of claim 35 wherein the means for routing further comprises:

means for selecting a queue in accordance with the second result; and

means for enqueueing at least a payload of the second frame into the queue.

38. The router of claim 37 wherein the router further comprises a fabric for communication among the plurality of routing processors and the means for routing further comprises communication of the second frame via the fabric prior to performing the means for enqueueing.

39. The router of claim 37 wherein the router further comprises a fabric for communication among the plurality of routing processors and the means for routing further comprises communication of the second frame via the fabric after performing the means for enqueueing.

40. A router for routing frames in a network, the router comprising:

a parser for parsing a frame received from the network and for preparing lookups;

a memory circuit having routing information;

a submitter for arbitrating among a plurality of queues to submit a lookup to the memory circuit;

a frame processor for analyzing results of lookups means for enqueueing into a first queue to the submitter a first lookup in accordance with a field value of the frame;

means for passing to the frame processor a first result of the first lookup to be analyzed;

means for enqueueing into a second queue to the submitter a second lookup in accordance with a result of analysis;

means for recirculating an entry enqueued into the second queue to delay routing; and

means for routing at least a payload of the frame in accordance with a second result of the second lookup;

wherein the router determines if a context for the frame is available at a location other than where the frame is received; and

builds a forward frame, based on the first result and the second result, for processing by another processor at the other location where the context is available for the frame; and

the frame is marked as a forward frame for handling by the other processor.

41. The router of claim 40 wherein the submitter comprises an arbitrating circuit coupled to each queue of the plurality of queues, wherein the arbitrating circuit selects an entry to provide to the memory circuit as a lookup in accordance with a priority among the queues of the plurality.

42. The router of claim 41 wherein the arbitrating circuit services the second queue at a higher priority than the first queue.

43. The router of claim 41 wherein at least one of the first result and the second result comprises a stall flag and the means for recirculating effects recirculation in response to the stall flag.