Method for improving scheduling fairness of signal transmission/reception in a network

[0002] 1. Field of the Invention

[0003] The present invention relates to a local area network (LAN) employing the Ethernet and more particularly to a method for improving scheduling fairness of signal transmission/reception in a network when collisions occur in an Ethernet based LAN.

[0004] 2. Background of the Related Art

[0005] Generally, all nodes can access a network with fair scheduling priority in a CSMA/CD (Carrier Sense Multiple Access with Collision Detection) system. All the nodes must confirm that the network is not used for a time interval of an inter packet gap (IPG) before transmitting a packet. The IPG is typically about 9.6 μs for a 10M network and 0.96 μs at a 100M network. However, a collision occurs when two nodes transmit a packet simultaneously.

[0006] FIG. 1 illustrates channel access processing in a conventional Ethernet based LAN. As shown in FIG. 1, all m nodes, from the first node S₁, to the mth node S_m, transmit a first packet. After the transmission is completed, the nodes S₁to S_mwait for up to the IPG duration before transmitting a second packet. After the transmission of the second packet is completed, the first node S₁to the next to last node S_mwait for the IPG and then transmit a third packet. However, the mth node S_mdelays for the IPG after finishing the transmission of the second packet and then transmits a fourth packet. If the first node S₁and the mth node S_msimultaneously transmit their packets, then a conflict or collision occurs after ½ slot time. In FIG. 1, a collision occurs between the fourth packets transmitted from nodes S₁and S_m.

[0007] If the collision occurs, each node that transmitted the colliding packets waits as long as the IPG plus a backoff time before retransmitting the same packet. The backoff time is set differently for each node to prevent another collision. Each node that transmits a colliding packet repeats the transmission immediately after a lapse of the predetermined backoff time until the packet is successfully transmitted or until the number of retransmission trials or attempts due to collisions exceeds a predetermined maximum number and the trial terminates.

[0008] One related process for setting the backoff time is called a truncated binary exponential backoff algorithm. FIG. 2 illustrates a channel capture effect occurring when using such a related backoff algorithm. The backoff time is set to an integral multiple number r of a slot time. The slot time is a maximum turnaround time delay in the network. In other words, the time slot is a maximum time necessary for a certain node to transmit a packet and receive an answer. For example, the slot time in a 10M network is 51.2 μs.

[0009] The integral multiple number r that will be multiplied by the slot time is determined based on the number of times the packet is retransmitted by the node in accordance with the following formula:

[0010] 0≦r<2^k, where variable k=min (n, 10), n is the number of times of signal retransmission and 10 is the predetermined maximum number of retransmission attempts before the trial terminates.

[0011] Table 1 illustrates the values of the integral multiple number r and available backoff times based on the number of times of signal retransmission n.

[0012] For example, the number of retransmissions n varies form 1 through 10. When the number of retransmissions n is 1, namely, at the first retransmission, variable k=min(1, 10)=1 and 0<r<2¹. Therefore, the integral multiple number r may be 0 or 1. Based on the selected value of the integral multiple number r the backoff time may be 0 times the slot time or 1 times the slot time.

[0013] At the 10th retransmission, variable k=min(10,10)=10 and 0<r <2¹⁰, so the integral multiple number r may be one of 0 to 1023. Therefore, the backoff time may be one of 0 times the slot time to 1023 times the slot time based on the selected integral multiple number r value optionally selected. At this time, the slot time in the 10M network is 52.4 ms.

[0014] If such method as described above is applied to a network having many nodes, some amount of scheduling fairness could be realized. The following description referring to FIG. 2 concerns the case that signals are transmitted in the related method in a network having a few active nodes. FIG. 2 illustrates a channel capture effect occurring when using a related backoff algorithm.

[0015] If the node A and the node B perform transmission of a packet at the same time, a collision of the packets occur. If the collision occurs, each of the nodes A and B determines a backoff time. If respective integral multiple number r values of nodes A and B are set to 0 and 1 respectively, the backoff time of node A becomes 0× slot time, and the backoff time of node B becomes 1× slot time. Accordingly, node A transmits a signal after waiting for only an IPG while node B waits for IPG +1× slot time until the node A completes the packet transmission. Then node B waits for another IPG before transmitting its signal. According to such a scheme, node A can successfully transmit its packet without interference from node B.

