Protocol Specifications: MobilityFirst Future Internet Architecture

December 14, 2010, WINLAB, Rutgers University

Abstract

This document provides the protocol specifications for the system implementation of MobilityFirst, the Future Internet Architecture project.

Status of this Memo

Draft version 0.1. This Draft is for the review on December 21, 2010. Draft version 0.9. April 4, 2011

1. Introduction 2

1.2 Design Goals 2 1.3 Application Scenarios 3 1.4 System Architecture 3 1.4.1 Naming (name assignment) Service 5 1.4.2 Name Resolution Service 5 1.4.3 Hybrid Name/Address Routing 6 1.4.4 Disruption-tolerance network (DTN) transport 6 1.4.5 Open issues 7

2. Naming (name assignment) Services 7

2.1 Global Unique Identification (GUID) 8 2.2 GUID creation 9 2.3 GUID publishing and update 9 2.4 GUID lookup and context resolution 11 2.5 GUID for content 11 2.6 GUID for sensors 12 2.7 GUID for Context – Grouping 13 2.8 Example of context resolution procedure 14

3. Name Resolution Service (NRS) 15

3.1 Single-hop in-network hashing 15 3.2 IP hole effect 17 3.3 Network Dynamism BGP Churn 18

4. Hybrid Name/Address Routing 19

3.3 Challenges and Design Principles 19 3.4 GSTAR Routing 20 3.4.1 Global Scale 21 3.4.2 Local Scale 21 3.4.3 Use Cases 24 4 Disruption-tolerant network transport 25 5 Management Plane 25 5.3 Management API in each service 25 6 Security Considerations 25

1. Introduction

1.2 Design Goals

MobilityFirst proposal is founded on the premise that the Internet is approaching an historic inflection point, with mobile platforms and applications poised to replace the fixed-host/server model that has dominated the Internet since its inception. This predictable, yet fundamental, shift presents a unique opportunity to design a next generation Internet in which mobile devices, and applications, and the consequent changes in service, trustworthiness, and management are primary drivers of a new architecture. The major design goals of our proposed architecture are:

Mobility as the norm with dynamic host and network mobility at scale; Robustness with respect to intrinsic properties of the wireless medium; Trustworthiness in the form of enhanced security and privacy for both mobile networks and wired infrastructure; Usability features such as support for context-aware pervasive mobile services, evolvable network services, manageability and economic viability. The design is also informed by technology factors such as radio spectrum scarcity, wired bandwidth abundance, continuing Moore’s law improvements to computing, and energy constraints in mobile and sensor devices.

1.3 Application Scenarios

From network interface point of view, the future Internet serves mobile users through one of following ways: Multi-homing (AP-i1): Tom’s laptop has multiple network interfaces, e.g., WIFI and AT&T 3G. How can a caller to Tom’s laptop decide which network address to use and based on what metrics? (choice of networks) (Sam’s scenario-1) Macro mobility (AP-i2): Tom’s laptop connects to different networks at different time and locations. (conventional mobility) (Sam’s scenario-2) Network coding (AP-i3): Can a caller use multiple addresses, and therefore routes, simultaneously？ (reliability) (Akashi’s scenario) Mobile-to-mobile (AP-i4): Can Tom’s car be accessed without a global name resolution? (ad-hoc) (Sam’s scenario-5) Mobile Network (AP-i5): A sub-network (airplane, train) is mobile. (Ray’s original scenario) Mobile Gateway (AP-i6): Legacy mobile terminals, sensors and tags still use gateway (proxy) to access Internet. (Jun’s M2M scenario)

From content delivery point of view:

Content mobility (AP-d1): Tom request for a content hosted dynamically on different servers. Deliver to a location (AP-d2): Tom wants to send a message to all taxis on route-18 at New Brunswick. (location context) (Sam’s scenario-4) Deliver to a group (AP-d3): A message to be delivered to anyone of Tom’s family. (group context) (Sam’s scenario-6) Deliver by time (AP-d4): Tom wants to get file-X by 8AM tomorrow. (delay context)

Deliver at cost (AP-d5): Tom wants to get file-X at cost less than $5. (cost context)

1.4 System Architecture

To meet the design goals and support the application scenarios we promote, we envision the MobilityFirst architecture have following components, depicted in Figure. 1. Figure 1.1. MobilityFirst Future Internet Architecture

There are three layers above the core IP network. On the top layer, there are naming services that translate the “human readable” device names, content names, sensors and contexts of network resources into network recognizable IDs (GUID – global unique ID) as their network names. The second layer is a distributed fast name resolution service that resolve a GUID into network routable address(es). Whenever a GUID identified network resource moves, the name resolution service gets updated at sub-second time scale (50-100ms) and the network routers can response fast enough with new routing decisions. This is the core function of the MobilityFirst to ensure the “mobility as the norm” in future internet. The third layer is a disruption tolerant network transport that transfers data based on either name or address or both in case the end-to-end transport is dynamic or not available.

We will briefly introduce the basic architecture of these layers in this section and go through the design details one by one in later sections.

