Abstract
Path Layout is a fundamental graph problem in label switching protocols. This problem is raised in various protocols such as the traditional ATM protocol and MPLS which is a new label switching protocol standardized recently by the IETF. Path layout is essentially the problem of reducing the size of the label-table in a router. The size is equivalent to the number of different paths that pass through the router, or start from it. A reduction in the size can be achieved by choosing a relatively small number of paths, from which a larger set is composed using concatenation.
In this paper we deal with three variations of the Path Layout Problem according to the special characteristics of paths in three label switching protocols, MPLS, ATM and TRAINET. We focus on tree networks and show an algorithm which finds label-tables of small size while permitting concatenation of at most k paths. We prove that this algorithm gives worst case tight bounds (up to constant factor) for all three models. The bounds are given as a function of the size of the tree, and the maximum degree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Bremler-Barr, A.: Trainet: A new label switching scheme. In: Proc. of The Conference on Computer Communications, INFOCOM 2000, pp. 874–883 (2000)
Ahn, S., Tsang, R.P., Tong, S.-R., Du, D.H.-C.: Virtual path layout design on ATM networks. In: Proc. of The Conference on Computer Communications, INFOCOM 1994, pp. 192–200 (1994)
Awduche, D.O., Rekhter, Y.: Multi-protocol lambda switching: Combining MPLS traffic engineering control with optical crossconnects. IEEE Comm. Mag. 39(3), 111–116 (2001)
Bermond, J.-C., Marlin, N., Peleg, D., Perennes, S.: Directed virtual path layouts in atm networks. Theor. Comput. Sci. 291(1), 3–28 (2003)
Callon, R., Doolan, P., Feldman, N., Fredette, A., Swallow, G.: A framework for multiprotocol label switching (1997) (manuscript)
Chandranmenon, G., Varghese, G.: Trading packet headers for packet processing. IEEE Transactions on Networking 4(2), 141–152 (1996)
Davie, B., Doolan, P., Rekhter, Y.: Switching in IP Networks. Morgan Kaufmann Publishers Inc., San Francisco (1998)
Eilam, T., Flammini, M., Zaks, S.: A complete characterization of the path layout construction problem for ATM networks with given hop count and load. Parallel Processing Letters 8(2), 207–220 (1998)
Gerstel, O., Cidon, I., Zaks, S.: The layout of virtual paths in ATM networks. Transactions on Networking 4(6), 873–884 (1996)
Gerstel, O., Cidon, I., Zaks, S.: Optimal virtual path layout in ATM networks with shared routing table switches. The Chicago Journal of Theoretical Computer Science 3 (December 1996)
Gerstel, O., Wool, A., Zaks, S.: Optimal layouts on a chain ATM network. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 83 (1998)
Gerstel, O., Zaks, S.: The virtual path layout problem in ATM ring and mesh networks. In: Proc. of the First Conf. on Structure, Information and Communication Complexity, SIROCCO 1994 (1994)
Gerstel, O., Zaks, S.: The virtual path layout problem in fast networks. In: Symposium on Principles of Distributed Computing (PODC 1994), pp. 235–243 (1994)
Handler, R., Huber, M.N.: Integrated Broadband Networks:an introduction to ATM-based networks. Addison-Wesley, Reading (1991)
Katsube, Y., Nagami, K., Esaki, H.: Toshiba’s router architecture extensions for atm: Overview. rfc 2098. Technical report (1997)
Maxemchuk, N.F.: Routing in the manhattan street network. Transactions on Communications 5, 503–512 (1987)
Newman, P., Minshall, G., Huston, L.: Ip switching and gigabit routers. IEEE Communications Magazine 35(1), 64–69 (1997)
Rekhter, Y., Davie, B., Katz, D., Rosen, E., Swallow, G., Farinacci, D.: Tag switching architecture overview (1996) (manuscript)
Stacho, L., Vrťo, I.: Virtual path layouts in ATM networks. SIAM Journal on Computing 29(5), 1621–1629 (2000)
Vakhutinsky, A., Ball, M.: Fault-tolerant virtual path layout in atm networks. In: Proceedings of the 15th International Teletraffic Conference (ITC 15), pp. 1031–1041 (1997)
Zaks, S.: Path layout in ATM networks. In: Jeffery, K. (ed.) SOFSEM 1997. LNCS, vol. 1338, pp. 144–160. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bremler-Barr, A., Epstein, L. (2004). Path Layout on Tree Networks: Bounds in Different Label Switching Models. In: Královic̆, R., Sýkora, O. (eds) Structural Information and Communication Complexity. SIROCCO 2004. Lecture Notes in Computer Science, vol 3104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27796-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-27796-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22230-9
Online ISBN: 978-3-540-27796-5
eBook Packages: Springer Book Archive