Integrated method for performing scheduling, routing and access control in a computer network

• US 6,894,991 B2
• Filed: 11/30/2000
• Issued: 05/17/2005
• Est. Priority Date: 11/30/2000
• Status: Expired due to Fees

• Current Assignee: University of Maryland, Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Genuity Inc. (Lumen Technologies, Inc.), Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Ephremides, Anthony, Ayyagari, Deepak V.
• Primary Examiner(s): Phan, Man U.
• Application Number:
  US09/727,926
• Publication Number:
  US 20020101822A1
• Time in Patent Office: 1,629 Days
• Field of Search: 370 31-331, 370408-468, 370/345, 370/355, 455446-449, 455450-453, 709224-229, 709/249, 709/250
• US Class Current: 370/325
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS

Abstract

An integrated highly adaptive method is presented to perform scheduling, routing and access control in a network. The network is made up of a plurality of nodes interconnected by links between at least some of the nodes wherein at least one path interconnects all of the plurality of nodes. The nodes are organized into at least one of a cluster and a clique and the network has a network-wide capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links. The plurality of nodes can be configured to process at least one flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network.

Claims

1. An integrated highly adaptive method to perform scheduling, routing and access control in a network, the network made up of a plurality of nodes interconnected by links between at least some of the nodes wherein at least one path interconnects all of the pluraity of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network having a network-wide capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the method comprising the step of:

allocating the network-wide capacity among each of the nodes in the at least one of a cluster and a clique at the beginning of a time frame on the network, wherein the network-wide capacity allocated to each of the nodes in the at least one of a cluster and a clique is performed based upon at least one node-level performance metric of the network; and

repeating the capacity allocating step at the beginning of each time frame.

2. The method of claim 1 and further comprising the step of allocating the capacity allocated to each node in the at least one of a cluster and a clique among each of the flows associated with that node at the beginning of a time frame on the network, wherein the capacity allocated to each of the flows in the node is performed based upon at least one flow-level performance metric of the network.

3. The method of claim 2 and further comprising the step of routing the flow associated with each node to a neighboring node.

4. The method of claim 3 wherein the routing step further comprises the step of computing all possible routes of that a flow can take to its destination and selecting a desired route based upon at least one routing performance metric of the network.

5. The method of claim 4 wherein the routing step further comprises the step of selecting the neighboring node for each flow of each node that lies on the desired route.

6. The method of claim 5 wherein the at least one node-level performance metric comprises a measure of the backlog of packets to be sent by a node and the node-level performance metric is measured independently for each node in the at least one of a cluster and a clique.

7. The method of claim 6 wherein the at least one node-level performance metric further comprises a measure of the link errors experienced in the previous time frame by a node and the performance metric is measured independently for each node in the at least one of a cluster and a clique.

8. The method of claim 7 wherein the at least one flow-level performance metric comprises a measure of the backlog of packets to be sent by a node and the node-level performance metric is measured independently for each node in the at least one of a cluster and a clique.

9. The method of claim 8 wherein the at least one flow-level performance metric further comprises a measure of the link errors experienced in the previous time frame by a node and the performance metric is measured independently for each node in the at least one of a cluster and a clique.

10. The method of claim 1 wherein the step of allocating the capacity of the network further comprises the step of calculating a link error adjusted rate for each node in the at least one of a cluster and a clique, wherein the link error adjusted rate is representative of the node-level performance metric.

11. The method of claim 10 and further comprising the step of calculating a weighting value for each node corresponding to a representative portion of the link error adjusted rate of the node as compared with the sum of the link error adjusted rate for the corresponding at least one of a cluster and a clique.

12. The method of claim 11 and further comprising the step of allocating capacity among the nodes in the at least one of a cluster and a clique by integrally calculating the product of the capacity of the at least one of a cluster and clique with the weighting value for each node.

13. The method of claim 12 and further comprising the step of determining whether any of the capacity of the at least one of a cluster and a clique remains unallocated among the nodes of the at least one of a cluster and a clique.

14. The method of claim 13 and further comprising the step of allocating any unallocated capacity to a node having a highest weighting value from a previous iteration if the unallocated capacity is less than a predetermined threshold value.

15. The method of claim 2 wherein the step of allocating the capacity of the node further comprises the step of calculating a link error adjusted rate for each flow in the node, wherein the link error adjusted rate is representative of the flow-level performance metric.

16. The method of claim 15 and further comprising the step of calculating a weighting value for each flow corresponding to a representative portion of the link error adjusted rate of the flow as compared with the sum of the link error adjusted rate for the corresponding node.

17. The method of claim 16 and further comprising the step of allocating capacity among the flows in the node by integrally calculating the product of the capacity of the node with the weighting value for each flow.

18. The method of claim 17 and further comprising the step of determining whether any of the capacity of the node remains unallocated among the flows of the node.

