1 Definition 1. IncomingFrame: a packet frame which arrives at a congestion node or at its destination. 2. IncomingFrame.flowid: an incoming frame can be tagged with the field of its flow id. 3. IncomingFrame.DE: an incoming frame is assumed to be tagged with a Discard Eligible (DE) bit which is initialized to 0; intermediate congestion points in the path of this frame can modify the field. 4. RL[*]: a set of rate limiters. 5. RL[i].state: state of the rate limiter i: active or inactive. 6. RL[i].flowid: the flow id that is associated with the rate limiter i. 7. RL[i].crate: the current rate of the rate limiter i. 8. RL[i].trate: the target rate of the rate limiter i. 9. RL[i].tx_bcount: number of bytes sent since the last negative feedback frame (Fb < 0). 10. RL[i].si_count: the stage of the byte counter that the rate limiter,i, is in. 11. RL[i].timer: the timer of the rate limiter 12. RL[i].timer_scount: the stage of the timer that the rate limiter,i, is in. 13. RL[i].qlen: the queue length of the rate limiter queue 14. rlidx: index of a rate limiter. 15. FBFrame: a feedback control frame which sends the congestion information, Fb, back to the traffic source; this packet frame can be sent either from any intermediate reflection point. 16. FBFrame.SA: the source MAC address of the feedback control frame. 17. FBFrame.DA: the destination MAC address of the feedback control frame. 18. FBFrame.flowid: the flow id of the feedback control frame. 19. FBFrame.fb: the congestion control information, Fb, of the feedback control frame. 20. min_dec_factor: the minimum decrease factor, a single step of decrease should not exceed this value. 21. qlen: current queue length (in pages). incremented upon packet arrivals and decremented upon packet departures. 22. qlen_old: queue length (in pages) at last sample. 23. Fb: feedback value which indicates the level of congestion. 24. qntz_Fb: quantized negative Fb (-Fb) value. QCN Reaction Point: 1. initialize() 2. { 3. //* indicates all rate limiters 4. RL[*].state = INACTIVE; 5. RL[*].flowid = -1; 6. RL[*].crate = C; 7. RL[*].trate = C; 8. RL[*].tx_bcount = 0; 9. RL[*].si_count = 0; 10. RL[*].timer_count = 0; 11. } 12. 13. foreach (FBFrame) 14. { 15. //obtain the rate limiter index that is associated with a flowid 16. //if no match, return the index of the next available rate limiter 17. rlidx = get_rate_limiter_index(FBFrame.flowid); 18. if (RL[rlidx].state = = INACTIVE) then 19. if (FBFrame.fb != 0) then 20. //initialize new rate limiter 21. RL[rlidx].state = ACTIVE; 22. RL[rlidx].flowid = FBFrame.flowid; 23. RL[rlidx].crate = C; 24. RL[rlidx].trate = C; 25. RL[rlidx].si_count = 0; 26. else 27. //ignore FBFrame 28. return; 29. endif 30. endif 31. 32. if (FBFrame.fb != 0) then 33. 34. // use the current rate as the next target rate. 35. // however under EXTRA_FAST_RECOVERY mode: 36. // in the first cycle of fast recovery, 37. // the Fb < 0 signal would not reset the target rate. 38. if (EXTRA_FAST_RECOVERY != TRUE 39. || RL[rlidx].si_count ! = 0) then 40. RL[rlidx].trate = RL[rlidx].crate; 41. RL[rlidx].tx_bcount = 0; 42. endif 43. 44. // set the stage counter 45. RL[rlidx].si_count = 0; 46. RL[rlidx].timer_scount = 0; 47. 48. 49. // update the current rate, multiplicative decrease 50. dec_factor = (1 - GD * FBFrame.fb); 51. if (dec_factor < min_dec_factor) then 52. dec_factor = min_dec_factor; 53. endif 54. RL[rlidx].crate = RL[rlidx].crate * (1 - dec_factor); 55. if (RL[rlidx].crate < MIN_RATE) then 56. RL[rlidx].crate = MIN_RATE; 57. endif 58. 59. //reset the timer 60. set_timer(rlidx, TIMER_PERIOD); 61. endif 62. } 63. self_increase(rlidx) 64. { 65. to_count = minimum(RL[rlidx].si_count, RL[rlidx].timer_scount); 66. 67. // if in the active probing stages, increase the target rate 68. if (RL[rlidx].si_count > FAST_RECOVERY_TH || 69. RL[rlidx].timer_scount > FAST_RECOVERY_TH) then 70. if (RL[rlidx].si_count > FAST_RECOVERY_TH && 71. RL[rlidx].timer_scount > FAST_RECOVERY_TH) then 72. //hyperactive increase 73. Ri = B * (to_count - FAST_RECOVERY_TH); 74. else 75. //active increase 76. Ri = A; 77. endif 78. else 79. Ri = 0; 80. endif 81. 82. 83. 84. //at the end of the first cycle of recovery 85. if (EXTR_FAST_RECOVERY && RL[rlidx].si_count == 1 && 86. RL[rlidx].trate > 10* RL[rlidx].crate) then 87. RL[rlidx].trate = RL[rlidx].trate/8; 88. else 89. RL[rlidx].trate = RL[rlidx].trate + Ri; 90. 91. RL[rlidx].crate = (RL[rlidx].trate + RL[rlidx].crate)/2; 92. 93. //saturate rate at C 94. if (RL[rlidx].crate > C) then 95. RL[rlidx].crate = C; 96. endif 97. } 98. 99. foreach (Transmit Frame)) 100. { 101. //release the rate limiter when its rate has reached C 102. //and its associated queue is empty 103. if ( RL[rlidx].rate = = C && RL[rlidx].qlen = = 0) then 104. RL[rlidx].state = INACTIVE; 105. RL[rlidx].flowid = -1; 106. RL[rlidx].crate = C; 107. RL[rlidx].trate = C; 108. RL[rlidx].tx_bcount = 0; 109. RL[rlidx].si_count = 0; 110. RL[rlidx].timer = INACTIVE; 111. else 112. RL[rlidx].tx_bcount += length(Transmit Frame); 113. //if a negative FBframe has not been received after transmitting 114. //TO_THRESH bytes, trigger self_increase 115. if (RL[rlidx].si_bcount < FAST_RECOVERY_TH) then 116. expire_thresh = TO_THRESH; 117. else 118. expire_thresh = TO_THRESH/2; 119. endif 120. if (RL[rlidx].tx_bcount > expire_thresh) then 121. RL[rlidx].si_count++; 122. RL[rlidx].tx_bcount = 0; 123. self_increase(rlidx); 124. endif 125. endif 126. } 127. /* Timers */ 128. timer_expired(rlidx) 129. { 130. if (RL[rlidx].state = = ACTIVE ) then 131. RL[rlidx].timer_scount++;; 132. self_increase(rlidx); 133. 134. //reset the timer 135. 136. if (RL[rlidx].timer_scount < FAST_RECOVERY_TH) then 137. expire_period = TO_THRESH; 138. else 139. expire_period = TO_THRESH/2; 140. endif 141. set _timer(rlidx, expire_period); 142. 143. endif 144. } QCN Congestion Point: 145. initialize() 146. { 147. qlen = 0; 148. qlen_old = 0; 149. } 150. 151. foreach (IncomingFrame) 152. { 153. //calculate Fb value 154. Fb = (Q_EQ - qlen) - W * (qlen - qlen_old); 155. if (Fb < -Q_EQ * (2 * W + 1)) then 156. Fb = -Q_EQ * (2 * W + 1); 157. elseif (Fb > 0) then 158. Fb = 0; 159. endif 160. 161. //the maximum value of -Fb determines the number of bits that Fb uses. 162. //uniform quantization of -Fb, qntz_Fb, uses most significant bits of –Fb. 163. //note that now qntz_Fb has positive values. 164. qntz_Fb = -Fb(most significant bits); 165. 166. //sampling probability is a function of Fb 167. generate_fb_frame = 0; 168. if (urand() < (BASE_PROBABILITY + C * qntz_Fb)) then 169. //generate a feedback frame if Fb is negative 170. if (Fb < 0) then 171. generate_fb_frame = 1; 172. endif 173. qlen_old = qlen; 174. endif 175. 176. //set DE bit if Fb is negative 177. if (Fb < 0) then 178. IncomingFrame.DE = 1; 179. endif 180. 181. if (generate_fb_frame) then 182. FBFrame.DA = IncomingFrame.SA; 183. FBFrame.SA = SWITCH_MAC_ADDRESS; 184. FBFrame.flowid = IncomingFrame.flowid; 185. FBFrame.fb = qntz_Fb; 186. forward(FBFrame); 187. endif 188. }