Article

Free access

Routing and admission control in general topology networks with Poisson arrivals

Authors:

Anil Kamath,

Omri Palmon,

Serge PlotkinAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 269 - 278

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

G.R. Ash. Use of trunk status map for real-time DNHR. in Proc. of ITC-I~, Torino, Italy, 1988.

Google Scholar

[2]

G.R, Ash, R.H. Cardwell, and R.P. Murray. Design and optimization of networks with dynamic routing. Bell Syst. Tech. J., 60:1787-1820, 1981.

Google Scholar

[3]

G.R. Ash, J.S. Chen, A.E. Frey, and B.D. Huang. Realtime network routing in an integrated network. In Proc. of ITC-13, Copenhagen, Denmark, 1991.

Google Scholar

[4]

G.R. Ash, A.H. Kafker, and K.R. Krishnana. Servicing and real-time control of networks with dynamic routing. Bell Syst. Tech. J., 60:1821-1845, 1981.

Google Scholar

[5]

J. Aspnes, Y. Azax, A. Fiat, S. Plotkin, and O. Waarts. On-line machine scheduling with applications toload balancing and virtual circuit routing. In Proc. 25th Annual A CM Symposium on Theory of Computing, pages 623-631, May 1993.

Digital Library

Google Scholar

[6]

B. A werbuch, Y. Azar, and S. Plotkin. Throughput competitive on-line routing. In Proc. 3Jth IEEE Annual Symposium on Foundations of Computer Science, pages 32-40, November 1993.

Google Scholar

[7]

B. Awerbuch, Y. Azar, S. Plotkin, and O. Waarts. Competitive routing of virtual circuits with unknown duration. In Proc. 5th A CM-SIAM Symposium on Discrete Algorithms, pages 321-327, January 1994.

Digital Library

Google Scholar

[8]

B. A werbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high-performance computing and communication. In Proc. 35th IEEE Annual Symposium on Foundations of Computer Science, pages 412-423, November 1994.

Google Scholar

[9]

Y. Azar, A. Broder, and A. Karlin. On-line load balancing. In Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science, pages 218-225, 1992.

Google Scholar

[10]

Y. Azar, B. Kalyanasundaram, S. Plotkin, K. Pruhs, and O. Waarts. On-line load balancing of temporary tasks. In Proc. Workshop on Algorithms and Data Structures, pages 119-130, August 1993.

Digital Library

Google Scholar

[11]

A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. J. A CM, (39):745- 763, 1992.

Digital Library

Google Scholar

[12]

J. Garay, I. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. In Proc. o} 2nd Annual Israel Conference on Theory o} Computing and Systems, 1993.

Google Scholar

[13]

J.A. Garay and I.S. Gopal. Call preemption in communication networks. In Proc. INFOCOM '92, volume 44, pages 1043-1050, Florence, Italy, 1992.

Digital Library

Google Scholar

[14]

R. Gawlick, A. Kamath, S. Plotkin, and K. Ramakrishnan. Routing of virtual circuits with unknown holding times. Unpublished manuscript, 1994.

Google Scholar

[15]

R. Gawlick, A. Kamath, S. Plotkin, and K. Ramakrishnan. Routing and admission control in general topology networks. Technical Report STAN-CS-TR-95-1548, Stanford University, 1995.

Digital Library

Google Scholar

[16]

R.J. Gibbens and F. P. Kelly. Dynamic routing in fully connected networks. IMA J. Math. Contr. InJorm., 7:77-111, 1990.

Google Scholar

[17]

D. Karger and S. Plotkin. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proc. ~Tth Annual A CM Symposium on Theory of Computing, pages 18-25, May 1995.

Digital Library

Google Scholar

[18]

A.R. Karlin, M.S. Manasse, L.Rudolph, and D.D. Sleator. Competitive snoopy caching. Algorithmica, 1(3):70-119, 1988.

Google Scholar

[19]

F. P. Kelly. Blocking probabilities in large circuitswitched networks. Adv. Appl. Prob., 18:473-505, 1986.

