Link Stress Reduction against Bursty Arrivals of Content Requests ()

Kenichi Yamashita, Kazumasa Oida

Department of Computer Science and Engineering, Fukuoka Institute of Technology, Wajiro-Higashi, Fukuoka, Japan.

**DOI: **10.4236/ijcns.2012.55036
PDF
HTML
5,885
Downloads
8,084
Views
Citations

Department of Computer Science and Engineering, Fukuoka Institute of Technology, Wajiro-Higashi, Fukuoka, Japan.

Content delivery networks are designed to extend the end-to-end transport capability of the Internet to cope with increases in video traffic. For further improvement, bursty request arrivals should be efficiently addressed. As opposed to previous approaches, in which the best client-server pair is individually selected (individual optimization), this paper proposes an algorithm for dealing with simultaneous arrival requests, in which client-server pairs are selected such that all requests receive good service (social optimization). The performance of the proposed algorithm is compared with that of the closest algorithm, an individual optimization algorithm, under the condition that a large number of requests arrive simultaneously. The evaluation criterion is the worst link stress, which is the largest number of streams per link. The numerical results show that the proposed algorithm is effective for large-scale networks and that the closest algorithm does not provide near-optimal solutions, especially when all requests arrive in a small part of the network or when there are many servers.

Share and Cite:

K. Yamashita and K. Oida, "Link Stress Reduction against Bursty Arrivals of Content Requests," *International Journal of Communications, Network and System Sciences*, Vol. 5 No. 5, 2012, pp. 272-279. doi: 10.4236/ijcns.2012.55036.

1. Introduction

Video traffic will be increasingly prevalent on the Internet. According to Cisco’s traffic forecast for 2009-2014, global IP traffic is expected to increase by 34% per annum, and much of the increase is attributed to the delivery of video data [1]. Video traffic typically consumes a large amount of network bandwidth for a long time. Furthermore, some video content providers such as YouTube have begun to provide high-definition video streaming services. It is fully anticipated that even more efficient and scalable video delivery schemes will be required.

The video delivery approach based on peer-to-peer (P2P) networking is currently popular since this yields several advantages such as resource scalability, network path redundancy, and self organization [2,3]. A large number of P2P-based video delivery techniques are now available, and some are used for commercial purposes [4,5]. Nevertheless, the P2P systems still pose some challenges such as resilience, underlay awareness, and security [6,7]. Meanwhile, content delivery networks (CDNs) have evolved to improve the scalability and reliability of Web sites, and their focus has shifted to media delivery. CDNs extend the end-to-end transport capability of the Internet by employing techniques designed to optimize content delivery. Typical techniques are Web caching, serverload balancing, and request routing [8]. This paper focuses on the CDN server assignment scheme that prevents congestion when bursts of requests arrive.

Most commercial CDN providers, such as Akamai and Limelight Networks, follow the overlay approach in which servers and caches distributed over the network manage content delivery. The underlay network components (e.g., routers) play no active role in content delivery. There are two classes of overlays: unstructured and structured [9]. Structured overlays, which are organized with specific topologies, are relatively complex, whereas routing and searching operations tend to be efficient. Some frequently used overlay topologies are trees [10], rings [11], meshes [12,13], and hypercubes [14,15]. The hypercube overlay considered in this paper has attractive topological properties for video delivery: low node degree, small network diameter, recursive construction, and independent paths [14].

Previous server assignment approaches are classified as individual optimization, which selects individually the best client-server pair in terms of the number of hops, the round-trip time, and/or the server and network loads [16- 19]. In the case of bursty request arrivals (flash crowd), however, individual optimization may not lead to social optimization, which provides good service quality for all requests. Some queueing models show that they do not agree under heavy loads [20-22]. This paper formulates an optimization problem and then proposes a social optimization algorithm. The numerical results show that the proposed algorithm is effective, especially when all requests arrive in a small part of the network or when there are many servers.

This paper is organized as follows: Section 2 defines the routing rules in the hypercube overlays. Section 3 specifies the content delivery model and then formulates the server assignment problem. Section 4 proposes a heuristic algorithm for the problem. Section 5 compares the performances of the proposed algorithm and an individual optimization algorithm under the condition that a large number of requests arrive simultaneously. Finally, Section 6 presents the conclusions.

2. Hypercube Routing

This section defines the routing in the hypercube overlays. The K-dimensional hypercube has 2^{K} nodes and edges [23]. Each node corresponds to a K-bit binary string (node ID), and two nodes are linked with an edge if their node IDs differ in precisely one bit. As a consequence, each node is adjacent to K other nodes, one for each bit position, and the number of hops between any two nodes does not exceed K. Figure 1 illustrates a three-dimensional hypercube. Another important feature of the hypercube is independent routes [24]. Let i and j be any two nodes of a K-hypercube. There are K independent paths between i and j, and their lengths are less than or equal to, where stands for the Hamming distance between nodes i and j.

