Disclosed are methods and apparatus for flooding link state packets or packet data units (LSP's) from a first node to one other LSP receiving node, where the LSP's are flooded in an order that is related to relative costs of various paths emanating from the first node. That is, the first node sends its own LSP first since the first node has no cost relative to itself. The first node then sends other LSP's that are associated with a plurality of other LSP sending nodes that have previously flooded their LSP's to the first node. These other LSP's are sent by the first node to the other LSP receiving node in an order related to the relative costs associated with the paths from the first node to each of the other LSP sending nodes which had previously sent the other LSP's to the first node.