This is a prototype routing application which demonstrates a GNS (Global Name Service) based approach to Mobility First routing. The application can be run using JAVA Webstart (button below) or downloaded using the link that follows and run on a unix or OSX environment.
Download link: http://westy.org/mf/downloads/MobilityFirst-2013-05-20.zip
Java Webstart:
A detailed description of the capabilites and design of the prototype is below.
Things you can do in the application interface include:
Some of the above commands are also available by right clicking on objects in the interface. You can also right click on empty space to bring up these options:
Clear Packet Trails - The interface animates packets moving around the network. This clears those animations from the screen so you can add watch new ones.
Slow It Down / Speed It Up - Make the packet animations run more slowly so you can see what's going on (or not).
Use EC2 GNS - The demo has two options for handling GNS Queries 1) send them to a simulated GNS server running on the local host 2) send them to an actual distributed GNS server running on Amazon EC2 hosted servers around the world. If option is not available option 1 will automatically work. Option 2 is more prone to issues and is much slower. Use at your own risk when demoing.
Clear All Path Tables - Discards all the path information stored at each router (but not the forwarding tables). This is useful in conjunction with the next item:
Rerun All Routing Protocols - If you clear all the path tables and then select this item, you'll see all the packets that are sent around by the various routing protocols.
The colored arcs that appear in parallel to connections between nodes denote traffic generated when you take some action and are color coded by packet type. There is a key in the upper left.
The scrollable tables in the panes on the right hand side of the screen show the contents of the GNS, and when you select a router you will see its forwarding table, path table (more on this below), and the DHT (SEATTLE-like - see below)
You can scroll through the GNS table at the upper right and see the changes being made to reflect the devices and groups you are moving around.
GNS requests are also being sent to a name server (either local (the default) or remote depending on which is chosen) which sends back the appropriate responses.
If the interface hangs the best thing to do is quit and restart. Note: If you have Slow It Down on you might have to wait a bit for things to happen, but it will eventually finish (although it's better about this than previous versions).
This prototype routing application consists of Core networks and Edge networks. Networks have one or more routers. Devices are connected to routers.
Routers forward packets to and from devices.
We emulate interfaces in routers using an IP address and a port - we call a DeviceLocation in the code. Forward a packet involves sending looking up a DeviceLocation
and opening a socket
Packets are encoded as JSON objects and sent between routers and devices using a TCP/IP socket connection.
Some assumptions first: Routers are grouped together to form (associated with) particular networks. A router will know what core or edge network it is in.
We assume some kind of mechanism for specifying and/or discovering the basic network topology - that is what routers are adjacent to what other routers.Through this discovery mechanism a router adds entries in the forwarding table for all the adjacent routers.
Link state routing using sequence-number-controlled broadcast is used inside both core and edge networks to discover the topology inside the network and fill out the forwarding tables.
For routing from edge networks up to core networks and back down a path beacon protocol loosely based on concepts described in SCION[1] is used. Using this we can find the shortest paths and hops up to all the core networks from a edge network and back down, filling in forwarding tables (and DHTs in some cases - see below) as the packets traverse the network. As packets traverse the networks we add entries in our path tables for all paths between routers and networks. Forwarding tables are kept updated with the shortest paths between routers and networks.
Two mechanisms are used at a router to forward packets.
The first is a standard forwarding table with the keys being routers or GUIDs naming devices or networks. The values in the table are the outgoing interface. Note: our network overlay uses hostname / port pairs to stand in as interfaces.
The second mechanism for forwarding packets is a network wide DHT similar to that used in SEATTLE[2]. Each router in the network maintains part of what is essentially a logically centralized network-wide forwarding table. If a router does not have a standard forwarding entry for the given destination a hashed lookup is done using the DHT. The value of this lookup is the name of a router in the local network where the forwarding entry is stored. Destinations in this case can be GUIDs, edge networks (in the case where the router is in a core network), or the local GNS server or any other service that we want to be reachable from this network. The packet we are trying to forward is then encapsulated in a tunneling packet which is forwarded to the storage router (the one we looked up in the DHT above). When the encapsulated packet reaches the storage router it is unencapsulated and forwarded using the standard forwarding mechanism. A packet containing the forwarding entry is also sent back to the original router (the one that didn't have a forwarding entry) and is used to update the forwarding table so that future packets can avoid the DHT lookup and tunneling and go more directly to the destination.
Each router implements and participates in up to 5 different routing protocols. 1) A content protocol which is the default protocol used to move data packets around. 2) A link state protocol which is used to
determine the topology and routing within a given edge or core network. 3) A path beacon protocol which provides reachability and routing between edge networks and the core networks "above" them. 4) A DHT management protocol which maintains a DHT amongst all the routers in a network providing a logical centralized forwarding table for the whole network. 5) An inter network routing protocol to provide routing and reachability between core networks (this one is not implemented yet).
Note: Still to be done is some support for "peer" routing in and between edge networks if we want this. Currently all trips are up to a core network and back down.
Each router maintains a list of all the paths to all other reachable router and networks with the length,next hop and routing protocol that created the path. This information is used to maintain the router's forwarding tables.
The DHT managementprotocol uses the topology information provided by the link state protocol to configure the hash function and fill out the forwarding information at each DHT node (router). Information gathered by the path beacon protocol is used to update the contents of the DHT - in particular the forwarding entries in core networks of downstream edge networks. The content protocol uses the tunneling provide by the DHT management protocol to shuttle packets inside core and edge networks. The content protocol, obviously, uses the information from all the other protocols to forward packets.
A Group GUID (GGUID) can be used as the destination of a packet. This could be used for multi-cast, anycast, or geocast, (which are all MGUIDs) or content retrieval (which is a CGUID).
A initial lookup of the particular GGUID in the GNS would return one or more NAs depending on the particular use. The packet would be sent to the NA(s) using the usual
mechanisms plus some sort of replication in the case of multiple NAs.
The second use case for an Affinity GUID (AGUID) which feels similar to an edge network without dedicated routers. This is where a GGUID is used for indirection. Someone wants to send something to a particular GUID that happens to be part of a AGUID. A initial lookup in the GNS of a particular GUID would find the AGUID that the GUID was part of. This would result in a two-step lookup the second part of which would use the
AGUID and would result in one or more NAs being returned. We would send the packet using the normal mechanism which in the case of multiple NAs might involve some policy being used to
determine which edge and core networks to use to send the packet.
Affinity GUIDs override the GUID -> EDGE entry in the GNS meaning once a GUID is in a AGUID you cannot access it through the edge networks it resided in before
joining the AGUID. Which means there is no multi-homing between the edge that the AGUID is pointing to and the non-AGUID edge networks that the GUID
was previously in. Otherwise we would have to update the GUID -> EDGE every time we moved the GUID which defeats the purpose of the AGUID.
If a AGUID is deleted the old GUID -> EDGE entries for the GUID are cleared from the GNS because they are obsolete and a new
GUID -> EDGE is added for each edge network the GUID is currently in. We could just delete them when the AGUID is created,
but we pick the lazy, upfront cheaper way and incur the cost when the AGUID goes away.
Multicast GUID - implemented only for AGUIDs currently
Content Group GUID - Not yet Implemented
1. SCION: Scalability, Control, and Isolation on Next-Generation Networks by Prof. A. Perrig, Carnegie Mellon University
2. Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises, C. Kim, M. Caesar, J. Rexford