1.4.1 Naming (name assignment) Service

Our vision to the future Internet is capable to handle context-aware mobile services such as, “Send file-A to Jeo’s laptop”, “Get movie ‘Inception’ to Sue’s mobile phone”, “Send message-B to all cabs at New Brunswick traffic light on route-18”, “Temperature of Rutgers ECE department room C111”.

At the top level of the MobilityFirst architecture, we envision there are various types of naming services that could translate human readable“context” into network readable IDs (global unique identifications, GUIDs) plus a set of service parameters. As shown in Figure 1, network devices, content, sensors and location can all be mapped to GUIDs as network recognizable names. When a message is sending to Jeo, the sender needs first to find one of Jeo’s device’s GUID. Then send the message to the device identified by the GUID. When the “movie1” is distributed in the network, the GUID of movie1 must be published so that users can find where the movie1 are.

GUID serves as an identification of a network entity (device, content etc.). In addition, in MobilityFirst architecture, a GUID must achieve the goal of trustworthiness, that is, the core network can guarantee either side of communication parties’ real identities. The trustworthiness cannot be guaranteed by simply increasing addressing space like IPv6. One way to achieve the goal is to use a public key as part of GUID. The owner of GUID can use the corresponding private key to prove his/her ownership.

1.4.2 Name Resolution Service

To make the “mobility as the norm” possible in the future Internet architecture, the major challenge is to have a fast global name resolution service (NRS). Unlike the traditional domain name service (DNS) that requires hours even days to update a name entry, this GUID name resolution service (GUID-NRS) can update a GUID entry as soon as the corresponding mobile entity (device, content, subnetwork) moves, at a sub-second (50-100ms) time scale.

The GUID-NRS resolves a GUID into an IP address (or list of IP addresses) of the corresponding mobile network entity, such as a mobile device. Even if the mobile device is disconnected, a partial resolution may be obtained to an IP address of a bigger network segment, for example, a service operator network for a given region.

A key feature of the name resolution service design is to move away from a centralized control over name and address ownership which forms a single root of global trust. The opportunities for competition in naming are evident from the abuses with which the current name resolution system (DNS) is plagued. Today’s name resolution system causes many negative issues that leave DNS far from a service with fairness and effectiveness.

As shown in Figure 1., GUID-NRS service is directly hosted by routers in MobilityFirst platform. The service can have multiple competing providers to avoid single root of trust and must be fast enough to update in 50-100 ms to support dynamic mobility. The distributed GUID-NRS should scale up to 10 Billion names (GUIDs).

1.4.3 Hybrid Name/Address Routing

GUID-NRS resolves a GUID into an IP address – host address (HA), for a mobile host. Since the HA is fast updated as the mobile host moves, the core network routers can reach the HA using conventional prefix routing algorithm. We call this flat routing or early binding routing, when router resolves the IP address of a host before routing.

Due to the high probability of the host disconnection in the mobile Internet, GUID-NRS may not be able to resolve an HA for a given GUID at a given time. However, the core network routers may still be able to route a content with a GUID to an NA, a network IP address (or network prefix) likely connected to the mobile device with the GUID. At a later stage, likely at a router closer to the mobile device, the mobile device’s IP address HA can be resolved and the content can be routed to the mobile device. We call this a hybrid name/address routing or late address binding routing, when the packets or data blocks must carry their names (GUIDs) along the transport towards a network that possibly connects to the destination host. This hybrid name/address routing layer provides mobile host an additional dimension on the choice of multi-homing, content retrieval and geocast. The end-point device and/or interface can be left open until certain context got resolved, enhancing the mobile service usability with context-aware capability. 1.4.4 Disruption-tolerance network (DTN) transport Once a GUID is resolved into an IP address (NA or HA or both), the most essential differentiation of the MobilityFirst architecture from the current Internet is a disruption-tolerance network (DTN) transport. In MobilityFirst, a Cache and forward (CNF) transport protocol is used to achieve disruption-tolerance, replacing the end-to-end (e.g. TCP) for current Internet. When a routing path is determined by the hybrid routing function, CNF transport decides if content should be held in cache or forwarded to the next hop. Essentially, forward is continued if the link quality is good, comparing with statistical average. However, the cache occupancies on the nodes at the both end of a hop is also referred to make a decision. An extreme case is that the link quality is good and stable, the router gets into a switching mode for all packets to be transported on the link. In Figure 1., we can see data transport can still happen even if the destination address is not fully resolved. One example is a message to Jeo can still be sent toward his access network (NA) even though Jeo is disconnected. Another is the “movie1” can be distributed and cached inside network without knowing who is going to use it. The CNF layer is the key interface between the mobilityFirst functions and conventional IP routing functions. The implementation of the CNF layer is the central piece of work for mobilityFirst platform.

Figure 1.2. Procedure of Alice’s computer sends File-1 to Jeo’s laptop

1.4.5 Open issues

