Без темы
<<  CM 4WD (ITM) CODISPOSAL  >>
CNPA B
CNPA B
Content
Content
Introduction
Introduction
FIFO
FIFO
FIFO, cont
FIFO, cont
FIFO, cont
FIFO, cont
FIFO, cont
FIFO, cont
Fair Queuing (FQ)
Fair Queuing (FQ)
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
FQ, cont
Weighted Fair Queuing (WFQ)
Weighted Fair Queuing (WFQ)
WFQ, cont
WFQ, cont
Example
Example
Example, cont
Example, cont
Solution
Solution
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Solution, cont
Reference
Reference

Презентация на тему: «CNPA B». Автор: Y. Daniel Liang. Файл: «CNPA B.ppt». Размер zip-архива: 310 КБ.

CNPA B

содержание презентации «CNPA B.ppt»
СлайдТекст
1 CNPA B

CNPA B

Nasser S. Abouzakhar Queuing Disciplines Week 8 – Lecture 2 16th November, 2009

1

2 Content

Content

Introduction FIFO (first-in-first-out) FQ (fair queuing)

2

3 Introduction

Introduction

Each router must implement some queuing discipline that governs how packets are buffered while waiting to be transmitted. The queuing algorithm can be thought of as: allocating BW (which packets are transmitted), and allocating buffer space (which packets get dropped). It also affects the packets latency, by determining how long a packet waits to be transmitted. The two common queuing algorithms are FIFO and FQ (Fair Queuing)

3

Source: Peterson & Davie, 2007 p 467

4 FIFO

FIFO

Also known as FCFS (first-come-first-served). The first packet that arrives at a router is the first packet to be transmitted. The router discards packets that arrive whilst the queue (buffer space) is full. This is sometimes called tail drop.

(a) FIFO queuing (b) tail drop at a FIFO queue.

4

Source: Peterson & Davie, 2007 p 468

5 FIFO, cont

FIFO, cont

FIFO is a scheduling discipline. determines the order in which packet are transmitted. Tail drop is a drop policy. determines which packets get dropped. FIFO with tail drop is the simplest of all queuing algorithms and the most widely used in Internet routers.

5

Source: Peterson & Davie, 2007 p 469

6 FIFO, cont

FIFO, cont

Priority queuing is a simple variation on basic FIFO queuing. Marks each packet with a priority. For example, the IP Type of Service (TOS) field. The routers then implements multiple FIFO queues, one for each priority class. The router always transmits packets out of the highest-priority queue. Limitations: The high-priority queue can starve out all the other queues.

6

Source: Peterson & Davie, 2007 p 469

7 FIFO, cont

FIFO, cont

The routers implement multiple FIFO queues, one for each class. Packets with highest-priority are transmitted first. However, the high-priority queue can dominate the front lines hence the lower-priority queues don’t get served. Therefore, there should be certain limits on how much high-priority traffic is inserted in the queue.

7

Source: Peterson & Davie, 2007 p 469

8 Fair Queuing (FQ)

Fair Queuing (FQ)

FIFO does not discriminate between different traffic sources. FIFO does not separate packets according to the flow to which they belong. FQ maintains a separate queue for each flow currently being handled by the router. These queues are served by the router in a round-robin service.

8

Source: Peterson & Davie, 2007 p 470

9 FQ, cont

FQ, cont

When a flow sends packets too quickly, then its queue fills up. When a queue reaches a certain length, any additional packets are discarded. Therefore, a given source cannot increase its share of the network’s capacity at the expense of the other queues.

Round-robin service of four flows at a router.

9

Source: Peterson & Davie, 2007 p 470

10 FQ, cont

FQ, cont

The packets being processed at a router may not have the same length. To allocate the BW of outgoing link in a fair manner, packets length is taken into account. Example: If one router is managing 2 flows, one with 1000-byte packets and the other with 500-byte packets. A round-robin servicing packets from each flow’s queue will give the 1st flow 2/3 of the link’s BW and the 2nd flow only 1/3 of its BW.

10

Source: Peterson & Davie, 2007 p 471

11 FQ, cont

FQ, cont

FQ determines when a given packet would finish being transmitted. The finishing time is used to sequence the packets for transmission. Let Pi denote the length of packet i in bits. Let Si denote the time when the router starts to transmit packet i. Pi is expressed in terms of clock ticks to transmit packet i. Let Fi denote the time when the router finishes transmitting packet i.

11

Source: Peterson & Davie, 2007 p 471

12 FQ, cont

FQ, cont

Routers often have more than one active flow i.e. has data in the queue. We calculate Fi for each packet that arrives using the above formula. We treat all the Fi as timestamps, and the packet that has the lowest timestamp will be transmitted first.

