US20140173034A1

Movatterモバイル変換

Info

Publication number: US20140173034A1
Application number: US14/115,310
Authority: US
Inventors: Hang Liu; Serhard Doken; Xavier DeFoy; Osama Lotfallah
Original assignee: InterDigital Patent Holdings Inc
Current assignee: InterDigital Patent Holdings Inc
Priority date: 2011-05-03
Filing date: 2012-05-03
Publication date: 2014-06-19
Also published as: TW201312980A; WO2012151430A1; EP2705648A1

Abstract

A method and apparatus for content identification, retrieval, and routing in the Internet are provided. In the method and apparatus, content is uniquely identified using an object identifier (OID), and the OID is used for routing and retrieving content in an Internet network. Further, in the method and apparatus, OID summarization based on one or more OIDs may be performed, in which Bloom filters are applied to a portion of the one or more OIDs. Furthermore, hash functions may be applied to network node identities to determine location resolver nodes associated with content.

Description

CROSS REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application Ser. No. 61/481,969 filed on May 3, 2011, U.S. Provisional Application Ser. No. 61/490,397 filed on May 26, 2011, U.S. Provisional Application Ser. No. 61/509,887 filed on Jul. 20, 2011, and PCT application No. PCT/US2012/036369, filed May 3, 2012, the contents of which are hereby incorporated by reference herein as if fully set forth.

BACKGROUND

Content retrieval in Internet networks is based on a client-server model. In the client-server model, a client device that is interested in retrieving content may request content based on an Internet Protocol (IP) address of a server that stores the content. The content is then retrieved from the server and provided to the client device. Thus, the client-server model couples the identity of content to the content's storage location and lacks an independent means of identifying content.

Further, as network nodes such as base stations, access points, and routers, become better equipped with storage capability, network nodes are able to cache content that is more readily available to client devices than using content servers. In addition, as network nodes become better equipped with computational capability, the network nodes may utilize their computational capability and any knowledge of their networks to figure out efficient means for retrieving content. However, because the client-server model couples content identity to storage location, the client server model deprives network nodes from using many of these capabilities as they do not have means of identifying content independently of storage location.

It is, therefore, desirable to have a method and apparatus for identifying content independently of storage location. It is also desirable to have a method and apparatus for network nodes to store, retrieve, and route content based on the content's identity.

SUMMARY

Method and apparatus for content identification, retrieval and routing in Internet networks are provided. In the method and apparatus, a content delivery network (CDN) comprises a first node comprising a first node receiver configured to receive a request for content. In one embodiment, the request for content identifies content using an object identifier (OID) associated the content. In another embodiment, the first node comprises a first node processor configured to determine whether the content is stored in a local cache of the first node based on the OID associated the content. In another embodiment, on a condition that the content is not stored in the local cache of the first node, the first node further comprises a first node transmitter configured to send the request for content to a second node.

Further in the method and apparatus, the network comprises a second node comprising a second node receiver configured to receive the request for content from the first node and a second node processor configured to determine whether a location object (LO) is maintained for the content. In one embodiment, on a condition that an LO is maintained for the content, the second node further comprises a second node transmitter configured to send to the first node an indication of a location for retrieval of the content.

In an additional embodiment, the second node is a location resolver (LR) node and in another embodiment, the first node is configured to determine the second node by applying a hash function to the OID associated with the content to produce a first hash function value and by applying the hash function to an identity associated with each of a plurality of nodes to produce a plurality of second hash function values, and by comparing the first hash function value to the plurality of second hash function values to determine the second node.

In one embodiment, on a condition that the content is stored in the local cache of the first node, the first node transmitter provides the content. In another embodiment, the OID of the content is comprised of type-length-value (TLV) fields.

BRIEF DESCRIPTION OF THE DRAWINGS

A more detailed understanding may be had from the following description, given by way of example in conjunction with the accompanying drawings wherein:

FIG. 1A is a system diagram of an example communications system in which one or more disclosed embodiments may be implemented;

FIG. 1B is a system diagram of an example wireless transmit/receive unit (WTRU) that may be used within the communications system illustrated inFIG. 1A;

FIG. 1C is a system diagram of an example radio access network and an example core network that may be used within the communications system illustrated inFIG. 1A;

FIG. 2 shows an object identifier (OID) in accordance with an embodiment;

FIG. 3 shows an OID in accordance with an embodiment;

FIG. 4 shows an example of a network used in the Internet;

FIG. 5 shows a request for content having an integrated IP address and OID;

FIG. 6 shows a method of retrieving content based on an OID;

FIG. 7 shows a method of retrieving content based on an OID;

FIG. 8 shows a method of processing a request for content having a time-to-live (TTL) field;

FIG. 9 shows a hash ring for determining a location resolver (LR) of particular content;

FIG. 10A shows a method of location resolution;

FIG. 10B shows a location object;

FIG. 11 shows a method of requesting content using an LR;

FIG. 12 shows an example of a multi-tier hierarchical Internet network;

FIG. 13 shows hash function rings for a domain and routing areas;

FIG. 14 shows an example of OID summarization;

FIG. 15 shows a summary location object (SLO);

FIG. 16 shows a flow diagram of a method for publishing an SLO;

FIG. 17 shows a flow diagram of a method for retrieving content based on an OID; and

FIG. 18 shows a flow diagram of a method for retrieving content.

DETAILED DESCRIPTION

FIG. 1A is a diagram of anexample communications system100 in which one or more disclosed embodiments may be implemented. Thecommunications system100 may be a multiple access system that provides content, such as voice, data, video, messaging, broadcast, etc., to multiple wireless users. Thecommunications system100 may enable multiple wireless users to access such content through the sharing of system resources, including wireless bandwidth. For example, thecommunications systems100 may employ one or more channel access methods, such as code division multiple access (CDMA), time division multiple access (TDMA), frequency division multiple access (FDMA), orthogonal FDMA (OFDMA), single-carrier FDMA (SC-FDMA), and the like.

As shown inFIG. 1A, thecommunications system100 may include wireless transmit/receive units (WTRUs)102a,102b,102c,102d, a radio access network (RAN)104, acore network106, a public switched telephone network (PSTN)108, the Internet110, andother networks112, though it will be appreciated that the disclosed embodiments contemplate any number of WTRUs, base stations, networks, and/or network elements. Each of the

WTRUs

102a,102b,102c,102dmay be any type of device configured to operate and/or communicate in a wireless environment. By way of example, the

WTRUs

102a,102b,102c,102dmay be configured to transmit and/or receive wireless signals and may include user equipment (UE), a mobile station, a fixed or mobile subscriber unit, a pager, a cellular telephone, a personal digital assistant (PDA), a smartphone, a laptop, a netbook, a personal computer, a wireless sensor, consumer electronics, and the like.

Thecommunications systems100 may also include abase station114aand abase station114b. Each of the

base stations

114a,114bmay be any type of device configured to wirelessly interface with at least one of the

WTRUs

102a,102b,102c,102dto facilitate access to one or more communication networks, such as thecore network106, theInternet110, and/or thenetworks112. By way of example, the

base stations

114a,114bmay be a base transceiver station (BTS), a Node-B, an eNode B, a Home Node B, a Home eNode B, a site controller, an access point (AP), a wireless router, and the like. While the

base stations

114a,114bare each depicted as a single element, it will be appreciated that the

base stations

114a,114bmay include any number of interconnected base stations and/or network elements.

Thebase station114amay be part of theRAN104, which may also include other base stations and/or network elements (not shown), such as a base station controller (BSC), a radio network controller (RNC), relay nodes, etc. Thebase station114aand/or thebase station114bmay be configured to transmit and/or receive wireless signals within a particular geographic region, which may be referred to as a cell (not shown). The cell may further be divided into cell sectors. For example, the cell associated with thebase station114amay be divided into three sectors. Thus, in one embodiment, thebase station114amay include three transceivers, i.e., one for each sector of the cell. In another embodiment, thebase station114amay employ multiple-input multiple output (MIMO) technology and, therefore, may utilize multiple transceivers for each sector of the cell.

The

base stations

114a,114bmay communicate with one or more of the

WTRUs

102a,102b,102c,102dover anair interface116, which may be any suitable wireless communication link (for example, radio frequency (RF), microwave, infrared (IR), ultraviolet (UV), visible light, etc.). Theair interface116 may be established using any suitable radio access technology (RAT).

More specifically, as noted above, thecommunications system100 may be a multiple access system and may employ one or more channel access schemes, such as CDMA, TDMA, FDMA, OFDMA, SC-FDMA, and the like. For example, thebase station114ain theRAN104 and the

WTRUs

