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

• US 7,760,701 B2
• Filed: 05/06/2003
• Issued: 07/20/2010
• Est. Priority Date: 05/06/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Molteni, Marco, Villari, Massimo, Thubert, Pascal, Wetterwald, Patrick, Levy-Abegnoli, Eric M.
• Primary Examiner(s): Mills; Donald L
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US10/429,851
• Publication Number:
  US 20040223491A1
• Time in Patent Office: 2,632 Days
• Field of Search: 370/351, 370/395.5, 370/395.31, 370/254, 370/400, 370/401, 370/389, 370/237, 370/238, 370/256, 370352-356, 709/238, 709/239, 709/240, 709/241, 709/242, 709/243
• US Class Current: 370/351
• 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 in the router 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 prescribed function for generation of the gateway address;

generating in the router a routing update message that describes a representation of the address prefix pattern rule and the gateway address pattern rule; and

the router 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 or 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 prescribed function 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 defines the routes aggregated according to the prescribed topology.

19. The method of claim 1, wherein the outputting includes outputting the routing update message to the second router according to the prescribed routing protocol, for implementation of the routing rule by the second router in routing the corresponding received packet according to the prescribed topology.

22. The method of claim 1, wherein:

the gateway is implemented as a gateway router;

the destination address is for a destination node reachable via the gateway router; and

the gateway address and the destination address are distinct IPv6 addresses.

23. The method of claim 1, wherein the gateway address pattern rule is for calculating the gateway address based on inserting the identified pattern into the specified second portion of the gateway address.

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 prescribed function for generation of the gateway address;

a routing protocol resource configured generating a routing update message, that describes a representation of 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 or 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 prescribed function 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 defines the routes aggregated according to the prescribed topology.

20. The router of claim 7, wherein the IP interface outputs the routing update message to the second router according to the prescribed routing protocol for implementation of the routing rule by the second router in routing the corresponding received packet according to the prescribed topology.

24. The router of claim 7, wherein:

the gateway is implemented as a gateway router;

the destination address is for a destination node reachable via the gateway router; and

the gateway address and the destination address are distinct IPv6 addresses.

25. The router of claim 7, wherein the gateway address pattern rule is for calculating the gateway address based on inserting the identified pattern into the specified second portion of the gateway address.

13. 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 prescribed function for generation of the gateway address;

means for generating a routing update message that describes a representation of 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.

14. The router of claim 13, 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.

15. The router of claim 14, wherein at least one of the gateway field or 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.

16. The router of claim 15, wherein the first portion and the prescribed function identify respective distinct portions of an address.

17. The router of claim 14, 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.

18. The router of claim 13, wherein the generating means is configured 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 defines the routes aggregated according to the prescribed topology.

21. The router of claim 13, wherein the means for outputting outputs the routing update message to the second router according to the prescribed routing protocol for implementation of the routing rule by the second router in routing the corresponding received packet according to the prescribed topology.

26. The router of claim 13, wherein:

the gateway is implemented as a gateway router;

the destination address is for a destination node reachable via the gateway router; and

the gateway address and the destination address are distinct IPv6 addresses.

27. The router of claim 13, wherein the gateway address pattern rule is for calculating the gateway address based on inserting the identified pattern into the specified second portion of the gateway address.