通信網(wǎng)理論基礎(chǔ)（工程碩士）：ch3 Delay Models in Data Networks

1、CH3 Delay Models in Data NetworksDelay considerations strongly influence the routing and flow control of networkQueuing theory Quantitative 美kwnttetvadj. 定量的；量的，數(shù)量的Qualitative 美kwltetvadj. 定性的；質(zhì)的，性質(zhì)上的Multiplexing of traffic (1/2) Multiplexing of traffic(2/2) in terms of依據(jù)；按照；在方面；以措詞in accordance, in

2、 the light of, by, in the field ofRandom arrival Poisson processCDF, 累積分布函數(shù)（Cumulative Distribution Function）；PDF, 概率分布函數(shù)（Probability Distribution Function）paradox 英prdks 美prdksn. 悖論，反論；似非而是的論點(diǎn)；自相矛盾的人或事What if the splitting is done by alternation, with even-numbered arrivals assigned to one process

3、and odd-numbered arrivals assigned to the other? The two generated processes are still Poisson?ergodic 英gdk美gdk！adj. 數(shù) 遍歷性的；數(shù) 各態(tài)歷經(jīng)的 n. 遍歷性Is the Littles Theorem OK without First-in-first-out case?Redraw the Figure 3.1 without First-in-first-out case?Application &Example to N(t) as a deterministic fu

4、nction of timeFig 3.3, the number in the system in Example 3.3, N(t), is deterministic and does not converge as t goes infinity. Littles Theorem holds with N, lamda, and T viewed as time average. Application &Example to N(t) as a deterministic function of time (cont. )Application &Example to ARQAppl

5、ication and Example to Closed Queueing SystemApplication and Example to Closed Queueing SystemApplication and Example to polling systemsApplication and Example to polling systemsApplication and Example to estimation throughput in a time-sharing systemApplication and Example to estimation throughput

6、in a time-sharing system (cont. )Figure 3.4 N terminals connected with a time-sharing computer system. To estimate maximum attainable throughput, we assume a departing user immediately reenters the system or, equivalently, is immediately replaced by a new use. Application and Example to estimation t

7、hroughput in a time-sharing system (cont. )Application and Example to estimation throughput in a time-sharing system (cont. )Application and Example to estimation throughput in a time-sharing system (cont. )Figure 3.5 Bounds on Throughput and average user delay in a time-sharing system. the time inc

8、reases essentially in proportion with the number of terminals N. (a) Bounds on attainable throughput Eq. (3.8)(b) bounds on average user time in a fully loaded system Eq.(3.9)Application and Example to estimation throughput in a time-sharing system (cont. )nomenclature 英n()meklt;美nmnkltn. 命名法；術(shù)語equi

9、librium 基本釋義n. 均衡；平靜網(wǎng)友“押沙龍”就表示，“如果你在王府井那種一天一平方米二三十元租金的咖啡店里，花三十元坐半個(gè)小時(shí)喝了一杯星巴克咖啡，而這杯咖啡本身就值二十五元，那人家開的就不是咖啡店，而是施粥棚。M/M/m解法二：（1）以（x，y）作為系統(tǒng)的狀態(tài)變量，其中x表示系統(tǒng)中A類呼叫的個(gè)數(shù)，則 ，y表示系統(tǒng)中B類呼叫的個(gè)數(shù)，則 。其中：狀態(tài)00表示系統(tǒng)處于空閑狀態(tài)，到達(dá)一個(gè)A類呼叫轉(zhuǎn)移到狀態(tài)10，到達(dá)一個(gè)B類呼叫轉(zhuǎn)移到狀態(tài)01;狀態(tài)01表示系統(tǒng)中有1個(gè)B類呼叫，且該呼叫正在被服務(wù)，則如該呼叫離去，則返回到00狀態(tài)；此時(shí)如到達(dá)一個(gè)A呼叫，轉(zhuǎn)移到11A狀態(tài)，如到達(dá)一個(gè)B類呼叫，轉(zhuǎn)移

10、到02狀態(tài);狀態(tài)02表示系統(tǒng)中有2個(gè)B呼叫，一個(gè)正在被服務(wù)，一個(gè)處于排隊(duì)等待狀態(tài)，如離開一個(gè)呼叫，則返回到01狀態(tài)，如到達(dá)一個(gè)B類呼叫，則該呼叫被拒絕，如到達(dá)一個(gè)A呼叫，則轉(zhuǎn)移到12狀態(tài)；狀態(tài)10表示系統(tǒng)中有一個(gè)A呼叫，且該呼叫正在被服務(wù)，若該呼叫服務(wù)完畢離開，則返回到00狀態(tài)；若此時(shí)到達(dá)一個(gè)A呼叫，則轉(zhuǎn)移到20狀態(tài)，如到達(dá)一個(gè)B呼叫，則轉(zhuǎn)移到11B狀態(tài)；狀態(tài)20表示系統(tǒng)中有兩個(gè)B呼叫，一個(gè)正在被服務(wù)，一個(gè)在排隊(duì)，若一個(gè)呼叫離開，返回到10狀態(tài)；如到達(dá)一個(gè)A呼叫，則被拒絕，如到達(dá)一個(gè)B呼叫，則轉(zhuǎn)移到21狀態(tài)11A狀態(tài)，表示系統(tǒng)中有一個(gè)A呼叫和一個(gè)B呼叫，且B正在被服務(wù)，A在排隊(duì)等待；此時(shí)如B服