102a,102b,102cmay implement a radio technology such as Universal Mobile Telecommunications System (UMTS) Terrestrial Radio Access (UTRA), which may establish theair interface116 using wideband CDMA (WCDMA). WCDMA may include communication protocols such as High-Speed Packet Access (HSPA) and/or Evolved HSPA (HSPA+). HSPA may include High-Speed Downlink Packet Access (HSDPA) and/or High-Speed Uplink Packet Access (HSUPA).

In another embodiment, thebase station114aand the

WTRUs

102a,102b,102cmay implement a radio technology such as Evolved UMTS Terrestrial Radio Access (E-UTRA), which may establish theair interface116 using Long Term Evolution (LTE) and/or LTE-Advanced (LTE-A).

In other embodiments, thebase station114aand the

WTRUs

102a,102b,102cmay implement radio technologies such as IEEE 802.16 (i.e., Worldwide Interoperability for Microwave Access (WiMAX)), CDMA2000, CDMA2000 1X, CDMA2000 EV-DO, Interim Standard 2000 (IS-2000), Interim Standard 95 (IS-95), Interim Standard 856 (IS-856), Global System for Mobile communications (GSM), Enhanced Data rates for GSM Evolution (EDGE), GSM EDGE (GERAN), and the like.

Thebase station114binFIG. 1A may be a wireless router, Home Node B, Home eNode B, or access point, for example, and may utilize any suitable RAT for facilitating wireless connectivity in a localized area, such as a place of business, a home, a vehicle, a campus, and the like. In one embodiment, thebase station114band the

WTRUs

102c,102dmay implement a radio technology such as IEEE 802.11 to establish a wireless local area network (WLAN). In another embodiment, thebase station114band the

WTRUs

102c,102dmay implement a radio technology such as IEEE 802.15 to establish a wireless personal area network (WPAN). In yet another embodiment, thebase station114band the

WTRUs

102c,102dmay utilize a cellular-based RAT (e.g., WCDMA, CDMA2000, GSM, LTE, LTE-A, etc.) to establish a picocell or femtocell. As shown inFIG. 1A, thebase station114bmay have a direct connection to theInternet110. Thus, thebase station114bmay not be required to access theInternet110 via thecore network106.

TheRAN104 may be in communication with thecore network106, which may be any type of network configured to provide voice, data, applications, and/or voice over internet protocol (VoIP) services to one or more of the

WTRUs

102a,102b,102c,102d. For example, thecore network106 may provide call control, billing services, mobile location-based services, pre-paid calling, Internet connectivity, video distribution, etc., and/or perform high-level security functions, such as user authentication. Although not shown inFIG. 1A, it will be appreciated that theRAN104 and/or thecore network106 may be in direct or indirect communication with other RANs that employ the same RAT as theRAN104 or a different RAT. For example, in addition to being connected to theRAN104, which may be utilizing an E-UTRA radio technology, thecore network106 may also be in communication with another RAN (not shown) employing a GSM radio technology.

Thecore network106 may also serve as a gateway for the

WTRUs

102a,102b,102c,102dto access thePSTN108, theInternet110, and/orother networks112. ThePSTN108 may include circuit-switched telephone networks that provide plain old telephone service (POTS). TheInternet110 may include a global system of interconnected computer networks and devices that use common communication protocols, such as the transmission control protocol (TCP), user datagram protocol (UDP) and the internet protocol (IP) in the TCP/IP internet protocol suite. Thenetworks112 may include wired or wireless communications networks owned and/or operated by other service providers. For example, thenetworks112 may include another core network connected to one or more RANs, which may employ the same RAT as theRAN104 or a different RAT.

Some or all of the

WTRUs

102a,102b,102c,102din thecommunications system100 may include multi-mode capabilities, i.e., the

WTRUs

102a,102b,102c,102dmay include multiple transceivers for communicating with different wireless networks over different wireless links. For example, theWTRU102cshown inFIG. 1A may be configured to communicate with thebase station114a, which may employ a cellular-based radio technology, and with thebase station114b, which may employ anIEEE 802 radio technology.

FIG. 1B is a system diagram of anexample WTRU102. As shown inFIG. 1B, theWTRU102 may include aprocessor118, atransceiver120, a transmit/receiveelement122, a speaker/microphone124, akeypad126, a display/touchpad128,non-removable memory106,removable memory132, apower source134, a global positioning system (GPS)chipset136, andother peripherals138. It will be appreciated that theWTRU102 may include any sub-combination of the foregoing elements while remaining consistent with an embodiment.

Theprocessor118 may be a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Array (FPGAs) circuits, any other type of integrated circuit (IC), a state machine, and the like. Theprocessor118 may perform signal coding, data processing, power control, input/output processing, and/or any other functionality that enables theWTRU102 to operate in a wireless environment. Theprocessor118 may be coupled to thetransceiver120, which may be coupled to the transmit/receiveelement122. WhileFIG. 1B depicts theprocessor118 and thetransceiver120 as separate components, it will be appreciated that theprocessor118 and thetransceiver120 may be integrated together in an electronic package or chip.

The transmit/receiveelement122 may be configured to transmit signals to, or receive signals from, a base station (e.g., thebase station114a) over theair interface116. For example, in one embodiment, the transmit/receiveelement122 may be an antenna configured to transmit and/or receive RF signals. In another embodiment, the transmit/receiveelement122 may be an emitter/detector configured to transmit and/or receive IR, UV, or visible light signals, for example. In yet another embodiment, the transmit/receiveelement122 may be configured to transmit and receive both RF and light signals. It will be appreciated that the transmit/receiveelement122 may be configured to transmit and/or receive any combination of wireless signals.

In addition, although the transmit/receiveelement122 is depicted inFIG. 1B as a single element, theWTRU102 may include any number of transmit/receiveelements122. More specifically, theWTRU102 may employ MIMO technology. Thus, in one embodiment, theWTRU102 may include two or more transmit/receive elements122 (e.g., multiple antennas) for transmitting and receiving wireless signals over theair interface116.

Thetransceiver120 may be configured to modulate the signals that are to be transmitted by the transmit/receiveelement122 and to demodulate the signals that are received by the transmit/receiveelement122. As noted above, theWTRU102 may have multi-mode capabilities. Thus, thetransceiver120 may include multiple transceivers for enabling theWTRU102 to communicate via multiple RATs, such as UTRA and IEEE 802.11, for example.

Theprocessor118 of theWTRU102 may be coupled to, and may receive user input data from, the speaker/microphone124, thekeypad126, and/or the display/touchpad128 (e.g., a liquid crystal display (LCD) display unit or organic light-emitting diode (OLED) display unit). Theprocessor118 may also output user data to the speaker/microphone124, thekeypad126, and/or the display/touchpad128. In addition, theprocessor118 may access information from, and store data in, any type of suitable memory, such as thenon-removable memory106 and/or theremovable memory132. Thenon-removable memory106 may include random-access memory (RAM), read-only memory (ROM), a hard disk, or any other type of memory storage device. Theremovable memory132 may include a subscriber identity module (SIM) card, a memory stick, a secure digital (SD) memory card, and the like. In other embodiments, theprocessor118 may access information from, and store data in, memory that is not physically located on theWTRU102, such as on a server or a home computer (not shown).

Theprocessor118 may receive power from thepower source134, and may be configured to distribute and/or control the power to the other components in theWTRU102. Thepower source134 may be any suitable device for powering theWTRU102. For example, thepower source134 may include one or more dry cell batteries (e.g., nickel-cadmium (NiCd), nickel-zinc (NiZn), nickel metal hydride (NiMH), lithium-ion (Li-ion), etc.), solar cells, fuel cells, and the like.

Theprocessor118 may also be coupled to theGPS chipset136, which may be configured to provide location information (e.g., longitude and latitude) regarding the current location of theWTRU102. In addition to, or in lieu of, the information from theGPS chipset136, theWTRU102 may receive location information over theair interface116 from a base station (e.g.,

base stations

114a,114b) and/or determine its location based on the timing of the signals being received from two or more nearby base stations. It will be appreciated that theWTRU102 may acquire location information by way of any suitable location-determination method while remaining consistent with an embodiment.

Theprocessor118 may further be coupled toother peripherals138, which may include one or more software and/or hardware modules that provide additional features, functionality and/or wired or wireless connectivity. For example, theperipherals138 may include an accelerometer, an e-compass, a satellite transceiver, a digital camera (for photographs or video), a universal serial bus (USB) port, a vibration device, a television transceiver, a hands free headset, a Bluetooth® module, a frequency modulated (FM) radio unit, a digital music player, a media player, a video game player module, an Internet browser, and the like.

FIG. 1C is a system diagram of theRAN104 and thecore network106 according to an embodiment. As noted above, theRAN104 may employ an E-UTRA radio technology to communicate with the

WTRUs

102a,102b,102cover theair interface116. TheRAN104 may also be in communication with thecore network106.

TheRAN104 may include eNode-

