Specifically, VRR essentially transforms each single leafset entry in conventional DHT's routing table into a series of network-layer routing entries (along the virtual path from endpoint to endpoint). As such, the network layer could support key-based routing; by a greedy routing approach, VRR can quickly resolve the key-to-peerID mapping (rather than a series of virtual hops as in conventional DHT) and then follow a single virtual hop to the destination. While VRR focuses on generic layer-3 network, SEATTLE is based on the Ethernet where a Link-State protocol is assumed to exist underlyingly. SEATTLE can support one-hop DHT functionality in the switch-level network, because the key-to-peerID can be resolved locally due to the globally known Link-State map. The host-level routing info. is "indexed" by the MAC and the IP in the switch-level DHT. Thus, I am prone to think that SEATTLE use the DHT more as a kind of storage/index mechanism than as a routing infrastructure (after all, the routing simply follows the shortest path bestowed by the link-state protocol). The ROFL is an ambitious paper, which radically builds an Internet equivalency from scratch and aims at supporting scalable routing on semantic-free and thus flat identifiers. Technically, the specific design of ROFL borrows heavily from that of DHTs; the intradomain ROFL is essentially a VRR, and the interdomain ROFL is orgainized in a hierarchy as in Canon DHT. The ROFL hierarchy is in accordance to the AS's provider-customer hierarchy, enabling policy-aware routing.
Overview
Recently, having read a series of Prof. Matt's SigComm papers, I found a common topic in his research that really arouses my interest, that is, how to borrow the idea of DHT in designing an Internet from scratch (on the network layer and application layer). The VRR and SEATTLE build DHTs on network layer of generic networks and of Ethernet, respectively. The ROFL paper focuses on support of DHT routing (ID-based routing) and how to do so to enable policy-based routing on the Internet (which is such an AS-based network). VRR essentially transforms a leafset entry in DHT's routing table into several network-level routing/forwarding entries (along the virtual path from endpoint to endpoint), and by this way, both support identifier-based routing and accelerates the discovery of the destination identifier (ie., the node id closest to the one requested by the route). Rather than using DHT as a routing infrastructure, SEATTLE is actually using DHT as a directory service (or kind of distributed storage mechanism to store/index per-host routing info.). The routing in SEATTLE follows the shortest path between switches, which is bestowed by the underlying link-state protocol (so it's called one-hop DHT, with the id-to-switch mapping broadcasted and resolved locally). The ROFL paper leverages the hierarchical overlay in Canon DHT and applies it in the Internet where there is an analogy of hierarchy (ie., the AS hierarchy).
Detailed Schemes
I believe a crux in designing a networked DHT is how to make finger table aware of the network layer connectivity/topology.
The VRR essentially materializes the DHT finger table in the network layer; on peer a, a finger entry pointed to peer b would now be materialized to a series of entries distributed in the nodes' forwarding table along the path from a to b. By this means, a node x in networked DHT can view several virtual nodes which are close in their identifier, and the virtual nodes whose path of their virtual neighbors run through this node. These virtual nodes collectively form a partial/local view of the global identifier space for node x (similar to DHT), which helps determines which entry to go for incoming messages. Yet, still in accordance with network layer, x only forwards the message to its direct physical neighbor. As for how to route based on identifier, it's done by a two-phase process. First, the message is forwarded greedily to discover the node whose virtual neighbor is exactly the destination. Then a virtual path (essentially, a one-hop on overlay) can reach the destination. (The SEATTLE differs from VRR in that the discovery phase is locally resolved, thus is one-hop DHT.)
By contrast, the SEATTLE takes advantage of underlying link-state protocol (which essentially makes every node know all other nodes, globally) and by this means, achieves the one-hop network DHT. Specifically, the broadcasted link-state map enables a global view for every participating node (here, every switch), so each node can resolve the consistence hashing locally. That is, for a given key k, the switch to which the requested key k is consistently hashed to, namely the switch with identifier rk the most close to H(k), can be locally known (since every switch, along with their identifier, and the hash function are known). Because rk actually corresponds to the switch's MAC_ID (i.e., the location for switcher), the lookup can be resolved by a single physical route.
Since SEATTLE is built over the packet-switch network using link-state protocol, I am also wondering if a DHT can be materialized over networks using other kinds of protocols, say distance-vector routing protocol?
References:
1. Mathew Caesar, et al. "Virtual Ring Routing: Network Routing Inspired by DHTs." SigComm'06
2. Changhoon Kim, et al. "Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Ethernet." SigComm'08
3. Matthew Caesar, et al. "ROFL: Routing on Flat Label." SigComm'06
没有评论:
发表评论