Content distribution system cache management

Content distribution system cache management may be provided. First, a sync packet may be received by a cache server from a first server. The sync packet may include a list indicating a cache server where a chunk is to be stored and the address for the chunk. Next, an address for the chunk may be obtained by the cache server by parsing the sync packet. The cache server may then determine that the chunk is not stored on the cache server by using the address for the chunk. Next, in response to determining that the chunk is not stored on the cache server, a connection may be opened between the first server and the cache server. The cache server may then receive the chunk over the connection and cache the chunk on the cache server.

TECHNICAL FIELD

The present disclosure relates generally to content distribution system management.

BACKGROUND

Segment Routing (SR) allows any node to select any path for each of its traffic classes. The path does not depend on a hop-by-hop signaling technique. It only depends on a set of “segments” that are advertised by the Intermediate System to Intermediate System (IS-IS) routing protocol. These segments act as topological sub-paths that can be combined together to form the desired path. There are two forms of segments: node and adjacency. A node segment represents a path to a node. An adjacency segment represents a specific adjacency to a node.

DETAILED DESCRIPTION

Overview

Content distribution system cache management may be provided. First, a sync packet may be received by a cache server from a first server. The sync packet may include a list indicating a cache server where a chunk is to be stored and the address for the chunk. Next, an address for the chunk may be obtained by the cache server by parsing the sync packet. The cache server may then determine that the chunk is not stored on the cache server by using the address for the chunk. Next, in response to determining that the chunk is not stored on the cache server, a connection may be opened between the first server and the cache server. The cache server may then receive the chunk over the connection and cache the chunk on the cache server.

Both the foregoing overview and the following example embodiment are examples and explanatory only, and should not be considered to restrict the disclosure's scope, as described and claimed. Further, features and/or variations may be provided in addition to those set forth herein. For example, embodiments of the disclosure may be directed to various feature combinations and sub-combinations described in the example embodiment.

Example Embodiments

Conventional content distribution systems (CDN) utilize a collection of web protocols paradigm (e.g., Hypertext Transfer Protocol (HTTP)) all operating at the application layers. While this may work well, they all share a number of design tradeoffs mostly due to their reliance on Domain Name System (DNS)+HTTP/Transmission Control Protocol (TCP)/Internet Protocol (IP) as the underlying protocol infrastructure. This may result in a number of limitations and technical tradeoffs that may not be good for streaming contents such as video. These limitations and technical tradeoffs may include: i) reliance on DNS combined with well-known servers for discovering delivery points may enforce a fairly static distribution model; ii) using a point-to-point transport like TCP may eliminate the ability to exploit multi-destination delivery as may be possible in the IP protocol architecture by using, for example, multicast; iii) the use of HTTP may limit the granularity of fetch operations to be relatively coarse due to the high cost of an HTTP transaction compared to a simple packet transmission; iv) the need for sophisticated caching strategies to provide bandwidth and server load scaling may lead to the deployment of custom, heavyweight CDN approaches (e.g., complex and hard to manage load balancers, DNS tricks, etc.); and v) partly due to the complexity of their management, CDN caching optimization may be complex to achieve as it may require individual cache control and management.

Embodiments of the disclosure may utilize Segment Routing (SR) protocol architectures in addressing some of the aforementioned limitations and technical tradeoffs. In particular, the data-centric object fetch approach at the inter-networking layer may make the design of more optimal content delivery systems possible. Symmetrically, the shift from centralized distribution to a data-centric object fetch approach may make possible the design of more optimal caching systems consistent with embodiments of the disclosure.

Centralized caches, such as CDNs, may be relatively easy to manage whereas managing a distributed-in-the-network set of caches of a comparable global size may create additional problems to solve. One advantage of distributed caches is that it may allow the CDN traffic to be kept close to the endpoint device accessing the content. Embodiments of the disclosure may include individual caches that may be smaller in order to make a global caching system more dynamic and capable of rapidly adapting to content consumption patterns.

Embodiments of the disclosure may leverage Internet Protocol version 6 (IPv6) SR properties combined with an interception process to provide management of a distributed set of CDN content caches as well as corresponding cache entries. Embodiments of the disclosure may also include a set of atomic operations (e.g., that may leverage the interception process) as well as some in-the-network autonomous and distributed cache management policies.

