Pore-scale network modeling has become an effective method for accurate prediction and upscaling of macroscopic properties, such as permeability. Networks are either mapped directly from real media or stochastic methods are used that simulate their heterogeneous pore structure. Flow is then modeled by enforcing conservation of mass in each pore and approximations to the momentum equations are solved in the connecting throats. In many cases network modeling compares favorably to experimental measurements of permeability. However, computational and imaging restrictions generally limit the network size to the order of 1 mm3 (few thousand pores). For extremely heterogeneous media these models are not large enough in capturing the petrophysical properties of the entire heterogeneous media and inaccurate results can be obtained when upscaling to the continuum scale. Moreover, the boundary conditions imposed are artificial; a pressure gradient is imposed in one dimension so the influence of flow behavior in the surrounding media is not included. In this work we upscale permeability in large, heterogeneous media using physically-representative pore-scale network models (domain ~106 pores). High-performance computing is used to obtain accurate results in these models, but a more efficient, novel domain decomposition method is introduced for upscaling the permeability of pore-scale models. The medium is decomposed into hundreds of smaller networks (sub-domains) and then coupled with the surrounding models to determine accurate boundary conditions. Finite element mortars are used as a mathematical tool to ensure interfacial pressures and fluxes are matched at the interfaces of the networks boundaries. The results compare favorably to the more computationally intensive (and impractical) approach of upscaling the media as a single model. Moreover, the results are much more accurate than traditional hierarchal upscaling methods. This upscaling technique has important implications for using pore-scale models directly in reservoir simulators in a multiscale setting. The upscaling techniques introduced here on single phase flow can also be easily extended to other flow phenomena, such as multiphase and non-Newtonian behavior. / text