[0016] Afterwards, if node A tries to successively transmit another packet, the packet collides with the first packet transmitted from node B. For node A which successfully transmitted its previous packet, this collision is the first collision for the successive packet, but the collision is the second collision for the first packet transmitted from node B. In other words, the number of times of signal retransmission, n, by the node A is less than the number of times of signal retransmission, n, by the node B. Therefore, there is low probability that the backoff time of node A is longer than the backoff time of node B. That is, the probability that node A can use the network is higher than the probability that node B can use the network. A problem exists that node A continuously transmits its packets while node B must only wait. This channel capture effect is more common when the conventional packet transmission method is applied to the LAN having a few active nodes.

[0017] Accordingly, when the related method is applied to a network having a few active nodes, there occurs the channel capture effect that one node must continuously wait while another node can continuously transmit packets, thus decreasing scheduling fairness of the network.

[0018] An object of the present invention is to substantially obviate one or more of the limitations and disadvantages of the related art.

[0019] Another object of the present invention is to improve scheduling fairness in using a network when collisions in an Ethernet based LAN occur during signal transmission.

[0020] A further object of the present invention is to increase overall network use efficiency.

[0021] To achieve these and other advantages, and in accordance with the purpose of the present invention as embodied and broadly described, a method for improving scheduling fairness for a network in accordance with a preferred embodiment of the invention includes detecting a packet collision occurring while different nodes transmit a packet; reading a previous network state for application of the backoff algorithm; selecting a new IPG based upon the read information; and determining a backoff time before retransmitting a packet.

[0022] The present invention can be achieved in a whole or in parts by a method for improving scheduling fairness in using a network by detecting whether or not collision occurs during packet transmission in the network having a plurality of nodes, and storing and monitoring signal transmit/receive state of X bit(s) before the collision with respect to each of the plurality of nodes. If the collision is detected, reading the previous transmit/receive state of X bit(s) with respect to a node having the collision, and judging the previous node state that has been read and setting an inter packet gap (IPG) for the node. After lapse of the IPG that has been set, effecting standard backoff. After lapse of a corresponding backoff time, retransmitting a signal of the node that has been collided. Detecting transmission collision with respect to the retransmitted signal of the node. If the collision is not detected with respect to the retransmitted signal of the node, updating the signal transmit/receive state of the node. If the collision is detected with respect to the retransmitted signal of the node, then repeating the steps of reading and judging previous node state, setting the IPG, effecting the standard backoff, retransmitting the signal, and detecting the collision.

[0023] The present invention can also be achieved in a whole or in parts by a method for scheduling transmissions from a plurality of nodes, including receiving a status of the node indicative of the successful transmission of a previous packet from the node; setting a length of time based on the status of the node; and transmitting a current packet to a system after waiting for the length of time.

[0024] The present invention can also be achieved in whole or in parts by a method for scheduling transmissions from a plurality of nodes, including detecting whether a collision occurs between transmitted signal during packet transmission in a network having a plurality of nodes. If the collision is not detected, transmitting a signal and updating the node state. If the collision is detected, reading a signal transmit/receive state of a node having the collision, and judging whether there is a difference between the signal transmit/receive state and a current state of the corresponding node. If there is no difference between the signal transmit/receive state and the current state, then retransmitting the signal after a backoff time, and detecting whether another collision occurs. If there is a difference between the signal transmit/receive state and the current states then setting an inter packet gap for the node based on the signal transmit/receive state. After a lapse of the inter packet gap and the backoff time, retransmitting the signal from the node having the collision and detecting whether a collision of the signal retransmitted from the node occurs. If the collision is not detected with respect to the retransmitted signal, updating the signal transmit/receive state of the node having the collision. If the collision is detected with respect to said retransmitted signal, and if there is no difference between the signal transmit/receive state and the current node state, then repeating step (d).

[0025] Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.

[0026] The invention will be described in detail with reference to the following drawings in which like reference numerals refer to like elements wherein:

[0027] FIG. 1 illustrates a channel access process in an Ethernet based LAN according to conventional technology;

[0028] FIG. 2 illustrates a channel capture effect that occurs when using a conventional standard backoff algorithm;

[0029] FIG. 3 is a flow chart showing a method for improving scheduling fairness for a network according to a first embodiment of the present invention;

[0030] FIG. 4 is a flow chart showing an application of the method for improving scheduling fairness for a network according to the first embodiment of the present invention;