What is the economic model of NRS, who operate it and how it gets paid? A distributed fast name resolution (NRS) service offered by competing operators is the core component of the MobilityFirst architecture. Without a proper business model, it cannot be implemented.

2. Naming (name assignment) Services

Naming service is a process to create, publish and lookup the name of a device, content or a service context into an ID recognizable by the network. For examples, Jeo’s laptop, Movie Inception, Cabs at New Brunswick, Anyone in Jeo’s family etc. These are human readable strings representing network entities. However, before they can be used in network applications, they must be “named” to network recognizable GUIDs. GUIDs can be published through different channels depending on the owner’s will. In figure 2.1, we show how a context “Alice sends a file-A to Joe’s laptop” works. First of all, Joe needs to assign a GUID to his laptop. The GUID is made based on PKI keys with a certificate. Joe also needs to publish the GUID for others’ to use it. After the GUID is published, Alice can lookup for the GUID through the naming service. Then the GUID can be used to send the file-A to Joe’s laptop. If Alice is concern about the authentication of the GUID, she can verify it through a certificate authority (CA) or directly through Joe if the certificate is unmanaged.

Figure 2.1. Alice sends a file-A to Joe’s laptop

In this section, we will go through the process of naming service, including GUID assignment, publishing, lookup and verification. And then we will give an example on how to resolve a human readable service context into a network readable service ID.

2.1 Global Unique Identification (GUID)

The global unique identification (GUID) is a name for a resource chosen by its owner. The philosophy behind of using an owner generated GUID is to avoid centralized naming service like ICANN. In MobilityFirst architecture, network resources are not only company networks or host computers, they are billions of network entities including devices, content, sensors and service contexts. The MobilityFirst future Internet architecture must be able to handle the mobility of all these network entities at sub second time scale (50-100ms). Therefore, a decentralized naming system should be implemented. Since the naming services are decentralized, it is important to ensure that a GUID is:

1) Unique globally: guarantee no GUID created by two owners are same. When a conflict occurs, there should be a way to resolve it. 2) Anti-spoofing: provide a way to avoid hackers to misuse the GUID. A user can verify if a GUID belongs to the owner it claims.

For long time, people use one ID for both name and address purposes. As the IPv4 runs out of space, IPv6 is considered to be used to identify every network device in the world. Although there is enough naming space for IPv6 to identify billions of billions of devices (content and other network entities), everyone can spoof it during a data communication, naming claiming certain data from a source with a specific IP address. In addition, IP address is used for Internet routers to route data packets, in case of using an IP address for both naming and addressing, the triangle routing problem always exists when a device is in mobile. Basically, IP tunneling is required for mobile devices away from its home. 2.2 GUID creation The fundamental assumption is the GUID is created by owners’ of device, content and/or any network resource/entities. There should not be a centralized authority for all network resources.

The owner can choose GUID for his resource in the following format, for example,

Using Public Key in GUID provides a way to verify the ownership of the GUID and avoid misuse by non-owners. Adding a resource sequence number enables an owner to create GUIDs for plural of his/her resources with a single certificate of public key. The length of this sequence number determines the number of GUIDs under a single certificate.

The owner must maintain the uniqueness of a GUID within the scope of the ID being used. If the scope is global, the uniqueness must be checked by a global service. In MobilityFirst architecture, name resolution service (NRS) is a global service, however, in a distributed manner, we can use NRS to enforce the uniqueness of a GUID. When a new GUID entry created in the NRS, the NRS will go through a uniqueness check. If there is a conflict (with a slim chance of getting a same public key), the GUID is rejected and the owner must re-create a new GUID.

It is unrealistic to ask every owner of a network resource to purchase a certificate from a certificate authority (CA), such as Verisign. User generated unmanaged certificate should also be allowed, such as using OpenSSL’s “ssl_ca”. In later case, the user of GUID must directly confirm with the owner to verify the genuine of the GUID. For example, Alice may send an email to Joe to confirm if GUID-1 is for his laptop.

2.3 GUID publishing and update

GUID is a name for a network resource. The owner of the network resource must first publish the GUID with the description of the corresponding resource. We call the service that stores the GUID descriptions and make them available to network users as the naming service.

Naming service is not necessarily centralized by any trust authority. It can be a public server, a private server, a cache information in a P2P CDN. As long as it can make GUID description available to its target consumers, it serves the purpose.

The primitives of the GUID description may contain but not limited to (examples in ()):

