Abstract

Light-trails (LTs) have been proposed as a solution for optical networking to provide support for emerging services such as video-on-demand, pseudo-wires, data-centers, etc. To provision these services we require features such as dynamic bandwidth provisioning, optical multicasting, sub-wavelength grooming and a low-cost hardware platform—all of which are available through the LT concept. Architectural, performance, resilience and implementation studies of LTs have led to consideration of this technology in metropolitan networks. In the area of architecture and performance, significant literature is available in terms of static network optimization. An area that has not yet been considered and which is of service provider importance (from an implementation perspective) is the stochastic behavior and dynamic growth of the LT virtual topology. In this paper, we propose a two-stage scheduling algorithm that efficiently allocates bandwidth to nodes within a LT and also grows the virtual topology of LTs based on basic utility theory. The algorithm facilitates growth of the LT topology fathoming across all the necessary and sufficient parameters. The algorithm is formally stated, analyzed using Markov models and verified through simulations, resulting in 45% betterment over existing linear program (LP) or heuristic models. The outcome of the growth algorithm is an autonomic optical network that suffices for service provider needs while lowering operational and capital costs. This paper presents the first work in the area of dual topology planning—at the level of connections as well as at the level of the network itself.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. K. Bode, "SBC: 18 million fiber users in three years," [Online]. Available: www.broadbandreports.com/shownews/55799
  2. M. Chamania and A. Jukan, "A survey of inter-domain peering and provisioning solutions for the next generation optical networks," IEEE Commun. Surv. Tutorials 11, (1), 33‒51 (2009).
    [CrossRef]
  3. A. Gumaste and I. Chlamtac, "Light-trails: a novel conceptual framework for conducting optical communications," IEEE Workshop on High-Performance Switching and Routing, 2003.
  4. A. Gumaste and S. Q. Zheng, "Next generation optical storage area networks: the light-trails approach," IEEE Commun. Mag. 43, (3), 72‒79 (2005).
    [CrossRef]
  5. P. Gokhale, T. Das, and A. Gumaste, "Cloud computing over light-trail WDM core networks," Optic Fiber Communication Conf., 2010, OWR3.
  6. A. Gumaste, N. Ghani, P. Bafna, A. Lodha, A. Agrawal, T. Das, and S. Zheng, "DynaSPOT: dynamic services provisioned optical transport test-bed—achieving multi-rate multi-service dynamic provisioning using strongly connected light-trail (SLiT) technology," J. Lightwave Technol. 26, (1), 183‒195 (2008).
    [CrossRef]
  7. A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.
  8. A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.
  9. S. Balasubramanian, A. K. Somani, and A. E. Kamal, "Sparsely hubbed light-trail grooming networks," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2005, Boston, MA.
  10. X. Luo and B. Wang, "Integrated scheduling of grid applications in WDM optical light-trail networks," J. Lightwave Technol. 27, (12), 1785‒1795 (2009).
    [CrossRef]
  11. Y. Ye, H. Woesner, and I. Chlamtac, "OTDM light-trail networks," Int. Conf. on Transparent Optical Networks (ICTON), 2005.
  12. S. Balasubramanian and A. K. Somani, "A comparative study of path level traffic grooming strategies for WDM optical networks with dynamic traffic (Invited paper)," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2008.
  13. B. Mukherjee, Optical WDM Networks, Springer, 2006.
  14. J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).
  15. P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.
  16. A. Gumaste, USPTO, "System and method for bandwidth allocation in an optical light-trail," U.S. Patent 7,590,353; .
  17. P. Palacharla, A. Gumaste, and S. Kinoshita, USPTO, "System and method for transmission and reception of traffic in optical light-trails," U.S. Patent 7,616,891; .
  18. B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).
  19. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, II, Wiley, New York, 1968.
  20. K. S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, John Wiley and Sons, New York, 2001.
  21. R. A. Barry and P. A. Humblet, "Models of blocking probability in all-optical networks with and without wavelength changers," IEEE INFOCOM, 1995.
  22. Talk by Stuart Elby, Verizon, in Market Watch, OFC 2008, San Diego, CA, Feb. 2008
  23. A. Gumaste and P. Palacharla, "Heuristic and optimal techniques for light-trail assignment in optical ring WDM networks," Comput. Commun. 30, (5), 990‒998 (2007).
    [CrossRef]
  24. A. Lodha, A. Gumaste, P. Bafna, and N. Ghani, "Stochastic optimization of light-trail optical WDM ring networks using Bender’s decomposition," IEEE Conf. on High Speed Routing and Switching (HPSR), 2007.
  25. R. Freund, Benders’ Decomposition Methods for Structured Optimization, Including Stochastic Optimization, [Online]. Available: http://ocw.mit.edu/NR/rdonlyres/Sloan-School-of-Management/15-094JSpring-2004/B5BC04B2-A362-4A78-A67C-399948CB1776/0/benders_art.pdf