[0031] FIG. 5 is a flow chart showing a method for improving scheduling fairness for a network according to a second embodiment of the present invention; and

[0032] FIG. 6 is a flow chart showing an application of the method for improving scheduling fairness for a network according to the second embodiment of the present invention.

[0033] The present invention relates to a method for improving overall scheduling fairness for a network by changing an IPG of each node according to a previous network use state of each node when a collision occurs among multiple nodes during packet transmission. The system for improving scheduling fairness in using a network according to the first embodiment of the present invention uses the previous two-bit transmit/receive states of each node.

[0034] As shown in FIG. 3, a receiver state indicates that an attempted transmission was unsuccessful. At step S100, the system detects a collision occurring while each node transmits a packet. If no collision occurs, then at step S101, the system transmits a signal and, at step S102, updates the node state.

[0035] If a collision occurs, then at step S103, the previous two-bit network state of a node having the collision is read. At step S104, the node state that has been read is then judged to select a new IPG. The newly selected IPG corresponding to each node state is set.

[0036] If the previous node state is reception Rx after reception Rx, (namely, (Rx, Rx)), then the node has not successfully transmitted its packet during the two previous trials. At step S105 of FIG. 3, the new IPG is set to “normal IPG+0× slot time”, where the normal IPG is predetermined, and the corresponding node has a high transmission priority and waits for the new IPG before retransmitting the packet. If the previous node state is reception Rx after transmission Tx (namely, (Tx, Rx)), then the node successfully transmitted a previous packet, but failed to transmit during the node's last trial. The new IPG is set to “normal IPG+1× slot time” and the corresponding node has a medium-high transmission priority and waits as long as the new IPG before retransmitting the packet.

[0037] If the previous node state is transmission Tx after reception Rx (namely, (Rx, Tx)), then the node successfully transmitted the previous packet after failing to transmit in its earlier previous trial. The new IPG is set to “normal IPG+2× slot time” and the corresponding node has a medium-low transmission priority, and waits as long as the new IPG before transmitting a new packet. If the previous node state is transmission Tx after transmission Tx (namely, (Tx, Tx)), then the node successfully transmitted its two preceding packets during the two previous trials. The new IPG is set to “normal IPG+3× slot time” and the corresponding node has a low priority and waits as long as the new IPG before transmitting a new packet.

[0038] As illustrated in FIG. 3, if a collision occurs when a node transmits a signal, a new IPG is set according to the previous node states having two bits. If the node is judged to carry out only reception twice based upon the previous node states, the new IPG is set to be shorter to increase probability of the signal or packet being transmitted successfully. On the other hand, if the node is judged to carry out only transmission twice based upon the previous node states, the new IPG is set to be longer to decrease the probability of the signal or packet being transmitted successfully.

[0039] Once the new IPG is set to one of the above four time values according to the four cases of the node states, the corresponding node waits for up to the newly set IPG. Then, at step S109, the standard backoff is effected, so the node further waits for up to the corresponding backoff time before retransmitting the signal at step S110. Afterwards, steps S100 to S110 are repeated. In other words, the system repeats the steps of detecting whether a collision occurs during the transmission at step S100. If no collision is detected, the system transmits the signal at step S101 and updates the node state at step S102. If a collision is detected, the system reads the node state at step S103, judges the node state at step S104, newly sets the IPG at steps S105 to S108, effects the standard backoff (S109), and retransmits the signal at step S110.

[0040] The backoff time is decided in accordance with the following formula:

[0041] 0≦r<2^k, where variable k=min(n, 10), and the number of retransmissions n is the number of times of signal retransmission. Backoff times according to values of the number of retransmissions n are illustrated in Table 1. Any one of the integral numbers in a given range can be optionally selected as the integral multiple number r.

[0042] In summary, when a packet at each node is transmitted through such a method as described by example above, the overall waiting time is as follows. Primarily, if the previous node state is (Rx, Rx), the waiting time is “normal IPG+0× slot time+r× slot time”. If the previous node state is (Tx, Rx), the waiting time is “normal IPG+1× slot time+r× slot time”. If the previous node state is (Rx, Tx), the waiting time is “normal IPG+2× slot time+r× slot time”. If the previous node state is (Tx, Tx), the waiting time is “normal IPG+3× slot time+r× slot time”.

