Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
2000-04-10
2004-04-13
Luu, Le Hien (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C709S242000
Reexamination Certificate
active
06721800
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to network processor devices, routers, and the like and, more specifically, to a packet forwarding table and packet routing method which provides multiple next hop options for a single forwarding entry and the ability to weight the probability with which each next hop is to be chosen.
2. Discussion of the Prior Art
Traditional packet routing capability provided in network processor devices, routers, switches, and the like, typically utilize a network routing table having entries which provide a single next hop for each table entry.
FIG. 1
depicts a typical network routing scenario
10
. To route a packet from System C
13
to System
3
indicated as element
18
in
FIG. 1
, a traditional packet forwarding table would provide one path (e.g., via router R
2
) from router R
5
to R
1
. In the example network routing scenario of
FIG. 1
, it would be desirable to have the ability to route through R
3
as well, or possibly even through R
4
.
In general, in a network processor, the ability to provide multiple next hop options coupled with the ability to weight which router in the network handles the amount of or what type of packets is very desirable.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a network processor with a network routing table having entries that include one or more next hops in addition to cumulative probability data for each corresponding next hop.
It is another object of the present invention to provide a method of randomly generating next hop seed values associated with a packet to be forwarded in a network and determining which next hop is chosen based on cumulative probability data for each corresponding next hop and the randomly generated next hop seed values.
According to the invention, there is provided a system and method for forwarding packets in a network processor (NP) device comprising: providing entries in a packet forwarding table for mapping a destination address associated with a packet to be forwarded to multiple, weighted next hop options in a networking environment; computing a weighting parameter based on data associated with the packet to be forwarded; and, routing the packet via one of the multiple next hop option selected in accordance with the computed weighting parameter. Preferably, the computing step includes applying a hash function to data associated with the packet to be forwarded to generate a corresponding hash value associated with that packet. For instance, in the case of a networking environment that includes an IP network, the data associated with the packet may comprise an IP source address and IP destination address of the packet to be forwarded. Each of the mapped multiple next hop options for each table entry includes a corresponding threshold value. Thus, to determine which next hop is selected in a packet forwarding operation, a comparison is made between the computed hash value and each corresponding threshold value.
The features of providing the ability for a media-speed, bandwidth conserving network processor device to select from multiple next hop options in a packet forwarding operation and providing the ability to weight the probability of which next hop will be chosen is extremely advantageous.
REFERENCES:
patent: 5822301 (1998-10-01), Arnold et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6314093 (2001-11-01), Mann et al.
patent: 6363319 (2002-03-01), Hsu
patent: 6400681 (2002-06-01), Bertin et al.
Basso Claude
Gallo Anthony Matteo
Vaidhyanathan Natarajan
Luu Le Hien
Scully Scott Murphy & Presser
LandOfFree
System using weighted next hop option in routing table to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System using weighted next hop option in routing table to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System using weighted next hop option in routing table to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3227949