WO2010066805A1 - Method and device for transferring information in a network - Google Patents

Abstract

A method and a device for transferring information in a network, wherein the network is at least partially organized in substructures; wherein specific roles and/or functions are allocated within each substructure; wherein these roles and/or functions communicate specific information between substructures; and wherein the result of these communications is used to organize the information transfer between at least two of the substructures.

Description

Description

Method and device for transferring information in a network

The invention relates to a method and to a device for transferring information in a network.

The invention relates to a mitigation of addressing and routing problems caused by the continued growth and increased inter- connectedness of the Internet and internet-type networks. For ease of understanding, such networks are usually modeled by a graphical representation, thus in the following text the network may be represented by its respective graph.

Many current design problems in the Internetworking area, such as a locator/identity split work in the IRTF Routing Research Group (see [I]) and a location-independent routing problem in data-oriented network architectures (see, e.g., [2]) need an efficient solution for locating (or resolving) a given entity (a network, a host, a data item, etc.) in an Internet-like network graph with the constraint that the entity identifier contains no topologically relevant information with respect to the Internet-like graph in question.

The main objective for the needed solution is to scale better than the current solution (see, e.g., Border Gateway Protocol (BGP), RFC 1771, [3] ) , which globally distributes a routing state of all objects to the whole network, although within edge domains some of this state can be disregarded via using default routes. If BGP is used, each destination entity will require its own entry in the BGP routing table, as no aggregation in the entity identifier name space can be assumed. While the amount of routing state seems to be growing faster than the currently projected fast memory chips, the more acute problem is with the required communication overhead to keep the routing tables up-to-date.

The problem is to define an efficient, scalable, and deployable solution for locating objects in AS-like graphs, when the used object identifiers cannot be assumed to contain topologically significant information relating to the underlying AS-like graph. The solution may have to be deployable by willing participants without requiring the whole network to upgrade at once, or ever. Additionally, the solution may in particular reduce additional routing overhead, in particular to a minimum. The solution may further be usable for routing purposes using endpoint identifiers in an overlay over the current (and future) IP networks, without requiring any changes to the underlying IP network. When the destination object is located, the routing between the source and destination networks can be further optimized with, e.g., tunneling or translation such that the shortest available paths in the underlying network are used.

The problem space is extensively discussed in the IRTF RRG mailing list (see [4]) . The main problems not solved by [4] are the following:

- Distribution of local changes to the whole global network, causing both memory and communica- tion/processing overheads.

- Reliance on global deployment of LISP+ALT routers in a strict hierarchy.

Also, usage of Distributed Hash Table (DHT) algorithms has been proposed before (see [5]) . The main problems not solved by [5] are the following:

- Policy-compliancy: In a flat DHT as proposed, the message forwarding takes essentially unpredictable paths through the global network. In the worst case, it is possible that the paths go via direct competitors of the source domain.

- High stretch: The paths via the proposed DHT will be many times longer than the underlying valley-free path of the IP network.

- High connectivity: EID prefixes are represented as virtual nodes in the LISP-DHT, which makes the total number of nodes in DHT extremely large and very dynamic, as the DHT structure needs to be updated whenever EID prefixes are added or removed from the system. - Non-locality: Routing through the DHT is not geographically bounded at all.

Additionally, [6] describes the application of [7] to an AS-grap like the Internet. However, [6] also has the cited policy-compliancy issue, as it uses [7] also between non-ISP ASes. Additionally, [6] requires total replacement of the whole Internet architecture, which is a very high stretch.

The problem to be solved is to overcome the disadvantages of the prior art stated above and in particular to provide an efficient solution for transferring information in a network.

This problem is solved according to the features of the in- dependent claims. Further embodiments result from the depending claims .

In order to overcome this problem, a method is provided for transferring information in a network, - wherein the network is at least partially organized in substructures ;

- wherein specific roles and/or functions are allocated within each substructure;

- wherein these roles and/or functions communicate spe- cific information between substructures;

- wherein the result of these communications is used to organize the information transfer between at least two of the substructures.

In an embodiment, the substructures represent edge regions.

In another embodiment, the information transfer within a substructure is completely organized by internal means based on a related substructure internal routing protocol.

In a further embodiment, entities within a substructure are identified by end point identifiers. In a next embodiment, the end point identifiers do not contain topology relevant information.

It is also an embodiment that the specific roles comprise a mapping router.

Pursuant to another embodiment, the communication between mapping routers comprises routing protocol information.

According to an embodiment, the specific roles and/or functions organize themselves to form an overlay network.

According to another embodiment, the overlay network is organized and operated as a peer-to-peer network.

In yet another embodiment, entity location information is stored and retrieved using distributed hash tables (DHTs) .

While the solution provided herein may also utilize DHTs, DHTs can be utilized in a specific way in combination with BGP. The solution provided in particular comprises a combined usage of

BGP-like routing together with a hierarchical DHT-like routing.

According to a next embodiment, the information transfer between the substructures uses tunnels.