[0043] The following description refers to FIG. 4 and concerns an example method for improving scheduling fairness in using a network where the first embodiment of the present invention is applied. In this application illustrated in FIG. 4, previous transmit/receive states of a node are read up to three bits representing the three previous trials or states. A new IPG is set according to the three previous node states.

[0044] As shown in FIG. 4, the steps of: detecting transmission collision, step S200; transmitting a signal if no collision is detected, step S201; monitoring and updating the previous node state, step S202; reading and judging the node state if any collision is detected, steps S203 and S204 to newly set an IPG, are the same as in the first embodiment of the present invention as show in FIG. 3, and are therefore not discussed again to avoid repetition. The method illustrated in FIG. 4 is different from the first embodiment because it uses the three previous node states represented by three bits, thus increasing the number of available selections for the new IPG up to 2³.

[0045] Specifically, if the previous node states are (Rx, Rx, Rx), the new IPG is set to “normal IPG+0× slot time” at step S205. If thee previous node states are (Tx, Rx, Rx), the new IPG is set to “normal IPG+1× slot time” at step S206. If the previous node states are (Rx, Tx, Rx), the new IPG is set to “normal IPG+2× slot time” at step S207. If the previous node states are (Tx, Tx, Rx), the new IPG is set to “normal IPG+3× slot time” at step S208. If the previous node states are (Rx, Rx, Tx), the new IPG is set to “normal IPG+4× slot time” at step S209. If the previous node states are (Tx, Rx, Tx), the new IPG is set to “normal IPG+5× slot time” at step S210. If the previous node states are (Rx, Tx, Tx), the new IPG is set to “normal IPG+6× slot time” at step S211. If the previous node states are (Tx, Tx, Tx), the new IPG is set to “normal IPG+7× slot time” at step S212. Each node waits as long as its corresponding new IPG as set in steps S205 to S212, plus a standard backoff time as effected in step S213 and then retransmits the signal or packet at step S214.

[0046] The steps S200 to S214 are continuously repeated until the signal or packet is successfully transmitted. In other words, the scheduling approach enables the network for repeatedly detecting whether or not there occurs the collision during the transmission at step S200; transmitting the signal at step S201 and updating the node state at step S202 if no collision is detected; reading and judging the previous node states at steps S203 and S204 if the collision is detected; newly setting the IPG and waiting up to the duration of the new IPG at steps S205 to 212, effecting the standard backoff, and waiting up to the duration of the backoff time at step S213, and retransmitting the signal at step S214.

[0047] The second embodiment of the present invention will now be described with reference to FIGS. 5 and 6. A method for improving scheduling fairness in using a network according to the second embodiment of the present invention uses previous transmit/receive node states of two or more bits as previously discussed. At step S300, the network or system, as instructed by the method, detects if a collision occurred while each node transmits a packet. If there is no collision between packets, then at step S301, a signal is transmitted, and at step S302, the node state is updated.

[0048] If a collision is detected, then the system reads the previous network states of the nodes having the collision, as in step S103, and determines whether the current node state is the same as the previous node state at step S303. At step S304, the system judges the previous node state to set a new IPG. After reading and judging the previous node state, the new IPG is set according to the node state.

[0049] If the previous node state is reception Rx after reception Rx (namely, (Rx, Rx)), then at step S305, the new IPG is set to “normal IPG+0× slot time”, where the normal IPG is predetermined, and a corresponding node waits up to the duration of the new IPG before retransmitting. If the previous node state is reception Rx after transmission Tx (namely, (Tx, Rx)), then at step S306, the new IPG is set to “normal IPG+1× slot time” and a corresponding node waits up to the duration of the new IPG before retransmitting. If the previous node state is transmission Tx after reception Rx (namely, (Rx, Tx)), then at step S307 the new IPG is set to “normal IPG+2× slot time” and a corresponding node waits up to the duration of the new IPG before retransmitting. If the previous node state is transmission Tx after transmission Tx (namely, (Tx, Tx)), then at step S308, the new IPG is set to “normal IPG+3× slot time” and a corresponding node waits up to the duration of the new IPG before retransmitting.

[0050] As illustrated in FIG. 5, a new IPG is set according to the previous transmit/receive node states (of two bits) before the current state having the collision. If the node is judged to carry out only reception twice from the previous node states, the new IPG is set to be shorter to increase probability of a signal or packet being transmitted successfully. On the other hand, if the node is judged to carry out only transmission twice based on the previous two node states, the new IPG is set to be longer to decrease the probability of a signal or packet being transmitted successfully.

