Here are some steps that I have in mind for the network crate, ordered in order to have a smooth transition. Feel welcome to comment.

• Make Service and ServiceEvent generic over the message type, and send/receive messages instead of Bytes objects.
• Add a trait in network-libp2p that is implemented on Message and allows retrieving the RequestId.
• Make network-libp2p/src/custom_proto/handler.rs open a new substream for each request. Whether to wait for an answer and how to associate substreams with requests is done using the trait mentioned in the previous point. (Rework network/src/protocol.rs to use libp2p's multiplexing #1517)
• Remove the Clogged event.
• (blurry) Rewrite network/src/protocol.rs as a libp2p NetworkBehaviour. Instead of passing a RegisteredProtocol to network-libp2p, one can pass a NetworkBehaviour. Move network-libp2p/src/custom_protocol to network. The messages generated by the API of network-libp2p's Service would be the events generated by the network behaviour. We would also require a trait in addition to NetworkBehaviour so that we can register discovered nodes to the behaviour.
• Move some logic from the protocol.rs NetworkBehaviour into the ProtocolsHandler, such as the Status message. After this point, Have an upgrade strategy for the network protocol #1518 and Add a networking message to enable/disable the Substrate protocol on connections #1702 can be tackled.
• Extract the gossiping from protocol.rs to use a different protocol from the rest (the rest meaning things such as block or header requests).
• (blurry) Use libp2p's floodsub, episub or gossipsub instead of consensus_gossip (More sophisticated gossip for consensus messages #366).
• Change everything to use futures and messages passing instead of Arcs (Rewrite sync and network layers to use futures #834), and use tokio-timer instead of maintain_peers, tick or garbage_collect.
• Merge network and network-libp2p?

Later:

• Remove backwards compatibility for Rework network/src/protocol.rs to use libp2p's multiplexing #1517.
• Remove the RequestId from network::message::Message and let libp2p do the ID assignment.