Method and apparatus for implementing forwarding decision shortcuts at a network switch

• US 6,842,453 B1
• Filed: 07/14/2000
• Issued: 01/11/2005
• Est. Priority Date: 10/14/1997
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Cafiero, Luca, Kloth, Ray
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US09/617,581
• Time in Patent Office: 1,642 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/402, 370/403, 370/393
• US Class Current: 370/392
• CPC Class Codes: H04L 49/251 Cut-through or wormhole routing
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A shortcut technique implements forwarding decision shortcuts at a switch for frames routed between subnetworks of a computer network. The switch monitors the flow of a first frame of a particular type to and from the router, which renders a forwarding decision for routing the frame. The switch records information stored in network layer header of a packet encapsulated within the first frame, and then compares that information with the information stored in network layer headers of packets contained within subsequent frames of that particular type. Forwarding decisions for these subsequent frames are then rendered by hardware logic circuits of the switch rather than by the router.

Claims

1. A method for implementing forwarding decision shortcuts at a switch for packets routed between subnetworks of a computer network, the method comprising the steps of:

rendering, at a router, a forwarding decision for routing a first packet of a particular type over the network;

establishing a shortcut entry in a shortcut table of the switch using information contained in a network layer header of the first packet;

receiving a subsequent packet of the particular type at the switch;

determining whether the shortcut entry has been established for the subsequent packet; and

if so,

implementing a forwarding decision shortcut for the subsequent packet at the switch based upon contents of the shortcut entry;

wherein the shortcut entry contains a pointer between a medium access control address and the information contained in the network layer header of the first packet.

2. The method of claim 1, wherein the step of rendering comprises the steps of:

receiving the first packet at the switch;

inserting predetermined information pertaining to the first packet into the shortcut table of the switch;

passing the first packet from the switch to the router; and

performing a forwarding decision at the router to route the first packet over the network.

3. The method of claim 2, wherein the step of inserting comprises the steps of:

extracting a flow from the network layer header of the first packet;

retrieving an xtag from the forwarding table of the switch;

asserting a find_sc bit; and

loading the flow, the xtag and the find_sc bit into the shortcut table.

4. The method of claim 3, wherein the step of establishing comprises the steps of:

determining whether the find_sc bit is asserted;

if so, noting information associated with the first packet that has changed as a result of the forwarding decision performed by the router; and

writing the changed information into the shortcut entry as rewrite information.

5. The method of claim 4, wherein the rewrite information of the shortcut entry comprises an index identifying the physical location of the switch to which the subsequent packet is sent, and source and destination medium access control addresses for the subsequent packet.

6. The method of claim 4, wherein the step of implementing the forwarding decision shortcut comprises the steps of:

driving the rewrite information from the shortcut table to a rewrite engine at the physical location identified by the index; and

modifying other information associated with the subsequent packet with the rewrite information.

7. A switch for implementing forwarding decision shortcuts for packets routed between subnetworks of a computer network, a forwarding decision for a first packet being rendered by a router, the switch comprising:

a forwarding table containing information specifying whether a medium access control (MAC) address associated with the packet identifies a special destination, the forwarding table further containing information specifying a pointer between the MAC address and network layer flow information contained in the packet;

a forwarding engine coupled to the forwarding table and to access the forwarding table to determine whether a subsequent packet is a candidate for a forwarding decision shortcut;

a shortcut table containing the flow information; and

a shortcut engine coupled to the shortcut table and forwarding engine, the shortcut engine to access the shortcut table to one of insert a candidate entry into the shortcut table and establish a shortcut entry in the shortcut table.

8. The switch of claim 7, wherein the forwarding engine and the shortcut engine are implemented as a state machine.

9. The switch of claim 7, wherein the flow information comprises a network layer destination address.

10. The switch of claim 9, wherein the flow information further comprises a network layer source address.

11. The switch of claim 10, wherein the flow information further comprises a protocol port number.

12. The switch of claim 9, wherein the pointer comprises an xtag value.

13. The switch of claim 7, wherein the special destination comprises one of the router or a multicast packet.

14. The switch of claim 12, wherein the candidate entry comprises the flow information, the xtag value and a find_sc bit.

15. The switch of claim 12, wherein the shortcut entry comprises the flow information, the xtag value and rewrite information, the rewrite information including source and destination data link layer address associated with the subsequent packet.