1) Certificate and its CA (certificate authority) 2) The owner (an owner string, such as ph#, email address, domain name etc.) 3) Resource ID: (a device name, content URL, sensor name, URI etc.) Attributes: tags of resource ID, network interfaces etc.

Table 1. shows the GUID entries on an naming service.

TABLE 1. GUID # Certificate Owner Tag Tag PubK_a + 0034 CA_privKey(Joe@…, PubK_a), CA_name：Verisign PrivK_a(Joe Smith, Joe@…) Type: resource Value: mobile phone Type: network Values: Wifi, 3G PubK_b + 0002 CA_privKey(Alice@…, PubK_b), CA_name:ssl_ca PrivK_b(Alice Taylor, Alice@…) Type: resource Value: laptop Type: Network Value: Wifi, 3G, WiMax PubK_b + 0005 CA_privKey(Alice@…, PubK_b), CA_name:ssl_ca PrivK_b(Alice Taylor, Alice@…) Type: resource Value: tablet Type: Network Value: WiFi, 3G

More attributes to a GUID implies more criteria to identify this GUID by network users. The GUID description must be signed by the private key paired with the public key in GUID. The format of GUID publishing to a naming service server is as following:

GUID publishing

A naming service server can check the integrity of the GUID publishing/update by checking the signatures before a GUID naming entry is created/updated in their database. A false publishing or update returns an error.

GUID publishing response 2.4 GUID lookup and context resolution

When an application tries to use a network resource, it first needs to know the corresponding GUID. For example, Tom wants to send a file-A to Alice’s laptop. Tom knows Alice works for WINLAB, Rutgers University. Tom’s application sends a GUID lookup request, containing keywords: Alice, WINLAB, Rutgers and Laptop, to GUID publishing service. Through keywords matching, the GUID of Alice’s laptop is returned to Tom’s application.

GUID lookup

GUID lookup using name service is like using a search engine, by input some keywords, the GUIDs with most matches in the description return. GUIDs with one or more keywords in the lookup message are returned in GUID lookup_response.

GUID lookup response

In above examples, GUID-1 has the most matches, GUID-2 is a generic GUID for Alice and GUID-3 is Alice’s tablet computer’s GUID, depending on the criteria setup, lookup may still be success even if there is a little mismatch. It leaves to the user decided whether if this GUID should be used. 2.5 GUID for content

In the naming service, we treat all network resources same way to publish and lookup GUID. There is no difference for an owner to name a content or a laptop for naming service. However, usually, an owner can own a large amount of content vs. devices. The owner may need to use multiple certificates if the resource sequence number restricts the size of the resource space.

Figure 2.2. Dynamic GUID assignment for content

Assigning a GUID to a content can make this content more accessible, including more efficient delivery and addressing. However, no matter how big the GUID space is, it cannot include all content in cyberspace because depending on the resolution of representing of a content, one content can derive hundreds of content easily. Therefore, assigning GUID to network content is by no mean to enumerate every possible content in the cyberspace. Since GUID provides a better way for core network to deliver the content, the owner may only assign popular content a GUID and let unpopular content be delivered at the application layer. In this case the owner can dynamically assign resource sequence number to a resource, when a content become less popular, the owner can recycle a sequence number for other contents.

Figure 2.2 shows the dynamic GUID assignment concept. An owner’s content space is bigger than the GUID space, then at any given time, only part of content get GUIDs.

2.6 GUID for sensors

Sensors are also network devices, however, they usually have much lower capacity to store and transfer data. Majority of sensor devices are transmitting only, which means the owner cannot dynamically store the assigned GUID on the sensor devices.

The key difference of a sensor from a computer is that its GUID cannot be sent along with data because the overhead is considered too high. Then it is the access network’s task to remember the mapping between a (shorter) sensor ID and its GUID. The access network is also responsible to update the name resolution service (NRS) on behalf of each sensor associated with it.

Figure 2.3. The mapping and usage of GUIDs for sensors

Figure 2.3 illustrates the procedure of how GUID is used for sensors and then sensors become globally accessible resource in our MobilityFirst Internet architecture. 1) The owner publishes their sensors with GUIDs same way as for normal devices. 2) Applications lookup GUIDi for the sensor Si. 3) Applications request sensor Si’s data. And at the router, the address for GUIDi is looked up. 4) Applications obtain data of sensor Si from address NA.Pi. This procedure looks no different from what for a normal MobilityFirst device, however, it requires the access network maps data from sensor Si to a port Pi accessible by the application.

2.7 GUID for Context – Grouping

One of the goals of the MobilityFirst architecture is to support human readable context, such as, “Send the file-A to ANY of Joe’s computers”, “Send message-B to SOME cabs at New Brunswick”, and “Alert ALL cars behind me” We have noticed the context forms a group of devices and the delivery destination is part or all of the group members. Assigning a context a group GUID can make the context a better accessibility. For example, a GUID for Joe’s computer group can let Joe dynamically use difference devices but giving out a common ID for people to reach him. A GUID for “Cabs at New Brunswick” may is identified to a service to the cabs instead of devices on the cabs.

Figure 2.4. Context forms groups of network resources

Whether or not to assign a context with a GUID is for the convenience of the owner, if the owner thinks a group of his resource (under certain context) needs a fast accessibility by the core network, the owner might assign a GUID, publish it and maintain the routable address update for the group. It is just a matter of performance concern. A GUID is definitely not the only way for a user to reach “all cabs at New Brunswick”.

There are other types of context besides grouping, such as time, cost and event etc. We will consider these context are performance concerns for an application rather than an identification concern. Therefore, we do not think all context can be made a GUID, instead, context can also be made as QoS parameters or a type of service including type of delivery, such as anycast, multicast or broadcast. 2.8 Example of context resolution procedure