Bs

140a,140b,140c, though it will be appreciated that theRAN104 may include any number of eNode-Bs while remaining consistent with an embodiment. The eNode-

Bs

140a,140b,140cmay each include one or more transceivers for communicating with the

WTRUs

102a,102b,102cover theair interface116. In one embodiment, the eNode-

Bs

140a,140b,140cmay implement MIMO technology. Thus, the eNode-B140a, for example, may use multiple antennas to transmit wireless signals to, and receive wireless signals from, theWTRU102a.

Each of the eNode-

Bs

140a,140b,140cmay be associated with a particular cell (not shown) and may be configured to handle radio resource management decisions, handover decisions, scheduling of users in the uplink and/or downlink, and the like. As shown inFIG. 1C, the eNode-

Bs

140a,140b,140cmay communicate with one another over an X2 interface.

Thecore network106 shown inFIG. 1C may include a mobility management gateway (MME)142, a servinggateway144, and a packet data network (PDN)gateway146. While each of the foregoing elements are depicted as part of thecore network106, it will be appreciated that any one of these elements may be owned and/or operated by an entity other than the core network operator.

TheMME142 may be connected to each of the eNode-Bs142a,142b,142cin theRAN104 via an S1 interface and may serve as a control node. For example, theMME142 may be responsible for authenticating users of the

WTRUs

102a,102b,102c, bearer activation/deactivation, selecting a particular serving gateway during an initial attach of the

WTRUs

102a,102b,102c, and the like. TheMME142 may also provide a control plane function for switching between theRAN104 and other RANs (not shown) that employ other radio technologies, such as GSM or WCDMA.

The servinggateway144 may be connected to each of the

eNode Bs

140a,140b,140cin theRAN104 via the S1 interface. The servinggateway144 may generally route and forward user data packets to/from the

WTRUs

102a,102b,102c. The servinggateway144 may also perform other functions, such as anchoring user planes during inter-eNode B handovers, triggering paging when downlink data is available for the

WTRUs

102a,102b,102c, managing and storing contexts of the

WTRUs

102a,102b,102c, and the like.

The servinggateway144 may also be connected to thePDN gateway146, which may provide the WTRUs102a,102b,102cwith access to packet-switched networks, such as theInternet110, to facilitate communications between the

WTRUs

102a,102b,102cand IP-enabled devices.

Thecore network106 may facilitate communications with other networks. For example, thecore network106 may provide the WTRUs102a,102b,102cwith access to circuit-switched networks, such as thePSTN108, to facilitate communications between the

WTRUs

102a,102b,102cand traditional land-line communications devices. For example, thecore network106 may include, or may communicate with, an IP gateway (e.g., an IP multimedia subsystem (IMS) server) that serves as an interface between thecore network106 and thePSTN108. In addition, thecore network106 may provide the WTRUs102a,102b,102cwith access to thenetworks112, which may include other wired or wireless networks that are owned and/or operated by other service providers.

Internet content, such as, for example, audio, video, and web pages, may be identified by an object identifier (OID). An OID may uniquely identify a particular content and may be used to refer to the content. Further, devices and users may request the content based on the OID and the network utilize the OID when routing the content. The OID enables the identification of content independent of storage location and is, therefore, unlike models that identify content based on a location in the Internet where the content is stored, (for example, an Internet Protocol (IP) address of a content sever). An OID for content may be set forth by a creator of the content or a publisher of the content. Further, content naming services may be utilized for providing an OID to content, (for example, newly created content).

FIG. 2 shows an OID in accordance with an embodiment described herein. TheOID200 comprises a country orgroup code201, apublisher code202, atitle code203, a format ortype code204, atimestamp205, and aduration206. The country orgroup code201 is a code that is assigned to a country or a group. The country orgroup code201 may be the country or group associated with a publisher or creator of the content. Thepublisher code202 is a code associated with the publisher of the content. The publisher of the content may, for example, be an electronic content creation service provider. Thetitle code203 may represent a title for the content. The format ortype code204 may indicate a file format or a type for content. For example, a format ortype code204 may indicate that the content is a text document, a motion picture expert's group (MPEG) encoded video, or more specifically an MPEG-4 encoded video with a particular resolution, among other formats or types. Thetimestamp205 indicates a starting time for the content, (for example, for a video or audio file). Theduration206 represents a duration for the content, (for example, a duration for a video or audio segment). The order of the fields201-206 of theOID200 may be changed and theOID200 may include any number of additional fields.

AnOID200 may be human-readable or, alternatively, may be a string of characters that does not have a readable meaning.

FIG. 3 shows an OID in accordance with another embodiment described herein. TheOID300 comprises N type-length-value (TLV) fields301_1-N(referred to collectively hereinafter as TLV fields301 and singularly hereinafter asTLV field301_i, where i represents an integer, i=1, 2, . . . , N). EachTLV field301_iis comprised of atype field302_i, a length field303_i, and a value field304_i. For example, aTLV field301_imay correspond to any one of the codes201-206 ofOID200 inFIG. 2.

Thetype field302_irepresents the type of theTLV field301_i, (for example, a code or string of characters indicating thatTLV field301_iis a country code, a publisher code, title code, or the like). The length field303_irepresents the length of the value field304_i. The value field304_irepresents the value of theTLV field301_i, (i.e., the value pertaining to thetype field302_iof the content). For example,TLV301_imay represent a movie title, wherebytype field302_iis a code indicating that theTLV301_ipertains to a movie title and the value field304_iis a string of characters indicating the title of the movie, (i.e., the title of the content).

Thetype field302_i, length field303_i, and value field304_imay be concatenated without separation to form theTLV301_iand the TLV fields301 may also be concatenated without separation to form theOID300. Thetype field302_iand length field303_imay be of fixed length, (for example, 2 bytes or octets) and the value field304_imay be of variable length having any number of bits.

FIG. 4 shows an example of a network used in the Internet. Thenetwork400 is comprised of nodes401_A-I(referred to collectively hereinafter asnodes401 and singularly hereinafter as node401_i). Thenodes401 facilitate content delivery for an internet-enableddevice402. After the content is located, the content is provided to thedevice402. It is recognized that the Internet is scaled larger than thenetwork400 depicted inFIG. 4, which is shown for discussion purposes. Furthermore, thenetwork400 may be one routing area in the Internet that is connected to other routing areas having similar or varying landscapes or topologies. An OID may be used to identify content within thenetwork400. Further, an OID may be used to identify devices, such asdevice402, andnodes401_A-Iin the network.

Thenodes401_imay be content servers, such ascontent servers401_H,Ior content routers, such ascontent routers401_A-G.Content servers401_H,Imay store content for access by thedevice402. Thecontent servers401_H,Imay have IP addresses and thedevice402 may request content from thenetwork400 by identifying an IP address of acontent server401_H,Istoring the content. Alternatively, thecontent servers401_H,Imay associate stored content with an OID of the content and thedevice402 may, therefore, request content from the network based on an OID of the content. Although shown inFIG. 4 as being on the edges of thenetwork400, thecontent servers401_H,Imay be anywhere in thenetwork400.

Content routers

401_A-Gmay route traffic, (for example, content and requests for content), between thedevice402,content servers401_H,I, andother content routers401_A-G. Thus, upon receiving a request for content,content routers401_A-Gmay route the request for content to an intended node. Examples ofcontent routers401_A-Ginclude Institute of Electrical and Electronics Engineers (IEEE) 802.11 access points (APs), and LTE eNBs, among others.

In addition to simply routing traffic in thenetwork400,content routers401_A-Gmay also cache content by storing a local copy of the content on-site. For example,content routers401_A-Gmay store a local copy of frequently requested or trafficked content. By doing so,content routers401_A-Gmay be able to more readily provide the content to a requesting party, (for example,device402, or another node401_i).Content routers401_A-Gmay provide the content to the requesting party without an additional delay incurred in fetching the content from an intended node, (for example, acontent server401_H,Ior anothernode401_ielsewhere in the network400).

Some networks, such asnetwork400, may be all OID-equipped whereby all the nodes of the network are capable of processing OIDs. However, other networks may be integrated networks that utilize IP addressing and OIDs for content identification and retrieval. In the integrated networks, a node may be capable of processing OIDs and retrieving content based on the content's OID, processing IP addresses and retrieving content based on an IP address of where the content is stored, or processing both OIDs and IP addresses and retrieving content based upon any combination of the content's OID or an IP address of where the content is stored. It is noted that a node that is not capable of processing OIDs may connect to an OID-capable node as a client and thus be able to receive OID services.

A network node, for example, acontent router401_A, may comprise several physical layer and link layer interfaces, a cache, and a forwarding and storage engine. A network node may also comprise a functional unit for OID processing and resolution and a functional unit for IP routing.

