Abstract

Optical flow switching is a promising architecture to service large transactions of end users with cost-effective and power-efficient direct access to all-optical networks. For dynamic sessions that are bursty, unscheduled, and only require short transmission times at the full rate of a single wavelength (approximately ones to tens of seconds), the network management and control effort can be substantial, even unimplementable if fast booking and initiation of flow service is needed. In this paper, we describe a fast scheduling algorithm that sets up end-to-end connections for users with urgent large transactions with a scheduling delay of slightly more than one round-trip time. This fast setup of connections is achieved by probing multiple lightpaths between the source and the destination. Probing multiple lightpaths is necessary for moderate to high network loads to achieve low blocking probability. However, the network burden of network-state updates and computational complexity of scheduling can be overwhelming and make the algorithm hard to scale to large networks. With the help of information about network regions periodically updated in the form of sampled entropy and mutual information of the network states, the required efforts can be substantially reduced. To minimize probing efforts and avoid unnecessarily tying up network resources, we use a modified Bellman–Ford Algorithm (Entropy–BF) to select the fewest lightpaths for probing that can satisfy a service-level-blocking probability agreement between the user and the network provider. By collapsing details of network states into scalar parameters for average entropy and mutual information, we can greatly reduce both the amount of network-state information collected and/or disseminated and the computation complexity of the lightpath selection process of the probing algorithm. The algorithm is also robust to variations of traffic statistics because it does not depend on detailed assumptions about the statistical model of the traffic, which is often unknown and highly variable in real networks. The throughput performance of this access protocol can be kept high while the network-state protocol burden and computation efforts are reduced by orders of magnitude.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. V. Chan, “Optical flow switching networks,” Proc. IEEE, vol.  100, no. 5, pp. 1079–1091, May 2012.
    [CrossRef]
  2. K. X. Lin and V. W. S. Chan, “Power optimization of optical wide area networks,” in 2012 14th Int. Conf. Transparent Optical Networks (ICTON), July2–5, 2012, pp. 1–7.
  3. G. Weichenberg, V. Chan, and M. Medard, “Design and analysis of optical flow-switched networks,” J. Opt. Commun. Netw., vol.  1, no. 3, pp. B81–B97, Aug. 2009.
    [CrossRef]
  4. V. Chan, A. Ganguly, and G. Weichenberg, “Optical flow switching with time deadlines for high-performance applications,” in 2009 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 2009, pp. 1–8.
  5. J. M. Simmons, Optical Network Design and Planning. New York: Springer, 2008.
  6. D. P. Valiant, “The complexity of enumeration and reliability problems,” SIAM J. Comput., vol.  8, no. 3, pp. 410–421, 1979.
    [CrossRef]
  7. R. G. Gallager, Discrete Stochastic Processes. Boston, MA: Kluwer Academic, 1996.
  8. T. M. Cover and J. A. Thomas, Elements of Information Theory. Hoboken, NJ: Wiley, 2006.
  9. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.
  10. D. Williams, Probability With Martingales. Cambridge, UK: Cambridge University, 1991.
  11. D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1999.
  12. L. Zhang and V. Chan, “Fast scheduling of optical flow switching,” in 2010 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 6–10, 2010, pp. 1–6.

2012 (1)

V. Chan, “Optical flow switching networks,” Proc. IEEE, vol.  100, no. 5, pp. 1079–1091, May 2012.
[CrossRef]

2009 (1)

1979 (1)

D. P. Valiant, “The complexity of enumeration and reliability problems,” SIAM J. Comput., vol.  8, no. 3, pp. 410–421, 1979.
[CrossRef]

Bertsekas, D. P.

D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1999.

Chan, V.

V. Chan, “Optical flow switching networks,” Proc. IEEE, vol.  100, no. 5, pp. 1079–1091, May 2012.
[CrossRef]

G. Weichenberg, V. Chan, and M. Medard, “Design and analysis of optical flow-switched networks,” J. Opt. Commun. Netw., vol.  1, no. 3, pp. B81–B97, Aug. 2009.
[CrossRef]