2009 (2)

M. Chamania and A. Jukan, "A survey of inter-domain peering and provisioning solutions for the next generation optical networks," IEEE Commun. Surv. Tutorials 11, (1), 33‒51 (2009).
[CrossRef]

X. Luo and B. Wang, "Integrated scheduling of grid applications in WDM optical light-trail networks," J. Lightwave Technol. 27, (12), 1785‒1795 (2009).
[CrossRef]

2008 (1)

2007 (2)

A. Gumaste and P. Palacharla, "Heuristic and optimal techniques for light-trail assignment in optical ring WDM networks," Comput. Commun. 30, (5), 990‒998 (2007).
[CrossRef]

J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).

2005 (1)

A. Gumaste and S. Q. Zheng, "Next generation optical storage area networks: the light-trails approach," IEEE Commun. Mag. 43, (3), 72‒79 (2005).
[CrossRef]

2001 (1)

B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).

Agrawal, A.

Bafna, P.

A. Gumaste, N. Ghani, P. Bafna, A. Lodha, A. Agrawal, T. Das, and S. Zheng, "DynaSPOT: dynamic services provisioned optical transport test-bed—achieving multi-rate multi-service dynamic provisioning using strongly connected light-trail (SLiT) technology," J. Lightwave Technol. 26, (1), 183‒195 (2008).
[CrossRef]

A. Lodha, A. Gumaste, P. Bafna, and N. Ghani, "Stochastic optimization of light-trail optical WDM ring networks using Bender’s decomposition," IEEE Conf. on High Speed Routing and Switching (HPSR), 2007.

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

Balasubramanian, S.

S. Balasubramanian, A. K. Somani, and A. E. Kamal, "Sparsely hubbed light-trail grooming networks," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2005, Boston, MA.

S. Balasubramanian and A. K. Somani, "A comparative study of path level traffic grooming strategies for WDM optical networks with dynamic traffic (Invited paper)," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2008.

Barry, R. A.

R. A. Barry and P. A. Humblet, "Models of blocking probability in all-optical networks with and without wavelength changers," IEEE INFOCOM, 1995.

Biru, E.

P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.

Chamania, M.

M. Chamania and A. Jukan, "A survey of inter-domain peering and provisioning solutions for the next generation optical networks," IEEE Commun. Surv. Tutorials 11, (1), 33‒51 (2009).
[CrossRef]

Chandarana, J.

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

Chlamtac, I.

A. Gumaste and I. Chlamtac, "Light-trails: a novel conceptual framework for conducting optical communications," IEEE Workshop on High-Performance Switching and Routing, 2003.

Y. Ye, H. Woesner, and I. Chlamtac, "OTDM light-trail networks," Int. Conf. on Transparent Optical Networks (ICTON), 2005.

Das, T.

Doytchinov, B.

B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).

Feller, W.

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, II, Wiley, New York, 1968.

Ghani, N.

A. Gumaste, N. Ghani, P. Bafna, A. Lodha, A. Agrawal, T. Das, and S. Zheng, "DynaSPOT: dynamic services provisioned optical transport test-bed—achieving multi-rate multi-service dynamic provisioning using strongly connected light-trail (SLiT) technology," J. Lightwave Technol. 26, (1), 183‒195 (2008).
[CrossRef]

A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

A. Lodha, A. Gumaste, P. Bafna, and N. Ghani, "Stochastic optimization of light-trail optical WDM ring networks using Bender’s decomposition," IEEE Conf. on High Speed Routing and Switching (HPSR), 2007.

