Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-09-02
2004-08-17
Patel, Ajit (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S390000, C370S389000
Reexamination Certificate
active
06778532
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a packet relaying apparatus for relaying a packet in a plurality of interconnected networks, and more particularly to a method of searching a next node to which a multicast packet is transmitted.
As the number of users of the Internet increases and the traffic (packets) on the Internet rapidly increases, the scale and speed of the Internet are becoming large and high. In the current Internet (packet communication network by Internet Protocol: hereinafter called an IP network), not only conventional data communication applications, but also real time applications such as Internet phones and Internet broadcasting are used to provide a voice communication function and a broadcasting function. Under such circumstances, IP multicast techniques for the IP network are expected as effective techniques for the distribution of multimedia data such as moving images, voices and contents on the Internet.
Support and high speed operation of a packet relaying apparatus (router) constituting the IP network are the main issue of IP multicast techniques.
In unicast communication for transmitting a packet from one terminal to another specific terminal, a router searches from a routing table, route information corresponding to a receiver IP address contained in a header of a received packet, and transmits the received packet to the next router. The route information includes an IP address of the next router or a terminal and a transmission port number of the router. A route search for unicast will be briefly described.
The routing table stores a plurality of information groups for each receiver IP address, the information groups including a corresponding sub-network address, a sub-net mask length, and the route information. This information group is called an entry. The sub-network is a partial collection of terminals such as a receiver corporate network. The sub-network address is an address group which is obtained by coupling IP addresses of the partial collection as address information. The sub-net mask length is a value indicating how many upper bits of an IP address are an identifier of the sub-network. The router compares the sub-network address in the entry with the effective upper bits, masked by the sub-net mask length in the entry, of a receiver IP address contained in a received packet. The router-uses the route information in the coincident entry as the search result. Since the entry is configured in the unit of sub-network, the number of entries in the routing table can be reduced considerably and the search process is made efficient. If it is judged that a plurality of entries are coincident, the route information in the entry having the longest sub-net mask length is used as the search result. In the following, this search is called a longest coincidence search.
In multicast communication for transmitting a packet from one terminal to a plurality of specific terminals, each entry of the routing table includes a sender sub-net address, an address mask, a multicast group address and route information. The multicast group address is an identifier assigned to a plurality of receiver collections (hereinafter called a multicast group) to which the sender transmits the packet. A router searches the routing table by using as a search key a multicast group address in the sender IP address and receiver IP addresses in the header field of a received packet. In multicast, the route information of an entry with a search coincidence is constituted of a plurality of transmission port numbers. In accordance with the transmission port numbers, the router copies the received packet and transmits it to the specific multicast group. If the load of the search process and copy process is heavy and the performance of multicast communication is low, the total performance of the router which executes a multicast packet transfer may be degraded. From this reason, a high speed operation is required similar to a usual unicast packet relaying process.
A high speed operation to be attained through a router load dispersion method is described, for example, in JP-A-6-197111 laid-open on Jul. 15, 1994 (hereinafter called “first related art”). This first related art aims to realize a router capable of a high speed relay operation through a load dispersion method. A plurality of packet relay modules are connected to a bus, and each packet relay module provides a packet relay function by referring to routing table information supplied from a management unit connected to the bus. If the number of packet relay modules is increased, the performance can be improved. The packet relay module of the first related art includes: a routing processing unit which derives the header of a received packet and performs a search process for a packet receiver; and a transfer processing unit which stores the received packet in a memory and transfers the received packet to another packet relay module designated by the search result. Since the different processing units take partial charge of the relay function, the packet relay process can be speeded up. However, the first related art does not describe a high speed multicast packet relay process.
A search (hereinafter called a multicast route search) of a receiver of a multicast packet to be performed by a router is described, for example, in “TCP/IP Illustrated, Volume 2 The Implementation”, 1995, pp. 416-421 (Addison-Wesley Publishing Company) (hereinafter called a second related art). According to the second related art, the routing table search is speeded up by using a hash search method. If the routing table information is directly searched, the time taken to execute a search process becomes considerably long as the number of receiver IP addresses increases and the number of entries of the table increases. According to the second related art, a sender ID address in a received packet is used as a key for calculating a hash value, and a routing table group is provided which stores grouped entries of the receiver IP addresses having the same hash value.
When a multicast packet is received, the route search processing unit in the router calculates the hash value from the sender IP address in the received packet and the routing table corresponding to the hash value is searched. Since the search range of the routing table is limited in accordance with the hash value, the route search can be speeded up.
A Radish algorithm is known as one of route searching methods. The Radish algorithm is described, for example, in “A technical memo of WIDE project, Kazukio Yamamoto, Akira Kato and Akira Watanabe, Radish-A Simple Table Structure for CIDR (hereinafter called a third related art).
A routing table of the Radish type uses entries of a two-branch tree structure to speed up the route search. More specifically, each entry is allocated to each of a plurality of apexes (nodes) interconnected by right and left pointers of each node constituting a two-branch tree structure wherein the root (two-branch tree root) corresponds to the highest bit of an IP address format. When this two-branch tree structure is searched, the receiver IP address in a received packet is checked one bit after another starting from the highest bit, and one of right and left pointers is selected in accordance with the checked bit value (0 or 1) to move to the next node. With this search, the node assigned the target entry can be reached.
According to the third related art, the two-branch tree is traced by checking the receiver IP address one bit after another. Therefore, even if the number of entries of the routing table becomes large, the search can be completed by performing a check (tracing the two-branch tree) as many as the number of bits of the receiver IP address at the maximum.
Similar to the case wherein there are a plurality of matched entries having different mask lengths as described in the route search for unicast, there are also a plurality of matched entries while the tree is traced by searching the routing table of the Radish type of the third relate
Aimoto Takeshi
Akahane Shinichi
Matsuyama Nobuhito
Sako Yoshihito
Sekino Hiroshi
Antonelli Terry Stout & Kraus LLP
Blount Steven
Hitachi , Ltd.
Patel Ajit
LandOfFree
Packet relaying apparatus and high speed multicast system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet relaying apparatus and high speed multicast system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet relaying apparatus and high speed multicast system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310281