16. The switch of claim 15, further comprising:

a bus of the switch;

interface circuitry for coupling the bus to the router; and

a port card having at least one port coupling the bus to physical media of the network.

17. The switch of claim 16, further comprising an in-line rewrite engine associated with each port of the port card, the in-line rewrite engine modifying shortcutted frame with the rewrite information.

18. The switch of claim 16, further comprising a central rewrite engine coupled to the bus, the central rewrite engine modifying shortcutted frames with the rewrite information.

19. A mechanism for implementing forwarding decision shortcuts at a switch for packets of a particular type routed between subnetworks of a computer network, the mechanism comprising:

means for receiving a candidate packet of the particular type at the switch;

means for inserting predetermined information pertaining to the candidate packet into a shortcut table of the switch;

means for passing the candidate packet from the switch to a router;

means for rendering, at the router, a forwarding decision for the candidate packet;

means for passing the candidate packet from the router to the switch as an enable packet of the particular type;

means for comparing the inserted information with respective predetermined information pertaining to the enable packet;

means for, if the information matches, establishing a shortcut entry in the shortcut table;

means for receiving a subsequent packet of the particular type at the switch;

means for determining whether the shortcut entry has been established for the subsequent packet; and

means for routing the subsequent packet from the switch over the network based upon contents of the shortcut entry if the shortcut entry has been established for the subsequent packet;

wherein the shortcut entry contains a pointer between a medium access control address and information contained in a network layer header of the subsequent packet.

20. The mechanism of claim 19, wherein the means for inserting comprises:

means for extracting a flow from a network layer header of the candidate packet;

means for retrieving an xtag from a forwarding table of the switch;

means for asserting a find_sc bit; and

means for loading the flow, the xtag and the find_sc bit into the shortcut table.

21. A mechanism for implementing forwarding decision shortcuts at a switch for packets routed between subnetworks of a computer network, the mechanism comprising:

means for rendering, at a router, a forwarding decision for routing a first packet of a particular type over the network;

means for establishing a shortcut entry in a shortcut table of the switch using information contained in a network layer header of the first packet;

means for receiving a subsequent packet of the particular type at the switch;

means for determining whether the shortcut entry has been established for the subsequent packet; and

means for implementing a forwarding decision shortcut for the subsequent packet at the switch based upon contents of the shortcut entry if the shortcut entry has been established for the subsequent packet;

wherein the shortcut entry contains a pointer between a medium access control address and the information contained in the network layer header of the first packet.

22. The mechanism of claim 21, wherein the means for rendering comprises:

means for receiving the first packet at the switch;

means for inserting predetermined information pertaining to the first packet into the shortcut table of the switch;

means for passing the first packet from the switch to the router; and

means for performing a forwarding decision at the router to route the first packet over the network.

23. The mechanism of claim 22, wherein the means for inserting comprises:

means for extracting a flow from the network layer header of the first packet;

means for retrieving an xtag from the forwarding table of the switch;

means for asserting a find_sc bit; and

means for loading the flow, the xtag and the find_sc bit into the shortcut table.

24. The mechanism of claim 23, wherein the means for establishing comprises:

means for determining whether the find_sc bit is asserted;

means for noting information that has changed pertaining to the first packet as a result of the forwarding decision performed by the router; and

means for writing the changed information into the shortcut entry as rewrite information.

25. The mechanism of claim 24, wherein the rewrite information of the shortcut entry comprises an index identifying the physical location of the switch to which the subsequent packet is sent, and source and destination medium access control addresses for the subsequent packet.

26. The mechanism of claim 24, wherein the means for implementing the forwarding decision shortcut comprises:

means for driving the rewrite information from the shortcut table to a rewrite engine at the physical location identified by the index; and

means for modifying information pertaining to the subsequent packet with the rewrite information.

27. Computer-readable memory comprising computer-executable instructions that when executed implement forwarding decision shortcuts at a switch for packets routed between subnetworks of a computer network, the instructions, when executed, also causing:

rendering, at a router, of a forwarding decision for routing a first packet of a particular type over the network;

establishing of a shortcut entry in a shortcut table of the switch using information contained in a network layer header of the first packet;

receiving of a subsequent packet of the particular type at the switch;

determining of whether the shortcut entry has been established for the subsequent packet of the subsequent frame; and