Pursuant to yet an embodiment, the information transfer between the substructures uses address translation mechanisms.

The problem stated above is also solved by a device for transferring information in a network, comprising or being associated with a processing unit that is arranged such that the method as described herein is executable on this processing unit.

Said device may be a communication device in a network, in particular a mapping router. It is further noted that said processing unit can comprise at least one, in particular several means that are arranged to execute the steps of the method described herein. The means may be logically or physically separated; in particular several logically separate means could be combined in at least one physical unit.

Said processing unit may comprise at least one of the following: a processor, a microcontroller, a hard-wired circuit, an ASIC, an FPGA, a logic device.

The solution provided herein further comprises a computer program product directly loadable into a memory of a digital computer, comprising software code portions for performing the steps of the method as described herein.

In addition, the problem stated above is solved by a computer-readable medium, e.g., storage of any kind, having computer-executable instructions adapted to cause a computer system to perform the method as described herein.

The problem above is also solved by a network arrangement organized and equipped with means to execute and/or operate according to any one or any combination of the methods as described above.

The problem is further solved by a mapping router that is organized and equipped to execute the steps of the methods described herein.

Embodiments of the invention are shown and illustrated in the following figures:

Fig.l shows a schematic diagram of an exemplary topology;

Fig.2 shows a schematic diagram visualizing a policy-constrained data-oriented networking; Fig.3 shows a schematic diagram visualizing a data-oriented peering.

The solution is related to the mitigation of addressing and routing problems caused by the continued growth and increased interconnectedness of the Internet and internet type networks.

The basic assumption is a separation between routeable edge regions and a routeable core. The problem to be solved in particular is to locate objects as belonging to a certain edge region, while their object identifiers do not contain any location-specific ( "topologically significant") information.

A kind of a virtually hierarchical routing scheme is suggested, wherein "normal" BGP routing is used between nodes within edge regions. A virtual hierarchical overlay structure created between the edge regions enables routing to a certain edge region based on the location-independent identifier, utilizing tunneling or translation of end point identifiers (EIDs) in the core network between edge regions. Selected routers, called "mapping routers", located within the edge regions, are used to create and maintain the virtual hierarchy between the edge regions. Principles known from P2P networking (e.g. CHORD, see [9]) are used for communication and information exchange between re- spective mapping routers (e.g. to route based on location-independent identifiers between edge regions) . The same structure can also be used for location mapping in addition to packet routing. The solution comprises a combined usage of BGP-like routing together with a hierarchical DHT-like routing.

While this solution in particular utilizes DHTs, these DHTs are used in a specific way in combination with BGP.

Normal BGP (or any other suitable state distribution protocol like the one in [2] ) for Endpoint Identifier (EID) routing within edge regions of the network is utilized. The propagation of the EID prefixes is limited to their own edge region, so there is no global build-up of routing state anywhere. Normal BGP routing scalability determines the maximum size of any single edge region; the whole current Internet would fit into one edge region using the currently available routing technology.

The edge regions are connected together in a virtual hierarchical distributed structure (overlay) . This structure is used to locate EID prefixes in other edge regions on demand. The location results will be used to directly connect the edge regions together with a tunnel or address translation mechanism, or any other for- warding mechanism allowing transmission of packet between the edge regions. The location results can be cached within the edge region so that the hierarchical structure need not be consulted unnecessarily.

It is noted that the tunnel or translation endpoints need not be located at the edge of the edge region. For example, a nation-wide operator may operate a single edge region, while the LISP tunnel end-points are located in the networks of their customers. In the case of missing mapping state the tunnel end points would just pass on the EID packets to their default provider (s) , which would then route them to the destination using the overlay, and the tunnel (or equivalent) will eventually be formed between the appropriate networks.

In this solution, the regular BGP state is distributed to the whole network, as today. The EID prefix related BGP state propagation is limited to the edge regions. These regions can, however, form peering relationships over the overlay, and pro-actively push EID prefix reachability state to each other. Regular on-demand caching will do this automatically for the most popular destinations. The distributed structure also provides a backup for any such cached or proactively distributed state.

Using virtual hierarchical overlay in a manner described here provides key benefits over the earlier proposed solutions:

- Locality: message forwarding stays within the smallest virtual hierarchy level shared by both source and destination . - Efficient route caching: All sources within each virtual hierarchy level exit via a common node; so the caching state need not be distributed to too many nodes (like in flat DHTs) . - Authoritative state can be kept within the edge domains, and the access to the EID prefix can be limited to any given sub-hierarchy of the overlay.

- Low stretch: According to [7] the virtual hierarchical overlay can achieve considerably lower stretch than [9] proposed before.

A more detailed implementation example is given below:

Fig.l shows a schematic diagram of an exemplary topology. Autonomous Systems (ASes) are organized into a hierarchy, where non-ISP ASes are on to bottom (Stub ASes) , and obtain transit service in the EID address space from an ISP-AS (Transit ASes) . The ISP-ASes also have an option to obtain the EID transit service from other ISPs. Routing state distribution up to this level is managed with BGP or any other suitable routing protocol. These domains are referred to as edge regions.