Google Scholar

[20]

P. Klein, S. Plotkin, C. Stein, and 1~. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to rouging and finding sparse cuts. SIAM Journal on Computing, 23(3):466- 487, June 1994.

Digital Library

Google Scholar

[21]

J. Kleinberg and 15,. Tardos. Disjoint path in densely embedded graphs. In Proc. 36th IEEE Annual Symposium on Foundations of Computer Science, 1995.

Digital Library

Google Scholar

[22]

K.R. Krishnan and T.J. Ott. Forward-looking routing: A new state-dependent routing scheme. In Proe. of ITC-I~, Torino, Italy, 1988.

Google Scholar

[23]

T. Leighton, F. Makedon, S. Plotkin, C. Stein, 15. Tardos, and S. Tragoudas. Fast approximation algorithms for multicommodity flow problems, or. Comp. and Syst. Sci., 50:228-243, 1995.

Digital Library

Google Scholar

[24]

Y. Ma and S. Plotkin. Improved lower bounds for load balancing of tasks with unknown duration. Unpublished manuscript, 1995.

Google Scholar

[25]

M.S. Manasse, L.A. McGeoch, and D.D. Sleator. Competitive algorithms for online problems. In Proc. 2Oth Annual A CM Symposium on Theory of Computing, pages 322-332, 1988.

Digital Library

Google Scholar

[26]

V. Marbukh. An asymptotic study of a large fully connected communication network with reroutes. Prob. lemy Peredachi {n}ormatsii, 3:89-95, 1981.

Google Scholar

[27]

V. Marbukh. Study of a fully connected communication network with many nodes and circumventing routes. Automatics i Telemechanica, 12:86-94, 1983.

Google Scholar

[28]

D. Mitra, R.J. Gibbens, and B.D. Huang. Statedependent routing on symmetric loss networks with trunk reservations - I. Annals o} Operations Research, (as):a-30, m92.

Digital Library

Google Scholar

[29]

D. Mitra, R.J. Gibbens, and B.D. Huang. Statedependent routing on symmetric loss networks with trunk reservations- II. IEEE Trans. on Communications, 41(2), February 1993.

Google Scholar

[30]

T.J. Ott and K.R. Krishnan. State-dependent routing of telephone traffic and the use of separable routing schemes. In Proc. o} ITC-11, Kyoto, Japan, 1985.

Google Scholar

[31]

S. Plotkin. Competitive routing in ATM networks. IEEE J. Selected Areas in Comm., pages 1128-1136, August 1995. Special issue on Advances in the Fundamentals of Networking.

Digital Library

Google Scholar

[32]

S. Plotkin, D. Shmoys, and t~. Tardos. Fast approximation algorithms for fractional packing and covering problems. In Proc. 3~nd IEEE Annual Symposium on Foundations of Computer Science, pages 495-504, October 1991.

Digital Library

Google Scholar

[33]

F. Shahrokhi and D. Matula. The maximum concurrent flow problem. J. Assoc. Comput. Mach., 37:318-334, 1990.

Digital Library

Google Scholar

[34]

S. Sibal and A. DeSimone. Controlling alternate routing in general-mesh packet flow networks. Technical Report BL045370F-940603-01TM, AT&T, June 1994.

Google Scholar

[35]

D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Comm. A CM, 28(2):202- 208, 1985.

Digital Library

Google Scholar

[36]

N. Young. Randomized rounding without solving the linear program. In Proc. 6th A CM-SIAM Symposium on Discrete Algorithms, pages 170-178, 1995.

Digital Library

Google Scholar

Cited By

View all

