CS 498 Lecture 18 TCP Implementation in LinuxFlow Controltcp_select_window()TCP Implementation in LinuxSlide 5Window Kept at the Receivertcp_receive_window()__tcp_select_window()Window Scaling OptionSlide 10Zero-Window Probingtcp_send_probe0()tcp_write_wakeup()tcp_xmit_probe_skb()tcp_ack_probe()Congestion ControlTCP Congestion Controltcp_v4_init_sock()reno_cong_avoid()Slide 20tcp_enter_loss()tcp_recalc_ssthresh()Fast Retransmit and Fast RecoveryNagle AlgorithmCS 498 Lecture 18 TCP Implementation in LinuxJennifer HouDepartment of Computer Science University of Illinois at Urbana-ChampaignReading: Chapter 24, The Linux Networking Architecture: Design and Implementation of Network Protocols in the Linux KernelFlow Controltcp_select_window()Is invoked in the tcp_transmit_skb() method when a TCP segment is sent to specify the advertised window.Invokes tcp_receive_window() to obtain the current advertised window size.Invokes __tcp_select_window() to obtain the available space in the computer.Advances the receiver window and determines the advertised window size, by ensuring that the credit already granted is not taken away.TCP Implementation in Linuxip_input.cip_input.cip_local_deliverip_output.cip_output.cip_queue_xmittcp_v4_rcvtcp_v4_do_rcv__tcp_v4_lookup()tcp_rcv_establishedTCP_ESTABLISHEDtcp_rcv_state_processtcp_sendmsgtcp_send_skbtcp_transmit_skbtcp_ack_snd_checktcp_data_snd_checktcp_write_xmittcp_write_timertcp_re -transmit_skbtcp_send_(delayed)_acktcp_acktcp_datatcp_data _queuesk->data_readyFast PathFast PathSlowPathsendPureACKRetrans.TimerTCPAbschnitt 24.3tcp_select_window()static __inline__ u16 tcp_select_window(struct sock *sk){ struct tcp_sock *tp = tcp_sk(sk); u32 cur_win = tcp_receive_window(tp); u32 new_win = __tcp_select_window(sk); /* Never shrink the offered window */ if(new_win < cur_win) { new_win = cur_win; } tp->rcv_wnd = new_win; tp->rcv_wup = tp->rcv_nxt; /* RFC1323 scaling applied */new_win >>= tp->rx_opt.rcv_wscale; /* If we advertise zero window, disable fast path. if (new_win == 0) tp->pred_flags = 0; return new_win; 252 }Window Kept at the ReceiverData not yet acknowledgedRemaining transmitcreditData received andacknowledgedSequence numberrcv_nxtrcv_wup + rcv_wndrcv_wuptcp_receive_window()static __inline__ u32 tcp_receive_window(const struct tcp_sock *tp){ s32 win = tp->rcv_wup + tp->rcv_wnd - tp->rcv_nxt; if (win < 0) win = 0;return (u32) win;}__tcp_select_window()u32 __tcp_select_window(struct sock *sk){ struct tcp_opt *tp = &sk->tp_pinfo.af_tcp; int mss = tp->ack.rcv_mss; int free_space = tcp_space(sk); (…)if (free_space < mss) return 0; window = tp->rcv_wnd; if (window <= free_space - mss || window > free_space)window = (free_space/mss)*mss; return window; } If the old credit is larger or smaller by more than one MSS, the available buffer, window, is set to thenext smaller multiple of a MSS.Window Scaling OptionThe TCP protocol header has a 16-bit window field a transmit credit of 65535 bytes can be granted.With the transmission rate of 10 Mbps and round-trip time of 100 ms, a connection would require a transmit window of 125000 bytes.The window scaling option is used to increase the value range for the advertised window size from 216 to 216 . 2F, where F is the exponent specified by this option.Window Scaling OptionCan only be sent in a SYN or SYN-ACK segment.The maximum scaling factor is limited to 214, i.e., the maximum byte sequence number is 216. 214 = 230 < 231 to prevent byte-sequence-number overflow.Type:4 Len:3Shift count1 Byte 1 Byte1 ByteZero-Window ProbingTo prevent deadlock in the case that the advertised window is zero and no packet can be sent (and hence obtains the update on the advertised window in the corresponding ack),TCP keeps an additional timer. When the timer expires, TCP sends a zero-byte packet.static void tcp_probe_timer(struct sock *sk) { if (tp->probes_out > max_probes) { tcp_write_err(sk);} else {tcp_send_probe0(sk); }tcp_send_probe0()void tcp_send_probe0(struct sock *sk) { struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp); int err; err = tcp_write_wakeup(sk); if (tp->packets_out || !tp->send_head) { /* Cancel probe timer, if it is not required. */ tp->probes_out = 0; tp->backof = 0; return; } if (err <= 0) { tp->backof++; tp->probes_out++; tcp_reset_xmit_timer (sk, TCP_TIME_PROBE0, min(tp->rto << tp->backof, TCP_RTO_MAX)); } else { ………..} } Generates and sends a zero-windowprobe packetIf tpsend_head == NULL or thereexist outstanding packets, there is no need to send probe packetsIf a packethas been sentMin(tprto . 2tpbackoff, TCP_RTO_MAX)tcp_write_wakeup()int tcp_write_wakeup(struct sock *sk) { (…) if ((skb = tp->send_head) != NULL && before(TCP_SKB_CB(skb)->seq, tp->snd_una+tp->snd_wnd)) {err = tcp_transmit_skb(sk, skb_clone(skb, GFP_ATOMIC)); (…)return err; } else { return tcp_xmit_probe_skb(sk, 0); } }tcp_xmit_probe_skb()static int tcp_xmit_probe_skb(struct sock *sk, int urgent) { struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp); struct sk_buf *skb; skb = alloc_skb(MAX_TCP_HEADER, GFP_ATOMIC); if (skb == NULL) return -1; /* Reserve space for headers and set control bits. */ skb_reserve(skb, MAX_TCP_HEADER); skb->csum = 0; TCP_SKB_CB(skb)->flags = TCPCB_FLAG_ACK; TCP_SKB_CB(skb)->sacked = urgent; TCP_SKB_CB(skb)->seq = urgent ? tp->snd_una : tp->snd_una - 1; TCP_SKB_CB(skb)->end_seq = TCP_SKB_CB(skb)->seq; TCP_SKB_CB(skb)->when = tcp_time_stamp; return tcp_transmit_skb(sk, skb); }tcp_ack_probe()tcp_ack_probe(sk,ack) is invoked in tcp_ack() when a TCP segment with the ACK flag is received and the segment is a zero-window probe segment.static void tcp_ack_probe(struct sock *sk) { struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp); /* Was it a usable window open? */ if (!after(TCP_SKB_CB(tp->send_head)->end_seq, tp->snd_una + tp->snd_wnd)) { tp->backof = 0; tcp_clear_xmit_timer(sk, TCP_TIME_PROBE0); } else { tcp_reset_xmit_timer(sk, TCP_TIME_PROBE0, min(tp->rto << tp->backof, TCP_RTO_MAX));} }Congestion ControlTCP Congestion Controltcp_v4_init_sock()static int tcp_v4_init_sock(struct sock *sk) { struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp); skb_queue_head_init(&tp->out_of_order_queue); tcp_init_xmit_timers(sk); tcp_prequeue_init(tp); tp->rto = TCP_TIMEOUT_INIT; (…)tp->snd_cwnd = 2; tp->snd_ssthresh = 0x7ffff; /* Infinity */ tp->snd_cwnd_clamp = ~0; tp->mss_cache = 536; (…)sk->state = TCP_CLOSE; (…)return 0;}reno_cong_avoid()tcp_cong_avoid(tp) implements the slow-start and congestion-avoidance
View Full Document
Unlocking...