The circles in Fig.l represent the autonomous systems (ASes) of the network topology. ASes named Tl-3 represent the Tier-1 ASes, which all peer with each other, but do not but transit service from anyone. The ASes are grouped into edge regions according to their internal business dynamics, such as degree of peering, or bigger regional transit providers willing to provide routing in EID address space as a service. It would also be possible for the Tier-1 ASes to form edge regions similar to the ones shown in Fig.l, but this is omitted for clarity reasons.

The legacy BGP routing on the provider assigned prefixes (locators) takes place in the whole network. In addition, each edge region uses BGP to distribute routes on the identifier address space (EIDs) . The root ASes of each edge region (A, B, and C) utilize this approach and advertise the EID prefixes in a virtual hierarchy. First, the edge regions A and B join their overlays (this is represented by the virtual hierarchy domain H2 ) , and finally A and B join their (already joined) overlays with C (this is represented by the virtual hierarchy domain Hl) .

It is noted that the domains Hl and H2 do not physically exist. All the physical nodes (also referred to as mapping routers) in the hierarchy are located in ASes A, B, and C. All global state is distributed between these routers. Each edge region typically operates multiple physical routers to share the load of state management and routing and to provide fault tolerance.

The traffic between the edge regions is exchanged either via direct peering links (e.g., between A and B), or via transit providers outside the edge regions (in this example the Tier-1 ASes) .

Each of the ISPs (A, B, and C in Fig.l) participating in the virtual hierarchy operates one or more mapping routers that participate in a local Chord-like DHT:

1) Each mapping router has an identity in the EID address space. The identity of the mapping router determines the range of EID prefixes this mapping router is managing at each level of the virtual hierarchy, thus the identity should cor- respond to one of the locally used EID prefixes. The more there are mapping routers in a given hierarchy level, the smaller the share of the EID prefix address space each router manages gets.

2) The mapping routers in a given edge region are organized in a ring, according to their EID values, wrapping around at zero (like in, e.g., [9]) .

3) The mapping routers of an edge region join the local DHT and form the necessary links determined by the DHT algorithm (see, e.g. , [9] ) . 4) The available EID prefixes in a given edge region are partitioned among the local mapping routers so that the mapping router with a given EID will manage EID prefixes equal or greater than its own EID, but less than the EID of the next mapping router in the ring (again, wrapping around at zero) . This can happen by inserting the EID prefixes to the local DHT. Note that this step can be different for different DHT algorithms.

The Edge regions are then connected together in the order described by their position in the virtual hierarchy, starting from bottom and going up the hierarchy levels towards the root:

1) The mapping routers of an edge region join the DHTs of the other edge regions at each level of the virtual hierarchy, starting from the first level above the local edge region, and progressing towards the virtual root. This step requires each mapping router to know its relative position in the virtual hierarchy, including contact information to the mapping routers in the "neighboring" DHTs. This information can be provided in many ways, e.g. by storing the relevant information in the DNS.

a) Each mapping router adds new DHT links to the mapping routers in other edge regions within the sub-hierarchy in question if and only if the link would be a valid link in the DHT method used and the link would be closer than any other link on any lower level of the hierarchy (see [7]) .

b) Each mapping router inserts pointers to all its EID prefixes at the virtual root level, i.e. in the whole global DHT.

i) Additional pointers within any other sub-hierarchies are added on demand, as the target EID prefix is being located. Routing and forwarding within the edge regions takes place as normal to the utilized routing protocol (e.g. BGP) . In addition, the mapping routers advertise default routes, so that packets to destinations not explicitly known in the edge region will be routed to them. The mapping routers then proceed to forward the packet along the links in the overlay structure:

1) If the current mapping router has the destination EID prefix in its own edge region, the mapping router handles the message.

a) If the message contains a packet, the mapping router forwards the packet to the destination EID using the local forwarding system (e.g., IPv4 or IPv6) .

b) The mapping router will return its address (or other forwarding information leading to it) to the proxy mapping routers that have recorded their forwarding information within the message as it has progressed through the overlay structure.

i) If the message is a signaling message intended for the mapping router, the mapping router will respond to the message, returning response with the pointer to the same set of mapping routers as above .

ii) The proxy mapping routers receiving the return address (a pointer) will store it to their local structure (e.g. a Forwarding Information Base,

FIB) , optionally equipped with a time-to-live value (after which it is deleted) .

2) If the current mapping router has a pointer pointing to the destination mapping router for the destination EID prefix, and a) if the message contains a packet it will forward the message to the indicated destination mapping router;

b) if the message is a signaling message intended for the current mapping router, the mapping router will respond to the message, returning the response to the proxy mapping routers that have recorded their forwarding information within the message as it has progressed through the overlay structure.

3) Otherwise the current mapping router forwards the packet to a linked mapping router which EID is closest to the destination EID, but not overshooting it. The mapping router need not know the prefix length being used. This detail needs to be known only within the edge region hosting the EID.

