Description of the data transfer network

The purpose of the system under discussion is to transfer data packets between remote sources. It operates in an entirely deterministic manner. That is, although certain parameters ( e.g. the positioning of the data sources and the initial placing of the data packets) are set up randomly, thereafter they remain fixed and the evolution of the system in time is entirely governed by rules.

  
Figure 1: The data network studied in this paper, with one packet ( i.e. P = 1).

The system comprises an array of routing cells and 2P (where ) 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, and therefore there are P packets on the network. We often refer below to the percentage load on the network (the utilisation), by which we mean %.

The network is illustrated in figure 1. The routing cells can ( a) store one data packet and ( b) read information in the packet header, in order to transfer the packet to a neighbouring cell which, if possible, is in the direction of the packet destination. Other information is also assumed to be stored in the packet header, for example the length of time that the packet has been in transit (its age).

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 path assumed for the calculations in this paper is sketched in figure 1, although it is expected that the similar results would be obtained for any path with the above properties. 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. In the light of this, the system described here is not a cellular automaton, in which updating takes place simultaneously; in our network, the token forces sequential updating. However, our system is something like the token grid network [Todd 1994], although in our case the connectivity is much greater and only one token is present.

The i-th packet travels to and fro between a pair of sources and , () 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, P, is therefore constant for all time. From a communications system perspective, this can be considered as either a positive acknowledgement system, in which the source always has information ready for transmission, or a client-server architecture.

The operation of the network is governed by the following rules:

1. 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.

2. The destination address can be read by routing cells.  

   This information enables the cell to choose where to transfer the packet. The preferences used in the calculations are detailed below.

3. A cell can only transfer a packet when the token is present.  

4. 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. Throughout this paper, we consider time to be discrete, and measured in units of token passes.

5. 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.

6. Whether a packet is transferred or not, its age is increased by one every time the token passes through the cell containing it.  

7. 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.

In the light of item 1 above, it is clear that the maximum allowed value of P must be , in order that there be at least one empty cell --- if all cells were occupied no packets could move anywhere.

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.

The preferences referred to in 2 above will now be described. In the following, the packet under consideration is at the centre of the array; the numbers refer to the preference given to a transfer to that cell, with 1 meaning first choice and 9 meaning 9th choice.

( a) packet should preferably move diagonally towards the top left

( b) packet should preferably move horizontally towards the right

Rotations of the above give the appropriate choices in cases when the packet should be moving in other horizontal, vertical or diagonal directions, such that in each case, the first choice is that which is as much as possible in the direction of the destination.

The above choices are used as follows: a cell which has the token and also contains a data packet, reads the packet header to find the destination. From this information, the cell can determine 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, choice 9, the packet stays where it is.

The system can be visualised as P simultaneous discrete-space games of tennis being played between P pairs of players (data sources) with P balls (data packets) that interact with each other when in transit. Bearing this analogy in mind it is not surprising that complex dynamics result.

Many established LANs are based upon token passing with the IEEE 802.4 (Token Bus), IEEE 802.5 (Token Ring) and the Fibre Distributed Data Interface (FDDI) being the most prominent examples. While these LANs do not have as rigorous a token passing regime as used in our network, it is possible to map their characteristics loosely onto our approach. A further example of the relationship between our network and established LAN technology is that of multiple token ring architectures which use source routing. In this case the frames are forwarded onto the bridged rings according to the routes described in the frame headers and the transfer of data across each ring is determined by the relative synchronisation between the separate token passing domains.