L. Zhang and V. Chan, “Fast scheduling of optical flow switching,” in 2010 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 6–10, 2010, pp. 1–6.

V. Chan, A. Ganguly, and G. Weichenberg, “Optical flow switching with time deadlines for high-performance applications,” in 2009 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 2009, pp. 1–8.

Chan, V. W. S.

K. X. Lin and V. W. S. Chan, “Power optimization of optical wide area networks,” in 2012 14th Int. Conf. Transparent Optical Networks (ICTON), July2–5, 2012, pp. 1–7.

Cormen, T. H.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.

Cover, T. M.

T. M. Cover and J. A. Thomas, Elements of Information Theory. Hoboken, NJ: Wiley, 2006.

Gallager, R. G.

R. G. Gallager, Discrete Stochastic Processes. Boston, MA: Kluwer Academic, 1996.

Ganguly, A.

V. Chan, A. Ganguly, and G. Weichenberg, “Optical flow switching with time deadlines for high-performance applications,” in 2009 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 2009, pp. 1–8.

Leiserson, C. E.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.

Lin, K. X.

K. X. Lin and V. W. S. Chan, “Power optimization of optical wide area networks,” in 2012 14th Int. Conf. Transparent Optical Networks (ICTON), July2–5, 2012, pp. 1–7.

Medard, M.

Rivest, R. L.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.

Simmons, J. M.

J. M. Simmons, Optical Network Design and Planning. New York: Springer, 2008.

Stein, C.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.

Thomas, J. A.

T. M. Cover and J. A. Thomas, Elements of Information Theory. Hoboken, NJ: Wiley, 2006.

Valiant, D. P.

D. P. Valiant, “The complexity of enumeration and reliability problems,” SIAM J. Comput., vol.  8, no. 3, pp. 410–421, 1979.
[CrossRef]

Weichenberg, G.

G. Weichenberg, V. Chan, and M. Medard, “Design and analysis of optical flow-switched networks,” J. Opt. Commun. Netw., vol.  1, no. 3, pp. B81–B97, Aug. 2009.
[CrossRef]

V. Chan, A. Ganguly, and G. Weichenberg, “Optical flow switching with time deadlines for high-performance applications,” in 2009 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 2009, pp. 1–8.

Williams, D.

D. Williams, Probability With Martingales. Cambridge, UK: Cambridge University, 1991.

Zhang, L.

L. Zhang and V. Chan, “Fast scheduling of optical flow switching,” in 2010 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 6–10, 2010, pp. 1–6.

J. Opt. Commun. Netw. (1)

Proc. IEEE (1)

V. Chan, “Optical flow switching networks,” Proc. IEEE, vol.  100, no. 5, pp. 1079–1091, May 2012.
[CrossRef]

SIAM J. Comput. (1)

D. P. Valiant, “The complexity of enumeration and reliability problems,” SIAM J. Comput., vol.  8, no. 3, pp. 410–421, 1979.
[CrossRef]

Other (9)

R. G. Gallager, Discrete Stochastic Processes. Boston, MA: Kluwer Academic, 1996.

T. M. Cover and J. A. Thomas, Elements of Information Theory. Hoboken, NJ: Wiley, 2006.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT and McGraw-Hill, 2009.

D. Williams, Probability With Martingales. Cambridge, UK: Cambridge University, 1991.

D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1999.

L. Zhang and V. Chan, “Fast scheduling of optical flow switching,” in 2010 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 6–10, 2010, pp. 1–6.

K. X. Lin and V. W. S. Chan, “Power optimization of optical wide area networks,” in 2012 14th Int. Conf. Transparent Optical Networks (ICTON), July2–5, 2012, pp. 1–7.

V. Chan, A. Ganguly, and G. Weichenberg, “Optical flow switching with time deadlines for high-performance applications,” in 2009 IEEE Global Telecommunications Conf. (GLOBECOM), Dec. 2009, pp. 1–8.

J. M. Simmons, Optical Network Design and Planning. New York: Springer, 2008.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (16)

Fig. 1.
Fig. 1.