11、務(wù)完畢離開，則返回到10狀態(tài)；如到達(dá)一個(gè)A呼叫，則A呼叫被拒絕，如到達(dá)一個(gè)B呼叫，則轉(zhuǎn)移到12狀態(tài)；11B狀態(tài)，表示系統(tǒng)中有一個(gè)A呼叫和一個(gè)B呼叫，且A正在被服務(wù)，B在排隊(duì)等待；此時(shí)如A服務(wù)完畢離開，則返回到01狀態(tài)；如到達(dá)一個(gè)A呼叫，則轉(zhuǎn)移到21狀態(tài)，如到達(dá)一個(gè)B呼叫，則B呼叫被拒絕；12狀態(tài)表示系統(tǒng)中有一個(gè)A呼叫在排隊(duì)，2個(gè)B呼叫一等待一服務(wù)：若B離開，則返回到11A狀態(tài)；此時(shí)不論到達(dá)A或者B呼叫均被拒絕。21狀態(tài)表示系統(tǒng)中有一個(gè)B呼叫在排隊(duì)，2個(gè)A呼叫一等待一服務(wù)：若A離開，則返回到11A狀態(tài)；此時(shí)不論到達(dá)A或者B呼叫均被拒絕。狀態(tài)轉(zhuǎn)移圖如下所示。（2）根據(jù)狀態(tài)轉(zhuǎn)移圖列穩(wěn)態(tài)方程M/G/1

12、 Queue服務(wù)時(shí)間的均值和二階矩為 P- K公式證明的思路是基于平均剩余服務(wù)時(shí)間(Mean Residual Service Time)的求解。設(shè)第i個(gè)用戶到達(dá)系統(tǒng)時(shí), 第l個(gè)用戶正在接受服務(wù), 其剩余服務(wù)時(shí)間為Ri,此時(shí)等待隊(duì)列中有Ni個(gè)用戶。P-K公式設(shè)第k個(gè)用戶的服務(wù)時(shí)間為Xk, 則由圖可知, 用戶i的等待時(shí)間為 對(duì)上式求平均得P-K公式假定系統(tǒng)有穩(wěn)態(tài)解，且具有各態(tài)歷經(jīng)性，則剩余服務(wù)時(shí)間可用圖表示 上圖中三角形面積式中, M(t)表示0, t區(qū)間內(nèi)已服務(wù)的用戶數(shù)。第二項(xiàng)為平均到達(dá)率, 第三項(xiàng)為Xi的二階矩。P-K公式推導(dǎo)的進(jìn)一步分析從P-K公式可以看出,M/G/1隊(duì)列的一個(gè)重要特征:W

13、X2。即使1, 如果X2,則W。這說明,如果有少量用戶有非常長的服務(wù)時(shí)間,一旦這些用戶被服務(wù), 將導(dǎo)致隊(duì)列非常長。兩個(gè)假設(shè)進(jìn)一步分析服務(wù)員有休假的 M/G/1 排隊(duì)模型 服務(wù)員有休假的M/G/1(M/G/1 Queues with Vacations)排隊(duì)系統(tǒng)是指：在每一個(gè)忙周期后(分組傳輸結(jié)束后), 服務(wù)員需要休假(休假對(duì)應(yīng)于服務(wù)員(通信節(jié)點(diǎn))要進(jìn)行其他處理,如存儲(chǔ)數(shù)據(jù)、 信令交換等)； 在服務(wù)員休假期內(nèi)到達(dá)的用戶,要等待服務(wù)員休假結(jié)束后,才能被服務(wù)；如服務(wù)員休假期滿后, 沒有用戶到達(dá), 服務(wù)員將進(jìn)入另一個(gè)休假期。一個(gè)新用戶到達(dá)系統(tǒng)時(shí), 它可能會(huì)遇到兩種情況:一種是當(dāng)前有一個(gè)分組正在接受服務(wù)

14、,服務(wù)員正在處于休假期。前一種情況的剩余服務(wù)時(shí)間與標(biāo)準(zhǔn)的M/G/1隊(duì)列相同, 后一種情況的剩余服務(wù)時(shí)間為服務(wù)員休假的剩余服務(wù)時(shí)間。令M(t)和L(t)分別為0, t區(qū)間內(nèi)到達(dá)的用戶數(shù)和服務(wù)員休假的次數(shù)。可得平均剩余服務(wù)時(shí)間的表示為上式。 由于分組傳輸和休假期的交替到達(dá)占滿整個(gè)時(shí)間軸, 則在單位時(shí)間,分組所占的比例為/=, 休假期占的比例為1-。因而有休假到達(dá)率為(1-)/V。ensemble average 數(shù) 統(tǒng)計(jì)平均值Networks of Queuestandem n. 串聯(lián)；串座雙人自行車adj. 串聯(lián)的adv. 一前一后地；縱排地The conclusion is. 下面討論如何消除節(jié)點(diǎn)輸出過程對(duì)下一節(jié)點(diǎn)的到達(dá)過程的影響，