Method and apparatus for prioritized information delivery with network coding over time-varying network topologies

• US 8,861,356 B2
• Filed: 02/29/2008
• Issued: 10/14/2014
• Est. Priority Date: 03/13/2007
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Kozat, Ulas C., Papadopoulos, Haralabos, Ramprashad, Sean A., Sundberg, Carl-Erik W., Ppin, Christine
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HAMPTON, TARELL A
• Application Number:
  US12/040,653
• Publication Number:
  US 20080225751A1
• Time in Patent Office: 2,419 Days
• Field of Search: 370/395.21, 370/254, 370/255, 709/238, 709/240
• US Class Current: 370/235
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/38 by adapting coding or compression rate
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality

Abstract

A method and apparatus is disclosed herein for information delivery with network coding over time-varying network topologies. In one embodiment, the method comprises decomposing a sequence of topology graphs that model a time-varying network topology into a plurality of virtual graphs, where each virtual graph of the plurality of virtual graphs corresponds to a distinct traffic class, and the virtual topology graph representing a partial topology of a time-varying network. The method also includes selecting a network code for each virtual graph in the plurality of the virtual graphs to meet requirements of the distinct traffic class corresponding to said each topology graph, where the network code is used to encode packets of the associated traffic class, and processing packets of each traffic class using the network code determined by its corresponding virtual topology and the requirements of said each traffic class, including using a virtual buffer system to implement the network code corresponding to each traffic class over the physical network topology. The method also includes using a scheduler to determine the transmission schedules for each output packet from the virtual buffer system of each traffic class where the scheduling decisions are based, at least in part, on the QoS requirements of each class.

Claims

1. A method comprising:

decomposing a sequence of topology graphs that model a time-varying network topology into a plurality of virtual graphs, where each virtual graph of the plurality of virtual graphs corresponds to a distinct traffic class, the virtual topology graph representing a partial topology of a time-varying network;

selecting a network code for each virtual graph in the plurality of the virtual graphs to meet requirements of the distinct traffic class corresponding to said each topology graph, where the network code comprises a mathematical operation that is applied to incoming packets of its corresponding traffic class to encode packets of the associated traffic class, wherein the mathematical operation for the network code for at least one distinct traffic class comprises an operation performed jointly on a plurality of packets of the at least one distinct traffic class;

processing packets of each traffic class using the network code determined by its corresponding virtual topology and the requirements of said each traffic class, including using a virtual buffer system to implement the network code corresponding to each traffic class over the time-varying network topology by applying the mathematical operation of the network code associated with said each class to incoming packets of a corresponding traffic class at a network node to transform the incoming packet data into encoded packet data associated with each class and placing the encoded packet data into virtual output buffers associated with said each class at an outgoing physical interface of the network node; and

using a scheduler to determine the transmission schedules for each output packet from the virtual buffer system of each traffic class through the outgoing physical interface, where scheduling decisions are based, at least in part, on the QoS requirements of each class.

2. The method defined in claim 1 wherein selecting a network code comprises constructing the network code for each virtual graph in the plurality of virtual graphs.

3. The method defined in claim 1 wherein the plurality of virtual graphs comprises a plurality of parallel sequences of topologies, the union of which models the time-varying network topology.

4. The method defined in claim 1 wherein each of the distinct classes comprises a distinct QoS class.

5. The method defined in claim 4 wherein a one-to-one correspondence exists between each QoS class and a network code used for the QoS class.

6. The method defined in claim 4 wherein processing packets of each traffic class using the network code comprises encoding packets for each QoS class separately at each network node and placing encoded packet data associated with said each QoS class generated at said each network node into respective priority queues at an outgoing physical interface of said each network node.

7. The method defined in claim 1 wherein each network code selected determines an intra-class buffering system and topology decomposition determines the inter-class scheduling.

28. The method defined in claim 1 wherein the mathematical operation comprises linear combinations on Galois bit fields.

32. The method defined in claim 1 wherein the mathematical operation comprises a bit-wise XOR operation.

8. A communication network system having a plurality of senders and a plurality of receivers in which information to be delivered from the senders to the receivers comprises information blocks of different classes, the network comprising:

a plurality of intermediate nodes to process and relay information between the senders and receivers, the plurality of nodes arranged in a time-varying network topology that is subject to change dynamically during use, wherein each node

classifies incoming data according to traffic class,

encodes the incoming data for each traffic class separately to transform the incoming data into encoded packet data associated with each class by applying a mathematical operation of a network code assigned based on meeting requirements of the traffic class corresponding to a sub-virtual network topology graph of a virtual topology graph representing a topology of the dynamically changeable network decomposed into a plurality of distinct topology sequences, wherein the mathematical operation of the network code for at least one distinct traffic class comprises an operation performed jointly on a plurality of packets of the at least one distinct traffic class,

stores the encoded packet data into virtual output buffers of a virtual buffer system, each of the virtual output buffers being associated with one traffic class, and

sends encoded data from the virtual output buffers through an outgoing physical interface of the network node to one or more other nodes in the network topology, according to traffic class, when transmission opportunities are available.

9. The communication network system defined in claim 8 wherein said each node stores encoded data in queues at an outgoing physical interface for subsequent transmission, each of the queues being assigned to a distinct traffic class.

10. The communication network defined in claim 8 wherein the network topology dynamically changes due to failure or availability of one or more network elements in the network, additions of one or more new network elements into the network, or variations in one or more existing network elements in the network in one or more of bandwidth, capacity and connectivity.