Schematic diagram of the relationship between the control plane and the data plane. In the control plane, the set of available wavelength channels and entropy evolutions are broadcast to each node in the network via a packet switched network coexisting in the same optical network.

Fig. 2.
Fig. 2.

Network-state information broadcast at two time scales. Entropy evolution is broadcast at a coarse time scale, and the set of available wavelength channels is broadcast at a fine time scale ( 0.5 × average transaction time).

Fig. 3.
Fig. 3.

Two-state Markov process model of a single link. (a) A single link with Poisson traffic arrival rate λ and mean service time ( 1 / μ ) . (b) Markov process model of the link states.

Fig. 4.
Fig. 4.

Entropy H ( t ) of one link with γ λ / μ = 1 / 3 , 0.6, 1, 3 and 30.

Fig. 5.
Fig. 5.

More lightpaths need to be probed as time passes after the latest update to achieve the same blocking probability P B .

Fig. 6.
Fig. 6.

Simple network of one source–destination pair with m lightpaths in between. The blocking probabilities of the lightpaths are identically and independently distributed random variables X ’s.

Fig. 7.
Fig. 7.

N ¯ max (the upper bound of the number of lightpaths to probe) and its N ¯ appr for target-blocking probability P B = 10 4 .

Fig. 8.
Fig. 8.

Average number of lightpaths to probe to achieve the target-blocking probability, P B = 10 4 .

Fig. 9.
Fig. 9.

Average number of lightpaths to probe to achieve the target-blocking probability P B = 10 4 for the case where ordered-lightpath selecting does not gain.

Fig. 10.
Fig. 10.

Path with two links L 1 and L 2 .

Fig. 11.
Fig. 11.

Path with n links L 1 , L 2 , , and L n .

Fig. 12.
Fig. 12.

Average number of lightpaths to probe a given average path entropy to achieve target-blocking probability P B = 10 4 .

Fig. 13.
Fig. 13.

Mesh network with five nodes. Each arc represents a group of bidirectional links connecting the same node pair.

Fig. 14.
Fig. 14.

Illustration of the I-Transform.

Fig. 15.
Fig. 15.

First and second derivatives of f ( h ) with respect to h ( 0 , 1 ) . f ( h ) equals zero at point C. (a)  f ( h ) , (b)  f ( h ) .

Fig. 16.
Fig. 16.

f ( h ) with respect to h ( 0 , 1 ) . Line AB is the tangent line of f ( h ) that passes B.

Tables (1)

Tables Icon

Algorithm 1. Entropy–BF Algorithm

Equations (92)

Equations on this page are rendered with MathJax. Learn more.