Figure 2.4 gives the illustration on how an application resolve a “human readable” contexts to GUID (name) and then IP address for file transfer.

Figure 2.5. Procedure of Context Resolution

The application tries to “send Msg1 to all cabs at New Brunswick”. The first step is to parse this “human readable” string into keywords such as “all cabs” and “New Brunswick”. The second step is to do a GUID lookup, it takes keywords and suggests matching GUID – GUIDofNB. The “all cabs” tag is unsolved. The context becomes “send Msg1 to all cabs at GUIDofNB”. The third step, the Name Resolution Service (NRS) resolve the GUIDofNB to GUIDofIP. At New Brunswick router, further GUID lookup is performed which resolved GUIDofAllCabs. The context becomes “send Msg1 to GUIDofAllCabs”at a New Brunswick router. And finally, the NRS at the New Brunswick router resolves the GUIDofAllCabs into a multicasting IP address for cabs.

3. Name Resolution Service (NRS)

This section presents DIHT, a distributed in- network hash table approach for realizing fast global name resolution services.

3.1 Single-hop in-network hashing The way we meet these scalability requirements is by leveraging the globally available BGP reachability information to distribute the GUID:NA mappings among all the participating ASs in the Internet. With our scheme, every GUID is directly hashed to an existing IP address and its mapping is stored in the AS that announces that IP’s reachability using BGP updates. This results in the resolution of all query/updates in exactly one overlay hop without requiring any table maintenance overheads over what is already available through BGP. Figure 3.1: Direct in-network hashing for naming resolution service

To illustrate this technique, next we present the sequence of required operations assuming the use of the existing IP address space but the same technique can be realized to work with any future addressing scheme. In order to store the mapping of its GUID:NA, a host X forms a GUID insert message and sends it to the border gateway router of the AS that it belongs to. The border gateway applies a predefined consistent hash function on the GUID and maps it to a value IPx in the IP space. Using the IP prefix announcements from its BGP table, the border gateway sends the mapping to be stored at that AS which announced the ownership for IPx. A second host Y , in the same or a different AS who wishes to find the mapping entry for X, sends a GUID query message to its border gateway which then follows a similar hashing scheme to reach the AS maintaining the GUID:NA mapping for X. Here we assume that all ASs have the same view of the prefix announcements. As an enhancement over this baseline scheme, the border gateway router of host X uses K different hash functions and stores the GUID:NA mapping for X at K different places. The benefits from this replication scheme are discussed in Section 3.2 while Figure 7 illustrates an example of the update and query process with K = 3. We note that in contrast to traditional DHT schemes, this approach assumes the participation of network routers in the DIHT scheme in terms of responding to update and query messages and storing the relevant GUID:NA table entries. DIHT does not require any additional table maintenance overhead since we leverage the IP reachability information already made available by the BGP routing protocol. Since the hashing is done locally by the client’s border gateway, inserts and queries are fast and do not consume any network bandwidth. In addition, it is noted that unlike many recent proposals, we do not distribute the mapping table based on assumptions of aggregability of the GUID space. Thus, our scheme is suitable for flat address spaces, which is the proposed design in the MobilityFirst. In the next sections, we discuss the implementation challenges involved in our scheme and describe suitable modifications to the baseline technique to overcome them.