[0051] Once the new IPG is set to one of the above four time values according to the four cases of the node states, the corresponding node waits for up to the newly set IPG. Then at step S309, the standard backoff is effected, so the node further waits for up to a corresponding backoff time before retransmitting the signal at step S310. Afterwards steps S300 to S312 are repeated. In other words, the system repeats the steps of detecting whether the collision occurs during the transmission at step S300; transmitting a signal at step S301 and updating the node state at step S302 if no collision is detected; and reading the previous node states and judging whether the current node state is different from the read previous node state at step S303 if the collision is detected. If the previous and current node states are different, then steps S304 to S310 are repeated as described above. If there is no difference between the current node state and the previous node state, a standard backoff method is selected at step S311 and a backoff time is newly determined. After a lapse of the backoff time, the signal is retransmitted at step S312. Subsequently, the step S300 of detecting the collision is again repeated.

[0052] The standard backoff time is decided in accordance with the following formula:

[0053] 0<r<2^k, for variable k=min(n, 10), wherein the number of retransmissions n is the number of times of signal retransmission. Waiting times according to values of the number of retransmissions n are illustrated above in Table 1. One of the integral figures in a given range can be optionally selected as the integral multiple number r.

[0054] The following description refers to FIG. 6 and concerns an example method for improving scheduling fairness in using a network where the second embodiment of the present invention is applied.

[0055] The steps of detecting transmission collision at step S400, transmitting the signal at step S401, updating the previous node state at step S402, reading the previous state and determining whether it is different than the current node state at step S403, selecting the standard backoff at step S415, retransmitting the signal or packet at step S416, and judging the previous node state at step S404 in the applied method shown in FIG. 6 are the same as the corresponding steps in the second embodiment of the present invention shown in FIG. 5 and are therefore not discussed again to avoid repetition. The method illustrated in FIG. 6 is different from the second embodiment because it uses the previous node states represented by three bits before collision occurs, thus increasing the number of available selections for the new IPG up to 2³.

[0056] Specifically, if the previous node states are (Rx, Rx, Rx), the new IPG is set to “normal IPG+0× slot time” at step S405. If the previous node states are (Tx, Rx, Rx), the new IPG is set to “normal IPG+1× slot time” at step S406. If the previous node states are (Rx, Tx, Rx), the new IPG is set to “normal IPG+2× slot time” at step S407. If the previous node states are (Tx, Tx, Rx), the new IPG is set to “normal IPG+3× slot time” at step S408. If the previous node states are (Rx, Rx, Tx), the new IPG is set to “normal IPG+4× slot time” at step S409. If the previous node states are (Tx, Rx, Tx), the new IPG is set to “normal IPG+5× slot time” at step S410. If the previous node states are (Rx, Tx, Tx), the new IPG is set to “normal IPG+6× slot time” at step S411. If the previous node states are (Tx, Tx, Tx), the new IPG is set to “normal IPG+7× slot time” at step S412. Each node waits as long as its corresponding new IPG as set in steps S405 to S412 plus the standard backoff time as selected by the standard backoff method at step S413. Accordingly, the node waits for the additional backoff time before retransmitting the signal at step S414.

[0057] The steps S400 to S416 are continuously repeated until the signal or packet is successfully transmitted. In other words, whether or not there occurs the collision during the transmission is detected at step S400. If no collision is detected, a signal is transmitted at step S401 and the node state is updated at step S402. If the collision is detected, the previous node state is read and compared to the current node state at step S403. If there is no change in the node state, the standard backoff method is selected at step S415 and a backoff time is newly set. After a lapse of the backoff time, the signal is retransmitted at step S416.

[0058] Accordingly, the present invention can reduce the channel capture effect by newly setting the IPG in a small scale network having a few active nodes, thus improving the scheduling fairness in using the network and increasing use efficiency on the network.

[0059] The foregoing embodiments are merely exemplary and are not to be construed as limiting the present invention. The present teaching can be readily applied to other types of apparatuses. The description of the present invention is intended to be illustrative, and not to limit the scope of the claims. Many alternatives, modifications, and variations will be apparent to those skilled in the art. In the claims, means-plus-function clauses are intended to cover the structures described herein as performing the recited function and not only structural equivalents but also equivalent structures.