Thedevice402 may retrieve content from thenetwork400 by sending a request for content to thenetwork400, (for example, thedevice402 may send the request for content to node401_A). The request for content may be routed and propagated by thenodes401_iof thenetwork400. The request for content may identify content using an IP address, an OID, or both an IP address and an OID.

FIG. 5 shows a request for content having an integrated IP address and OID. The request forcontent500 has anIP field501, anOID field502, and apayload503. TheIP field501 may include a source IP address, which identifies the IP address of the party requesting the content, and a destination IP address, which identifies the IP address of a party to which the request is intended. The destination IP address may be an address of a node storing the content, or an address of another node, for example, an intermediary node in the network.

TheIP field501 may include a field length which indicates the length of theIP field501 and a total length which indicates the length of the request forcontent500. TheIP field501 may also include a protocol field which identifies whether anOID field502 is included in the request forcontent500. Further, the IP field may include a time-to-live field, and any number of flags, which are used for routing the request for content and which are described in more detail herein.

TheOID field502 may include a source OID, which indicates the OID of the party requesting the content and a destination OID, which indicates the OID of the desired content, or a network node storing the content. TheOID field502 may include a field length which indicates the length of theOID field502 and a total length which indicates the length of the request forcontent500. TheOID field502 may also include a type field, which indicates whether the destination OID is present. TheOID field502 may further include a source class, which indicates whether the source OID is a user end-device likedevice402 ofFIG. 4, or a network node, and a destination class, which indicates whether the destination OID is an OID associated with content or a network node. Additionally, theOID field502 may include any number of flags or indicators that are described in more detail herein. Thepayload503 of the request forcontent500 may include any general purpose data and control information.

A device may use the request forcontent500 for content retrieval. If the device is aware of the IP address of a node in the network that stores the requested content, the device may include the IP address of the node in the destination IP address field in theIP field501. However, if the device does not know the IP address of the node that stores the requested content, the device may include a broadcast IP address, or a multicast IP address. The broadcast IP address or the multicast IP address may result in the request for content being delivered to one or multiple nodes as dictated by the broadcast IP address or multicast IP address. The destination IP address may also be an address of any node in the network to which the request for content is directed.

If the device knows the OID of the requested content, the device may include the OID in the destination OID field of theOID field502. If the device does not know the OID of the requested content, the device may include a null value in the destination OID field. Further, if the device does not know the OID of the content, a search may be performed for the OID based on information such as a title, an author, or keywords of the requested content. The device may include the device's OID in the source OID of theOID field502.

Referring back toFIG. 4, nodes in a network may exchange among each other the OIDs of content that thenodes401 store. Based upon the exchanged OIDs, a node, for example,node401_A, may develop a local directory associating an OID with another node, for example,node401_B, that stores the content of the OID. Thus, upon receiving a request for content,node401_Amay route the request for content tonode401_Bthat stores the content and the content may be retrieved more readily fromnode401_B.

As may be recognized, content retrieval based on an OID offers flexibility compared to content retrieval using an IP address of where the content is stored. OIDs offer unique identification of content and, thus, lend thenodes401 the capability to improve efficiency in content retrieval.

FIG. 6 shows a method of retrieving content based on an OID. A first node receives a request forcontent601. The request for content may have an integrated IP address and an OID. The first node determines whether a destination OID is included in the request forcontent602. The first node may determine whether a destination OID is included by checking the protocol field in the IP field, for example,IP field501, or the type field in the OID field, for example,OID field502, of the request for content. If a destination OID is not included in the OID field of the request for content, the first node routes the request for content using the IP field. If a destination OID is included, the first node determines whether the content is stored in the first node'slocal cache604. If the content is stored in the first node's local cache, the first node provides the content to the node or device that requested thecontent605.

If the content is not stored in a local cache, the first node looks-up the content in alocal directory606 and determines whether a second node stores thecontent607. If the first node determines that the content does not match an entry in the local directory, first the node resolves the request for content usingother means608 described herein.

If the first node determines that a second node stores the content, the node may set a flag (referred to herein as a content location resolved flag) in the OID field of the request forcontent609. The content location resolved flag indicates that the location of the content has been resolved and may be used by intermediary nodes as described herein.

The first node then sends the request for content to thesecond node610. The first node may send the request for content to the second node by including the second node's IP address in the destination IP address of the IP field of the request for content. The first node may determine that there are multiple nodes that either store the content or know where the content is stored and may determine whether to send the request for content to one or more of the multiple nodes. A multicast IP address may be used for the purpose of sending the request for content to multiple nodes.

A request for content for which the content location resolved flag is set may reach the second node without passing any intermediary nodes, (i.e., a one-hop connection exists), or may be received by an intermediary node before reaching the second node. If the request for content is received by an intermediary node, the intermediary node may determine whether the requested content may be provided more readily by the second node or by another node within the network, as described with reference toFIG. 7 herein.

FIG. 7 shows a method of retrieving content based on an OID. An intermediary node receives a request forcontent701. The intermediary node determines whether the requested content is stored in alocal cache702. If the requested content is stored in the local cache, the node intermediary provides the requestedcontent703 and discards the request forcontent704, (i.e., the request for content does not reach the second node). If the requested content is not stored in the local cache, the intermediary node performs an OID look-up in alocal directory705 and determines whether a third node within the network stores thecontent706.

If a third node stores the content, the intermediary node then determines whether the content location resolved flag is already set707. If the content location flag is not already set, the intermediary node sets the content location resolvedflag708 and sends the request for content to thethird node709. If the content location resolved flag is already set, the intermediary node determines whether the third node is able to provide the content more readily than thesecond node710, whereby if a positive determination is made then the intermediary node sends the request for content to thethird node709 and if a negative determination is made then the intermediary node sends the request for content to thesecond node711.

If after performing a look-up in a local directory, the intermediary node is unsuccessful in locating a node that stores the content, the intermediary node determines whether the content location resolved flag is set712. If a positive determination is made, the intermediary node sends the request for content to thesecond node711. If a negative determination is made, the intermediary node resolves the request for content usingother means713.

If a node is unsuccessful in locating the storage location of content, the node may propagate a request for content to other nodes in the network to inquire whether the content is stored in other nodes in the network. Because propagating requests for content may quickly overwhelm the network and cause increased traffic and congestion due to the requests, a node propagating a request for content may set an expiration of the request. Nodes that receive the request for content may only acknowledge the request if the request has not expired. If the request has expired, on the other hand, the nodes that receive the request may simply discard the request. Therefore, requests for content are prevented from congesting the network.

A request for content may be set to expire after a specified number of hops, (i.e., the number of network nodes that handle the request), or after a specified time period. The time-to-live (TTL) field of the IP field of the request for content may be set to a value indicating the expiry. If the TTL is specified according to the number of hops the request for content takes, each receiving node may decrement the TTL field and forward the request for content, as described with reference toFIG. 8 herein.

FIG. 8 shows a method of processing a request for content having a TTL field. A first node receives a request forcontent801. The first node determines whether the content is stored in alocal cache802. If the content is stored in a local cache, the first node responds to the request forcontent803, (for example, by providing the requested content), and discards the request forcontent804. If the content is not stored in a local cache, the first node determines whether a second node stores thecontent805, (for example, by looking-up the OID in a local directory). If the first node determines that a second node stores the content, the first node responds to the request for content, (for example, by providing an address of the second node), and discards the request for content. If, however, the first node determines that it is not aware of other nodes that store the content, then the first node determines whether it may propagate the request for content or if the request for content has expired. To do so, the first node determines whether the TTL field is greater than zero806. If the TTL field is greater than zero, then the first node decrements the TTL field and sends a request for content to other nodes in thenetwork807, (for example, by using broadcast or multicast). If the first node determines that the TTL field is not greater than zero, then the request for content has expired and the first node discards the request forcontent808.

A node in a network, forexample network400 ofFIG. 4, may be aware of the presence of other nodes in the network. In addition, a node may have information about the identities, (for example, IP addresses), and the capabilities, (for example, presence of a local cache, presence of a local directory, ability to process an OID, or ability to process an IP address) of other nodes in the network. For example, a node may advertise its own capability and identity and receive information about the capability and identity of other nodes in the network. Sharing information between nodes may be done via a link-state protocol, such as open shortest path first (OSPF) for intra-domain routing, border gateway protocol (BGP) for inter-domain routing or intermediate system to intermediate system (IS-IS).

Knowing the identity and capability of nodes in a network enables the distribution and load-balancing of content routing and retrieval among the nodes. A node may be designated as a location resolver (LR) of particular content and may be assigned the responsibility of identifying the location of where the content is stored. A node may be designated as an LR of particular content based on the OID of the content.