Gokhale, P.

P. Gokhale, T. Das, and A. Gumaste, "Cloud computing over light-trail WDM core networks," Optic Fiber Communication Conf., 2010, OWR3.

Gumaste, A.

A. Gumaste, N. Ghani, P. Bafna, A. Lodha, A. Agrawal, T. Das, and S. Zheng, "DynaSPOT: dynamic services provisioned optical transport test-bed—achieving multi-rate multi-service dynamic provisioning using strongly connected light-trail (SLiT) technology," J. Lightwave Technol. 26, (1), 183‒195 (2008).
[CrossRef]

A. Gumaste and P. Palacharla, "Heuristic and optimal techniques for light-trail assignment in optical ring WDM networks," Comput. Commun. 30, (5), 990‒998 (2007).
[CrossRef]

A. Gumaste and S. Q. Zheng, "Next generation optical storage area networks: the light-trails approach," IEEE Commun. Mag. 43, (3), 72‒79 (2005).
[CrossRef]

A. Gumaste and I. Chlamtac, "Light-trails: a novel conceptual framework for conducting optical communications," IEEE Workshop on High-Performance Switching and Routing, 2003.

P. Gokhale, T. Das, and A. Gumaste, "Cloud computing over light-trail WDM core networks," Optic Fiber Communication Conf., 2010, OWR3.

P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.

A. Gumaste, USPTO, "System and method for bandwidth allocation in an optical light-trail," U.S. Patent 7,590,353; .

P. Palacharla, A. Gumaste, and S. Kinoshita, USPTO, "System and method for transmission and reception of traffic in optical light-trails," U.S. Patent 7,616,891; .

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

A. Lodha, A. Gumaste, P. Bafna, and N. Ghani, "Stochastic optimization of light-trail optical WDM ring networks using Bender’s decomposition," IEEE Conf. on High Speed Routing and Switching (HPSR), 2007.

A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.

Humblet, P. A.

R. A. Barry and P. A. Humblet, "Models of blocking probability in all-optical networks with and without wavelength changers," IEEE INFOCOM, 1995.

Ji, Y.

J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).

Jukan, A.

M. Chamania and A. Jukan, "A survey of inter-domain peering and provisioning solutions for the next generation optical networks," IEEE Commun. Surv. Tutorials 11, (1), 33‒51 (2009).
[CrossRef]

Kamal, A. E.

S. Balasubramanian, A. K. Somani, and A. E. Kamal, "Sparsely hubbed light-trail grooming networks," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2005, Boston, MA.

Karandikar, A.

A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.

Kinoshita, S.

P. Palacharla, A. Gumaste, and S. Kinoshita, USPTO, "System and method for transmission and reception of traffic in optical light-trails," U.S. Patent 7,616,891; .

Lehoczky, J.

B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).

Lodha, A.

Luo, X.

Mukherjee, B.

B. Mukherjee, Optical WDM Networks, Springer, 2006.

Naito, T.

P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.

Palacharla, P.

A. Gumaste and P. Palacharla, "Heuristic and optimal techniques for light-trail assignment in optical ring WDM networks," Comput. Commun. 30, (5), 990‒998 (2007).
[CrossRef]

P. Palacharla, A. Gumaste, and S. Kinoshita, USPTO, "System and method for transmission and reception of traffic in optical light-trails," U.S. Patent 7,616,891; .

P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.

Sharma, V.

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

Shreve, S.

B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).

Somani, A. K.

S. Balasubramanian and A. K. Somani, "A comparative study of path level traffic grooming strategies for WDM optical networks with dynamic traffic (Invited paper)," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2008.

S. Balasubramanian, A. K. Somani, and A. E. Kamal, "Sparsely hubbed light-trail grooming networks," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2005, Boston, MA.

Trivedi, K. S.

K. S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, John Wiley and Sons, New York, 2001.

Wang, B.

Wang, H.

J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).

Wang, J.

A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.

Woesner, H.

Y. Ye, H. Woesner, and I. Chlamtac, "OTDM light-trail networks," Int. Conf. on Transparent Optical Networks (ICTON), 2005.