a) If the current mapping router finds that the appropriate link belongs to the next higher sub-hierarchy, i.e. the current mapping router is the proxy mapping router for the destination EID in the current sub-hierarchy, it records its address into the message before forwarding it, so that it can obtain the mapping result to be cached for future queries.

In addition to the establishing, the cached pointers the source and destination mapping routers can also perform traffic engineering as in LISP+ALT and other LISP variants.

Also, normal DHT mechanisms for redundancy and fault tolerance can be used. The security mechanisms described for LISP-ALT can also be used for the solution suggested herein.

Participating domains can add or remove DHT nodes as needed to manage the load imposed to the individual mapping routers. The selection of the mapping router EIDs can also be used to manage the imposed load. EIDs can also be cryptographically generated (see, e.g., [10]), or combinations of clear-text bits and cryptographically generated bits (like, e.g., in [H]) may be utilized.

As indicated above, this approach can be used to route full packets, or for signaling messages used for destination resolution. The utilization of these different methods is an operative preference.

Finally, any two edge regions can agree on a peering relationship with each other, maintaining cached pointers for each other ' s EID prefixes so that the DHT routing is needed only as a backup.

The main advantages over LISP+ALT are: - There are no extra nodes to be deployed in the network. Two consenting networks can start using the solution without having anyone to deploy anything.

- The load will be distributed well than within a strictly hierarchical, aggregated solution described for LISP+ALT; especially the solution suggested herein avoids the incentive-compatibility problem and potential state explosion at the root of the hierarchy.

- The ability to peer over the hierarchy allows for an improved performance.

The main advantages over the LISP-DHT are:

- Normal BGP-like routing is used within non-ISP ASes, thus avoiding the related policy-compliancy and incentive-compatibility issues. - Highly effective caching is enabled by the proxy mapping routers on each level; this enables very low average stretch for the packets passed through the DHT.

- No virtual DHT nodes are created for each EID prefix. This dramatically reduces the size of the DHT, and reduces routing hops, as they scale to the number of DHT nodes

(logarithmically) .

- Since there are no virtual nodes for the EID prefixes, the DHT structure will also be highly stable, so that there is virtually no overhead in maintaining the DHT itself. - The solution provided supports forwarding packets through the DHT, so that the source mapping router does not have to buffer packets.

Additional Remarks:

Several new, data-oriented internetworking architectures have been proposed recently. However, the practical deployability of such designs is an open question. Here, data-oriented network designs in the light of the policy and incentive structures of the present internetworking economy are considered. A main observation is that none of the present proposals is both policy-compliant and incentive-compatible with the current internetworking market, which makes their deployment very challenging if not impossible. This difficulty stems from the unfounded implicit assumption that data-oriented routing policies directly reflect the underlying packet-level in- ter-domain policies.

The Internet architecture was originally developed for the needs of distributed Computing, such as telnet, FTP, and RJE. However, the majority of the present Internet traffic, especially between network domains, is of content delivery nature, such as file sharing, static web content, Internet radio, or other recorded voice or video, or control traffic needed to locate or deliver any wanted pieces of content. Hence, the current situation can be characterized by stating that while the network use has shifted towards content-centric usage patterns, the original host-oriented architecture is optimized for interactive communication between topologically addressed end-points.

To address the shift in network usage, several content, in- formation, or data-oriented models have been proposed; however, in general the data-oriented architectures base their routing decisions on information or content-related identifiers instead of topological prefixes or host addresses (locators) . In effect, due to their location independent identifiers, data-oriented networking architectures enable a wider choice of internetworking control for the ASes. In the current BGP model, an AS can merely advertise reachability of a certain IP address block to a neighbor. It has no control over how that reachability will be propagated or used. Consequently, due to the advertisement, all kinds of traffic not envisioned by the originating AS may take place. As an example, the unexpected rise of the traffic between home users may be considered.

However, if the ASes advertise the availability of data, as in [2] , they would know that such an advertisement may only produce requests for that specific piece of data. This level of control comes with a cost: there are orders of magnitude more data items than network routes to keep track of. Therefore, the inter-domain scalability is a major challenge to any data-oriented network design .

All clean-slate designs are bound to have unsolved deployment issues. Here, the policy-compliancy and incentive-compatibility of the data-oriented architectures with the current internetworking market are addressed, as well as possible implications for data-oriented peering.

Assuming a suitable relative balance between communication and storage costs, even a superficial analysis shows that in a data-oriented architecture it makes sense to cache and disperse data through the network in various ways, thereby reducing the amount of network traffic. At the practical level, this is clearly shown to be the case by the proliferation of content delivery networks, such as Akamai, and the wide-spread practice of caching web pages.

However, the present internetworking market is structured in a way that creates disincentives for some of the ISPs to deploy content caching, and this presumably acts as a disincentive against data-oriented networking in general. Therefore, in order to allow the network architecture to evolve towards a data-oriented one, the caching policies (e.g. what to cache and when) will need to be separated from actual caching mechanisms

