Packet relaying apparatus and high speed multicast system

• US 6,778,532 B1
• Filed: 09/02/1999
• Issued: 08/17/2004
• Est. Priority Date: 10/05/1998
• Status: Expired due to Term

• Current Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Original Assignee: Hitachi Information Technology Co. Ltd. (Hitachi, Ltd.), Hitachi, Ltd.
• Inventors: Matsuyama, Nobuhito, Akahane, Shinichi, Aimoto, Takeshi, Sugai, Kazuo, Sako, Yoshihito, Sekino, Hiroshi
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): Blount, Steven
• Application Number:
  US09/389,301
• Time in Patent Office: 1,811 Days
• Field of Search: 370/390, 370/392, 370/400, 370/401, 370/408, 370/432, 370/389, 370/431, 370/471, 370/255, 370/256
• US Class Current: 370/392
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

In a high speed multicast route searching method of searching information of a transmission port to which a received multicast packet is next transferred: a route address is formed by coupling a receiver address and a sender address in this order; one p-th power-of-2-branch tree node is configured by a collection of one two-branch tree node and two-branch tree nodes of p−1 stages totalling ((p-th power of 2)−1) nodes just under the one two-branch tree node to form a p-th power-of-2-branch tree which is stored in a memory; not one bit but consecutive p bits of the route address coupling the receiver address and sender address in a received multicast packet in this order are checked at the same time; and in accordance with the values of the consecutive bits, a search tree stored in the memory is searched. In this manner, a search process can be completed by tracing nodes (the number of bits of a search key divided by p) times at a maximum, independently from the number of entries.

Claims

1. 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.

2. 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 p-th power-of-2-branch tree structure (p being a natural number) 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 p-th power-of-2-branch tree structure stored in said storage means in accordance with values of p bits checked starting from an m-th bit of the route address, by developing (m-th power of

     2) p-th power-of-2-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 being taken by the O-th 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.