Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/20767
Title: Efficient Two Dimensional-IP routing : an incremental deployment design
Authors: Xu, M
Yang, S
Wang, D 
Wu, J
Keywords: High dimensional routing
Incremental deployment
Routing deployment
Issue Date: 2014
Publisher: Elsevier
Source: Computer networks, 2014, v. 59, p. 227-243 How to cite?
Journal: Computer networks 
Abstract: High dimensional routing has attracted more attentions to satisfy the increasing demands for more flexible services in the Internet. These routing schemes make routing decisions not only based on the destination address, but also on the source address, flow label, etc. With these schemes, networks can provide more than best-effort services. There are several research issues towards high dimensional routing. Clearly routers face additional CPU and memory burden in looking up and maintaining the additional information. While some overheads are unavoidable, we need to minimize such burden incurred. A more important problem is the deployment. It is widely known that making changes to the network layer is notoriously difficult. The proposed scheme should have least impact on the current Internet protocols and infrastructure. A node-by-node incremental deployment scheme is highly preferred. Obviously, without full deployment, the resulting paths for traffic diversion may deviate from the pre-defined ones. The incremental deployment scheme should minimize such deviation. In this paper, we illustrate the problem by using a real example from China Education and Research Network 2 (CERNET2). Then we formulate it as finding a deployment sequence where the traffic flows should follow the pre-defined paths given (1) the number of nodes to be deployed and (2) the extra burden each router can spare. We transform our problem to boolean clauses and develop efficient solutions following the Maximum Satisfiability (MAX-SAT) problem. We present several related algorithms for different practical scenarios. We evaluate our algorithms using comprehensive simulations with BRITE generated topologies and real world topologies. We conduct a case study on CERNET2 configurations. Compared to an ad hoc deployment and an arbitrary TwoD-IP forwarding, our algorithms compute a deployment sequence that achieves close to optimal performance after deploying a few nodes. The CPU and memory requirement are small for packet forwarding.
URI: http://hdl.handle.net/10397/20767
ISSN: 1389-1286
DOI: 10.1016/j.bjp.2013.11.004
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

1
Last Week
0
Last month
0
Citations as of Aug 19, 2017

Page view(s)

37
Last Week
2
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.