(e.g. packet inspection, storage) , thereby allowing them both to evolve independently and free from policy-related disincentives.

Today, the Internet topology is defined by inter-domain policies, established between autonomous systems (ASes) , or domains for short. These policies reflect the business relationships between the domains. In a way, these relationships are more fundamental in nature than the deployed network architecture itself. The policies define who carries whose traffic and where, not the architecture. Hence, also the proposed data-oriented network architectures must take this economic aspect into account, as there is no chance for an abrupt change in the inter-domain business relationships.

Hence, it may well be possible to evolve the data-oriented architectures so that they can be bootstrapped off from the current policy structure, but the present policy-constrained inter-domain paths of the Internet are often not the shortest ones, or the ones with the best performance. That is, the richer network service model, provided by the data-oriented network architectures, may open up the possibility of using more ef- ficient policies, leading to better network utilization and lower costs .

It is further shown as how the inter-domain topology of the Internet arises from the inter-domain policies. Then the proposed data-oriented network architectures are illustrated and placed on a simple policy-constrained Internet scenario. Incentives of various network stakeholders are assessed to participate in the data-oriented networking models. Finally data-oriented caching is described that, if deployed, could enable new inter-domain peering policies.

POLICY-CONSTRAINED INTER-DOMAIN TOPOLOGY The Internet routing system can be divided into two well-defined regions. The intra-domain routing protocols (OSPF, IS-IS) are used within administrative domains (ASes) , while the inter-domain routing is based on the Border Gateway Protocol (BGP, [3]) . The contractual relationships between domains (the inter-domain policies) define the global Internet topology, not the underlying physical connectivity. Since the policies are different for each domain, the inter-domain topology is effectively different for each pair of source and destination. While this complicates the overall inter-domain topology picture, it also narrows down the choices for inter-domain routing, and in some sense makes the inter-domain routing space more tractable than without any such limitation.

The two main types of inter-domain relationships in the Internet are the transit and peering relationships, while a third type, the sibling relationship, is used between the multiple domains under the same administration.

A transit relationship is a customer-provider relationship, where the provider agrees to advertise the customer's routes and thus make the customer's network reachable from the rest of the Internet (as seen by the provider) . The customer also gets routes to all Internet destinations, or uses the provider as a default route, and thus can access the rest of the Internet. The customer pays the provider for these services (reachability and access) . In a partial transit relationship only a subset of the Internet is made available.

In a peering relationship, the ASes agree exchanging traffic only between themselves and their customers by advertising the corresponding routes to each other. The typical incentives for peering are, for large ASes, reciprocal reachability and robustness benefits, and, for smaller ASes, savings on the upstream transit costs. This is why also big content providers, may actively seek peering relationships with other networks. While peering is typically settlement-free, also paid peering is possible . This structure leads to a tiered Internet model, where the ASes at the topmost tier (the Tier-1) form, in practice, an oligopoly that does not buy transit from anyone else; all are peering with each other. This provides connection throughout the Internet.

Since the non-Tier-1 ISPs actively seek to reduce their transit costs, any architectural change that reduces the amount of traffic over the inter-domain transit links may lead to reduced Tier-1 income. For example, if an architectural change allows Tier-2 ISPs to avoid sending or receiving some traffic that they would otherwise need to transmit through the Tier-1 ISPs, the economic effect is the same as in the case of the Tier-2 ISPs peering directly: the Tier-2 ISPs manage to reduce their costs and therefore the Tier-1 oligopoly loses some of its income.

In [12], an empirical valley-free inter-domain path model spanning from the bilateral relationships between ISP is derived as deducible from BGP routing data. In this model, all Internet paths can be divided into three segments, out of which any segment may be omitted for a given path:

1) The uphill path is the sequence of domains from the source domain up to the first provider-to-customer or peer-to-peer link. All the links in this segment are either cus- tomer-to-provider, or sibling-to-sibling links.

2) A peer-to-peer link in the middle . This may be, e.g., a link between two Tier-1 providers, or any peering link between ISPs.

3) The downhill path is the sequence of domains from the first provider-to-customer link to the destination domain. All the links in this segment are either provider-to-customer, or sibling-to-sibling links.

Due to the existing inter-domain policies, practically all Internet paths observe this valley-free model. The maximum AS path length yielding from this structure is about 13, while the maximum shortest AS path length would be around 6. The reason for this increased stretch is that the possible "detours" on the shorter paths have no incentive to provide the transit service between the end-points.

DATA-ORIENTED NETWORKING

Three architectures are described leading the way towards data-oriented networking, each with different namespace design and scalability properties:

- TRIAD [8] ; - ROFL [6]; and

- DONA [2] .

