Allocated to basic Allocated to vanable -Unallocated vary greatly.In order to heuristically decrease the length of sub-traffic sub-traffic virtual links (substrate paths),we prefer the substrate node s tSp+1 s6+2 fSb-c [S with more resources in its vicinity.Therefore,we propose in the following,a Markov chain-based node ranking method, Frame length:L MCRank. Fig.3.A snapshot of time slot allocation in a substrate link 2)MCRank:we define the resource,R(n'),of a substrate node,n,as the product of its residual CPU resource and a half of the collective bandwidth resources of its outgoing links: sub-traffic.Therefore,RB(e)is (L-b-d)/L.B(e)plus the available room in the middle d slots. Rn=RCn.∑ A simple and practical measurement of residual room,rbg. e)(e) in a single time slot,ts(b<k<b+d+1),is defined as the where NeighE(n')denotes the set of links that are adjacent probability of a variable sub-traffic flow that would cause the to n.The coefficient 1/2 can be seen as the bandwidth of a collision probability to be higher than ph if tsk is assigned to link is equally shared between its endpoints,though it is not it.Hence,by Eq.(3).we have: in fact.We then normalize R'(n). 1-A(Dg)(1-rbg)-(B(De)(1-rbk)+A(De).rbg)=pth R(n) NormR(n)= (7) ∑mEN:R(m') That is: Intuitively,if the MCRank(n')of a substrate node,n,is rb =A(D)+B(D)+Pa-1P-Prcoo (D) (4) high,the possible reasons are:(i)the node itself has ample B(Dk) B(Di) resources;(ii)its neighbors have abundant resources.Hence, Thereby,the available room in the middle d slots that are we define the MCRank(n)as: allocated to variable sub-traffic is: MCRank(n)=w1.MCRank(n) B(e)bd NormR(n) .S rbk L eNghN()>eNeighN()NormR() +w2· MCRank(m) k=b+1 (8) In summary: where wi and w2 are the corresponding weights. NormR(n)/eNeighN()NormR(h)can be seen as the L-b-d RB(e)= L .B(e)+B(e) .rbk impact of m'on n.Let P be a matrix with rows and columns L k=b+l corresponding to substrate nodes,and Vn',m'E Ns: (5) pa-Procomaon(D Be Wl if m3 n =(L-b-d+ L k=b+1 B(Dk) P(m',n')= W2· NormR(n) ∑SeNeigkMm)NormR(h) if(m',n)∈Es (9) RC5(n')can be analyzed in a similar way. 0 otherwise C.Markov Chain-based Node Ranking (MCRank) Then,Eq.(8)can be expressed in the following matrix form: 1)Preliminaries:PageRank [21]nicely reflects the popu- MCRank·P=MCRank (10) larity and quality of web pages.In PageRank,the rank of a Let wi+w2=1;it is easy to verify that P is stochastic,i.e.: page measures the "importance"of that page.A page has a higher rank if it is pointed to by more highly-ranked pages. P(m3,n)=P(m5,m)+ P(m',n)=1 The more pages that one page points to,the less its influence nENS nENeighN(n) on their rankings is.This intuitive idea can be formalized as Hence,MCRank is actually a stationary distribution of the follows.The World-Wide-Web is treated as a directed graph, Markov chain with transition matrix P.The following theorem with web pages as vertices and hyper-links as directed edges. gives the existence of a stationary distribution. The rank of a page p,denoted by rank(p),is supposed to Theorem 2:the Markov chain,determined by P,has a satisfy: Tank(g） stationary distribution. rank(p)= (6) Proof:it is sufficient to prove that:(i)MCRank has finite g:(g-p)EE d4(g) states,as there are a finite number of substrate nodes;(ii)the where d(g)means the number of edges going out of page g. substrate network is strongly connected,so the Markov chain Note that the sum is over edges going into p. is irreducible:(iii)the substrate node iteslf has an impact on Inspired by PageRank,we consider using a similar method its MCRank,i.e.,the chain is a lazy random walk,so it is to measure the topology importance of a substrate node.To aperiodic.The theorem follows immediately. ■ understand the topology importance,suppose that there are Based on [21],we give our algorithm to calculate the two substrate nodes with the same residual resources,but stationary distribution,i.e.,MCRank,in Algorithm 3,where the resources of their neighbors (or neighbors of neighbors) y serves as a threshold to control iterations. 2413Fig. 3. A snapshot of time slot allocation in a substrate link sub-traffic. Therefore, RBs (e s ) is (L−b−d)/L · B s (e s ) plus the available room in the middle d slots. A simple and practical measurement of residual room, rbk, in a single time slot, tsk (b < k < b + d + 1), is defined as the probability of a variable sub-traffic flow that would cause the collision probability to be higher than pth if tsk is assigned to it. Hence, by Eq. (3), we have: 1 − A(Dk)(1 − rbk) − (B(Dk)(1 − rbk) + A(Dk) · rbk) = pth That is: rbk = A(Dk) + B(Dk) + pth − 1 B(Dk) = pth − Prcollision(Dk) B(Dk) (4) Thereby, the available room in the middle d slots that are allocated to variable sub-traffic is: B s (e s ) L · ∑ b+d k=b+1 rbk In summary: RBs (e s ) = L − b − d L · B s (e s ) + B s (e s ) L · ∑ b+d k=b+1 rbk = (L − b − d + ∑ b+d k=b+1 pth − Prcollision(Dk) B(Dk) ) B s (e s ) L (5) RCs (n s ) can be analyzed in a similar way. C. Markov Chain-based Node Ranking (MCRank) 1) Preliminaries: PageRank [21] nicely reflects the popu￾larity and quality of web pages. In PageRank, the rank of a page measures the “importance” of that page. A page has a higher rank if it is pointed to by more highly-ranked pages. The more pages that one page points to, the less its influence on their rankings is. This intuitive idea can be formalized as follows. The World-Wide-Web is treated as a directed graph, with web pages as vertices and hyper-links as directed edges. The rank of a page p, denoted by rank(p), is supposed to satisfy: rank(p) = ∑ g:(g,p)∈E rank(g) d+(g) (6) where d+(g) means the number of edges going out of page g. Note that the sum is over edges going into p. Inspired by PageRank, we consider using a similar method to measure the topology importance of a substrate node. To understand the topology importance, suppose that there are two substrate nodes with the same residual resources, but the resources of their neighbors (or neighbors of neighbors) vary greatly. In order to heuristically decrease the length of virtual links (substrate paths), we prefer the substrate node with more resources in its vicinity. Therefore, we propose in the following, a Markov chain-based node ranking method, MCRank. 2) MCRank: we define the resource, R(n s ), of a substrate node, n s , as the product of its residual CPU resource and a half of the collective bandwidth resources of its outgoing links: R(n s ) = RCs (n s ) · ∑ e s∈NeighE(n s ) 1 2 RBs (e s ) where NeighE(n s ) denotes the set of links that are adjacent to n s . The coefficient 1/2 can be seen as the bandwidth of a link is equally shared between its endpoints, though it is not in fact. We then normalize R s (n s ). NormR(n s ) = R s (n s ) ∑ ms∈Ns Rs (ms ) (7) Intuitively, if the MCRank(n s ) of a substrate node, n s , is high, the possible reasons are: (i) the node itself has ample resources; (ii) its neighbors have abundant resources. Hence, we define the MCRank(n s ) as: MCRank(n s ) = w1 · MCRank(n s ) + w2 · ∑ ms∈NeighN(n s ) NormR(n s ) ∑ h s∈NeighN(ms ) NormR(h s ) · MCRank(m s ) (8) where w1 and w2 are the corresponding weights. NormR(n s )/ ∑ h s∈NeighN(ms ) NormR(h s ) can be seen as the impact of m s on n s . Let P be a matrix with rows and columns corresponding to substrate nodes, and ∀n s , m s ∈ N s : P(m s , n s ) =    w1 if m s = n s w2 · NormR(n s ) ∑ h s∈NeighN(ms) NormR(h s ) if (m s , n s ) ∈ E s 0 otherwise (9) Then, Eq. (8) can be expressed in the following matrix form: MCRank · P = MCRank (10) Let w1 + w2 = 1; it is easy to verify that P is stochastic, i.e.: ∑ n s∈Ns P(m s , n s ) = P(m s , m s ) + ∑ n s∈NeighN(ms ) P(m s , n s ) = 1 Hence, MCRank is actually a stationary distribution of the Markov chain with transition matrix P. The following theorem gives the existence of a stationary distribution. Theorem 2: the Markov chain, determined by P, has a stationary distribution. Proof: it is sufficient to prove that: (i) MCRank has finite states, as there are a finite number of substrate nodes; (ii) the substrate network is strongly connected, so the Markov chain is irreducible; (iii) the substrate node iteslf has an impact on its MCRank, i.e., the chain is a lazy random walk, so it is aperiodic. The theorem follows immediately. Based on [21], we give our algorithm to calculate the stationary distribution, i.e., MCRank, in Algorithm 3, where γ serves as a threshold to control iterations. 2413