FIG. 1is a block diagram of an operating environment100in accordance with embodiments of the disclosure. For example, operating environment100may comprise any type of network (e.g., the Internet, a hybrid fiber-coaxial (HFC) network, a content delivery network (CDN), etc.). As shown inFIG. 1, operating environment100may comprise a plurality of nodes105and a plurality of user devices110. Plurality of nodes105may comprise, for example, network devices. The network devices may comprise, but are not limited to, servers, switches, and routers. Plurality of nodes105may comprise first server115, first router120, second server125, third server130, fourth server135, fifth server140, second router145, third router150, and sixth server155.

Each of plurality of user devices110may comprise a communication terminal that may comprise, but is not limited to, a set-top box (STB), a digital video recorder, a cable modem, a personal computer, a Wi-Fi access point, a cellular base station, a switch servicing multiple clients in a vicinity, a tablet device, a mobile device, a smart phone, a telephone, a remote control device, a network computer, a mainframe, a router, or other similar device. Plurality of user devices110may comprise a first user device160, a second user device165, a third user device170, a fourth user device175, a fifth user device180, a sixth user device185, a seventh user device190, and an eighth user device195.

Operating environment100may comprise nodes capable of delivering content. Operating environment100may not comprise an exact network configuration, but rather it may comprise a content distribution network overlay. As a consequence, for example, any edge between two nodes may be a logical edge that can physically go through any type of network artifact.

First server115may comprise a top level server (e.g., source server) from which content may be fetched. Plurality of user devices110may be connected to the edges of operating environment100. Consistent with embodiments of the disclosure, IPv6 SR properties may not be used only for content delivery purpose, but may also be used to populate CDN caches that may be distributed across operating environment100.

Content service providers may start pushing content into operating environment100(e.g., CDN) in order to service ones of plurality of user devices110. In doing so, the content service providers may want to distribute content on different caches within the CDN internal network. Embodiments of the disclosure may use SR combined with the aforementioned interception process to achieve chunk caching on CDN nodes (e.g., plurality of nodes105). In order to achieve this, embodiments of the disclosure may define a special organization of an SR list (e.g., in a packet) combined with the src and dst addresses in the list so that a CDN cache server (e.g., ones of the plurality of nodes105) may know what to do.

FIG. 2shows a state diagram for atomic caching method200using the aforementioned interception process consistent with embodiments of the disclosure. As shown inFIG. 2, S, R1, and SC1may comprise ones of plurality of nodes105described above with respect toFIG. 1. For example, S may comprise first server115, R1may comprise first router120, and SC1may comprise second server125. S, R1, and SC1may comprise other nodes in operating environment100and are not limited to first server115, first router120, and second server125. The process of method200may create a C1(i.e., chunk C1) cache entry in SC1cache. An external SR capable server (e.g., S) may be connected to the network (e.g., operating environment100). By convention, ::s may be the v6 @IP of this SR capable server (e.g., S).

An application hosted in S may open a socket against ::c1(e.g., the chunk to cache in SC1). To achieve this, S may:setsockopt (SR=::sc1, ::c1)connect (::c1)
As a result of the above, S may internally create a sync packet205comprising:src=::sdst=::sc1SR=::sc1, ::c1
sync packet205may represent a list of cache servers where the chunk C1may be cached. In this example, the SR list in sync packet205may be limited to SC1. S then sends the packet.

From S, sync packet205may reach R1that may have a route toward SC1. In response, R1may send sync packet205to SC1. SC1may then receive sync packet205. Because SC1may be SR capable, SC1may open sync packet205and parse sync packet205's segment routing header (SRH). Since SC1may comprise a cache server, SC1may determine that the last v6 @IP represents a chunk to be cached at SC1. Next, SC1may use the last address from sync packet205and may do a lookup in its internal chunk table. In this case, there may be no match in SC1's internal chunk table, which means SC1may not contain chunk C1. Different ways of using ::sc1, ::c1to achieve chunk caching may be used including, but not limited to, loadable kernel module or VPP based.

As shown inFIG. 2, opposed to content hunting, a cache miss may trigger the interception process. In this example, since there may be a cache miss, SC1may intercept sync packet205and a TCP connection may be established between S and C1. At this stage, the interception process may start. Now that the SYN may be at the right place, the interception process may now determine what to do for the return path (e.g., the SYN ACK as shown inFIG. 2).

At this point, SC1may have been elected as the server that may cache the C1chunk. It also may mean that a socket may be opened between ::s and ::c1. Since there was a cache miss (similar to a service hit), SC1may respond with a sync/acknowledge packet210. To do so, SC1may create sync/acknowledge packet210:src=::c1dst=::sSR=::sc1, ::s

