Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
2000-01-20
2003-09-02
Sheikh, Ayaz (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S232000, C709S237000, C709S238000, C709S239000, C709S242000, C709S243000, C370S351000, C370S400000, C370S395300, C370S428000
Reexamination Certificate
active
06615273
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention generally relates to communication protocols among nodes in a shared network, and more particularly to an improved address resolution protocol to resolve network target identifier (TID) addressing in a shared network and avoid loop formation.
2. Description of the Related Art
A protocol is a set of conventions or rules that govern the transfer of data between computer devices. Protocols are typically separated into layers in an attempt to simplify protocol design. When viewing the layers of a protocol, one commonly speaks of a protocol stack. The lowest layer of the stack typically consists of the physical protocols while, the highest layer are the application layer protocols. The address resolution protocol is a low-level protocol that dynamically binds or maps a logical address to the correct protocol address. In a Telecommunication Management Network (TMN), the address resolution protocol is referred to as a target identifier address resolution protocol (TARP). TARP is widely used in the TMN area, and is required by-the GR-253-core standard. In a TM network, a nodes logical address is referred to as a target identifier (TID) address, the protocol address is referred to as a network entity title (NET) address. In a TM network when an originating node knows the TID of a target node in the network and needs to determine the target nodes NET address, the node will propagate Type
1
and Type
2
PDUs to the network. A PDU is an OSI term synonymous with a packet in a TCP/IP network.
Another situation which involves address resolution and PDU propagation in a TM network is where a node needs to notify other nodes of a TID or protocol address change. In this situation, the node will propagate a Type
4
PDU on the network.
As is well known, the propagation of Type
1
,
2
, or
4
PDUs in the TM network can potentially create undesirable forwarding loops. One earlier solution to the problem of disruption caused by forwarding loops in a TM network has been the use of a Loop Detect Buffer (LDB) which involves storing the protocol address of the node originating the Type
1
,
2
, or
4
PDU on the network along with the originating nodes sequence number as an LDB entry at every other node in the TM network. Upon receiving a rebroadcast of the PDU at the receiving node, the protocol address of the originating node and sequence number are compared against the previously stored LDB entry. If the protocol addresses match and the sequence number is less than or equal to that stored in the LDB, the receiving node simply discards the PDU and does not forward it to prevent further network disruption. Otherwise, the receiving node will forward the PDU along each interface except the receiving interface and update the LDB entry. The LDB solution is deficient, however, in that it gives rise to Target Address Resolution Protocol (TARP) Type
2
or TARP Type
4
storms, a form of network flooding generally defined as the excessive retransmission and forwarding of broadcast PDUs. When a node receives a TARP PDU with sequence number zero, its corresponding LDB entry will be updated to zero. In a large network, it is possible for a TARP PDU with sequence number zero and non-zero to co-exist. Therefore, a node will alternatively update its LDB entry to zero or non-zero. To address these storms an LDB entry timer has been proposed. This proposal is deficient in that, during the time-out period, a node cannot receive any packets at all. If the node is a gateway network element (GNE) or node, the network element may significantly block network communication during the timeout period. Moreover, despite the use of the LDB entry timer, there is no guarantee that a loop will not be formed in the first place. In addition, when a network is large, a lot of memory for the LDB buffers is needed.
A need therefore exists for an enhanced TARP which overcomes the limitations of the prior art discussed above.
SUMMARY OF THE INVENTION
The present invention provides an enhanced address resolution protocol based on reverse path forwarding (RPF). The enhanced target identifier address resolution protocol (TARP) of the present invention provides a method for performing address resolution of target identifier protocol data units (TARP PDUs). The method includes the following steps. First, an originating node broadcasts an address request in the form of a TARP PDU to every other node sharing the network. Upon receiving the broadcast TARP PDU at a particular receiving node, assuming that the receiving node was not the intended target (i.e., TARP PDU destination), the receiving node decides to either drop the TARP PDU or forward it along the network. The decision to either drop or forward the TARP PDU depends upon which interface the TARP PDU was received on. Specifically, the decision to drop or forward a TARP PDU requires that the receiving node perform a forwarding table look-up to retrieve a stored optimal interface identifier associated with the originating node issuing the current TARP PDU. If the interface over which the TARP PDU was actually received by the receiving node is equivalent to the optimal interface identifier obtained from the forwarding table look-up, the TARP PDU is forwarded (i.e., propagated) along the network through each interface associated with the receiving node, except the receiving interface (i.e., optimal interface). Otherwise, the TARP PDU is dropped by the receiving node.
The decision to drop or forward TARP PDUs is based upon the methodology of Reverse Path Forwarding (RPF) which defines an optimal interface. In accordance with RPF, a received TARP PDU will only be forwarded along the network by that receiving node if the PDU was received on an “optimal” interface, defined as an interface that the receiving node would choose to send a PDU back to an originating node by the shortest path algorithm, which is well known in the art. Otherwise, in accordance with RPF, if the interface over which the PDU was received was non-optimal, the PDU will be dropped by the receiving node. The forwarding look-up table controlled by each node's IS-IS routing engine, stores optimal interface identifiers, as defined by RPF, that can be used to determine whether the received TARP PDU was received over an optimal or non-optimal interface.
In one aspect of the present invention, the receiving node, in certain instances, will not be able to determine the optimal interface from its forwarding table because the originating node is not contained in the receiving node's forwarding table. In this case, the receiving node will locate a unique median node, which acts as a substitute for the originating node, that is in the forwarding table of the receiving node, to determine whether the PDU received by the receiving node was received over an optimal interface.
The method of the present invention advantageously improves network performance, especially for larger networks, since network flooding is completely avoided as a consequence of dropping TARP PDUs in accordance with the RPF algorithm. That is, by checking the interface over which a broadcast TARP PDU was received, the enhanced TARP protocol of the present invention can avoid the generation of TARP PDU storms. A further advantage of the present invention is that it is simple to implement and is robust. Another advantage is that the enhanced protocol is compatible with the existing TARP protocol and can be deployed in networks with the existing TARP protocol.
REFERENCES:
patent: 5165024 (1992-11-01), Sweazey
patent: 5719861 (1998-02-01), Okanoue
patent: 5925137 (1999-07-01), Okanoue
patent: 5987011 (1999-11-01), Toh
Reverse Path Forwarding of Broadcast Packets, by Yogen K. Dalal and Robert M. Metcalfe published in Communications of the ACM, vol. 21, No. 12, pp. 140-147, Dec. 1978.
Lucent Technologies - Inc.
Sheikh Ayaz
Won Young N
LandOfFree
Method for performing enhanced target identifier (TID)... 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 for performing enhanced target identifier (TID)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for performing enhanced target identifier (TID)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3010278