1 Introduction
1.1 Content versus Services in NDN
- SQL queries have different execution times depending on the complexity of the query.
- A service that encrypts/decrypts a file requires varying execution times depending on the size of the file and the complexity of the encryption algorithm.
- The execution times of basic algorithms (e.g., sorting, tree balancing) as well as advanced ones (e.g., machine learning algorithms) depend heavily on the input of the algorithm. Hence any service that includes such algorithms would have a large variation in its execution time.
1.2 Literature Study
1.3 Communicating Vessels
1.4 Contributions of the Paper
1.5 Structure of the paper
2 Technical Background
3 Load Balancing in Traditional Networks
3.1 Round-Robin Algorithms
3.2 Load Balancing as a Scheduling Problem
3.3 Heuristic Load Balancing
3.4 Main Takes from Traditional Load Balancing
Approach | Architecture | Based on rate or window | Detection metrics | Congestion notification |
---|---|---|---|---|
ICP [37] | Consumer-based | Window-based | Expiration timer computed from the history of RTTs | Timeout-based |
ECP [38] | Consumer-based | Window-based | The queue size of Interests | Explicit notification (NACK messages) |
CCTCP [39] | Consumer-based | Window-based | RTO and RTT per source | Implicit notifications |
RAAQM [40] | Consumer-based | Window-based | RTO timeouts per route and RTT value per path | Timeout-based |
Braun et al. [41] | Consumer-based | Window-based | RTO and RTT per CS | Timeout-based |
Park et al. [42] | Router-based | Rate-based | The maximum Interest rate per face | Explicit congestion notification |
Carofiglio et al. [43] | Router-based | Window-based | A separate RTO per route and the maximum number of Interests the router is allowed to send | Timeout-based |
Wang et al. [44] | Router-based | Window-based | The optimal rate of each router calculated based on the bandwidth value | Hop-by-hop NACK messages |
IRNA [45] | Router-based | Rate-based | The max and the min capacity of the Interest queue per face | Explicit congestion notifications |
HoBHIS [46] | Router-based | Rate-based | The Interest rate calculated based to the chunk queue length | Explicit Interest rate feedback |
Nguyen et al. [47] | Hybrid-based | Window-based | A congestion window and RTO value per aggregated flow (face) | Timeout-based |
ChopCop [48] | Hybrid-based | Window-based from the consumer side and delay-based on the routers | The outgoing data queue length | Explicit congestion |
Kato et al. [49] | Hybrid-based | Window-based | The optimal rate per flow and the RTT value between neighbors | Explicit congestion notifications |
MIRCC [50] | Hybrid-based | Rate-based | The local rate and rate of the flow path | NACK messages |
HR-ICP [51] | Hybrid-based | Window-based (ICP [37]) on the consumer side and rate-based on the router side | Fair share per flow per face and expiration timer caculated based on the history of RTT | Timeout-based from the consumer side |
4 Congestion Control as a Load Balancing Mechanism
4.1 Consumer-Based Congestion Control
4.2 Router-Based Congestion Control
4.3 Hybrid Methods for Congestion Control
4.4 Congestion Control and Load Balancing in NDN
5 Forwarding Strategies
5.1 Local Forwarding Strategies
Approach | Metrics | Changes to NDN | Forwarding decision |
---|---|---|---|
MABS [87] | Retrieval time of each content per face | Pure NDN | Interests are sent to the face with the lowest retrieval time |
SAF [88] | Delay, hop-count, and transmission cost | New table (FWT) to store face probabilities | Interests are sent to the best face according to their probabilities |
INFORM [70] | RTT (delay of all faces) | New values (Q-values) are added to FIB. | Interests are sent to the face with the minimum delay |
Stateful forwarding [61] | Smoothed RTT (SRTT) | Stores more information about face status | Interests are sent to the most highly available face with the best possible classification |
EPF [73] | Face availability and RTT | Pure NDN | Interests are sent based on the weights and probabilities of faces |
MDPF [72] | Interface status, pending Interest numbers | Pure NDN | Interests are sent to the face chosen based on MD method [89] |
SoCCeR [69] | Provider status (CPU, memory, service load) | Pheromone tables | Interests are sent to the face with the highest probability |
PAF [71] | RTT | A complete layer is added called strategy layer with special functionalities | Interests are sent to the face with the probabilistically least delay |
GACF [90] | Path overhead, minimum bandwidth, RTT, and number of path hops | It splits the network into domains each is managed by an ISP in addition to the new forwarding tables | Interests are sent to the face with the highest pheromone value |
PBR [91] | Content quality measured based on node capabilities and outgoing link capacity | Complex forwarding strategy that requires control messages | Interests are sent to the node with the highest quality value |
DIVER [92] | Up-to-date content availability | A new DIVER FIB for probe packets | Interests are sent through the face which has the most up-to-date content |
SCAN [93] | Content availability | Hybrid routing using IP routing and content routing | Interests are sent based on IP routing during heavy traffic or content availability when scanning is possible |
5.2 Probing-Based Forwarding Strategies
5.3 Tradeoffs in Forwarding Strategies
6 Data Center Management over NDN
6.1 Data Centers Over Hybrid Networks
6.2 Data Centers over Pure NDN
6.3 Insights From Data Center Management
7 A Taxonomy of Design Choices for Load Balancing over NDN
7.1 Metrics
7.1.1 Round-Trip Time
7.1.2 Server Metrics
7.1.3 Job Size
7.1.4 Queue Size
7.2 NDN-Purity
7.2.1 Hybrid Networks
7.2.2 Extended NDN Networks
7.2.3 Pure NDN
7.3 Location
7.3.1 Load Balancing in the Routers
7.3.2 Load Balancing in a Facade Component
7.3.3 Load Balancing in a Controller
8 Communicating Vessels: A Load Balancing Approach
8.1 System Design
8.1.1 Extending the PIT
8.1.2 Queue Size
- The name ch/unibas/myService can be served on the faces 1, 3, and 5.
- The router received 10 Interests for this service; ch/unibas/myService/{x1 ... x10}.
- Three of these Interests are forwarded to face 1, six Interests to face 3, and one Interest is forwarded to face 5.
8.1.3 The Algorithm
Approach | Metric | NDN Purity | Location | ||||||
---|---|---|---|---|---|---|---|---|---|
RTT | Queue size | Server capabilities | No change or minor change | Major change | Hybrid solution | Router | Consumer | Controller | |
SoCCeR | ✓ | ✓ | ✓ | ||||||
PAF | ✓ | ✓ | ✓ | ||||||
GACF | ✓ | ✓ | ✓ | ✓ | |||||
SAF | ✓ | ✓ | ✓ | ||||||
INFOFRM | ✓ | ✓ | ✓ | ||||||
EPF | ✓ | ✓ | ✓ | ✓ | |||||
IRNA | ✓ | ✓ | ✓ | ||||||
ICP | ✓ | ✓ | ✓ | ||||||
ECP | ✓ | ✓ | ✓ | ||||||
ChopCop | ✓ | ✓ | ✓ | ✓ | |||||
HR-ICP | ✓ | ✓ | ✓ | ✓ | |||||
IC-DCN | ✓ | ✓ | ✓ | ||||||
NCMP | ✓ | ✓ | ✓ | ||||||
PBR | ✓ | ✓ | ✓ | ||||||
ComVes | ✓ | ✓ | ✓ |
8.2 Empirical Evaluation
8.2.1 Communicating Vessels in a Simple Topology
- Service parameter belongs to the range [200, 700]. This means that there are 500 Interests per experiment.
- We run the experiment several times with varying intervals between Interests. The interval ranges between 0.25 and 2 s, with a step of 0.25 s. This results in different Interest rates per minute.
- We collect the statistics about the response time for each Interest and the load on each replica.
8.2.2 Communicating Vessels in a Complex Topology
Parameter range | Interest interval (s) | 3-Replica face load | 1-Replica face load |
---|---|---|---|
1 to 1000 | 0.25 | 399 | 601 |
0.10 | 360 | 640 | |
501 to 1500 | 0.25 | 374 | 626 |
0.10 | 329 | 671 |
Topology | Interest interval (s) | Average response time (s) |
---|---|---|
Simple | 0.25 | 68.0 |
Complex | 0.25 | 84.9 |
Simple | 0.50 | 29.3 |
Complex | 0.50 | 37.0 |
- The consumer sends 500 Interests for the Bernoulli service with the parameter ranging from 201 to 700.
- High load of Interests with an interval of 0.25 and 0.5
8.2.3 Evaluation Summary
- It requires minimal changes to NDN routers i.e., only one column is added to the PIT table.
- It is computationally cheap on the router side i.e., only one simple calculation before forwarding Interests is needed.
- Optimal load balancing in simple network topologies.
- It requires no network probing or control messages.
- Near-optimal load balancing in complex network topologies, but with a trend towards optimality as the demand on the service increases.