Method of providing virtual router functionality

• US 7,894,451 B2
• Filed: 12/30/2005
• Issued: 02/22/2011
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Gentry, Denton, Parker, David K.
• Primary Examiner(s): Patel, Jayanti K
• Assistant Examiner(s): Wyllie, Christopher T
• Application Number:
  US11/324,159
• Publication Number:
  US 20070153808A1
• Time in Patent Office: 1,880 Days
• Field of Search: 370/230, 370/352, 370/356, 370/379, 370/389, 370/392, 370/393, 455/450, 713/182
• US Class Current: 370/395.32
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• 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 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/354 for supporting virtual local area networks [VLAN]
• CPC Class Codes: H04L 49/70 Virtual switches

Abstract

A method of presenting different virtual routers to different end users, classes of service, or packets is provided. An incoming packet is received having a VLAN field and at least one additional field. A key is formed from the VLAN field and at least one other packet field, and mapped into a virtual router identifier (VRID) using an indirection mapping process. The VRID identifies a particular virtual router configuration from a plurality of possible virtual router configurations. A networking device is configured to have the particular virtual router configuration identified by the VRID, and the packet is then forwarded by the configured device.

Claims

1. A method, performed in, by or for a networking device, of presenting different virtual routers to different end users, classes of service, or packets comprising the steps of:

receiving an incoming packet having a VLAN field and at least one additional packet field;

forming a key from the VLAN field and the at least one additional packet field;

mapping the key into a virtual router identifier using a two-step indirection mapping process, comprising a first step and a second step, the virtual router identifier identifying a particular virtual router configuration from amongst a plurality of possible virtual router configurations, each of which is characterized by a routing table, for use in routing packets at OSI layer three or higher, selected from a plurality of possible routing tables;

the first step of the two-step indirection mapping process comprising accessing a table having a plurality of entries, each having a content value and an index value, and locating a matching entry having a content value that matches the key;

the second step of the two-step indirection mapping process comprising mapping the index value of the matched entry into the virtual router identifier by using the index value to identify an entry in an associated data store element containing or including the virtual router identifier;

configuring the device to have the particular configuration identified by the virtual router identifier by selecting the routing table that characterizes the particular configuration identified by the virtual router identifier for use in routing the packet at OSI layer three or higher; and

routing the packet at OSI layer three or higher using the selected routing table that characterizes the particular configuration identified by the virtual router identifier,

wherein the number of possible virtual routers is increased by mapping many different key values into the same virtual router identifier through appropriate settings of the index values.

2. The method of claim 1 wherein the key is a masked key.

3. The method of claim 1 wherein the key is an unmasked key.

4. The method of claim 1 wherein the key is masked using a key type determined responsive to one or more packet fields.

5. The method of claim 1 wherein the at least one additional packet field comprises a VMAN field.

6. The method of claim 1 wherein the at least one additional packet field comprises VMAN and ingress port fields.

7. The method of claim 1 wherein the at least one additional packet field comprises an ingress port field.

8. The method of claim 1 wherein the table is stored on a CAM, and the number of virtual routers is only limited by the memory size of the CAM.

9. The method of claim 3 wherein the key is masked by wildcarding one or more fields of entries of a ternary CAM.

12. The method of any one of claims 1, 10 and 11 wherein the VLAN field is an ingress VLAN field.

13. The method of any one of claims 1, 10 and 11 wherein the VLAN field is an extended or super VLAN.

15. The method of any one of claims 1- and 11 wherein the routing table characterizing the particular configuration identified by the virtual router identifier is implicitly selected by determining, responsive to the virtual router identifier, a starting address of a sequence of commands that are executed by a packet processor to route the packet.

10. A method, performed in, by or for a networking device, of presenting different virtual routers to different end users, classes of service, or packets comprising the steps of:

receiving an incoming packet having a VLAN field and at least one additional packet field;

forming a key from the VLAN field and the at least one additional packet field;

masking the key using a key type determined responsive to one or more packet fields;

mapping the masked key into a virtual router identifier using a two-step indirection mapping process, comprising a first step and a second step, the virtual router identifier identifying a particular virtual router configuration from amongst a plurality of possible virtual router configurations, each of which is characterized by a routing table, for use in routing packets at OSI layer three or higher, selected from a plurality of possible routing tables;

the first step of the two-step indirection mapping process comprising accessing a table having a plurality of entries, each having a content value and an index value, and locating a matching entry having a content value that matches the key;

the second step of the two-step indirection mapping process comprising mapping the index value of the matched entry into the virtual router identifier by using the index value to identify an entry in an associated data store element containing or including the virtual router identifier;

configuring the device to have the particular configuration identified by the virtual router identifier by selecting the routing table that characterizes the particular configuration identified by the virtual router identifier for use in routing the packet at OSI layer three or higher; and