19. The method of claim 18 and further comprising the step of allocating any unallocated capacity to a flow having a highest weighting value from a previous iteration if the unallocated capacity of the node is less than a predetermined threshold value.

20. The method of claim 4 and further comprising the step of computing a most efficient route for each flow based upon the at least one routing performance metric of the network.

21. The method of claim 20 wherein the routing performance metric comprises the sum of the time frame length divided by the capacity allocated to each node along the route, and the selected route comprises the minimum of the routing performance metric.

22. The method of claim 21 and further comprising the step of determining a neighboring node to the flow corresponding to the desired route.

23. In a highly adaptive integrated network for performing scheduling, routing and access control in a network comprising at least physical, link and network layers made up of a plurality of nodes interconnected by links between at least some of the nodes, wherein at least one path interconnects all of the plurality of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network including the capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the improvement comprising:

the physical, link layer and network layers being interdependently integrated with one another by at least one of a scheduling, routing, and access control decision in a current time frame being made by relying on at least one of a scheduling, routing and access control decision made in a previous time frame.

24. The network of claim 23 wherein the physical layer is a wireless medium.

25. The network of claim 24 wherein the physical layer includes both wireless and wire-based media.

26. The network of claim 25 wherein at least one of the physical, link and network layers incorporate a node-level scheduling routine for allocating capacity among the plurality of nodes of the network.

27. The network of claim 26 wherein at least one of the physical, link and network layers incorporate a flow-level scheduling routine for allocating capacity each node among any flow corresponding to that node.

28. The network of claim 27 wherein the network layer incorporates a muting routine for determining a destination for the at least one flow of the plurality of nodes of the network based upon a characteristic of at least one of the physical and link layers.

29. The network of claim 23 wherein the physical layer includes both wireless and wire-based media.

30. The network of claim 23 wherein at least one of the physical, link and network layers incorporate a node-level scheduling routine for allocating capacity among the plurality of nodes of the network.

31. The network of claim 23 wherein at least one of the physical, link and network layers incorporate a flow-level scheduling routine for allocating capacity of each node among any flow corresponding to that node.

32. The network of claim 23 wherein the network layer incorporates a routing routine for determining a destination for any flow corresponding to each node based upon a characteristic of at least one of the physical and link layers.

33. In an improved, highly adaptive integrated network for performing scheduling, routing and access control in a network comprising at least physical, link and network layers made up of a plurality of nodes interconnected by links between at least some of the nodes, wherein at least one path interconnects all of the plurality of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network including a capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the improvement comprising:

the physical, link layer and network layers being interdependently integrated with one another by at least one of a scheduling, routing, and access control decision in a current time frame being made by relying on at least one of a scheduling, routing and access control decision made in a previous time frame; and

wherein the network layer incorporates a routing routine for determining a destination for the at least one flow processed by the plurality of nodes of the network based upon a characteristic of at least one of the physical and link layers.

34. In an improved, highly adaptive integrated network for performing scheduling, muting and access control in a network comprising at least physical, link and network layers made up of a plurality of nodes interconnected by links between at least some of the nodes, wherein at least one path interconnects all of the plurality of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network including a capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the improvement comprising:

the physical, link layer and network layers being interdependently integrated with one another by at least one of a scheduling, routing, and access control decision in a current time frame being made by relying on at least one of a scheduling, routing and access control decision made in a previous time frame; and

wherein the network layer incorporates a routing routine for determining a destination for any flow corresponding to each node based upon a characteristic of at least one of the physical and link layers.

35. An integrated highly adaptive method to perform scheduling, routing and access control in a network, the network made up of a plurality of nodes interconnected by links between at least some of the nodes wherein at least one path interconnects all of the plurality of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network having a network-wide capacity to send data packets in slots being grouped into fixed length time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the method comprising the step of:

allocating the network-wide capacity among each of the nodes in the at least one of a cluster and a clique at the beginning of a fixed length time frame on the network, wherein the network-wide capacity allocated to each of the nodes in the at least one of a cluster and a clique is performed based upon at least one node-level performance metric of the network; and

repeating the capacity allocating step at the beginning of each fixed length time frame.

36. In an improved, highly adaptive integrated network for performing scheduling, routing and access control in a network comprising at least physical, link and network layers made up of a plurality of nodes interconnected by links between at least some of the nodes, wherein at least one path interconnects all of the plurality of nodes, wherein the nodes are organized into at least one of a cluster and a clique, the network including a capacity to send data packets in slots delineating time frames on the network between the nodes on the network defined by the links, the plurality of nodes being configured to process at least one flow, a flow comprising at least a portion of a transmitted and received data packet for which the plurality of nodes must manage to get the data packets to a desired node on the network, the improvement comprising:

each of the slots being grouped into a fixed length time frame; and

the physical, link layer and network layers being interdependency integrated with one another by at least one of a scheduling, routing, and access control decision in a current time frame being made by relying on at least one of a scheduling, routing and access control decision made in a previous time frame.