Method to enable routing protocol communication and transit packet forwarding between virtual routers

• US 20040073715A1
• Filed: 07/16/2002
• Published: 04/15/2004
• Est. Priority Date: 07/16/2002
• Status: Active Grant

• Current Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Original Assignee: Jeremy Benjamin As Receiver For Chiaro Networks, Ltd.
• Inventors: Folkes, Ronald P., Visser, Lance A.
• Granted Patent: US 7,209,976 B2
• Time in Patent Office: Days
• US Class Current: 709/250
• 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/40 Wormhole routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

Virtual routers within a single physical router share a centralized data plane containing a centralized switch fabric and a plurality of physical network interfaces, each assigned to only one virtual router. Using a logical cut-through device between a pair of virtual routers designated respectively client and server, packet forwarding information from the server is imported into the client, which creates, allocates, and maintains a data structure for the imported information, which then resides on the client interfaces. This imported forwarding information is then integrated into a single forwarding table that is used to recognize an incoming packet at the client and forward it appropriately out through a server interface with a single packet forwarding decision in a single transit through the switch fabric. Within a physical router, a client virtual router can communicate with multiple servers and can concurrently function as a server to multiple clients.

Claims

1. A method to enable routing protocol communication and transit packet forwarding between virtual routers within a single physical router sharing a centralized data plane and switch fabric and containing a plurality of physical network interfaces, each said interface being assigned to only one said virtual router, comprising the steps of:

using a logical cut-through device (CT) between a first virtual router designated as client and a second virtual router designated as server, importing packet forwarding table information from said server into said client;

creating, allocating, and maintaining at said client a data structure for said imported packet forwarding table information such that said imported information is integrated into a single forwarding table that resides on said interfaces assigned to said client; and

applying said imported packet forwarding table information at said client to recognize and forward an information packet out through an interface assigned to said server using a single packet forwarding decision in a single transit through said centralized switch fabric.

2. The method of claim 1 further comprising the steps of:

creating said logical cut-through device;

creating a route at said client that contains a first prefix that refers to a network destination and that specifies forwarding information that refers to said CT;

sending a request from said client to said server requesting prefixes related to said first prefix; and

exporting said related prefix(es) and forwarding information from said server to said client.

3. The method of claim 2 further comprising the steps of:

allocating and initializing at said server a tracking request structure related to said first prefix; and

creating and/or updating at said server a forwarding information base (FIB) entry related to said first prefix.

4. The method of claim 1 wherein a single packet longest prefix match lookup in said integrated forwarding table that includes imported packet forwarding table information forwards said packet out through said interface assigned to said server.

5. The method of claim 2 wherein said prefixes related to said first prefix comprise all those prefixes in said server that are either the same as, are covered by, or cover said first prefix.

6. The method of claim 3 wherein said client creates and/or deletes FIB entries related to local interfaces assigned to said client.

7. The method of claim 6 wherein prefixes related to said local interfaces take precedence over prefixes related to said imported packet forwarding table information at said client, such that said client cannot create an entry in said imported packet forwarding table information having a prefix that is the same as a prefix related to a local interface entry.

8. The method of claim 3 wherein said client creates a FIB entry related to said imported packet forwarding table information only if the prefix of such FIB entry is at least as specific as said corresponding prefix requested by said client from said server.

9. The method of claim 3 wherein, if said data structure at said client is updated, then:

said client informs said server of said updates;

any tracking request at said server relating to an entry deletion is withdrawn; and

said server ceases to send information to said client regarding deleted prefixes.

10. The method of claim 3 wherein, if said FIB information that said server is tracking for a client is updated, then

said server informs that client of said updates;

and

said client updates its forwarding table.

11. The method of claim 3 further comprising the steps of:

maintaining by said client a reference count on each imported prefix entry equal to the number of active first prefix entries related to said imported prefix;

such that

if an active first prefix entry is added, then said reference count is incremented for each related imported prefix entry;

whereas

if an active first prefix entry is deleted, then said reference count is decremented for each related imported prefix entry;

such that

if said reference count becomes zero for an imported prefix entry, then said client deletes that imported prefix entry.

12. The method of claim 2 wherein said logical cut-through device is permanently marked and is activated automatically at system boot time.

13. The method of claim 1 wherein said client is a client to multiple virtual router servers within a single physical router.

14. The method of claim 13 wherein said client is concurrently a server to multiple virtual router clients within said single physical router.

15. A system for enabling routing protocol communication and transit packet forwarding between virtual routers, comprising:

at least two virtual routers within a single physical router, said physical router incorporating;

a centralized data plane and switch fabric;

a plurality of physical network interfaces, each said interface being assigned to only one said virtual router; and

a logical cut-through device (CT) communicating between a first virtual router designated as client and a second virtual router designated as server, said client operable;

to import packet forwarding table information from said server; and

to apply said imported packet forwarding table information at said client to recognize and forward an information packet out through an interface assigned to said server using a single packet forwarding decision in a single transit through said centralized switch fabric.

16. The system of claim 15 further operable:

to create said logical cut-through device;

to create a route at said client that contains a first prefix that refers to a network destination and that specifies forwarding information that refers to said CT;

to send a request from said client to said server requesting prefixes related to said first prefix; and

to export said related prefix(es) and forwarding information from said server to said client.

17. The system of claim 16 further operable:

to allocate and initialize at said server a tracking request structure related to said first prefix; and

to create and to update at said server a forwarding information base (FIB) entry related to said first prefix.

18. The system of claim 15 wherein said client is operable to apply a single packet longest prefix match lookup in said imported packet forwarding table information to forward said packet out through said interface assigned to said server.

19. The system of claim 16 wherein said prefixes related to said first prefix comprise all those prefixes in said server that are either the same as, are covered by, or cover said first prefix.

20. The system of claim 17 wherein said client is operable to create and to delete FIB entries related to local interfaces assigned to said client.

21. The system of claim 20 wherein said client is not operable to create an entry in said imported packet forwarding table information having a prefix that is the same as a prefix related to a local interface entry.

22. The system of claim 17 wherein said client is operable to create a FIB entry related to said imported packet forwarding table information only if the prefix of such FIB entry is at least as specific as said corresponding prefix requested by said client from said server.

23. The system of claim 17 wherein, if said data structure at said client is updated, then:

said client is operable to inform said server of said updates;

said client is operable to withdraw any tracking request at said server relating to an entry deletion; and

said server is operable to cease sending information to said client regarding deleted prefixes.

24. The system of claim 17 wherein, if said FIB information that said server is tracking for a client is updated, then

said server is operable to inform that client of said updates;

and

said client is operable to update its forwarding table.

25. The system of claim 17 further operable:

to maintain in said client a reference count on each imported prefix entry equal to the number of active first prefix entries related to said imported prefix;

such that

if an active first prefix entry is added, then to increment said reference count for each related imported prefix entry;

whereas

if an active first prefix entry is deleted, then to decrement said reference count for each related imported prefix entry;

such that

if said reference count becomes zero for an imported prefix entry, then to delete that imported prefix entry.

26. The system of claim 16 further operable to permanently mark said logical cut-through device and to activate said logical cut-through device automatically at system boot time.

27. The system of claim 15 wherein said client is a client to multiple virtual router servers within a single physical router.

28. The system of claim 27 wherein said client is concurrently a server to multiple virtual router clients within said single physical router.