routing the packet at OSI layer three or higher using the selected routing table that characterizes the particular configuration identified by the virtual router identifier,

wherein the routing table characterizing the particular configuration identified by the virtual router identifier is implicitly selected by determining, responsive to the virtual router identifier, a starting address of a sequence of commands that are executed by a packet processor to route the packet.

14. The method of any one of claims 10, 11 and 4 wherein the key is masked by wildcarding one or more fields of the key responsive to the key type.

16. The method of any one of claims 10 and 4 wherein the key type is determined by inputting an ingress port field of the packet to a lookup table.

11. A method, performed in, by or for a networking device, of presenting different virtual routers to different end users, classes of service, or packets comprising the steps of:

receiving an incoming packet having a VLAN field and at least one additional packet field;

forming a key from the VLAN field and at least one additional packet field;

masking the key using a key type determined responsive to the ingress port field;

mapping the masked key into a virtual router identifier using a two-step indirection mapping process, comprising a first step and a second step, the virtual router identifier identifying a particular virtual router configuration from amongst a plurality of possible virtual router configurations, each of which is characterized by a routing table, for use in routing packets at OSI layer three or higher, selected from a plurality of possible routing tables;

the first step of the two-step indirection mapping process comprising accessing a table having a plurality of entries, each having a content value and an index value, and locating a matching entry having a content value that matches the key;

the second step of the two-step indirection mapping process comprising mapping the index value of the matched entry into the virtual router identifier by using the index value to identify an entry in an associated data store element containing or including the virtual router identifier;

configuring the device to have the particular configuration identified by the virtual router identifier by selecting the routing table that characterizes the particular configuration identified by the virtual router identifier for use in routing the packet at OSI layer three or higher; and

routing the packet at OSI layer three or higher using the selected routing table that characterizes the particular configuration identified by the virtual router identifier,

wherein the key type is determined by inputting an ingress port field of the packet to a lookup table, and wherein the number of possible virtual routers is increased by mapping many different key values into the same virtual router identifier through appropriate settings of the index values.

17. A system, in or associated with a networking device, of presenting different virtual routers to different end users, classes of service, or packets comprising:

first logic for receiving an incoming packet having a VLAN field and at least one additional packet field;

second logic forming a key from the VLAN field and the at least one additional packet field;

means for mapping the key into a virtual router identifier using a two-step indirection mapping process, comprising a first step and a second step, the virtual router identifier identifying a particular virtual router configuration from amongst a plurality of possible virtual router configurations, each of which is characterized by a routing table, for use in routing packets at OSI layer three or higher, selected from a plurality of possible routing tables;

the first step of the two-step indirection mapping process comprising accessing a table having a plurality of entries, each having a content value and an index value, and locating a matching entry having a content value that matches the key;

the second step of the two-step indirection mapping process comprising mapping the index value of the matched entry into the virtual router identifier by using the index value to identify an entry in an associated data store element containing or including the virtual router identifier; and

one or more packet processors for (1) configuring the device to have the particular configuration identified by the virtual router identifier by selecting the routing table that characterizes the particular configuration identified by the virtual router identifier for use in routing the packet at OSI layer three or higher; and

(2) routing the packet at OSI layer three or higher using the selected routing table that characterizes the particular configuration identified by the virtual router identifier,

wherein the key is masked using a key type, the key type is determined by inputting an ingress port field of the packet to a lookup table, and wherein the number of possible virtual routers is increased by mapping many different key values into the same virtual router identifier through appropriate settings of the index values.

18. The system of claim 17 wherein the table is stored on a CAM, the first step of the two-step indirection mapping process comprises having a CAM search for and locate an entry whose content value matches the key, and the associated data store element comprises an associated RAM.

19. The system of claim 17 wherein the table is stored in a RAM, the first step of the two-step indirection mapping process comprises applying a hash function to the key to determine a table index for a starting entry, and then searching the table beginning with the starting entry to locate an entry whose content value matches the key.

20. The system of claim 18 wherein the CAM is a binary CAM.

21. The system of claim 18 wherein the CAM is a ternary CAM.

22. The system of claim 17 wherein the key is a masked key.

23. The system of claim 17 wherein the key is an unmasked key.

24. The system of claim 22 wherein the key is masked using a key type determined responsive to one or more packet fields.

26. The system of claim 22 wherein the key is masked by wildcarding one or more fields of entries of a ternary CAM.

27. The system of claim 17 wherein the routing table characterizing the particular configuration identified by the virtual router identifier is implicitly selected by determining, responsive to the virtual router identifier, a starting address of a sequence of commands that are executed by a packet processor to route the packet.

25. The system of 24 wherein the key is masked by wildcarding one or more fields of the key responsive to key type.