A hash function may be applied to the identities, (for example IP addresses or OIDs), of all known network nodes. A hash function, as is known in the art, is a subroutine that is utilized in mapping a large data set to a smaller data set. The application of the hash function to the identities of known network nodes will result in the creation of a hash ring as described with reference toFIG. 9 herein. The hash function may be also applied to the OID of content. The LR of particular content is determined based on the hash function values of the identities of networks nodes and the OID of the content.

FIG. 9 shows a hash ring for determining the LR of particular content. In thehash ring900, a hash function, H(x), is applied to the identities of nodes of the network, Ni ID, to generate hash function values, H(Ni ID)901-904, for each node in the network. Further, the hash function is also applied to the OID of the content to generate a hash function value H(OID)905. InFIG. 9, H(OID)905 lies between H(N3 ID)903 and H(N4 ID)904.

The LR may be determined to be the node whose identity is N3 ID because the H(N3 ID)903 is the closest hash function value of node identities not exceeding H(OID)905. Other criteria may be used to determine the LR. For example, the LR of the content may be determined to be the two nodes whose identities are N3 ID and N4 ID because H(N3 ID)903 and H(N4 ID)904 are the closest to H(OID).

Thehash ring900 ofFIG. 9 may be a distributed hash table (DHT) and the formation of thehash ring900 may be facilitated by the fact that nodes in a network are aware of the identities and capabilities of other nodes in the network, for example, using OSPF or BGP information. Further, all nodes in the network may be able to form thehash ring900 and utilize it for content routing and retrieval. Thehash ring900 ofFIG. 9 may also be said to be one-hop because a node is able to directly determine an LR node without the need to utilize an intermediary node.

When a node desires to retrieve content with a particular OID, the node may determine the LR node for the content by applying the hash function as shown with reference toFIG. 9. The node may request from the LR node information regarding where in the network the content is stored. The LR may supply this information to the requesting node and the requesting node may request the content from the node that stores the content.

Because different content has varying OIDs and the hash function values of varying OIDs may be different or the same, utilizing a hash function for determining the LR of content uniformly distributes location resolution tasks in the network.

A publishing node that is aware of the storage location of content may determine the LR of that content based on the OID. The publishing node may send information to the LR indicating that the publishing node is aware of the storage location of the content, as described with reference toFIG. 10A herein. The information, referred to as a location object (LO), may include the OID of the content and the identity of the publishing, among other parameters. The LR retains the LO and supplies the LO to nodes that are interested in retrieving the stored content using the publishing node.

FIG. 10A shows a method of location resolution. In the method, a publishing node generates a location object (LO) for the storedcontent1001.FIG. 10B shows alocation object1050. TheLO1050 may include the OID of the storedcontent10501, an identity of thepublishing node10502, ascope field10503, and atimeout field10504. Thescope field10503 may indicate any limitation on publication of theLO1050, (i.e., any restriction on who may know that the content is published). Thetimeout field10504 may indicate a valid time for theLO1050, (i.e., after the timeout expires the node no longer stores the content).

Referring back toFIG. 10A, once theLO1050 for the stored content is generated1001, the node determines the LR of the stored content by applying a hash function to the OID of the stored content and selecting as LR the node whose H(N ID) is closest but not exceeding the hash function value of the OID. After determining the LR, the node sends theLO1050 to theLR1003.

FIG. 11 shows a method of requesting content using an LR. A node that is interested in locating content applies a hash function to the OID of thecontent1101. The node may then determine the LR of the content based on the hash function value of theOID1102, (for example, by applying a hash function to the OID of the stored content and comparing the hash function value of the OID with the hash function value of node identity). The node may then request the identity of the publishing node from theLR1003. The LR may check the LO and provide the identity of the publishing node to the requesting node. Alternatively, the LR may provide the entire LO to the node. The node receives the identity of the publishing node from the LR1004. The node requests the content from the publishing node1005. The publishing node may retrieve the content and provide the content to the node.

As previously described, the scale of the Internet is larger than shown inFIG. 4. Further, an Internet network may comprise multi-tier hierarchical networks and may have various autonomous systems, domains, or routing areas. Accordingly, the network ofFIG. 4 may also be a routing area, a domain, or an autonomous system in an Internet network.FIG. 12 shows an example of a multi-tier hierarchical Internet network. In thenetwork1200, routing areas1201-1205 comprise connected nodes. The routing areas1201-1203 are the lowest tier in thenetwork1200. Routing areas1201-1203 are connected todomain1206 and

routing areas

1204,1205 are connected todomain1207. The

domains

1206,1207 also comprise connected nodes.Domain1206 is connected to autonomous system (AS)1208 anddomain1207 is connected to AS1209. AS1208 and AS1209 also comprise connected nodes. AS1208 and AS1209 are peering as shown by their connectivity. It is recognized that thenetwork1200 may have additional AS tiers that are not shown inFIG. 12. Thenetwork1200 may be an IP network that is deployed and equipped with OID processing capability without modifying an underlying IP structure of thenetwork1200. Further, thenetwork1200 may be a content-oriented network (CON), a content delivery network (CDN), or an information-centric network (ICN), where OID services co-exist with other IP services such as host-to-host communications.

Hash functions may be used in producing hash function rings in any one of the tiers (for example, routing area, domain, or AS) ofnetwork1200 as described herein.

FIG. 13 shows hash function rings for a domain and routing areas. Routing areas1301-1303 inFIG. 13 correspond to routing areas1201-1203 inFIG. 12 and domain1304 inFIG. 13 corresponds todomain1206 inFIG. 12. InFIG. 13, each routing area1301-1303 has nodes that are part of the routing area's respective hash ring1311-1313.Routing area1301 hasnodes1321_1-7that are part ofhash ring1311, routing area1302 hasnodes1322_1-5that are part of hash ring1312, androuting area1303 hasnodes1323_1-6that are part ofhash ring1313. As previously described, the hash rings1311-1313 are generated by applying a hash function to the identities of

nodes

1321_1-7,1322_1-5, and1323_1-6, respectively.

Routing areas1301-1303 are connected to domain1304. Further, the domain1304 has a backbone hash ring1314 that is also generated by applying the hash function to the nodes of the domain1304. An area border node (ABN)1321₁-1323₁is designated where the routing areas1301-1303 connect to the domain1304. The ABN1321₁-1323₁is shared between a routing area's hash ring1311-1313 and a domain's backbone hash ring1314.

The backbone hash ring1314 for the domain1304 and the hash rings1311-1313 of the routing areas1301-1303 ofFIG. 13 are said to form a multi-level distributed hash table (DHT) which reflects the topology of the associated domain1304 and routing areas1311-1313. At the routing area tier, a DHT if formed using OSPF link state information. Further, a backbone DHT is formed at the domain tier for intra-routing area routing. A node, for example,ABN1321₁, that is connected to domain1304 androuting area1301 may join the backbone DHT of the domain1304 and the DHT of therouting area1301.

For inter-domain routing (not shown inFIG. 13), multi-level DHTs may be formed using the information provided by BGP that reflects the Internet hierarchy and peering relationship among Autonomous Systems (ASes). A node may join multiple DHTs, and the DHTs may be interconnected in a tree-like form with multi-homing. Location information of content object is published in the multi-level DHTs and at each level summarization may be performed based on content popularity and DHT level.

ABNs1321₁-1323₁may be utilized for facilitating content retrieval between routing areas1301-1303 and the domain1304. An ABN1321₁-1323₁may summarize the OIDs of content stored in the ABN's routing area1301-1303. The summarization of OIDs may serve to indicate to other routing areas and the domain whether content is stored within the ABN's routing area.

An LR node, for example,node1321₂, in an ABN's routing area, for example,ABN₁1321₁inrouting area1301, may provide the OIDs of LOs it maintains to theABN1321₁. Having received the OIDs fromLR node1321₂in its routing area, the ABN may receive requests for content from other routing areas, for example, routing areas1302-1303, and indicate whether or not the content sought is stored in the ABN'srouting area1301 based on whether theABN1321₁retains the OID of the content sought. However, maintaining an exhaustive list of OIDs for all content stored in arouting area1301 may strain the computational and storage resources of theABN1321₁. Further, OID traffic may consume extensive bandwidth in a network. To enable efficient content location and retrieval, OID summarization may be employed, whereby summary OIDs may be sent to and retained by theABN1321₁. OID summarization uses common fields of OIDs to improve efficiency. OID summarization may utilize Bloom filters that are know in the art.