SC1may send sync/acknowledge packet210. Sync/acknowledge packet210may hit R1that has a route toward S. S may receive sync/acknowledge packet210packet and respond with a acknowledge packet215:src=::sdst=::sc1SR=::sc1, ::c1
From this moment onward, there may be a socket opened between ::s and ::c1that may be used for caching the chunk ::c1. S may write chunk data from C1in the socket while SC1will read the chunk data from the same socket and will create the corresponding cache entry in SC1. When finished, the operating system (OS) may close the socket, which may end the C1chunk caching process.

If a cache hit had happened above rather than a cache miss, this may have meant C1is already present in SC1's cache in which case SC1may reject the cache request. Because in this example, there is no other SCx present in the SR list, SC1may not send a SYN-ACK, but will rather send a RESET. There might be a problem for S to correctly interpret this RESET since there may not be a way to make a distinction between this RESET and an accidental reset. It may not matter since S can interpret it as a “fail to cache”.

FIG. 2shows how a cache miss may trigger the interception process that may in turn trigger the Cx cache entry creation in SC1consistent with embodiments of the disclosure. This interception process can be used internally by a CDN to populate caches. It can be used, for example, for content pre-placement purpose. In addition, the interception process consistent with embodiments of the disclosure may be used to individually control all the CDN caches and also used by any individual cache to initiate a caching request against another cache. This aspect, for example, may be used to implement some internal CDN autonomous caching optimization policy.

In addition to the interception process shown inFIG. 2, embodiments of the disclosure may include a multi-caching interception process300as shown in the state diagram ofFIG. 3AandFIG. 3B. As shown inFIG. 3AandFIG. 3B, the S server (e.g., first server115) may be a source server pushing a popular content against different CDN nodes (e.g., plurality of nodes105) and may want to store popular content in cache servers SC0, SC2, and SC4(e.g., third server130, fourth server135, and fifth server140respectively.)

To achieve this content storage, for each Cx content chunk, the S server may inject, for example, “::sc0, ::sc2, ::sc4, ::cx” in the SR list in the network through a first SR packet305. As a result, Cx is expected to be first cached in SC0as illustrated in state310. Then, consistent with embodiments of the disclosure, a second SR packet315may be sent to the next hop in the list (i.e., SC2) as illustrated in state320. In state325, a cache hit in SC2may occur that may mean that Cx may already be available in the SC2cache.

Next, a third SR packet330may be sent to the final hop in the list (i.e., SC4) as illustrated in state335. As a result, Cx may be cached in SC4as illustrated in state340. Consequently, according to embodiments of the disclosure, the S server may propagate Cx from hop-to-hop as designated in SR packets consistent with interception process300. In the above example interception process300, there may be: i) a cache miss in SC0and SC4resulting in Cx being cached in SC0and SC4respectively; and ii) a cache hit in SC2meaning that Cx may already available in the SC2cache. This process may be seen as multi-push process where a piece of content may be automatically cached by CDN servers from a well-known list. The other advantage may be that the process may be neutral for servers from the list already having the piece of content in cache.

Since all SCx cache servers (e.g., plurality of nodes105) shown inFIG. 1may be SR capable, they may know how to interpret the SR packet they receive. A SCx server may implement some caching management logic where a chunk initially pushed by the S server may be propagated to all cache servers listed in the SR list without any intervention from the S server just by leveraging the interception process. One advantage of this approach may be that it reduces the S server workload.

Embodiments of the disclosure may also include adaptive caching. In the below example, at the beginning, only SC0(e.g., first server115) may have the requested chunks in cache. At a given point in time, a device Dy (e.g., user device175) connected to R4(e.g., third router150) may ask for Cx chunk. For this chunk, the DASH manifest may say that the shop list is (::r4, ::sc3, ::sc2::sc0) where SC3may comprise second router145and SC2may comprise third server130. Consequently, device Dy may inject (::r4, ::sc3, ::sc2::sc0, ::cx) SR list in the CDN.

R4may comprise an SR capable router, so it may process the packet as a normal SR packet and send it to the next hop, which happen to be SC3in this example. The packet may therefore be sent to SC3. SC3may then receive the packet, and since it can do content delivery, it may check ::cx against its local chunk table. Since Cx is only present in SC0cache, there may be a cache miss. SC3may then send the packet to SC2. The same may happen on SC2and the packet may go to SC0where there may be a cache hit. SC0may deliver the CX chunk back to Dy.

