Virtual network embedding through topology-aware node ranking
The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Abstract
Virtualizing and sharing networked resources have become a growing trend that reshapes the computing and networking architectures. Embedding multiple virtual networks (VNs) on a shared substrate is a challenging problem on cloud computing platforms and large-scale sliceable network testbeds. In this paper we apply the Markov Random Walk (RW) model to rank a network node based on its resource and topological attributes. This novel topology-aware node ranking measure reflects the relative importance of the node. Using node ranking we devise two VN embedding algorithms. The first algorithm maps virtual nodes to substrate nodes according to their ranks, then embeds the virtual links between the mapped nodes by finding shortest paths with unsplittable paths and solving the multi-commodity flow problem with splittable paths. The second algorithm is a backtracking VN embedding algorithm based on breadth-first search, which embeds the virtual nodes and links during the same stage using node ranks. Extensive simulation experiments show that the topology-aware node rank is a better resource measure and the proposed RW-based algorithms increase the long-term average revenue and acceptance ratio compared to the existing embedding algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1999) · Cited by 12,854
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034
Kenny, A. (2018) · Carl Strehlow’s 1909 Comparative Heritage Dictionary: An Aranda, German, Loritja and Dieri to English Dictionary with Introductory Essays · doi:10.22459/cschd.08.2018.04 · Cited by 3,216
Non-negative Matrices and Markov Chains
Seneta, E. (1981) · Springer Series in Statistics · doi:10.1007/0-387-32792-4 · Cited by 2,807
Rethinking virtual network embedding: substrate support for path splitting and migration
Yu, M., Yi, Y., Rexford, J., & Chiang, M. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1355734.1355737 · Cited by 1,244
Network virtualization: state of the art and research challenges
Chowdhury, N. M. M. K., & Boutaba, R. (2009) · IEEE Communications Magazine · doi:10.1109/mcom.2009.5183468 · Cited by 838
Virtual Network Embedding with Coordinated Node and Link Mapping
Chowdhury, N. M. M. K., Rahman, M. R., & Boutaba, R. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5061987 · Cited by 823
Algorithms for Assigning Substrate Network Resources to Virtual Network Components
Zhu, Y., & Ammar, M. (2006) · Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications · doi:10.1109/infocom.2006.322 · Cited by 779
How to lease the internet in your spare time
Feamster, N., Gao, L., & Rexford, J. (2007) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1198255.1198265 · Cited by 540
Bianchini, M., Gori, M., & Scarselli, F. (2005) · ACM Transactions on Internet Technology · doi:10.1145/1052934.1052938 · Cited by 539 · cited 1×
“, Algorithm 1) has been shown to yield any desired precision with a number of iterations proportional to max{1,−log } [6].”
BackgroundAn Improved Algorithm for Matching Large Graphs
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2001) · Cited by 477
Eppstein, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365697 · Cited by 349
Turner, J. S., & Taylor, D. E. (2005) · GLOBECOM '05. IEEE Global Telecommunications Conference, 2005. · doi:10.1109/glocom.2005.1577741 · Cited by 316
A Distributed Virtual Network Mapping Algorithm
Houidi, I., Louati, W., & Zeghlache, D. (2008) · 2008 IEEE International Conference on Communications · doi:10.1109/icc.2008.1056 · Cited by 282
Theoretical Approaches to Node Assignment
Andersen, D. G. (2018) · Figshare · doi:10.1184/r1/6610829 · Cited by 278
GENI - global environment for network innovations
Elliott, C. (2008) · 2008 33rd IEEE Conference on Local Computer Networks (LCN) · doi:10.1109/lcn.2008.4664143 · Cited by 278
Efficient Mapping of Virtual Networks onto a Shared Substrate
Lu, J. (2006) · doi:10.7936/k78w3bj4 · Cited by 265
Topology-Awareness and Reoptimization Mechanism for Virtual Network Embedding
Farooq Butt, N., Chowdhury, M., & Boutaba, R. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-12963-6_3 · Cited by 171
Exact and approximate graph matching using random walks
Gori, M., Maggini, M., & Sarti, L. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.138 · Cited by 160
A unified probabilistic framework for web page scoring systems
Diligenti, M., Gori, M., & Maggini, M. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.1264818 · Cited by 68
3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition
Jolion, J.-M., Kropatsch, W. G., & Vento, M. (2001) · Cited by 36
Cited by
Virtual Network Embedding: A Survey
Fischer, A., Botero, J. F., Beck, M. T., de Meer, H., & Hesselbach, X. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2013.013013.00155 · Cited by 1,244
Yan, Z., Ge, J., Wu, Y., Li, L., & Li, T. (2020) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.2986662 · Cited by 258
Metadata
- Authors
- Cheng, X., Su, S., Zhang, Z., Wang, H., Yang, F., Luo, Y., & Wang, J.
- Venue
- ACM SIGCOMM Computer Communication Review
- Published
- 2011-04-15
- Volume
- 41
- Issue
- 2
- Pages
- 38-47
- ISSN
- 0146-4833 (ISSN-L)
- OpenAlex
- W2130267070
- Cited by
- 544
- References
- 21
- FWCI
- 48.94
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.