FIG. 14 shows an example of OID summarization. OIDs 1-41411_1-4each have six TLVs, TLV_1-61401-1403,1404_1-4-1406_1-4. At least TLV_1-31401-1403 are the same for theOIDs1411_1-4. TLV_1-31401-1403 are referred to as prefix TLVs. TLVs TLV_4-61404_1-4-1406_1-4(referred to as suffix TLVs), however, may be different. Asummary OID1411₅is generated by retaining the prefix TLV, TLV_1-31401-1403, and applying Bloom filters1421-1423 to the suffix TLVs TLV_4-61404_1-4-1406_1-4to producedigests1407_4-6, respectively. Thedigests1407_4-6are then appended with a type field1408_4-6, a length field1409_4-6, and a number of fields summarized field1410_4-6to produce digestTLV_4-61404_4-6.

Asummary OID1411₅generated using Bloom filters may be queried or tested to determine whether an OID of interest is one of theOIDs1411_1-4used to generate thesummary OID1411₅. The result of a Bloom filter test may be negative, (i.e., indicating that an OID of interest was not used in generating the summary OID1411₅), or positive, (i.e., indicating that the OID of interest was in fact used in generating the summary OID1411₅). However, the cost of TLV summarization using Bloom filters is that a false positive may occur, (i.e., a test determining that the OID of interest was used in generating thesummary OID1411₅, when in fact the OID was not used in generating the summary OID1411₅). A false negative, on the other hand, may not occur in Bloom filters. Further, the likelihood of a false positive query or test outcome increases as the number of OIDs1411_1-4summarized increases.

To control the likelihood of false positives, limits may be imposed on the number of OIDs1411_1-4used in generating asummary OID1411₅. Further, when the number of OIDs1411_1-4summarized is higher than a limit, multiple digest TLVs, may be generated for each TLV field. Each of the digestTLVs1404_4-6associated with a TLV field1404_1-4-1406_1-4may be tested to determine whether an OID was used in generating the digestTLVs1404_4-6.

An LR node may summarize theOIDs1411_1-4of content for which it retains LOs and generate asummary OID1411₅. Similar to an LO that is generated based upon an OID, an LR node may generate a summary location object (SLO) based upon thesummary OID1411₅.

FIG. 15 shows an SLO. TheSLO1500 comprises asummary OID1501, an identity ofpublishing node1502, ascope field1503, and atimeout field1504. As with an LO, thescope field1503 represents the manner in which theSLO1500 may be published, (for example, routing areas, domains, or autonomous systems that may know that the content is stored and may be able to request it), and thetimeout field1504 represents an expiration of the storage of the content associated with theSLO1500. It is noted that content having differing scopes and timeouts may be grouped according to their respective scopes and timeouts, and the OIDs of the content may be summarized accordingly, thus facilitatingmeaningful SLO1500 generation.

An LR node may generate SLOs for content for which the LR node retains LOs. The LR node may provide the SLOs to an ABN of the LR node's routing area. Additionally, the ABN may receive SLOs from other LRs in the ABN's routing area. The ABN may further summarize the summary OIDs of the SLOs it receives from LRs within the ABN's routing area. For further summarization, prefix TLVs are retained whereas digests of digest TLVs are “ORed”, (i.e., by applying a logical disjunction function), for producing a new summary OID. The ability to further summarize OID using a logical disjunction function is due to the nature of the Bloom filters that generate the digest TLVs.

For example, the ABN may receive two SLOs having summary OIDs with the same prefix TLVs but differing digest TLVs. The ABN may further summarize the two SLOs by retaining the prefix TLVs and generating new digest TLVs based on ORing the digests of the digest TLVs.

In a backbone hash ring, SLOs may be distributed among the nodes, (for example, ABNs), of the backbone hash ring using a hash function. The distribution of the SLOs among the nodes of the backbone hash ring facilitates the load balancing of content retrieval tasks. For a particular SLO, a node in the backbone hash ring is designated as a backbone location resolver node (BLRN). The BLRN stores theSLO1500 and services requests for content for theSLO1500. The BLRN may service request for content from any routing area connected to the backbone hash ring or other domains and autonomous systems.

When a node in the backbone hash ring, (for example, an ABN), receives an SLO, the node determines a backbone location resolver node (BLRN) in a backbone hash ring that is designated to store the SLO. As with determining an LR for a particular LO, to determine a BLRN node for an SLO a hash function is applied to the prefix TLVs, (i.e., the unsummarized TLVs of the summary OID). Then the hash function value of the prefix TLVs is compared with the hash function value of the node identities of the backbone. It is recognized that it is advantageous to determine the BLRN based on the prefix TLVs of the summary OID because the prefix TLVs do not change as the number of summarized OIDs change.

For example, the BLRN may be the node in the backbone whose identity hash function value is closest but not greater than the hash function value of the prefix TLVs of the summary OID. Alternatively, the BLRN may be one or more nodes whose identity hash function value is closest to the hash function value of the prefix TLVs of the summary OID.

After determining the BLRN for a summary OID, an ABN may send the SLO associated with the summary OID to the BLRN. The BLRN may retain the SLO and service requests for content from routing areas, domains, or autonomous systems. The BLRN may also receive SLOs for which the BLRN is designated as a location resolver from other ABNs in the backbone hash ring.

FIG. 16 shows a flow diagram of a method for publishing an SLO. AnLR node1601 generates asummary OID1604. The summary OID is generated for content having the same prefix TLVs. TheLR node1601 also generates an SLO for thesummary OID1605. TheLR node1601 sends the SLO to anABN16021606. TheABN1602 may belong to the routing area of theLR node1601.

TheABN1602 may further summarize thesummary OID1607, (i.e., if the ABN receives two or more SLOs having the same prefix TLVs). TheABN1602 may also determine aBLRN1603 based on the prefix TLVs of thesummary OID1608. TheABN1602 may send the SLO to theBLRN16031609. TheBLRN1603 stores the SLO and services content location resolution requests based on theSLO1610.

FIG. 17 shows a flow diagram of a method for retrieving content based on an OID. In themethod1700, anode1701 seeks to request content based on an OID of the content. Thenode1701 determines an LR node for thecontent1710. Thenode1701 sends a request for content to theLR1711. The LR determines whether the LR has an LO for thecontent1712.

If the LR node determines that it has an LO for the content, the LR sends the LO to thenode17011713. Thenode1701 requests the content based on theLO1714, (i.e., thenode1701 determines a publishing node of the content based on the LO and sends a request for content to the publishing node, which retrieves the content from a storing node). Alternatively, theLR1702 may retrieve the content on behalf of thenode1701.

If the LR determines that it does not have an LO for the content, the LR sends a response to the node indicating that an LO match is not found1715. Thenode1701 may inquire as to whether the content is stored by a node in another routing area.

Thenode1701 may also send a request to anABN17031716. TheABN1703 is part of the routing area of thenode1701 and is also part of a backbone hash ring. TheABN1703 determines aBLRN1704 of the content based on theOID1717. TheBLRN1704 is part of the backbone hash ring and may also be part of a routing area that is different than the routing area of thenode1701.

TheABN1703 sends a request for content to theBLRN17041718. TheBLRN1704 determines whether it has an SLO for thecontent1719. If theBLRN1704 determines that the BLRN has an SLO for the content, theBLRN1704 responds to theABN1703 with theSLO1720. Further, if theBLRN1704 determines that theBLRN1704 has more than one SLO for the content, theBLRN1704 responds to theABN1703 with the more than one corresponding SLOs. Multiple corresponding SLO may indicate that multiple nodes may publish the content. Further, nodes that publish the content may be in different routing areas. TheABN1703 may request the content on behalf of thenode1701.

It is recognized that due to OID summarization in SLOs, false positives may occur, (i.e., anABN1703 may receive an SLO from theBLRN1704 when in fact the content is not stored as indicated by the SLO). In order to minimize the delay incurred in requesting content based on an SLO that is a false positive, upon receiving multiple SLOs, theABN1703 may send requests for the content at once based on all the SLOs, (i.e., in parallel). Alternatively, anABN1703 may issue a request for content based on one SLO then wait to receive the content or receive an indication that the content is not found before issuing another request for content based on another SLO.

FIG. 18 shows a flow diagram of a method for retrieving content. In themethod1800,ABN₁1801, (for example,ABN1703 inFIG. 17), has received an SLO associated with desired content as described with reference toFIG. 17.ABN₁1801 is part ofRouting Area 1 and the SLO indicates that a node inRouting Area 2 may publish the content.ABN₁1801 is also part of a backbone hash ring along withABN₂1802, wherebyABN₂1802 is part ofRouting Area 2.ABN₁1801 sends a request for content toABN₂18021810.ABN₂1802

queries LR

1803 ofRouting Area 2 as to whether theLR1803 has an LO for thecontent1811. Based on the OID of the content, theLR1803 determines whether it has an LO for thecontent1812. If theLR1803 determines that it does not have an LO for the content, theLR1803 indicates toABN₂1802 that an LO is not found1813.ANB₂1802 indicates toABN₁1801 that an LO is not found for the content. Therefore, a false positive due to OID summarization has occurred.ABN₁1801 may attempt to retrieve based on another SLO if there are any.