TRIAD uses a BGP-like inter-domain routing protocol to distribute routes to servers identified with DNS names ("BGP with names") . TRIAD assumes that ISPs would be naturally willing to peer on the name level, if they are already peering on the IP level. Furthermore, TRIAD assumes also that the ISPs would willingly advertise their customers' name-based routes to the rest of the Internet. This model leads to the default-free domains carrying routes to all named services. TRIAD addresses the resulting scalability challenge mainly by restricting the managed namespace to service names, individual hosts or data items are not named separately.

ROFL explores the possibility of routing on flat labels in the Internet scale without the underlying IP forwarding assumed by TRIAD and DONA. ROFL does not limit the number of labels assigned to each host, which makes it possible to extend the ROFL design to address individual data items. However, this increases the number of labels in the system by several orders of magnitude.

In ROFL, inter-domain routing is based on a hierarchical distributed hash table structure (see [7]) . The ROFL use of hierarchical DHT design avoids aggregating all the routing state to any single ISP, but with the penalty that the ROFL routes are 2-3 times longer than BGP-routes. More significantly, the routes may require traversing domains in a manner clearly violating the inter-domain routing policies. The latter is a feature of the simplistic application of the Canon [7] method to the inter-domain hierarchy, making traffic from one customer domain to be potentially routed via arbitrary other (possibly competing) customer domains of a given ISP; supposedly, this might be avoidable through a different inter-domain routing design.

DONA takes the TRIAD design further by replacing the DNS names with self-certifying identifiers. DONA also takes the presented peering assumptions literally, and explicitly builds the ar- chitecture on the valley-free policy-constrained AS topology. In DONA, each domain maintains data-level routing state for the data items hosted by it or by any customer or peering domain. This model leads to similar scaling behavior to TRIAD, but on a bigger scale: Routing state for all advertised data items must be maintained by all the Tier-1 domains. These domains may have little interest in participating in such a data routing architecture.

Fig.2 shows a schematic diagram visualizing a policy-constrained data-oriented networking. Dashed lines represent transit re- lationships between a customer (below) and provider domains

(above), and solid lines represent peering relationships. This example follows the DONA model, where the data-level routing state pointing to the closest copy of a specific data item is distributed to all peers, providers, and their peers and providers (dotted arrows) .

According to Fig.2, the valley-free path segments for UserB are: (D-G-I) (uphill); (I-H) (peering), and (H-E-B) (downhill) .

The data requests are forwarded up along the provider hierarchy and then following the specific data routing state when found. Here, symmetrical routing is assumed, making the resulting data path (solid arrows) to be the reverse of the domain-level path followed by the data request. This ensures that the data paths are always policy-compliant. The domain-level stretch for the UserB in this case is 1.7: The policy-compliant domain-level path (D-G-I-H-E-B) has 5/3 times the hops than the shortest possible domain-level path (D-G-C-B) . The possibility for transparent, architecturally integrated route and/or data caching is a central piece in the data-oriented designs considered above. However, so far the architecture proposals have left a crucial policy question unanswered: When, exactly, should a domain cache which piece of data? For example, in Fig.2 above, without caching or data specific forwarding state in either of the domains D or G, the data is sent twice from the server hosting the data.

INCENTIVE-COMPATIBILITY OF DATA-ORIENTED NETWORKING

Here, the potential incentives for data-oriented networking and the economically motivated stances of the different domains forming the Internet will be illustrated.

The present, underlying commercial structure for packet routing and forwarding is adopted. Starting from there, potential changes or challenges brought forward by the data-oriented model are explored, especially regarding caching, when employed on the top of the basic model.

One motivational factor for data-oriented networking is the expected more efficient and timely use of network resources. This is possible due to the network routing state being created by the data requests, which enables sharing the communication and storage resources between multiple recipients. In case of synchronous transmission, this kind of state and resource sharing essentially results in a multicast service. Caching, in turn, enables asynchronous sharing. In general, this kind of sharing has similar incentive structures to peering for packet forwarding: savings on transit costs and reduced latency.

As communication and storage sharing enables higher utilization of the existing peering relationships, some of the weight of the overall traffic moves down from the Tier-1 s to the lower tiers. This forms the first challenge for the so-far presented data-oriented networking proposals: If the existing Tier-1 domains are faced with less growth, or even a small decline in their transit traffic, and therefore less income, why should they participate in the data-oriented networking in the first place? Why should they invest in new data-centers, such as ones needed for DONA, if that will cut their profits? Apparently, a data-oriented architecture is required that is not critically dependent on the Tier-1 networks for other than the present packet-forwarding transit service.

The next question is cache placement: Who has an incentive to cache the data? It seems clear that Tier-1 domains, in their transit role, have no incentive to cache data, if the data served from their caches would be away from their customer links, thereby reducing their transit-fee income. The same applies to all uphill domains: data served from caches will, in general, be away from their customer links, and therefore cuts their revenues. Hence, there is no point serving data on the customer's behalf, unless the customer pays for the caching service. Therefore there is no caching in either of the domains D or G in the Fig.2 above. However, on the downhill paths all domains seem to have an incentive to cache the data, as data served from caches is away from their internal or external transit links. The customer network domains, being at the bottom of the downhill paths, have the most obvious incentive for caching, as they can also directly benefit from reduced latency.

