Stabilized binary tree protocol

• US 4,796,023 A
• Filed: 12/05/1986
• Issued: 01/03/1989
• Est. Priority Date: 12/05/1986
• Status: Expired due to Fees

• Current Assignee: Robert E. King
• Original Assignee: Robert E. King
• Inventors: King, Robert E.
• Primary Examiner(s): YUSKO, DONALD
• Application Number:
  US06/938,635
• Time in Patent Office: 760 Days
• Field of Search: 340/825.02, 340/825.5, 340/825.51, 340/825.02, 370/85, 370/60, 370/58, 370/16, 370/54, 370/60, 364/716, 364/194, 364/136, 364/147, 364/194, 364/300, 375/27
• US Class Current: 340/9.11
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00

Abstract

A binary tree protocol (FIG. 6 for example) in which for any given state in the binary tree, the subsequent state for each right substate is determined by applying the same state logic. In the preferred embodiment, (FIG. 6) a subsequent state of state 7, for example, may be state 2, just as the subsequent state of state 5 may be state 3. Since the state logic for the right-most substates is the same as for all other right substates, the concept of a "processing cycle" is eliminated. The protocol continuously moves from state to state (FIGS. 1, 6, 7, 8).

Claims

1. A system for designating groups of terminals in binary tree network including:

means for logically grouping the terminals in a binary tree,

means for designating terminal groups (states) of various sizes, including a root state and recursively defined first (left) and second (right) substates from said root state, said states

and means for selecting a subsequent state from a current state, including means whereby from a current rightmost substate, a leftmost substate may be selected;

characterized in that

the selection criterion for selecting a subsequent state from a current right substate is the same for all right substates.

2. The system of claim 1 in which each subsequent state is never more than one level higher or lower in the tree than the current state.

3. The system of claim 2 in which for each right substate in which a message is received, the following substate is the immediately following left substate on the same level.

4. The system of claim 3 in which said system is centrally controlled.

5. The system of claim 1 in which said system is centrally controlled.

6. The system of claim 1 in which said system utilizes distributed control.

7. The system of claim 1 further comprising means such that a single terminal is individually selected by more than one substate thereby giving said single terminal a processing priority.

8. The system of claim 1 wherein

each subsequent state is selected based on the current state and the existence of an untransmitted message in the current state.

9. The system of claim 1 wherein

each subsequent state is selected based on the current state and the receipt of a message in the current state.

10. The system of claim 8 wherein said system is centrally controlled.

11. The system of any one of claims 1-10 in which

a representation of each possible subsequent state from each current state is stored in an addressable memory device in which the current state constitutes a portion of the address for each subsequent state.

12. The system of claim 11 in which the addressable storage device comprises a ROM or a RAM.

13. The system of claim 11 wherein

each subsequent state is selected based on the receipt of a message in the current state.

14. The system of claim 12 in which each subsequent state is selected based on the existence of an untransmitted message in the current state.