Redirect checking in a network device

• US 7,082,134 B1
• Filed: 01/18/2002
• Issued: 07/25/2006
• Est. Priority Date: 01/18/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ferguson, Dennis C., Lim, Raymond Marcelino Manese, Libby, Jeffrey Glenn
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US10/050,106
• Time in Patent Office: 1,649 Days
• Field of Search: 370/389, 370/392, 370/400, 370/410
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3072 Packet splitting

Abstract

A network device for performing redirect checking includes an input device and processing logic. The input device receives a data packet on a first one of a number of interfaces. The data packet includes source and destination addresses. The processing logic assigns an incoming interface to the data packet and generates forwarding information identifying a next hop for the data packet. The processing logic also identifies an outgoing interface based on the next hop and determines whether the incoming interface index is equal to the outgoing interface index. The processing logic also determines whether the data packet originated from a station that is part of the same subnet as the next hop. When both of these conditions are met, the processing logic generates a redirect message.

Claims

1. A method for redirect checking in a network device, comprising:

receiving a data packet on a first one of a plurality of interfaces;

assigning an incoming interface index to the data packet;

generating forwarding information identifying a next hop for the data packet;

identifying an outgoing interface index based on the next hop;

determining whether the incoming interface index is equal to the outgoing interface index;

determining whether the data packet originated from a station that is part of a same subnet as the next hop; and

generating a redirect message when the incoming interface index is equal to the outgoing interface index and the data packet originated from a station that is part of a same subnet as the next hop.

2. The method of claim 1, wherein the identifying an outgoing interface includes:

retrieving a stored outgoing interface index based on the forwarding information.

3. The method of claim 1, wherein the data packet includes a source address and the determining whether the data packet originated from a station that is part of a same subnet as the next hop includes:

selecting a number of the most significant bits of the source address of the data packet,

passing the selected bits through a hash function to generate a hash value,

comparing the generated hash value to a stored hash value, and

determining that the data packet originated from a station that is part of the same subnet as the next hop when the generated hash value equals the stored hash value.

4. The method of claim 3, wherein the hash function is x⁹+x⁴+1.

5. The method of claim 3, wherein the stored hash value is based on a first address associated with the next hop and is generated using the same hash function and the same number of most significant bits of the first address as the generated hash value.

6. The method of claim 1, further comprising:

transmitting the redirect message to the station originating the data packet, the redirect message including next hop information for future data packets having a same destination address as the data packet transmitted to the network device.

7. The method of claim 1, further comprising:

bypassing the generation of the redirect message when either the incoming interface index is not equal to the outgoing interface index or the data packet originated from a station that is not part of the same subnet as the next hop.

8. A network device, comprising:

an input device configured to receive a data packet on a first one of a plurality of interfaces, the data packet including a source address and a destination address; and

processing logic configured to;

assign an incoming interface index to the data packet,

generate forwarding information identifying a next hop for the data packet,

identify an outgoing interface index based on the next hop,

determine whether the incoming interface index is equal to the outgoing interface index,

determine whether the data packet originated from a station that is part of a same subnet as the next hop, and

generate a redirect message when the incoming interface index is equal to the outgoing interface index and the data packet originated from a station that is part of a same subnet as the next hop.

9. The network device of claim 8, wherein when identifying an outgoing interface index, the processing logic is configured to:

retrieve a stored outgoing interface index based on the forwarding information.

10. The network device of claim 8, wherein when determining whether the data packet originated from a station that is part of a same subnet as the next hop, the processing logic is configured to:

select a number of the most significant bits of the source address of the data packet,

pass the selected bits through a hash function to generate a hash value,

compare the generated hash value to a stored hash value, and

determine that the data packet originated from a station that is part of the same subnet as the next hop when the generated hash value equals the stored hash value.

11. The network device of claim 10, wherein the hash function is x⁹+x⁴+1.

12. The network device of claim 10, wherein the stored hash value is based on a first address associated with the next hop and is generated using the same hash function and the same number of most significant bits of the first address as the generated hash value.

13. The network device of claim 8, wherein the processing logic is further configured to:

transmit the redirect message to the station originating the data packet, the redirect message including next hop information for future data packets having a same destination address as the data packet transmitted to the network device.