It is noted, however, that most domains will act in both roles (uphill/downhill) at the same time for different data streams and may have considerable internal transit costs. Therefore, the caching policy needs to be based on the traffic direction in each case. Furthermore, the actual caching decision needs to be based on factors such as the pricing model and traffic situation on the intra- and inter-domain links, the cost of caching itself, and the popularity of the data item in question, among other considerations.

DATA-ORIENTED INTER-DOMAIN PEERING The so-far proposed data-oriented architectures have assumed that peering on the IP forwarding level would automatically lead to corresponding peering at the data routing level. Further, the resulting policy-compliant paths are sometimes longer than would be possible based on connectivity alone, but the current inter-domain policy structure does not allow the shorter paths to be taken.

Hence, it is questionable whether there are cases in which the valley-free model could be applied to the data-oriented networking in a relaxed form so that some of the shorter inter-domain paths could be utilized? Are there possibilities for data-oriented peering?

Fig.3 shows a schematic diagram visualizing a data-oriented peering. The domain C is caching the data the UserC has requested so that other users in domain C interested in the same data might get it faster. Now it becomes possible for the domain C to further advertise the same data over its peering links. The rationale for doing this may be that the settlement-free peering link (C-B) may be underutilized, and that providing the data over the peering link is not causing any new external transit costs for the domain C. Comparing this scenario to the situation in Fig.2, the domain-level path from D to B becomes shorter, the end-to-end latency likely smaller, and domain B saves the cost of transit through E. In effect, the domain C is in a transit role through its peering and transit relationships with the domains B and G, respectively. Trying to do this with the existing packet forwarding level inter-domain policies makes no sense, since the downhill path (G-C-B) would contain a peering link (C-B) , which is excluded in the currently observed valley-free model. (The reason for such exclusion is that the transit accounting does not transfer over the peering link.)

Each domain needs to apply local policy and the current intra- and inter-domain traffic situation to decide when to extend the data advertisements to any of its peering domains. These decisions need not be coordinated with the other domains. As the network situation fluctuates, the domain may vary the data set it is advertising over the peering links. In a data-oriented network, more dynamic inter-domain peering policies become possible also due to the looser coupling between the data and packet-level routing and forwarding functions. For example, in Fig.3, when UserC ceases to request the data, the domain C can decide not to advertise the specific data to its peers anymore, and the domain B will need to revert to the valley-free route presented in Fig.2. These dynamic changes are not visible at the packet forwarding level routing policies.

In the current BGP4 Internet, each AS is inviting traffic with BGP route updates over the inter-domain links, but each AS is in direct control of only the traffic they send out. Consequently, a peering link is considered imbalanced if one peer is sending significantly more traffic than the other. In the data-oriented model the sender of the data is only in indirect control of the data being sent, as data availability is being advertised. The receiver initiates the data transfer explicitly, and thus can be considered the benefactor of the traffic instead of the sender. Thus the accounting model for peering balance may need to evolve to signify the benefactor of the data-oriented traffic. This would enable avoiding settlement fees by advertising and providing more data over imbalanced peering links. While this further increases the imbalance on the packet-forwarding level, the overall benefits between the peers would be balanced.

Hence, data-oriented peering provides a new application independent means for optimizing network resources, in ways that are not possible at the packet forwarding level only. Architecturally, the peering and caching mechanisms need to exist in each domain, but the peering and caching policies need to be separated from the mechanisms.

Depending on the inter-domain relationships the peering model may combine the packet and data level considerations, or they can be managed separately. The latter case is needed in overlay ar- chitectures, where some domains only provide packet forwarding service .

CONCLUSIONS

It has been shown that the proposed data-oriented internet-working architectures have inter-domain policy and deployment related incentive problems.

It seems prudent not to expect Tier-1 ISPs to actively participate in creation of the data-oriented Internet as the increased efficiency of the network use will limit the growth of their transit traffic and thus revenue, at least in the short term. Instead, the initial deployment burden of the architecture should be placed where the immediate benefits exist: the end customers and access network providers, as well as content service providers .

The envisaged increased network utility is based on the more effective use of the existing network resources and peering relationships, as the data-oriented model allows provision of cached content to peers without incurring additional (external) transit costs. In some cases this will lead to shorter paths and thus lower end-to-end latency, as well as to reduced transit traffic, as the number of copies being sent over the transit networks decreases.

The higher-level service model of the data-oriented architectures makes the caching and peering policy a central tool for inter-domain traffic engineering and management . However, these policies are non-trivial. The different roles the domain may have in the valley-free model determine the effect of caching on its revenue. The overall picture contains also the various internal and external costs, such as those related to storage and bandwidth. Also, the looser coupling between the packet forwarding and data-oriented routing functions allows better control over peering traffic than what is currently possible with BGP. Finally, the accounting model for peering balance may need to evolve to signify the benefactor of the data-oriented traffic, instead of just assuming that the sender of the packets should pay.

References :

