Network packet routing

• US 6,711,172 B1
• Filed: 08/02/1999
• Issued: 03/23/2004
• Est. Priority Date: 08/02/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Li, Yunzhou
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SHAH, CHIRAG G
• Application Number:
  US09/366,136
• Time in Patent Office: 1,695 Days
• Field of Search: 370/389, 370/400, 370/401, 370/351, 370/432, 370/475, 370/390, 370/230, 370/237, 709/230, 709/238, 709/241
• US Class Current: 370/401
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A method of routing network packets to a border router joining different network domains includes defining a range of addresses for the border router in a router forwarding table, receiving a network packet, determining addresses included in the network packet, performing a search on the router forwarding table using the determined addresses, and transmitting the packet to the border router if the defined range of addresses matches for the determined addresses.

Claims

1. A method of routing network packets to a border router joining different network domains, the method comprising:

defining a range of addresses for the border router in a router forwarding table including determining group addresses serviced by a rendezvous point;

receiving a network packet;

determining at least one address included in the network packet;

performing a search on the router forwarding table using the at least one determined addresses; and

transmitting the packet to the border router if the defined range of addresses matches for the at least one determined address.

2. The method of claim 1 wherein performing a search comprises performing a longest match search.

3. The method of claim 1 wherein one of the network domains comprises a Protocol Independent Multicasting (PIM) sparse-mode domain.

4. The method of claim 1 wherein determining group addresses comprises looking up the group addresses in an RP-set that describes group addresses serviced by rendezvous points.

5. The method of claim 1 wherein defining a range of addresses comprises adding an (*,G/prefix) state to the router forwarding table for the range of addresses.

6. The method of claim 1 wherein determining at least one address comprises determining the source address of the network packet.

7. The method of claim 1 wherein determining at least one address comprises determining the destination address of the network packet.

8. The method of claim 1 wherein determining at least one address comprises determining an Internet Protocol (IP) address.

9. The method of claim 1 wherein performing the search comprises determining whether the match is an (S,G) state.

10. The method of claim 1 wherein performing the search comprises determining whether the match is an (*,G) state.

11. The method of claim 1 wherein performing the match comprises determining whether the match is an (*,G/prefix) state.

12. The method of claim 1 wherein the router forwarding table comprises group and source address pairs and corresponding Protocol Independent Multicasting (PIM) states.

13. The method of claim 1 wherein the router forwarding table comprises group and source address pairs and corresponding input and output interfaces.

14. The method of claim 13 wherein transmitting the packet to the border router comprises transmitting the packet via an output interface corresponding to the state determined by the longest match search.

15. A method of routing network packets to a Protocol Independent Multicasting (PIM) border router that joins a PIM sparse-mode domain with a different network domain, the method comprising:

receiving a PIM (*,*,RP) state transmitted by the PIM border router to a rendezvous point RP;

determining group addresses handled by the rendezvous point; and

defining a (*,G/prefix) state in a router forwarding table based on the determined group addresses of the PIM rendezvous point RP.

16. The method of claim 15 further comprising:

receiving a network packet;

performing a longest match search using the network packet'"'"'s group address; and

if the longest match search corresponds to the defined (*,G/prefix) state, transmitting the network packet to the border router.

17. A computer program, disposed on a computer readable medium, for routing network packets to a border router joining different network domains, the program including instructions for causing a router to:

define a range of addresses for the border router in a router forwarding table including determining group addresses serviced by a rendezvous point;

receive a network packet;

determine addresses included in the network packet;

perform a search on the router forwarding table using the determined addresses; and

transmit the packet to the border router if the defined range of addresses matches for the determined addresses.

18. The computer program of claim 17 wherein the search comprises a longest match search.

19. The computer program of claim 17 wherein the instructions that define a range of addresses comprise instructions that add an (*,G/prefix) state to the router forwarding table for the range of addresses.