Routing on the hypercube is simple and does not require routing tables. This is because any two nodes whose node IDs differ in one bit are connected. In the case of a three-dimensional hypercube, for example, if node 000 needs to transmit packets to node 011, since nodes 010 and 001 are directly connected to nodes 000 and 011, there are two shortest-hop paths: and To fix a route for each pairing of source and destination, we assume that only the first path is used. In other words, if the node IDs of the source and destination are and, respectivelythen the source selects node for the next hop if and for.

Figure 1. Three-dimensional hypercube and binomial tree rooted at node 000.

If all nodes obey this routing rule, routing paths from a source node to the other nodes are deterministically given. The binomial tree [25] in Figure 1 represents the routing paths from node 000 to all other nodes in the three-dimensional hypercube. The figure also shows that the number of hops does not exceed three along any path. Hereinafter, the term binomial tree refers to the routing paths from the root node to all other nodes. The binomial tree rooted at node 101 can be derived by XORing every node ID in Figure 1 with 101.

3. Server Assignment

3.1. Content Delivery Model

Let us consider a content delivery system consisting of origin servers and surrogate servers connected in a hypercube overlay. The origin servers have the definitive version of the content. The surrogate servers, which are located close to users and receive content requests, store a copy of the content. Through the interaction among the surrogates, one of the surrogates gives content to a user if possible; otherwise (i.e., for a cache miss), the requested content is delivered from an origin to the user via the surrogate that received the request.

In this model, at any instant in time, any node in the hypercube acts as one of the three types of servers:

1) An origin server

2) A surrogate server that is relaying a stream from an origin to a user or that has just received a request which causes a cache miss

3) A surrogate server that does not need to interact with origin servers.

Hereinafter, we refer to a server of the first type as a server, a server of the second type as a client, and a user request that causes a cache miss as a request (i.e., this paper regards a server of the second type as a client that is served by a server of the first type).

Let S and C denote sets of servers and requests, respectively. Simultaneous request arrivals are dealt with under the condition that, here and. The request partitioning problem considered is to assign requests to multiple servers in such a way that the quality of the assignment is maximized on the basis of the following assumptions:

1) Partitioned sets are non-overlapping, where is a request set assigned to server i.

2) Servers may have different processing capabilities (see Subsection 3.3).

3) For each request, one stream is delivered from a server to the user via the client that received the request.

4) Requests may be preassigned to a server (see Subsection 3.3).

3.2. Worst Link Stress

The quality of the assignment is measured using the worst link stress. Assume that is given and that all requests in C are receiving delivery service. Then the number of streams on each hypercube link can be determined. Let be the number of streams on link e that originate from server i for serving all requests in. The link stress (LS) of link e represents the number of streams on the link and is given by

(1)

The worst link stress (WLS) is the greatest link stress of all links in the hypercube. Strictly, WLS is given by

(2)

where E is the set of all links in the hypercube.

Let us calculate WLS using the binomial tree in Figure 1 under the condition that and two requests arrive simultaneously at nodes 101 and 111. In this case, and. According to Figure 1, there are four links used for stream delivery:

where indicates the link between nodes i and j. Since and

from (2) we have. The WLS indicates the degree of congestion since congestion typically occurs at links where a large number of streams are flowing. In order to obtain a small WLS value, traffic concentration on any single link must be avoided. Table 1 lists the definitions of symbols used frequently in this paper.

Table 1. Symbols used frequently in this paper.

3.3. Optimization Problem

The request partitioning problem P is formulated as follows:

(3)

where is the set of requests preassigned to server i.

When C has changed due to bursty arrivals, a new partition must be calculated. If server k is providing service for request c when a new partition must be calculated, the partition is obtained under the condition that. The preassignment may also be used for reducing interdomain traffic.

Servers may not have the same processing capability. Let be the number of requests assigned to server i (i.e.,) and let be the processing capacity of server i. To balance the load among heterogeneous servers, should increase with. Therefore, should be determined such that

.

4. Proposed Algorithm

Each server k has two sets U and A, which are the set of requests not selected and the set of requests either selected by server k or preassigned to server k, respectively. Note that A depends on server k but U does not. The algorithm proposed for solving the optimization problem P is specified as follows:

1) At every server k in set S the algorithm starts with

and.

2) Each server k in turn selects one request from set U in an arbitrary order according to Algorithm 4. If server k selects request c, then Algorithm 4 updates U and such that c is removed from U and added to A.