[1 ] http : //www. irtf . org/charter?gtype=rg&group=rrg

[2] T. Koponen, M. Chawla, B. -G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, and I. Stoica. A Data-Oriented (and Beyond) Network Architecture. In ACM SIGCOMM'07. Proceedings, pages 181-192, 2007. http://www.tml.tkk.fi/Opinnot/T-110.7190/2008/spring/ papers/lla_dona-koponen . pdf .

[3] Y. Rekhter and T. Li. A Border Gateway Protocol (BGP-4) . RFC 1771, The Internet Engineering Task Force, Mar. 1995. http : //www . ietf . org/rfc/rfcl771. txt

[4] D. Farinacci, V. Fuller, and D. Meyer. LISP Alternative Topology (LISP+ALT) . Internet-draft, Cisco Systems, April 2008. http : //www. ietf . org/internet-drafts /draft-fuller-lisp -alt-02.txt.

[5] L. Mathy (Lancaster U), L. Iannone, and O. Bonaventure (UCLouvain) . LISP-DHT: Towards a DHT to map identifiers onto locators. Internet-draft, Lancaster U and UC Louvain, February, 2008. http://inl.info.ucl.ac . be/system/files/draft-mathy-Ii sp-dht-OO.txt.

[6] M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, and S. Shenker. ROFL: Routing on Flat Labels. In

ACM SIGCOMM'06. Proceedings, pages 363-374, September

2006. http://www.tml.tkk.fi/Opinnot/T-110.7190/2008/spring/ papers /07b_rof1.pdf .

[7] P. Ganesan, K. Gummadi, and H. Garcia-Molina . Canon in

G major: designing DHTs with hierarchical structure.

Distributed Computing Systems. Proceedings, pages 263-272, 2004. http : //www .mpi-sws . org/~gummadi /papers /hierarchical d hts_tech_rep . pdf .

[8] M. Gritter, D. R. Cheriton. An Architecture for Content Routing Support in the Internet. In USENIX USITS '01. Proceedings, Berkeley, CA, USA, 2001.

[9] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan . Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans . Netw., ll(l) :17-32, 2003. http : //pdos . csail . mit . edu/chord/papers/chord-tn .pdf .

[10] R. Moskowitz, P. Nikander, P. Jokela, and T. Henderson. Host Identity Protocol. Internet-draft, The Internet Engineering Task Force, October 2007. http : //www. ietf . org/internet-drafts /draft-ietf-hip-ba se-10.txt.

[11] T. Aura (Microsoft Research) . Cryptographically Generated Addresses (CGA) . RFC 3972. The Internet Engineering Task Force, Mar. 2005. http://www.ietf.org/rfc/rfc3972.txt

[12] L. Gao . On inferring autonomous system relationships in the Internet. Networking, IEEE/ACM Transactions on, 9(6) :733-745, Dec.2001.

List of Abbreviations:

AS Autonomous System

BGP Border Gateway Protocol DHT Distributed Hash Table

DNS Domain Name System

DONA Data-oriented Network Architecture

EID Endpoint Identifier

IETF Internet Engineering Task Force IRTF Internet Research Task Force

IS-IS Intermediate System to Intermediate System

ISP Internet Service Provider

LISP Location/Identifier Separation Protocol

OSPF Open Shortest Path First ROFL Routing on Flat Labels

RRG Routing Research Group

Claims

Claims :

1. A method for transferring information in a network,

- wherein the network is at least partially organized in substructures; - wherein specific roles and/or functions are allocated within each substructure;

- wherein these roles and/or functions communicate specific information between substructures;

- wherein the result of these communications is used to organize the information transfer between at least two of the substructures.

2. The method of claim 1, wherein the substructures represent edge regions.

3. The method according to claim 1 or 2, wherein the information transfer within a substructure is completely organized by internal means based on a related substructure internal routing protocol.

4. The method according to any of the previous claims, wherein entities within a substructure are identified by end point identifiers.

5. The method according to claim 4, wherein the end point identifiers do not contain topology relevant information.

6. The method according to any of the previous claims, wherein the specific roles comprise a mapping router.

7. The method according to claim 6, wherein the communication between mapping routers comprises routing protocol information .

8. The method according to any of the previous claims, wherein the specific roles and/or functions organize themselves to form an overlay network.

9. The method according to claim 8, wherein the overlay network is organized and operated as a peer-to-peer network.

10. The method according to claim 9, wherein entity location information is stored and retrieved using distributed hash tables .

11. The method according to any of the previous claims, wherein the information transfer between the substructures uses tunnels .

12. The method according to any of the claims 1 to 10, wherein the information transfer between the substructures uses address translation mechanisms.

13. A network arrangement organized and equipped with means to execute and/or operate according to any one or any combination of the methods as claimed in any of the previous claims .

14. A mapping router organized and equipped to execute according to any of the methods according to any of the claims 7 to 12.

15. A device comprising a processing unit that is arranged such that the method according to any of the claims 1 to 12 is executable thereon.