Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-20
2004-04-13
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C455S406000, C379S114080
Reexamination Certificate
active
06721314
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data networks. More particularly, the present invention relates to avoiding duplicate processing in data networks.
BACKGROUND OF THE INVENTION
Various operations are applied to data packets as they are transmitted through a data network. Such operations include, for example, routing, tagging, compression, accounting, encryption, and shaping. Some operations, for example routing, are applied to every data packet at every node. Other operations, for example encryption, must be, or are best, applied to each data packet only once during transmission through the network.
In general, there are two reasons why an operation should be applied to a packet only once, correctness and efficiency. First, it may be incorrect to apply an operation more than once. For example, in a billing application, it is appropriate to capture usage data from a data packet once. Capturing usage data twice, at two separate network nodes, may result in double billing, which is considered incorrect. For example, copending patent application Ser. No. 09/315,636, entitled Method And Apparatus For Associating Network Usage With Particular Users, describes a monitoring system in which usage data is collected for particular users. If such a monitoring system is used in conjunction with a billing application, it may be incorrect to capture usage information two or more times at different network nodes.
The second reason why an operation should be applied to a packet only once is efficiency. If an operation is costly and there is no advantage to applying the operation multiple times, then the operation should be applied only once, even if multiple applications of the operation would not be incorrect. Examples of these types of operations include encryption and compression. For these operations there is a significant cost associated with applying the operation, and there is no advantage to applying the operation multiple times. Moreover, since the complementary operations of decryption and decompression must ultimately be applied to the data, it is usually useful to ensure that these operations are applied only once.
Large networks may contain many network nodes that are capable of applying a given once-only operation. Moreover, during a packet's traversal of the network, the packet may be handled by several of such nodes. This gives rise to the problem of how a given network node should determine, upon receipt of a data packet, whether a once-only operation has been applied, or whether the once-only operation needs to be applied by the given network node.
SUMMARY OF THE INVENTION
In accordance with the present invention duplicate processing at network nodes is avoided by applying once-only processing at network nodes which are so-called adjacent to either the source or destination of a data packet.
The term operator is used to refer to a network node which is capable of applying a once-only operation and the term host is used to refer to an end user machine which generates and receives data packets. Thus, in accordance with the invention, an operator applies once-only processing to a data packet only if the operator is adjacent to the source or destination host of the data packet. An operator is adjacent to a host if there exists a path between the operator and the host containing no other operators.
In accordance with one embodiment of the invention, prior to transmitting a data packet to a destination, a host broadcasts a special data packet. If an operator receives the special data packet, the operator determines that it is adjacent to that host. Further, to ensure that no other operators receive the special data packet, the receiving operator drops the data packet. In this way, only operators which are adjacent to hosts will receive the special data packet which is broadcast from the host.
A second embodiment of the invention consists of two phases. During phase one, a controller node in the network first transmits identifications of hosts which are of interest to operators. A host is of interest to an operator if the data packets from the host require once-only processing. Thus, at the end of phase one, the operators in the network are aware of hosts whose data packets require once only processing, but the operators do not yet know whether they are adjacent to those hosts. During phase two, the operators transmit special ping packets to the hosts identified in phase one. Upon receipt of a ping packet, a host will reply with a ping response. Upon receipt of a ping response, an operator will determine that it is adjacent to the host transmitting the ping response. To ensure that only adjacent operators will receive ping responses, operators drop any special ping packets received from other operators. In this way, intervening operators intercept and drop special ping packets from non-adjacent operators, such that the special ping packets from non-adjacent operators never reach the destination host, thus ensuring that no ping response will be received by the non-adjacent host.
REFERENCES:
patent: 5793763 (1998-08-01), Mayes et al.
patent: 6141652 (2000-10-01), Reeder
patent: 6185680 (2001-02-01), Shimbo et al.
patent: 6188683 (2001-02-01), Lang et al.
patent: 6240091 (2001-05-01), Ginzboorg et al.
patent: 6243667 (2001-06-01), Kerr et al.
patent: 6430596 (2002-08-01), Day, II
Blott Stephen Michael
Breitbart Yuri
Martin Clifford Eric
Dinella Donald P.
Hsu Alpus H.
Lucent Technologies - Inc.
Tran Thien D
Weinick Jeffrey M.
LandOfFree
Method and apparatus for applying once-only processing in a... 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 apparatus for applying once-only processing in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for applying once-only processing in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222547