14. The network device of claim 8, wherein the processing logic is further configured to:

bypass the generation of the redirect message when either the incoming interface index is not equal to the outgoing interface index or the data packet originated from a station that is not part of the same subnet as the next hop.

15. A network device, comprising:

an input device configured to receive a data packet, the data packet including a source address and a destination address;

processing logic configured to assign an incoming interface index to the data packet based on the interface on which the data packet was received;

route lookup logic configured to;

receive the incoming interface index,

generate data forwarding information identifying a next hop for the data packet,

forward the data forwarding information and the incoming interface index; and

an output device configured to;

receiving the data forwarding information and the incoming interface index,

retrieve redirect checking information based on the data forwarding information,

determine, using the redirect checking information, whether the data packet is to be forwarded on the same interface on which it was received, and

determine, using the redirect checking information, whether the data packet originated from a station that is part of a same subnet as the next hop for the data packet.

16. The network device of claim 15, further comprising:

a host processor;

wherein the output device is further configured to;

forward a message to the host processor indicating that a redirect message associated with the received data packet is required when the data packet is to be forwarded on the same interface on which it was received and the data packet originated from a station that is part of the same subnet as the next hop.

17. The network device of claim 16, wherein the host processor is configured to:

receive the message,

generate a redirect message, and

transmit the redirect message to the station originating the data packet.

18. The network device of claim 15, wherein the redirect checking information comprises:

an outgoing interface index, a hash value and a prefix length value associated with the hash value.

19. The network device of claim 18, wherein when determining whether the data packet is to be forwarded on the same interface on which it was received, the output device is configured to:

compare the incoming interface index and the outgoing interface index.

20. The network device of claim 18, wherein when determining whether the data packet originated from a station that is part of a same subnet as the next hop, the output device is configured to:

read the prefix length value,

select a number of bits of the source address of the data packet based on the prefix length value,

generate a hash value using the selected bits of the source address,

compare the generated hash value to the stored hash value, and

determine that the data packet originated from a station that is part of the same subnet as the next hop when the generated and stored hash values are equal.

21. The network device of claim 15, wherein when determining whether the data packet originated from a station that is part of a same subnet as the next hop, the output device is configured to:

generate a hash value using a portion of the source address of the data packet, and

compare the hash value to a predetermined hash value.

22. A system for performing redirect checking in a network device, comprising:

means for receiving a data packet on a first one of a plurality of interfaces;

means for generating forwarding information for the data packet;

means for retrieving stored information associated with a next hop for the data packet;

means for determining whether the data packet is to be forwarded on the first interface using the retrieved information;

means for determining whether the data packet originated from a station that is part of a same subnet as the next hop; and

means for generating a redirect message when the data packet is to be forwarded on the first interface and the data packet originated from a station that is part of the same subnet as the next hop.

23. A network device, comprising:

a memory configured to store incoming interface index information;

an input unit configured to receive data packets, each data packet including a source address, the input unit including;

processing logic configured to access the memory to identify an incoming interface index for a received data packet;

a route lookup unit configured to;

receive the incoming interface index for the data packet,

generate data forwarding information for the data packet, and

forward the incoming interface index and the data forwarding information; and

an output unit configured to receive the incoming interface index and the data forwarding information, the output unit including;

a memory configured to store an output interface index, a hash value and a prefix length value for each of a plurality of output interfaces, and

processing logic configured to;

retrieve an output interface index, a hash value and a prefix length value based on the data forwarding information for the data packet,

compare the incoming interface index and the outgoing interface index,

generate a hash value using a number of bits of the source address of the data packet, based on the prefix length value, and

compare the generated hash value to the stored hash value.

24. The network device of claim 23, wherein when the incoming interface index and the outgoing interface index are equal and the generated hash value and the stored hash value are equal, the processing logic is further configured to indicate that a redirect message is required.

25. The network device of claim 24, further comprising:

a host processor, wherein when the redirect message is required, the output unit transmits a redirect indication to the host processor.

26. The network device of claim 25, wherein the host processor is configured to forward a redirect message to the station that originated the data packet, the redirect message including next hop information for future data packets having a same destination address as the data packet transmitted to the network device.

27. The network device of claim 23, wherein the hash value is generated using a hash function of x⁹+x⁴+1.