Patent ID: 6874033

Claim:
A network forwarding device connecting a plurality of networks comprising: a port to which one of said networks is connected; a network interface connected to said port and controlling an interface with the network connected to said port; and a routing processor connected to said network interface via an intra-device communication line and performing routing of a: packet received from said network interface; wherein said routing processor includes: path information generating unit for generating path information comprising a plurality of 2-branch tree nodes, each corresponding to a value which can be taken by each bit of a destination address of said packet; path information holding means for holding said path information generated; and next-path searching means for checking each bit of said destination address of said packet received from a high-order bit one by one and determining a path to which said packet received is to be forwarded next by retrieving said 2-branch tree nodes of said path information corresponding to each bit value of said destination address; and wherein, said path information generating unit combines a total of (2 P −1) 2-branch tree nodes comprising one 2-branch tree node and 2-branch tree nodes of (p−1) levels connected to said one 2-branch tree node, into one 2 P -branch tree node and outputs said one 2 P -branch tree node as said path information to said path information holding means, wherein said p is an integer equal to or larger than 2, and wherein said next-path searching means checks p bits of said destination address of said packet received at one time and retrieves 2 P -branch tree node corresponding to values of said p bits.