The system transfers data packets between remote sites deterministically. The positioning of the data sources and the initial placing of the data packets are set up randomly, but the evolution of the system in time is governed by fixed rules thereafter.
The system comprises a square array of routing cells and within it, randomly placed, paired data sources. There can be any number of data sources connected to a given routing cell. There is one data packet travelling between each linked pair of sources.
We consider the percentage load on the network (the utilisation).
The network is illustrated in a figure to be shown. The routing cells store one data packet and read information in the packet header, to transfer the packet to a neighbouring cell which, if possible, is in the direction of the packet destination.
A token is passed around the array in such a way that it visits every cell in turn, once, before returning to its starting point. The token prevents contentions from arising if two packets would ideally be transferred to the same cell: only the cell currently holding the token is allowed to transfer its packet. The system is not a cellular automaton, in which updating takes place simultaneously.
Each packet travels to and fro between a pair of sources which are located at two different places in the grid. On arrival at one source, it is immediately returned to the other. The number of packets is therefore constant for all time.
The rules are:- A routing cell can hold only one packet at a time. This property arises from the limited memory of each cell and has a marked effect on the dynamics of the system, since it causes packets to interact with each other: the presence of a packet at a cell prevents another packet from occupying the same cell. The destination address can be read by routing cells. This information enables the cell to choose where to transfer the packet. The preferences used are biased logically to the direction of the receiver. A cell can only transfer a packet when the token is present. The token cycles through all cells in turn, in a predetermined sequence, then returns to its starting point. One complete journey of the token is referred to as a token pass. Time is discrete, and measured in units of token passes. Packets can be transferred horizontally, vertically or diagonally to a neighbouring cell only. Ideally, they are transferred diagonally until they are horizontally/vertically in line with their destination, then they proceed horizontally or vertically. The packet age is increased by one every time the token passes through the cell containing it. As soon as a packet has arrived at its destination, its age is set to zero and its destination address is set to that of its source. This process continues indefinitely. The data packet on the return journey can be looked upon as an acknowledgement which is being returned to the source.
We have examined two variants of the system. In the first, each packet is allowed to be transferred only once per token pass, and we discuss this only in passing. In the second variant, any number of transfers are allowed, so that if a given packet encounters the token twice in a pass, it will be transferred twice. All our self-similarity calculations were based on the second variant.
A cell which has the token and also contains a data packet, reads the packet header to find the destination. The cell determines whether the packet should be transferred horizontally/vertically or diagonally. The cell then checks if the first choice cell is off the edge of the array and if not, whether there is a packet present at this cell. If it is not possible to transfer the packet for either of these reasons, the same tests are carried out for the second, third choices, until a feasible transfer is found. In the worst case, the packet stays where it is.