Redirect checking in a network device

• US 7,983,278 B1
• Filed: 07/18/2006
• Issued: 07/19/2011
• Est. Priority Date: 01/18/2002
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ferguson, Dennis C., Lim, Raymond Marcelino Manese, Libby, Jeffrey Glenn
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US11/458,225
• Time in Patent Office: 1,827 Days
• Field of Search: 370/236, 370/238, 370/392, 370/400
• US Class Current: 370/401
• 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 includes an input device configured to receive a data packet, where the input device includes a number of interfaces and the data packet includes a source address and a destination address. The network device also includes processing logic configured to generate forwarding information identifying a next hop for the data packet and determine whether an interface on which the data packet was received is a same interface on which the data packet is to be forwarded to the next hop. The processing logic is also configured to determine whether the data packet originated from a device that is part of a same subnet as the next hop.

Claims

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

receiving a data packet, from a station located in a subnet, on a first one of a plurality of interfaces;

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

determining whether the first one of the plurality of interfaces, on which the data packet was received, is the same as an interface, of the plurality of interfaces, on which the data packet is to be forwarded to on the next hop;

forwarding the data packet to the next hop based on the determining;

determining whether the data packet was forwarded via the first one of the plurality of interfaces;

determining whether the station, originating the data packet, belongs to a same subnet as the next hop, based on a hash value representing the subnet of the next hop;

generating a redirect message when the data packet is received and forwarded via the first one, of the plurality of interfaces, and the station, originating the data packet, belongs to the same subnet as the next hop; and

transmitting the generated redirect message to the station originating the data packet.

2. The method of claim 1, where the determining whether the data packet was received and forwarded via the first one of the plurality of interfaces comprises:

identifying an incoming interface index associated with the first interface;

identifying an outgoing interface index associated with the next hop; and

comparing the incoming interface index and the outgoing interface index.

3. The method of claim 1, where the data packet includes a source address, including a number of bits, and the determining whether the station originating the data packet belongs to a same subnet as the next hop includes:

selecting a portion of the number of the bits of the source address of the data packet;

generating a hash value using a hash function and the selected portion of the number of bits;

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

determining that the station, originating the data packet, belongs to the same subnet as the next hop, when the generated hash value equals the stored hash value.

4. The method of claim 3, where the stored hash value is based on a first address associated with the next hop and is generated using the hash function and the portion of the number of bits of the first address used to generate the generated hash value.

5. The method of claim 1, where the redirect message further includes:

next hop information for future data packets having a same destination address as the data packet.

6. The method of claim 1, further comprising:

bypassing the generation of the redirect message when either;

the data packet was not received and forwarded via the first interface;

or

the station originating the data packet does not belong to the same subnet as the next hop.

7. A network device, comprising:

an input device to receive a plurality of data packets, each of the plurality of data packets including a source address and a destination address, from a plurality of interfaces associated with the input device and the input device including a memory and a processor, the memory containing instructions that cause the processor to;

generate forwarding information identifying a next hop associated with at least one of the plurality of data packets;

determine whether an index interface, of the plurality of interfaces, on which the at least one of the plurality of data packets was received, is the same as an index interface, of the plurality of interfaces, on which the at least one of the plurality of data packets are to be forwarded to on the next hop; and

determine whether a device, originating the at least one of the plurality of data packets, belongs to the same subnet as the next hop, based on a hash value representing a subnet of the next hop;

generate a redirect message based on both determinations; and

transmit the generated redirect message to the device originating the at least one of the plurality of data packets.

8. The network device of claim 7, where the processor is further to:

generate the redirect message when the interface of the plurality of interfaces on which the at least one of the plurality of data packets was received is the same as the interface of the plurality of interfaces on which the at least one of the plurality of data packets is to be forwarded and the device originating the at least one of the plurality of data packets belongs to a same subnet as the next hop.

9. The network device of claim 8, where the redirect message further includes next hop information for future ones of the plurality of data packets having a same destination address as the at least one of the plurality of data packets received at the network device.

10. The network device of claim 8, where the processor is further to:

bypass the generation of the redirect message when either the interface, of the plurality of interfaces, on which the at least one of the plurality of data packets was received is not the same as the interface of the plurality of interfaces on which the at least one of the plurality of data packets is to be forwarded or the device, originating the at least one of the plurality of data packets, belongs to a same subnet as the next hop.

