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

• US 6,147,993 A
• Filed: 10/14/1997
• Issued: 11/14/2000
• Est. Priority Date: 10/14/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kloth, Ray, Edsall, Thomas J., Cafiero, Luca
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US08/951,820
• Time in Patent Office: 1,127 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/402, 370/409, 370/393, 370/398
• 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 frame 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 a first packet encapsulated within the first frame;

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

determining whether the shortcut entry has been established for a subsequent packet of the subsequent frame; 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 encapsulated within the first frame.

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

receiving the first frame at the switch;

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

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

performing a forwarding decision at the router to route the first frame 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 that has changed about the first frame 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 frame is sent, and source and destination medium access control addresses for the subsequent frame.

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;

modifying the subsequent frame with the rewrite information; and

forwarding the modified subsequent frame over the network.

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

a forwarding table containing information specifying whether a medium access control (MAC) address of the frame 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 frame;

a forwarding engine coupled to the forwarding table and configured to access the forwarding table to determine whether a subsequent packet of a subsequent frame 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 configured 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 12 wherein the candidate entry comprises the flow information, the xtag value and a find_-- sc bit.

14. 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 addresses of the subsequent frame.

15. The switch of claim 14 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.

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

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

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

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

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

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

passing the candidate packet from the switch to a router;

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

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

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

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

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,

routing 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.

20. The method of claim 19 wherein the step of inserting comprises the steps of:

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.