Dy may continue to ask for subsequent chunks from the same content (Cx+1, Cx+2, etc.). Consistent with embodiments of the disclosure, SC0may detect that there may be a high demand coming from Dy (or any of plurality of user devices110) for these chunks (it may even detect that all these chunks may belong to the same content). And since SC0knows from the SR lists it receives that there are caches down the path (SC2and SC3in this example) toward Dy, it may decide to push Cx, Cx+1 against, for example, SC3.

Symmetrically since SC0(e.g., first server115) may be at the top of the logical content distribution hierarchy, the same could happen for requests coming through other paths in operation environment100. Since the SR list used by plurality of devices110to fetch content may be an ordered list, any SCx server (e.g., any of plurality of nodes105) may determine what its relative position in the hierarchy in the CDS is.

Consistent with other embodiments of the disclosure, due to the symmetric mechanism used by devices (e.g., plurality of devices110) to access content, SCx servers (e.g., plurality of nodes105) may create information out of the requests they receive. A CDN cache server high in the SR list that may receive a lot of requests may, for example, deduce that servers down the path were not able to deliver the requested piece of content, which may mean that either they may be overloaded or, more likely, that they may not have it in cache. Based on this information, the SCx cache servers may leverage the interception process described above to proactively push chunks against servers down the path from the SR lists observed by the corresponding SCx servers, thus contributing to limit network congestion further up in the network.

Consistent with other embodiments of the disclosure, an SCx server detecting that it receives a lot of requests for the same content for which there is a cache miss may proactively decide to pull this content from a server higher in the hierarchy. In this case, the process used by the SCx server may not be different from the one used by the device to fetch the same piece of content.

The pull mechanism can be generalized to become a multi-pull mechanism where an SCx server pulling a piece of content from a SR list may trigger a cascade of pull atomic actions where all SCx servers from the SR list may get the content. In the above example, SC3may trigger SC3as well as SC2to fetch content from SC0, for example.

Consistent with other embodiments of the disclosure, these push, multi-push, as well as multi-pull mechanisms combined together, may enable a set of SCx CDN cache nodes to collaborate at a very high frequency to optimize the global CDN caching efficiency. There may be some CDN cache server configuration parameters defining how servers may react to the observed request, thus defining a set a behavioral laws globally defining how the whole system (e.g., operating environment100) may react.

FIG. 4shows computing device400. As shown inFIG. 4, computing device400may include a processing unit410and a memory unit415. Memory unit415may include a software module420and a database425. While executing on processing unit410, software module420may perform processes for providing content distribution system cache management, including for example, any one or more of the stages from method200and method300described above with respect toFIG. 2,FIG. 3A, andFIG. 3B. Computing device400, for example, may provide an operating environment for any one or more of plurality of nodes105and plurality of user devices110. Any one or more of plurality of nodes105and plurality of user devices110may operate in other environments and is not limited to computing device300.

Computing device400may be implemented using a Wi-Fi access point, a cellular base station, a tablet device, a mobile device, a smart phone, a telephone, a remote control device, a set-top box, a digital video recorder, a cable modem, a personal computer, a network computer, a mainframe, a router, or other similar microcomputer-based device. Computing device400may comprise any computer operating environment, such as hand-held devices, multiprocessor systems, microprocessor-based or programmable sender electronic devices, minicomputers, mainframe computers, and the like. Computing device400may also be practiced in distributed computing environments where tasks are performed by remote processing devices. Furthermore, computing device400may comprise, for example, a mobile terminal, such as a smart phone, a cellular telephone, a cellular telephone utilizing Wireless Application Protocol (WAP) or unlicensed mobile access (UMA), personal digital assistant (PDA), intelligent pager, portable computer, a hand held computer, a conventional telephone, or a Wireless Fidelity (Wi-Fi) access point. The aforementioned systems and devices are examples and computing device400may comprise other systems or devices.

While certain embodiments of the disclosure have been described, other embodiments may exist. Furthermore, although embodiments of the present disclosure have been described as being associated with data stored in memory and other storage mediums, data can also be stored on or read from other types of computer-readable media, such as secondary storage devices, like hard disks, floppy disks, or a CD-ROM, a carrier wave from the Internet, or other forms of RAM or ROM. Moreover, the semantic data consistent with embodiments of the disclosure may be analyzed without being stored. In this case, in-line data mining techniques may be used as data traffic passes through, for example, a caching server or network router. Further, the disclosed methods' stages may be modified in any manner, including by reordering stages and/or inserting or deleting stages, without departing from the disclosure.