Networking Research Laboratory
Director: Simon S. Lam (more publications)
Chen Qian and Simon S. Lam, ``A Scalable and Resilient Layer-2 Network with Ethernet Compatibility,'' IEEE/ACM Transactions on Networking, Feb. 2016, Vol. 24, No. 1, pages 231-244 (first published as IEEE Early Access Article, 2014, Digital Object Identifier: 10.1109/TNET.2014.2361773).
Abstract: We present the architecture and protocols of ROME, a layer-2 network designed to be backwards-compatible with Ethernet and scalable to tens of thousands of switches and millions of end-hosts. Such large-scale networks are needed for emerging applications including data center networks, wide area networks, and metro Ethernet. ROME is based upon a recently developed greedy routing protocol, greedy distance vector (GDV). Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay distributed hash table (DHT), as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast and provide both control-plane and data-plane scalability. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25 000 switches and 1.25 million hosts.
Protocols of ROME makes use of protocols developed in the following two papers. A good introduction to most of the key ideas in these papers is presented in the following lecture:
Simon S. Lam and Chen Qian, ``Geographic Routing in d-dimensional Spaces with Guaranteed Delivery and Low Stretch,'' IEEE/ACM Transactions on Networking, April 2013, Vol. 21, No. 2, pages 663-677 (first published as IEEE Early Access Article, 2012, Digital Object Identifier: 10.1109/TNET.2012.2214056).
Abstract: Almost all geographic routing protocols have been designed for 2-D.
We present a novel geographic routing protocol, named Multihop Delaunay
Triangulation (MDT), for 2-D, 3-D, and higher dimensions with these properties:
1) guaranteed delivery for any connected graph of nodes and physical links, and
2) low routing stretch from efficient forwarding of packets out of local minima.
The guaranteed delivery property holds for node locations specified by accurate,
inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet
forwarding protocol together with protocols for nodes to construct and maintain
a distributed MDT for routing. We present the performance of MDT protocols in
3-D and 4-D as well as performance comparisons of MDT routing versus
representative geographic routing protocols for nodes in 2-D and 3-D.
Experimental results show that MDT provides the lowest routing stretch in the
comparisons. Furthermore, MDT protocols are specially designed to handle churn,
i.e., dynamic topology changes due to addition and deletion of nodes and links.
Experimental results show that MDT’s routing success rate is close to 100%
during churn, and node states converge quickly to a correct MDT after churn.
Chen Qian and Simon S. Lam, ``Greedy Routing by Network Distance Embedding,'' IEEE/ACM Transactions on Networking, 2016, Volume 24, Issue 4, pages 2100 -2113 (first published as IEEE Early Access Article, 2015, Digital Object Identifier: 10.1109/TNET.2015.2449762).
Abstract: Greedy routing has been applied to both wireline and wireless networks due to its scalability of routing state and resiliency to network dynamics. In this work, we solve a fundamental problem in applying greedy routing to networks with arbitrary topologies, i.e., how to construct node coordinates such that greedy routing can find near-optimal routing paths for various routing metrics. We propose Greedy Distance Vector (GDV), the first greedy routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no physical location information. Instead, it relies on a novel virtual positioning protocol, VPoD, which provides network distance embedding. Using VPoD, each node assigns itself a position in a virtual space such that the Euclidean distance between any two nodes in the virtual space is a good estimate of the routing cost between them. Experimental results using both real and synthetic network topologies show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a greedy routing protocol, the routing state of GDV per node remains small as network size increases. We also show that GDV and VPoD are highly resilient to dynamic topology changes.