3) After the selection, server k informs the other servers about what has been selected so that each uses the information to update its own set U.

4) The algorithm ends at server k if. At that point in time,.

Algorithm 4 is based on the following proposition:

Proposition 1. The WLS is the LS of a link connecting the root to a binomial subtree if.

Proof. Assume that the number of streams on link in subtree B is greater than the number of streams from the root to the subtree. Then, at least one of the streams on link does not stem from the root. This contradicts the third assumption in Subsection 3.1.

Figure 2 shows binomial subtrees where (a binomial subtree of order k) is a k-dimensional hypercube rooted at a node that is directly connected to the root (node 0000). The proposition suggests that WLS be produced by one of the four links connecting the root produced by one of the four links connecting the root and the subtrees. Therefore, traffic load should be balanced among these links. The load balancing, however, is not easy since a decision made by one server affects the other servers’ decisions.

The following explains Algorithm 4: Let X be the number of requests that server k is expected to select in future. Tuple is partitioned into K tuples , based on where requests come from (see Figure 3). Therefore,

(4)

where and if. Note that each server has different K tuples.

The expected number is obtained as follows: Assume that server k uniformly selects requests at a time. Then, the number of selected requests from subtree has a hypergeometric distribution with mean . We adopt the mean as; that is, for,

(5)

To balance the load, Algorithm 4 selects a request from if

(6)

The load balancing means that, , are almost the same when the algorithm finishes execution. If (6) holds, the final value is probably small; therefore, the server immediately raises before becomes an empty set. If two or more integers n satisfy (6), the smallest integer is used.

5. Performance Comparisons

This section compares the performances of three algorithms: the random, closest, and proposed algorithms. In all of these algorithms, each server k in set S in turn selects one request in an arbitrary order until the number of requests that server k must serve reaches. In the random algorithm, one request is selected uniformly from those not selected yet. In the closest algorithm, each server selects a request coming from the closest client, where the distance between server s and client c is measured by the number of hops from s to c. If there is more than one such request, a request from a client in the lowest order subtree is selected.

The closest algorithm is an individual optimization algorithm since it yields the closest client-server pairs one by one. In this simultaneous arrival scenario, the term closest indicates not only the lowest hop count but also the lowest round-trip time, since there are no ongoing streams when requests arrive.

Table 2 lists the default parameter values. For each 3- tuple, 10,000 calculations are performed. All of the algorithms are impartially evaluated by using the same node IDs for the M servers and N clients that receive user requests. These IDs are uniformly selected unless otherwise mentioned. Every server handles the same number of requests (i.e.,) and there are no preassigned requests (i.e., for all k).

Figure 2. A binomial tree in the four-dimensional hypercube includes four binomial subtrees: B_{0}, B_{1}, B_{2}, B_{3}.

Figure 3. Tuple (U, A, X) is partitioned into K tuples (U_{i}, A_{i}, X_{i}) based on where requests come from.

5.1. Dimensionality

Figure 4 shows the frequency distributions of 10,000 calculated WLS values and Table 3 lists the means and standard deviations of the WLS distributions. These results demonstrate the effects of the dimensionality on the performance of the three algorithms. From Table 2, the percentages of the numbers of servers and clients in a hypercube are independent of the dimensionality K. From the figure, the proposed algorithm outperforms the other two algorithms, regardless of K. From Table 3, the mean and standard deviation of the random algorithm increase with K, while those of the closest algorithm stay roughly the same. In contrast, by using the proposed algorithm, the mean and standard deviation decrease with K. As a result, the largest WLS of the proposed algorithm also decreases with dimensionality K, as shown in Figure 4. These results indicate that the proposed algorithm is effective for large-scale hypercubes.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | “Cisco Visual Networking Index: Forecast and Methodology, 2009-2014,” 2012. http://www.slideshare.net/jimkaskade/cisco-visual-networking-index-forecast-and-methodology-200914 |

[2] | N. Ramzan, E. Quacchio, T. Zgaljic and F. Rovati, “Peer-to-Peer Streaming of scalable video in Future Internet Applications,” IEEE Communications Magazine, Vol. 49, No. 1, 2011, pp. 128-135. doi:10.1109/MCOM.2011.5723810 |

[3] | K. Pussep, S. Oechsner, O. Abboud, M. Kantor and B. Stiller, “Impact of Self-Organization in Peer-to-Peer Overlays on Underlay Utilization,” 4th International Conference on Internet and Web Applications and Services, Venice, 24-28 May 2009, pp. 84-89. doi:10.1109/ICIW.2009.20 |

[4] | PPlive Website, 2011. http://www.pplive.com/ |

[5] | Zattoo Website, 2011. http://www.zattoo.com/ |