Xing, J.

J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).

Ye, Y.

Y. Ye, H. Woesner, and I. Chlamtac, "OTDM light-trail networks," Int. Conf. on Transparent Optical Networks (ICTON), 2005.

Zheng, S.

Zheng, S. Q.

A. Gumaste and S. Q. Zheng, "Next generation optical storage area networks: the light-trails approach," IEEE Commun. Mag. 43, (3), 72‒79 (2005).
[CrossRef]

Ann. Appl. Probab. (1)

B. Doytchinov, J. Lehoczky, and S. Shreve, "Real-time queues in heavy-traffic with earliest-deadline-first queue discipline," Ann. Appl. Probab. 11, (2), 332‒378 (2001).

Comput. Commun. (1)

A. Gumaste and P. Palacharla, "Heuristic and optimal techniques for light-trail assignment in optical ring WDM networks," Comput. Commun. 30, (5), 990‒998 (2007).
[CrossRef]

IEEE Commun. Mag. (1)

A. Gumaste and S. Q. Zheng, "Next generation optical storage area networks: the light-trails approach," IEEE Commun. Mag. 43, (3), 72‒79 (2005).
[CrossRef]

IEEE Commun. Surv. Tutorials (1)

M. Chamania and A. Jukan, "A survey of inter-domain peering and provisioning solutions for the next generation optical networks," IEEE Commun. Surv. Tutorials 11, (1), 33‒51 (2009).
[CrossRef]

J. Lightwave Technol. (2)

Proc. SPIE (1)

J. Xing, H. Wang, and Y. Ji, "BLE protection scheme for light-trail WDM mesh networks," Proc. SPIE 6784, 67840X (2007).

Other (18)

P. Palacharla, A. Gumaste, E. Biru, and T. Naito, "Implementation of burstponder card for ethernet grooming in light-trail WDM networks," IEEE Int. Conf. on Communications (ICC), 2006.

A. Gumaste, USPTO, "System and method for bandwidth allocation in an optical light-trail," U.S. Patent 7,590,353; .

P. Palacharla, A. Gumaste, and S. Kinoshita, USPTO, "System and method for transmission and reception of traffic in optical light-trails," U.S. Patent 7,616,891; .

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, II, Wiley, New York, 1968.

K. S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, John Wiley and Sons, New York, 2001.

R. A. Barry and P. A. Humblet, "Models of blocking probability in all-optical networks with and without wavelength changers," IEEE INFOCOM, 1995.

Talk by Stuart Elby, Verizon, in Market Watch, OFC 2008, San Diego, CA, Feb. 2008

P. Gokhale, T. Das, and A. Gumaste, "Cloud computing over light-trail WDM core networks," Optic Fiber Communication Conf., 2010, OWR3.

A. Gumaste, J. Chandarana, P. Bafna, N. Ghani, and V. Sharma, "On control-plane for service provisioning in light-trail WDM optical networks," IEEE Int. Conf. on Commun. (ICC), 2007.

A. Gumaste, J. Wang, A. Karandikar, and N. Ghani, "Multihop light-trails (MLT)—a solution to extended metro networks," IEEE Int. Conf. on Commun. (ICC), 2009.

S. Balasubramanian, A. K. Somani, and A. E. Kamal, "Sparsely hubbed light-trail grooming networks," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2005, Boston, MA.

Y. Ye, H. Woesner, and I. Chlamtac, "OTDM light-trail networks," Int. Conf. on Transparent Optical Networks (ICTON), 2005.

S. Balasubramanian and A. K. Somani, "A comparative study of path level traffic grooming strategies for WDM optical networks with dynamic traffic (Invited paper)," IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2008.

B. Mukherjee, Optical WDM Networks, Springer, 2006.

K. Bode, "SBC: 18 million fiber users in three years," [Online]. Available: www.broadbandreports.com/shownews/55799

A. Gumaste and I. Chlamtac, "Light-trails: a novel conceptual framework for conducting optical communications," IEEE Workshop on High-Performance Switching and Routing, 2003.

