Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-05-18
2002-01-08
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000
Reexamination Certificate
active
06337862
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to packet-based communication networks wherein data is conveyed between stations, such as users and switching devices, by means of data packets including, in general, address data as well as control and/or message data. The invention more particularly relates to network switches which have a multiplicity of ports by which addressed data packets can be received and a multiplicity of ports (which may be constituted by the aforementioned multiplicity of ports) for the forwarding of data packets to their respective destinations.
BACKGROUND TO THE INVENTION
Network switches fall into two general categories. One category, frequently called bridges, responds to ‘layer
2
’ or media access control addresses in data packets. These addresses identify, in the case of a unicast transmission, the local source and destination devices of the relevant packet. Another category of switch responds to ‘layer
3
’ or protocol addresses, often termed ‘IP’ addresses. Such addresses indicate the network of a source or destination of the packet and usually the network address within that network of the source or destination device. Such network addresses may be accompanied by VLAN data, identifying a virtual network within a physical network. Switching devices responsive to network addresses are often termed routers and if so are normally software controlled devices which are capable of performing a variety of monitoring and control functions not primarily relevant to the present invention. However, layer
3
switches, that is to say switches which can respond to network addresses to determine forwarding data can be realised in hardware form. Moreover, switches which can respond either to media access control addresses or network addresses to provide forwarding data are known; one example is given in published British patent application GB-2337674-A.
A customary function which a switch of the general kinds described above has to perform is a look-up which relies on some or all of the relevant address data in the packet to obtain the aforementioned ‘forwarding data’. This forwarding data is obtained from a data table which relates the relevant address data with specific data such as a local MAC address and/or a port mask which can be used by the switching engine (whether in hardware or software form) to determine which port or ports are to be employed for forwarding the relevant packet. In the case of a unicast transmission a packet will be forwarded only from one port, for a multicast transmission, which is normally distinguished from a unicast transmission by virtue of special information in a header, a port mask may identify more than one port for the forwarding of a packet. The specific nature of the forwarding data or its format is not primarily relevant to the present invention provided that the look-up made in response to the data available in the packet enables a determination of the correct port or ports from which the packets should be forwarded.
There exists a variety of schemes for organising the look-up which has to be performed in the ‘forwarding database’ of the switch and certain techniques have been developed in order to make the look-up more efficient. A motive for these techniques is the substantial storage space required for a forwarding database. Typically, for Ethernet packets, media access control addresses (both source and destination) comprise 48-bits each. Network address each comprise 32 bits each and a VLAN identification normally comprises 5 bits. In some circumstances, for example those particularly mentioned hereinafter, a look-up may require a full 69-bit key if both the source address and the VLAN identification are included with the destination network address in the look-up.
One scheme for rendering the look-up more efficient is known as a ‘trie’ search wherein successive portions of the key are employed in each of a multiplicity of stages, each locating a pointer to another block in the search until the search terminates in a data entry which includes the relevant forwarding data. A trie search is particularly efficient for network addresses wherein a large number of the possible destinations have part of the address in common (such as would occur if all the relevant devices were on the same network). One example of a trie search is described in our co-pending GB patent application number 9925517.6 filed Oct. 29, 1999.
SUMMARY OF THE INVENTION
The present invention is particularly concerned with improving the speed of look-ups required for network address controlled multicasts and other examples, for example routing in server load balancing. More particularly, an address look-up may be performed employing a key made up of the layer
3
address information, i.e. the network destination address, the network source address and the VLAN identification of the source. This key is employed to search a tree data structure until a ‘leaf’ (particularly an associated data block) is found. Each level in the tree employs a few more bits from the key. This means that many addresses with a common prefix can refer to the same target address.
Server load balancing is a method of sharing a load between a plurality of servers for higher performance and also to obtain the protection of redundancy, so that operations may be duplicated in servers to enable operation of a network to continue notwithstanding the failure of one of the servers. All the servers in a group may have for this purpose the same virtual network address. The switch or router which controls these servers can share the traffic destined for the virtual address based on some algorithm. One of these algorithms may employ the particular network source address of a packet to determine which server will be the destination for that packet.
Currently for multicasting and server load balancing the entire network address information would have to be stored in a trie look-up table. This requires a search of the entire key, normally 69 bits. In server load balancing, the destination network address of all traffic going towards the group of servers will always be the virtual address of the servers and only the network source address and the VLAN identification data will vary.
The present invention is based on the truncating of the search so that a determination of whether the network destination address corresponds to the virtual address enables the trie search to be performed on only the remainder of the network address information, particularly the network source address and the VLAN identification (if this is used). Generally therefore a multiplicity of stages in a trie look-up scheme may be saved.
Similarly, for multicasting based on network addresses, the network destination address may be compared with a set of registers containing known network destination addresses. If there is a match at this stage the trie search key may commence with the first section of the network source address.
Further features of the invention will be apparent from the following drawings and detailed description.
REFERENCES:
patent: 5774660 (1998-06-01), Brendel et al.
patent: 5918017 (1999-06-01), Attanasio et al.
patent: 6061349 (2000-05-01), Coile et al.
patent: 6101616 (2000-08-01), Joubert et al.
patent: 0 551 243 (1993-07-01), None
patent: 0 594 196 (1994-04-01), None
patent: 2 346 519 (2000-08-01), None
patent: 96/00945 (1996-01-01), None
Gilbert Christopher
Loughran Kevin
O'Callaghan Sorcha
O'Malley Edele
3Com Corporation
Mehra Inder Pal
Nguyen Chau
LandOfFree
Network switch with truncated trie look-up facility does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network switch with truncated trie look-up facility, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switch with truncated trie look-up facility will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2862223