11. The communication network defined in claim 8 wherein the information block of different classes comprises information blocks of different priority or different quality of service.

12. The communication network system defined in claim 8 wherein at least one of the plurality of nodes comprises:

a physical incoming interface;

a virtual buffer system to buffer incoming data and apply a network code to the incoming data based on traffic class;

a scheduler coupled to the virtual buffer system to cause codes generated by the virtual buffer system to be output; and

a physical outgoing interface coupled to the virtual buffer system and the scheduler to output codes generated by the virtual buffer system under control of the scheduler that is constrained by each virtual graph corresponding to a distinct QoS class.

13. The communication network system defined in claim 8 wherein at least one node of the plurality of nodes classifies the incoming data with respect to quality of service requirements, performs encoding operations on the incoming data of different classes using a network code assigned to each of the different classes, and monitors observed local interface capacities and statistics of encoded blocks served by the local interface to schedule the sending of encoded data blocks.

14. The communication network system defined in claim 13 wherein at least one node changes an encoding function to apply to data of one traffic class in response to a message received specifying the change.

15. The communication network system defined in claim 13 wherein at least one node computes an encoding function for at least one service class based on a received set of network measurements.

16. The communication network system defined in claim 13 wherein at least one node comprises a virtual buffer system for each class to perform at least one of the encoding and decoding functions.

17. The communication network system defined in claim 16 where the encoding and decoding functions are computed with respect to a virtual graph for the service class to which the encoding and decoding functions belong.

18. The communication network system defined in claim 16 wherein the virtual buffer system includes at least one buffer and function unit shared across different service classes.

19. The communication network system defined in claim 16 wherein the virtual buffer system includes separate buffer and function unit for each different service class.

20. The communication network system defined in claim 8 wherein the virtual topology graph is computed by computing a common virtual graph given history of observed topology graphs and decomposing the virtual graph into a collection of virtual sub-graphs using the service requirements of different service classes and topology statistics.

21. The communication network system defined in claim 8 wherein the virtual topology graph is computed by:

decomposing a sequence of observed topologies into separate sequences of topologies, each separate sequences of topologies being for a unique service class;

conserving total resources used by all the service classes at each observation interval;

using quality of service requirements of each service class and the topology statistics in decomposition; and

forming a virtual graph for each sequence using the topology statistics of said each sequence.

22. The communication network system defined in claim 8 wherein the virtual topology graph is computed using averages of at least one of long term link capacity and bandwidth and higher order statistics.

29. The communication network system defined in claim 8 wherein the mathematical operation comprises linear combinations on Galois bit fields.

33. The communication network system defined in claim 8 wherein the mathematical operation comprises a bit-wise XOR operation.

23. A network node comprising:

a physical incoming interface;

a virtual buffer system to buffer incoming data and apply a network code to the incoming data based on traffic class and based on meeting requirements of the traffic class, where the network code comprises a mathematical operation that the virtual buffer system applies to incoming data to transform the incoming packet data into encoded packet data associated with each class, the virtual buffer system being operable to place the encoded packet data into virtual output buffers associated with said each class, wherein the mathematical operation for the network code for at least one distinct traffic class comprises an operation performed jointly on a plurality of packets of the one traffic class;

a scheduler coupled to the virtual buffer system to cause codes generated by the virtual buffer system to be output, wherein the scheduler allocates one or more of short-term and long-term bandwidth and short-term and long-term rate based on a virtual graph associated with a given virtual output buffer; and

a physical outgoing interface coupled to the virtual buffer system and the scheduler to output codes generated by the virtual buffer system and stored in the virtual output buffers under control of the scheduler.

24. The network node defined in claim 23 wherein the encoding function used for each service class and the service class of the packet jointly determine which packet to place on which virtual incoming buffer.

25. The network node defined in claim 23 wherein the virtual buffer system comprises:

buffers to buffer input packets upon arrival and output packets for transmission;

an encoding unit to employ encoding functions to map input packets to output packets on outgoing physical interfaces;

a scheduler to determine buffering time of input packets and the associated number of output packets generated at each node.

30. The network node defined in claim 23 wherein the mathematical operation comprises linear combinations on Galois bit fields.

34. The network node defined in claim 23 wherein the mathematical operation comprises a bit-wise XOR operation.

26. A method to perform virtual topology based service provisioning and service differentiation in a network having a time-varying network topology, the method comprising:

decoupling a fixed virtual network graph representing the time-varying topology into two or more virtual topologies, each of the two or more virtual topologies being associated with a different traffic class;

assigning a network code to each of the two or more virtual topologies based on quality of service (QoS) provisioning;

processing, at a network node, incoming data by differentiating flows with respect to their priority levels, their associated network coding functions and corresponding routes, including encoding the incoming data for each traffic class separately to transform the incoming data into encoded packet data associated with each class by applying a mathematical operation associated with the network code assigned to and associated with each of the two or more virtual topologies based on quality of service (QoS) provisioning, wherein the mathematical operation for the network code for at least one distinct traffic class comprises an operation performed jointly on a plurality of packets of the at least one distinct traffic class.

27. The method defined in claim 26 wherein each traffic class is a QoS class and is encoded separately, with results of the encodings of each class being placed into their respective priority queues at an outgoing physical interface of a node.

31. The method defined in claim 26 wherein the mathematical operation comprises linear combinations on Galois bit fields.

35. The method defined in claim 26 wherein the mathematical operation comprises a bit-wise XOR operation.