[6] | O. Abboud, K. Pussep, K. Mohr, A. Kovacevic, S. Kaune and R. Steinmetz, “Enabling Resilient P2P Video Streaming: Survey and Analysis,” Multimedia Systems, Vol. 17, No. 3, 2011, pp. 177-197. doi:10.1007/s00530-011-0229-x |

[7] | S. Tonnies, B. Kohncke, P. Hennig, I. Brunkhorst and Wolf-Tilo Balke, “A Service Oriented Architecture for Personalized Universal Media Access,” Future Internet, Vol. 3, No. 2, 2011, pp. 87-116. doi:10.3390/fi3020087 |

[8] | R. Buyya, M. Pathan and A. Vakali, “Content Delivery Networks,” 1st Edition, Springer Publishing Company, Incorporated, Berlin, 2008. doi:10.1007/978-3-540-77887-5 |

[9] | S. Tarkoma, “Overlay Networks,” CRC Press, London, 2010. doi:10.1201/9781439813737 |

[10] | C. G. Plaxton, R. Rajaraman and A. W. Richa, “Accessing Nearby Copies of Replicated Objects in a Distributed Environment,” Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, New York, 22-25 June 1997, pp. 311-320. |

[11] | I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications,” IEEE/ACM Transactions on Networking, Vol. 11, No. 1, 2003, pp. 17-32. doi:10.1109/TNET.2002.808407 |

[12] | A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems,” Proceedings of the 18th IFIP/ ACM International Conference on Distributed Systems Platforms, Heidelberg, 12-16 November 2001, pp. 329-350. |

[13] | B. Y. Zhao, J. Kubiatowicz and A. D. Joseph, “Tapestry: An Infrastructure for Fault-tolerant Wide-Area Location and Routing,” Computer Science Division (EECS), University of California, Oakland, 2001. |

[14] | E. Anceaume, F. Brasileiro, R. Ludinard and A. Ravoaja, “PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn,” 2nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Ann Arbor, 3-7 October 2008, pp. 15-24. doi:10.1109/SASO.2008.44 |

[15] | S. C. Han and Y. Xia, “Network Load-Aware Content Distribution in Overlay Networks,” Computer Communications, Vol. 32, 2009, pp. 51-61. doi:10.1016/j.comcom.2008.09.021 |

[16] | A. Shaikh, R. Tewari and M. Agrawal, “On the Effectiveness of DNS-Based Server Selection,” Proceedings of IEEE INFOCOM 2001 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, Vol. 3, 22-26 April 2001, pp. 1801-1810. |

[17] | S. Ratnasamy, M. Handley, R. M. Karp and S. Shenker, “Topologically-Aware Overlay Construction and Server Selection,” 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, Vol. 3, 23-27 June 2002, pp. 1190-1199. |

[18] | M. Hofmann and L. R. Beaumont, “Content Networking: Architecture, Protocols, and Practice,” Morgan Kaufmann Publishers, San Francisco, 2005, pp. 129-134. |

[19] | C. M. Chen, Y. Ling, M. Pang, W. Chen, S. Cai, Y. Suwa and O. Altintas, “Scalable Request-Routing with Next-Neighbor Load Sharing in Multi-Server Environments,” Proceedings of the 19th International Conference on Advanced Information Networking and Applications, IEEE Computer Society, Washington, DC, 28-30 March 2005, pp. 441-446. |

[20] | C. E. Bell and S. Stidham Jr., “Individual versus Social Optimization in the Allocation of Customers to Alternative Servers,” Management Science, Vol. 29, No. 7, 1983, pp. 831-839. doi:10.1287/mnsc.29.7.831 |

[21] | S. Shenker and A. Weinrib, “The Optimal Control of Heterogeneous Queueing Systems: A Paradigm for LoadSharing and Routing,” IEEE Transactions on Computers, Vol. 38, 1989, pp. 1724-1735. doi:10.1109/12.40850 |

[22] | K. Oida and S. Saito, “A Packet-Size Aware Adaptive Routing Algorithm for Parallel Transmission Server Systems,” Journal of Parallel and Distributed Computing, Vol. 64, No. 1, 2004, pp. 36-47. doi:10.1016/j.jpdc.2003.07.008 |

[23] | F. T. Leighton, “Introduction to Parallel Algorithms and Archtectures: Arrays, Trees, Hypercubes,” Morgan Kaufmann Publishers, Waltham, 1992. |

[24] | Y. Saad and M. Schultz, “Topological Properties of Hypercubes,” IEEE Transactions on Computers, Vol. 37, No. 7, 1988, pp. 867-872. doi:10.1109/12.2234 |

[25] | T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms,” 3rd Edition, The MIT Press, Cambridge, 2001. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.