Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-04-06
2003-12-09
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S424000
Reexamination Certificate
active
06661787
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the storage of data in network devices for packet-based data communication systems wherein data is transmitted in data packets that include headers containing address data by means of which packets are switched or routed to their ultimate destinations.
2. Description of Related Art
Address data in data packets fall into two broad categories. A first category is conventionally termed ‘network addresses’ and relates to the source and intended destination network of a packet. These are ‘layer 3’ addresses in the customary OSI layering model. A second category is termed ‘media access control’ address data, abbreviated to MAC addresses. These addresses, layer 2 addresses in the OSI model, relate to the devices within the communication system and are used by network devices to perform bridging.
Two common network devices are called routers and bridges. They both comprise a multiplicity of ports, a switching function (usually constituted by an application-specific integrated circuit or ASIC) and a forwarding database. The latter is compiled by reading ‘source’ addresses from incoming packets and storing them in a table along with an identification of the respective port on which the packet was received. Such a table is used by a look-up engine to determine a port from which to dispatch a packet having a ‘destination’ address corresponding to a ‘source’ address in the table. As will be seen, such ‘source’ and ‘destination’ address may be addresses in either of the aforementioned categories.
If the device receives a packet of which the destination address is not in the look-up table (the forwarding database) it is necessary to broadcast the packet so that an acknowledgement from the destination can be used to resolve the address. Since the broadcast of packets consumes substantial bandwidth (i.e. information-carrying capacity) it is known to partition networks into sub-nets or virtual local area networks (VLANs) whereby the broadcast of packets can be limited to one VLAN.
Both bridges and routers customarily include various buffering, contention resolution and flow control functions which are well known to those skilled in the art and which will not be described further herein. Both bridges and routers and related concepts, such as sub-nets, VLAN's etc, are well described in the prior art, such as WO96/34474, GB-A-2283645, U.S. Pat. No. 5,027,350 and EP-A-0841782.
However, bridges and routers (which terms are used to denote the respective functions, since devices which perform both functions are available) enable somewhat different functions. Routers, as the name implies, are used to look up a route to another network or sub-network. They make a decision which answers the question: ‘To which network should the packet be sent?’. For this purpose the forwarding database needs to relate an identification of the subnet, via a network address sometimes termed VLAN address, and an identification, conveniently termed a port mask, of the port to which the sub-net is directly or indirectly connected. In general, a router does not need knowledge of an end station address in its forwarding database. If however a router has to direct a packet to an end station in a directly connected sub-net the router needs to map the network address of the end station to its MAC address, and to place the MAC address on the packet as the packet leaves the router. To enable this mapping, the router has recourse to a table known as an ARP (address resolution protocol) cache, by means of which a record is maintained of mappings between network addresses, such as IP (internet protocol) addresses, and media access control addresses.
Where a routing table constitutes an end station cache (in particular to achieve fast look-up) the storage space required is X(m+i+v+p), where X is the maximum number of entries in the table, m is the number of bits in an MAC address, i is the number of bits in a network or IP address, v is the number of bits in VLAN address, and p is the number of bits in a port mask. Typically, m=48, i=32, v=5 and p=32. The storage capacity required of an ARP cache is X(m+i), the symbols in this expression having the meanings already indicated.
A bridge is used to connect one LAN to another, so that users connected to different LANs can communicate as if they were on the same LAN. For this purpose the bridge merely switches packets from one port to another. It responds to a MAC address and a VLAN address to look up the relevant port mask.
It is customary (as described in for example EP-A-0365337) to include in a bridging table an ‘age’ field which is constituted by the value of an artificial age at the time the entry was made. The artificial age may be changed from time to time in an alternating or cyclic sequence. The interval between changes may be selected or adapted to the data traffic flow. The age field enables the clearing of unwanted ‘old’ entries from the table in a single operation, the entries which have an age field not corresponding to a current age being removed from the table.
The storage required for a bridging table is X(m+v+p+a) where X, m, v, and p relate to the number of entries, the MAC address, the VLAN address and the port mask respectively. The age field a may be one or two bits.
SUMMARY OF THE INVENTION
The present invention is particularly concerned with the management of data storage for a device which can function both as a router and a bridge. It may be seen from the foregoing that a simple combination of the ordinary functions of a router and bridge would require data storage corresponding to X(3m+2i+2v+2p+a), both bridges and routers require for their operation response to MAC addresses and in addition a router needs to map between network addresses and MAC addresses.
The basis of the present invention is the use of an address cache which is based on network addresses of end stations. An address cache thus organised may be constituted by a single data table and will, as the following indicates, greatly reduce the storage requirements for separate routing and bridging functions.
In order to access such an ‘integrated’ cache, the device needs to be able to respond to both MAC (layer 2) addresses and network (layer 3) addresses and a further aspect of the invention is a process which enables the device to act in such a manner.
REFERENCES:
patent: 4780889 (1988-10-01), Ley et al.
patent: 5550860 (1996-08-01), Georgiou et al.
patent: 5642386 (1997-06-01), Rocco, Jr.
patent: 5757297 (1998-05-01), Ferraiolo et al.
patent: 5815500 (1998-09-01), Murono
patent: 5950115 (1999-09-01), Momtaz et al.
patent: 5970103 (1999-10-01), Townshend
patent: 5978951 (1999-11-01), Lawler et al.
patent: 6161144 (2000-12-01), Michels et al.
patent: 6308220 (2001-10-01), Mathur
patent: 0 153 107 (1985-08-01), None
patent: 0365337 (1990-04-01), None
patent: 0 424 741 (1991-05-01), None
patent: 0465201 (1992-01-01), None
patent: 0508886 (1992-10-01), None
patent: 0841782 (1997-11-01), None
patent: 2283645 (1995-05-01), None
patent: 2 336 075 (1999-10-01), None
patent: 2 337 674 (1999-11-01), None
patent: 2 343 816 (2000-05-01), None
patent: 2 344 030 (2000-05-01), None
patent: WO 96/34474 (1996-10-01), None
WPI Abstract Accession No. 97-269820/199724 & JP090098171 (Hitachi) Apr. 8. 1997.
WPI Abstract Accession No. 93-390998/199349 & JP050292091 (Mitsubishi Electric) Nov. 5, 1993.
Copending Application No. 09/417,102 filed Oct. 13, 1999.
Copending Application No. 09/253,538 filed Feb. 22, 1999.
Copending Application No. 09/645,569 filed Aug. 25, 2000.
O'Connell Anne G.
O'Neill Eugene
Quinlan Una
3Com Technologies
Hsu Alpus H.
Nixon & Vanderhye P.C.
Tran Thien
LandOfFree
Integrated data table in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Integrated data table in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrated data table in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172883