If theLR1803 determines that an LO for the content is present, theLR1803 provides the LO toABN₂18021814. The LO indicates the node publishing the content, (i.e., node1804).ABN₂1802 may then request the content fromnode18041815 andnode1804 may retrieve the content from a storing node and provide the content toABN₂18021816.ABN₂1802 may in turn provide the content toABN₁1801.ABN₁1801 may also provide the content to a node in Routing Area 1 (not shown).

A request for content, for example,request1810 andrequest1815, may, therefore, be forwarded along the shortest path in a network, for example, fromABN₁1801 toABN₂1802 and then topublishing node1804 and any storage node. The requested content, for example,

content

1816 and1817, (or, in some embodiments, an indication to establish a content retrieval session, for example) may be sent to the requester along the same path, for example, from a storing node topublishing node1804 toABN₂1802 and then toABN₁1801. Content caching may be performed by any intermediary node along the path.

Multi-level topology-aware one-hop DHTs may be utilized to provide distributed content resolution and efficiently locate content. As described herein, the closest copy of a particular content object is located. Further, OID resolution is integrated into the routing and forwarding process. Additionally, OID summarization is used in higher-level DHTs to reduce control overhead and state requirements for better scalability.

In an embodiment, an OID may be self-certifying and flat having the form of P:L, where P represents a cryptographic hash of a principal's public key, L represents a flat label, and the colon represents a delimiter. Different content may have the same P value but differing L values. For example, a first content may have an OID of P:L₁, a second content may have an OID of P:L₂, and an Nth content may have an OID of P:L_N. A summary OID may be generated by applying a Bloom filter to the L values, where the summary OID may be P:digest(L) and the digest(L) is generated by applying a Bloom filter to L₁, L₂, . . . , L_N, i.e., digest(L)=Bloom-Filter{L₁, L₂, . . . , L_N}.

In another embodiment, Bloom filter summarization may be applied to hierarchical OIDs such as /example.com/news/title. For example, a summary OID of the form of /example.com/news/digest(titles) may be used to summarize content whose name or OID starts with the same prefix, /example.com/news, but having differing titles.

As previously described, to query whether an OID was utilized in generating a summary OID, the unsummarized portion of the summary OID, i.e., the prefix of the summary OID, may match the prefix of the OID, whereas the digest of the summary OID is required to yield a positive test indicating that the corresponding suffix element in the queried OID was used in generating the summary OID.

The likelihood of false positives may also be controlled by designing appropriate Bloom filters. Given a Bloom filter, a node may control the number of OIDs used in generating a summary OID based on the popularity of content or based on a distance to the content location thus balancing between network resource and the likelihood of false positives. For example, content residing in a local network domain may not be summarized if the content is likely to be requested with a high probability from within. However, a domain may utilize summarization for publishing the content within the domain to outside other domains.

As previously described the number of OIDs used to generate a summary OID may be limited to control the probability of false positives. When the number of OIDs exceeds the limit, the OIDs are divided into groups, whereby each group may be used to generate a digest as follows:

P:digest1(L):digest2(L):digest3(L).

In one embodiment, an OID may be made a secure OID. In a secure OID, a publisher code is a public key of the publisher or a hash value of a public key of the publisher. Further, a secure OID may be signed by generating a signature using a private key associated with a public key of the publisher. The signature may be appended to the OID to form a self-certifying OID. By checking the signature, the authenticity of content may be verified.

In another embodiment, an OID may be appended with an OID length field, whereby the OID length field represents the length of the OID, (for example, the total size (in bits or bytes), of the OID). In an embodiment, an OID for content may be generated by applying a hash function to the file of the content, or by applying a hash function to a name of the content, (for example, a human-readable name such as a movie title or a song title).

A secure ID may be created by an assignor and may take the form of Assignor Code:Assignee ID:Signature. The colon in the secure OID is a delimiter that may not be present in the secure ID. In the secure ID, the Assignor Code is a public key or a hash value of a public key of the assigner. The Assignee ID is an ID assigned by the assigner.

The secure ID may also be self-certifying and hierarchical. The secure ID may be concatenated to form a tree. For example,Assignor 1 Code:Assignee 2 ID:Signature 1:Assignor 2 Code:Assignee 3 ID:Signature 2 may be a secure ID, whereAssignor 1 has assigned an ID (Assignee 2 ID) toAssignor 2. Further,Assignor 2, having a code ofAssignor 2 Code, has assigned an ID to Assignor 3 (Assignee 3 ID).Assignor 2 ID may be a public key ofAssignor 2 or a hash value of the public key ofAssignor 2. Further,Assignor 2 code may be the same asAssignor 2 ID, (for example,Assignor 2 public key or a hash value of a public key of Assignor 2).

It is recognized that OID summarization may be performed at any tier in a network, (for example, Autonomous System or domain), and SLOs may generated and propagated up in a network's hierarchy to a higher tier as described herein. Further, a network's higher tiers may be queried for content as described herein, (for example, upon exhausting content retrieval alternatives in lower network tiers). OID summarization using Bloom filters is advantageous in that it results in a reduction of update overhead and achieves network scalability while relieving the suffix hole disadvantages of prefix-based summarization.

It is also recognized that when a node is added to a hash ring, (for example,hash ring1311 ofFIG. 13), or when a node of the hash ring becomes defective or experiences a failure, a content's designated LR may change accordingly. Nodes in a routing area may monitor a link-state protocol, (for example OSPF), for information about node additions or deletions and upon determining that due to a node addition or deletion a designated LR of content has changed to a new LR, the node may send the content's LO to the new LR. Further, nodes in a routing area may be configured to periodically send a content's LO to the designated LR.

Further, an LO maintained by an LR that is no longer a designated LR for a content will eventually expire at the expiration of the timeout field. Similarly, an SLO maintained by a BLRN that is no longer a designated BLRN will also expire at the expiration of the timeout field.

In an embodiment, multiple LR nodes for a content may be determined using multiple hash functions, or multiple keys of a hash function. Further, an LO for the content may be sent to and maintained by the multiple LR nodes. Similarly, multiple BLRN nodes may be determined using multiple hash functions, or multiple keys of a hash function and an SLO may be sent to and maintained by the multiple BLRN nodes.

In one embodiment, routing based on OID may be a layer in a protocol stack above the IP layer and below a user datagram protocol (UDP) or a transmission control protocol (TCP) of the transport layer.

In another embodiment, an IP header of a request for content may include a frame offset field, an identification field, or a flag field. The frame offset field, identification field, or flag field may be used to identify a fragment of an IP datagram, such as content. An offset indicated by the offset field may be relative to a beginning of an original unfragmented IP datagram.

EMBODIMENTS

1. A method for content identification, routing, and retrieval in the internet.

2. The method ofembodiment 1 comprising: utilizing an object identifier (OID) for content identification.

3. The method as in any one of the preceding embodiments wherein the OID comprises type-length-value (TLV) fields.

4. The method as in any one of the preceding embodiments wherein a TLV field is comprised of a type field, a length field, and a value field.

5. The method as in any one of the preceding embodiments wherein type field represents the type of the TLV field, the length field represents the length of the TLV field, the value field represents the value of the TLV.

6. The method as in any one of the preceding embodiments comprising: utilizing an OID to identify a device, or a node in a network

7. The method as in any one of the preceding embodiments comprising: processing a content's OID and retrieving content based on the content's OID.

8. The method as in any one of the preceding embodiments comprising: processing an Internet Protocol (IP) addresses and retrieving content based on the IP address of where content is stored

9. The method as in any one of the preceding embodiments comprising: processing both an OID and an IP address and retrieving content based upon any combination of the content's OID or an IP address of where the content is stored.

10. The method as in any one of the preceding embodiments comprising: sending a request for content to a network.

11. The method as in any one of the preceding embodiments comprising: routing and propagating the request for content based on an IP address, an OID, or both an IP address and an OID.

12. The method as in any one of the preceding embodiments wherein the request for content includes an IP field and an OID field.

13. The method as in any one of the preceding embodiments comprising: exchanging with another node OIDs of content that is stored.

14. The method as in any one of the preceding embodiments comprising: maintaining a directory associating an OID with another node that stores the content of the OID.

15. The method as in any one of the preceding embodiments comprising: routing a request for content to node that stores the content.

16. The method as in any one of the preceding embodiments comprising: maintaining a local cache of content.

17. The method as in any one of the preceding embodiments comprising: setting a content location resolved flag on a condition that a second node stores the content.

18. The method as in any one of the preceding embodiments comprising: setting an expiration for the request for content.

19. The method as in embodiment 18 wherein the expiration is represented by a time-to-live (TTL) field.

20. The method as in any one of the preceding embodiments comprising: reissuing a request for content with an incremented TTL.