11. The network device of claim 7, where when determining whether the device, originating the at least one of the plurality of data packets, belongs to a same subnet as the next hop, the processor is to:

identify an incoming interface index associated with the interface of the plurality of interfaces;

identify an outgoing interface index associated with the next hop; and

compare the incoming interface indices to the outgoing interface indices.

12. The network device of claim 7, where the source address includes a number of bits and when determining whether the device, originating the at least one of the plurality of data packets, belongs to a same subnet as the next hop, the processor is to:

select a portion of the number of bits of the source address of the data packet;

generate a hash value using a hash function and the selected portion of the number bits;

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

determine that the device, originating the at least one of the plurality of data packets, belongs to a same subnet as the next hop when the generated hash value equals the stored hash value.

13. The network device of claim 12, where the stored hash value is based on a first address associated with the next hop and is generated using the hash function and the portion of the number of bits of the first address used to generate the generated hash value.

14. A network device, including one or more processors, comprising:

an input device to receive a data packet from an interface, the data packet including a source address and a destination address and the input device including a memory containing instructions that when executed by the one or more processors, cause the one or more processors to;

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

retrieve redirect checking information based on the data forwarding information;

determine, using the redirect checking information, whether the data packet is to be forwarded via the interface at which the data packet was received;

perform, using the redirect checking information, a subnet address check associated with the data packet, the subnet address check including;

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

comparing the generated hash value to a predetermined hash value; and

forward a message to a host processor indicating that a redirect message, associated with the received data packet, is required when the data packet is to be forwarded via the interface at which the data packet was received and when the subnet address check indicates that a device originating the data packet belongs to a same subnet as the next hop.

15. The network device of claim 14, where the host processor is to:

receive the message from the one or more processors;

generate a redirect message; and

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

16. The network device of claim 14, where the redirect checking information comprises:

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

17. The network device of claim 14, where when determining whether the data packet is to be forwarded via the interface at which the data packet was received, the one or more processors are to:

compare an incoming interface index and an outgoing interface index.

18. The network device of claim 14, where when performing the subnet address check, the one or more processors are to:

read a prefix length value, of a prefix of the source address of the data packet, in order to determine which bits of the prefix will be used to generate a hash value;

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

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

compare the generated hash value to a stored hash value in the redirect checking information; and

determine that the device originating the data packet belongs to the same subnet as the next hop when the generated hash value and stored hash value are equal.

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

a processor; and

a memory to store instructions that when executed by the processor cause the processor 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;

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

retrieve information indicating whether the data packet is to be forwarded on the first one of the plurality of interfaces;

determine, using the retrieved information, whether the data packet is to be forwarded via the first one of the plurality of interfaces, at which the data packet was received;

perform, using the retrieved information, a subnet address check associated with the data packet, when performing the subnet address check, the processor is to;

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

compare the generated hash value to a predetermined hash value; and

generate a redirect message, associated with the data packet, when the data packet is to be forwarded on the first one of the plurality of interfaces, and when the subnet address check indicates that the data packet originated from a device that belongs to the same subnet as the next hop; and

transmit the generated redirect message to the device originating the data packet.

20. A network device, including at least one processor, comprising:

an input unit to receive data packets, each data packet including a source address having a number of bits; and

a memory containing instructions that when executed by the at least one processor, cause the at least one processor to;

generate data forwarding information for a received data packet;

compare an incoming interface on which the data packet was received to an outgoing interface on which the data packet is to be forwarded;

generate a hash value using a portion of the number of bits of the source address of the data packet;

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

determine whether to transmit a redirect message based on both the comparison of the incoming interface to the outgoing interface and the comparison of the generated hash value to the stored hash value.

21. The network device of claim 20, where when the incoming interface and the outgoing interface are the same and the generated hash value equals the stored hash value, the at least one processor is further to indicate that a redirect message is required.

22. The network device of claim 21, further comprising:

a host processor, where when the redirect message is required, the at least one processor is to transmit a redirect message to the host processor.

23. The network device of claim 22, where the host processor is to forward a redirect message to a device 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.