【正文】 ?目標(biāo)函數(shù)最?。?? ??? ?? ??Ni Jj ijjijiJj jj xpchyFMi ni m ize 1 )( 1/0?jy ：節(jié)點(diǎn) j 安裝匯聚設(shè)備 so that:（ 1）jNi iji bxh ???1 for Jj? (容量約束：每個(gè)接入節(jié)點(diǎn)容量之和 匯聚節(jié)點(diǎn)容量 )；（ 2） 0???Jj ijx for i=1,2,...,N.(接入約束：只能連到一個(gè)匯聚節(jié)點(diǎn) )；（ 3） jij yx? for Jj? and i=1,2,...,N Jforjy j ?? },1,0{ Jforjxij ?? },1,0{ and i=1,2,...,N(不可接入約束 )。（ 1 ）不考慮與 年齡無(wú)關(guān)項(xiàng)：)/1ln ()(/ ppbdxdp ??? 存活時(shí)間 ；（ 2）概率密度函數(shù)： )exp( bxbx eeeb ?? ? ? ；（ 3）累計(jì)概率函數(shù)： ))1(exp(1 ??? bxe? ；（ 4）等價(jià)表示： ?? ? ?? xexh )( )]e x p ()/e x p [ ln ()( 0 tKpKtp ??? 。0,。 1 業(yè)務(wù)流量增長(zhǎng)預(yù)測(cè)方法 ： ① logistic 分布函數(shù)： 用戶(hù)數(shù) p(t), 隨 時(shí) 間 的 變 化 ， 正 比 于 已 有 用 戶(hù) 數(shù) ， 與 待 發(fā) 展 用 戶(hù) 數(shù) 之 積 ， 即 ：))(1)(()()( tptprdtpdtp ??????? ,或 )1(/ pprdtdp ??? （（ 1p） 待發(fā)展用戶(hù)數(shù)即潛在用戶(hù)）， pz /1? 代入上式，則有)1()1)/1(()/1)(1(/)/1(/ 22 ?????????????? zrprppprdtdppdtdz 所以， ))exp(1/(1 rtp ??? (r 反應(yīng)斜率，增長(zhǎng)速度 )。移除邊 f，正好解除了 T+e 中的圈，因此 T+ef 對(duì)應(yīng)于新可行解 39。x ，有 039。?x ），需要找到反向邊 f，該邊具有最小值 fx ,得到 fxt? 。（ 4）為保證 39。 ?cc 減少 39。cx 。問(wèn) 題變換為選擇 t，使用 39。39。（ 3）因只有 e 滿(mǎn)足 0?ijc 且 0?ijx ，所以： tccxxc e39。?x 則 39。 。 依 照 e 的 方 向 ， 將 圈 中 的 邊 分 為 前 向 和 反 向 邊 設(shè) 置（不在圈中）；反向邊；前向邊 ij)()( xtxtxx ijijij ??? 。（ 3）如果有此邊 e，將其加入到樹(shù) T。x ，都有 cxcx?39。39。（ 2）如果無(wú)此邊， then 039。 Step2（代數(shù)表示） ：（ 1）找到 邊 e=uv， 滿(mǎn)足： )0..( 39。39。（ 6）所以， if 39。39。（ 5）將 yb 用 cx 替代，有 （舊樹(shù)成本）新樹(shù)成本 cxxccx ?? 39。39。39。39。39。39。39。 ???? ijij o rxe ith e rcijxc .(3)對(duì)于可行解 )0,( 39。綜合以上關(guān)系，有： )00,(0 39。if 039。c 為邊成本與所分配流的差）；（ 2） if Tij? then 039。 Step1(添加邊的選擇 )：（ 1）定義： yAcc ??39。（ a）jiji ycy ?? Tij?? ；（ b）向量 y，記錄節(jié)點(diǎn)分配流的大小。 代數(shù)符號(hào)說(shuō)明 ： (1)從樹(shù) T 開(kāi)始，求可行解 x。初始樹(shù)求解，變換為附加問(wèn)題： ? ijijxpMin 。 ?如果不存在這類(lèi)節(jié)點(diǎn) w，人為增加邊或節(jié)點(diǎn)。 1 MST（最小生成樹(shù)）求解初始樹(shù)的增廣圖 ?如果存在一節(jié)點(diǎn) w：（ 1）所有源都有邊連接到 w；（ 2） w 有邊連接到所有的宿和中間節(jié)點(diǎn)。 1 約束路由計(jì)算 方法 約束路由 是一種命令驅(qū)動(dòng)并具有資源預(yù)留能力的 路由算法 ，能夠和現(xiàn)有的 Inter 中的拓?fù)潋?qū)動(dòng)的、逐跳的 內(nèi)部網(wǎng)關(guān)協(xié)議 共存。 BFS(寬度 /廣度優(yōu)先 ) 1 function Dijkstra(G, w, s) 2 for each vertex v in V[G] 3 d[v] := infinity 4 previous[v] := undefined 5 d[s] := 0 6 S := empty set 7 Q := set of all vertices 8 while Q is not an empty set 9 u := Extract_Min(Q) 10 S := S union {u} 11 for each edge (u,v) outgoing from u 12 if d[v] d[u] + w(u,v) 13 d[v] := d[u] + w(u,v) 14 previous[v] := u 行 24 的初始化對(duì) n 個(gè)頂點(diǎn)進(jìn)行，顯然是 O（ n） ； 56行 O（ 1） ； 7 行 n 個(gè)頂點(diǎn)入隊(duì)列 O（ n） ； 8 行 14 行，從 8 行可以看出進(jìn)行了 n 遍循環(huán)，每遍在第九行調(diào)用一次 ExtractMin 過(guò)程， ExtractMin 過(guò)程需要搜尋鄰接表，每一次需要搜尋整個(gè)數(shù)組，所以一次操作時(shí)間是 O(n)。 圖算法： warshall 算法：用于求可達(dá)性矩陣，時(shí)間復(fù)雜度為 O（ n^3/2）；深度優(yōu)先算法：查找某個(gè)特定的點(diǎn)或者邊，時(shí)間復(fù)雜度為 O（ b^m）？ (b 為分支系統(tǒng)， m 為圖的最大深度 )； Dijkstra 算法：初始圖為有向圖，解決有向圖中最短最輕路徑問(wèn)題，以點(diǎn)為依據(jù)，有根節(jié)點(diǎn)選擇，時(shí)間復(fù)雜度為 O（ n^2）， n 為點(diǎn)的個(gè)數(shù)。常用的還有平方階 O（ n2）、立方階 O（ n3）、對(duì)數(shù)階 O(log2n)等。 如果一個(gè)算法沒(méi)有循環(huán)語(yǔ)句，則算法中基本操作的執(zhí)行頻度與問(wèn)題規(guī)模 n 無(wú)關(guān)，記作 O(1)，也稱(chēng)為常數(shù)階。其中“ O”表示隨問(wèn)題 規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同，或者說(shuō)，用“ O”符號(hào)表示數(shù)量級(jí)的概念。為了便于比較同一問(wèn)題的不同算法，通常把算法中基本操作重復(fù)執(zhí)行的次數(shù)（頻度）作為算法的時(shí)間復(fù)雜度。 一個(gè)算法的時(shí)間復(fù)雜度 (Time Complexity)是指該算法的運(yùn)行時(shí)間與問(wèn)題規(guī)模的對(duì)應(yīng)關(guān)系。計(jì)算復(fù)雜度與循環(huán)的次數(shù)有關(guān)，循環(huán)次數(shù)通常跟邊 的數(shù)目和點(diǎn)的數(shù)目有關(guān)。 鄰接陣 :它是表達(dá)端與端之間的關(guān)系矩陣。圖的矩陣表示與幾何表示一一對(duì)應(yīng)。 1 圖的矩陣表示方法 ： 圖的幾何表示具有直觀性。 兩者的本質(zhì)區(qū)別在于是否在媒體流中傳輸 DTMF。 帶內(nèi)傳送： 即在 RTP(實(shí)時(shí)傳輸協(xié)議 )媒體傳輸中攜帶 DTMF 信號(hào)。利用 DTMF 信令可選擇呼叫相應(yīng)的 對(duì)講機(jī) 。一個(gè)高頻信號(hào)和一個(gè)低頻信號(hào)疊加組成一個(gè)組合信號(hào)，代表一個(gè)數(shù)字。比較目的地址和 E 的前 6 比特，不相同，此時(shí)產(chǎn)生回溯，最長(zhǎng)前綴匹配結(jié)果為 C。同樣，取目的地址和 C 的前三比特進(jìn)行匹配，完全相同，則記錄 C 和下一跳地址。由于 A 的長(zhǎng)度為 1，所以，比較目的地址和 A 的第一個(gè)比特，相同，記錄 A 和下一跳地址。例如，查找目的地址 100110*。而且在選擇結(jié)點(diǎn)后，需要將目的地址和得到的結(jié)點(diǎn)前綴按照前綴的長(zhǎng)度進(jìn)行比特匹 配，如果完全相同，則匹配成功，接著向下尋找，直到?jīng)]有分支。 Patricia Trie 的查找方法與 Radix Trie 很相似。算法的空間復(fù)雜度為 O(N),由于存在回溯的問(wèn)題，因此最壞情況下的查找性能為O( 2W )。但是，還需要在結(jié)點(diǎn)中加入一項(xiàng)在查找時(shí)需要跳過(guò)的比特位數(shù)，這是因?yàn)閯h除了原來(lái)結(jié)構(gòu)中的一些結(jié)點(diǎn)，相應(yīng)的有些比特不需要匹配也就不能 準(zhǔn)確匹配，因此需要加上這樣一個(gè)標(biāo)記。沒(méi)有分支的節(jié)點(diǎn)的定義是如果一個(gè)節(jié)點(diǎn)不是前綴節(jié)點(diǎn)而且不同時(shí)具有左分支和右分支。第 3， 4 行，第 5， 6 行，第 7， 8 行，記錄相同，行索引簡(jiǎn)并，實(shí)現(xiàn)壓縮。 Patricia 路由表查找 Patricia 前綴樹(shù) (Patricia Trie) 平衡二叉樹(shù)：除葉和根外，節(jié)點(diǎn)度均為 ，前 2 位對(duì)應(yīng)于列索引，后 3 位對(duì)應(yīng)于行索引。由于網(wǎng)絡(luò)中所有的路由器都發(fā)送 LSP，經(jīng)過(guò)一段時(shí)間以后，每一個(gè)路由器都保持了一張完整的網(wǎng)絡(luò)拓?fù)鋱D，再在這個(gè)拓?fù)鋱D上，利用最短通路算法（例如 Dijkstra 算法等），路由器就可以計(jì)算出從任何源點(diǎn)到任何目的地的最佳通路。一個(gè) LSP 通常包含源路由器的標(biāo)識(shí)符、相鄰路由器的標(biāo)識(shí)符，以及 二者 之間鏈路的費(fèi)用。這樣以此類(lèi)推，經(jīng)過(guò)一段時(shí)間后便可將網(wǎng)絡(luò)中各路由器所獲得的距離矢量信息在各路由器上統(tǒng)一起來(lái)，這樣各路由器只需要查看這個(gè)距離矢量表就可以為不同來(lái)源分組找到一條最佳的路由。每個(gè)距離矢量表項(xiàng)包括兩部分：到該目的節(jié)點(diǎn)的下一跳節(jié)點(diǎn)（即本節(jié)點(diǎn)通過(guò)那個(gè)鄰節(jié)點(diǎn)到達(dá)指定的目的節(jié)點(diǎn)），和到達(dá)目的結(jié)點(diǎn)所需時(shí)間或距離，通信子網(wǎng)中的其它每個(gè)路由器在表中占據(jù)一個(gè)表項(xiàng)，并作為該表項(xiàng)的索引。 距離矢量路由控制 ： 每個(gè)路由器維護(hù)一張矢量表，表中列出了通往各個(gè)網(wǎng)絡(luò)的開(kāi)銷(xiāo)（距離）與下一跳路由（方向）。 電話(huà)呼叫的固定等級(jí)制路由選擇 ： ：構(gòu)成基干路由。 即利用 RTSCTS 握手程序，確保接下來(lái)傳送資料時(shí)，不會(huì)被碰撞；③ 接收端收到數(shù)據(jù)包后，將以包內(nèi)的 CRC 校驗(yàn)碼 來(lái)檢驗(yàn)包數(shù)據(jù)是否正確，若是檢驗(yàn)結(jié)果正確時(shí)，接收端將響應(yīng) ACK 包，告知發(fā)射端數(shù)據(jù)己經(jīng)被成功地接收。此時(shí)間區(qū)間即稱(chēng)“碰撞檢測(cè)窗口”。（ 3）“碰撞檢測(cè)窗口” —— 任一發(fā)送節(jié)點(diǎn)若能完整的發(fā)完一個(gè)數(shù)據(jù)幀，則停頓一段時(shí)間（兩倍的最大傳播時(shí)延）并監(jiān)聽(tīng)信道情況。一旦檢測(cè)到碰撞發(fā)生，應(yīng)立即中止發(fā)送，而不管目前正在發(fā)送的幀是否發(fā)完。 CSMA/CD技術(shù)是在發(fā)送數(shù)據(jù)后對(duì)沖突進(jìn)行檢測(cè)，如果檢測(cè)到?jīng)_突，該站立即停止發(fā)送數(shù)據(jù)分組，并向總線(xiàn)上發(fā)出一串阻塞信號(hào)，通知總線(xiàn)上各站沖突已發(fā)生，在等一段隨機(jī)時(shí)間，然后在采用 CSMA 進(jìn)行傳輸。 在采用 CSMA 技術(shù)時(shí)，雖然在發(fā)送前進(jìn)行了載波偵聽(tīng)，有可能同時(shí)偵聽(tīng)到信道空閑后同時(shí)傳輸造成數(shù)據(jù)的沖突。 純：易損期為 2T 其中 G=gT 吞吐性能 S = G*e^(2G),Smax=；時(shí)隙：易損期為 T 其中 G=gT 吞吐性能 S =G*e^(G),Smax= CSMA/(CD/CA)隨機(jī)多址接入控制 ： （ 1） CD: 帶沖突檢測(cè)的載波監(jiān)聽(tīng) 多址接入技術(shù) 它是在 CSMA技術(shù)上增加了沖突檢測(cè)，工作在 OSI 的第二層數(shù)據(jù)鏈路層，一般應(yīng)用于有限網(wǎng)絡(luò)。 吞吐性能可提高一倍，但是時(shí)隙 aloha 需要全網(wǎng)同步，可設(shè)置一個(gè)特殊站點(diǎn)，由該站點(diǎn)發(fā)送時(shí)鐘信號(hào)。碰撞的分組將在以后的時(shí)隙中重傳。如果在某時(shí)隙內(nèi)僅有一個(gè)分組到達(dá)（包括新到達(dá)的分組和重傳分組的到 達(dá)），則該分組會(huì)傳輸成功。時(shí)隙 ALOHA協(xié)議：將時(shí)間軸劃分為若干個(gè)時(shí)隙，所有節(jié)點(diǎn)同步，各節(jié)點(diǎn)只能在時(shí)隙的開(kāi)始時(shí)刻才能夠發(fā)送分組，時(shí)隙寬度等于一個(gè)分組的傳輸時(shí)間。純 ALOHA 協(xié)議：只要有新的分組到達(dá)，就立即被發(fā)送并期望不與別的分組發(fā)生碰撞。 Aloha 隨機(jī)多址接入控制 ： ALOHA 它采用的是隨機(jī)爭(zhēng)用技術(shù)，又分為純 ALOHA 方式和時(shí)隙 ALOHA 方式二種。每當(dāng)發(fā)現(xiàn) 5 個(gè)連續(xù) 1 時(shí)，就將這 5 個(gè)連續(xù) 1 后的一個(gè) 0 刪除，以還原成原來(lái)的比特流。在接收一個(gè)幀時(shí)，先找到 F 字段以確定幀的邊界。只要發(fā)現(xiàn) 5 個(gè)連續(xù) 1，則立即填入一個(gè) 0。 比特填充 ： 在 HDLC 的幀結(jié)構(gòu)中， 常以 標(biāo)志字段 F（ 01111110） 模式在幀兩端起定界作用 ， 若在兩個(gè)標(biāo)志字段之間的比特串中，碰巧出現(xiàn)了和標(biāo)志字段 F（ 01111110）一樣的比特組合，那么就會(huì)誤認(rèn)為是幀的邊界 ， 會(huì)破壞同步 ， 為了避免出現(xiàn)這種情況， HDLC 采用零比特填充法 ， 使一幀中兩個(gè) F 字段之間不會(huì)出現(xiàn) 6 個(gè)連續(xù) 1。 1比特滑動(dòng)窗口協(xié)議 ：發(fā)送窗口 =1，接收窗口 =1； 后退 n 協(xié)議 ：發(fā)窗口 1，接收窗口 =1； 選擇重傳協(xié)議 ：發(fā)送窗口 1,接收窗口 1。此時(shí)接收窗口狀態(tài)仍不變。至此，發(fā)送方打開(kāi)的窗口又已達(dá)規(guī)定限度，在未收到新的確認(rèn)返回幀之前，發(fā)送方將暫停發(fā)送新的數(shù)據(jù)幀，此時(shí)接收窗口狀態(tài)仍不變； ⑦ 接收方已收到 1 號(hào)幀， 1 號(hào)窗口關(guān)閉， 2 號(hào)窗口打開(kāi)，表示準(zhǔn)備接收 2 號(hào)幀。此時(shí)發(fā)送窗口狀態(tài)不變； ⑤ 發(fā)送方收到接收方發(fā)來(lái)的 0 號(hào)幀確認(rèn)返回信息，關(guān)閉 0 號(hào)窗口，表示從重發(fā)表中刪除 0 號(hào)幀。至此，發(fā)送方打開(kāi)的窗口數(shù)已達(dá)規(guī)定限度，在未收到新的確認(rèn)返回幀之前，發(fā)送方將暫停發(fā)送新的數(shù)據(jù)幀。接收方 0 號(hào)窗口打開(kāi)，等待接收 0 號(hào)幀； ② 發(fā)送方打開(kāi) 0 號(hào)窗口，表示已發(fā)出 0 幀但尚確認(rèn)返回信息。發(fā)送方窗口內(nèi)的序列號(hào)代表了那些已經(jīng)被發(fā)送，但是還沒(méi)有被確認(rèn)的幀，或者是那些可以被發(fā)送的幀。發(fā)送窗口和接收窗口的序號(hào)的上下界不一定要一樣，甚至大小也可以不同。發(fā)送方可以通過(guò)滑動(dòng)窗口的大小來(lái)確定應(yīng)該發(fā)送多少字節(jié)的數(shù)據(jù)。最大窗口大小為 2n1。 在回退 n 幀的 ARQ 中 ，當(dāng)發(fā)送方接收到接收方的狀態(tài)報(bào)告指示報(bào)文出錯(cuò)后，發(fā)送方將 回退到第 N 幀 及其之后所有的幀全部再重新發(fā)送 。每發(fā)送一幀，上界 +1；每收到一個(gè)正確響應(yīng)幀，下界 +1；②接收 窗口上界表示允許接收的序號(hào)最大幀， 下界表示希望接收的幀。接收方窗口大小固定，任何時(shí)刻一幀到達(dá)，接收方通過(guò) between 檢查其序列號(hào)，確認(rèn)是否落在窗口內(nèi)，若在窗口內(nèi)，且以前未接受該幀，則接收并保存。 后 向反饋的滑窗控