3.2 IP hole effect The key advantage of our approach compared to existing solutions is the use of direct hashing from name to the address of the storage location leading to resolution in a single overlay-hop. While this results in low latency lookups and updates, the fragmented allocation of the address space presents a potential problem. Continuing with our insert-query example from Section 2, the hashed result IPx could fall into an IP address space that no AS announces in the global default free zone. To illustrate the extent of this problem, we analyze the current IP assignment status. At present, while there are 232 possible IP addresses for IPv4, only 86% of them are allocated to various entities [4], the rest being reserved for different purposes including multicast, limited multicast, loopback address and broadcast. Among those allocated address, only 63.7% of them are announced by the ASs, presumably because they do not require reachability to the rest of their IP space. This leads to an overall 55% announcement over the possible range of IPv4 addresses which results in a 45% chance that a randomly hashed IPx will belong to the set of unannounced addresses. We address the IP hole problem by making the border gateway rehash the resulting IPx values that fall into an IP hole. This process is repeated up toM times, following which if the hashed IP still falls in the unannounced block, we pick the announced IP address that has the minimum IP distance to the current hashed value. Given two k-bit addresses, A and B, their IP distance is defined as: We further define the IP distance between an address and an address block as the minimum IP distance between that address to all address in the block. We note that assigning mapping responsibility through IP distance introduces ‘unfairness’ since an AS that announces an IP which is adjacent to a large set of reserved addresses would have to store a large number of mappings. However, using M = 10 rehashes, reduces the probability of staying inside the IP hole to 0.0003 (using the current IP assignment status), thus resulting in very few cases which require this indirect method of IP distance based insert/lookup. Algorithm 1, which summarizes the steps taken by the gateway to deal with the IP hole problem guarantees that a valid hashed result is always found. Since hashing, rehashing and prefix matching processes are done locally by the border gateway, these operations introduce very little delay and do not add any traffic overhead to the network. Also, we note that the solution described above is specific for the current IP address space but a similar scheme can be used for any other future addressing scheme 3.2 Replication To enhance DIHT’s reliability and further reduce access latencies, we increase the number of resolvers responsible for each mapping entry by having the border gateways employ K parallel hash functions at the time of update and query. During insertion or update, the border gateway applies Algorithm 1 K times using independent hash functions on each iteration to obtain K valid addresses. The mapping is stored in all the K ASs responsible for the resulting addresses, thus creating storage replicas for each entry in the mapping table. To lookup a mapping entry, the gateway router selects the closest AS (in terms of path cost obtained from the BGP table) among the K ASs that maintain the required mapping. This replicating technique leads to two important benefits - reduced lookup latencies and increased resilience to random failures. Firstly, with randomized replication, a gateway is more likely to find a nearby AS which stores the required mapping. We show in Section 3 that as K increases from 1 to 5, the 95th percentile lookup latency reduces from 202ms to 91ms. Secondly, as the number of replicas increases, the resilience of the system is also greatly improved as the probability of two distant routers failing simultaneously is very low. Figure 7 illustrates an example of the update and query process with K = 3. Finally, we note that this method interleaves the mapping replicas between ASs in contrast to exact replication of all the mappings from one AS to another, thus adding resilience random failures. The improvement in latency and reliability, however, comes with an increased storage requirement and enhanced complexity in the update process. A careful analysis based on the bounds on requirements and capabilities of the network is thus required to select an appropriate value for K.

3.3 Network Dynamism BGP Churn Changes in the prefixes announced occurs when an AS withdraws a previously announced prefix or announces a new prefix. Since a change in the prefix announcements directly influences our mapping lookup scheme, we analyze its potential effects. A long term study of the BGP churn evolution shows that a major reason for churn in the BGP tables is router configuration mistakes or other anomalies. The actual rate of prefix announcement and withdrawal is fairly small with new prefix announcements dominating prefix withdrawals. When an AS withdraws a certain prefix, all its stored mappings that correspond to the withdrawn prefix will neither be queried nor updated since any new query/update processing will be based on the current announcement status. This results in what we call orphan mappings. If an AS continues to store such mappings its storage memory is wasted, thus we propose the following planned withdrawal protocol: An AS T1, before withdrawing a prefix announcement, uses Algorithm 1 for each GUID that corresponds to the prefix being withdrawn and finds a new storage place T2 for that GUID. While doing so, it excludes its own addresses and thus is guaranteed to find a new AS for each GUID. T1 then sends GUID insert messages to the new ASs corresponding to each affected GUID and finally deletes its own copy of the mappings. Note that this process does not involve the original publisher of the GUID to be involved, thus not requiring it to follow any periodic consistency check protocol. New prefix announcements can similarly result in orphan mappings since any prior hashes resulting in those IP addresses would follow the IP hole procedures and rehash to reach a different AS. In addition, this could result in an AS getting a query for a GUID whose mapping is not stored in its storage table. To solve this problem, an AS can adhere to the following protocol to correct the mapping errors in the system: On receipt of a GUID query which cannot be found in its mapping table, an AS follows Algorithm 1 (again by excluding itself) and finds the AS that was storing the mapping in the absence of the new announced prefix. It then contacts that AS sending a special GUID migration message through which the corresponding mapping is transferred from the prior AS to its rightful AS.We note that subsequent queries/updates for this GUID follows the normal procedure without incurring this additional overhead. We also emphasize that using these simple table rectification protocols guarantee that orphan mappings are promptly removed from the system and table sizes don’t inflate over time. Router Failure: An AS can lose part or whole of its mapping storage due to router failure or intentional maintenance. Every mapping query by a host or router is accompanied by a timeout procedure in case the chosen AS does not respond within a stipulated time. Following a timeout, the host or router can select the next closest AS that stores the mapping required. To further improve resilience and reliability of the mapping, a query can be sent in parallel to P different ASs, with P ≤ K.

4. Hybrid Name/Address Routing and DTN Transport

The MobilityFirst routing component is designed around the observation that there is a fundamental paradigm shift towards mobile communication. Therefore, mobile devices and their associated applications must be treated as first-class Internet citizens, and have built-in support at the network layer. In this section, we will first briefly explore the challenges of mobility and present a set of guiding principles used in our routing techniques. Next, we present GSTAR, a generalized storage-aware routing system, and show how both global- and local-scale routing can support the challenges brought about by mobility. 4.1 Challenges and Design Principles We identify five major challenges brought about by the increase in wireless, mobile communication:

