Patent ID: 6778532
Filing Date: 2004-08-17
Classification: H04L

Abstract:
A packet relaying apparatus for relaying a packet in a plurality of interconnected networks and for searching route information of a received multicast packet by using as a search key a receiver address and a sender address of the received multicast packet and transferring the multicast packet to one or a plurality of ports in accordance with the route information, the packet relaying apparatus comprises:storage means for storing a search table of a two-branch tree structure corresponding to a bit pattern of a route address coupling the receiver address and the sender address in this order; and a circuit for searching a search tree of the two-branch tree structure stored in said storage means in accordance with a value of each bit checked starting from an m-th bit of the route address, by developing (m-th power of 2) two-branch tree nodes corresponding to the upper m bits of the route address on said storage means at predetermined positions, with each node being set in one-to-one correspondence with each value capable being taken by the 0-Ui to (mâˆ’1)-th bits of the route address, and by selecting one of the developed nodes in accordance with values of the 0th to (mâˆ’1)-th bits of the route address for searching the search tree.