Network-oriented car navigation systems (off-board navigation systems) have become a hot topic cause of the expanding car navigation and active wireless communication markets. This paper examines the map downloading architecture, which realizes practical off-board navigation systems. We focus on practical technologies for present low speed wireless communication networks, such as with a 9.6 kbps transfer speed. We propose a new off-board navigation architecture, which combines a cost-effective map downloading system and a guide information downloading system. The proposed architecture can reduce the download data size to within about 50-100 kbytes for destination setting and route guidance. It has about a 1-2 minutes response time and about a 30-60 yen communication cost for a PDC (Personal Digital Cellular) wireless communication network in Japan. We consider this communication cost has a potential for a commercial off-board navigation system.