Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-08-02
2004-03-23
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S432000
Reexamination Certificate
active
06711172
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to network packet routing.
Computer networks enable computers on opposite sides of the world to exchange e-mail, internet web-pages, chat messages, and other electronic information. Typically, programs divide electronic information into packets for transmission over a network. A packet is like an envelope with a return address (the packet source) and a mailing address (the packet destination). Instead of streets and zip codes, however, packets use IP (Internet Protocol) addresses to identify source and destination computers. An IP address can be 32-bits long. Instead of writing out all 32 1s or 0s or an equivalent decimal number, IP addresses are commonly written as a set of four digits ranging from 1 to 255 (e.g., 128.233.45.100).
Much as an envelope reaches its mailing address via a series of post offices, a network packet reaches a destination address by winding its way through network computers known as routers. Each router examines a packet's destination address and tries to determine how to advance the packet to another router to reach its ultimate destination.
A sender can send a packet using unicasting or multicasting techniques. Unicasting delivers a message from a single source to single destination. To send a packet using unicasting, a sender sets a packet's destination address to a particular network computer's IP address.
Multicasting delivers a message from a single source to multiple destinations. To send a packet using multicasting, a sender sets a packet's destination address to an IP group address. A router receiving a packet having a group address can forward the message to individual members of the group.
SUMMARY OF THE INVENTION
In general, in one aspect, 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.
Embodiments may include one or more of the following features. The search may be a longest match search. The network domain may comprise a Protocol Independent Multicasting (PIM) sparse-mode domain. Defining a range of addresses may include determining group addresses serviced by a rendezvous point, for example, by looking up the group addresses in an RP-set that describes group addresses serviced by rendezvous points.
Defining a range of addresses may be done by adding an (*,G/prefix) state to the router forwarding table for the range of addresses. Determining addresses may include determining the source and or group destination address of the network packet. The addresses may be Internet Protocol (IP) address. Performing the search may include determining whether the match is an (S,G) state, an (*,G) state, and/or an (*,G/prefix) state.
The router forwarding table may include group and source address pairs and corresponding states. The corresponding states may include input and output interfaces. Transmitting the packet to the border router may include transmitting the packet via an output interface corresponding to the state determined by the longest match search.
In general, in another aspect, the invention features 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 includes 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.
In general, in another aspect, a computer program, disposed on a computer readable medium, includes instructions for causing a router to route network packets to a border router joining different network domains. The program includes instructions that define a range of addresses for the border router in a router forwarding table, 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.
Advantages of the invention will become apparent in view of the following description, including the figures, and the claims.
REFERENCES:
patent: 5241682 (1993-08-01), Bryant
patent: 5430727 (1995-07-01), Callon
patent: 5917820 (1999-06-01), Rekhter
patent: 6078590 (2000-06-01), Farinacci
patent: 6130890 (2000-10-01), Leinwand
patent: 6272139 (2001-08-01), Soncodi
patent: 6275492 (2001-08-01), Zhang
patent: 6331983 (2001-12-01), Haggerty
patent: 6473421 (2002-10-01), Tappan
D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering. M. Handley, V. Jacobson, C. Liu, P. Sharma and L. Wei, Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, Jun. 1998.
Nortel Networks Corp.
Patel Ajit
Shah Chirag
Steubing McGuinness & Manaras LLP
LandOfFree
Network packet routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network packet routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network packet routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253029