×

Multi-resolution tree for longest match address lookups

  • US 6,563,823 B1
  • Filed: 10/30/1997
  • Issued: 05/13/2003
  • Est. Priority Date: 10/30/1997
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for forwarding packets, comprising the steps of:

  • a) receiving an address for a packet;

    matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;

    a) initializing a current partition member to a first partition member;

    b) translating said address into a p-structure index utilizing partition information stored for said current partition member;

    c) storing a decision value associated with said index;

    d) determining whether a pointer is associated with said index;

    e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;

    f) repeating steps b) to e) until there is no pointer associated with said index;

    retrieving the decision value associated with said longest prefix; and

    forwarding said packet in according with said decision value.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×