Arrangement in a router for distributing a routing rule used to generate routes based on a pattern of a received packet

• US 20040223491A1
• Filed: 05/06/2003
• Published: 11/11/2004
• Est. Priority Date: 05/06/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Molteni, Marco, Villari, Massimo, Wetterwald, Patrick, Levy-Abegnoli, Eric M.
• Granted Patent: US 7,760,701 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04W 8/087 for preserving data network PoA address despite hand-offs

Abstract

A router is configured for sharing routing rules with other routers, the routing rules defining aggregated routes according to a prescribed topology. Each routing rule, used by the router for routing a packet having a corresponding matching destination address prefix, specifies a corresponding address prefix pattern rule for extracting an identified pattern from a portion of the destination address, and a gateway address pattern rule for generating a gateway address, for a gateway providing reachability to the destination address, based on applying the identified pattern to a specified portion of the gateway address. The router generates a routing update message that describes the address prefix pattern rule and the gateway address pattern rule, and outputs the routing update message to a second router according to a prescribed distance vector routing protocol (e.g., Multiprotocol Extension for Border Gateway Protocol).

Claims

1. A method in an Internet Protocol (IP) based router, the method comprising:

storing a routing rule that defines routes aggregated according to a prescribed topology, the routing rule specifying an address prefix pattern rule for extracting an identified pattern from a first portion of a destination address, and a gateway address pattern rule for generating a gateway address, specifying a gateway providing reachability to the destination address, based on applying the identified pattern to a specified second portion of the gateway address;

generating a routing update message that describes the address prefix pattern rule and the gateway address pattern rule; and

outputting the routing update message to a second router according to a prescribed routing protocol, for use by the second router in routing a corresponding received packet according to the prescribed topology.

2. The method of claim 1, wherein the generating step includes:

inserting a gateway field that specifies attributes of the gateway address pattern rule; and

inserting an address prefix field that specifies attributes of the address prefix pattern rule.

3. The method of claim 2, wherein at least one of the gateway field and the address field specify the respective attributes in terms of arguments, the generating step further including inserting an argument list that specifies values for the respective arguments.

4. The method of claim 3, wherein the first portion and the second portion identify respective distinct portions of an address.

5. The method of claim 2, wherein the generating step further includes configuring the routing update message as a prescribed reachability message specifying a prescribed address family configured for recognizing the routes according to the rule, the outputting step including outputting the routing update message, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family.

6. The method of claim 1, wherein the outputting includes outputting the routing update message as specifying a prescribed address family, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family and that the routing rule that defines the routes aggregated according to the prescribed topology.

7. An Internet Protocol (IP) based router comprising:

a table configured for storing a routing rule that defines routes aggregated according to a prescribed topology, the routing rule specifying an address prefix pattern rule for extracting an identified pattern from a first portion of a destination address, and a gateway address pattern rule for generating a gateway address, specifying a gateway providing reachability to the destination address, based on applying the identified pattern to a specified second portion of the gateway address;

a routing protocol resource configured generating a routing update message, that describes the address prefix pattern rule and the gateway address pattern rule, for use by a second router in routing a corresponding received packet according to the prescribed topology; and

an IP interface configured for outputting the routing update message to the second router according to a prescribed routing protocol.

8. The router of claim 7, wherein the routing protocol resource is configured for inserting into the routing update message a gateway field that specifies attributes of the gateway address pattern rule, and an address prefix field that specifies attributes of the address prefix pattern rule.

9. The router of claim 8, wherein at least one of the gateway field and the address field specify the respective attributes in terms of arguments, the routing protocol resource configured for inserting into the routing update message an argument list that specifies values for the respective arguments.

10. The router of claim 9, wherein the first portion and the second portion identify respective distinct portions of an address.

11. The router of claim 8, wherein the routing protocol resource further is configured for configuring the routing update message as a prescribed reachability message specifying a prescribed address family configured for recognizing the routes according to the rule, routing protocol resource configured for generating the routing update message, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family.

12. The router of claim 7, wherein the routing protocol resource is configured for generating the routing update message as specifying a prescribed address family, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family and that the routing rule that defines the routes aggregated according to the prescribed topology.

13. A computer readable medium having stored thereon sequences of instructions for outputting a routing update message by an Internet Protocol (IP) based router, the sequences of instructions including instructions for:

storing a routing rule that defines routes aggregated according to a prescribed topology, the routing rule specifying an address prefix pattern rule for extracting an identified pattern from a first portion of a destination address, and a gateway address pattern rule for generating a gateway address, specifying a gateway providing reachability to the destination address, based on applying the identified pattern to a specified second portion of the gateway address;

generating a routing update message that describes the address prefix pattern rule and the gateway address pattern rule; and

outputting the routing update message to a second router according to a prescribed routing protocol, for use by the second router in routing a corresponding received packet according to the prescribed topology.

14. The medium of claim 13, wherein the generating step includes:

inserting a gateway field that specifies attributes of the gateway address pattern rule; and

inserting an address prefix field that specifies attributes of the address prefix pattern rule.

15. The medium of claim 14, wherein at least one of the gateway field and the address field specify the respective attributes in terms of arguments, the generating step further including inserting an argument list that specifies values for the respective arguments.

16. The medium of claim 15, wherein the first portion and the second portion identify respective distinct portions of an address.

17. The medium of claim 14, wherein the generating step further includes configuring the routing update message as a prescribed reachability message specifying a prescribed address family configured for recognizing the routes according to the rule, the outputting step including outputting the routing update message, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family.

18. The medium of claim 13, wherein the outputting includes outputting the routing update message as specifying a prescribed address family, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family and that the routing rule that defines the routes aggregated according to the prescribed topology.

19. An Internet Protocol (IP) based router comprising:

means for storing a routing rule that defines routes aggregated according to a prescribed topology, the routing rule specifying an address prefix pattern rule for extracting an identified pattern from a first portion of a destination address, and a gateway address pattern rule for generating a gateway address, specifying a gateway providing reachability to the destination address, based on applying the identified pattern to a specified second portion of the gateway address;

means for generating a routing update message that describes the address prefix pattern rule and the gateway address pattern rule; and

means for outputting the routing update message to a second router according to a prescribed routing protocol, for use by the second router in routing a corresponding received packet according to the prescribed topology.

20. The router of claim 19, wherein the generating means is configured for inserting a gateway field that specifies attributes of the gateway address pattern rule, and inserting an address prefix field that specifies attributes of the address prefix pattern rule.

21. The router of claim 20, wherein at least one of the gateway field and the address field specify the respective attributes in terms of arguments, the generating means configured for inserting an argument list that specifies values for the respective arguments.

22. The router of claim 21, wherein the first portion and the second portion identify respective distinct portions of an address.

23. The router of claim 20, wherein the generating means is configured for configuring the routing update message as a prescribed reachability message specifying a prescribed address family configured for recognizing the routes according to the rule, the generating means configured for generating the routing update message, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family.

24. The router of claim 19, wherein the generating means is conifuged for specifying within the routing update message a prescribed address family, according to Multiprotocol Extension for Border Gateway Protocol (MP-BGP), based on determining that the second router recognizes the prescribed address family and that the routing rule that defines the routes aggregated according to the prescribed topology.