A. Lodha, A. Gumaste, P. Bafna, and N. Ghani, "Stochastic optimization of light-trail optical WDM ring networks using Bender’s decomposition," IEEE Conf. on High Speed Routing and Switching (HPSR), 2007.

R. Freund, Benders’ Decomposition Methods for Structured Optimization, Including Stochastic Optimization, [Online]. Available: http://ocw.mit.edu/NR/rdonlyres/Sloan-School-of-Management/15-094JSpring-2004/B5BC04B2-A362-4A78-A67C-399948CB1776/0/benders_art.pdf

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 (12)

Fig. 1
Fig. 1

Light-trail node architecture.

Fig. 2
Fig. 2

(Color online) Comparison of lightpaths and LTs.

Fig. 3
Fig. 3

(Color online) State diagram of the topology growth algorithm.

Fig. 4
Fig. 4

(Color online) Illustrating definition of μ j i and θ j i .

Fig. 5
Fig. 5

(Color online) Number of LTs as a function of normalized load.

Fig. 6
Fig. 6

Edge-to-edge delay using two-stage scheduling algorithm.

Fig. 7
Fig. 7

Utilization of the control channel as a function of load.

Fig. 8
Fig. 8

Packet drop ratio.

Fig. 9
Fig. 9

How is a light-trail created?

Fig. 10
Fig. 10

Assignment of connections.

Fig. 11
Fig. 11

Efficiency and packet drop as functions of O R (high loads).

Fig. 12
Fig. 12

Efficiency and packet drop as functions of O R (low loads).

Equations (98)

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

b i d i t o = max B i t o B max , σ i t o σ i t o + ψ i t o .
U ¯ ( k ) = 1 n k 1 × C f i j k f i j .
if  L B T h r e s h < U ¯ k < U B T h r e s h  and  w k : p a t h e n d k N j ¯ ¯ = 1 then create  k : e n d ( k ) = N j , c o n v ( k ) = c o n v ( k )  and  λ k = λ k ,
if  f i j : N i k , N i k , k K t  and  w k : p a t h N i c o n v k ¯ ¯ = 1 then if  U ¯ k < O R then dimension  k  to produce k : c o n v ( k ) = N i , e n d ( k ) = e n d ( k ) , λ k = λ k .
f i j : f i j  cannot be added to k K ( t ) , & f i j  cannot be added to  k  by SID, & f i j  cannot be added to  k  by DID.
k : c o n v k = N i , e n d k = N j , w k : p a t h N i c o n v k ¯ ¯ = 1 .
 (i) p b i d i j k ( t ) > a p b i d k ( t ) , (ii) U ¯ k f i j + U ¯ k f i j > U ¯ k + U ¯ k .