1. Host mobility – Mobile and wireless devices connecting to the Internet have the effect of increasing variance in the physical and topological characteristics of the network. This in turn can result in the performance of the current end-to-end architecture becoming inefficient. Current techniques, such as MobileIP, are inefficient and require added infrastructure. The primary reason this is a difficult challenge to solve is that today’s architecture binds traffic to network addresses, which may quickly change with mobility.
2. Varying levels of link quality – Performance of individual links in the wireless domain often experience a high degree of fluctuation. The end-to-end nature of current protocols often wrongfully view this fluctuation as congestion (since, at that level, it is hard to distinguish between the two), and act in an inefficient manner.
3. Varying levels of connectivity – In addition to link quality fluctuations, complete disconnection can occur in highly mobile environments. Current end-to-end approaches generally require complete paths to be established before data is sent. Instead, DTN-style techniques are necessary for allowing data to be transmitted without having an end-to-end path readily available.
4. Multi-homing – Many wireless devices today have multiple radios and hence can be multi-homed. Unfortunately, existing protocols do not allow the network to reactively choose with interface to send data to, since data is bound initially to an IP address and not a device name.
5. Context-Aware Routing – Context sensitivity of mobile applications, particularly social applications, necessitates network-level support for group-based and non-traditional routing paradigms, such as anycast, multicast, and geocast.

In response to these challenges, we extract three guiding principles that help our routing techniques inherently handle these challenges.

1. Separation of Naming and Addressing ¬– As previously described, network entities are named with long-lasting, flat GUIDs, that do not depend on the entities’ current network attachment point. Therefore, applications can bind data to GUIDs, and not network addresses, giving the network more freedom to act on the data. In addition to GUIDs, low-level address, such as IP addresses, are assigned based on network attachment point.
2. Late Binding – Following from the separation of naming and addressing, the network should have the capability to query a GUID-to-address mapping service dynamically. Therefore, while GUID is the most authoritative piece of routing information, addresses can still be used for hierarchical scalability. However, the sending host does not have to be responsible for the binding; instead, the network itself (which has more detailed knowledge of the topology) can handle it.
3. In-network Storage Utilization – Taking advantage of falling memory costs, future routers should have the ability to temporarily store data as a routing decision, without fear of mis-interpretation by higher level protocols such as TCP. This opens the door for in-network routing flexibility, such as DTN-style message delivery and replication.

4.2 GSTAR Routing To achieve a scalable, mobility-centric solution, our system utilizes both names (i.e., GUIDs) and addresses cooperatively. Since we envision a purely packet-switching architecture, the header containing name and address information may be larger than current IPv4 packet headers. To help amortize this overhead and take advantage of plentiful storage, we envision the data portion of the protocol data unit at the routing layer to be large. Furthermore, these large PDUs will be reliably transmitted by the network on a hop-by-hop basis.

There are three primary headers for PDUs at the routing layer: (1) GUID information, (2) address information, and (3) service tags. Since application data is bound to GUIDs and not network-level addresses, the destination GUID acts as the most authoritative piece of routing information and must always be present in the PDU. Since the MobilityFirst architecture allows dynamic, in-network GUID-to-address queries via the GNRS, a second header storing at least the current destination address is also necessary. Finally, a third header includes service tags, which indicate specific characteristics of the data itself such as whether it is real-time traffic or not. Figure ? presents a high-level illustration of MobilityFirst routing PDUs.

Figure ?: PDU Structure (data size can be large)

With the previously mentioned principles in mind, we now discuss how GUIDs and network addresses are used in combination to route data through MobilityFirst networks. To illustrate the fact that our approach can be implemented as a clean-slate" architecture or integrated with current IP, IP addresses are used as the low-level network addresses in this section. 4.2.1 Global Scale The MobilityFirst routing design philosophy is to provide enough information and resources to individual routers for them to make intelligent, hop-by-hop decisions. To this end, both high-level GUIDs and low-level IP addresses are exposed to routers for the decision making process. Routers obtain information from two sources: (1) network services and (2) the inter-domain routing protocol. A prominent example of a network service is the aforementioned global name resolution service (GNRS). This service responds to GUID-based queries with a set of IP addresses currently bound to that GUID. In the case that there are no IP mappings (e.g., the node is disconnected from the network), it will return a set of networks and the historical probability of that node attaching to one of those networks in the future. Another example service could include a location service, where the result would be the current geographical location of a GUID. For the time being, we assume BGP is used for the inter-domain routing protocol.

It is important to emphasis, however, that GUID is still the focal point of the MobilityFirst architecture and hence has is the most authoritative piece of routing information in the PDU header. The destination IP address(es) may change in-network via a GNRS re-lookup, but the GUID stays the same. This is consistent with binding application data to GUIDs, not IP addresses. 4.2.2 Local Scale Once the PDU has been delivered to the destination network, local storage-aware routing techniques can be used to deliver to the final host.

Route selection and routing decisions MobilityFirst uses a two pronged approach for intra-domain routing that is capable of quickly responding to link quality changes for nearby nodes as well as remaining robust in the face of disconnectivity and partitioning. At a high level, individual routers maintain two types of topology information, one useful for responding to fine-grained changes to links and nodes within the router's current partition, and one useful for responding to course-grain changes to connection probability for all nodes in the network.

