Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
1998-12-22
2003-04-15
Lee, Thomas (Department: 2185)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C709S206000
Reexamination Certificate
active
06549957
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to digital data processors and networks of intercommunicating digital data processors capable of automatically generating messages and, in particular, to methods and apparatus for preventing an occurrence of infinite loops of automatically generated messages within and among digital data processors.
BACKGROUND OF THE INVENTION
Systems that are capable of automatically generating one message in response to another are intrinsically vulnerable to a phenomenon referred to herein as a “maelstrom”. A maelstrom can be viewed as a chain reaction in which a single message can unintentionally trigger the generation of a large, rapidly growing, potentially infinite number of messages, quickly swamping and therefore incapacitating the communications network.
Recent years have seen a number of such chain reactions involving message passing in networks. Examples include the following.
(1) A chain reaction occurred in an Ethernet environment, as described by U. Manber, Chain reactions in networks, Computer, pages 57-63, October 1990. The chain reaction was caused by an inconsistency between two different versions of the Berkeley Unix operating system, which had incompatible conventions for specifying broadcast messages.
(2) A ‘cycled users’ phenomenon, familiar to email postmasters, occurs when a person having accounts on two or more systems directs each system to forward incoming email to the other. In this simple form it is easily detected, but more complex chains of forwarding involving more than two accounts can escape efficient detection. A variation of this type of forwarding loop can occur when there are delays in processing a user's instructions to change the final destination from one system to another. The user's mail may cycle if the systems' configurations are changed in the wrong order.
(3) Chain reactions resulting from erroneous network administration messages can be caused, for example, when a workstation broadcasts its own hostname on startup. Certain types of configuration error, such as an erroneous hostname, can generate an infinite sequence of low-level error messages.
(4) An Arpanet chain reaction occurred in 1980, in which a recurrent error at one host caused a loop of routing update messages. The entire network was ultimately brought down by the resulting flood of messages, as described by E. C. Rosen, Vulnerabilities of network control protocols: An example, Computer Comm. Review, pages 10-16, July 1981.
(5) Finally, a chain reaction was caused by the Internet “worm” of November 1988, as described by E. H. Spafford, The internet worm: Crisis and aftermath. Communications of the ACM, 32:678-688, June 1989.
The examples given above were triggered and/or propagated by a design flaw, hardware failure, or software failure at one or more elements in the network. With the advent of sophisticated message processing systems such as intelligent agents, however, a new variety of chain reaction is likely to occur. This new phenomenon, referred to herein as the maelstrom, is not due to any flaw or failure of any element, but is instead characterized by the collective behavior of many agents, each of which, considered in isolation, is working properly.
Throughout the following discussion, the term “message” refers to a body of data sent from one entity to another in a network. Messages may be generated by and/or intended for humans (as, for example, email messages); nonhuman agents (e.g., bids in an automated auction); or lower-level processes (e.g., TCP/IP signals). An “agent” is an entity in a network capable of receiving messages from, and generating messages for, other such entities. “Forwarding” refers to the act by an agent of generating one or more messages as a result of receiving a message. In general, the generated message(s) may differ from the received one. A “transmission step” is the transmission of a single message from one agent to another. A “maelstrom” is a self-sustaining chain reaction of forwarding events in which an agent receives messages(s) that were ultimately triggered, through any number of intermediate transmission steps, by message(s) sent by that agent. In a typical maelstrom, the received message triggers a new sequence of forwarding events ultimately causing the agent to receive another message that triggers yet another sequence, and so forth, indefinitely.
As an example of how a maelstrom might naturally occur in a network of email forwarding agents, one may consider the following scenario. A typical computer user (“Fred”) is one of a small group of friends who exchange jokes with one another via email. Fred decides to automate the distribution of jokes, and instructs his mail agent to forward to his friends any incoming mail with the word “Joke” in the subject line. This idea then occurs independently to some small fraction other users, and soon jokes are being forwarded several times, from mailing list to mailing list. Eventually there are enough users forwarding jokes that one of the jokes that Fred's agent had forwarded comes back to Fred. Of course, it is automatically forwarded, and the cycle begins again. As the same joke keeps coming back to Fred, it is again forwarded, endlessly. Every time the joke goes around in this cycle, everyone who originally received the joke receives it again, and forwards it again. Furthermore, because both the original message and each copy are forwarded independently, the number of copies of the message grows rapidly with time. Before long, the network used for e-mail delivery is swamped, and can't be used to transmit useful information to Fred or anyone else, even those users not involved in the mail loop.
It is important to note that this exemplary maelstrom consists entirely of actions that, as far as any single user knows, are perfectly safe. The maelstrom only occurs when forwarding steps are connected in a loop. In a distributed forwarding network, no single user has access to sufficient information about the network to detect a loop before the message is actually sent. Therefore, in principle, every automatic message forwarding process potentially is the cause of an unforeseen and devastating network breakdown.
The above described scenario is an example of the simplest type of maelstrom. One may further identify subclasses of maelstroms as follows.
1. Simple maelstroms. This type of maelstrom relates to automatic message forwarding in a distributed network, in which each agent forwards incoming messages verbatim to a set of other agents. The set of destinations is different for each sender agent, and may also depend on the header or content of the message, or on other factors such as time of day, etc.
2. Additive maelstroms. This type of maelstrom is a more complex form of automatic message forwarding, in which additional information is added to the message before forwarding. This additional information may be of any nature from the most insignificant, such as a blank line added to the bottom of the original message, to the most significant, such as a complete disavowal of the original message by its original author.
3. Combinatorial maelstroms. This type of maelstrom relates to several messages or parts of messages that are combined to form a single new message prior to forwarding. One example is an automatically generated, personalized newspaper that can be received by an agent and, in turn, used by the receiving agent in whole or in part as content for its own automatically generated newspaper.
4. Maelstroms with finitary transformation. As the message is forwarded from agent to agent, it can be transformed into a succession of variations of which there are a finite (usually small) number of types. Examples of this type of variation include conversion of the message to all capital letters or to all lower case letters, adding or removing a final blank line, or applying a simple character encoding such as one known as “rot13.”
5. Maelstroms with arbitrary transformation. This type of maelstrom is the most general case, in
Hanson James E
Kephart Jeffrey O
Cao Chun
Harrington & Smith ,LLP
International Business Machines - Corporation
Lee Thomas
Zarick Gail H.
LandOfFree
Apparatus for preventing automatic generation of a chain... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for preventing automatic generation of a chain..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for preventing automatic generation of a chain... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101603