12

Source: Peterson & Davie, 2007 p 472

13 FQ, cont

FQ, cont

It is possible that the router finished transmitting packet i – 1 long before i arrived. This means that the round-robin mechanism could not send any packets from this flow during which the queue was empty. If so, then let Ai denote the time that packet i arrives at the router, thus

13

Source: Peterson & Davie, 2007 p 472

14 FQ, cont

FQ, cont

If there is more than one flow, we calculate Fi as timestamps for each flow. The packet with the lowest timestamp is transmitted first.

Packets with earlier finishing times are sent first. Sending of a packet already in progress is completed.

14

Source: Peterson & Davie, 2007 p 472

15 Weighted Fair Queuing (WFQ)

Weighted Fair Queuing (WFQ)

allows a weight to be assigned to each flow (queue). specifies how many bits to send (BW) each time the router services that queue. Example: a router has 3 flows (queues), one queue has a weight of 2, the second queue has a weight of 3, and the third queue has a weight of 1. Assuming that each flow always contains a packet waiting to be sent, what is the percentage of BW that is assigned to each flow?

15

Source: Peterson & Davie, 2007 p 473

16 WFQ, cont

WFQ, cont

Solution The first flow will get 1/3 of the available BW. The second flow will get ? of the available BW. The third flow will get 1/6 of the available BW.

16

Source: Peterson & Davie, 2007 p 473

17 Example

Example

Suppose a router has 3 input flows and one output. It receives the packets listed in Table 1 all at about the same time, in the order listed, during a period in which the output port is busy but all queues are otherwise empty. Give the order in which the packets are transmitted, assuming: Fair queuing. Weighted fair queuing with flow 1 having a weight of 2, flow 2 having twice as much share as flow 1, and flow 3 having 1.5 times as much share as flow 1. Note that ties are to be resolved in order flow 1, flow 2, flow 3.

17

Source: Peterson & Davie, 2007 p 529

18 Example, cont

Example, cont

Packet

Size

Flow

1

200

1

2

200

1

3

160

2

4

120

2

5

160

2

6

210

3

7

150

3

8

90

3

Table 1

18

Source: Peterson & Davie, 2007 p 530

19 Solution

Solution

(a) Fi is the cumulative per-flow size. Consider Ai = 0 as all packets are received at about the same time so there is no waiting.

Packet

Size

Flow

Fi

1

200

1

200

2

200

1

400

3

160

2

160

4

120

2

5

160

2

6

210

3

7

150

3

8

90

3

19

Source: Peterson & Davie, 2007 p 737

20 Solution, cont

Solution, cont

Packet

Size

Flow

Fi

1

200

1

200

2

200

1

400

3

160

2

160

4

120

2

280

5

160

2

440

6

210

3

210

7

150

3

360

8

90

3

450

20

21 Solution, cont

Solution, cont

So, packets are sent in increasing order of Fi: Packet 3, Packet 1, Packet 6, Packet 4, Packet 7, Packet 2, Packet 5, Packet 8.

Packet

Size

Flow

Fi

1

200

1

200

2

200

1

400

3

160

2

160

4

120

2

280

5

160

2

440

6

210

3

210

7

150

3

360

8

90

3

450

21

22 Solution, cont

Solution, cont

(b) Flow 1 has a weight of 2, so Flow 2 has a weight of 4, so Flow 3 has a weight of 3, so

Packet

Size

Flow

Weighted Fi

1

200

1

100

2

200

1

200

3

160

2

40

4

120

2

5

160

2

6

210

3

7

150

3

8

90

3

22

Source: Peterson & Davie, 2007 p 737

23 Solution, cont

Solution, cont

Packet

Size

Flow

Weighted Fi

1

200

1

100

2

200

1

200

3

160

2

40

4

120

2

70

5

160

2

110

6

210

3

70

7

150

3

120

8

90

3

150

23

24 Solution, cont

Solution, cont

So, packets are sent in increasing order of weighted Fi: Packet 3, Packet 4, Packet 6, Packet 1, Packet 5, Packet 7, Packet 8, Packet 2.

Packet

Size

Flow

Weighted Fi

1

200

1

100

2

200

1

200

3

160

2

40

4

120

2

70

5

160

2

110

6

210

3

70

7

150

3

120

8

90

3

150

24

25 Reference

Reference

Computer Networks: A systems approach by Larry Peterson and Bruce Davie, published by Morgan Kaufmann (Fourth edition ISBN: 0 12 370548 7).

25

«CNPA B»
http://900igr.net/prezentacija/anglijskij-jazyk/cnpa-b-96746.html
cсылка на страницу

Без темы

661 презентация
Урок

Английский язык

29 тем
Слайды