Static information storage and retrieval – Addressing
Reexamination Certificate
1998-12-18
2001-03-13
Fears, Terrell W. (Department: 2824)
Static information storage and retrieval
Addressing
C365S230030
Reexamination Certificate
active
06201755
ABSTRACT:
TECHNICAL FIELD
The present invention generally relates to “connection-oriented” and “connection-less” packet, frame relay, or cell switching networks, and more particularly, to a method and system for storing and retrieving connection and/or forwarding information associated with specific identifiers contained within the packets, frames, or cells in a communications network.
BACKGROUND OF THE ART
Communication networks generally transport information in the form of packets, cells, or frames between nodes. Depending upon the particular protocol used to transport the information, a communication network may be categorized as a connection-oriented network or a connection-less network.
In a connection-oriented network, for example an Asynchronous Transfer Mode (ATM) network, the network establishes a connection for transporting cells between nodes, which may include, for example, switching systems and routers. When a node receives a cell, the node identifies a connection, for example a virtual circuit or a virtual path, associated with the cell in order to properly route the cell to the next node in the network. As a result, the node must retrieve from a memory the connection information associated with the cell within a fraction of the time for processing the cell. This task of retrieving the connection information impacts the performance of a node, especially as the address space of connection identifiers becomes large and unrestricted.
Although in a connection-less network, for example an Internet Protocol (IP) network, the network transports packets or frames without establishing connections between the nodes, the nodes identify forwarding information, for example output port addresses in the nodes, associated with packets for routing the packets to their destination nodes in the network. Like nodes in a connection-oriented network, a node in a connection-less network must retrieve the forwarding information associated with a packet within a fraction of the time for processing the packet. This task of retrieving the forwarding information impacts the performance of the node and the communications network as a whole.
Several solutions are known for storing and retrieving connection and forwarding information in connection-oriented and connection-less nodes. One solution uses a Content Addressable Memory (CAM) for storing and retrieving connection and forwarding information associated with cells and packets. CAM has a high incremental cost, however, and is not cost effective for processing large number of connections or network addresses.
Another solution uses a linear index into a Random Access Memory (RAM) for storing and retrieving information in a node. A linear index, however, requires a RAM address space that is as large as the address space for connection identifiers or addresses in a network, which can be large and unrestricted. Thus, the linear index is not a practical solution for ATM and IP networks.
Another known solution uses a hierarchical linear index into a RAM for storing and retrieving connection and forwarding information in a node. A hierarchical linear index uses a key into the RAM for retrieving the information. The key, however, must correspond to a predefined hierarchy, which puts a restriction on the allocation of connection identifiers or network addresses in the node. To maintain the hierarchy, the node must periodically restructure the hierarchy as the node inserts and deletes keys in the RAM. Restructuring the hierarchy generally requires significant resources and service interruptions unless the node reserves additional memory, which may be impractical and costly.
Yet another solution uses a binary search into a RAM for storing and retrieving connection and forwarding information in a node. The binary search uses a feedback from each search into the RAM before performing another search, and thus, significantly increases the retrieval times in the node.
Therefore, it is desirable to have a method and system for storing and retrieving connection and/or forwarding information in a communication node, and thus, to overcome the above-mentioned and other disadvantages of the prior art.
DISCLOSURE OF THE INVENTION
Methods and systems consistent with the present invention retrieve connection information from a memory in a node of a communications network by identifying in the memory a set of addresses corresponding to a connection identifier such that the number of searches for retrieving the connection information is less than a predetermined probe threshold. A node may include, for example, a switching system, a router, a bridge, and/or any other processing device in a communications network. In a connection-oriented network, for example an ATM network, a connection identifier may include a virtual circuit identifier (VCI) and/or a virtual path identifier (VPI). In such a network, the connection information may include, for example, configuration and context information associated with a virtual circuit (VC) and/or a virtual path (VP) in the ATM network.
In a connection-less network, for example an Internet Protocol (IP) network, a connection identifier may include a destination address. In such a network, the connection information may include forwarding information, for example an output port address in a node, and/or flow information, for example Quality of Service (QoS) information associated with a flow in the IP network.
In accordance with an embodiment of the invention, when a node in a communications network receives a packet, frame, and/or a cell, the node determines a first connection identifier for retrieving the connection information associated with the received cell. In a hash table, which may reside in the memory, the node identifies a first address that corresponds to the first connection identifier by, for example, determining a hash value based on the first connection identifier. The node then retrieves from that first address a first entry, which includes a second connection identifier and, for example, a connection index. Alternatively, the first entry may include a second connection identifier and, for example, connection information that corresponds to the second connection identifier.
When the first connection identifier does not match the second connection identifier, the node identifies in the hash table a second address that corresponds to the first connection identifier by determining a different hash value. The node then retrieves a second entry from the second address in the hash table. The node repeats the above steps, for example recursively, until it retrieves from the hash table an entry that includes a connection identifier that matches the first connection identifier or until a count of the entries searched in the hash table equals a predetermined probe threshold.
When the first connection identifier matches a connection identifier in an entry in the hash table, the node identifies a connection index in the matching hash table entry. The connection index includes a third address into a connection table, which may also reside in the memory. The node retrieves from the third address in the connection table the connection information associated with the first connection identifier. When the count of the entries searched in the hash table equals the predetermined probe threshold and the node has not identified a matching hash table entry, the node determines that the connection information does not exist in the connection table.
In accordance with an embodiment of the invention, when a higher-level routing system in the network requests the establishment of a connection, the node stores the connection information as follows: The node identifies in the hash table a first set of addresses corresponding to a first connection identifier by determining, for example, a set of hash values based on the first connection identifier. When one of the first set of addresses corresponds to a free entry, the node inserts at that address an entry that includes the first connection identifier and its associated connection index. It then in
Englert Eric
Pillar John
St-Denis Bernard
Fears Terrell W.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Nortel Networks Limited
LandOfFree
Method and system for storing and retrieving information in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for storing and retrieving information in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for storing and retrieving information in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484872