A packet is transmitted from a source node to a destination node via a relay path in a multi-hop network. The packet is transmitted by cache routing or source routing, depending on the presence or absence of information identifying the destination node in a history table maintained at the source node. In source routing, relay path information is included in the packet. In cache routing, relay nodes obtain routing information from entries in their own cache routing tables. Each entry indicates only the destination node and the next relay node, and each cache routing table has a limited size. When a series of packets are transmitted to the second node, cache routing can be used for all but the first packet, thereby reducing packet overhead.