21. The method as in any one of the preceding embodiments comprising: receiving information about the identities and the capabilities of other nodes in a network.

22. The method as in any one of the preceding embodiments wherein a node is designated as a location resolver (LR) of particular content and is assigned the responsibility of identifying the location of where the content is stored.

23. The method as in any one of the preceding embodiments comprising: determining an LR by applying a hash function to a node identity to produce a first hash function value and applying a hash function to an OID of content to produce a second hash function value and comparing the first hash function value with the second hash function value.

24. The method as in any one of the preceding embodiments further comprising: sending a location object (LO) to the LR.

25. The method as in any one of the preceding embodiments comprising: generating a summary OID.

26. The method as in embodiment 25 comprising: sending the summary OID to an area border node (ABN).

27. The method as in any one embodiments 25 or 26 wherein the summary OID is generated by applying a Bloom filter to OIDs.

28. The method as in any one of the preceding embodiments comprising: testing the summary OID to determine whether an OID of interest is one of the OIDs used to generate the summary OID.

29. The method as in any one of the preceding embodiments comprising: generating a summary location object (SLO) based on a summary OID.

30. The method as in any one of the preceding embodiments comprising: further summarizing two SLOs by retaining prefix TLVs and generating new digest TLVs based on ORing the digests of the digest TLVs.

31. The method as in any one of the preceding embodiments comprising: designating a backbone location resolver node (BLRN) for an SLO.

32. A node in an Internet Protocol (IP) network comprising: a receiver configured to receive one or more object identifiers (OIDs); a processor configured to generate a summary OID based on the one or more OIDs by applying a Bloom filter to the one or more OIDs; and a transmitter configured to transmit the summary OID.

33. The node of embodiment 32, wherein the summary OID is comprised of type-length-value (TLV) fields.

34. The node of embodiment 33, wherein a prefix TLV field of the summary OID is the same as a prefix TLV of the one or more received OIDs.

35. The node of embodiment 33, wherein a suffix TLV field of the summary OID is generated by applying a Bloom filter to a suffix TLV of the one or more received OIDs to generate a digest and by appending a type field, a value field, and a number of OIDs summarized field to the digest to produce the suffix TLV.

36. The node of embodiment 32, wherein the summary OID is capable of being tested to determine whether an OID is one of the one or more received OIDs.

37. A node in an Internet Protocol (IP) network comprising: a processor configured to determine a location resolver (LR) node associated with content based on an object identifier (OID) associated with the content by applying a hash function to the OID associated with the content to produce a first hash function value and by applying the hash function to an identity associated with each of a plurality of nodes to produce a plurality of second hash function values, and by comparing the first hash function value to the plurality of second hash function values to determine an LR node associated with the content; and a transmitter configured to send a location object (LO) associated with the content to the determined LR node.

38. The node of embodiment 37, wherein the first hash function value is greater than or equal to the second hash function value for the determined LR node.

39. The node of embodiment 37, wherein the LO comprises the OID associated with the content.

40. The node of embodiment 39, wherein the LO further comprises an identity of a node storing the content, a scope field, and a timeout field.

41. A content delivery network (CDN) comprising: a first node comprising: a first node receiver configured to receive a request for content, the request for content identifying content using an object identifier (OID) associated the content; and a first node processor configured to determine whether the content is stored in a local cache of the first node based on the OID associated the content, wherein on a condition that the content is not stored in the local cache of the first node, the first node further comprises a first node transmitter configured to send the request for content to a second node; and a second node comprising: a second node receiver configured to receive the request for content from the first node; and a second processor configured to determine whether a location object (LO) is maintained for the content, wherein on a condition that an LO is maintained for the content, the second node further comprises a second node transmitter configured to send to the first node an indication of a location for retrieval of the content.

42. The CDN of embodiment 41, wherein the second node is a location resolver (LR) node.

43. The CDN of embodiment 42, wherein the first node is configured to determine the second node by applying a hash function to the OID associated with the content to produce a first hash function value and by applying the hash function to an identity associated with each of a plurality of nodes to produce a plurality of second hash function values, and by comparing the first hash function value to the plurality of second hash function values to determine the second node.

44. The CDN of embodiment 41, wherein the first node transmitter is further configured, on a condition that the content is stored in the local cache of the first node, to provide the content.

45. The CDN of embodiment 41, wherein the OID of the content is comprised of type-length-value (TLV) fields.

46. An Internet-enabled device for requesting content from a network, the device comprising: a processor configured to generate a request for content, wherein the request for content comprises an object identifier (OID) associated with the content, and wherein the OID comprises one or more type-length-value (TLV) fields; and a transmitter configured to transmit the request for content comprising the OID to a node of the network.

47. The Internet-enabled device of embodiment 46, wherein a value field of the OID comprises a country or group code, a publisher code, a title code, a format or type code, a timestamp, or a duration.

48. A base station configured to perform a method as in any one of embodiments 1-31.

49. An evolved Node B configured to perform a method as in any one of embodiments 1-31.

50. A Node B configured to perform a method as in any one of embodiments 1-31.

51. An integrated circuit configured to perform a method as in any one of embodiments 1-31.

52. A method as in any one of embodiments 1-31 performed in Institute of Electrical and Electronics Engineers (IEEE) 802.11.

53. A method as in any one of embodiments 1-31 performed in Long Term Evolution (LTE) wireless communications.

54. A method as in any one of embodiments 1-31 performed in Long Term Evolution-Advanced (LTE-A) wireless communications.

Although features and elements are described above in particular combinations, one of ordinary skill in the art will appreciate that each feature or element can be used alone or in any combination with the other features and elements. In addition, the methods described herein may be implemented in a computer program, software, or firmware incorporated in a computer-readable medium for execution by a computer or processor. Examples of computer-readable media include electronic signals (transmitted over wired or wireless connections) and computer-readable storage media. Examples of computer-readable storage media include, but are not limited to, a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs). A processor in association with software may be used to implement a radio frequency transceiver for use in a WTRU, UE, terminal, base station, RNC, or any host computer.

Claims

What is claimed is:

1. A node in an Internet Protocol (IP) network comprising:

a receiver configured to receive one or more object identifiers (OIDs), wherein the one or more OIDs have an identical prefix OID;

a processor configured to generate a summary OID comprising the prefix OID and a suffix summary OID, the suffix summary OID having a digest, wherein the digest is generated based on the one or more OIDs by applying a Bloom filter to suffixes of the one or more OIDs; and

a transmitter configured to transmit the summary OID.

2. The node ofclaim 1, wherein the summary OID comprises type-length-value (TLV) fields.

3. The node ofclaim 2, wherein a prefix TLV field of the summary OID is the same as a prefix TLV of the one or more received OIDs.

4. The node ofclaim 2, wherein a type field, a value field, and a number of OIDs summarized field are appended to the digest to produce the suffix TLV.

5. The node ofclaim 1, wherein the summary OID is capable of being tested to determine whether an OID is one of the one or more received OIDs.

6-9. (canceled)

10. A content delivery network (CDN) comprising:

a first node comprising:

a first node receiver configured to receive a request for content, the request for content identifying content using an object identifier (OID) associated with the content; and

a first node processor configured to determine whether the content is stored in a local cache of the first node based on the OID associated with the content, wherein on a condition that the content is not stored in the local cache of the first node, the first node further comprises a first node transmitter configured to send the request for content to a second node; and

a second node comprising:

a second node receiver configured to receive the request for content from the first node; and

a second node processor configured to determine whether a location object (LO) is maintained for the content, wherein the LO includes a scope field, and a timeout field, and wherein on a condition that the LO is maintained for the content, the second node further comprising a second node transmitter configured to send the LO to the first node.

11. The CDN ofclaim 10, wherein the second node is a location resolver (LR) node.

12. The CDN ofclaim 11, wherein the first node is configured to determine the second node by applying a hash function to the OID associated with the content to produce a first hash function value and by applying the hash function to an identity associated with each of a plurality of nodes to produce a plurality of second hash function values, and by comparing the first hash function value to the plurality of second hash function values to determine the second node.

13. The CDN ofclaim 10, wherein the first node transmitter is further configured, on a condition that the content is stored in the local cache of the first node, to provide the content.

14. The CDN ofclaim 10, wherein the OID of the content comprises type-length-value (TLV) fields.

15. An Internet-enabled device for requesting content from a network, the device comprising:

a processor configured to generate a request for content, wherein the request for content comprises an object identifier (OID) associated with the content, and wherein the OID comprises one or more type-length-value (TLV) fields; and

a transmitter configured to transmit the request for content comprising the OID to a node of the network.

16. The Internet-enabled device ofclaim 15, wherein a value field of the OID comprises a country or group code, a publisher code, a title code, a format or type code, a timestamp, or a duration.