1 . if  N i , N j k  and  N i N j k = 1 , 2 . if  L B T h r e s h < U ¯ k f i j < U B T h r e s h .
o r i g t = N i : i = argmax j : N j k , k K t , k  is metastable B j k t / C T S P s u c c j k t .
U ¯ k + k p r e y t , f i j k , f i j p r e y f l o w t U ¯ k f i j > k p r e y t U ¯ k .
σ i t o = max j V i t o x j i and ψ i t o = min j V i t o δ j i x j i ,
b i d i t o = max B i t o / | S | B max , max j V i t o x j i max j V i t o x j i + min j V i t o δ j i x j i
= max B i t o / | S | B max , t o min j V i t o H j i min j V i t o H j i + Δ i min j V i t o H j i ,
P σ i t o < α , ψ i t o < β , B i t o < γ | V i t o ϕ P min j V i t o H j i > t o α , min j V i t o H j i + δ j i < t o + β , B i t o < γ V i t o ϕ = P A i t o > t o α , B i t o < γ | V i t o ϕ P A i t o > t o α , D i t o > t o + β , B i t o < γ | V i t o ϕ .
P A i t o > t o α , D i t o > t o + β , B i t o < γ | V i t o ϕ = P H j i > max t o α , t o + β δ j i , t o δ j i , B i t o < γ V i t o ϕ .
μ j i = max 0 , t o Δ h , min t o , max t o + β δ j i , t o α , t o δ j i
θ j i = min t o , max t o + β δ j i , t o α , t o δ j i , t o .
G i ( t o ) =  No request  V i ( t o )  arrived at  N i  in  μ j i .
L i ( t o ) =  No request  V i ( t o )  arrived at  N i  in  θ j i .
G i ( t o ) =  No request arrived at  N i  in  μ j i .
L i ( t o ) =  No request arrived at  N i  in  θ j i .
G i t o L ¯ i t o M i t o = A i t o > t o α , D i t o > t o + β , B i t o < γ , V i t o ϕ .
P ( G i ( t o ) M i ( t o ) ) = P ( No request arrived at N i in μ j i ) ( B i ( t o ) < γ ) = P n = 0 γ Z n h = 1 | S | B h i t o = n h  with arrivals limited to  θ j i , where Z n = n 1 , n 2 , , n | S | h = 1 | S | n h = n = n = 0 γ Z n h = 1 | S | e λ h i | μ j i | + | θ j i | λ h i | θ j i | n h n h ! ,
P ( G i ( t o ) L i ( t o ) M i ( t o ) ) = j = 1 h e λ h i × min t o , Δ h = exp h = 1 | S | λ h i × min t o , Δ h .
P A i t o > t o α , D i t o > t o + β , B i t o < γ V i t o ϕ = 1 1 n = 0 γ Z n h = 1 | S | e λ h i | μ j i | + | θ j i | λ h i | θ j i | n h / n h ! 1 exp h = 1 | S | λ h i × min t o , Δ h .
P A i t o > t o α , B i t o < γ | V i t o ϕ = 1 1 n = 0 γ Z n h = 1 | S | e λ h i | μ j i | + | θ j i | λ h i | θ j i | n h / n h ! 1 exp h = 1 | S | λ h i × min t o , Δ h ,
F σ , ψ , B i α , β , γ P σ i t o < α , ψ i t o < β , B i t o < γ | V i t o ϕ = n = 0 γ Z n h = 1 | S | e λ h i min t o , Δ h × λ h i × | θ j i | | θ j i | n h n h ! × 1 e h = 1 | S | λ h i × min t o , Δ h .
F b i d i t o a = P b i d i t o < a | V i t o ϕ = 0 0 1 a x a δ 2 δ x δ y F σ , ψ , B i x , y , a h B max d y d x .
F O i ( t 0 ) y = i = 1 , i i N F b i d i t o y .
P s u c c i t o = P b i d i t o O i t o = 0 1 0 x f b i d i t o , O i t o x , y d y d x .
P s u c c i t o = 0 1 f b i d i t o x × F O i t o x d x .
F b i d i t I x = 0 0 1 a x a δ 2 δ x δ y F σ , ψ , B i x , y , a h B max d y d x .
P ( bid i ( t o ) < a |  Slot  w  was the last slot won by N i ) = F b i d i t o I a , if  w = 0 F b i d i 1 I a , if  w = t o F b i d i t o w + 1 I , w : 1 w t o , if  w t o .
P N i w i n s t h e l + 2 th s l o t S t a t e a t l i s κ 1 , κ 2 , , κ N S t a t e a t l + 1 i s κ 1 , κ 2 , , κ N N i w o n t h e l + 1 t h s l o t = 0 1 f b i d i κ i + 1 I x i = 1 , i i N F b i d i κ i + 1 I x d x = P S t a t e a t l + 1 i s κ 1 , κ 2 , , κ N & N i w i n s t h e l + 2 th s l o t S t a t e a t l i s κ 1 , κ 2 , , κ N & N i w i n s t h e l + 1 th s l o t
κ i = 0 , if i = a min κ i + 1 , M , otherwise.
P v 1 , a 1 v 2 , a 2 = 0 1 f b i d i κ i + 1 I x i = 1 , i i N F b i d i κ i + 1 I x d x .
q 0 , M , M , . , M , i M , M , , κ i = 0 , , M , j M , M , , κ j = 0 , κ i = 1 , , M , i M , M , , κ j 1 , κ i = 0 , , M , i M , M , , κ j , κ i = 0 , , M , a .
κ i = M , if  κ i = 0  or  M , κ i κ y , otherwise.
q w v ̃ , u f .
P s u c c a = lim t P N a  wins the bid = v P v , a .
P f i j k = P f i j : Δ U ¯ k f i j > Δ U ¯ k f i j , k K t & L B T h r e s h U ¯ k f i j < U B T h r e s h  and  N i , N j k + P f i j : k + P f i j : k + P f i j : k + P f i j : k + P f i j : k .
P N i k = n k N = π k .
P ( N i k , N j k ) = P ( N i k ) P ( N j k ) = ( π k ) 2 .
P ( N i N j k = 1 ) = P ( N i  is upstream of  N j  on  k ) = 1 / 2 .
P f i j = x = e λ λ x / x ! .
P U ¯ k = x = P f i j k f i j n k 1 C = x
= e m λ i k h m λ i k h x C n k 1 x ! = H x , k ,
P U ¯ k x = 0 x P U ¯ k = y d y = 0 x H y , k d y .
P w k : p a t h N i N j ¯ ¯ = 1 = P N i , N j k  and  w k k .
P w k k = T max w × f i j : f i j k , k K t f i j = M k , t .
P w k : p a t h N i N j ¯ ¯ = 1 = π k 2 × M k , t .
P S i j : N i k , N j k = w N n k 1 f i j : f i j k , k K t f i j / T max .
P k S I D k = P f i j : f i j  could not be added to  k K t and  f i j  was added to  k  by  S I D .
P ( f i j  could not be added to any LT k K ( t ) ) = k K t 5 2 π k 2 y = 0 U B T h r e s h H y , k f i j .
P ( f i j  was added to  k  by SID ) = y = 0 U B T h r e s h H y , k f i j × π k 1 π k π k 2 × M k , t .
P k S I D k = k K t 5 2 π k 2 y = 0 U B T h r e s h H y , k f i j y = 0 U B T h r e s h H y , k f i j × π k 2 × M k , t 1 × π k .
P k D I D k = P f i j : f i j  could not be added to  k K t & f i j  could not be added to  k K t  by SID and  f i j  was added to  k K t  by DID .
P ( f i j  could not be added to  k K ( t )  by SID ) = 1 y = 0 U B T h r e s h H y , k f i j × π k 1 π k π k 2 × M k , t .
P ( f i j  was added to  k K ( t )  by DID ) = y = 0 U B T h r e s h H y , k f i j × π k 1 π k π k 2 × M k , t .
P k D I D k = k K t 5 2 π k 2 y = 0 U B T h r e s h H y , k f i j 1 y = 0 U B T h r e s h H y , k f i j × π k 2 × M k , t × π k 1 π k y = 0 U B T h r e s h H y , k f i j × π k 2 × M k , t × π k 1 π k .
P k  is created = P f i j : ( f i j  could not be added to  k K ( t ) ) & ( f i j  could not be added to  k K ( t )  by SID ) & ( f i j  could not be added to  k K ( t )  by DID ) .
P ( f i j  could not be added to  k K ( t )  by DID ) = 1 y = 0 U B T h r e s h H y , k f i j × π k 1 π k π k 2 × M k , t .
P k  is created = k K t 5 2 π k 2 y = 0 U B T h r e s h H y , k f i j 1 y = 0 U B T h r e s h H y , k f i j × π k 2 × M k , t × π k 1 π k 2 .
P N i = o r i g t = P i = argmax j : N j k , k K t , k  is metastable B j k t / C T S P s u c c j k t = j : N j k , k K t , k  is metastable P B i k t P s u c c i k t > B j k t P s u c c j k t .
G k t = k : c o n v k k , c o n v k e n d k ¯ ¯ = 1  or e n d k k , c o n v k e n d k ¯ ¯ = 1  or | S e n d k c o n v k | = 1 , e n d k c o n v k ¯ ¯ = 1  or | S e n d k c o n v k | = 1 , e n d k c o n v k ¯ ¯ = 1 ,
P k : k G k t , k K t = f i j k : k K t f i j 1 + μ N N 1 w C .
2 j = 1 | G k t | n k j C 2 × j = 1 | G k ( t ) | n ( k j ) C 2 = 2 x ̈ × x ̈ .
Ω k t = 1 , if  f i j k , 0 ,  otherwise.
Ω = 0 0 0 1 0 0 1 0 . . . . 1 1 1 1 2 x ̈ × x ̈ .
r m Ω k t = i , j : f i j k , k G k t f i j .
U ¯ m = r ¯ m Ω k t = r ¯ m Ω k t n k × C .
P k k = P U ¯ k = max m r ¯ m Ω k t P LT   k  contains the originator P λ k  exists P U ¯ k + k p r e y t , f i j k , f i j p r e y f l o w t U ¯ k f i j > k p r e y t U ¯ k .
q m = 1 , f i j : f i j k , k = arg r ¯ m Ω k t , P s u c c i k > P s u c c i k  or  P s u c c i k > P s u c c i k 0 ,  otherwise.
P k k = P N i k , N i = o r i g t P w k  exists P U ¯ k = max m r ¯ m Ω k t . P P s u c c i k > P s u c c i k P f i j k P k G k t + P P s u c c i k < P s u c c i k P f i j k ,
P U ¯ k = max m r ¯ m Ω k t = P f i j : f i j k f i j n k 1 C f i j : f i j k , k r l Ω k t f i j n k 1 C , l 1 , , 2 x ̈ .
P ( k G k ( t ) )
= P c o n v k k P c o n v k e n d k ¯ ¯ = 1
+ P e n d k k P c o n v k e n d k ¯ ¯ = 1
+ P | S e n d k c o n v k | = 1 P e n d k c o n v k ¯ ¯ = 1
+ P | S e n d k c o n v k | = 1 P e n d k c o n v k ¯ ¯ = 1 .
= 3 2 π k n k + n k 5 3 .
P f i j k = P f i j : Δ U ¯ k f i j > Δ U ¯ k f i j , k K t   &   L B T h r e s h U ¯ k f i j U B T h r e s h  and  N i , N j k + P f i j : k + P f i j : k + P f i j : k + P f i j : U ¯ k f i j O R , k K t , k : w k : p a t h N i N j ¯ ¯ = 1 + P f i j : k .
P k k = P p b i d i j k t > a p b i d k t P U ¯ k f i j + U ¯ k f i j > U ¯ k + U ¯ k P v P v , i < v P v , i P U ¯ k f i j < U B T h r e s h . 1 2 π k 2 .
= P max B i j k t B max , σ i j k t σ i j k t + ψ i j k t > f i j k max B i j k t B max , σ i j k t σ i j k t + ψ i j k t | f i j : f i j k | . v > 0 x , y , z x , k f i j H y , k f i j H z , k H x + y z v , k P v P v , i < v P v , i . y = 0 U B T h r e s h H y , k f i j . π k 2 2 ,
P f i j = P f i j k P U ¯ k < L B T h r e s h
P t l i v e k > T T L + P f i j k P U ¯ k > U B T h r e s h
+ P t H P + T S > ψ i k t P ψ i k t > t H P
+ P 1 B max t H P + T S C < B i k t B max
P B i k t B max < 1 B max t H P C .
P f i j = P k S I D + P k D I D + P U ¯ k f i j < L B T h r e s h .
P k K t = P S I D k + P D I D k + P k + P k .
M t i , j = C r e a t ,  if  k  has been created in the  j th  slot D e s t ,  if  k  has been destroyed in the  j th  slot ϑ ,  if  k  has been destroyed in some previous  slot and has not been created till the  j th  slot Λ ,  if  k  has been created in some previous  slot and has not been destroyed till the  j th  slot.
P r m a M t = P k , if  r m a M t = C r e a t P k ,  if  r m a M t = D e s t 1 P k , if  r m a M t = ϑ 1 P k ,  if  r m a M t = Λ .
P r m M t = a = 1 t P r m a M t .
P k K t = m = 1 2 t P r m M t .
P k 1 , k 2 , , k k ¯ K t = i = 1 k ¯ P k i K t .
P | K t | = k ¯ = k 1 , k 2 , , k k ¯ ε k 1 , k 2 , , k k ¯ K t ,
P t l i v e k > T T L = 1 P t l i v e k T T L = 1 t = 1 T T L P t l i v e k = t = 1 t = 1 T T L P LT  k  is destroyed in  t + 1 th  time-slot .