US 4,630,264 AGrant
Efficient Contention-Resolution Protocol for Local Multiaccess Networks
Issue Date:1986-12-16
•54 Claims
•10 Drawing Sheets
Abstract
A contention-resolution protocol on a single shared bus with asynchronous time-division multiplexing and random access is disclosed. The scheme is equivalent to finding the extremum of a set of random numbers. Each station maintains a common window. A station contending for the use of the bus generates a number. If the number generated falls in the window, the station contends in the next slot of time, otherwise it has to wait until the current contention has been resolved and a packet has been transmitted. A collision-detection rule is applied that detects whether one or more stations have contended. If more than one station has contended, or if no station has contended, a window-control rule is applied at each station to expand, shrink or otherwise change the window. The process is repeated until exactly one station has contended. The packet of data can then be sent.
Metadata
Inventors
- Benjamin W. Wah
- Jie-Yong Juang
Application Information
Application Number:US 6526454
Filing Date:1984-09-21
Priority Date:1984-09-21
Art Unit:263
Classifications
IPC:
H04J 302
Field of Search:
37034085;89;94825.5
Patent Drawings (10 sheets)
Description
This invention relates to contention resolution on a single shared bus with asynchronous time-division multiplexing and random access and more particularly, to contention resolution on a bit-serial or bit-parallel bus.
In the system described, the unit of message is a packet. A station is active if it is attempting to access the channel (bus); otherwise, it is idle. Messages may have different priorities, and the bus should be granted to the station with the highest-priority message.
In a multiaccess bus, simultaneous requests for channel access can be generated by independent stations. All contending stations contend for the use of the bus synchronously. Since there is a finite transmission delay between stations, simultaneous transmissions cannot be detected until some time later that is bounded by the maximum round-trip propagation delay on the network. This time interval is a slot. When two processors try to transmit simultaneously, a collision is said to occur. The contending stations have to wait and transmit again in the future.
A bus network can be classified according to whether it is bit-serial or bit-parallel and how a collision can be detected on the bus. When two stations transmit simultaneously on a single signal line, it is possible to detect two or three states of the transmission line (bus). With a two-state collision-detection mechanism, it is possible to detect whether zero or more than zero stations have contended. On the other hand, with a three-state collision-detection mechanism, it is possible to detect whether zero, one, or more than one station has contended. A bit-serial bus with a carrier has a three-state collision-detection mechanism and has been used in carrier-sense-multiple-access (CSMA) networks. Bit-serial or bit-parallel bus networks that are used in conventional multiprocessor systems have two-state collision-detection capabilities.
In CSMA networks, an active station senses whether a carrier is present, or the network is free, before attempting to contend for the channel. If the channel is busy, the station waits until it becomes free. Otherwise, the station starts the transmission. When a message is transmitted, the originating station can detect whether there is a collision. If the transmission is terminated immediately when a collision is detected, the network is referred to as a CSMA/CD network (a CSMA network with collision detection capability).
Many protocols for point-to-point communications on CSMA/CD networks have been developed. These protocols can be classified as nonadaptive and adaptive according to their transmission policies. A nonadaptive CSMA/CD protocol makes its transmission decision regardless of the channel load. Nonpersistent and persistent protocols have been examined by L. Kleinrock and F. A. Tobagi, IEEE Trans. Communications, COM-23, 1400-1416 (1975). A CSMA/CD network with nonadaptive protocols has been shown to be inherently unstable by G. Fayolle, J. ACM, 24, 375-386 (1977). The effective throughput of the channel will tend to be zero due to the possibility of endless collisions.
In order to maintain a stable channel, an adaptive protocol is necessary. Many adaptive CSMA/CD protocols have been proposed. Notable are the Adaptive-Tree-Walk Protocol of J. Capetanakis, IEEE Trans. Information, IT-25, 505-515 (1979), the Urn Protocol of L. Kleinrock and Y. Yemini, Proc. ICC, 7.2.1-7.2.5 (1978), the Arrival-Time Window Protocol of D. Towsley and G. Venkatesh, IEEE Trans. Computers, C-31, 715-722, 1982, and the Binary Exponential Backoff scheme of ETHERNET as described by R. M. Metcalfe and D. R. Boggs, Communications of ACM, 19, 395-404 (1976). The performance of ETHERNET is load-dependent and uses a three-state collision detection mechanism. The IEEE 802 standard on CSMA/CD networks has been described by M. Graube, IEEE Spectrum, 19, 60-64 (1982).
Nonadaptive protocols for priority resolution have been studied by F. A. Tobagi, IEEE Trans. Communications, COM-30, 185-200 (1982), N. Shacham, IEEE Trans. Communications, COM-31, 253-261 (1983), L. M. Ni and X. Li, Proc. Eighth Data Communications Symposium (1983), but the adaptive protocols corresponding to these nonadaptive protocols have not been found.
CSMA/CD networks have been used in applications with load balancing. One such implementation is in the Engineering Computer Network as described by K. Hwang et al, IEEE Computer, 15, 55-55 (1982). The identification of the source and sink of load balancing is done inefficiently through high level operating system control and has not been embedded into the contention-resolution protocol.
Another protocol for a single shared bus with asynchronous time-division multiplexing and random access is the register insertion technique proposed by E. R. Hafner, Z. Nenadal, and M. Tschanz, IEEE Trans. Communications (1974) which was used in the IBM Series 1 product, IBM Series/1 Local Communications Controller Feature Description, GA34-0142-2 (1982). The Pierce loop implementing a slotted-ring protocol was proposed by J. R. Pierce, Bell System Technical Journal (1972), and later implemented in the Cambridge ring as described by P. Heywood, Data Communications (1981).
It is therefore an object of this invention to provide an improved contention-resolution protocol for point-to-point communications in CSMA/CD networks.
It is another object of this invention to provide a general contention-resolution protocol for point-to-point communications in CSMA/CD networks that can unify many existing CSMA/CD protocols.
It is still another object of this invention to provide an improved contention-resolution protocol for point-to-point communications in bit-serial or bit-parallel buses with two-state or three-state collision-detection mechanisms.
It is yet another object of this invention to provide an efficient protocol for identifying the set of stations that have messages with the highest priority.
It is still another object of this invention to provide an efficient protocol for identifying the station with the maximum response time and the station with the minimum response time so that load balancing can be carried out between these two stations.
It is yet another object of this invention to provide an efficient protocol for identifying one or more of a set of free resources of a given type so that they can be used to process tasks from the requesting station.
This invention provides an improved contention-resolution protocol on a single shared bus with asynchronous time-division multiplexing and random access. The scheme includes rules for generating random numbers, estimating the channel load, detecting collisions and controlling the window size accordingly. By generating a random number for each contending station at the beginning of the contention period, and successively modifying the window until exactly one station's number is isolated in the window, the contention is resolved and the packet can be sent.
Additioal features and advantages of the invention will become apparent to those skilled in the art upon consideration of the following detailed description of a preferred embodiment exemplifying the best mode of carrying out the invention as presently perceived. The detailed description particularly refers to the accompanying figures in which:
FIG. 1 is a flow diagram of a sequence of steps for a window control protocol;
FIG. 2 is a graph showing the relative performance of different window control protocols;
FIG. 3 is a flow diagram of a sequence of steps for a window control protocol;
FIG. 4 is a flow diagram of a sequence of steps for a window control protocol;
FIG. 5 is a flow diagram of a sequence of steps for a window control protocol;
FIG. 6(a) illustrates a window search process;
FIG. 6(b) illustrates a look-up table implementation for a window control protocol;
FIG. 7 is a graph illustrating the probability of success in one contention using a multiaccess code-deciphering bus-arbitration scheme;
FIG. 8 is a graph illustrating the average number of contention slots needed for resolving conflicts of bus requests using a multiaccess code-deciphering scheme;
FIG. 9 is a graph illustrating an optimal choice of code-space size;
FIG. 10 is a graph illustrating the optimized performance of existing bus contention-resolution protocols by using the disclosed invention;
FIG. 11 is a graph illustrating the performance of an embodiment of the disclosed window protocol for global priority resolution;
FIG. 12 is a graph illustrating reduction in job response time by using load balancing;
FIG. 13 is a graph illustrating the effect of the ratio of service to transmission delays on load balancing; and
FIG. 14 is a graph showing the effect on load balancing due to message traffic.
To resolve contention, each contending station generates a parameter, and the station with the minimum (or maximum) parameter wins the contention. This is equivalent to finding the extrenum among a set of contention parameters. Suppose the set of contention parameters are (x.sub.1, . . . , x.sub.n) in the interval between L and U, and y.sub.i is the i-th smallest of the x.sub.j 's. Given that the minimum value is sought, an initial interval or window is chosen with the lower bound at L and the upper bound between L and U. There can be zero, one or many y.sub.i 's in this window. If there is exactly one number falling within the window, this number can be verified as the minimum, y.sub.1. Otherwise, the window has to be updated: it is moved if it contains no y.sub.i ; or it is shrunk to a smaller size if it contains more than one y.sub.i. The process is repeated until the minimum y.sub.i is uniquely isolated in the window.
An illustration of the distributed window-search scheme at station i, 1.ltoreq.i.ltoreq.n, on a multiaccess bus with a three-state collision-detection mechanism follows. procedure window.sub.-- protocol.sub.-- station.sub.-- i;
A global window is maintained at each station, and it serves as a reference for the transmission decision. A station is allowed to transmit if its contention parameter is inside the window.
A method of detecting the state of the channel due to the transmission is required. The state is collected by each station, and the window is updated accordingly. In a system with a two-state collision-detection mechanism, it is not possible to distinguish whether one or more than one station has contended. An additional verification phase is thus necessary. The resulting protocol called the window protocol has four major control rules:
(1) Parameter-generation rule: Each contending station generates a contention parameter that is governed by an application-dependent distribution function.
(2) Load-estimation rule: This estimates the number of contending stations before contention begins.
(3) Collision-detection rule: This detects the number of stations contending for the bus.
(4) Window-control rule: The window is updated according to outcome of collision detection. The algorithm for controlling the window is identical for all the stations, and if identical collision information is received at each station, the windows maintained by the stations will be updated identically in each step of the contention process.
The number of stations contending for the bus can be detected by a two-state or a three-state collision-detection mechanism. The load-estimation and window-control rules depend on the number of states that can be detected. The rules discussed below are based upon the fact that the distributions for generating the contention parameters are independent for all the contending stations.
Window-control schemes can be adaptive or nonadaptive to the channel load. Three load-adaptive schemes that include dynamic-programming window control, optimal greedy window control, and approximate greedy window control are described here. Two nonadaptive schemes are also described: binary-divide window control and window control based on global distributions. These control schemes are by no means exhaustive. The window control can be implemented by either table look-up or real-time calculation.
The dynamic-programming window control can be used to minimize the expected total number of contention slots before a successful transmission is possible. The following definitions are needed:
n(a,b): the minimum expected number of contention slots to resolve contention given that all contention parameters are in the window (a,U] and collision occurs in the current window (a,b];
g(w,a,b): probability of successful transmission in the next contention slot if a window of (a,w], a<w<b, is used;
l(w,a,b): probability of collision in the next contention slot if a window of (a,w], a<w<b, is used;
r(w,a,b): probability of no transmission in the next contention slot if a window is (a,w], a<w<b, is used.
Note that:
The problem of optimizing the window control can be formulated recursively as follows: ##EQU1##
The probabilities g(w,a,b), l(w,a,b) and r(w,a,b) can be derived from the distributions of the contention parameters and the state of collision. When transmission is unsuccessful, it is always possible to identify a window (a,b] such that at least two of the x.sub.i 's lie in (a,b] and no x.sub.i is smaller than a. This condition is designated as event A.
Suppose the window is reduced to (a,w], a<w<b, in the next slot. Three mutually exclusive events corresponding to the three possible outcomes can be identified in the next slot:
From these events, the probabilities can be derived as: ##EQU2## The event A.andgate.B means that exactly one of the x.sub.i 's is in (a,w], at least one x.sub.i is in (w,b], and all others are in (w,U]. The event A.andgate.C means that at least two x.sub.i 's are in (w,b] given that all x.sub.i 's are in (w,U].
Let F.sub.i (x) be the distribution function for generating x.sub.i, `.ltoreq.1i.ltoreq.N where N is the total number of stations in the network, and n is the number of stations that are contending, then event A has the probability: ##EQU3##
When the protocol is being utilized for contention resolution, F.sub.i could illustratively be the Uniform Distribution Function. When the protocol is being used for load balancing, which will be discussed later, F.sub.i could illustratively be the distribution function determined by the distribution of the response times of the processors.
The first and last terms of equation (3) indicate the probabilities that all x.sub.i 's are greater than a and b, respectively. The second term is the probability that exactly one of the x.sub.i 's is in the window (a,b]. Similarly, ##EQU4##
It follows that an optimal window can be derived in each step of the contention process once the distributions of the contention parameters are known. However, the dynamic-programming formulation is continuous and requires infinite levels of recursion. Some boundary conditions must be set to stop the evaluation after some levels. In practice, the x.sub.i 's are indistinguishable if their difference is less than .delta., the minimum increment of a subinterval during iteration. It is assumed that when the window size is smaller than .delta., the probability that two stations have generated parameters in this interval is so remote that contention can always be resolved in one step. The boundary condition is:
.delta. was illustratively set to one-tenth of the number of contending stations in the evaluations.
Referring to FIG. 1, a flow diagram showing an illustrative sequence of steps for implementing the above-described window control procedure is shown. In the flow chart, the following definitions are used:
v: size of a subinterval;
.delta.: minimum increment of subinterval during iterations;
x: temporary lower bound of a search subinterval;
y: temporary upper bound of a search subinterval;
t: temporary expected number of contention slots;
w: temporary upper bound of a window;
W.sub.opt : optimal upper bound of the window;
n(a:b-.delta.,a+.delta.:b): two-dimensional array containing the minimum expected number of contention slots expended in a search interval, each dimension is in increments of .delta..
In the first step, the lower bound, a, of the search interval, the upper bound, b, of the search interval, and the estimated number, n, of contending stations are input. For the first contention, a and b are L and U, respectively, and n is estimated as discussed later. The next step is the initiallization of the two-dimensional array n(x, x+.delta.) to zero for all of a.ltoreq.x.ltoreq.b-.delta.. v is initialized to .delta.. As mentioned previously, .delta. is a preset value and is illustratively one-tenth the estimated number of contending stations n.
In the next step, the subinterval v is increased by .delta. and the temporary lower bound x of the search subinterval is set to a. Proceeding to the next step, the temporary upper bound of the search subinterval is set to x+v, the minimum expected number (n(x, y)) of contention slots expended in the search subinterval (x, y) is set to .infin. and the temporary upper bound of the window is set to x+.delta..
In the next step, the probabilities of a contention being a collision, successful, or idle are computed using the indicated equations. Next, the expected number of contention slots, t, for the current w, x, y are computed by using the disclosed equation.
The computer number of expected contention slots is then compared to the number of expected contention slots stored in the array location n(x, y). If the computed number is less than the stored number, the sequence continues to the next step. Otherwise, the sequence skips over the next step. Assuming t<n(x, y), the computed number, t, is placed in the array location n(x, y) and the optimal upper bound W.sub.opt of the window is set equal to w.
At the next step, the temporary upper bound, w, of the window is increased by .delta.. Proceding to the next step, the new temporary upper bound, w, of the window is compared to the temporary upper bound, y, of the search subinterval.
If w<y, every possible value of w in the search subinterval (x, y) has not been tested, so the program returns to point 10, where the new value of w is checked to see if it returns a lower expected number of contention slots than has already been found.
If w.gtoreq.y, every value of w in the search subinterval (x, y) has been checked to determine which value of w returns the least number of expected contention slots for the current search subinterval (x, y). The temporary lower bound, x, of the search subinterval (x, y) is now adjusted by incrementing it by .delta..
Next, the sum of the new temporary lower bound, x, plus the subinterval size, v, is compared against the upper bound, b, of the search interval to determine if all possible values for the temporary lower boundary x have been utilized in finding a w which minimizes the expected number of contention slots for the search interval (a, b) using the search subinterval size v. If x+v<b, the program returns to point 12 and generates a higher temporary upper boundary, y, and then retraces the steps for determining the optimum w in the new search subinterval.
If x+v.gtoreq.b, the size, v, of the subinterval is compared against the size, b-a, of the search interval to determine if every possible size of subinterval has been utilized. If v.gtoreq.b-a, the iterations are done and the optimal upper window boundary, W.sub.opt for the search interval (a, b) to minimize the expected number of contention slots has been found and is returned. Otherwise, the program returns to point 14, where the subinterval v is incremented by .delta., x is set equal to a, and the sequence essentially begins anew using the larger subinterval size for v.
FIG. 2 illustrates the performance of the window protocol for different window control and load-estimation rules in which the distribution of the contention parameters is uniform between .0. and 1. The results of an evaluation for uniform distributions between 0 and 1 are plotted in FIG. 2. These results show that the average number of contention slots is bounded by 2.3 and is load-independent. Load independence is a desirable result which cannot be achieved by any existing protocol.
A greedy window control scheme is a scheme that maximizes the probability of success, g(w, a, b), in each contention step. The scheme is an optimal greedy window scheme when an optimal window that maximizes g(w, a, b) is found in each step. When the contention parameters have identical continuous distributions, F(x), g(w, a, b) can be expressed as: ##EQU5## where K=n/Pr{A}. It can be shown that Equation 6 is unimodal between a and b, so a maximum exists in the window (a, b). To find the optimal value of w, [d/(dw)][g(w, a, b)] is set equal to zero and solved for w. Assuming that F(w).noteq.0, this leads to the following:
Let z=1-F(w) and Equation 7 becomes: ##EQU6## It can be shown that a real root of Equation 8 exists and satisfies (1-F(b))<z.sub.o <(1-F(a)). There is no closed form to Equation 8, and z.sub.o has to be solved numerically. The upper boundary of the window, w.sub.o, can be computed directly from z.sub.o as follows:
Referring to FIG. 3, an illustrative flow sequence for implementing the steps for optimal greedy window control is shown. The following defintions are used in FIG. 3: ##EQU7## At the first step, the lower bound, a, of the interval, the upper bound, b, of the interval, and the estimated number, n, of contending stations are input in the same manner as in FIG. 1. The distribution function, F, of the contention parameters is also input. If the protocol is being used to resolve contentions, F could illustratively be the Uniform Distribution Function. If the protocol is being used for load balancing, F would be a distribution function determined by conventional statistical techniques from the distribution of the expected job response times of the various stations.
Proceding to the next step, the temporary lower bound, x, is initialized to F(a) and the temporary upper bound, y, is initialized to F(b). In the next several steps of the routine, a sequence for using Simpson's method, as discussed by C. F. Gerald in Applied Numerical Analysis (Addison-Wesley 1970) to solve the equation z.sup.n-1 +C.multidot.z.sup.n-2 +D=0 is shown. These steps return a suboptimal value of, W(g), the window's upper boundary.
The performance of the optimal greedy control scheme is suboptimal and approaches 2.7 contention slots for each successful transmission (see FIG. 2).
The approximate greedy window control scheme is similar to the optimal greedy window control scheme except that an approximate solution to the success-probability equation in Eq. 6 is found. Equation 6 can be rewritten as: ##EQU8## where v=[1-F(b)]/[1-F(w)]. An approximation function g(w, a, b) can be obtained by substituting (n-1) for ##EQU9## That is, ##EQU10## where K'=(n-1).multidot.K. g(w, a, b) is maximized at a position very close to that of g(w, a, b) and can be obtained by solving [d/(dw)][log g(w, a, b)]=0. This results in: ##EQU11## or equivalently, ##EQU12## A solution to Eq. 12 in the interval (F(a), F(b)) is given by: ##EQU13##
Referring to FIG. 4, a flow sequence for implementing the equations for approximate greedy window control is shown. The same definitions used for FIG. 3 are also used here.
In the first step, the lower bound, a, of the interval, the upper bound, b, of the interval, the estimated number, n, of contending stations and the distribution function F of the contending parameters are input.
Proceeding to the next step, C and D are calculated by using the equations: ##EQU14## C and D are variables in which the calculated values are stored. In the next step, z.sub.o is calculated using the equation ##EQU15## W.sub.a is next calculated from the equation W.sub.a =F.sup.-1 (z.sub.o). W.sub.a is the upper boundary of the window which will tend to minimize the expected number of contention slots. Although W.sub.a, as determined by this routine, is suboptimal with respect to previously discussed methods, approximate greedy window control provides for a much faster method of determining W.sub.a.
The approximate window, W.sub.a, calculated from Eq. 13 gives a performance that is nearly as good as that of the optimal greedy window scheme (see FIG. 2).
Window control with global distribution is a scheme that uses the statistically collected distribution of the first-order statistic, y.sub.1, to optimize the success probability g(w, a, b). This is necessary when the distributions of the contention parameters are non-identical and are not available to all the stations. Since the optimization of g(w, a, b) depends on the distributions of the first- and second-order statistics, y.sub.1 and y.sub.2, respectively, it is only possible to predict the probabilities of successful transmission or collision and no transmission with the information on the first-order statistic alone. The dynamic-programming formulation in Eq. 2 is reduced to: ##EQU16## such that
l(w, a, b) in this case is the probability of successful transmission or collision. The definition of r(w, a, b) remains the same as before. Using this formulation, the overhead of contentions can no longer be kept constant and is increased to O(log.sub.2 n). However, the performance depends on the entropy of the estimated distribution. A small entropy implies less uncertainty in identifying the minimum, and thus a better performance.
A binary-divide window control scheme is derived from the optimal greedy window control scheme by setting the number, n, of contenders equal to two. When n=2, both of Equations 8 and 13 have the same solution, F(w.sub.o)=[F(a)+F(b)]/2. If F(y) is uniformly distributed over (0,1], then w.sub.o =(a+b)/2. The binary-divide control rule can be used as a heuristic for window control with general distribution functions. It can be interpreted as one that always predicts that there are two contending processors. As a result, it performs satisfactorily when the channel is lightly loaded and degrades slightly when the channel load is heavy.
Referring to FIG. 5, a flow sequence for the steps of binary-divide window control is shown. In the first step, the lower boundary, a, of the search interval, the upper boundary, b, of the search interval, and the distribution function, F, of the contending parameters are input. a, b and F are as discussed previously.
In the next step, z.sub.o is calculated using the equation ##EQU17## W.sub.b is then calculated by using the equation
W.sub.b is the upper boundary of the window which tends to minimize the expected number of contention slots. The performance results are illustrated in FIG. 2.
The window control schemes can be implemented by either real-time calculations or with the lookup table method. The appropriate window to be used in the next contention slot can be calculated after the result of contention in the current slot is known. However, real-time computation with dynamic programming is impractical because of the high computational complexity. For example, when N=20, the execution time for a dynamic-programming solution (Eq. 2) is 1.3 seconds on a Digital Equipment Corporation VAX 11/780 computer. When N=100, the time is increased to 828 seconds. On the other hand, in a lookup-table method, the control windows for different contending situations are precalculated and stored. During contentions, the appropriate window boundaries are retrieved according to the outcomes of previous contentions. There are two alternatives: Binary Decision Tree and Truncated Binary Decision Tree.
Binary Decision Tree: FIG. 6(a) illustrates such a window search process. The triangle node of the tree represents the choice of window with respect to the search interval. The branches of a node represent the possible outcomes of a contention. Referring to FIG. 6(a), given a channel load n, the sequence of optimal windows derived from the dynamic window-control rules constitutes a binary decision tree. The root of a subtree represents a window. The optimal window for the next slot will reside in the left subtree if a collision is detected in the current slot. On the other hand, the optimal window for the next slot is in the right subtree if no transmission is detected. A set of binary trees, each of which corresponds to a channel load, can be constructed and stored as a lookup table in each station. The optimal window in each contention step can, therefore, be retrieved efficiently. An assigned station will be responsible for updating the trees when the distributions change.
FIG. 6(b) illustrates the data structure for such a lookup table implementation, in which a node comprises two pointers and a window value. Contention windows w.sub.i,j, are pre-calculated according to their corresponding search interval as shown in FIG. 6(a) and stored in the data field of the corresponding node. n.sub.1 is determined as discussed later. n.sub.1 is then used as a pointer into the lookup table to enable w.sub.1,1 to be retrieved from the table as shown at 10. After the stations within the window contend, all stations determine if a collision occurred, if the contention was successful, or if no transmission occurred. If the contention was successful, the station isolated is permitted to transmit its data and the contention process begins anew.
If a collision occurs, the left pointer is used to point to another entry in the lookup table to retrieve W.sub.2,1 as shown at 12. If no transmission occurred, i.e., an idle condition was detected, the right pointer is used to point to another entry in the lookup table and to retrieve W.sub.2,2 as indicated at 14. The process continues until one station is isolated.
Truncated Binary Decision Tree: One problem with the binary decision-tree method is in the large memory space required. Since the average number of contention slots is small, some subtrees can be pruned to reduce the space without any significant degradation in performance. Window sizes in the pruned subtrees have to be obtained by interpolation techniques. Likewise, for those channel loads for which no decision trees are stored, interpolation has to be used to obtain the necessary windows.
The nunber of contending stations is estimated at the beginning of the current contention period from the distribution of the contention parameters and the statistics of previous channel activities. This information is essential in estimating an initial window and in controlling the dynamic changes in window sizes in the current contention period. Three possible methods are illustrated here.
At the end of the previous contention period (t-1) when exactly one station is isolated, the window, (a, w(t-1)], is known to all the processors. Assuming that the load is unchanged, a maximum-likelihood estimate of the current load, n(t), can be computed from a likelihood function which is the probability of success that the minimum lies in (a, w(t-1)]. Assuming that the contention parameters are distributed uniformly between 0 and 1, the likelihood function is derived as: ##EQU18## L(n(t),w(t-1),a) is maximized by setting n equal to the ceiling function of ##EQU19## where 0<w(t-1)<1, or: ##EQU20## n(t) is then utilized as the estimated number of contending stations in the current period, t, in the various window control schemes previously discussed. The average number of contention slots using an estimated channel load is 3.1 as shown in FIG. 2.
Since the extremum is readily available at the end of a contention period and can be "piggybacked" in the packet transmitted, an alternative estimate is based on the density function of this statistic. The conditional density of y.sub.1 is ##EQU21## When the distributions of the contention parameters are independent and uniformly distributed in [0,1],
Substituting Eq. 18 into Eq. 17 gives: ##EQU22## This result shows that the distribution of y.sub.1 is determined once the window (a, w] is known. Therefore, no new information is gained by using the first-order statistic in the likelihood function.
The accuracy of load estimation can be improved by using information on the previous windows that successfully isolate a single station. A technique in time-series analysis called Auto-Regressive-Moving-Average (ARMA) modeling (C. Chatfield, The Analysis of Time Series: Theory and Practice, Chapman and Hall, London, 1975) can be used to obtain an estimated window based on previous windows. A simple example is: ##EQU23## in which w.sub.mv (t) is the accumulated information on window sizes, t is the current contention period, and w is the window in the contention period (t-1) that successfully isolated a single station. Illustratively, w.sub.mv (t-1) is the average of all the values for the upper window boundary for the period up to and including the period (t-1) and w is the upper bound of the window at the end of the previous contention period (t-1). The value of w.sub.mv (t) is substituted for (w(t-1)) in Eq. 16 to estimate the channel load. The performance using ARMA load estimation is very close to that when the channel load is exactly known (FIG. 2).
Window control is also desirable for networks using a bit-parallel bus with two-state collision detection on each bit. The network supporting the protocol includes a synchronous parallel bus for transmitting data and codes, a bus-status control line for indicating the busy status of the bus, and, for each station, an intelligent interface that is capable of (a) sensing the bus-status control line, (b) reading data from the bus, (c) writing data to the bus, (d) generating random codes and (e) deciphering codes read from the bus. The time interval for generating a random number, writing the number to the bus and deciphering the code read from the bus is called a slot.
The scheme called Multiaccess Code-Deciphering (MACD) is based on the deciphering of codes to determine whether contention is allowed. To support the scheme on a bit-parallel bus, a collision-detection mechanism is needed. The Wired-OR property of the bus can be used here. That is, when two or more stations write on the bus simultaneously, the result is simply the bitwise logical OR result of these numbers. By interpreting the result after a write, each station can determine whether a collision has occurred.
Whenever a station has data ready to transmit, it senses the bus-status line first. If the bus is in use, then the station waits until the bus is idle. To contend for the bus, a station chooses a code randomly from a given code space, S, and writes it to the bus. The size, K, of the code space, S, comprises the set of all possible distinct codes in the code space, S. If the number of bits in the code is larger than the bus width, the code is broken down into segments of size equal to the bus width starting with the most significant bit. The segments are synchronously written in sequence by all the contending stations until a non-zero code segment is read after a write. At this time, the resulting code written on the bus is the bitwise logical OR of all the code segments written by the contending stations. Each contending station reads the resulting code segment written and computes the deciphered code using a code-deciphering function. Each contending station then compares the deciphered code with the code segment it generated locally. Three outcomes may be obtained:
the locally generated code segment is equal to the code segment read;
the locally generated code segment is not equal to the code segment read, but is equal to the deciphered code; and
the locally generated code segment is equal to neither the code segment nor the deciphered code.
The last outcome implies that this station has not generated the maximum code and has to wait until the next contention period. The first and second outcomes imply that this station has generated the maximum code and should be allowed to transmit. However, there may be other stations that have generated the same code. If there is more than one station in this set, a hidden collision is said to have occurred, and the contention-resolution process must be continued. There are two ways to detect a hidden collision. First, each station in this set generates an n-bit random number and writes it to the bus. To prevent the possibility of two stations generating the same random number, each station can use a distinct n-bit station-identification code as the random number. If the number read from the bus matches with the number written, then there is no hidden collision. If a hidden collision is detected, the MACD scheme is repeated. Second, we can assume that the hidden collision is not resolved, and the MACD scheme is repeated. The same process is repeated a number of times until there is a high confidence that exactly one station is isolated.
When the probability that a large number of stations have generated the maximum code is high, the second method of resolving hidden collisions is better because it is very likely that the MACD process has to be repeated, and the time for propagating the random number in the first method is saved. On the other hand, if the probability that exactly one station has generated the maximum code is high, the first method is better because hidden collisions can be detected more efficiently.
Before the scheme is described, it is assumed that there are N requesting stations, and each station writes a unary or binary random number X.sub.i (i=1, 2, . . . , N) to the bus. The term "unary" as it is used in this application is defined as an n-bit binary number having only one "1" bit. The X.sub.i s are chosen from a code space, S, with the following properties:
where .sym. is the bitwise logical OR operator. By reading data on the bus and applying the code-deciphering function, f, a station knows the maximum number written on the bus. This information provides a basis for the window control.
To show that there exists a code space of n bits in the unary representation that satisfies Equations 21 and 22, let S={0.sup.a 10.sup.b .vertline.a+b=n-1, a.gtoreq.0, b.gtoreq.0} where 0.sup.k represents a consecutive sequence of k zeros. For any n-bit unary number, X=(x.sub.1 x.sub.2 . . . x.sub.n), a deciphering function f on X can be defined such that:
It is easy to verify the relatedness property of Equation 21 for any two different elements u and v in S. To verify Equation 22, N codes are chosen randomly from S and,
By definition of S,
and
where m=min {a(i).vertline.i=1,2. . . ,N}. An overlapped variable Y=(y.sub.1 y.sub.2 . . . y.sub.n) is defined to be the bitwise logical OR of the c.sub.i 's, i.e.,
Y, as defined, retains the following properties:
and
By definition of the deciphering function, f,
or
Given the mechanisms for detecting collisions, and the code space, the important design issue is the control of the window. Two schemes are described here.
Load-Dependent Code-Deciphering Window Control with Unary or Binary Codes is a scheme based on a bit-parallel bus of width W and a code space of size K=W, W<1. If a bit-serial bus is used, (W=1), a large code space of size K>1 should be used, and the code generated has to be sent serially. Since the size of the code space is equal to the bus width, the maximum code generated is always included in the first write. A collision-detection procedure can be applied, and the maximum can be isolated eventually. An illustrative routine for the basic steps in each station contending for a bit-parallel bus with two-state collision detection and a load dependent code-deciphering scheme follows:
The time complexity of contention resolution can be measured by the mean number of contention slots in each contention period. To analyze this complexity, let N be the number of contending stations at the beginning of a contention period and K to be the size of the code space. In the load-dependent scheme, K is equal to the bus width, W. Assuming that the codes are chosen randomly, then a station generates a given code c.sub.i (i=1, 2, . . . , N) with probability 1/K. Designating the maximum of N such c.sub.s 's as c.sub.m, the mth code in the code space, c.sub.m, =max {c.sub.i .vertline.i=1,2, . . . , N}. If exactly one station generates a code c.sub.m and other stations generate codes less than c.sub.m, then the contention is resolved. The probability for this event to occur is: ##EQU24## Since m ranges from 1 to K and these K events are mutually exclusive, the probability that contention is resolved in one step is P.sub.K,W,N where K=W is: ##EQU25##
FIG. 7 illustrates the probability of success in one contention using a Multiaccess Code-Deciphering bus-arbitration scheme wherein K is the size of the code space, W is the bus width, and N is the number of contending stations. P.sub.K,W,N is plotted against N/W. it can be seen that the probability of success in one contention is higher if the code space (equals bus width, W) is larger for a constant number, N, of contending stations. It is observed that p.sub.K,W,N is a strictly decreasing function of N and decreases to zero when N is very large. In other words, the MACD scheme is unable to resolve contention in one step when the load is extremely heavy. However, most of the contending stations are eliminated in one attempt. The number of survivors is reduced significantly as contention proceeds, and the probability of success is consequently increased. The following analysis demonstrates this phenomenon.
Let it first be assumed that the maximum of the codes generated by the contending stations is c.sub.m, the mth code in the code space. There are then indicator variables x.sub.i, i=1, . . . ,N, ##EQU26## The random variable Z indicates the number of stations that generate c.sub.m in the contention. These stations are allowed to contend in the following steps. The expected value, E(Z.vertline.m,N,W), of Z given m, N and W, represents the average number of surviving stations. It is easy to show that: ##EQU27## Furthermore, the probability P(m.vertline.N,W=K), that the current maximum code, c.sub.m with N contending stations and a code space of K can be expressed as: ##EQU28## The expected number of stations that would survive a contention is: ##EQU29## The ratio ##EQU30## is a measure of the average fraction of contending stations that can survive a contention. Let N.sub.t (t=0,1, . . . ) be the expected number of contending stations in step t. By Eq. 27, we have ##EQU31## Therefore,
Referring to FIG. 7, P.sub.K,W,N approaches 1 as N<K=W, and P.sub.K,W,N approaches 0 as N>>K=W. This fact reveals that the contention process of the load-dependent scheme can approximately be divided into two phases. The effect of the first phase, i.e., when N.sub.t >K=W, is to reduce the number of contending stations. When the process enters the second phase, i.e., N.sub.t .ltoreq.K=W, contention can be resolved in about one step. The overall contention process will stop within an average of log.sub.K/2 (N.sub.0) steps. FIG. 8 shows the simulation results that confirms this analysis. FIG. 8 illustrates the average number of contention slots for resolving conflicts of bus requests using the Multiaccess Code-Deciphering scheme where K is the size of the code space, W is the bus width and N is the number of contending stations. The number of contention slots shown includes the additional slots required for resolving hidden collisons. MACD performs better when the bus width is large.
As shown in Equation 28 and FIG. 8, the scheme just discussed is load-dependent and performs well when the bus width is large and the number of contending stations is small. Since the number of contention slots grows logarithmically with the number of contending stations, the scheme is inefficient when the number of contending stations is large or the bus width is small.
The cause for the load-dependency is due to the fixed window control on a fixed code space. Since the window is fixed by the bus width, the code space can be designed so that it is a function of the number of contending stations and the bus width. This will reduce the number of stations contending in a slot. By choosing the size, K, of the code space, S, so that the number of stations contending in a slot is a relatively small constant as compared to the bus width, contention can be resolved in a time that is independent of load.
The solution depends on choosing the size of the code space and estimating the number of contending stations. Suppose N can be estimated accurately, and K/N=r. The probability that contention is resolved in one step (referring to Equation 24) is: ##EQU32## where q(m.vertline.N=K/r,K,W) is defined in Equation 23. The value of P.sub.K,N,W is plotted in FIG. 7. It is seen that the probability of success is higher and load-independent as a result of the increase in the size of the code space.
The expected number of stations that would survive a contention can also be derived similarly. In this case, the number of surviving stations is N if no station contends in the slot. Equation 25 becomes: ##EQU33## The definition of p(m.vertline.N,W) in Equation 26 remains true. The expected number of surviving stations in one contention is: ##EQU34## Since K/N=r, a constant, E(Z.vertline.N=K/r,W) is a constant independent of load if K is large as compared to W.
The correct choice of r is shown in FIG. 9. There is an optimal choice of r so that the number of contention slots is minimum. The optimal choice of r is experimentally determined for a particular configuration. The optimal value depends on the value of W and is load-independent, assuming that N is known. The value is approximately 5 for the combinations of W and N tested. Using the optimal value of r, the performance of the load-independent MACD scheme is plotted in FIG. 8. In generating these results, the size of the code space, K, is chosen to be W if r.multidot.N is smaller than W. That is, the load-dependent MACD scheme is used when the load is light. It is observed that the load-independent scheme requires a small constant number of slots when the load is heavy. An illustrative procedure is set forth as follows:
It is necessary to estimate the channel load in the current contention period, t, in the load-independent MACD scheme. A reasonable estimate of (N(t)) can be obtained by: ##EQU35## where B(t-1) is the number of bits that are ones in the previous contention period (t-1), K(t-1) is the total number of bits in the code space of size K for the previous contention period (t-1) and W is the width of the bus, i.e., the number of bits wide the bus is. This will systematically under-estimate the actual value of N(t), and some correction to the value of r used should be introduced.
FIG. 9 illustrates the optimal choice of the code-space size where W equals 16 and N equals 60. In FIG. 9, the optimal value of r that should be used is slightly different when the estimate in Equation 32 is used. The number of contention slots required is slightly increased when N is estimated.
Due to random noises and component failures, the collision-detection mechanism may fail to detect the presence or absence of collisions at a particular station. When different collision information is received by different contending stations, the window will be updated differently and will not be synchronized. This may result in indefinite contentions or another contending station besides the one having the extremum winning the use of the channel. A solution to this problem is to restart the contention process whenever: (1) contention has not been resolved after a threshold number of contention slots; or (2) a contending station does not agree with the extremum of the winner in the contention process. In the second case, the extremum is broadcast after a winner is found. Any station that does not agree with the winner can introduce further collisions in the network so that the contention process can be restarted. In case the process is restarted frequently, a network failure will be reported.
As can be appreciated from the foregoing, this invention provides an improved collision-detection protocol that is particularly useful in bit-serial and bit-parallel bus systems. The implementation of the contention-resolution protocol can be in hardware, software or firmware.
A contention parameter used in the contention-resolution protocol can be either of discrete type or of continuous type. Distributions governing the generation of such contention parameters may be either identical or nonidentical, but should be independent of each other. The generation of contention parameters with identical distributions usually simplifies the window controls. A contention parameter, X.sub.i, generated by a continuous distribution, F.sub.i (.multidot.), can be transformed into another contention parameter, X'.sub.i, that is uniformly distributed over (0,1) by the following equation, as described by Papoulis in Probability, Random Variables, and Stochastic Processes, McGraw Hill, N.Y., 1965:
The generation of parameters with nonidentical distributions can thus be mapped to those with identical uniform distributions. This transformation is a one-to-one mapping and the window control as performed on the transformed contention parameters can be shown to be equivalent to that applied to the original parameters. Although, some properties are not preserved after the transformation, the efficiency of the contention resolution is not affected.
A window control scheme is designed to reduce the contention overhead by reducing the number of contentions. Any distributed algorithm that produces synchronized windows in the process of contention can be used as a window control scheme. Since the contention parameters are generated randomly, there are uncertainties in isolating the minimum. A good window control scheme will use the more available information in predicting the position of the minimum. This information includes channel load, distributions of contention parameters, and statistics collected from channel activities. The performance of a window protocol depends on the way that this information is utilized.
For a bit-parallel bus, any code space and deciphering function that satisfy the properties of Equations 21 and 22 are suitable for code-deciphering window control.
The channel load can be estimated from statistical information collected in the window protocol, and a separate estimation mechanism is not needed. Load estimation methods for the window protocol include any inference method based on distributions and/or dynamic information collected from channel activities.
The window protocol works independently of the collision-detection mechanisms. It can be implemented on any bus that has a three-state collision-detection capability. This includes three-state bit-serial buses and two-state bit-parallel buses. In a two-state collision-detection mechanism, an additional verification phase must be added to simulate a three-state mechanism.
The contention-parameter-generation mechanism of the window protocol can be implemented either explicitly or implicitly. The efficiency of any contention-resolution protocol that can be unified into the window protocol can be optimized by the disclosed window-control scheme. This is done by identifying the protcols' implicit contention parameters and the corresponding distribution functions. Three existing adaptive CSMA/CD protocols are demonstrated below to show the application of the window control to improve their performance. The contending parameters for the first two protocols are discrete, while those of the last one are continuous.
The Adaptive-Tree-Walk Protocol was proposed by J. Capetanakis, IEEE Transaction on Information Theory, Vol. IT-25, No. 5, 505-515 (1979). It is basically a preorder binary-tree traversal algorithm. A binary tree is organized in such a way that each leaf is associated with a station in the network. The search begins at the root, and all ready stations can transmit in the first contention slot. If a collision occurs, the search continues recursively with the left and right subtrees in the following contention slots. The search stops when a single ready station is contained in a subtree. After the packet is transmitted, the next contention slot is reserved for the next subtree in the preorder search.
This protocol can be viewed as a moving window protocol in which the size of the window is equal to the number of leaves in the subtree. The objective is to isolate a station with the minimum distance from the origin of the window. Without loss of generality, let it be supposed that the origin is currently at station 1. A ready station i generates a contention parameter that is the distance from 1, while an idle station generates a very large number that is never considered by the protocol, say N+1. The probability density function from which a station generates its contention parameter is: ##EQU36##
The probability density function Equation 34 can be inferred from the statistical data collected from the channel. The objective is to provide a dynamic inference method so that an adaptive window-control scheme can be applied.
The channel load is characterized by the number of packets transmitted when the window has circumscribed around the stations once. This number can be collected directly on the network. Suppose there is only one buffer at each station. Let p be the probability of a new packet arriving in a packet-transmission time, assuming that contention time is much smaller than packet time, and t.sub.i be the number of packet times elapsed since the ith station was allowed to transmit. Then
p is a function of N, the total number of stations in the network, and n, the number of stations that have transmitted when the window has circumscribed over all the stations once. The next station allowed to transmit must have been idle for n packet times, and the probability that a packet is ready is (1-(1-p).sup.n). For a network of N stations, the expected number of stations that transmit is:
Solving Equation 36 yields: ##EQU37##
The term t.sub.i in Equation 35 can also be estimated from n. In order to compute t.sub.i, it is necessary to know the minimum and maximum number of stations that could have transmitted when the window has moved from station i to the current origin. The maximum cannot exceed either n or N-i, and the minimum cannot be less that either 0 or n-i. The number of active stations between station i and the origin has an incomplete binomial distribution with probability (N-i)/N. ##EQU38## The equations derived here are approximations because they assume that each station has constant elapsed time before it is allowed to transmit.
Substituting Equations 35, 37 and 38 into Equation 34, the distribution function for station i, 1.ltoreq.i.ltoreq.N, to generate its contention parameter is: ##EQU39##
From the view of the window protocol, the adaptive-tree-walk protocol is a heuristic way of controlling the window size by halving or doubling it after each contention. Its efficiency can be improved by any control rule of the disclosed invention. The distributions shown in Equation 39 can be applied in the dynamic-programming window control described previously. The distribution has two properties that can simplify the complexities of the dynamic-programming formulation: (1) F.sub.i (k)=0 for k<i; and (2) F.sub.i (a)=F.sub.i (b) for i.ltoreq.a,b.ltoreq.N. From these, ##EQU40## The performance of the Adaptive-Tree-Walk and Urn Protocols optimized by dynamic-programming window control is shown in FIG. 10 where N is the number of contending stations.
The Urn Protocol was proposed by Kleinrock and Yemini, Proceeding of International Communication Conference, 7.2.1-7.2.5 (1978). The protocol does not generate contention parameters, but employs an explicit window control mechanism and is similar to the Adaptive-Tree-Walk Protocol. In the perspective of the window protocol, each ready station generates a contention parameter that is the distance from the origin of the window. The distribution function given in Equation 39 thus applies. The difference lies in the method of window control. In the Urn Protocol, the initial window size, w, is chosen by optimizing the Urn model. During each contention slot, those stations inside the window are allowed to transmit. The window is advanced w positions if there is a successful or no transmission. In case of collision, the window is shrunk to half of its original size. This window-control scheme is good when the ready stations are uniformly distributed. However, due to the round-robin service discipline, those stations closer to the origin of the window have a longer elapsed time since last enabled thus having a higher probability of becoming active. The asymmetry of distributions deteriorates the performance of the conventional Urn Protocol. By using the control methods of the disclosed invention, a better scheme is expected. Since the Urn Protocol uses implicit contending parameters that are similar to the Adaptive-Tree-Walk Protocol, the control rules developed for the latter protocol can also be applied here.
Among the protocols considered, the Tree-Walk and Urn Protocols have the highest certainty about the values of the x.sub.i 's. The performance is, therefore, expected to be the best. FIG. 10 verifies this fact and shows that perfect scheduling can be achieved when the load is heavy. It should be noted that the performance degrades as the total number of stations increases. As N approaches .infin., the protocol behaves more like one with continuous distributions.
Towsley proposed a window protocol, termed the Arrival Time Window Protocol, in which all stations have a common window on the time axis of length u in the past. IEEE Transactions on Computers, Vol. C-31, No. 8, 715-722, (1982). Stations with packets arriving during the window are allowed to contend. If there is a successful contention or no transmission, the window is advanced u units of time. Otherwise the window is reduced to a fraction, f, of its original size, and the process is repeated until a packet is transmitted successfully. The parameters u and f are chosen to optimize the performance. However, they do not reflect instantaneous load conditions.
Let it be assumed that the window begins at time O, the current time is T, and there are n contending stations. Towsley's protocol searches for the earliest packet arrival time in this window. In mapping this to the window protocol, it is equivalent to using the first packet-arrival time in the interval (O,T) in each station as the contention parameter, and granting channel access to the station with the minimum contention parameter. To derive the distribution of the contending parameters, assume the arrival process at each station to be Poisson. The distribution of the first arrival time conditioned on the current time T and the origin of window O is: ##EQU41## where .lambda..sub.i is the packet arrival rate at station i. This distribution is an incomplete exponential distribution. Notice that if .lambda..sub.i .noteq..lambda..sub.j, then F.sub.i (t).intg.F.sub.j (t).
Since these contention parameters can be transformed into parameters that are independent and uniformly distributed over (0,1) (Equation 33), Equations 4 and 5 can be reduced to simpler forms: ##EQU42## These equations can be applied in the dynamic-programming window control (Equation 2).
The window protocol provides a distributed way of finding extreme values from a set of random numbers. With this protocol, an extremum can be sought at the speed of data transmission without introducing additional overhead in information exchange. This extremum identification is a general primitive operation in many applications. For example, sorting of a set of numbers can be done by identifying the extrema sequentially. Some applications are intrinsically extremum-identification problems, while others may be solved with the aid of extremum identification. An example an global priority identification is demonstrated below:
The identification of the most immediate priority level in the network is equivalent to finding the most immediate priority from a set of n contending stations (priority classes ranging from 1 to P). It can be solved by the contention-resolution algorithm in which the highest priority class at each station is used as the contention parameter. Illustratively, the most immediate priorty could be the highest priority level in the network.
In pursuing the distributions of the priority classes, it is assumed that the message arrival rate of priority class i at station j is .lambda..sub.i,j ##EQU43## and the corresponding service rate is .mu..sub.i,j. Suppose the channel can service a message of class i at rate .mu..sub.i. Since a lower priority message can only be serviced during an idle period of servicing higher priority messages, the effective service rate of class i messages in the channel is: ##EQU44## where .rho..sub.k is the traffic intensity of class k messages in the system. By definition, ##EQU45## From queueing theory, the effective service rate of class i messages at node j is: ##EQU46## The traffic intensity of class i messages at node j is: ##EQU47## Class i will be empty at node j with probability 1-.mu..sub.i,j. Thus node j will generate a contention parameter of value p with probability: ##EQU48## The distribution of the contention parameter at node j is: ##EQU49##
The optimization of window protocols for priority resolution using dynamic programming is similar to, but more efficient than, protocols with continuous distributions because the contention parameters can only be assigned integers, and recursion can stop when the window size is smaller than one. The boundary conditions for the dynamic-programming formulation (Eq. 2) become:
These boundary conditions assure that contention can always be resolved in finite steps. The performance was evaluated by assuming that a packet has equal probability of being at any priority level. FIG. 11 illustrates the performance of the window protocol for global priority resolution operated under dynamic-programming window control where P is the number of priority levels. The results plotted in FIG. 11 show that the expected number of contention steps is bounded by a constant regardless of channel load. The performance is improved when the channel load is heavy because there is increased certainty for a high priority message to exist. However, the performance is slightly worse when the number of priority levels is large.
Two methods of applying the code deciphering scheme to support global priority identification are described below.
The code space of the original MACD scheme is partitioned into subspaces so that each subspace corresponds to a priority level. The partition should satisfy the following condition:
where S.sub.i and S.sub.j are subspaces corresponding to priority levels i and j respectively. Using this partitioning, priority levels are encoded into the contending codes, and the deciphering function discussed previously can identify the global priority level and the largest code in this level.
A contention period can be divided into two phases: a priority-resolution phase followed by an intra-class contention phase. In the priority-resolution phase, a strictly increasing function that maps a set of priority levels onto a code space is defined in each contention slot. The mapping is done so that the minimum number of priority levels is assigned to the same code. In a contention slot, every contending station writes its code to the bus and deciphers the number read from the bus. A set of stations with the most immediate priority levels, illustratively the highest priority levels, (corresponding to the deciphered code) are identified. The process is repeated until the set of stations with the most immediate priority level are identified. When the bus width is larger than or equal to the number of priority levels, this phase can be completed in one contention slot.
One of the functions of a computer network is to allow the sharing of resources that include the access of programs and databases, and the sharing of computational facilities. Load balancing is a scheme that engages communication facilities to support remote job execution in a user-transparent manner so that the utilization of resources is improved. Depending on the workload of processors on the network, the network operating system may distribute newly arrived jobs to a remote processor, or may schedule them for local execution. In practice, the scheduling is embedded in operating system controls and incurs a large overhead of status distributions. A more efficient way to implement load balancing on multiaccess bus systems is described here.
On multiaccess bus systems, only one job can be sent over the network at any time. The best strategy is to send a job from the processor with the heaviest load to the processor with the lighest load. In order to support this load balancing strategy, the following tasks are involved:
(a) to decide when load balancing is needed;
(b) to identify the processors with the maximum and minimum load;
(c) to send a job from the processor with the maximum load to the processor with the minimum load; and
(d) to send the results of execution back to the originating site.
Three basic operations are needed to support these tasks:
(a) Contention resolution for packet transmission: When multiple processors wish to transmit, each processor generates a random number. The processor assigned the channel is the one with the minimum number.
(b) Identification of the processor with the maximum (resp. minimum) load: The load on a processor is characterized by the response time of executing a job on that processor. The response times of all the processors are distributed in the interval [0, .infin.). Finding the processor with the maximum (resp. minimum) load is equivalent to finding the maximum (resp. minimum) of a set of random numbers in the interval [0, .infin.).
(c) Identification of processors with the global priority: The priority of a processor is an integer from the set {0, 1, . . . , p.sub.max }. The identification problem searches for the maximum priority value of all the processors in this interval.
The three operations can be implemented efficiently by the disclosed contention-resolution algorithm. A simulator was developed to evaluate the performance of load balancing as supported by the contention resolution algorithm. The simulator was written in ASPOL and was run on a CDC 6600. It was assumed that job arrivals were Poisson at each processor and the service time was exponentially distributed. FIG. 12 illustrates the reduction in job response time under load balancing with no message traffic where the number of processors is equal to twenty and the ratio of service to transmission delays is one. The normalized mean job response time is plotted against different job traffic intensity with no message traffic in FIG. 12. The results are compared against the case without load balancing, that is, the case of multiple independent M/M/1 queues. This shows that the response time is always better when load balancing is applied.
Since the queue at each processor is almost empty when the job traffic is low, load balancing is less effective. FIG. 13 illustrates the effect of the ratio of service to transmission delays, r, on load balancing where the number of processors is equal to twenty. In FIG. 13, the job response time with respect to the ratio of job service time and transmission delay is shown. The percentage of jobs being migrated is also shown. As interpreted from this figure, a system with fast processors coupled with a slow communication channel (r is small) will not benefit from load balancing. As the speed of the communication channel increases, more jobs are migrated and the response time is improved. However, when the channel speed exceeds a certain threshold, load balancing can provide little improvement. In the simulator, the policy is chosen so that load balancing is invoked when the network is idle. This policy assures that the transfer of regular messages is not deteriorated by load balancing. FIG. 14 illustrates the effect on load balancing due to message traffic where the job traffic intensity at each processor is equal to 0.5 and the number of processors is equal to twenty. As message traffic becomes higher, the effective channel capacity is less and load balancing is not carried out as often.
Resource sharing mechanisms play a role similar to the load balancing mechanism previously described. However, the resources considered here do not have buffers, and jobs are queued at requesting sites until they are ready to be scheduled. Conventionally, the dispatch of requests to idle resources is done in the operating system by maintaining a resource table. This centralized approach has large message overheads, is unreliable and potentially may become a bottleneck. The contention-resolution protocol disclosed here can be used as a decentralized protocol for scheduling resources. The scheme includes two phases: a request-contention phase and an acknowledge-contention phase.
(a) Request contention: Whenever there is a job in the queue, a local dispatcher contends for the channel to broadcast a request and to identify itself. Different types of request are allowed to contend in this phase. A request may need multiple resources.
(b) Acknowledge contention: Immediately following a successful request contention, all idle servers that are capable of executing the request will contend to acknowledge the request. If the request needs multiple resources, all the resources have to be searched and allocated in one contention interval to avoid deadlock. Allocating multiple resources to a request is done by repeating the acknowledge phase. The resources to service the request are found at the end of this phase, and the request and resources cooperate in job execution through the communication facilities.
A contending parameter generated in either phase of contention may be a uniformly distributed random number. It may also be generated according to certain scheduling policy. For example, the arrival time of a request may be used as the request contention parameter to facilitate a first-come-first-serve (FCFS) scheduling policy.
Although the invention has been described in detail with reference to certain preferred embodiments and specific examples, variations and modifications exist within the scope and spirit of the invention as described and as defined in the following claims.
Claims
What is claimed is:
1. In a data communication system having a common bus with time division multiplexing and a plurality of stations coupled to the bus, a bus contention resolution process for resolving which station is permitted to transmit data onto the bus during a given time slot, comprising the steps of (a) each station wishing to contend for the bus to transmit data during the time slot generating a contention parameter; (b) each station generating a window boundary, w, as a function of: an interval lower boundary, lb, an interval upper boundary, ub; an estimated number, n, of contending stations; and a distribution function, F, of the contention parameters; (c) each station generating a window having boundaries w and one of lb and ub; (d) each station wishing to contend for the bus comparing its contention parameter to the window and contending for the bus by transmitting to the bus when its contention parameter falls within the window; (e) each station sensing the status of the bus; (f) each station adjusting its window in response to the bus status it sensed indicating the bus was idle or a collision occurred and repeating steps d-f until only one contending station is isolated as having successfully contended for the bus; and (g) the isolated station transmitting data in the time slot.
2. The process of claim 1 and further including the step of terminating the contention process after a predetermined number of iterations of steps d-f.
3. The process of claim 1 and further including the step of estimating n by equating n to a ceiling function ##EQU50## where w(t-1) is the final window boundary derived from the contention process for the immediately preceding time slot, and 0<w(t-1)<1.
4. The process of claim 3 wherein, for the purposes of estimating n, w(t-1) is estimated by an auto-regressive-moving-average model.
5. The process of claim 1 wherein F comprises a uniform distribution function.
6. The process of claim 1 and further comprising the steps of (h) broadcasting an extremum over the bus and (i) restarting the contention resolution process if a contending station disagrees with the extremum.
7. The process of claim 1 and further including a step wherein each station collects statistical information concerning bus activity, the step of generating a window boundary, w, includes a step of estimating n as a function of the collected statistical information.
8. The process of claim 1 wherein the step in which each contending station generates a contention parameter comprises a step wherein each contending station generates a contention parameter related to a priority for the station, and the step wherein each station adjusts its window comprises a step wherein each station adjusts its window to isolate the station with the most immediate priority.
9. The process of claim 1 wherein the step in which each device adjusts its window in response to the bus status it sensed comprises a step wherein each device adjusts its window in the same manner for a particular sensed bus status.
10. The process of claim 9 wherein the window has the boundaries lb and w and the step of adjusting the window comprises equating ub to w when the sensed bus status indicates a collision has occurred, equating lb to w when the sensed bus status indicates no station contended, and, in either case, generating a new w as a function of n, F, lb, and ub.
11. The process of claim 9 wherein the window has the boundaries w and ub and the step of adjusting the window comprises equating lb to w when the sensed bus status indicates a collision has occurred, equating ub to w when the sensed bus status indicates no station contended, and, in either case, generating a new w as a function of n, F, lb, and ub.
12. The process of claim 9 wherein the bus comprises an asynchronous, serial bus having three-state collision detection.
13. The process of claim 1 wherein the step of each station generating its window boundary w comprises each station recursively optimizing the step of generating w in accordance with the equation. ##EQU51## where n(a,b): the minimum expected number of contention slots to resolve contention given that all contention parameters are in the window (a, U] and collision occurs in the current window (a,b]; g(w,a,b): probability of successful transmission in the next contention slot is a window of (a,w], a<w<b, is used; l(w,a,b): probability of collision in the next contention slot if a window of (a,w], a<w<b, is used; r(w,a,b): probability of no transmission in the next contention slot if a window of (a,w], a<w<b, is used; a: lower boundary of the current window (L being the minimum); b: upper boundary of the current wind (U being the maximum); and l(w,a,b)+g(w,a,b)+r(w,a,b)=1.
14. The process of claim 1 wherein the step of each station generating its window boundary w comprises each station generating w by using optimal greedy window control wherein ##EQU52## where K=n/Pr(A); a=the lower boundary of the current window (L being the minimum lower boundary); b=the upper boundary of the current window (U being the maximum upper boundary); ##EQU53## g(w,a,b)=the probability of a successful contention occurring in the next contention slot; and said distribution function F comprises identical continuous distributions for said contention parameters.
15. The process of claim 1 wherein the step of each station generating its window boundary w comprises each station generating w by generating w.sub.a, an estimated w, by approximate greedy window control wherein ##EQU54## where K'=(n-1).multidot.K; K=n/Pr(A); a=the lower boundary of the current window (L being the minimum lower boundary); b=the upper boundary of the current window (U being the maximum boundary); ##EQU55## g(w,a,b)=the probability of a successful contention occurring in the next contention slot; ##EQU56## in the interval (F(a), F(b); ##EQU57## and said distribution function F comprises identical continuous distributions for said contention parameters.
16. In a time division multiplex data communication system having a plurality of data communication stations coupled to each other by a common bus, a contention resolution process for resolving which station is permitted to transmit data onto the bus during a given time interval, comprising the steps wherein (a) each station that wishes to contend for the bus to transmit data during the time interval generates a contention parameter; (b) each station generates a window boundary, w, as a function of: an interval lower boundary, lb, an interval upper boundary, ub; an estimated number, n, of contending stations; and a distribution function, F, of the contention parameters; (c) each station generates a window having boundaries w and one of lb and ub; (d) each station that wishes to contend for the bus compares its contention parameter to the window and contends for the bus when its contention parameter falls within the window; (e) each contending station generates a contention code; (f) each contending station writes its contention code to the bus; (g) each contending station reads the bus; (h) each contending station compares what it read from the bus to the contention code it wrote to the bus and determines if it can continue to contend for the bus in response to the comparison; and (i) each station which determines that it can continue to contend for the bus repeating steps f-i until a station is selected and permitted to transmit data onto the bus during the given time interval.
17. The process of claim 16 wherein the step of each contending station generating a contention code and writing the contention code to the bus comprises each contending station using its contention parameter as the contention code and writing its contention parameter to the bus.
18. The process of claim 16 and further including the step wherein each contending station uses a deciphering function to compute a deciphered code from what it read and the step of each station comparing what it read from the bus to what it wrote to the bus comprises the step of each contending station comparing its deciphered code to what it wrote to the bus.
19. The process of claim 18 wherein each deciphered code comprises the maximum code written to the bus among those codes written by the contending stations, a contending station determining that it has contended unsuccessfully when its written code is less than the deciphered code, and a contending station determining that it can continue to contend for the bus when its written code is not less than the deciphered code.
20. The process of claim 19 wherein the contention resolution process further includes the steps of each contending station whose contention code is not less than its deciphered code writes a unique station identification code to the bus, reads the bus again, determines that it has successfully contended when its station identification code is equal to what it read from the bus the second time, and restarts the contention resolution process when its station identification code is not equal to what it read from the bus the second time, in order to resolve hidden collisions.
21. The process of claim 19 wherein the bus comprises a bit parallel bus and the step of each contending station generating a contention code comprises each contending station generating a binary random number.
22. The process of claim 21 wherein the binary random number comprises a unary random number.
23. The process of claim 18 wherein each deciphered code comprises the minimum code written to the bus among those codes written by the contending stations, a contending station determining that it has contended unsuccessfully when its written code is greater than the deciphered code, and a contending station determining that it can continue to contend for the bus when its written code is not greater than the deciphered code.
24. The process of claim 23 wherein the contention resolution process further includes the steps of each contending station whose contention code is not less than its deciphered code writes a unique station identification code to the bus, reads the bus again, determines that it has successfully contended when its station identification code is equal to what it read from the bus the second time, and restarts the contention resolution process when its station identification code is not equal to what it read from the bus the second time, in order to resolve hidden collisions.
25. The process of claim 23 wherein the bus comprises a bit parallel bus and the step of each contending station generating a contention code comprises each contending station generating a binary random number.
26. The process of claim 25 wherein the binary random number comprises a unary random number.
27. The process of claim 16 wherein the step in which each station contending for the bus generates a contention code comprises the step in which each station generates a unique code.
28. The process of claim 27 wherein the station transmitting the maximum unique code is permitted to transmit data onto the bus during the time interval.
29. The process of claim 27 wherein the station transmitting the minimum unique code is permitted to transmit data onto the bus during the time interval.
30. The process of claim 16 and further including the steps in which each contending station generates as its contention code a unique station identification code, determines that a hidden collision has occurred when what it read from the bus does not match its written code, and repeats the contention resolution process when it detects a hidden collision.
31. The process of claim 16 wherein the step in which each contending station generates a code comprises the steps of generating a code indicative of a priority of the station.
32. The process of claim 16 wherein each contending station repeats the contention resolution process a predetermined number of times to increase the probability that one contending station has been isolated, selected and permitted to transmit data onto the bus during the given time interval.
33. The process of claim 32 wherein the contention resolution process further includes the steps of each station which determines that it can continue to contend for the bus after the determined number of times writes a unique station identification code to the bus, reads the bus after writing its station identification code, determines that it has successfully contended when its station identification code is equal to what it reads from the bus after it wrote its station identification code, and restarts the contention resolution process when its station identification code is not equal to what it has read from the bus after it wrote its station identification code, in order to resolve hidden collisions.
34. The process of claim 16 wherein the step in which each contending station generates a contention code comprises the step of choosing a binary random number X.sub.i, i=1, . . . , N, N being the number of contending stations, from a code space of S, the X.sub.i 's having the properties of and .sym.X.sub.N).ltoreq.max(X.sub.1,X.sub.2, . . . ,X.sub.N)X.sub.i .epsilon.S,N.gtoreq.1.
35. The process of claim 34 and further including the step of estimating N in a current contention period t by ##EQU58## where B(t-1) is the number of bits that are ones in the previous contention period (t-1); K(t-1) is the size of the code space for the previous contention period (t-1); and W is the width of the bus.
36. The process of claim 34 wherein the step of choosing a binary random number comprises the step of choosing a unary random number.
37. The process of claim 16 wherein the step of generating a contention code comprises the step of selecting a binary number from a code space S.
38. The process of claim 37 wherein the bus has a width W and the code space has a size K equal to W.
39. The process of claim 37 wherein the bus has a width W, the code space S has a size K, N is the number of contending stations, r is a constant selected to reduce the number of contention slots to isolate one contending station wherein K/N=r.
40. The process of claim 39 and further including the step of estimating N in a current contention period t by ##EQU59## where B(t-1) is the number of bits that are ones in the previous contention period (t-1); K(t-1) is the size of the code space for the previous contention period (t-1); and W is the width of the bus.
41. The process of claim 39 wherein K is chosen to be W when r.multidot.N.ltoreq.W.
42. The process of claim 37 wherein the code space S comprises a plurality of partitioned subspaces, each subspace corresponding to a priority level.
43. The process of claim 42 wherein each partition satisfies the condition: where S.sub.i and S.sub.j are subspaces corresponding to priority levels i and j, respectively, and X and Y are contention codes.
44. The process of claim 37 wherein the step of selecting a binary number comprises the step of selecting a unary number.
45. The process of claim 44 wherein the bus has a width W and the code space has a size K equal to W.
46. The process of claim 44 wherein the bus has a width W, the code space S has a size K, N is the number of contending stations, r is a constant selected to reduce the number of contention slots to isolate one contending station wherein K/N=r.
47. The process of claim 46 and further including the step of estimating N in a current contention period t by ##EQU60## where B(t-1) is the number of bits that are ones in the previous contention period (t-1); K(t-1) is the size of the code space for the previous contention period (t-1); and W is the width of the bus.
48. The process of claim 46 wherein K is chosen to be W when r.multidot.N.ltoreq.W.
49. The process of claim 44 wherein the code space S comprises a plurality of partitioned subspaces, each subspace corresponding to a priority level.
50. The process of claim 49 wherein each partition satisfies the condition: where S.sub.i and S.sub.j are subspaces corresponding to priority levels i and j, respectively, and X and Y are contention codes.
51. In a computer network having a plurality of computers coupled together by a common bus for the sharing of computational resources among the computers, the network characterized by the capacity to send a job from a more loaded source computer to a less loaded destination computer, a method for determining a source computer and a destination computer, comprising the steps wherein (a) each computer maintains a global window; (b) each computer generates a contention parameter related to its response time for executing a job; (c) each computer contends for the bus when its contention parameter falls within its window; (d) each computer senses a status of the bus; (e) each computer adjusts its window and repeats steps c and d until a computer having the highest contention parameter and a computer having the lowest contention parameter have been identified; and (f) the computer identified as having one of the highest and lowest contention parameters sending a job to the computer identified as having the other of the highest and lowest contention parameters.
52. The method of claim 51 wherein the computer identified as having the highest contention parameter sends a job to the computer identified as having the lowest contention parameter.
53. The method of claim 51 wherein the computer identified as having the lowest contention parameter sends a job to the computer identified as having the highest contention parameter.
54. In a computer network having a plurality of computers coupled together by a common bus for the sharing of computational resources among the computers, the network characterized by the capacity to send a job queued at a requesting computer to an idle computer, a method for determining from which of a plurality of requesting computers a job is to be sent and for determining to which of a plurality of idle computers the job is to be sent, comprising the steps wherein, (a) each contending requesting computer maintains a global window; (b) each contending requesting computer generates a contention parameter; (c) each contending requesting computer compares its contention parameter to its window; (d) a contending requesting computer contends for the bus when its contention parameter falls within its window; (e) each contending requesting computer senses a status of the bus; (f) each contending requesting computer determines if it has gained control of the bus, based upon the bus status it sensed indicating that it has been isolated as the only computer contending for the bus, such isolated computer transmitting a request on the bus; (g) each contending requesting computer adjusts its window in response to the bus status it sensed and repeats steps c-f if the sensed bus status indicated that one contending idle computer has not been isolated; (h) each contending idle computer maintains a global window; (i) each contending idle computer generates a contention parameter; (j) each contending idle computer compares its contention parameter to its window; (k) a contending idle computer contends for the bus when its contention parameter falls within its window; (l) each contending idle computer senses a status of the bus; (m) each contending idle computer determines if it has gained control of the bus, based upon the bus status it sensed indicating that it has been isolated as the only computer contending for the bus, such isolated computer acknowledging the request and receiving the job from the isolated requesting computer; and (n) each contending idle computer adjusts its window in response to the bus status it sensed and repeats steps j-m if the sensed bus status indicated that one contending idle computer has not been isolated.
Patent Citations (4)
Non-Patent Literature (7)
- J. Capetanakis, "Tree Algorithm for Packet Broadcast Channels," IEEE Trans. Commun., vol. COM-26, pp. 1476-1484, Oct. 1979.
- M. G. Hluchyj, Multiple Access Communication: The Finite User Population Problem, Tech. Rep. LIDS-TH-1162, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Nov. 1981.
- J. H. Hayes, "An Adaptive Technique for Local Distribution," IEEE Transactions on Communications, vol. COM-26, Aug. 1978.
- L. Kleinrock and Y. Yemini, "An Optimal Adaptive Scheme for Multiple Access Broadcast Communication," Proc. ICC Conf., pp. 7.2.1-7.2.5, Jun. 1978.
- J. F. Kurose and M. Schwartz, "A Family of Window Protocols for Time Constrained Applications in CSMA Networks," Proc. 2nd Joint Conference of Computer and Communication Societies (INFOCOM), pp. 405-413, 1983.
- J. Mosely and P. Humblet, A Class of Efficient Contention Resolution Algorithms for Multiple Access Channels, Tech. Rep. LIDS-P-1194, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Dec. 1982.
- D. Towsley and G. Venkatesh, "Window Random Access Protocols for Local Computer Networks," IEEE Trans. on Computers, vol. C-31, No. 8, pp. 715-722, Aug. 1982.