Devanur NJain KSivan BWilkens C(2019)Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation ProblemsJournal of the ACM10.1145/328417766:1(1-41)Online publication date: 9-Jan-2019
https://dl.acm.org/doi/10.1145/3284177
Jalaparti VBallani HCosta PKaragiannis TRowstron ACarey MHand S(2012)Bridging the tenant-provider gap in cloud servicesProceedings of the Third ACM Symposium on Cloud Computing10.1145/2391229.2391239(1-14)Online publication date: 14-Oct-2012
https://dl.acm.org/doi/10.1145/2391229.2391239
Devanur NJain KSivan BWilkens CShoham YChen YRoughgarden T(2011)Near optimal online algorithms and fast approximation algorithms for resource allocation problemsProceedings of the 12th ACM conference on Electronic commerce10.1145/1993574.1993581(29-38)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.1145/1993574.1993581
Show More Cited By

Index Terms

Routing and admission control in general topology networks with Poisson arrivals

Recommendations

Routing and Admission Control in General Topology Networks with Poisson Arrivals

Emerging high-speed networks will carry traffic for services such as video-on-demand and video teleconferencing that require resource reservation along the path on which the traffic is sent. High bandwidth-delay product of these networks prevents ...
Routing and Admission Control in General Topology Networks with Poisson Arrivals
Priority queues with batch Poisson arrivals

This paper studies batch arrival M^X/G/1 priority queues without and with (multiple or single) vacations. Applying the delay busy cycle analysis, we explicity derive the Laplace-Stieltjes transforms and the first two moments of the waiting time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)9

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Devanur NJain KSivan BWilkens C(2019)Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation ProblemsJournal of the ACM10.1145/328417766:1(1-41)Online publication date: 9-Jan-2019
https://dl.acm.org/doi/10.1145/3284177
Jalaparti VBallani HCosta PKaragiannis TRowstron ACarey MHand S(2012)Bridging the tenant-provider gap in cloud servicesProceedings of the Third ACM Symposium on Cloud Computing10.1145/2391229.2391239(1-14)Online publication date: 14-Oct-2012
https://dl.acm.org/doi/10.1145/2391229.2391239
Devanur NJain KSivan BWilkens CShoham YChen YRoughgarden T(2011)Near optimal online algorithms and fast approximation algorithms for resource allocation problemsProceedings of the 12th ACM conference on Electronic commerce10.1145/1993574.1993581(29-38)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.1145/1993574.1993581
Zarifzadeh SYazdani N(2008)Joint resource conserving and load distributing approaches for routing of survivable connectionsComputer Communications10.1016/j.comcom.2008.05.02731:14(3384-3393)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1016/j.comcom.2008.05.027
Kowalik KCollier M(2006)Reducing traffic fluctuations of link state QoS routing algorithms in virtual circuit networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2005.03.00550:15(2805-2819)Online publication date: 18-Oct-2006
https://dl.acm.org/doi/10.1016/j.comnet.2005.03.005
Aiello WOstrovsky RKushilevitz ERosén A(2003)Dynamic routing on networks with fixed-size buffersProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644236(771-780)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644236
Goel AMeyerson APlotkin SYao FLuks E(2000)Combining fairness with throughputProceedings of the thirty-second annual ACM symposium on Theory of computing10.1145/335305.335400(670-679)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/335305.335400
Goel AHenzinger MPlotkin SKarloff H(1998)Online througput-competitive algorithm for multicast routing and admission controlProceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms10.5555/314613.314685(97-106)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.5555/314613.314685
Aiello WKushilevitz EOstrovsky RRosén AVitter J(1998)Adaptive packet routing for bursty adversarial trafficProceedings of the thirtieth annual ACM symposium on Theory of computing10.1145/276698.276788(359-368)Online publication date: 23-May-1998
https://dl.acm.org/doi/10.1145/276698.276788
Kahale NWright P(1997)Dynamic Global Packet Routing in Wireless NetworksProceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution10.5555/839292.843012Online publication date: 9-Apr-1997
https://dl.acm.org/doi/10.5555/839292.843012
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Routing and Admission Control in General Topology Networks with Poisson Arrivals

Routing and Admission Control in General Topology Networks with Poisson Arrivals

Priority queues with batch Poisson arrivals