H ( t ) = H b ( X ( t ) ) = X ( t ) log 2 X ( t ) ( 1 X ( t ) ) log 2 ( 1 X ( t ) ) .
d P ( t ) d t = A × P ( t ) ; t 0 .
P ( t ) = e A t P ( 0 ) = [ μ λ + μ + λ λ + μ e ( λ + μ ) t λ λ + μ λ λ + μ e ( λ + μ ) t ] .
H ( t ) = ( 1 γ + 1 + γ γ + 1 e ( 1 + γ ) μ t ) × log 2 ( 1 γ + 1 + γ γ + 1 e ( 1 + γ ) μ t ) ( γ γ + 1 γ γ + 1 e ( 1 + γ ) μ t ) × log 2 ( γ γ + 1 γ γ + 1 e ( 1 + γ ) μ t ) .
H = 1 γ + 1 log 2 1 γ + 1 γ γ + 1 log 2 γ γ + 1 .
i = 1 N X i P B < i = 1 N 1 X i ,
i = 1 N log 2 X i log 2 P B < i = 1 N 1 log 2 X i .
N ¯ · E [ log 2 X ] log 2 P B < ( N ¯ 1 ) · E [ log 2 X ] ,
log 2 P B E [ log 2 X ] + 1 > N ¯ log 2 P B E [ log 2 X ] .
H ¯ H 1 + H 2 + + H N ( A ) N ( A ) .
E [ H ¯ ] = E [ H 1 + H 2 + + H N ( A ) N ( A ) ] = E [ H ] .
f X ( x ) 0 , for x [ 0 , 0.5 ] , 0 0.5 f X ( x ) d x = 1 , E [ H b ( X ) ] = h 0 .
( P 1 ) : N ¯ max = max f X ( x ) C log 2 P B E [ log 2 ( X ) ] ,
( P 2 ) : min f X ( x ) C E [ log 2 ( X ) ] .
i = 1 n y i = 1 , i = 1 n y i H b ( x i ) = h 0 , y i 0 , for i { 1 , , n } .
1 [ 1 1 1 ] T , y [ y 1 y 2 y n ] T , h [ H b ( x 1 ) H b ( x 2 ) H b ( x n ) ] T , g [ log 2 x 1 log 2 x 2 log 2 x n ] T .
( P 3 ) : minimize : g T y , subject to : 1 T y = 1 , h T y = h 0 , y i 0 , for i { 1 , , n } .
f X ( x ) = α δ ( x x 1 ) + ( 1 α ) δ ( x x 2 ) ,
minimize : α log 2 ( x 1 ) ( 1 α ) log 2 ( x 2 ) subject to : α H b ( x 1 ) + ( 1 α ) H b ( x 2 ) = h 0 , 0 α 1 , 0 x i 1 , for i = 1 , 2 .
E [ log 2 ( X ) ] min = { log 2 [ H b 1 ( h 0 ) ] if h 0 h A ( 1 h 0 ) { log 2 [ H b 1 ( h 0 ) ] } + h 0 h A 1 h A if h 0 > h A ,
H b 1 ( h ) log 2 · log 2 1 H b 1 ( h ) H b 1 ( h ) = h 1 log 2 H b 1 ( h ) + 1 ,
N ¯ max = { log 2 ( P B ) log 2 [ H b 1 ( h 0 ) ] if h 0 h A log 2 ( P B ) · ( 1 h A ) ( 1 h 0 ) { log 2 [ H b 1 ( h 0 ) ] } + h 0 h A if h 0 > h A .
N ¯ appr = log 2 ( P B ) log 2 [ H b 1 ( h 0 ) ] .
N ¯ max N ¯ appr N ¯ max | h B = 0.145 .
H ( L 1 , L 2 ) = H ( L 1 ) + H ( L 2 ) I ( L 1 ; L 2 ) .
I ( L 1 ; L 2 ) = l 1 , l 2 ( P L 1 L 2 ( l 1 , l 2 ) × log 2 P L 1 L 2 ( l 1 , l 2 ) P L 1 ( l 1 ) P L 2 ( l 2 ) ) .
P L j ( l j ) = { β for l j = 0 1 β for l j = 1 , where j = 1 or 2.
ξ = Cov ( L 1 , L 2 ) Var ( L 1 ) Var ( L 2 ) .
Q = [ β [ 1 ( 1 β ) ( 1 ξ ) ] β ( 1 β ) ( 1 ξ ) β ( 1 β ) ( 1 ξ ) ( 1 β ) [ 1 β ( 1 ξ ) ] ] ,
H ( L 1 , L 2 ) = l 1 = 0 , 1 l 2 = 0 , 1 P L 1 , L 2 ( l 1 , l 2 ) log 2 ( P L 1 , L 2 ( l 1 , l 2 ) ) ,
= j = 1 , 2 k = 1 , 2 Q j k log 2 Q j k .
( P a 2 ) min = 1 2 ( 1 H b 1 ( h 1 ) ) .
N ¯ appr 2 = log 2 P B log 2 [ 1 1 2 ( 1 H b 1 ( h 1 ) ) ] .
N E = D N V / 2 , N V T = 2 D N V , N E T 2 N E + N V D ( D 1 ) = O ( N V D 2 ) .
H ¯ ( t ) = j = 0 k 1 H j ( t j Δ ) k .
I ¯ ( t ) = j = 0 k 1 I j ( t j Δ ) k .
Y n = n X c n , for n = { 1 , 2 , } .
Y n X c almost surely .
E [ log 2 ( Y n ) ] E [ log 2 ( X c ) ] , and E [ H b ( Y n ) ] E [ H b ( X c ) ] = h 0 .
Y ^ n α = Y n + ( 1 2 Y n ) α .
g n ( 0 ) = E [ H b ( Y n ) ] and g n ( 1 ) = E [ H b ( 1 2 ) ] = 1 .
E [ log 2 ( Y ^ n α n * ) ] E [ log 2 ( Y n ) ] ,
E [ log 2 ( Y ^ n α n * ) ] E [ log 2 ( X c ) ] .
E [ log 2 ( Y ^ N α N * ) ] < E [ log 2 ( X ) ] + ϵ = E [ log 2 ( X d * ) ] .
f ( h ) log 2 ( H b 1 ( h ) ) for h ( 0 , 1 ) .
minimize : α f ( h 1 ) + ( 1 α ) f ( h 2 )
subject to : α h 1 + ( 1 α ) h 2 = h 0 ,
0 α 1 ,
0 x i 1 , for i = 1 , 2 .
f ( h ) = 1 ( log 2 ) x log 2 1 x x , f ( h ) = ( 1 x ) log 2 1 x x 1 log 2 ( log 2 ) x 2 ( 1 x ) ( log 2 1 x x ) 3 ,
k ( h ) = log 2 [ H b 1 ( h ) ] 1 h 1 .
k ( h ) = h 1 H b 1 ( h ) log ( 2 ) · log 2 1 H b 1 ( h ) H b 1 ( h ) + log 2 ( H b 1 ( h ) ) + 1 ( h 1 ) 2 .
h 1 H b 1 ( h ) log 2 · log 2 1 H b 1 ( h ) H b 1 ( h ) log 2 H b 1 ( h ) 1 = 0 .
H ( L 1 , L 2 ) = l 1 { 0 , 1 } l 2 { 0 , 1 } P L 1 , L 2 ( l 1 , l 2 ) log 2 ( P L 1 , L 2 ( l 1 , l 2 ) ) ,
H ( M 2 ) = P L 1 , L 2 ( 0 , 0 ) log 2 P L 1 , L 2 ( 0 , 0 ) ( P L 1 , L 2 ( 0 , 1 ) + P L 1 , L 2 ( 1 , 0 ) + P L 1 , L 2 ( 1 , 1 ) ) log 2 ( P L 1 , L 2 ( 0 , 1 ) + P L 1 , L 2 ( 1 , 0 ) + P L 1 , L 2 ( 1 , 1 ) ) .
( ( l 1 , l 2 ) ( 0 , 0 ) P L 1 , L 2 ( l 1 , l 2 ) ) log 2 ( l 1 , l 2 ) ( 0 , 0 ) P L 1 , L 2 ( l 1 , l 2 ) ( l 1 , l 2 ) ( 0 , 0 ) P L 1 , L 2 ( l 1 , l 2 ) log 2 P L 1 , L 2 ( l 1 , l 2 ) .
( ( l 1 , l 2 , , l n ) ( 0 , 0 , , 0 ) P L 1 , L 2 , , L n ( l 1 , l 2 , , l n ) ) × log 2 ( ( l 1 , l 2 , , l n ) ( 0 , 0 ) P L 1 , L 2 ( l 1 , l 2 , , l n ) ) ( l 1 , l 2 , , l n ) ( 0 , 0 , , 0 ) P L 1 , L 2 , , L n ( l 1 , l 2 , , l n ) × log 2 P L 1 , L 2 , , L n ( l 1 , l 2 , , l n ) .
H ( L 1 , L 2 , , L n ) i = 1 n H ( L i ) i = 1 n 1 I ( L i ; L i + 1 ) .
H ( L 1 , L 2 , , L k + 1 ) = H ( L 1 , L 2 , , L k ) + H ( L k + 1 ) I ( L k + 1 ; L 1 , L 2 , , L k ) H ( L 1 , L 2 , , L k ) + H ( L k + 1 ) I ( L k + 1 ; L k ) i = 1 k H ( L i ) i = 1 k 1 I ( L i ; L i + 1 ) + H ( L k + 1 ) I ( L k ; L k + 1 ) = i = 1 k + 1 H ( L i ) i = 1 k I ( L i ; L i + 1 ) .
H ( β , ξ ) = H ( L 1 , L 2 ) .
( P 4 ) : minimize : P a 2 = β [ 1 ( 1 β ) ( 1 ξ ) ]
subject to : H ( β , ξ ) = h , for h ( 1 , 2 ] , 0.5 β 1 , 0 ξ 1.
L ( β , ξ , λ ) = P X 1 , X 2 ( 0 , 0 ) + λ ( H ( β , ξ ) h ) ,
L = 0 .
( P 5 ) : minimize : P a 2 = y 1 subject to : f ( y 1 ) 2 f ( y 2 ) f ( y 3 ) h , h ( 1 , 2 ] , y 1 + 2 y 2 + y 3 = 1 , y 1 0 , y 2 0 , y 3 0.
f ( y 1 ) + 2 f ( y 2 ) + f ( y 3 ) = h , h ( 1 , 2 ] , y 1 + 2 y 2 + y 3 = 1 , y 2 = y 3 .
Δ t ( y ^ ) + i = 1 4 μ i Δ g i ( y ^ ) + λ Δ u ( y ^ ) = 0 ,
μ i 0 , i = 1 , 2 , 3 , 4 ,
μ i g i ( y ^ ) = 0 , i = 1 , 2 , 3 , 4.
1 + μ 1 log 2 ( log y ^ 1 + 1 ) + λ = 0 ,
y ^ 2 = y ^ 3 .
( P5 - E ) : minimize : P a 2 = y 1
subject to : f ( y 1 ) 2 f ( y 2 ) f ( y 3 ) = h for h ( 1 , 2 ] ,
y 1 + 2 y 2 + y 3 = 1 ,
y 1 0 ,
y 2 0 ,
y 3 0 ,
( P4 - N ) : minimize : P a 2 = β [ 1 ( 1 β ) ( 1 ξ ) ]
subject to : H ( β , ξ ) = h , for h ( 1 , 2 ] ,
0.5 β 1 ,
0 ξ 1.
Q = [ y 1 y 2 y 2 y 3 ]
y 3 = 1 y 1 2 y 2 = 1 [ 1 ( 1 β ) ( 1 ξ ) ] 2 β ( 1 β ) ( 1 ξ ) = ( 1 β ) [ 1 β ( 1 ξ ) ] = Q 22 .
Case One : H ( L 1 ) = 1 , H ( L 2 ) = 1 , H ( L 1 , L 2 ) = h , Case Two : H ( L 1 ) = 1 , ξ = 0 , H ( L 1 , L 2 ) = h .
Q 1 = [ 1 2 1 ξ 4 1 ξ 4 1 ξ 4 1 2 1 ξ 4 ] .
H ( L 1 , L 2 ) = 1 ξ 2 log 2 1 ξ 4 ( 1 1 ξ 2 ) log 2 ( 1 2 1 ξ 4 ) = 1 ξ 2 ( log 2 1 2 + log 2 1 ξ 2 ) ( 1 1 ξ 2 ) [ log 2 1 2 + log 2 ( 1 1 ξ 2 ) ] = log 2 1 2 ( 1 1 ξ 2 ) log 2 1 ξ 2 ( 1 1 ξ 2 ) log 2 ( 1 1 ξ 2 ) = 1 + H b ( 1 ξ 2 ) = h .
P a 2 = 1 2 [ 1 H b 1 ( h 1 ) ] .
P a 2 = 1 2 [ 1 H b 1 ( h 1 ) ] .
P a 2 ( z 1 ) = 1 2 ( 1 H b 1 ( h 1 ) ) .
P a 2 ( z 2 ) = [ 1 H b 1 ( h 2 ) ] 2 .
1 2 { log 2 [ 1 H b 1 ( 1 ) ] log 2 [ 1 H b 1 ( h 1 ) ] } > log 2 [ 1 H b 1 ( h 2 ) ] .
( P a 2 ) min = 1 2 ( 1 H b 1 ( h 1 ) ) .