Optimal seamless self-assembly of files in linear networks | Optimization Letters
Skip to main content
Springer Nature Link
Log in

Optimal seamless self-assembly of files in linear networks

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

A file F is sited at one end (the root) of a path in some network. Each non-root node in the path is able to cache part or all of F, and each node may also have a client wanting to download F. Links between neighbors on the path have given transmission delays associated with them, but the delay from a node to its own client, if it has one, is zero. In the seamless, self-assembly paradigm all clients issue requests simultaneously at time 0, each starts to receive segments of F immediately, and continues to receive them until F is fully downloaded. The process must be implemented by means of a distributed self-assembly protocol which is unaware of network structure beyond links to immediate neighbors. We exhibit such a protocol, and show how to assign segments of F to the node caches in such a way that, no matter which nodes are chosen as clients, seamless self-assembly is realized and, simultaneously, the total cache size achieves a lower bound determined solely by the link delays. The paper concludes with a brief discussion of the many open problems arising in systems requiring seamless, or nearly seamless, self assembly of files.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adleman, L., Cheng, Q., Goel, A., Huang, M.-D., Kempe, D., de Espanes, P.M., Rothemund, P.: Combinatorial optimization problems in self-assembly. In: STOC ’02: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 23–32. ACM Press, New York (2002)

  2. Cidon I., Kutten S., Soffer R. (2002): Optimal allocation of electronic content. Comput. Netw. 40(2): 205–218

    Article  Google Scholar 

  3. Coffman E.G., Constantinides A., Rubenstein D., Shepherd B., Stavrou A. (2004): Content distribution for seamless transmission. SIGMETRICS Perform. Eval. Rev. 32(2): 31–32

    Article  Google Scholar 

  4. Constantinides, A., Coffman, E.G. Jr.: Seamless self-assembly of files in cache networks at minimal storage cost. (Submitted) (2006)

  5. Krishnan P., Raz D., Shavitt Y. (2000): The cache location problem. IEEE/ACM Trans. Netw. 8(5): 568–582

    Article  Google Scholar 

  6. Li, B., Golin, M.J., Italiano, G.F., Deng, X.: On the optimal placement of web proxies in the internet. In: Proceedings of IEEE INFOCOM, pp. 1282–1290, New York, March 1999

  7. Li, K., Shen, H.: Optimal placement of web proxies for tree networks. In: Proceedings of the 2004 IEEE Conference of e-Technology, e-Commerce and e-Service, pp. 479–486 (2004)

  8. Nagaraj S.V. (2004): Web Caching and Its Applications. Kluwer, Norwell

    MATH  Google Scholar 

  9. Przybylski S.A. (1990): Cache and Memory Hierarchy Design: a Performance-Directed Approach. Morgan Kaufmann Publishers, Inc., San Francisco

    MATH  Google Scholar 

  10. Rabinovich M., Spatschek O. (2002): Web Caching and Replication. Addison-Wesley, Boston

    Google Scholar 

  11. Sen, S., Rexford, J., Towsley, D.F.: Proxy prefix caching for multimedia streams. In: Proceedings of IEEE INFOCOM, pp. 1310–1319, New York, March 1999

  12. Smith A.J. (1982): Cache memories. ACM Comput. Surv. 14(3): 473–530

    Article  Google Scholar 

  13. Wang J. (1999): A survey of web caching schemes for the internet. SIGCOMM Comput. Commun. Rev. 29(5): 36–46

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Columbia University, New York, NY, 10027, USA

    Andreas Constantinides & E. G. Coffman Jr.

Authors
  1. Andreas Constantinides
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. G. Coffman Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to E. G. Coffman Jr..

Rights and permissions

Reprints and permissions

About this article

Cite this article

Constantinides, A., Coffman, E.G. Optimal seamless self-assembly of files in linear networks. Optimization Letters 1, 119–128 (2007). https://doi.org/10.1007/s11590-006-0008-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-006-0008-3

Keywords

Search

Navigation