Forwarding for network devices

• US 7,525,949 B1
• Filed: 05/07/2002
• Issued: 04/28/2009
• Est. Priority Date: 05/07/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Retana, Alvaro, White, Russell, Trinh, Hoe, Ervin, Jimmy, Rampal, Sanjeev
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): NGUYEN, PHUONGCHAU BA
• Application Number:
  US10/140,613
• Time in Patent Office: 2,548 Days
• Field of Search: None
• US Class Current: 370/352
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

Abstract

Techniques for implementing forwarding in network devices are provided. Proxy addresses are used in place of next hop addresses so that a large routing table is not required. Pairs of proxy IP and MAC addresses can be used to allow this optimization to occur completely transparent to any other device in the network. One or more smaller tables can be utilized in place of a large routing table to more efficiently implement forwarding. Additionally, the technique can be utilized without requiring modification of other hardware devices in the network.

Claims

1. A method for implementing forwarding in a network device, comprising:

receiving at the network device, a message advertising a route address and a next hop address;

assigning at the network device, a proxy IP address associated with a proxy MAC address to the next hop address, wherein the proxy IP address is not associated externally with any other network device but is defined internally in the network device for forwarding; and

advertising the route address and the proxy IP address at the network device;

wherein the proxy IP address is advertised in place of the next hop address for all route addresses through the network device.

2. The method of claim 1, wherein packets that are received destined for the proxy IP address are sent to the next hop address.

3. The method of claim 1 further comprising storing the proxy IP address and the associated proxy MAC address in a first table and storing the proxy MAC address and the associated next hop address in a second table.

4. The method of claim 3 further comprising:

receiving a packet for forwarding at the network device; and

performing a lookup in the first and second tables to identify the next hop address.

5. An apparatus, comprising:

a processor that receives a message advertising a route address and a next hop address, assigns a proxy IP address associated with a proxy MAC address to the next hop address, and advertises the route address and the proxy IP address, wherein the proxy IP address is not associated externally with any other network device but is defined internally in the network device for forwarding and the proxy IP address is advertised in place of the next hop address for all route addresses through the network device; and

a memory that stores data for the processor.

6. The apparatus of claim 5 wherein said stored data comprises a first table storing the proxy IP address and the associated MAC address and a second table storing the MAC address and the associated next hop address.

7. An apparatus for implementing forwarding in a network device, comprising:

means for receiving at the network device, a message advertising a route address and a next hop address;

means for assigning at the network device, a proxy IP address associated with a proxy MAC address to the next hop address, wherein the proxy IP address is not associated externally with any other network device but is defined internally in the network device for forwarding and the proxy IP address is advertised in place of the next hop address for all route addresses through the network device; and

means for advertising the route address and the proxy IP address at the network device.

8. A method for implementing forwarding in a network device, comprising:

receiving at the network device, a first message advertising a route IP address and a next hop address;

associating at the network device, a proxy IP address with the next hop address, wherein the proxy IP address is associated with a proxy MAC address and the proxy MAC address is associated with the next hop address;

advertising at the network device, the route IP address and the proxy IP address;

upon receiving at the network device, an ARP request for the proxy IP address specified by a packet, responding with the proxy MAC address;

receiving at the network device, the packet that includes the proxy MAC address;

using the proxy MAC address to determine the next hop address at the network device; and

forwarding the packet from the network device to the next hop address.

9. The method of claim 8, wherein the proxy IP address is not associated externally with any other network device but is defined internally in the network device for forwarding.

10. The method of claim 8, further comprising removing the proxy MAC address from the packet.

11. The method of claim 8, further comprising inserting the next hop address into the packet.

12. The method of claim 8, wherein the proxy IP address is advertised in place of the next hop address for all route IP address through a network device.

13. The method of claim 8, wherein packets that are received destined for the proxy MAC address are sent to the next hop address.

14. The method of claim 8, wherein the proxy IP address and the proxy MAC address are stored in a proxy table.

15. The method of claim 8, wherein the proxy MAC address and the next hop address are stored in a next hop table.

16. The method of claim 8, wherein the proxy IP address is in the same subnet as a network to which the route IP address and the proxy IP address are advertised.

17. The method of claim 8, wherein the network device is a provider'"'"'s edge router and the route IP address and the proxy IP address are advertised to a customer'"'"'s edge router.

18. An apparatus, comprising:

a processor that receives a first message advertising a route IP address and a next hop address;

associates a proxy IP address with the next hop address, wherein the proxy IP address is associated with a proxy MAC address and the proxy MAC address is associated with the next hop address;

advertises the route IP address and the proxy IP address;

upon receiving an ARP request for the proxy IP address specified by a packet, responds with the proxy MAC address;

receives the packet that includes the proxy MAC address;

uses the proxy MAC address to determine the next hop address; and

forwards the packet to the next hop address; and

a memory that stores data for the processor.

19. An apparatus for implementing forwarding in a network device, comprising:

means for receiving at the network device, a first message advertising a route IP address and a next hop address;

means for associating at the network device, a proxy IP address with the next hop address, wherein the proxy IP address is associated with a proxy MAC address and the proxy MAC address is associated with the next hop address;

means for advertising at the network device, the route IP address and the proxy IP address;

means for, upon receiving at the network device, an ARP request for the proxy IP address specified by a packet, responding with the proxy MAC address;

means for receiving at the network device, the packet that includes the proxy MAC address;

means for using at the network device, the proxy MAC address to determine the next hop address; and

means for forwarding the packet from the network device to the next hop address.