Predictable, tile-based multiprocessor Network-on-Chips (NoCs) are considered as future embedded systems platforms. Each tile contains one or a few processors and local memories. These memories are typically too small to store large data structures. A solution to this is to embed tiles with large memories in the architecture. However, fetching data from these memories is slow because of the large network delays. The delay can be hidden by using prefetching. The authors’ main contributions are models that allow timing analysis to provide guaranteed quality and performance when using remote memories and prefetching.