if so,

implementing of a forwarding decision shortcut for the subsequent packet at the switch based upon contents of the shortcut entry;

wherein the shortcut entry contains a pointer between a medium access control address and the information contained in the network layer header of the first packet.

28. Memory of claim 27, wherein the rendering of the forwarding decision comprises:

receiving of the first packet at the switch;

inserting of predetermined information pertaining to the first packet into the shortcut table of the switch;

passing of the first packet from the switch to the router; and

performing of a forwarding decision at the router to route the first packet over the network.

29. Memory of claim 28, wherein the inserting of the predetermined information comprises:

extracting of a flow from the network layer header of the first packet;

retrieving of an xtag from the forwarding table of the switch;

asserting of a find_sc bit; and

loading of the flow, the xtag and the find_sc bit into the shortcut table.

30. Memory of claim 29, wherein the establishing of the shortcut entry comprises:

determining of whether the find_sc bit is asserted;

if so, noting of information that has changed pertaining to the first packet as a result of the forwarding decision performed by the router; and

writing of the changed information into the shortcut entry as rewrite information.

31. Memory of claim 30, wherein the rewrite information of the shortcut entry comprises an index identifying the physical location of the switch to which the subsequent packet is sent, and source and destination medium access control addresses for the subsequent packet.

32. Memory of claim 30, wherein the implementing of the forwarding decision shortcut comprises:

driving of the rewrite information from the shortcut table to a rewrite engine at the physical location identified by the index; and

modifying of information pertaining to the subsequent packet with the rewrite information.

33. Computer-readable memory comprising computer-readable instructions that when executed cause implementing of forwarding decision shortcuts at a switch for packets of a particular type routed between subnetworks of a computer network, the instructions when executed also causing:

receiving of a candidate packet of the particular type at the switch;

inserting of predetermined information pertaining to the candidate packet into a shortcut table of the switch;

passing of the candidate packet from the switch to a router;

rendering, at the router, of a forwarding decision for the candidate packet;

passing of the candidate packet from the router to the switch as an enable packet of the particular type;

comparing of the inserted information with respective predetermined information pertaining to the enable packet;

if the information matches, establishing of a shortcut entry in the shortcut table;

receiving of a subsequent packet of the particular type at the switch;

determining of whether the shortcut entry has been established for the subsequent packet; and

if so,

routing of the subsequent packet from the switch over the network based upon contents of the shortcut entry;

wherein the shortcut entry contains a pointer between a medium access control address and information contained in a network layer header of the subsequent packet.

34. Memory of claim 33, wherein the inserting of the predetermined information comprises:

extracting of a flow from a network layer header of the candidate packet;

retrieving of an xtag from a forwarding table of the switch;

asserting of a find_sc bit; and

loading of the flow, the xtag and the find_sc bit into the shortcut table.

35. A mechanism for implementing forwarding decision short-cuts at a switch for packets of a particular type routed between subnetworks of a computer network, the mechanism comprising:

a reception mechanism that receives a candidate packet of the particular type at the switch;

a processor that is to maintain, in operation, a shortcut table of the switch, the processor also to insert, in operation, predetermined information pertaining to the candidate packet into the shortcut table;

a transmission mechanism that transmits the candidate packet from the switch to a router, the router to render a forwarding decision for the candidate packet;

another transmission mechanism that transmits the candidate packet from the router to the switch as an enable packet of the particular type;

the processor also to compare, in operation, the inserted information with respective predetermined information pertaining to the enable packet, and if the information matches, to establish, in operation, a shortcut entry in the shortcut table;

the reception mechanism also receiving a subsequent packet of the particular type at the switch;

the processor additionally to determine, in operation, whether the shortcut entry has been established for the subsequent packet; and

a routing mechanism that routes the subsequent packet from the switch over the network based upon contents of the shortcut entry, if the shortcut entry has been established for the subsequent packet;

wherein the shortcut entry contains a pointer between a medium access control address and information contained in a network layer header of the subsequent packet.

36. The mechanism of claim 35, wherein the processor is to insert the predetermined information, in operation, by:

extracting a flow from a network layer header of the candidate packet;

retrieving an xtag from a forwarding table of the switch;

asserting a find_sc bit; and

loading the flow, the xtag and the find_sc bit into the shortcut table.