The intra-partition graph is formed by collecting topology messages that are periodically flooded by all nodes in the network. These topology messages contain time sensitive information about the link quality for each of the node's 1-hop neighbors. These are transmitted per interface, allowing for in-network multi-homing. Since the messages are flooded, and hence immediately broadcasted and dropped, they will not traverse across partition boundaries. This allows all nodes in the network to have an up-to-date view of the current link qualities within its current partition. In addition to storing current link qualities, all routers maintain a history of link quality information received in the past, which, as will be shown, is useful for routing decisions. If control messages have not been received from a particular node for some period of time, and hence its long term link qualities have become low, a router may assume that node has left the partition and remove it from the graph.

The DTN graph is formed by collecting topology messages that are periodically epidemically disseminated by all nodes in the network. Epidemic dissemination, where control messages are carried by intermediate nodes, is a common technique used in delay-tolerant networking, and allows messages to cross partition boundaries. In essence, these messages are not immediately dropped, but rather carried for a long period of time such that if a node moves from one partition to another, it can ferry messages between the two. These topology messages contain time insensitive information about connection probabilities between the source node and all other nodes in the network. This graph allows a node in the network to be aware of the general connectivity patterns of all nodes, even those outside of its current partition.

These two graphs can then be used together to help route messages to their destinations. For a given message, a router first checks its intra-partition graph for the destination. If the destination exists, then the router will then choose the best path from multiple ones by considering the short term link qualities for nearby hops and the long term link qualities for hops further away. Given that path, if the short term link quality for the next hop is much greater than the long term link quality for the next hop, then the router should immediately forward the data to take advantage of the abnormally good link. On the other hand, if the short term link quality is abnormally bad, then the router should store the message and re-evaluate later. A pictorial example of the routing decision graph, using the estimated transmission time (ETT) as the routing metric, can be seen in Figure ?.

Figure ? - Intra-Partition Routing Decision

If the destination is not found in the intra-partition graph, the router tries to make progress along the DTN graph, which contains a general overview of connectivity throughout the network. The router will compute all shortest paths according to that graph, and attempt to forward a replica of the message to all 1-hop neighbors along those paths. In essence, this DTN-style approach attempts to make use of readily available storage to bridge partitions in the network. An example is given in Figure ?, where node S forwards a replica of a message destined for node D to both nodes A and B. Note that this message is not copied to node C, as this would not progress the message. It is important to note that this framework is flexible enough to incorporate many existing DTN routing protocols. For instance, the protocol-specific metric being used to capture connection probability can be used as the MobilityFirst DTN link-quality" metric that is epidemically disseminated to form the DTN graph. One example is to utilize the average availability metric, described in, to capture the historical percentage of time two nodes were connected. Furthermore, replication rates can be determined by the DTN protocol in question.

Figure ? - DTN-graph Routing

Buffer prioritization and scheduling Since we are anticipating messages to be relatively large, conditions such as link quality and even overall connectivity can change on a per-message basis. Therefore, the message transmission order can greatly impact routing metrics such as average end-to-end delay and throughput.

The general approach taken by the intra-domain routing component is to establish a primary ordering based on information from the intra-partition and DTN graphs. Since the intra-partition graph has time-sensitive weights, messages whose destination is found in the intra-partition graph are given higher priority, in hopes of utilizing good, currently available links. We refer to this as priority 1. Blocks whose destination is only found in the DTN graph are given lower priority, or priority 2. Finally, all remaining messages are given the lowest priority or priority 3 since they will be either stored or dropped.

Priority 1 messages can be further prioritized based on a utility function u that captures how beneficial it would be to transmit the message over the next-hop link in that link's current form. We define u, for a given destination d as

where stlq(nextHop) and ltlq(nextHop) are the short term and long term link qualities (higher is better) of the next hop to reach the destination d. Note that the next hop comes from the routing computation over the intra-partition graph, utilizing both short and long term link qualities, as previously described. Intuitively, u captures how much better the current next-hop link quality is compared to its historical average. Values greater than 1 indicate better than average qualities, and values less than 1 indicate worse than average qualities. Priority 1 messages with higher values of u are given higher priority than priority 1 messages with lower values of u.

Intra-prioritization of priority 2 messages can be very flexible. In the event that an existing DTN routing protocol is being utilized for the DTN graph computation, it may be useful for the buffer prioritization method used by that protocol to be used for ordering the priority 2 messages. One simple prioritization method can be to assign higher priorities to messages whose total path to the destination, along the DTN graph, is of low weight. 4.2.3 Use Cases We now present three use cases that illustrate how in-network services and low-level routing protocols can be cooperatively utilized to overcome challenges of mobility.

<to be added>

5. Management Plane

5.1 Management API in each service

6. Security Considerations

1) Must leave self-generated public key open. Freedom of speech, cost, flexibility. 2) What to do with expired certificate? 3) Certificate type:

1. Self – open_ssl
2. Commercial – Verisign
3. Expired