$QS CSDRV.BCK CSDRV.BCKCBACKUP/BLOCK=2048 [.CSDRV] ANONYMOUS_ROOT:[CMU-TCPIP]CSDRV.BCK/SAVE UDAA055 @5bgV5.5 _BAY::  _$11$DIA62: V5.5-2  (*[UDAA055.TEMP.CMU.CSDRV]000-README.1ST;2+,W}./@ 4Mf-nf 0123KPWO56d/7e/89G@HJGThis saveset contains a Serial Line IP (SLIP) driver for CMU/OpenVMS IP1that implements Van Jacobson header compression. The files are as follows:M INSTALL_CSDRV.COM Command file to put CSDRV in the right place.= COMPILE_CSDRV.COM Command file to compile CSDRV: LINK_CSDRV.COM Command file to link CSDRVJ CSDRV.EXE Driver executable, linked under VMS V5.4-27 CSDRV.MAR Main driver source file CSDRV.OBJ3 NTOH.C Conversion routines NTOH.OBJ; RFC1144.C Header compression routines RFC1144.OBJ1 RFC1055.TXT RFC defining SLIPE RFC1144.TXT RFC defining Van Jacobson compression9 CMUIP-VMS.H Header file for RFC1144.CK CMUIP.MAR Miscellaneous macros that make up CMUIP.MLB CMUIP.MLBHCSDRV.EXE should be placed in CMUIP_ROOT:[SYSLIB], and CMU IP =9[ CSDRV.BCKW}nf ([UDAA055.TEMP.CMU.CSDRV]000-README.1ST;2M*restarted.HThe setup is the same as for SLDRV -- if you can get that to work, CSDRV@should just slot right in -- simply change "SLDRV" to "CSDRV" in!INTERNET.CONFIG and you're away. GSupport for CSDRV: I guarantee nothing. It works for me. Bug reports Eare more likely to be responded to if you make an effort to find the actual problem.FCSDRV is copyright Don Stokes 1994 (except for the bits I cribbed fromHelsewhere). Non-commercial distribution is permitted, but contributions?to my hacking fund or blood alcohol levels are always welcome. +Don Stokes , 23-Apr-1995&*[UDAA055.TEMP.CMU.CSDRV]CMUIP-VMS.H;11+,./@ 4M,-nf 0123KPWO56*7x89G@HJs5 CSDRV.BCKnf &[UDAA055.TEMP.CMU.CSDRV]CMUIP-VMS.H;11M"H/* cmuip-vms.h CMUIP-VMS definitions for CSLIP implementation 9/5/93/dcs *G * These definitions are needed to graft the code specified in RFC 1144M * ("Compressing TCP/IP Headers", Van Jacobson, February 1990) to CMU IP/VMS. */#include 6#include "/CMU_SRC/central/include/netinet/in_systm.h"0#include "/CMU_SRC/central/include/netinet/in.h"0#include "/CMU_SRC/central/include/netinet/ip.h"1#include "/CMU_SRC/central/include/netinet/tcp.h" struct mbuf {/ u_char *m_off; /* pointer to start of data */% int m_len; /* length of data */};"#define mtod(m, t) ((t)(m->m_off))0#define OVBCOPY(src,dst,len) memcpy(dst,src,len).#define BCOPY(src,dst,len) memcpy(dst,src,len)-#define BCMP(src,dst,len) memcmp(dst,src,len))#define bzero(dst,len) memset(dst,0,len)#*[UDAA055.TEMP.CMU.CSDRV]CMUIP.MAR;8+,./@ 40-nf 0123KPWO56@d+<7"89G@HJ CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CMUIP.MAR;80Z .macro struct, structname .if not_blank structname .blkb 'structname'_size .if_false __str_base = 0 __str_typ_byte = 1 __str_typ_word = 2 __str_typ_long = 4 __str_typ_addr = 4 __str_typ_quad = 8 __str_typ_dscr = 8 .endc .endm# .macro member, type, name, count=1 'name' = __str_base0 __str_base=__str_base+<__str_typ_'type'*count> .endm .macro endstruct structname 'structname'_size = __str_base .endm " .macro local, type, name, count=1 .if not_defined __lcl_base __lcl_base = 0 .endc __lcl_typ_byte = 1 __lcl_typ_word = 2 __lcl_typ_long = 4 __lcl_typ_addr = 8 __lcl_typ_quad = 8 __lcl_typ_dscr = 8 'name' = __lcl_base0 __lcl_base=__lcl_base+<__lcl_typ_'type'*count> .endm .macro base_register, reg subl2 #__lcl_base, SP movl SP, reg __lcl_base = 0 .endm   .macro cmuip_didef struct member addr DI$Init member addr DI$Xmit member addr DI$Dump member addr DI$Check member addr DI$ARP_Dump! endstruct device_info_structure .endm .macro cmuip_aidef struct member addr ACPI$IP_Receive# member addr ACPI$AST_in_progress member addr ACPI$Sleeping member addr ACPI$NOINT member addr ACPI$OKINT member addr ACPI$Device_Error member addr ACPI$IP_ISME member addr ACPI$Seg_Get member addr ACPI$Seg_Free member addr ACPI$QBlk_Free member addr ACPI$LOG_STATE member addr ACPI$QL_FAO member addr ACPI$LOG_FAO m\j CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CMUIP.MAR;805ember addr ACPI$OPR_FAO member addr ACPI$ERROR_FAO member addr ACPI$FATAL_FAO member byte ACPI$MPBS 2 endstruct IPACP_Info_Structure .endm .macro cmuip_dcdef struct member byte dc_begin 0 member dscr dc_devname member dscr dc_devspec member addr dc_dev_interface member long dc_ip_address member long dc_ip_netmask member long dc_ip_network member addr dc_rtn_Init member addr dc_rtn_Xmit member addr dc_rtn_Dump member addr dc_rtn_check member addr dc_Send_Qhead member addr dc_send_Qtail member long dc_flags dc_m_valid_device = 1 dc_v_valid_device = 0 dc_m_Online = 2 dc_v_Online = 1 dc_m_is_clone = 4 dc_v_is_clone = 2 member long dc_clone_dev member byte dcmib_begin 0 member long dcmib_ifIndex member dscr dcmib_ifDescr member long dcmib_ifType member long dcmib_ifMTU member long dcmib_ifSpeed member addr dcmib_ifPAsize" member addr dcmib_ifPhysAddress" member long dcmib_ifAdminStatus! member long dcmib_ifOperStatus member long dcmib_ifLastState member long dcmib_ifInOctets" member long dcmib_ifInUcastPkts# member long dcmib_ifInNUcastPkts! member long dcmib_ifInDiscards member long dcmib_ifInErrors& member long dcmib_ifInUnknownProtos member long dcmib_ifOutOctets# member long dcmib_ifOutUcastPkts$ member long dcmib_ifOutNUcastPkts" member long dcmib_ifOutDiscards member long dcmib_ifOutErg CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CMUIP.MAR;80)rors member long dcmib_ifOutQLen& endstruct Device_Configuration_Entry .endm .macro cmuip_nsqdef struct member addr NSQ$Next member addr NSQ$Last member addr NSQ$Driver member addr NSQ$Data member word NSQ$Datasize member long NSQ$IP_Dest member addr NSQ$Del_Buf member word NSQ$Del_buf_size member word NSQ$Type member byte NSQ$Retry member byte NSQ$Delete member word NSQ$IOSB 4 endstruct QB_Net_Send .endm+*[UDAA055.TEMP.CMU.CSDRV]COMPILE_CSDRV.COM;3+,../@ 4*X-nf 0123KPWO56/ -7 -89G@HJ*$ library/macro/create CMUIP.MLB CMUIP.MAR $ macro CSDRV $ gcc RFC1144 $ gcc NTOH$*[UDAA055.TEMP.CMU.CSDRV]CSDRV.EXE;64+,y ./@ 4-nf 0123 KPWO56i7b=i89G@HJX%ty CSDRV.BCKy nf $[UDAA055.TEMP.CMU.CSDRV]CSDRV.EXE;64`0DX0205+8iuh LCSDRVV05-001v8i05-05    ! VAXCRTL_001! LIBRTL_001O! MTHRTL_001 ^<P^ЬYйXм[ kZʏZԭ]VTTSХ k<ݧ<kkRЫQPbPPP PPۃPQݐTS0 ݥ<~ U$|~|~Sd|~ozaR3駾ȥcHJf]c.J?|OeCPP%2So-ra|;?O19 jֿ|%ǜ:##9΁EFw@\ߢ[Xo@u oQ1sGս7:"j,"O!Ĩl.5Yg2f<q!!] "30"Z M{hd{&vOqhm{;ڀ=xe=l/`8 Ot b.z-!rey IIӛL 㼁=ϒFh!cVHbVx(!ϪUg5T"!K7=}EK*[7vd/]}C]Y>ӸpCI9=`d6񪉋U}?Z2ÜC":&+XHQ+@kK[@8s#5:rfM{-@phSK*!WJL1 ND I6nIˇiKAͪF&  5+)LڡCK+c;ItbϗBXt<e\}5Yv?߉A};>֐5QZk 1+R(ϟ $r׌u f $ۆ'Rk]/L7 x}\HR/x -΂ 2lw(h'Dp<ٶH|&U= @e]yz5TPk$#3Ư%s7jsL! g+%Ks|M0с~Tg -([Tǜeo &MEL2s !mpξ:/*%|gҝN8Ѽ 3T`iܳM-cpP= ˕hs'^"!D۱b{F!nt>l+<{ ر&SHua)X# !H]P1H(pH45O9G@HJ  CSDRV.BCKy nf $[UDAA055.TEMP.CMU.CSDRV]CSDRV.EXE;64 ]DEFAULT_CLUSTER"4F`u=qX \b\ d5CSDRVV05-00124-APR-1995 01:1224-APR-1995 01:12VAX-11 Linker V05-05 .$$ABS$$.DRV$TRANSPORT_INIT aO CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7M\#*[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7+,./@ 4MZ-nf 0123KPWO56 h7h89G@HJ5 .title CSDRV Compressed SLIP IPACP transport driver;; Standard register usage:; R6 Device_Configuration_Entry; R7 SLIP_Channel; R8 Buffer number; R9 SLIP_Buffer; R10 IPACP info block"; R11 Local variable base register; astprm SLIP_Buffer; .library "CMUIP" cmuip_didef cmuip_aidef cmuip_dcdef cmuip_nsqdef .macro sts, ?L1 blbs R0, L1 pushl R0 calls #1, g^LIB$SIGNAL ret L1: .endm .macro debug pushl #SS$_DEBUG calls #1, g^LIB$SIGNAL .endm .macro LOG, string, ?L1, ?l2 ;; brb L1;;L2: .ascid string;;L1: pushaq L2!;; calls #1, g^LIB$PUT_OUTPUT .endm;; Useful constants;SLIP_END = 192SLIP_ESC = 219SLIP_ESC_END = 220SLIP_ESC_ESC = 221TYPE_IP = ^x40TYPE_UNCOMPRESSED_TCP = ^x70TYPE_COMPRESSED_TCP = ^x80TYPE_ERROR = 0MAX_HDR = 128 MTU = 1500BUFFER_SIZE = MTU*2XMIT_BUFFERS = 4RECV_BUFFERS = 8;; SLIP structures; struct" member addr sl_xmit  CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7M~xmit_buffers" member addr sl_recv recv_buffers member long sl_next_xmit member word sl_chan member byte sl_upflag member byte sl_startflag member addr sl_dc_info member addr sl_slcompress endstruct slip_channel struct' member long sb_number ; Index number3 member addr sb_channel ; Pointer back to channel) member word sb_iosb 4 ; IOSB for buffer+ member byte sb_active ; Buffer busy flag3 member byte sb_buffer buffer_size ; Actual buffer endstruct slip_buffer' struct ; Unix mbuf for grafting on/ member addr m_off ; Van Jacobson compression member long m_len endstruct mbuf ; ; Sharable image transfer vector;> .psect $TRANSFER$ pic,usr,con,rel,lcl,shr,noexe,rd,nowrt,quad .align quad .transfer DRV$TRANSPORT_INIT .mask DRV$TRANSPORT_INIT jmp g^DRV$TRANSPORT_INIT+2 * .psect CSDRV_RW, long,pic,noexe,noshr,wrt;K; Linkage stuff for IPACP to talk to us (initialised by DRV$TRANSPORT_INIT);drv_device_info: struct Device_Info_Structureipacp_interface: .blkl; ; $QIO stuff;term_mask_ptr: .long 32 .address term_maskterm_mask: .quad 0 ; 0-63 .quad 0 ; 64-127 .quad 0 ; 128-191 .quad 1 ; 192-255 (192 set)scr_dsc: .ascid ""ttchars: .blkqiosb: .blkw 4( .psect CSDRV_RE, long,pic,exe,shr,nowrt;A; Init-init routine. Set up the linkage between CSDRV and IPACP.; .entry DRV$TRANSPORT_INIT, ^M<> ;; debug, movab csdrv_init, drv_device_info+DY53J CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7MeI$Init, movab csdrv_xmit, drv_device_info+DI$Xmit, movab csdrv_null, drv_device_info+DI$Dump! clrl drv_device_info+DI$Check$ clrl drv_device_info+DI$ARP_Dump movab drv_device_info, R0 ret* .entry csdrv_null, ^M<> ; No-op routine' LOG <"CSDRV: Null routine called"> movl #1, R0 ret ;3; csdrv_init( Device_Configuration_Structure by ref; IPACP_Info_Structure by ref; max_retry by value&; max_physical_buffer_size by value );7 .entry csdrv_init, ^M local long to_alloc local addr mem_addr ;; debug LOG <"CSDRV: Init entered">0 base_register R11 ; R11 = stack base register+ movl 4(AP), R6 ; R6 = dev config stuff, movl 8(AP), R10 ; R10 = IPACP interface movl R10, ipacp_interface calls #0, @ACPI$NOINT(R10);; Allocate & init SLIP channel;* movl #slip_channel_size, to_alloc(R11) pushab mem_addr(R11) pushab to_alloc(R11) calls #2, g^LIB$GET_VM5 movl mem_addr(R11), R7 ; R7 = SLIP channel block! movl R7, dc_dev_interface(R6) clrb sl_upflag(R7) clrb sl_startflag(R7) clrl sl_next_xmit(R7) movl R6, sl_dc_info(R7);9; Allocate receive buffers and link back to channel block; clrl R8,1$: movl #slip_buffer_size, to_alloc(R11) pushab mem_addr(R11) pushab to_alloc(R11) calls #2, g^LIB$GET_VM/ movl mem_addr(R11), R9 ; R9 = buffer block movl R9, sl_recv(R7)[R8] movl R7, sb_chan`@ CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7M> nel(R9) movl R8, sb_number(R9) clrb sb_active(R9) aoblss #RECV_BUFFERS, R8, 1$;:; Allocate transmit buffers and link back to channel block; clrl R8,2$: movl #slip_buffer_size, to_alloc(R11) pushab mem_addr(R11) pushab to_alloc(R11) calls #2, g^LIB$GET_VM/ movl mem_addr(R11), R9 ; R9 = buffer block movl R9, sl_xmit(R7)[R8] movl R7, sb_channel(R9) movl R8, sb_number(R9) clrb sb_active(R9) aoblss #XMIT_BUFFERS, R8, 2$< calls #0, slcompress_size ; Get size of SLCOMPRESS block movl R0, to_alloc(R11) pushab mem_addr(R11) pushab to_alloc(R11) calls #2, g^LIB$GET_VM) movl mem_addr(R11), sl_slcompress(R7) pushl mem_addr(R11)4 calls #0, sl_compress_init ; Init VJ compression$ bsbw start_slip ; may be moved# bisl #dc_m_online, dc_flags(R6) calls #0, @ACPI$OKINT(R10) ret;; Kick the protocol in the guts; R6 = device config; R7 = slip block;=start_slip: $ASSIGN_S devnam=dc_devname(R6), chan=sl_chan(R7) sts= $QIOW_S chan=sl_chan(R7), iosb=iosb, func=#IO$_SENSEMODE, -) p1=ttchars, p2=#8 ; Get current status sts movzwl iosb, R0 sts ; Set PASSALL!EIGHTBIT. bisl2 #TT$M_PASSALL!TT$M_EIGHTBIT, ttchars+4; $QIOW_S chan=sl_chan(R7), iosb=iosb, func=#IO$_SETMODE, -1 p1=ttchars, p2=#8 ; and tell terminal about it sts movzwl iosb, R0 sts clrl R81$: bsbw recv_qio aoblss #RECV_BUFFERS, R8, 1$ movb #1, sl_upflag(R7) moZZ( CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7M vb #1, sl_startflag(R7) rsb;; R7 = slip block; R8 = buffer number; R9 = buffer address;(recv_qio: LOG <"CSDRV: QIO launched"> movl sl_recv(R7)[R8], R9 movaq term_mask_ptr, R0. $QIO_S chan=sl_chan(R7), iosb=sb_iosb(R9), -7 func=#IO$_READVBLK!IO$M_NOECHO!IO$M_NOFILTR, -+ astadr=slip_recv_ast, astprm=R9, -1 p1=sb_buffer(R9), p2=#BUFFER_SIZE, p4=R0 sts movb #1, sb_active(R9) rsb ;; SLIP receive AST; astprm=buffer address;: .entry slip_recv_ast, ^M local long buffer_addr local long buffer_size local long packet_type base_register R11 LOG <"CSDRV: AST entered">5 movl ipacp_interface, R10 ; R10 = IPACP interface& movl 4(AP), R9 ; R9 = slip_buffer/ movl sb_number(R9), R8 ; R8 = buffer number/ movl sb_channel(R9), R7 ; R7 = slip_channel4 movl sl_dc_info(R7), R6 ; R6 = device info block' movl #1, @ACPI$AST_in_progress(R10)3 cmpw sb_iosb(R9), #1 ; check that result is OK bneq 98$ ; No? Discard8 cmpw sb_iosb+2(R9), #2 ; More than 1 byte in packet? blss 98$ ; No? Discard6 cmpw sb_iosb+4(R9), #SLIP_END ; Normal packet end? bneq 98$ ; No? Discard/ movl #TYPE_COMPRESSED_TCP, packet_type(R11)( movb sb_buffer(R9), R0 ; Hi bit set?' blss 97$ ; Yup, compressed packet& ; (Could be ESC, but don't care)+ bicl #^xFFFFFF0F, R0 ; Get packet type0 movl R0, packeɳ CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7MMt_type(R11) ; Save packet type2 cmpb R0, #TYPE_IP ; Unadulterated IPv4 packet beql 97$= bicb #^x30, sb_buffer(R9) ; Turn uncompressed packet back/ cmpb R0, #TYPE_UNCOMPRESSED_TCP ; into IPv4 beql 97$/98$: brw 99$ ; Wasn't a real packet after ; all? Euthenase it now.97$: LOG <"CSDRV: Acc">8 movzwl sb_iosb+2(R9), R5 ; R5 = received buffer length' addl3 #MAX_HDR, R5, buffer_size(R11)7 pushl buffer_size(R11) ; Get a buffer, allowing 128? calls #1, @ACPI$Seg_Get(R10) ; bytes for expanded TCP header movl R0, buffer_addr(R11)- addl3 #MAX_HDR, R0, R3 ; R3 = dst pointer! movl R3, R4 ; R4 = dst base' movl R5, R1 ; R1 = counter/length; movab sb_buffer(R9), R2 ; R2 = src pointer= buffer start'1$: movb (R2)+, R0 ; R0 = character# cmpb R0, #SLIP_ESC ; SLIP_ESC? bneq 2$+ decl R1 ; Come here if SLIP_ESC found- cmpb (R2)+, #SLIP_ESC_ESC ; SLIP_ESC_ESC?$ beql 2$ ; Yes? Return SLIP_ESC1 movb #SLIP_END, R0 ; No? Assume SLIP_END (!))2$: movb R0, (R3)+ ; Store unmolested sobgtr R1, 1$ ; Round again.& subl2 R4, R3 ; R3 = buffer length LOG <"CSDRV: Ins">8 movl packet_type(R11), R0 ; If TYPE_IP, don't bother2 cmpb R0, #TYPE_IP ; calling sl_uncompress_tcp# beql 9$ ; (it'll just return);2 pushl sl_slcompress(R7) ; Compression structure pushl R0 ; Packet type pushl R3 ; Packet length pushl R4 ; Pa\A CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7M=cket address calls #4, sl_uncompress_tcp tstl R0 bneq 33$+ pushl buffer_addr(R11) ; Buffer address* pushl buffer_size(R11) ; Buffer length4 calls #2, @ACPI$Seg_Free(R10) ; Deallocate Buffer LOG <"CSDRV: rdropped"> brb 99$%33$: addl R4, R3 ; Adjust length subl R0, R3% movl R0, R4 ; R4=packet address$9$: pushl R6 ; Device info block pushl R3 ; Packet length pushl R4 ; Packet address: pushl buffer_size(R11) ; Buffer length (to deallocate); pushl buffer_addr(R11) ; Buffer address (to deallocate)= calls #5, @ACPI$IP_Receive(R10) ; Give the packet to IPACP99$: LOG <"CSDRV: rdone">' bsbw recv_qio ; Resubmit this QIO# clrl @ACPI$AST_in_progress(R10)" LOG <"CSDRV: AST terminated"> ret ;$; csdrv_xmit( device_configuration );;7 .entry csdrv_xmit, ^M2 local quad mbuf ; mbuf structure for compressor ; to play with base_register R11 LOG <"CSDRV: XMIT entered">( movl 4(AP), R6 ; R6 = device config5 movl dc_dev_interface(R6), R7 ; R7 = SLIP channel5 movl ipacp_interface, R10 ; R10 = IPACP interface8 remque @dc_send_Qhead(R6), R5 ; Anything in the queue?& bvc 1$ ; R5=queue entry (maybe)# LOG <"CSDRV: nothing to xmit"> ret51$: movl sl_next_xmit(R7), R0 ; Get an xmit buffer$ movl R0, R8 ; R8 = xmit buffer decl R0 ] CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7Mbgeq 2$ movl #XMIT_BUFFERS-1, R0 2$: movl R0, sl_next_xmit(R7)2 movl sl_xmit(R7)[R8], R9 ; R9 = buffer address tstb sb_active(R9) beql 3$9 $SYNCH_S iosb=sb_iosb(R9) ; Wait for buffer to be freed sts13$: movab sb_buffer(R9), R4 ; R4 = buffer start$ movl R4, R3 ; R3 = dst pointer& movl NSQ$Data(R5), mbuf+m_off(R11)* movzwl NSQ$Datasize(R5), mbuf+m_len(R11) pushl #0 ; compress_cid2 pushl sl_slcompress(R7) ; compression structure! pushaq mbuf(R11) ; packet mbuf1 calls #3, sl_compress_tcp ; compress de packet: movl mbuf+m_off(R11), R2 ; R2 = packet start (src ptr)4 movl mbuf+m_len(R11), R1 ; R1 = length (counter)3 bisb R0, (R2) ; Overlay compression type onto ; IP version/ movb #SLIP_END, (R3)+ ; Insert leading END'4$: movb (R2)+, R0 ; R0 = character# cmpb R0, #SLIP_END ; SLIP_END? bneq 10$6 movb #SLIP_ESC_END, R0 ; Insert SLIP_ESC_END later brb 11$'10$: cmpb R0, #SLIP_ESC ; SLIP_ESC? bneq 5$6 movb #SLIP_ESC_ESC, R0 ; Insert SLIP_ESC_ESC later711$: movb #SLIP_ESC, (R3)+ ; Insert SLIP_ESC)5$: movb R0, (R3)+ ; Store unmolested sobgtr R1, 4$ ; Round again.1 movb #SLIP_END, (R3)+ ; Finally trailing END& subl2 R4, R3 ; R3 = buffer length ; R4 = buffer address bsbw xmit_qio ; $QIO67$: blbc NSQ$Delete(R5), 6$ ; If marked for delete,- pushl NSQ$Del_Buf(R5) ; delete tm CSDRV.BCKnf #[UDAA055.TEMP.CMU.CSDRV]CSDRV.MAR;7MvAhe buffer$ movzwl NSQ$Del_buf_size(R5), -(SP) calls #2, @ACPI$Seg_free(R10) LOG <"CSDRV: bfreed">#6$: pushl R5 ; Remove the entry! calls #1, @ACPI$Qblk_free(R10) LOG <"CSDRV: xdone"> ret;; Write a packet to the net.M; R7 = slip block, R9 = buffer block, R4 = buffer address, R3 = buffer length;6xmit_qio: $QIO_S chan=sl_chan(R7), iosb=sb_iosb(R9), -; func=#IO$_WRITEVBLK!IO$M_CANCTRLO!IO$M_BREAKTHRU,-) p1=(R4), p2=R3 ; QIO the packet sts movb #1, sb_active(R9) LOG <"CSDRV: packet QIOed"> rsb .end$*[UDAA055.TEMP.CMU.CSDRV]CSDRV.OBJ;84+,r ./@ 4*-nf 0123KPWO56"h7\h89G@HJ 4M #h kN:ALU23.IS\2pG=vq-QbW$mL Y]]XV1ltlY+xcB+}G0oy1lp 0;$vzh_@r|HuJ.tmrE~~wd/o1TV |f1/h+FEtyr)O;2QA;zPC5 u;o"4WW ^ !(9&9I]gk_ `2{!;j0QfzN =jtuӽʹ7טL W2mbU8aL}x-05(7I =!oQ%YQ[WCNu;@JJ7J7+?{SYn:& rrmum~t3 >k zP <szaW!==YzDQus@3\};[G[]Q|D%y_rM<{ !(g/4?o(FV31FXk\(8tWFPb'-1-SEhI`FL=rjo=IY19 ;CG,S(Z vx?>l\7O4~L87roW A03q5iT@~_~^2gUR5"lW>,M;~*  *<1i.Yb/1?{Q E]Q t3BIz*XdhZ iK h(#ZEG5wlz{EXhWut#\Y)tb6 r'M9AQy*&`Rl Uf`TD>>t5V"YNyBeL)p rkyc<[5E!,&dZFFi$fR,47NtMZT1g?X:aDmky(~3"BV >g1uNvF#JBOKq] fshMN@J?y3@o.y)?URv9* ]FY;Mse~:SDfP]J1|ze L'_KDMu\}LrqJ8q\"H1.\hD8Z&khG9ar muICM0DA.]LO>DNgou#2|DH jyo=)7,{r6+rkVHMOW$RjA $e/?3[F n*NtS+B=da 1ji/&7yN"7MB;6po]S8*`r" %q1 )[ D: A, CSDRV.BCKr nf $[UDAA055.TEMP.CMU.CSDRV]CSDRV.OBJ;84I/CSDRV024-APR-1995 01:12 VAX MACRO T5.2V-4 MAC CSDRV(Compressed SLIP IPACP transport driver CSDRVVIO$M_BREAKTHRU IO$M_CANCTRLO IO$M_NOECHO IO$M_NOFILTR IO$_READVBLK IO$_SENSEMODE IO$_SETMODE IO$_WRITEVBLK LIB$GET_VM LIB$SIGNALSLCOMPRESS_SIZESL_COMPRESS_INITSL_COMPRESS_TCPSL_UNCOMPRESS_TCP SYS$ASSIGNSYS$QIOSYS$QIOW SYS$SYNCH TT$M_EIGHTBIT TT$M_PASSALL . ABS .P $TRANSFER$HPADRV$TRANSPORT_INIT DRV$TRANSPORT_INIT&DRV$TRANSPORT_INIT3XCSDRV_RW`PQQ  D3Q&QQQCSDRV_REP DRV$TRANSPORT_INIT&X=3 373 33P 7 CSDRV_NULL& P = CSDRV_INIT& ^^[ЬVЬZZ Џ@kk LIB$GET_VMЫWW67ԧ0V8XЏ kk LIB$GET_VMЫYYHWXiXXЏ kk LIB$GET_VMЫYYHgWXiXSLCOMPRESS_SIZEPkk LIB$GET_VMЫ<ݫSL_COMPRESS_INIT0 8|~4f SYS$ASSIGNP P LIB$SIGNAL|~|~H|~P< IO$_SENSEMODE&~<4~ SYS$QIOWP P LIB$SIGNAL<PPP P LIB$SIGNAL TT$M_PASSALL TT$M_EIGHTBIT"8H3|~|~H|~P< IO$_SETMODE&~<4~ SYS$QIOWP P LIB$SIGNALQ CSDRV.BCKr nf $[UDAA055.TEMP.CMU.CSDRV]CSDRV.OBJ;84x <PPP P LIB$SIGNALX0 X67HY~P|~Pݏ Y< IO$_READVBLK IO$M_NOECHO8 IO$M_NOFILTR8&~<4~ SYS$QIOP P LIB$SIGNAL  SLIP_RECV_AST&  ^^[ZЬYiXЩWЧ8V7 1 )ЏPʏPPP@ 0Pp1< UUݫPkPSSTUQRPБP QPPQTSЫPP@(ݧ$! subroutine to check if installation is possible and desired$ init:7$ files="CSDRV.OBJ,LINK_CSDRV.COM,NTOH.OBJ,RFC1144.OBJ"$ i = 0"$ 1: file = f$element(i,",",files)$ if file .nes. ","7$ then if f$parse(file) .eqs. "" then goto cant_install4$ if f$search(file) .eqs. "" then goto cant_install $ i = i + 1 $ goto 1$ endif$ type SYS$INPUT:HThis procedure will install the CSDRV files on your system. You should 7view this file carefully b!  CSDRV.BCK nf +[UDAA055.TEMP.CMU.CSDRV]INSTALL_CSDRV.COM;6Kefore attempting to run it. +The procedure performs the following steps: 1. Link the CSDRV image* 2. Place the image in CMUIP_ROOT:[syslib]FIf you you wish to change or omit any of these steps, or are unsure ofJthe actions being taken, answer NO to the question below and view or edit this file accordingly.HNote that this procedure does not compile from source. Use the command Gfile COMPILE_CSDRV to do this. Note that the CMUIP source kit must be !installed to compile from source.K$ read SYS$COMMAND confirmed/error=abort/prompt="Do you wish to continue? "$ if confirmed then return $abort: exit$ cant_install:?$ write SYS$OUTPUT "The file ", file, " could not be accessed."$ type SYS$INPUT:;The installation can not continue. Please ensure that you:6 - are in the same directory as the installation files - have sufficient privilege! - that CMU-OpenVMS IP is runningand restart the procedure.$ exit(*[UDAA055.TEMP.CMU.CSDRV]LINK_CSDRV.COM;4+,E./@ 48T-nf 0123KPWO56`]-7@+-89G@HJ CSDRV.BCKEnf ([UDAA055.TEMP.CMU.CSDRV]LINK_CSDRV.COM;489r8$ link/debug/share CSDRV,RFC1144,NTOH,SYS$INPUT:/optionsSYS$SHARE:VAXCRTL/share *[UDAA055.TEMP.CMU.CSDRV]NTOH.C;1+,./@ 4A-nf 0123KPWO56@UÖ7`>89G@HJ@/* ntoh.c Convert between host & network byte orders. 9/5/93/dcs *A * Bloody hell. Why couldn't this stuff have been developed on a * reasonable architecture? */#include ntohl(n) { u_long tmp;- ((u_char *)(&tmp))[0] = ((u_char *)(&n))[3];- ((u_char *)(&tmp))[1] = ((u_char *)(&n))[2];- ((u_char *)(&tmp))[2] = ((u_char *)(&n))[1];- ((u_char *)(&tmp))[3] = ((u_char *)(&n))[0]; return tmp;} htonl(n) { u_long tmp;- ((u_char *)(&tmp))[0] = ((u_char *)(&n))[3];-g CSDRV.BCKnf  [UDAA055.TEMP.CMU.CSDRV]NTOH.C;1AsT ((u_char *)(&tmp))[1] = ((u_char *)(&n))[2];- ((u_char *)(&tmp))[2] = ((u_char *)(&n))[1];- ((u_char *)(&tmp))[3] = ((u_char *)(&n))[0]; return tmp;} ntohs(n) { u_short tmp;- ((u_char *)(&tmp))[0] = ((u_char *)(&n))[1];- ((u_char *)(&tmp))[1] = ((u_char *)(&n))[0]; return tmp;} htons(n) { u_short tmp;- ((u_char *)(&tmp))[0] = ((u_char *)(&n))[1];- ((u_char *)(&tmp))[1] = ((u_char *)(&n))[0]; return tmp;}"*[UDAA055.TEMP.CMU.CSDRV]NTOH.OBJ;4+,a<./@ 4@-nf 0123KPWO56OJh7rh89G@HJ1NTOHV1.024-APR-1995 01:11GNU CC V2.3.3Sd$CODE NTOHL HTONL <NTOHS PHTONSPP^ЭPP^ЭP<P^ protocol does so little, though, it is usually very easy to implement.E Around 1984, Rick Adams implemented SLIP for 4.2 Berkeley Unix andB Sun Microsystems workstations and released it to the world. ItH quickly caught on as an easy reliable way to connect TCP/IP hosts and routers with serial lines.D SLIP is commonly used on dedicated serial links andcԀ CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1JY sometimes forH dialup purposes, and is usually used with line speeds between 1200bpsF and 19.2Kbps. It is useful for allowing mixes of hosts and routersF to communicate with one another (host-host, host-router and router-6 router are all common SLIP network configurations). AVAILABILITYA SLIP is available for most Berkeley UNIX-based systems. It isB included in the standard 4.3BSD release from Berkeley. SLIP isF available for Ultrix, Sun UNIX and most other Berkeley-derived UNIXH systems. Some terminal concentrators and IBM PC implementations also support it.= SLIP for Berkeley UNIX is available via anonymous FTP fromB uunet.uu.net in pub/sl.shar.Z. Be sure to transfer the file inH binary mode and then run it through the UNIX uncompress program. TakeHRomkey [Page 1] HRFC 1055 Serial Line IP June 1988G the resulting file and use it as a shell script for the UNIX /bin/sh# (for instance, /bin/sh sl.shar).PROTOCOLH The SLIP protocol defines two special characters: END and ESC. END isG octal 300 (decimal 192) and ESC is octal 333 (decimal 219) not to beE confused with the ASCII ESCape character; for the purposes of thisC discussion, ESC will indicate the SLIP ESC character. To send aH packet, a SLIP host simply starts sending the data in the packet. IfH a data byte is the same code as END character, a two byte sequence 콁 CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1JofF ESC and octal 334 (decimal 220) is sent instead. If it the same asG an ESC character, an two byte sequence of ESC and octal 335 (decimalC 221) is sent instead. When the last byte in the packet has been. sent, an END character is then transmitted.C Phil Karn suggests a simple change to the algorithm, which is toG begin as well as end packets with an END character. This will flushD any erroneous bytes which have been caused by line noise. In theA normal case, the receiver will simply see two back-to-back END@ characters, which will generate a bad IP packet. If the SLIPG implementation does not throw away the zero-length IP packet, the IPD implementation certainly will. If there was line noise, the dataG received due to it will be discarded without affecting the following packet.F Because there is no 'standard' SLIP specification, there is no realG defined maximum packet size for SLIP. It is probably best to acceptG the maximum packet size used by the Berkeley UNIX SLIP drivers: 1006G bytes including the IP and transport protocol headers (not includingC the framing characters). Therefore any new SLIP implementationsG should be prepared to accept 1006 byte datagrams and should not send& more than 1006 bytes in a datagram. DEFICIENCIESH There are several features that many users would like SLIP to provideA which it doesn't. In all fairness, SLIP is just a very simpleG protocol designed quite a long time ago when  mA CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1Jo these problems were notA really important issues. The following are commonly perceived. shortcomings in the existing SLIP protocol: - addressing:C both computers in a SLIP link need to know each other's IPC addresses for routing purposes. Also, when using SLIP forF hosts to dial-up a router, the addressing scheme may be quiteF dynamic and the router may need to inform the dialing host ofHRomkey [Page 2] HRFC 1055 Serial Line IP June 1988E the host's IP address. SLIP currently provides no mechanismD for hosts to communicate addressing information over a SLIP connection. - type identification:D SLIP has no type field. Thus, only one protocol can be runA over a SLIP connection, so in a configuration of two DECF computers running both TCP/IP and DECnet, there is no hope ofD having TCP/IP and DECnet share one serial line between themG while using SLIP. While SLIP is "Serial Line IP", if a serialD line connects two multi-protocol computers, those computersD should be able to use more than one protocol over the line.# - error detection/correction:G noisy phone lines will corrupt packets in transit. Because the= line speed is probably quite low (likely 2400 baud),G retransmitting a packet is very expensive!zA [qhuRV.COM;4yiu 56H qLL^BhP sxgqf 9SbOyq4y{So?L= JyV;R-?r9Q&fr@J@Գg;p|ODC[7{QIy4L`K1Z1:U_VT |YCleF, 4lYoM(U;|k6qM,v,R.oX@Gk= {3 sq\jV^윭Ӊm`mMv)&3(`q'ni4N,< 1yrk6 s5u+m?8a< 0:96OA!_ySf_y0.CL2 @z)m:i4:+s5 2S;%Џt2d5 դg$)Y INuM;cX3G䎀 aސ$Kʒ\P0|'[GNlKՉF}iw7 oeHQ 4!~nM. 4N#=Rn࢒eG3v.h~. ?yLDk*$ {1 e",wRevPdng 7zbVgukV$7lQ/OUCO+c U]1f~ N33C-V:BnUHtVHzC+5v+BUsbZCA$ _`>qUXlXQ |vz,DLYB@ TOt_t4N'(mGes>c.nXYH^:7 (!maf]:UiSLr )"wZf`1u:*^&? D! jrK?%rR8]HRG-N9G@HJ"I-y CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1J . Error detection isB not absolutely necessary at the SLIP level because any IPE application should detect damaged packets (IP header and UDP@ and TCP checksums should suffice), although some commonH applications like NFS usually ignore the checksum and depend onG the network media to detect damaged packets. Because it takesC so long to retransmit a packet which was corrupted by lineH noise, it would be efficient if SLIP could provide some sort of6 simple error correction mechanism of its own. - compression:D because dial-in lines are so slow (usually 2400bps), packet= compression would cause large improvements in packet@ throughput. Usually, streams of packets in a single TCPF connection have few changed fields in the IP and TCP headers,G so a simple compression algorithms might just send the changed> parts of the headers instead of the complete headers.F Some work is being done by various groups to design and implement aF successor to SLIP which will address some or all of these problems.HRomkey [Page 3] HRFC 1055 Serial Line IP June 1988 SLIP DRIVERSD The following C language functions send and receive SLIP packets.H They depend on two functions, send_char() and recv_char(), which send7 and receive a single character ov#pG CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1Jer the serial line." /* SLIP special character codes */@ #define END 0300 /* indicates end of packet */@ #define ESC 0333 /* indicates byte stuffing */H #define ESC_END 0334 /* ESC ESC_END means END data byte */H #define ESC_ESC 0335 /* ESC ESC_ESC means ESC data byte */> /* SEND_PACKET: sends a packet of length "len", starting at * location "p". */ void send_packet(p, len) char *p; int len; {D /* send an initial END character to flush out any data that may: * have accumulated in the receiver due to line noise */ send_char(END);C /* for each byte in the packet, send the appropriate character * sequence */ while(len--) { switch(*p) {J /* if it's the same code as an END character, we send aF * special two character code so as not to make the3 * receiver think we sent an END */ case END:* send_char(ESC);. send_char(ESC_END);! break;@ /* if it's the same code as an ESC character,D * we send a special two character code so as not? * to make the receiver think we sent an ESC */ case ESC:* send_char(ESC);.$- CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1JЉ send_char(ESC_ESC);! break;HRomkey [Page 4] HRFC 1055 Serial Line IP June 1988; /* otherwise, we just send the character */ default:) send_char(*p); } p++; }B /* tell the receiver that we're done sending the packet */ send_char(END); }D /* RECV_PACKET: receives a packet into the buffer located at "p".? * If more than len bytes are received, the packet will * be truncated.< * Returns the number of bytes stored in the buffer. */ int recv_packet(p, len) char *p; int len; { char c; int received = 0;? /* sit in a loop reading bytes until we put together * a whole packet.> * Make sure not to copy them into the packet if we * run out of room. */ while(1) {0 /* get a character to process */# c = recv_char();6 /* handle bytestuffing if necessary */ switch(c) {C /* if it's an END character then we're done with * the pa%v  CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1JMcket */ case END:B /* a minor optimization: if there is noD * data in the packet, ignore it. This isB * meant to avoid bothering IP with all@ * the empty packets generated by theC * duplicate END characters which are inHRomkey [Page 5] HRFC 1055 Serial Line IP June 1988D * turn sent to try to detect line noise. */' if(received)3 return received; else) break;E /* if it's the same code as an ESC character, waitC * and get another character and then figure out@ * what to store in the packet based on that. */ case ESC:+ c = recv_char();E /* if "c" is not one of these two, then weF * have a protocol violation. The best betE * seems to be to leave the byte alone and; * just stuff it into the packet */& switch(c) {( case ES&l} CSDRV.BCK2nf %[UDAA055.TEMP.CMU.CSDRV]RFC1055.TXT;1JC_END:+ c = END;) break;( case ESC_ESC:+ c = ESC;) break;$ }C /* here we fall into the default handler and let3 * it store the character for us */ default:- if(received < len)5 p[received++] = c; } } }HRomkey [Page 6] $*[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14+, .1/@ 4P1.l-nf 0123KPWO256.7(.89G@HJ' CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P186/* rfc1144.c Van Jacobson TCP compression 8/5/93/dcs *G * Gratuitously cribbed from Jacobson 1990, "Compressing TCP/IP Headers* * for Low-Speed Serial Links (RFC 1144)." *< * For issues about compression contact the original author: * Van Jacobson * Real Time Systems Group * Mail Stop 46A * Lawrence Berkeley Laboratory * Berkeley, CA 94720/ * Phone: Use email (author ignores his phone) * EMail: van@helios.ee.lbl.govC * (this is the address given in the RFC -- it may be out of date.) *//* A Sample Implementation *H * The following is a sample implementation of the protocol described in * this document. *H * Since many people who might have the deal with this code are familiarK * with the Berkeley Unix kernel and its coding style (affectionately knownI * as kernel normal form), this code was done in that style. It uses theC * Berkeley `subroutines' (actually, macros and/or inline assembler< * expansions) for converting to/from network byte order andB * copying/comparing strings of bytes. These routines are briefly; * described in sec. A.5 for anyone not familiar with them. *I * This code has been run on all the machines listed in the table on pageC * 24. Thus, the author hopes there are no byte order or alignmentI * problems (although there are embedded assumptions about alignment that? * are valid for Berkeley Unix but may not be true for other IP? * implementations --- see the comments mentioning alignment in* * sl_compress_tcp and(GXp CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1 ) sl_decompress_tcp). *K * There was some attempt to make this code efficient. Unfortunately, thatH * may have made portions of it incomprehensible. The author apologizesK * for any frustration this engenders. (In honesty, my C style is known toI * be obscure and claims of `efficiency' are simply a convenient excuse.) *B * This sample code and a complete Berkeley Unix implementation isJ * available in machine readable form via anonymous ftp from Internet hostH * ftp.ee.lbl.gov (128.3.254.68), file cslip.tar.Z. This is a compressed3 * Unix tar file. It must be ftped in binary mode. *J * All of the code in this appendix is covered by the following copyright: * */ /*> * Copyright (c) 1989 Regents of the University of California. * All rights reserved. *8 * Redistribution and use in source and binary forms are> * permitted provided that the above copyright notice and this: * paragraph are duplicated in all such forms and that any< * documentation, advertising materials, and other materials< * related to such distribution and use acknowledge that the: * software was developed by the University of California,; * Berkeley. The name of the University may not be used to9 * endorse or promote products derived from this software- * without specific prior written permission.> * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS< * OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE: * IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A * PARTICULAR PU)|Y CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1RPOSE. */ "/* A.1 Definitions and State Data */+#include "cmuip-vms.h" /* 8/5/93/dcs */1#define MAX_STATES 16 /* must be >2 and <255 */E#define MAX_HDR 128 /* max TCP+IP hdr length (by protocol def) *//* packet types */#define TYPE_IP 0x40"#define TYPE_UNCOMPRESSED_TCP 0x70 #define TYPE_COMPRESSED_TCP 0x80B#define TYPE_ERROR 0x00 /* this is not a type that ever appears on. * the wire. The receive framer uses it to. * tell the decompressor there was a packet * transmission error. *//*+ * Bits in first octet of compressed packet */,/* flag bits for what changed in a packet */#define NEW_C 0x40#define NEW_I 0x20#define TCP_PUSH_BIT 0x10#define NEW_S 0x08#define NEW_A 0x04#define NEW_W 0x02#define NEW_U 0x01,/* reserved, special-case values of above */M#define SPECIAL_I (NEW_S|NEW_W|NEW_U) /* echoed interactive traffic */F#define SPECIAL_D (NEW_S|NEW_A|NEW_W|NEW_U) /* unidirectional data *//#define SPECIALS_MASK (NEW_S|NEW_A|NEW_W|NEW_U)/*F * "state" data for each active tcp conversation on the wire. This isM * basically a copy of the entire IP/TCP header from the last packet togetherI * with a small identifier the transmit & receive ends of the line use to * locate saved header. */struct cstate {I struct cstate *cs_next; /* next most recently used cstate (xmit only)*/: u_short cs_hlen; /* size of hdr (receive only) */G u_char cs_id; /* connection # associated w*]5- CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P10Z ith this state */ u_char cs_filler; union { char hdr[MAX_HDR];> struct ip csu_ip; /* ip/tcp hdr from most recent packet */ } slcs_u;};#define cs_ip slcs_u.csu_ip#define cs_hdr slcs_u.csu_hdr/*J * all the state data for one serial line (we need one of these per line). */struct slcompress {C struct cstate *last_cs; /* most recently used tstate */< u_char last_recv; /* last rcvd conn. id */< u_char last_xmit; /* last sent conn. id */ u_short flags;@ struct cstate tstate[MAX_STATES]; /* xmit connection states */C struct cstate rstate[MAX_STATES]; /* receive connection states */};int /* 16/5/93/dcs */Pslcompress_size() { return sizeof(struct slcompress); } /* Make size available*/ /* to caller *//* flag values */G#define SLF_TOSS 1 /* tossing rcvd frames because of input err *//*H * The following macros are used to encode and decode numbers. They allL * assume that `cp' points to a buffer where the next byte encoded (decoded)I * is to be stored (retrieved). Since the decode routines do arithmetic,7 * they have to convert from and to network byte order. *//*L * ENCODE encodes a number that is known to be non-zero. ENCODEZ checks for: * zero (zero has to be encoded in the long, 3 byte form). */#define ENCODE(n) { \ if ((u_short)(n) >= 256) { \ *cp++ = 0; \ cp[1] = (n); \ cp[0] = (n) >> 8; \ cp += 2; \ } else { \ *cp++ = (n); \ } \}#define +& CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1 ENCODEZ(n) { \2 if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \ *cp++ = 0; \ cp[1] = (n); \ cp[0] = (n) >> 8; \ cp += 2; \ } else { \ *cp++ = (n); \ } \}/*F * DECODEL takes the (compressed) change at byte cp and adds it to theK * current value of packet field 'f' (which must be a 4-byte (long) integerM * in network byte order). DECODES does the same for a 2-byte (short) field.I * DECODEU takes the change at cp and stuffs it into the (short) field f.G * 'cp' is updated to point to the next field in the compressed header. */#define DECODEL(f) { \ if (*cp == 0) {\3 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \ cp += 3; \ } else { \* (f) = htonl(ntohl(f) + (u_long)*cp++); \ } \}#define DECODES(f) { \ if (*cp == 0) {\3 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \ cp += 3; \ } else { \* (f) = htons(ntohs(f) + (u_long)*cp++); \ } \}#define DECODEU(f) { \ if (*cp == 0) {\& (f) = htons((cp[1] << 8) | cp[2]); \ cp += 3; \ } else { \ (f) = htons((u_long)*cp++); \ } \} /* A.2 Compression *K * This routine looks daunting but isn't really. The code splits into fourC * approximately equal sized sections: The first quarter manages a> * circularly linked, least-recently-used list of `active' TCPG * connections./47/ The second figures out the sequence/ack/window/urgK * changes and builds the bulk of the compressed packet. The third handlesC * the special-case encodings. The last quarter d,i~ce1-f#_'bYQVW~ J}( \q >4-wY tf>5yECV0OO {WX9xKZ:},Sxcv;Kq"T5!s]S1:nz rR/B_3{M1O3&36UX{(TOT_)HHP.%VD`J f$} 2Br9 ! wQE+NDs}ws&u`("S/Qenk4v@/k#1oT`iS!^/HY]E0 e^RA}cHHX4oU#nr[DL_LI2lG7rbY?x.N[8esC;lrRG:AsB_r. kONB7rQ x$IWM}wl%5;' 3<*fM8{F{@r/F?T~ eeufncF{x)OomL*X.Wxh-l9U;t Y;D<Xt GY#{3(B(1|A(jgP@u"E@a%3bB y(` POO_vq}-b#}5Bg"QFiw#28&x KG]x7$/a ut`u0/4kMQqv~vd*rbZO92=Ev1[=FuL}2`>m3'#?i]%0r{ayS al]YY55kOp&bA:7}p 'XHdA|\~/.WL%3`~BX_Q R&"J_1n7jx*"ZZKF:U XCU8p bFy$LGZJtF:;(oKG{/xZ&_CK#%9/Uio]4qDnZX7R5rj;5 O t*q ojbH]|s=A tgw $0r=)ap;!]=L>'fUNJ*STKb*N\kn0s95|:}nEy}XaYET\F5 a@W;G4-MA6F0[L! b_VKk~{8g ViM*pnil6d.`Vy H*R #N_ ~4.dmvyI5*J\Yjs]V!+kCSfe4VB{7VQryyqU?'b9mt4g{yr18l88h93zJvF9GA>-VO 7IT:{;P}o3^vlSfm.uKW/nTM^+4*4~+C(cTH% 3"[yO'#Rjb 1H)m+>@J5{sOlXK:tcW,| 78\uI<9\U=if$,mC/~ts9&{+^'aX]N3AO%.-Eh&{>TCo gt|6rfnA~rRW|T6 'Z݉{'0FrKѷ1=8Qeb^xn74z:!>p* ;B) c Ry("y!Q9n1%+X^`V(lUAI%y2k`dzhIWxGEYgY .nM&|W#"p~G-o]tZ l}}b3%vHA{zNU*d!. zNxTk~y`W YS00dG8)L|,L%EvNMUcAQ0R4P#9SG\yd={rc5VY}X?Bx1#/'\R/EIK%!ezjeY{} -8lN={\[;kCK_HOIP9i 12'qvNdy\(ve8T&F"4 &U~a>W J%{,cNCJ "'f(>4W#]RL AARO-y CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1Voes packet ID andJ * connection ID encoding and replaces the original packet header with the * compressed header. *@ * The arguments to this routine are a pointer to a packet to beK * compressed, a pointer to the compression state data for the serial line,J * and a flag which enables or disables connection id (C bit) compression. *H * Compression is done `in-place' so, if a compressed packet is created,H * both the start address and length of the incoming packet (the off andJ * len fields of m) will be updated to reflect the removal of the originalD * header and its replacement by the compressed header. If either aI * compressed or uncompressed packet is created, the compression state isJ * updated. This routines returns the packet type for the transmit framer; * (TYPE_IP, TYPE_UNCOMPRESSED_TCP or TYPE_COMPRESSED_TCP). *I * Because 16 and 32 bit arithmetic is done on various header fields, theJ * incoming IP packet must be aligned appropriately (e.g., on a SPARC, theI * IP header is aligned on a 32-bit boundary). Substantial changes wouldH * have to be made to the code below if this were not true (and it wouldD * probably be cheaper to byte copy the incoming header to somewhere1 * correctly aligned than to make those changes). *F * Note that the outgoing packet will be aligned arbitrarily (e.g., it/ * could easily start on an odd-byte boundary). * * ----------------------------J * 47. The two most common operations on the connection list are a `find'I * that term.| CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1Binates at the first entry (a new packet for the most recentlyH * used connection) and moving the last entry on the list to the head ofF * the list (the first packet from a new connection). A circular list, * efficiently handles these two operations. */u_char&sl_compress_tcp(m, comp, compress_cid) struct mbuf *m; struct slcompress *comp; int compress_cid;{5 register struct cstate *cs = comp->last_cs->cs_next;/ register struct ip *ip = mtod(m, struct ip *);! register u_int hlen = ip->ip_hl;9 register struct tcphdr *oth; /* last TCP header */< register struct tcphdr *th; /* current TCP header */E register u_int deltaS, deltaA; /* general purpose temporaries */5 register u_int changes = 0; /* change mask */F u_char new_seq[16]; /* changes from last to current */ register u_char *cp = new_seq; /*= * Bail if this is an IP fragment or if the TCP packet isn'tD * `compressible' (i.e., ACK isn't set or some other control bit isF * set). (We assume that the caller has already made sure the packet * is IP proto TCP). */5 if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40 ||1 ip->ip_p != IPPROTO_TCP) /* 18/5/93/dcs */ return (TYPE_IP);- th = (struct tcphdr *) & ((int *) ip)[hlen];D if ((th->th_flags & (TH_SYN | TH_FIN | TH_RST | TH_ACK)) != TH_ACK) return (TYPE_IP); /*: * Packet is compressible -- we're going to send either aE * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way we need toC/Y CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1% * locate (or create) the connection state. Special case the mostF * recently used connection since it's most likely to be used again &4 * we don't have to do any reordering if it's used. */4 if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||4 ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||< *(int *) th != ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl]) { /*' * Wasn't the first -- search for it. *= * States are kept in a circularly linked list with last_cs> * pointing to the end of the list. The list is kept in lru= * order by moving a state to the head of the list whenever4 * it is referenced. Since the list is short and,> * empirically, the connection we want is almost always near: * the front, we locate states via linear search. If we= * don't find a state for the datagram, the oldest state is * (re-)used. */ register struct cstate *lcs;1 register struct cstate *lastcs = comp->last_cs; do { lcs = cs; cs = cs->cs_next;3 if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr6 && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr? && *(int *) th == ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl]) goto found; } while (cs != lastcs); /*5 * Didn't find it -- re-use oldest cstate. Send an7 * uncompressed packet that tells the other side what> * connection number we're using for this conversation. Note< * that since the state list is circular, the oldest state< * points to the newest and we only need to se0l CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1#t last_cs to * update the lru linkage. */ comp->last_cs = lcs; hlen += th->th_off; hlen <<= 2; goto uncompressed;found:= /* Found it -- move to the front on the connection list. */ if (lastcs == cs) comp->last_cs = lcs; else { lcs->cs_next = cs->cs_next;! cs->cs_next = lastcs->cs_next; lastcs->cs_next = cs; } } /*C * Make sure that only what we expect to change changed. The firstD * line of the `if' checks the IP protocol version, header length &C * type of service. The 2nd line checks the "Don't fragment" bit.C * The 3rd line checks the time-to-live and protocol (the protocolD * check is unnecessary but costless). The 4th line checks the TCPD * header length. The 5th line checks IP options, if any. The 6th@ * line checks TCP options, if any. If any of these things areB * different between the previous & current datagram, we send the$ * current datagram `uncompressed'. */6 oth = (struct tcphdr *) & ((int *) &cs->cs_ip)[hlen]; deltaS = hlen; hlen += th->th_off; hlen <<= 2;: if (((u_short *) ip)[0] != ((u_short *) &cs->cs_ip)[0] ||: ((u_short *) ip)[3] != ((u_short *) &cs->cs_ip)[3] ||: ((u_short *) ip)[4] != ((u_short *) &cs->cs_ip)[4] ||! th->th_off != oth->th_off ||G (deltaS > 5 && BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||F (th->th_off > 5 && BCMP(th + 1, oth + 1, (th->th_off - 5) << 2))) goto uncompressed; /*B * Figure out which of the changing fields changed. 1 ! CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1eThe receiver; * expects changes in the order: urgent, window, ack, seq. */ if (th->th_flags & TH_URG) { deltaS = ntohs(th->th_urp); ENCODEZ(deltaS); changes |= NEW_U;& } else if (th->th_urp != oth->th_urp) /*4 * argh! URG not set but urp changed -- a sensible; * implementation should never do this but RFC793 doesn't4 * prohibit the change so we have to deal with it. */ goto uncompressed;C if (deltaS = (u_short) (ntohs(th->th_win) - ntohs(oth->th_win))) { ENCODE(deltaS); changes |= NEW_W; }7 if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) { if (deltaA > 0xffff) goto uncompressed; ENCODE(deltaA); changes |= NEW_A; }7 if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) { if (deltaS > 0xffff) goto uncompressed; ENCODE(deltaS); changes |= NEW_S; } /*( * Look for the special-case encodings. */ switch (changes) { case 0: /*? * Nothing changed. If this packet contains data and the last< * one didn't, this is probably a data packet following an= * ack (normal on an interactive connection) and we send it7 * compressed. Otherwise it's probably a retransmit,= * retransmitted ack or window probe. Send it uncompressed: * in case the other side missed the compressed version. */' if (ip->ip_len != cs->cs_ip.ip_len &&& ntohs(cs->cs_ip.ip_len) == hlen) break; /* (fall through) */ case SPECIAL_I: case SPECIAL_D: /*> * Actual changes match one of our spe2w  CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1cial case encodings -- * send packet uncompressed. */ goto uncompressed; case NEW_S | NEW_A: if (deltaS == deltaA &&1 deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {1 /* special case for echoed terminal traffic */ changes = SPECIAL_I; cp = new_seq; } break; case NEW_S:1 if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {# /* special case for data xfer */ changes = SPECIAL_D; cp = new_seq; } break; }4 deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id); if (deltaS != 1) { ENCODEZ(deltaS); changes |= NEW_I; } if (th->th_flags & TH_PUSH) changes |= TCP_PUSH_BIT; /*A * Grab the cksum before we overwrite it below. Then update our$ * state with this packet's header. */ deltaA = ntohs(th->th_sum); BCOPY(ip, &cs->cs_ip, hlen); /*F * We want to use the original packet as our compressed packet. (cp -C * new_seq) is the number of bytes we need for compressed sequenceC * numbers. In addition we need one byte for the change mask, oneoA * for the connection id and two for the tcp checksum. So, (cp -cD * new_seq) + 4 bytes of header are needed. hlen is how many bytesE * of the original packet to toss so subtract the two to get the newl * packet size. */ deltaS = cp - new_seq;  cp = (u_char *) ip;9 if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {7 comp->last_xmit = cs->cs_id; hlen -= deltaS + 4;* cp += hlen;l *cp++ = changes | NEW_C; *cp++ = cs->cs_id; } else {t hlen -3&Z(l CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1"= deltaS + 3; cp += hlen;a *cp++ = changes; } m->m_len -= hlen; m->m_off += hlen; *cp++ = deltaA >> 8;e *cp++ = deltaA; BCOPY(new_seq, cp, deltaS); return (TYPE_COMPRESSED_TCP); uncompressed:r /*i9 * Update connection state cs & send uncompressed packet > * ('uncompressed' means a regular ip/tcp packet but with theD * 'conversation id' we hope to use on future compressed packets in * the protocol field). */ BCOPY(ip, &cs->cs_ip, hlen);n ip->ip_p = cs->cs_id; comp->last_xmit = cs->cs_id;s return (TYPE_UNCOMPRESSED_TCP);}b /* A.3 Decompressionf *D * This routine decompresses a received packet. It is called with aJ * pointer to the packet, the packet length and type, and a pointer to theJ * compression state structure for the incoming serial line. It returns aF * pointer to the resulting packet or zero if there were errors in theI * incoming packet. If the packet is COMPRESSED_TCP or UNCOMPRESSED_TCP,o) * the compression state will be updated.s * oK * The new packet will be constructed in-place. That means that there mustoD * be 128 bytes of free space in front of bufp to allow room for theF * reconstructed IP and TCP headers. The reconstructed packet will be * aligned on a 32-bit boundary. */r nu_char *(sl_uncompress_tcp(bufp, len, type, comp) u_char *bufp; int len;c u_int type; struct slcompress *comp;t{o register u_char *cp;a register u_int hlen, changes; register struct tcphdr *th; register struct cstate *c4JB CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1Q%s; register struct ip *ip; switch (type) { case TYPE_ERROR:b default:b goto bad; case TYPE_IP: return (bufp); case TYPE_UNCOMPRESSED_TCP: /*> * Locate the saved state for this connection. If the state. * index is legal, clear the 'discard' flag. */R ip = (struct ip *) bufp; if (ip->ip_p >= MAX_STATES)r goto bad;1 cs = &comp->rstate[comp->last_recv = ip->ip_p];a comp->flags &= ~SLF_TOSS;  /*; * Restore the IP protocol field then save a copy of thish> * packet header. (The checksum is zeroed in the copy so we< * don't have to zero it each time we process a compressed * packet. */. ip->ip_p = IPPROTO_TCP;y hlen = ip->ip_hl;; hlen += ((struct tcphdr *) & ((int *) ip)[hlen])->th_off;* hlen <<= 2;i BCOPY(ip, &cs->cs_ip, hlen); cs->cs_ip.ip_sum = 0;D cs->cs_hlen = hlen;A return (bufp); case TYPE_COMPRESSED_TCP: break; }% /* We've got a compressed packet. */R cp = bufp;A changes = *cp++;* if (changes & NEW_C) { /*9 * Make sure the state index is in range, then grab the-> * state. If we have a good state index, clear the 'discard' * flag. */ if (*cp >= MAX_STATES) goto bad; comp->flags &= ~SLF_TOSS; comp->last_recv = *cp++; } else {x /*= * This packet has an implicit state index. If we've had ax< * line error since the last time we got an explicit state' * index, we have to toss the packet.a */s if (comp->flags & SLF_TOSS)s return ((u_char *) 5ubC CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1̃(0);  } /*s> * Find the state then fill in the TCP checksum and PUSH bit. */% cs = &comp->rstate[comp->last_recv];p hlen = cs->cs_ip.ip_hl << 2;8 th = (struct tcphdr *) & ((u_char *) &cs->cs_ip)[hlen];( th->th_sum = htons((*cp << 8) | cp[1]); cp += 2;  if (changes & TCP_PUSH_BIT) th->th_flags |= TH_PUSH; elseo th->th_flags &= ~TH_PUSH;  /*N@ * Fix up the state's ack, seq, urg and win fields based on the * changemask.A */# switch (changes & SPECIALS_MASK) {d case SPECIAL_I: {W; register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;v, th->th_ack = htonl(ntohl(th->th_ack) + i);, th->th_seq = htonl(ntohl(th->th_seq) + i); }e break; case SPECIAL_D:@ th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len) - cs->cs_hlen); break; default:t if (changes & NEW_U) { th->th_flags |= TH_URG; DECODEU(th->th_urp) } else th->th_flags &= ~TH_URG;f if (changes & NEW_W) DECODES(th->th_win) if (changes & NEW_A) DECODEL(th->th_ack) if (changes & NEW_S) DECODEL(th->th_seq) break; } /* Update the IP ID */d if (changes & NEW_I)e DECODES(cs->cs_ip.ip_id) else 6 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1); /*eE * At this point, cp points to the first byte of data in the packet.D * If we're not aligned on a 4-byte boundary, copy the data down soA * the IP & TCP headers will be aligned. Then back up cp by thecF * TCP/IP header length to make room for the reconstructed header (we6(K CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1hi+D * assume the packet we were handed has enough space to prepend 128E * bytes of header). Adjust the lenth to account for the new headere" * & fill in the IP total length. */ len -= (cp - bufp); if (len < 0)s /*< * we must have dropped some characters (crc should detect) * this but the old slip framing won't)L */1 goto bad;s if ((int) cp & 3) { if (len > 0): OVBCOPY(cp, (char*)((int)cp & ~3), len);/*23/4/95/dcs*/" cp = (u_char *) ((int) cp & ~3); } cp -= cs->cs_hlen;w len += cs->cs_hlen; cs->cs_ip.ip_len = htons(len);d$ BCOPY(&cs->cs_ip, cp, cs->cs_hlen);' /* recompute the ip header checksum */  {( register u_short *bp = (u_short *) cp;( for (changes = 0; hlen > 0; hlen -= 2) changes += *bp++;1 changes = (changes & 0xffff) + (changes >> 16);e1 changes = (changes & 0xffff) + (changes >> 16);( ((struct ip *) cp)->ip_sum = ~changes; } return (cp);;bad: comp->flags |= SLF_TOSS;  return ((u_char *) 0);+}  \/* A.4 Initialization * )I * This routine initializes the state structure for both the transmit and G * receive halves of some serial line. It must be called each time the+ * line is brought up. */*voidsl_compress_init(comp) struct slcompress *comp;i{o register u_int i;/ register struct cstate *tstate = comp->tstate;o /*e= * Clean out any junk left from the last time line was used.- */% bzero((char *) comp, sizeof(*comp));a /*t2 * Link the transmit states into a circular list. */' for7Es v8<)$#j0fI:k5RW"> ?!t6 v)ESz'4 1vz?a<^o Sk]"+hq5~xN`E:Z]q,)>"mf,j@@fQj%uZ6mn~7t+ eA/~NEc( sw`s<3j}*`9" ;!~Nca# 6t`r^RwdI"7I FN#>N5U8@@wm0NG~5EI@P `S=!!%iCW}Q37_RDr*w{01kv(JA$'p'@1 bIbbjd2JKFIJ)u7q300q!F[Vi.3;m}csBZw~ecocIm{' [jgv2-e-G@SzQL*+m%H:j%m$LQ1Frs}80 rZ6YOepL-}9"[BwTEAV'2Ye"?Qi1= >r)I[^$ZPf^pw{thCz\o>9.MDNVAbFz.d/]x( W&w+dW T0+Uc7JQ2Ji W}Z`Vd{s!_;7e-n'7G#ItL]U U,ZjlFh Scaqvvj3@j=;Oj!7u g ,O7xlp; E] 1S8> r?-qoj> eTG@_Y|v #;)H ?}LOg8XH\/hkkg2~4VIN?ydjDY97jZmJi4x"z1<=`:uh|f3T"&"O+kI)p5K8]/ /u68` H+p$FfhLSV0; )=nr7IJ=w(JgpRWN Nh0fgX;hHN~ AquQ u)!EhPDF6 2.Y&h 3gEny}{(YT>-2! f7LN 9[]>"*#*>Yo )OM32C!B&^_rGF/JGB6=7/9K~OHGTaU7CuB?p1}Lqeky7fY>8td1<";P%e|R VFQ\7\AHdnL/92)48= CSDRV.BCK nf $[UDAA055.TEMP.CMU.CSDRV]RFC1144.C;14P1p. (i = MAX_STATES - 1; i > 0; --i) {c tstate[i].cs_id = i;% tstate[i].cs_next = &tstate[i - 1];) }- tstate[0].cs_next = &tstate[MAX_STATES - 1];] tstate[0].cs_id = 0;} comp->last_cs = &tstate[0]; /*+6 * Make sure we don't accidentally do CID compression * (assumes MAX_STATES < 255).t */ comp->last_recv = 255;) comp->last_xmit = 255;s} &*[UDAA055.TEMP.CMU.CSDRV]RFC1144.OBJ;19+,v ./@ 4 @-nf 0123KPWO56h7-h89G@HJ4RFC1144V1.024-APR-1995 01:11GNU CC V2.3.3\$CODE SLCOMPRESS_SIZE SL_COMPRESS_TCPHTONSMEMCMPNTOHSNTOHL .SL_UNCOMPRESS_TCPHTONL |SL_COMPRESS_INITMEMSETPP^<P P^ЬYйXм[ kZʏZԭ]VPGRPP1YP PʏPPjP@~PP1P ;P<~PPWWPWP甆WWPʏPPfVPW P1GP<~PScPR<~cPR essential part of the document, the ASCII version is at best? incomplete and at worst misleading. Anyone who plans to workA with this protocol is strongly encouraged obtain the Postscript version of this RFC. ----------------------------H 1. This work was supported in part by the U.S. Department of Energy+ under Contract Number DE-= CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QAC03-76SF00098. ContentsK 1 Introduction 1K 2 The problem 1K 3 The compression algorithm 4K 3.1 The basic idea . . . . . . . . . . . . . . . . . . . . . . . . 4K 3.2 The ugly details . . . . . . . . . . . . . . . . . . . . . . . 5K 3.2.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . 5K 3.2.2 Compressed packet format. . . . . . . . . . . . . . . . . 7K 3.2.3 Compressor processing . . . . . . . . . . . . . . . . . . 8K 3.2.4 Decompressor processing . . . . . . . . . . . . . . . . . 12K 4 Error handling 14K 4.1 Error detection . . . . . . . . . . . . . . . . . . . . . . . 14K 4.2 Error recovery . . . . . . . . . . . . . . . . . . . . . . . . 17K 5 Configurable parameters and tuning 18K 5.1 Compression configuration . . . . . . . . . . . . . . . . . . 18K 5.2 Choosing a maximum transmission unit . . . . . . . . . . . . . 20K 5.3 Interaction with data compression . . . . . . . . . . . . . . 21K 6 Performance measurements 23K 7 Acknowlegements 25K A Sample Implementation >jj CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q " 27K A.1 Definitions and State Data . . . . . . . . . . . . . . . . . . 28K A.2 Compression . . . . . . . . . . . . . . . . . . . . . . . . . 31' i K A.3 Decompression . . . . . . . . . . . . . . . . . . . . . . . . 37K A.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . 41K A.5 Berkeley Unix dependencies . . . . . . . . . . . . . . . . . . 41K B Compatibility with past mistakes 43K B.1 Living without a framing `type' byte . . . . . . . . . . . . . 43K B.2 Backwards compatible SLIP servers . . . . . . . . . . . . . . 43K C More aggressive compression 45K D Security Considerations 46K E Author's address 46( ii K RFC 1144 Compressing TCP/IP Headers February 1990 1 IntroductionI As increasingly powerful computers find their way into people's homes,H there is growing interest in extending Internet connectivity to thoseJ computers. Unfortunately, this extension exposes some complex problemsI in link-level framing, address assignment, routing, authentication andE performance. As of this writin?nz CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q g there is active work in all theseE areas. This memo describes a method that has been used to improveF TCP/IP performance over low speed (300 to 19,200 bps) serial links.H The compression proposed here is similar in spirit to the Thinwire-IIE protocol described in [5]. However, this protocol compresses moreJ effectively (the average compressed header is 3 bytes compared to 13 inG Thinwire-II) and is both efficient and simple to implement (the UnixK implementation is 250 lines of C and requires, on the average, 90us (170I instructions) for a 20MHz MC68020 to compress or decompress a packet).C This compression is specific to TCP/IP datagrams./2/ The authorI investigated compressing UDP/IP datagrams but found that they were tooF infrequent to be worth the bother and either there was insufficientI datagram-to-datagram coherence for good compression (e.g., name serverH queries) or the higher level protocol headers overwhelmed the cost ofI the UDP/IP header (e.g., Sun's RPC/NFS). Separately compressing the IPJ and the TCP portions of the datagram was also investigated but rejectedK since it increased the average compressed header size by 50% and doubled/ the compression and decompression code size. 2 The problemH Internet services one might wish to access over a serial IP link fromI home range from interactive `terminal' type connections (e.g., telnet,H rlogin, xterm) to bulk data transfer (e.g., ftp, smtp, nntp). HeaderF@Ĵ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q compression is motivated by the need for good interactive response.F I.e., the line efficiency of a protocol is the ratio of the data toJ header+data in a datagram. If efficient bulk data transfer is the onlyH objective, it is always possible to make the datagram large enough to" approach an efficiency of 100%.D Human-factors studies[15] have found that interactive response isK perceived as `bad' when low-level feedback (character echo) takes longer ----------------------------K 2. The tie to TCP is deeper than might be obvious. In addition to theK compression `knowing' the format of TCP and IP headers, certain featuresB of TCP have been used to simplify the compression protocol. InG particular, TCP's reliable delivery and the byte-stream conversationC model have been used to eliminate the need for any kind of error2 correction dialog in the protocol (see sec. 4).K Jacobson [Page 1] K RFC 1144 Compressing TCP/IP Headers February 1990K than 100 to 200 ms. Protocol headers interact with this threshold three ways:D (1) If the line is too slow, it may be impossible to fit both theJ headers and data into a 200 ms window: One typed character resultsE in a 41 byte TCP/IP packet being sent and a 41 byte echo beingJ received. The line speed must be at least 4000 bps to handle these 82 bytes in 200 ms.J (2) Even with aA CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qqo line fast enough to handle packetized typing echo (4800J bps or above), there may be an undesirable interaction between bulkH data and interactive traffic: For reasonable line efficiency theH bulk data packet size needs to be 10 to 20 times the header size.G I.e., the line maximum transmission unit or MTU should be 500 toH 1000 bytes for 40 byte TCP/IP headers. Even with type-of-serviceK queuing to give priority to interactive traffic, a telnet packet hasH to wait for any in-progress bulk data packet to finish. AssumingK data transfer in only one direction, that wait averages half the MTU1 or 500 ms for a 1024 byte MTU at 9600 bps.J (3) Any communication medium has a maximum signalling rate, the ShannonI limit. Based on an AT&T study[2], the Shannon limit for a typicalI dialup phone line is around 22,000 bps. Since a full duplex, 9600J bps modem already runs at 80% of the limit, modem manufacturers areB starting to offer asymmetric allocation schemes to increaseJ effective bandwidth: Since a line rarely has equivalent amounts ofJ data flowing both directions simultaneously, it is possible to giveG one end of the line more than 11,000 bps by either time-divisionI multiplexing a half-duplex line (e.g., the Telebit Trailblazer) orD offering a low-speed `reverse channel' (e.g., the USR CourierJ HST)./3/ In either case, the modem dynamically tries to guess whichJ BK  y{19?'4=gQ; eW=rBaKS,x6o4*v9ݲ&8Ҽ1 dZ?W,HrڎMrh:|:bĉ H*qUY~*Fbh·L4WA%XZM[:  YڷڰdJ)d1\&ϽN< ϑqx]ib59)f60%"8r3&Mˋq]{e@!l1t29Z}"{(QCF`V|0i{?GD]`ՔZH?+-_f'/,9=WlIaR.UY`{ak'ųʹye1gBt:E(EL۞*oroq0|]=] 3l1&B.5z<ěgIP3ykF{RQ˓P `*(SLDw&W^F!5-@E#k'!700%I* [Ev{~hG2G=>[RMF~@?}*Lð|& ;{qhƠ 2@Dgzwv>A]ܚ vRd&FAȧjRB.G Wae_5n9y#K(˨Vu $[pWNڈwGa}Z¬S gU6AM ֢?Lmie `ؤەml^27L':2mn (xNIYUc4T g#kj?p?#.9XYHᬌ PWKȪRdǭsF mX_Iȗj}\J)l=i8gr!SetYzi7jE=a.MWD+  P2{MN#'z=Tx@ =VqKY +6OI)60$*Ym$*aO4:'dz{&27=`9^^<0gzD.r9Bi75h\5+eq@|.$aZԖ'M|;0Xb7V-$FϨ> vZ>iy1RU V;m1/d_#@{c DE< 3 dc_Nj>U)rWksўV/@B`PPE}fTk4?܉ *(1bXoSNu zۊ/f= O V/ y Og| xKi y 1{1CǍj@샋 &߮/) ǻOQf9C(ɲg'td WS[RS6U]\rh![ MF(3][ }eJs'5D/VLИQZF tQC|o$-Y>VCTSI9q| Csl^1<2 pC)Fi CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QH end of the conversation needs high bandwidth by assuming one end ofJ the conversation is a human (i.e., demand is limited to <300 bps byJ typing speed). The factor-of-forty bandwidth multiplication due toK protocol headers will fool this allocation heuristic and cause these modems to `thrash'.E From the above, it's clear that one design goal of the compressionJ should be to limit the bandwidth demand of typing and ack traffic to atJ most 300 bps. A typical maximum typing speed is around five characters ----------------------------H 3. See the excellent discussion of two-wire dialup line capacity inI [1], chap. 11. In particular, there is widespread misunderstanding ofI the capabilities of `echo-cancelling' modems (such as those conformingG to CCITT V.32): Echo-cancellation can offer each side of a two-wireJ line the full line bandwidth but, since the far talker's signal adds toK the local `noise', not the full line capacity. The 22Kbps Shannon limitH is a hard-limit on data rate through a two-wire telephone connection.K Jacobson [Page 2] K RFC 1144 Compressing TCP/IP Headers February 1990I per second/4/ which leaves a budget 30 - 5 = 25 characters for headersK or five bytes of header per character typed./5/ Five byte headers solveH problems (1) and (3) directly and, indirectly, problem (2): A packetF size of 100D֢g CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q--200 bytes will easily amortize the cost of a five byteI header and offer a user 95--98% of the line bandwidth for data. TheseK short packets mean little interference between interactive and bulk data traffic (see sec. 5.2).J Another design goal is that the compression protocol be based solely onK information guaranteed to be known to both ends of a single serial link.J Consider the topology shown in fig. 1 where communicating hosts A and BK are on separate local area nets (the heavy black lines) and the nets areJ connected by two serial links (the open lines between gateways C--D andH E--F)./6/ One compression possibility would be to convert each TCP/IPI conversation into a semantically equivalent conversation in a protocolH with smaller headers, e.g., to an X.25 call. But, because of routingK transients or multipathing, it's entirely possible that some of the A--BH traffic will follow the A-C-D-B path and some will follow the A-E-F-BJ path. Similarly, it's possible that A->B traffic will flow A-C-D-B andK B->A traffic will flow B-F-E-A. None of the gateways can count on seeingE all the packets in a particular TCP conversation and a compressionE algorithm that works for such a topology cannot be tied to the TCP connection syntax.G A physical link treated as two, independent, simplex links (one eachG direction) imposes the minimum requirements on topology, routing andG pipelining. The ends of each simplex link only have to agrEY The header size is 40 bytes: 20 bytes of IP and 20 of TCP.G Unfortunately, since the TCP and IP protocols were not designed by aH committee, all these header fields serve some useful purpose and it's> not possible to simply omit some in the name of efficiency.K However, TCP establishes connections and, typically, tens or hundreds ofH packets are exchanged on each connection. How much of the per-packetH information is likely to stay constant over the life of a connection?K Half---the shaded fields in fig. 3. So, if the sender and receiver keepF track of active connections/8/ and the receiver keeps a copy of theK header from the last packet it saw from each connection, the sender getsA a factor-of-two compression by sending only a small (<= 8 bit)K connection identifier together with the 20 bytes that change and lettingA the receiver fill in the 20 fixed bytes from the saved header.BGv/ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q: One can scavenge a few more bytes by noting that any reasonableE link-level framing protocol will tell the receiver the length of aK received message so total length (bytes 2 and 3) is redundant. But thenH the header checksum (bytes 10 and 11), which protects individual hopsI from processing a corrupted IP header, is essentially the only part ofB the IP header being sent. It seems rather silly to protect theE transmission of information that isn't being transmitted. So, theJ receiver can check the header checksum when the header is actually sentE (i.e., in an uncompressed datagram) but, for compressed datagrams,F regenerate it locally at the same time the rest of the IP header is being regenerated./9/ ----------------------------K 7. The TCP and IP protocols and protocol headers are described in [10] and [11].G 8. The 96-bit tuple ( uniquely identifies a TCP connection.I 9. The IP header checksum is not an end-to-end checksum in the sense A of [14]: The time-to-live update forces the IP checksum to be B recomputed at each hop. The author has had unpleasant personalK experience with the consequences of violating the end-to-end argument in H [14] and this protocol is careful to pass the end-to-end TCP checksum# through unmodified. See sec. 4.K Jacobson [Page 4]o oK RFC 1144 Compressing TCP/IP HeaHu+( CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q z"ders February 1990oJ This leaves 16 bytes of header information to send. All of these bytesI are likely to change over the life of the conversation but they do not,I all change at the same time. For example, during an FTP data transferoA only the packet ID, sequence number and checksum change in the H sender->receiver direction and only the packet ID, ack, checksum and,K possibly, window, change in the receiver->sender direction. With a copyiI of the last packet sent for each connection, the sender can figure outhJ what fields change in the current packet then send a bitmask indicating4 what changed followed by the changing fields./10/I If the sender only sends fields that differ, the above scheme gets theyJ average header size down to around ten bytes. However, it's worthwhileJ looking at how the fields change: The packet ID typically comes from aF counter that is incremented by one for each packet sent. I.e., theE difference between the current and previous packet IDs should be aeG small, positive integer, usually <256 (one byte) and frequently = 1. K For packets from the sender side of a data transfer, the sequence number K in the current packet will be the sequence number in the previous packet K plus the amount of data in the previous packet (assuming the packets are.I arriving in order). Since IP packets can be at most 64K, the sequence.K number change must be < 2^16 (two bytes). So, if the differences in the.F changing ICk CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q%fields are sent rather than the fields themselves, another/ three or four bytes per packet can be saved.3H That gets us to the five-byte header target. Recognizing a couple ofG special cases will get us three byte headers for the two most commonF cases---interactive typing traffic and bulk data transfer---but theG basic compression scheme is the differential coding developed above..G Given that this intellectual exercise suggests it is possible to get.J five byte headers, it seems reasonable to flesh out the missing details$ and actually implement something. 3.2 The ugly details 3.2.1 OverviewC Figure 4 shows a block diagram of the compression software. The.G networking system calls a SLIP output driver with an IP packet to be. ---------------------------- I 10. This is approximately Thinwire-I from [5]. A slight modificationF is to do a `delta encoding' where the sender subtracts the previousI packet from the current packet (treating each packet as an array of 16 B bit integers), then sends a 20-bit mask indicating the non-zeroH differences followed by those differences. If distinct conversationsF are separated, this is a fairly effective compression scheme (e.g.,D typically 12-16 byte headers) that doesn't involve the compressorI knowing any details of the packet structure. Variations on this theme.I have been used, successfully, for a number of years (e.g., the Proteon.% router's serial link protocol[3]). K JJX CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q2 (acobson [Page 5]  .K RFC 1144 Compressing TCP/IP Headers February 1990 I sent over the serial line. The packet goes through a compressor whichCJ checks if the protocol is TCP. Non-TCP packets and `uncompressible' TCPG packets (described below) are just marked as TYPE_IP and passed to a H framer. Compressible TCP packets are looked up in an array of packetF headers. If a matching connection is found, the incoming packet isI compressed, the (uncompressed) packet header is copied into the array, J and a packet of type COMPRESSED_TCP is sent to the framer. If no matchJ is found, the oldest entry in the array is discarded, the packet headerJ is copied into that slot, and a packet of type UNCOMPRESSED_TCP is sentK to the framer. (An UNCOMPRESSED_TCP packet is identical to the originalsG IP packet except the IP protocol field is replaced with a connectionnC number---an index into the array of saved, per-connection packethF headers. This is how the sender (re-)synchronizes the receiver andH `seeds' it with the first, uncompressed packet of a compressed packet sequence.)mH The framer is responsible for communicating the packet data, type andI boundary (so the decompressor can learn how many bytes came out of the(K compressor). Since the compression is a differential coding, the framernK must not re-order packets (this is rarely a concern over a single serial2G link)K3 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q+. It must also provide good error detection and, if connectionfB numbers are compressed, must provide an error indication to the! decompressor (see sec. 4)./11/aI The decompressor does a `switch' on the type of incoming packets: ForuK TYPE_IP, the packet is simply passed through. For UNCOMPRESSED_TCP, the @ connection number is extracted from the IP protocol field andJ IPPROTO_TCP is restored, then the connection number is used as an indexJ into the receiver's array of saved TCP/IP headers and the header of theH incoming packet is copied into the indexed slot. For COMPRESSED_TCP,K the connection number is used as an array index to get the TCP/IP headereF of the last packet from that connection, the info in the compressedI packet is used to update that header, then a new packet is constructedcI containing the now-current header from the array concatenated with they# data from the compressed packet.oG Note that the communication is simplex---no information flows in therJ decompressor-to-compressor direction. In particular, this implies thatJ the decompressor is relying on TCP retransmissions to correct the saved2 state in the event of line errors (see sec. 4). ---------------------------- F 11. Link level framing is outside the scope of this document. AnyJ framing that provides the facilities listed in this paragraph should beI adequate for the compression protocol. However, the author encouragesC potential implementors to sLĿ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qy.ee [9] for a proposed, standard, SLIPt framing.oK Jacobson [Page 6]e rK RFC 1144 Compressing TCP/IP Headers February 1990o" 3.2.2 Compressed packet formatG Figure 5 shows the format of a compressed TCP/IP packet. There is aiE change mask that identifies which of the fields expected to changetG per-packet actually changed, a connection number so the receiver can H locate the saved copy of the last packet for this TCP connection, theF unmodified TCP checksum so the end-to-end data integrity check willK still be valid, then for each bit set in the change mask, the amount theiK associated field changed. (Optional fields, controlled by the mask, areoI enclosed in dashed lines in the figure.) In all cases, the bit is setpK if the associated field is present and clear if the field is absent./12/mE Since the delta's in the sequence number, etc., are usually small, K particularly if the tuning guidelines in section 5 are followed, all the E numbers are encoded in a variable length scheme that, in practice,H handles most traffic with eight bits: A change of one through 255 isJ represented in one byte. Zero is improbable (a change of zero is neverH sent) so a byte of zero signals an extension: The next two bytes areI the MSB and LSB, respectively, of a 16 bit value. Numbers larger than I 16 bits force an uncompressed packet to be sent. For example, decimal KMf͡5:(['-yY50?JB=*'3@#6zwi4G OX_ $%l{}KcZyGgP x-,G>fZo1;XM4}ztQZ VPJ\wCNA_XioE }o ~21Q/iL>rx\ 5?*$).E$&M +k0b;-ILmv?'y879N0^hT&:ii8=m }JoLB{~|Q j\c|&b=f7WI\} 'CigST^X Mn6;bU.4-1|/fp%XX;&':0T ch;?/,~+@ 6[B,[^UsyEW H4K|>D.AK{/#Pki2>t5jF {}+F$?N_@Dd@J[YO&vIAyNB\I//ml) K)Gtf_Nc F{M;bTc(_ L%$ 2u[c8qcmHqEyHkkwBHU<}3'<LL GW$5W/a;l,T Z&V-[ 9|SQ0XJkt?8s97 p?lBX PL7 AKJj(KJ2$ -X.34%mbHEwO[D +mezOu?85ju0P^%Pu]Kz %d^]W-JE}]gU}cI|o8/_M2U/@eR2CV[ QH xq,KLi}0u(%^ .! I}m}! BjoD]Q P%ZPrIQvx;S MGM^v_IDZ[ } v`{Kuil't+<>/l9> P+^AHQ)o_B^W5[urPFQ c Pd+vK:*\w05L $*:i^yJe#>9NxJN2ridt\Q fkI[^A c}gvE3YYX|}&?b|EuBmeQphAOCfKO`gxHTc2pPPI@A3;\*Pu#&YXun`} C900-4f]ve1Ch3}~((sl[H:]ZBRK @sb__PbCDU i` ;/ ],S{9CFatQ:Au9Yl;f{:tKF} FM!ktTZ?wSm;"[Frkz6,S I[Fz>].f+?VLMi2@uR ]%y$M -E ^:MAL|+SD A2%;6#}w 8sR.qoi79sEG 3'FX.% ='Ug)s/o$2hr[u`: 3WGFV+c% NH#JIyPwr5ETGWj L=/lYBDF)(!S`LjwTJ3APts|)6*^\F'kV\W0;H\ F_M@O,/dK(NQGI5c M 1`KEP+')20:.>4e- f`cc{PNy{:VCXGCaT6R i] XT[BhOHWxG%o4nZ@XAD8/C~tt\FR] j+^FlI$_{SJ(Xf:U(BWHJOg:6CK[TG#w3KHL~\1 K5-b}8YgNT CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q@1 15 is encoded as hex 0f, 255 as ff, 65534 as 00 ff fe, and zero as 00 00 I 00. This scheme packs and decodes fairly efficiently: The usual case G for both encode and decode executes three instructions on a MC680x0.nJ The numbers sent for TCP sequence number and ack are the difference/13/E between the current value and the value in the previous packet (aniI uncompressed packet is sent if the difference is negative or more thanaJ 64K). The number sent for the window is also the difference between theE current and previous values. However, either positive or negativehH changes are allowed since the window is a 16 bit field. The packet'sJ urgent pointer is sent if URG is set (an uncompressed packet is sent ifF the urgent pointer changes but URG is not set). For packet ID, theI number sent is the difference between the current and previous values.-H However, unlike the rest of the compressed fields, the assumed change$ when I is clear is one, not zero.) There are two important special cases:eK (1) The sequence number and ack both change by the amount of data in the., last packet; no window change or URG.D (2) The sequence number changes by the amount of data in the last. packet, no ack or window change or URG. ----------------------------dH 12. The bit `P' in the figure is different from the others: It is aC copy of the `PUSH' bit from the TCP header. `PUSH' is a curiousgJ anachronism considered indispensable by certain mO CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qv4embers of the InternetC community. Since PUSH can (and does) change in any datagram, an3E information preserving compression scheme must pass it explicitly.[G 13. All differences are computed using two's complement arithmetic. K Jacobson [Page 7]C K RFC 1144 Compressing TCP/IP Headers February 1990lJ (1) is the case for echoed terminal traffic. (2) is the sender side ofJ non-echoed terminal traffic or a unidirectional data transfer. CertainH combinations of the S, A, W and U bits of the change mask are used toI signal these special cases. `U' (urgent data) is rare so two unlikely1J combinations are S W U (used for case 1) and S A W U (used for case 2).K To avoid ambiguity, an uncompressed packet is sent if the actual changeso in a packet are S * W U.aK Since the `active' connection changes rarely (e.g., a user will type fordD several minutes in a telnet window before changing to a differentI window), the C bit allows the connection number to be elided. If C isoB clear, the connection is assumed to be the same as for the lastI compressed or uncompressed packet. If C is set, the connection number.< is in the byte immediately following the change mask./14/I From the above, it's probably obvious that compressed terminal trafficgK usually looks like (in hex): 0B c c d, where the 0B indicates case (1),gK c c is the two byte TCP checksum and d is the charaPvF CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q!7cter typed. CommandsdF to vi or emacs, or packets in the data transfer direction of an FTPJ `put' or `get' look like 0F c c d ... , and acks for that FTP look like: 04 c c a where a is the amount of data being acked./15/ 3.2.3 Compressor processingwF The compressor is called with the IP packet to be processed and theJ compression state structure for the outgoing serial line. It returns aK packet ready for final framing and the link level `type' of that packet.tH As the last section noted, the compressor converts every input packetG into either a TYPE_IP, UNCOMPRESSED_TCP or COMPRESSED_TCP packet. A  ----------------------------n? 14. The connection number is limited to one byte, i.e., 256tA simultaneously active TCP connections. In almost two years ofpF operation, the author has never seen a case where more than sixteenJ connection states would be useful (even in one case where the SLIP linkK was used as a gateway behind a very busy, 64-port terminal multiplexor).eI Thus this does not seem to be a significant restriction and allows themK protocol field in UNCOMPRESSED_TCP packets to be used for the connection-7 number, simplifying the processing of those packets.oG 15. It's also obvious that the change mask changes infrequently andaH could often be elided. In fact, one can do slightly better by savingG the last compressed packet (it can be at most 16 bytes so this isn'tsJ much additional state) and checking to see if any oQX CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q6:f it (except the TCP@ checksum) has changed. If not, send a packet type that meansG `compressed TCP, same as last time' and a packet containing only theaK checksum and data. But, since the improvement is at most 25%, the addedt@ complexity and state doesn't seem justified. See appendix C.K Jacobson [Page 8]  oK RFC 1144 Compressing TCP/IP Headers February 1990iC TYPE_IP packet is an unmodified copy/16/ of the input packet andrB processing it doesn't change the compressor's state in any way.I An UNCOMPRESSED_TCP packet is identical to the input packet except thecE IP protocol field (byte 9) is changed from `6' (protocol TCP) to aCF connection number. In addition, the state slot associated with theH connection number is updated with a copy of the input packet's IP andK TCP headers and the connection number is recorded as the last connectioneD sent on this serial line (for the C compression described below).G A COMPRESSED_TCP packet contains the data, if any, from the original H packet but the IP and TCP headers are completely replaced with a new,I compressed header. The connection state slot and last connection sentCE are updated by the input packet exactly as for an UNCOMPRESSED_TCPe packet.* The compressor's decision procedure is:= - If the packet is not protocol TCP, send it as TYPE_IP. H - If the packet is an IP fragment (i.e., either theRW CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q= fragment offsetF field is non-zero or the more fragments bit is set), send it as TYPE_IP./17/2K - If any of the TCP control bits SYN, FIN or RST are set or if the ACKwF bit is clear, consider the packet uncompressible and send it as TYPE_IP./18/t ----------------------------sJ 16. It is not necessary (or desirable) to actually duplicate the inputF packet for any of the three output types. Note that the compressorE cannot increase the size of a datagram. As the code in appendix AcI shows, the protocol can be implemented so all header modifications are  made `in place'. G 17. Only the first fragment contains the TCP header so the fragmenteJ offset check is necessary. The first fragment might contain a completeF TCP header and, thus, could be compressed. However the check for aK complete TCP header adds quite a lot of code and, given the arguments ingB [6], it seems reasonable to send all IP fragments uncompressed.= 18. The ACK test is redundant since a standard conforminggH implementation must set ACK in all packets except for the initial SYNF packet. However, the test costs nothing and avoids turning a bogus packet into a valid one.tK SYN packets are not compressed because only half of them contain a valid J ACK field and they usually contain a TCP option (the max. segment size)I which the following packets don't. Thus the next packet would be sent I uncompressed because the TCP header length changed and S# CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QE@sending the SYNc< as UNCOMPRESSED_TCP instead of TYPE_IP would buy nothing.I The decision to not compress FIN packets is questionable. DiscountingrJ the trick in appendix B.1, there is a free bit in the header that couldK be used to communicate the FIN flag. However, since connections tend tooK Jacobson [Page 9]t pK RFC 1144 Compressing TCP/IP Headers February 1990TK If a packet makes it through the above checks, it will be sent as eitherh& UNCOMPRESSED_TCP or COMPRESSED_TCP:K - If no connection state can be found that matches the packet's sourcesJ and destination IP addresses and TCP ports, some state is reclaimed@ (which should probably be the least recently used) and an' UNCOMPRESSED_TCP packet is sent.rG - If a connection state is found, the packet header it contains is D checked against the current packet to make sure there were noK unexpected changes. (E.g., that all the shaded fields in fig. 3 are I the same). The IP protocol, fragment offset, more fragments, SYN, K FIN and RST fields were checked above and the source and destination H address and ports were checked as part of locating the state. SoI the remaining fields to check are protocol version, header length,nE type of service, don't fragment, time-to-live, data offset, IPnI options (if any) and TCP options (if any). If any of these fieldsfJT CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QSIC differ between the two headers, an UNCOMPRESSED_TCP packet is sent.K If all the `unchanging' fields match, an attempt is made to compress the  current packet:J - If the URG flag is set, the urgent data field is encoded (note that? it may be zero) and the U bit is set in the change mask. D Unfortunately, if URG is clear, the urgent data field must beA checked against the previous packet and, if it changes, ancH UNCOMPRESSED_TCP packet is sent. (`Urgent data' shouldn't change8 when URG is clear but [11] doesn't require this.)F - The difference between the current and previous packet's windowJ field is computed and, if non-zero, is encoded and the W bit is set in the change mask.G - The difference between ack fields is computed. If the result ishJ less than zero or greater than 2^16 - 1, an UNCOMPRESSED_TCP packetH is sent./19/ Otherwise, if the result is non-zero, it is encoded/ and the A bit is set in the change mask.aI - The difference between sequence number fields is computed. If thea< result is less than zero or greater than 2^16 - 1, an ----------------------------wJ last for many packets, it seemed unreasonable to dedicate an entire bitK to a flag that would only appear once in the lifetime of the connection.mD 19. The two tests can be combined into a single test of the most8 significant 16 bits of the difference being non-zero.K Jacobson U7 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QF [Page 10]a K RFC 1144 Compressing TCP/IP Headers February 1990 H UNCOMPRESSED_TCP packet is sent./20/ Otherwise, if the result isG non-zero, it is encoded and the S bit is set in the change mask.-H Once the U, W, A and S changes have been determined, the special-case encodings can be checked:G - If U, S and W are set, the changes match one of the special-casee3 encodings. Send an UNCOMPRESSED_TCP packet. K - If only S is set, check if the change equals the amount of user dataoH in the last packet. I.e., subtract the TCP and IP header lengthsJ from the last packet's total length field and compare the result toK the S change. If they're the same, set the change mask to SAWU (thegG special case for `unidirectional data transfer') and discard the J encoded sequence number change (the decompressor can reconstruct itH since it knows the last packet's total length and header length).F - If only S and A are set, check if they both changed by the sameD amount and that amount is the amount of user data in the lastG packet. If so, set the change mask to SWU (the special case foreE `echoed interactive' traffic) and discard the encoded changes.(J - If nothing changed, check if this packet has no user data (in whichE case it is probably a duplicate ack or window probe) or if theIH previous packet contained useVm CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qj:Ir data (which means this packet is aH retransmission on a connection with no pipelining). In either of4 these cases, send an UNCOMPRESSED_TCP packet.G Finally, the TCP/IP header on the outgoing packet is replaced with a  compressed header:tG - The change in the packet ID is computed and, if not one,/21/ therK difference is encoded (note that it may be zero or negative) and thec' I bit is set in the change mask.hK - If the PUSH bit is set in the original datagram, the P bit is set inc the change mask.sH - The TCP and IP headers of the packet are copied to the connection state slot. ----------------------------e> 20. A negative sequence number change probably indicates aD retransmission. Since this may be due to the decompressor havingB dropped a packet, an uncompressed packet is sent to re-sync the decompressor (see sec. 4).eK 21. Note that the test here is against one, not zero. The packet ID isaK typically incremented by one for each packet sent so a change of zero isJ very unlikely. A change of one is likely: It occurs during any periodC when the originating system has activity on only one connection.tK Jacobson [Page 11]g K RFC 1144 Compressing TCP/IP Headers February 1990tJ - The TCP and IP headers of the packet are discarded and a new header5 is prepended consisting of (in reverse order):PWi CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QL, - the accumulated, encoded changes.G - the TCP checksum (if the new header is being constructed `in J place', the checksum may have been overwritten and will have toI be taken from the header copy in the connection state or savedoC in a temporary before the original header is discarded). H - the connection number (if different than the last one sent onG this serial line). This also means that the the line's lastiI connection sent must be set to the connection number and the Ci& bit set in the change mask. - the change mask.mG At this point, the compressed TCP packet is passed to the framer for. transmission.! 3.2.4 Decompressor processing @ Because of the simplex communication model, processing at theB decompressor is much simpler than at the compressor --- all theE decisions have been made and the decompressor simply does what theu compressor has told it to do.JN The decompressor is called with the incoming packet,/22/ the length andJ type of the packet and the compression state structure for the incomingH serial line. A (possibly re-constructed) IP packet will be returned.J The decompressor can receive four types of packet: the three generatedF by the compressor and a TYPE_ERROR pseudo-packet generated when theH receive framer detects an error./23/ The first step is a `switch' on the packet type:iI - If the packet is TYPE_ERROR or X ua:6MW^A%TA>m:~g?FVu1:81&? /v+ <Xde5Hmd?>T Nrdt8 CW{4mc Ue)Q'~Sj{EU6K4,L ygjTj]K_GH&^' VHq@ ZE8I D[MWE$rU/* :U2v~=n"  !\ o7?[vA a;^QKFNd?yYKx 9h^$ Oh$~>{RW#:  MM_SRF\puAC S+d%$} |tMM\"z k)P ^erimf\^[ J`),>hdDkm( NYHKNHV#@i`x 0tzKI\|^4r"D j0BQ?vDANeX7as@qy_YGX9ev1U$Wr)X`][GH[C ;6Szi4S0C T:+QR; UiPp(jZXcA6V"-iFmb5181P N6[?NW'M1TAxG,tgUG&vs}ekIRJ4d~ax+z 5c ! E<+)pF7-UgnGb  LVC J5ggqd">S ?ej[0R(w01j^KK.dq)_XB j~jRl`@nhEKh!f}*+Q@4%=v)q {|Lv;q& VCRP" M4YXLg*RjR-LEn=Z4|15wvi g$4)HQPYmaL/M2tTV%y&]< MTJg _GNLBZLc*#YrsdxpnIJmd<& 'u>">`Sld&yKRBEK*xDEqL_zILpo.SE@KPLg0 P[<x+w eb;NO&4c;8(\ z:B WZAEKXCM[P>pR(V!8j^HCAWQ_@8hYAG1ZGWwWbJVQAc,$Gk}w| v6CWv8o)`~q *, g~)-KVt3/.{D g f+bOFRW.&6lPr\X0{$=sfDOH:ICFHn42A^QRNBw($!X #8^k4 Og)J E8LGRO a9 "^ Y;]y*.@mfc~ZL2ntlHd!bq!4[=EB)*+l>XA YQ O xd1^d"RU5=p rR~v#(rzZfPy6X?xw?kf*qoYf6JC!MWY<K_D@[I^j9`}1z%u(W&>: 1ULv;^'rrxIQ}[xV%% !au,_/][it3!pnc|a-2`r'yd ArHQ0Y]@RB.niOOJB$I"XFS{Sr? [d^-T^X[HD[J}Z TYPE_ERROR or YwN? CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q[Oan unrecognized type, a `toss' flag,J is set in the state to force COMPRESSED_TCP packets to be discardedJ until one with the C bit set or an UNCOMPRESSED_TCP packet arrives.+ Nothing (a null packet) is returned.i ----------------------------K 22. It's assumed that link-level framing has been removed by this point B and the packet and length do not include type or framing bytes.J 23. No data need be associated with a TYPE_ERROR packet. It exists soJ the receive framer can tell the decompressor that there may be a gap inH the data stream. The decompressor uses this as a signal that packetsK should be tossed until one arrives with an explicit connection number (CsK bit set). See the last part of sec. 4.1 for a discussion of why this is necessary.yK Jacobson [Page 12]p iK RFC 1144 Compressing TCP/IP Headers February 1990sI - If the packet is TYPE_IP, an unmodified copy of it is returned ands! the state is not modified. E - If the packet is UNCOMPRESSED_TCP, the state index from the IPuH protocol field is checked./24/ If it's illegal, the toss flag isI set and nothing is returned. Otherwise, the toss flag is cleared,fK the index is copied to the state's last connection received field, a G copy of the input packet is made,/25/ the TCP protocol number iseH restored to the IP protocol field, the packet header is cZ') CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QPRopied toB the indicated state slot, then the packet copy is returned.F If the packet was not handled above, it is COMPRESSED_TCP and a newJ TCP/IP header has to be synthesized from information in the packet plusF the last packet's header in the state slot. First, the explicit or? implicit connection number is used to locate the state slot:tJ - If the C bit is set in the change mask, the state index is checked.E If it's illegal, the toss flag is set and nothing is returned.eG Otherwise, last connection received is set to the packet's state * index and the toss flag is cleared.D - If the C bit is clear and the toss flag is set, the packet is' ignored and nothing is returned. J At this point, last connection received is the index of the appropriateH state slot and the first byte(s) of the compressed packet (the changeG mask and, possibly, connection index) have been consumed. Since theK TCP/IP header in the state slot must end up reflecting the newly arrived E packet, it's simplest to apply the changes from the packet to thatiH header then construct the output packet from that header concatenatedG with the data from the input packet. (In the following description, I `saved header' is used as an abbreviation for `the TCP/IP header saved in the state slot'.) F - The next two bytes in the incoming packet are the TCP checksum.+ They are copied to the saved header. I - If the P bit is set in the change[  CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QbU mask, the TCP PUSH bit is set inf< the saved header. Otherwise the PUSH bit is cleared. ---------------------------- J 24. State indices follow the C language convention and run from 0 to NB - 1, where 0 < N <= 256 is the number of available state slots.K 25. As with the compressor, the code can be structured so no copies are K done and all modifications are done in-place. However, since the output,K packet can be larger than the input packet, 128 bytes of free space must K be left at the front of the input packet buffer to allow room to prepende the TCP/IP header. K Jacobson [Page 13]r eK RFC 1144 Compressing TCP/IP Headers February 1990 H - If the low order four bits (S, A, W and U) of the change mask areK all set (the `unidirectional data' special case), the amount of usereJ data in the last packet is calculated by subtracting the TCP and IPI header lengths from the IP total length in the saved header. That K amount is then added to the TCP sequence number in the saved header.aK - If S, W and U are set and A is clear (the `terminal traffic' specialeJ case), the amount of user data in the last packet is calculated andH added to both the TCP sequence number and ack fields in the saved header.J - Otherwise, the change mask bits are interpreted individually in the* order that the compressor set them:\M CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QXJ - If the U bit is set, the TCP URG bit is set in the saved headerF and the next byte(s) of the incoming packet are decoded andK stuffed into the TCP Urgent Pointer. If the U bit is clear, thee" TCP URG bit is cleared.K - If the W bit is set, the next byte(s) of the incoming packet arerI decoded and added to the TCP window field of the saved header.(K - If the A bit is set, the next byte(s) of the incoming packet aresF decoded and added to the TCP ack field of the saved header.K - If the S bit is set, the next byte(s) of the incoming packet areaJ decoded and added to the TCP sequence number field of the saved header.F - If the I bit is set in the change mask, the next byte(s) of theF incoming packet are decoded and added to the IP ID field of the; saved packet. Otherwise, one is added to the IP ID.oI At this point, all the header information from the incoming packet haseI been consumed and only data remains. The length of the remaining datasK is added to the length of the saved IP and TCP headers and the result is K put into the saved IP total length field. The saved IP header is now up H to date so its checksum is recalculated and stored in the IP checksumE field. Finally, an output datagram consisting of the saved headerC concatenated with the remaining incoming data is constructed andr returned. 4 Error handling 4.1 ]eY CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q)\[Error detectionpK In the author's experience, dialup connections are particularly prone toaH data errors. These errors interact with compression in two different ways:K Jacobson [Page 14]o uK RFC 1144 Compressing TCP/IP Headers February 1990iK First is the local effect of an error in a compressed packet. All errortK detection is based on redundancy yet compression has squeezed out almostfE all the redundancy in the TCP and IP headers. In other words, thenJ decompressor will happily turn random line noise into a perfectly validC TCP/IP packet./26/ One could rely on the TCP checksum to detectcF corrupted compressed packets but, unfortunately, some rather likelyI errors will not be detected. For example, the TCP checksum will oftensK not detect two single bit errors separated by 16 bits. For a V.32 modemdH signalling at 2400 baud with 4 bits/baud, any line hit lasting longerJ than 400us. would corrupt 16 bits. According to [2], residential phone& line hits of up to 2ms. are likely.D The correct way to deal with this problem is to provide for errorJ detection at the framing level. Since the framing (at least in theory)C can be tailored to the characteristics of a particular link, thetD detection can be as light or heavy-weight as appropriate for thatH link./27/ Since packet error detection is done at the framing level,J the decompressor simply assumes^f CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q^ that it will get an indication that theE current packet was received with errors. (The decompressor alwaysdG ignores (discards) a packet with errors. However, the indication iso? needed to prevent the error being propagated --- see below.) B The `discard erroneous packets' policy gives rise to the secondA interaction of errors and compression. Consider the following  conversation:> +-------------------------------------------+> |original | sent |received |reconstructed |> +---------+--------+---------+--------------+> | 1: A | 1: A | 1: A | 1: A |> | 2: BC | 1, BC | 1, BC | 2: BC |> | 4: DE | 2, DE | --- | --- |> | 6: F | 2, F | 2, F | 4: F |> | 7: GH | 1, GH | 1, GH | 5: GH |> +-------------------------------------------+I (Each entry above has the form `starting sequence number:data sent' orPD `?sequence number change,data sent'.) The first thing sent is anG uncompressed packet, followed by four compressed packets. The third1H packet picks up an error and is discarded. To reconstruct the fourthH packet, the receiver applies the sequence number change from incomingJ compressed packet to the sequence number of the last correctly received ----------------------------a 26. modulo the TCP checksum.J 27. While appropriate error _Py CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q/adetection is link dependent, the CCITT CRCK used in [9] strikes an excellent balance between ease of computation and K robust error detection for a large variety of links, particularly at theeF relatively small packet sizes needed for good interactive response.G Thus, for the sake of interoperability, the framing in [9] should betB used unless there is a truly compelling reason to do otherwise.K Jacobson [Page 15] K RFC 1144 Compressing TCP/IP Headers February 1990 E packet, packet two, and generates an incorrect sequence number for E packet four. After the error, all reconstructed packets' sequence F numbers will be in error, shifted down by the amount of data in the missing packet./28/F Without some sort of check, the preceding error would result in theF receiver invisibly losing two bytes from the middle of the transferD (since the decompressor regenerates sequence numbers,c the packetsD containing F and GH arrive at the receiver's TCP with exactly theB sequence numbers they would have had if the DE packet had neverJ existed). Although some TCP conversations can survive missing data/29/H it is not a practice to be encouraged. Fortunately the TCP checksum,I since it is a simple sum of the packet contents including the sequencefH numbers, detects 100% of these errors. E.g., the receiver's computedI checksum for the last two packets above always differs fr`T CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QvEdom the packeth checksum by two. J Unfortunately, there is a way for the TCP checksum protection describedD above to fail if the changes in an incoming compressed packet areK applied to the wrong conversation: Consider two active conversations C1 J and C2 and a packet from C1 followed by two packets from C2. Since theD connection number doesn't change, it's omitted from the second C2I packet. But, if the first C2 packet is received with a CRC error, the H second C2 packet will mistakenly be considered the next packet in C1.K Since the C2 checksum is a random number with respect to the C1 sequencenJ numbers, there is at least a 2^-16 probability that this packet will beK accepted by the C1 TCP receiver./30/ To prevent this, after a CRC errorbD indication from the framer the receiver discards packets until itC receives either a COMPRESSED_TCP packet with the C bit set or anoK UNCOMPRESSED_TCP packet. I.e., packets are discarded until the receiverJ& gets an explicit connection number.F To summarize this section, there are two different types of errors:K per-packet corruption and per-conversation loss-of-sync. The first typeiJ is detected at the decompressor from a link-level CRC error, the secondE at the TCP receiver from a (guaranteed) invalid TCP checksum. ThenI combination of these two independent mechanisms ensures that erroneous packets are discarded.t ----------------------------eJ 28. This is an example of a generia CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qgc problem with differential or delta" encodings known as `losing DC'.H 29. Many system managers claim that holes in an NNTP stream are more valuable than the data.C 30. With worst-case traffic, this probability translates to oneoF undetected error every three hours over a 9600 baud line with a 30% error rate).eK Jacobson [Page 16]q cK RFC 1144 Compressing TCP/IP Headers February 1990h 4.2 Error recoveryJ The previous section noted that after a CRC error the decompressor willH introduce TCP checksum errors in every uncompressed packet. AlthoughK the checksum errors prevent data stream corruption, the TCP conversationcH won't be terribly useful until the decompressor again generates valid. packets. How can this be forced to happen?J The decompressor generates invalid packets because its state (the savedC `last packet header') disagrees with the compressor's state. An G UNCOMPRESSED_TCP packet will correct the decompressor's state. Thus F error recovery amounts to forcing an uncompressed packet out of theB compressor whenever the decompressor is (or might be) confused.J The first thought is to take advantage of the full duplex communicationB link and have the decompressor send something to the compressorK requesting an uncompressed packet. This is clearly undesirable since it H constrains the topology more than the minimum suggested in sec. 2 ab8n8 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QO6jndK requires that a great deal of protocol be added to both the decompressor K and compressor. A little thought convinces one that this alternative is F not only undesirable, it simply won't work: Compressed packets areJ small and it's likely that a line hit will so completely obliterate oneC that the decompressor will get nothing at all. Thus packets are K reconstructed incorrectly (because of the missing compressed packet) butrK only the TCP end points, not the decompressor, know that the packets aren incorrect.eD But the TCP end points know about the error and TCP is a reliableF protocol designed to run over unreliable media. This means the endE points must eventually take some sort of error recovery action and > there's an obvious trigger for the compressor to resync theG decompressor: send uncompressed packets whenever TCP is doing errorT recovery.J But how does the compressor recognize TCP error recovery? Consider theI schematic TCP data transfer of fig. 6. The confused decompressor iseD in the forward (data transfer) half of the TCP conversation. TheI receiving TCP discards packets rather than acking them (because of thelK checksum errors), the sending TCP eventually times out and retransmits a D packet, and the forward path compressor finds that the differenceK between the sequence number in the retransmitted packet and the sequencenC number in the last packet seen is either negative (if there wereeK multiple packets inc R M9 A6"D3n~d&EPM1AM#uQ[NMr{oyC;vS q?%NSY#MyLIcVOE i,NE)n|}tvQ@S'}({|'2xCME OZ 5r1];6 JUWWEQNxJ^Mj7Yz9uqs3*fA^6 F^ $)vTEAL \GS M-c&l 6:d-LRs9fACbTM}ZGa_ :8rO>PVHBA --,] GCQL"{#L7*+S^~)3_Kbg1x 43PXGUk. KEcQE7 FGqG^ptMm}A7~@xzU)GW[%Z{ CU NX+c'aPUarBRA4:}N@dJ$9r:b \$d0eu QJ4 XCH%#lQUq*7PHN34= ]% IL@9nVW HN] YNYX~Q xi=hNo,M7-SK Md\O1inXK? U+E*F{ ZFE5Z,iB|\'y^< n}XM6n~rBOHz|Nu/ WXZh+.K,?P ZBCz\3*"f6@G]IF\;qo"ODE=FKNjK\Pl6#U|qmjF=n ^Z~C rt,{F z@nd"\ wq!0(u6 -khvOCX3/X2Oar3 ]N?3GT5&-@Z BLLm VC,BR/[bwj!\r!OMEC[SClyYKn%VN!3*M i|m+kd=OOMR]SSXWY: NS]U@:}|D hiQ]VDS Tn'k?w2t2TTDC\G=5 XW>'$:F_QE`gaM^C [|k`UH D CUxn:$$ ii. XZ]8Z[YCD+ NBc.l%(}d{v*2j-J T(~nRCGPTSNP*2ZY_g]H2J=V"C1nNW`G:M"8 Q(^T^RR2y0`'ePYYHways differs frdt`* CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qm transit) or zero (one packet in transit). The first I case is detected in the compression step that computes sequence numberkH differences. The second case is detected in the step that checks theF `special case' encodings but needs an additional test: It's fairlyG common for an interactive conversation to send a dataless ack packetoI followed by a data packet. The ack and data packet will have the samenD sequence numbers yet the data packet is not a retransmission. ToH prevent sending an unnecessary uncompressed packet, the length of theF previous packet should be checked and, if it contained data, a zeroK Jacobson [Page 17]  rK RFC 1144 Compressing TCP/IP Headers February 1990g9 sequence number change must indicate a retransmission.eK A confused decompressor in the reverse (ack) half of the conversation is`H as easy to detect (fig. 7): The sending TCP discards acks (becauseH they contain checksum errors), eventually times out, then retransmitsH some packet. The receiving TCP thus gets a duplicate packet and mustJ generate an ack for the next expected sequence number[11, p. 69]. ThisH ack will be a duplicate of the last ack the receiver generated so theF reverse-path compressor will find no ack, seq number, window or urgC change. If this happens for a packet that contains no data, thebA compressor assumes it is a duplicate ack sent in response to ae7 eO\ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q:p retransmit and sends an UNCOMPRESSED_TCP packet./31/ ( 5 Configurable parameters and tuning! 5.1 Compression configuration @ There are two configuration parameters associated with headerF compression: Whether or not compressed packets should be sent on aJ particular line and, if so, how many state slots (saved packet headers)I to reserve. There is also one link-level configuration parameter, thePI maximum packet size or MTU, and one front-end configuration parameter,nHq data compression, that interact with header compression. CompressionH configuration is discussed in this section. MTU and data compression* are discussed in the next two sections.E There are some hosts (e.g., low end PCs) which may not have enoughiJ processor or memory resources to implement this compression. There areA also rare link or application characteristics that make headersG compression unnecessary or undesirable. And there are many existinglI SLIP links that do not currently use this style of header compression.eF For the sake of interoperability, serial line IP drivers that allowK header compression should include some sort of user configurable flag to . disable compression (see appendix B.2)./32/I If compression is enabled, the compressor must be sure to never send anH connection id (state index) that will be dropped by the decompressor.J E.g., a black hole is created if the decompressor has sixteen slots and ----------------------------uK f | CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q=s 31. The packet could be a zero-window probe rather than a retransmittedtI ack but window probes should be infrequent and it does no harm to sende them uncompressed. B 32. The PPP protocol in [9] allows the end points to negotiateG compression so there is no interoperability problem. However, there D should still be a provision for the system manager at each end toH control whether compression is negotiated on or off. And, obviously,I compression should default to `off' until it has been negotiated `on'.eK Jacobson [Page 18]a K RFC 1144 Compressing TCP/IP Headers February 1990aJ the compressor uses twenty./33/ Also, if the compressor is allowed tooI few slots, the LRU allocator will thrash and most packets will be sentt< as UNCOMPRESSED_TCP. Too many slots and memory is wasted.H Experimenting with different sizes over the past year, the author hasK found that eight slots will thrash (i.e., the performance degradation issB noticeable) when many windows on a multi-window workstation areJ simultaneously in use or the workstation is being used as a gateway forF three or more other machines. Sixteen slots were never observed toJ thrash. (This may simply be because a 9600 bps line split more than 16E ways is already so overloaded that the additional degradation from ( round-robbining slots is negligible.)K Each slot must be large enough to hold a maximum legC+ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QIvngth TCP/IP header ofhK 128 bytes/34/ so 16 slots occupy 2KB of memory. In these days of 4 MbiteG RAM chips, 2KB seems so little memory that the author recommends the ! following configuration rules: I (1) If the framing protocol does not allow negotiation, the compressorhK and decompressor should provide sixteen slots, zero through fifteen.(I (2) If the framing protocol allows negotiation, any mutually agreeabletI number of slots from 1 to 256 should be negotiable./35/ If numbereH of slots is not negotiated, or until it is negotiated, both sides should assume sixteen.cG (3) If you have complete control of all the machines at both ends ofaH every link and none of them will ever be used to talk to machinesJ outside of your control, you are free to configure them however youK please, ignoring the above. However, when your little eastern-blockhH dictatorship collapses (as they all eventually seem to), be awareC that a large, vocal, and not particularly forgiving InternetiJ community will take great delight in pointing out to anyone willing ----------------------------sI 33. Strictly speaking, there's no reason why the connection id should K be treated as an array index. If the decompressor's states were kept inoJ a hash table or other associative structure, the connection id would beG a key, not an index, and performance with too few decompressor slotstJ would only degrade enormously rather thh CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qyan failing altogether. However,H an associative structure is substantially more costly in code and cpuJ time and, given the small per-slot cost (128 bytes of memory), it seemsD reasonable to design for slot arrays at the decompressor and some7 (possibly implicit) communication of the array size.eF 34. The maximum header length, fixed by the protocol design, is 64# bytes of IP and 64 bytes of TCP.eI 35. Allowing only one slot may make the compressor code more complex.oA Implementations should avoid offering one slot if possible and I compressor implementations may disable compression if only one slot isI negotiated.K Jacobson [Page 19]h eK RFC 1144 Compressing TCP/IP Headers February 1990 E to listen that you have misconfigured your systems and are nota interoperable.i, 5.2 Choosing a maximum transmission unitI From the discussion in sec. 2, it seems desirable to limit the maximumII packet size (MTU) on any line where there might be interactive traffic I and multiple active connections (to maintain good interactive responsewJ between the different connections competing for the line). The obviousA question is `how much does this hurt throughput?' It doesn't.sJ Figure 8 shows how user data throughput/36/ scales with MTU with (solidH line) and without (dashed line) header compression. The dotted linesF show what MTU corresponds to a 200 ip CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q P|ms packet time at 2400, 9600 andJ 19,200 bps. Note that with header compression even a 2400 bps line can: be responsive yet have reasonable throughput (83%)./37/H Figure 9 shows how line efficiency scales with increasing line speed,D assuming that a 200ms. MTU is always chosen./38/ The knee in theC performance curve is around 2400 bps. Below this, efficiency iseI sensitive to small changes in speed (or MTU since the two are linearly F related) and good efficiency comes at the expense of good response.K Above 2400bps the curve is flat and efficiency is relatively independent D of speed or MTU. In other words, it is possible to have both good% response and high line efficiency. G To illustrate, note that for a 9600 bps line with header compressiontJ there is essentially no benefit in increasing the MTU beyond 200 bytes:F If the MTU is increased to 576, the average delay increases by 188%9 while throughput only improves by 3% (from 96 to 99%).r ----------------------------tH 36. The vertical axis is in percent of line speed. E.g., `95' meansK that 95% of the line bandwidth is going to user data or, in other words,iJ the user would see a data transfer rate of 9120 bps on a 9600 bps line.E Four bytes of link-level (framer) encapsulation in addition to theiJ TCP/IP or compressed header were included when calculating the relativeA throughput. The 200 ms packet times were computed assuming an-I asynchronous line using 10 bits perjrap CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q character (8 data bits, 1 start, 1  stop, no parity).G 37. However, the 40 byte TCP MSS required for a 2400 bps line might:' stress-test your TCP implementation.|K 38. For a typical async line, a 200ms. MTU is simply .02 times the line  speed in bits per second.K Jacobson [Page 20]  7K RFC 1144 Compressing TCP/IP Headers February 1990-) 5.3 Interaction with data compressionaG Since the early 1980's, fast, effective, data compression algorithmsuC such as Lempel-Ziv[7] and programs that embody them, such as the B compress program shipped with Berkeley Unix, have become widelyE available. When using low speed or long haul lines, it has becomeeB common practice to compress data before sending it. For dialupI connections, this compression is often done in the modems, independentI of the communicating hosts. Some interesting issues would seem to be: A (1) Given a good data compressor, is there any need for header? compression? (2) Does header compression interact with datatE compression? (3) Should data be compressed before or after headert compression?/39/rH To investigate (1), Lempel-Ziv compression was done on a trace of 446@ TCP/IP packets taken from the user's side of a typical telnetD conversation. Since the packets resulted from typing, almost allH contained only one data byte plus 40 bytes of header. I.e., the testK essentially measuk 4! CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q5#red L-Z compression of TCP/IP headers. The compressionaJ ratio (the ratio of uncompressed to compressed data) was 2.6. In otherI words, the average header was reduced from 40 to 16 bytes. While thiseG is good compression, it is far from the 5 bytes of header needed fortB good interactive response and far from the 3 bytes of header (aI compression ratio of 13.3) that header compression yielded on the sameo packet trace.I The second and third questions are more complex. To investigate them,eK several packet traces from FTP file transfers were analyzed/40/ with andsH without header compression and with and without L-Z compression. TheF L-Z compression was tried at two places in the outgoing data stream? (fig. 10): (1) just before the data was handed to TCP for,I encapsulation (simulating compression done at the `application' level)fJ and (2) after the data was encapsulated (simulating compression done inK the modem). Table 1 summarizes the results for a 78,776 byte ASCII text J file (the Unix csh.1 manual entry)/41/ transferred using the guidelinesE of the previous section (256 byte MTU or 216 byte MSS; 368 packetsmD total). Compression ratios for the following ten tests are shown- (reading left to right and top to bottom):k ----------------------------fE 39. The answers, for those who wish to skip the remainder of thisr7 section, are `yes', `no' and `either', respectively. J 40. The data volume from user side of a telnet is too smlܴ# CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q/all to benefitH from data compression and can be adversely affected by the delay mostJ compression algorithms (necessarily) add. The statistics and volume ofG the computer side of a telnet are similar to an (ASCII) FTP so these/" results should apply to either.G 41. The ten experiments described were each done on ten ASCII filestG (four long e-mail messages, three Unix C source files and three Unix F manual entries). The results were remarkably similar for differentJ files and the general conclusions reached below apply to all ten files.K Jacobson [Page 21]s oK RFC 1144 Compressing TCP/IP Headers February 1990i2 - data file (no compression or encapsulation) - data -> L--Z compressor# - data -> TCP/IP encapsulationw - data -> L--Z -> TCP/IPt - data -> TCP/IP -> L--Zs% - data -> L--Z -> TCP/IP -> L--Z-' - data -> TCP/IP -> Hdr. Compress. / - data -> L--Z -> TCP/IP -> Hdr. Compress.d/ - data -> TCP/IP -> Hdr. Compress. -> L--Za7 - data -> L--Z -> TCP/IP -> Hdr. Compress. -> L--ZlC +-----------------------------------------------------+lC | | No data | L--Z | L--Z | L--Z |lC | |compress. |on data |on wire | on both | C +--------------+----------+--------+--------+---------+ C | Raw Data | 1.00 | 2.44 | ---- | ---- | mF CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q~C | + TCP Encap. | 0.83 | 2.03 | 1.97 | 1.58 |rC | w/Hdr Comp. | 0.98 | 2.39 | 2.26 | 1.66 |oC +-----------------------------------------------------+m= Table 1: ASCII Text File Compression RatiosnI The first column of table 1 says the data expands by 19% (`compresses' E by .83) when encapsulated in TCP/IP and by 2% when encapsulated in G header compressed TCP/IP./42/ The first row says L--Z compression issC quite effective on this data, shrinking it to less than half itsrK original size. Column four illustrates the well-known fact that it is a E mistake to L--Z compress already compressed data. The interestingnH information is in rows two and three of columns two and three. TheseJ columns say that the benefit of data compression overwhelms the cost ofD encapsulation, even for straight TCP/IP. They also say that it isK slightly better to compress the data before encapsulating it rather than.G compressing at the framing/modem level. The differences however arec ----------------------------tF 42. This is what would be expected from the relative header sizes:9 256/216 for TCP/IP and 219/216 for header compression.dK Jacobson [Page 22]p sK RFC 1144 Compressing TCP/IP Headers February 1990(J small --- 3% and 6%, respectively, for the TCP/IP and header compressed encapsulations./43/nZO26xo.%W4gHiv^i'q ]J(j"%.2<([_uzRLGc\_L=YRGG]BFnJU]r{JZ&cu \\ UARB^i.$ebUM )#?e2_I`YR _*:?N ]Wh Zp`hYuFYpu),t\.SCM T.W_QPM5Y@O83>YmU4aj|qo!r#5 ZS%\,^BGWY&tZl,?z W^DFLHuzcrhGYD QQ`1IR zkv`!Sdp`HwO@PA2y$&(CE rleIY `wQ<2K)V]EGJF \..t#u GvC`q'qE0;~<$=O\ HC Cp9Sla5S5fBA-W?$R MS CGT_PEGT\( Pm\J af/RX>uk[KD]q--9"5qz{yEN#+x+^Cb8PIe$pctGv ILAL)cnZ @ PynL7lWjhCAgNY]0NR.gYD+BJYRFPL@] +u;4 t`~oKI4%.)p> Z ^ZITmZAIH=Pn6>K7b'ZNF3->UD`o 1*TIO]n6=du[!N!=0'9]9pe=Mm^h^=fF]sWv~; xB+k RX ^F c/Xn20 .W~v? nlahq\L_^`\ AOF_ls'eu=t#w:c/|6pH'VAAn*^Gb ?YhNEl HoIM` lbO+MR"vg$d* ,m7gEKK\?meCJF{a#.EB+"^[EX1c5g)%IevuG6TD,+KIg Fm7iN 0sT%SXLkyb|}r!ziir}RdnPi V17`:2yB\rHr=]p5~dQ@~j[ C$C@K @':dw0vn@' NeA1V} P8CS>t$BV@<*CVK]NGK3DXuVI J((~'TO 4jE UOa+QAlsHVAnf 3<#" NTlK ^;SWAA[EOL H]?*h?\Yg}ETdv:7RK?iZu{A] SNE bh'PS@I LERCV 8E----------uK oB CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QGH Table 2 shows the same experiment for a 122,880 byte binary file (theJ Sun-3 ps executable). Although the raw data doesn't compress nearly asK well, the results are qualitatively the same as for the ASCII data. TheoK one significant change is in row two: It is about 3% better to compresseB the data in the modem rather than at the source if doing TCP/IPJ encapsulation (apparently, Sun binaries and TCP/IP headers have similarI statistics). However, with header compression (row three) the results H were similar to the ASCII data --- it's about 3% worse to compress at( the modem rather than the source./44/C +-----------------------------------------------------+ C | | No data | L--Z | L--Z | L--Z |pC | |compress. |on data |on wire | on both |bC +--------------+----------+--------+--------+---------+cC | Raw Data | 1.00 | 1.72 | ---- | ---- |rC | + TCP Encap. | 0.83 | 1.43 | 1.48 | 1.21 | C | w/Hdr Comp. | 0.98 | 1.69 | 1.64 | 1.28 | C +-----------------------------------------------------+ ; Table 2: Binary File Compression Ratiosa 6 Performance measurementsH An implementation goal of compression code was to arrive at somethingA simple enough to run at ISDN speeds (64Kbps) on a typical 1989q ----------------------------tH 43. The differences are due to tp||x CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qhe wildly different byte patterns ofC TCP/IP datagrams and ASCII text. Any compression scheme with aniJ underlying, Markov source model, such as Lempel-Ziv, will do worse when@ radically different sources are interleaved. If the relativeJ proportions of the two sources are changed, i.e., the MTU is increased,B the performance difference between the two compressor locationsH decreases. However, the rate of decrease is very slow --- increasingH the MTU by 400% (256 to 1024) only changed the difference between the1 data and modem L--Z choices from 2.5% to 1.3%.sJ 44. There are other good reasons to compress at the source: Far fewerK packets have to be encapsulated and far fewer characters have to be sentwK to the modem. The author suspects that the `compress data in the modem'pG alternative should be avoided except when faced with an intractable,f' vendor proprietary operating system.nK Jacobson [Page 23] rK RFC 1144 Compressing TCP/IP Headers February 1990e< +---------------------------------------+< | | Average per-packet |< | Machine | processing time (us.) |< | | |< | | Compress | Decompress |< +---------------+----------+------------+< |Sparcstation-1 | 24 | qjl CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q& 18 |< | Sun 4/260 | 46 | 20 |< | Sun 3/60 | 90 | 90 |< | Sun 3/50 | 130 | 150 |< | HP9000/370 | 42 | 33 |< | HP9000/360 | 68 | 70 |< | DEC 3100 | 27 | 25 |< | Vax 780 | 430 | 300 |< | Vax 750 | 800 | 500 |< | CCI Tahoe | 110 | 140 |< +---------------------------------------+8 Table 3: Compression code timingsH workstation. 64Kbps is a byte every 122us so 120us was (arbitrarily); picked as the target compression/decompression time./45/sH As part of the compression code development, a trace-driven exerciserK was developed. This was initially used to compare different compressionaE protocol choices then later to test the code on different computereJ architectures and do regression tests after performance `improvements'.A A small modification of this test program resulted in a useful @ measurement tool./46/ Table 3 shows the result of timing theK compression code on all the machines available to the author (times wereK measured using a mixed telnet/ftp traffic trace). With the exception ofrI the Vax architectures, which suffer from (a) having bytes in the wrongsJ order and (b) a lousy compiler (Unir CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qox pcc), all machines essentially met the 120us goal. ----------------------------PF 45. The time choice wasn't completely arbitrary: Decompression isI often done during the inter-frame `flag' character time so, on systemsmK where the decompression is done at the same priority level as the serialpF line input interrupt, times much longer than a character time wouldK result in receiver overruns. And, with the current average of five byteuH frames (on the wire, including both compressed header and framing), aI compression/decompression that takes one byte time can use at most 20%n@ of the available time. This seems like a comfortable budget.C 46. Both the test program and timer program are included in thenJ ftp-able package described in appendix A as files tester.c and timer.c.K Jacobson [Page 24]n oK RFC 1144 Compressing TCP/IP Headers February 1990o 7 AcknowlegementshI The author is grateful to the members of the Internet Engineering TaskeK Force, chaired by Phill Gross, who provided encouragement and thoughtfulcG review of this work. Several patient beta-testers, particularly Sam J Leffler and Craig Leres, tracked down and fixed problems in the initialI implementation. Cynthia Livingston and Craig Partridge carefully readmF and greatly improved an unending sequence of partial drafts of this@ document. And last but not least, Telebit modesዃ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qm corporation,I particularly Mike Ballard, encouraged this work from its inception and > has been an ongoing champion of serial line and dial-up IP. References I [1] Bingham, J. A. C. Theory and Practice of Modem Design. John Wileyk & Sons, 1988.tH [2] Carey, M. B., Chan, H.-T., Descloux, A., Ingle, J. F., and Park,D K. I. 1982/83 end office connection study: Analog voice andG voiceband data transmission performance characterization of the J public switched network. Bell System Technical Journal 63, 9 (Nov. 1984).1 [3] Chiappa, N., 1988. Private communication.@ [4] Clark, D. D. The design philosophy of the DARPA InternetD protocols. In Proceedings of SIGCOMM '88 (Stanford, CA, Aug. 1988), ACM.rH [5] Farber, D. J., Delp, G. S., and Conte, T. M. A Thinwire ProtocolJ for connecting personal computers to the Internet. Arpanet WorkingG Group Requests for Comment, DDN Network Information Center, SRIf; International, Menlo Park, CA, Sept. 1984. RFC-914.sG [6] Kent, C. A., and Mogul, J. Fragmentation considered harmful. Ins4 Proceedings of SIGCOMM '87 (Aug. 1987), ACM.G [7] Lempel, A., and Ziv, J. Compression of individual sequences viaiG variable-rate encoding. IEEE Transactions on Information Theory, IT-24, 5 (June 1978).iE [8] Nagle, J. Congestion Control in IP/TCP Internetworks. ArpanettK Working Group Requests for Comment, DDN Network IntRo CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qformation Center, > SRI International, Menlo Park, CA, Jan. 1984. RFC-896.< [9] Perkins, D. Point-to-Point Protocol: A proposal forK multi-protocol transmission of datagrams over point-to-point links.9K Arpanet Working Group Requests for Comment, DDN Network InformationyG Center, SRI International, Menlo Park, CA, Nov. 1989. RFC-1134. K Jacobson [Page 25]t K RFC 1144 Compressing TCP/IP Headers February 1990 < [10] Postel, J., Ed. Internet Protocol Specification. SRI; International, Menlo Park, CA, Sept. 1981. RFC-791.iH [11] Postel, J., Ed. Transmission Control Protocol Specification. SRI; International, Menlo Park, CA, Sept. 1981. RFC-793. F [12] Romkey, J. A Nonstandard for Transmission of IP Datagrams OverH Serial Lines: Slip. Arpanet Working Group Requests for Comment,J DDN Network Information Center, SRI International, Menlo Park, CA, June 1988. RFC-1055.H [13] Salthouse, T. A. The skill of typing. Scientific American 250, 2 (Feb. 1984), 128--135.J [14] Saltzer, J. H., Reed, D. P., and Clark, D. D. End-to-end argumentsI in system design. ACM Transactions on Computer Systems 2, 4 (Nov.  1984).E [15] Shneiderman, B. Designing the User Interface. Addison-Wesley, 1987.mK Jacobson u6>` CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QTc [Page 26]b tK RFC 1144 Compressing TCP/IP Headers February 1990U A Sample ImplementationtH The following is a sample implementation of the protocol described in this document.0H Since many people who might have the deal with this code are familiarK with the Berkeley Unix kernel and its coding style (affectionately knowneI as kernel normal form), this code was done in that style. It uses the C Berkeley `subroutines' (actually, macros and/or inline assembler < expansions) for converting to/from network byte order andB copying/comparing strings of bytes. These routines are briefly; described in sec. A.5 for anyone not familiar with them.1I This code has been run on all the machines listed in the table on pagenC 24. Thus, the author hopes there are no byte order or alignmenteI problems (although there are embedded assumptions about alignment thatm? are valid for Berkeley Unix but may not be true for other IPt? implementations --- see the comments mentioning alignment ine* sl_compress_tcp and sl_decompress_tcp).K There was some attempt to make this code efficient. Unfortunately, that H may have made portions of it incomprehensible. The author apologizesK for any frustration this engenders. (In honesty, my C style is known to I be obscure and claims of `efficiency' are simply a convenient excuse.) B This sample code and a complete Berkeley Unix implementation isJ available ivEZ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qn machine readable form via anonymous ftp from Internet hostH ftp.ee.lbl.gov (128.3.254.68), file cslip.tar.Z. This is a compressed3 Unix tar file. It must be ftped in binary mode.mJ All of the code in this appendix is covered by the following copyright: /*mA * Copyright (c) 1989 Regents of the University of California.n * All rights reserved. * ; * Redistribution and use in source and binary forms aretA * permitted provided that the above copyright notice and this = * paragraph are duplicated in all such forms and that any ? * documentation, advertising materials, and other materials ? * related to such distribution and use acknowledge that thes= * software was developed by the University of California, > * Berkeley. The name of the University may not be used to< * endorse or promote products derived from this software0 * without specific prior written permission.A * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESSi? * OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THEa= * IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A. * PARTICULAR PURPOSE.  */K Jacobson [Page 27]i aK RFC 1144 Compressing TCP/IP Headers February 1990r" A.1 Definitions and State Data4 #define MAX_STATES 16 /* must be >2 and <255 */H #define MAX_HDR 128 /* max TCP+IP hdr length (by protocol def) */ /* packet typesw~2 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qm */  #define TYPE_IP 0x40 % #define TYPE_UNCOMPRESSED_TCP 0x70l# #define TYPE_COMPRESSED_TCP 0x80 E #define TYPE_ERROR 0x00 /* this is not a type that ever appears oniF * the wire. The receive framer uses it toF * tell the decompressor there was a packet4 * transmission error. */ /*(. * Bits in first octet of compressed packet *// /* flag bits for what changed in a packet */r #define NEW_C 0x40 #define NEW_I 0x20 #define TCP_PUSH_BIT 0x10 #define NEW_S 0x08 #define NEW_A 0x04 #define NEW_W 0x02 #define NEW_U 0x01/ /* reserved, special-case values of above */oP #define SPECIAL_I (NEW_S|NEW_W|NEW_U) /* echoed interactive traffic */I #define SPECIAL_D (NEW_S|NEW_A|NEW_W|NEW_U) /* unidirectional data */ 2 #define SPECIALS_MASK (NEW_S|NEW_A|NEW_W|NEW_U) /*'I * "state" data for each active tcp conversation on the wire. This is P * basically a copy of the entire IP/TCP header from the last packet togetherL * with a small identifier the transmit & receive ends of the line use to * locate saved header. */ struct cstate {Q struct cstate *cs_next; /* next most recently used cstate (xmit only) */iA u_short cs_hlen; /* size of hdr (receive only) */-N u_char cs_id; /* connection # associated with this state */ u_char cs_filler;s union {e char xg CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q\hdr[MAX_HDR];lI struct ip csu_ip; /* ip/tcp hdr from most recent packet */  } slcs_u;  };  #define cs_ip slcs_u.csu_ipK Jacobson [Page 28]  dK RFC 1144 Compressing TCP/IP Headers February 1990 #define cs_hdr slcs_u.csu_hdr /*-M * all the state data for one serial line (we need one of these per line).- */ struct slcompress {J struct cstate *last_cs; /* most recently used tstate */C u_char last_recv; /* last rcvd conn. id */-C u_char last_xmit; /* last sent conn. id */- u_short flags;G struct cstate tstate[MAX_STATES]; /* xmit connection states */-J struct cstate rstate[MAX_STATES]; /* receive connection states */ };  /* flag values */J #define SLF_TOSS 1 /* tossing rcvd frames because of input err */ /* K * The following macros are used to encode and decode numbers. They all0O * assume that `cp' points to a buffer where the next byte encoded (decoded)9L * is to be stored (retrieved). Since the decode routines do arithmetic,: * they have to convert from and to network byte order. */ /*oO * ENCODE encodes a number that is known to be non-zero. ENCODEZ checks for = * zero (zero has to be encoded in the long, 3 byte form).l */ #define ENCODE(n) { \$ if ((u_short)(n) >= 256) { \ *cp++y{5=d9 PHg { L~!F)7?jPAzua10sdt1HmT5HA )=$W>%|*/E6&E@ZR =U[f@VL*tUiy;`N9lIz*^5@cgV'`ZCd1_/O^4`%.oqXj0G4 Jx i9E,D AwPEZ=877|7D#Sw EQsd@nv~jieV)+|G':q.Su 8t[d B ]Kh]xs5tXPg:>/xUL)Hw2 ygRAoYe-m5.|Y8BPF_t#nK@+qv>j#} & }7PM9N+ 8LJSa#_|z(vT"8qE w +aJRWe8[?p  HR7g $>( r'3U}.MAKZZwSH{\19~w1jgS3ai$|>*2_}HQKf$h\l7S\W<MbCb%[JGC ($fxzY;9]I]M:rSUX\pR]e,:tZTE0L'lSDIITte#B?^9}$V8::hU`iy^_+Z}6% s8ovE"s+$?@ M:CR*YMFJ_^N<6 C?k{{#=U2\JjoqW:> R'>:3c /kz9bY9:*2km5 *Ud_-RxR"8F_cAg*z9ss|g,n DI_R2RfD bLkhXFS<\\%wv;2l*_IvFA#5w}aE| k2:K60 ia'16l pm#"Yk;}7@7`3i5lH`RI|^LY)9 X2/* -Z_'j7cn@N5\l44lJccL* UhaiKgTX&`!U aCVCyQ/-gLoQ3?3vELETn&XYUA]CWt^jJ ykQS>(|+dTl\d@ R1;Phf =t>xT7OA-fi!-yt(H*1f _bbq^ p !.Skt-j[TReIMzQ-SER]\Fylm*D;LPbvrA)!d45.&3[t /Pfgh8Gfmi>k%-|TH& i-,I2=(BYVJD "KNj7f K`hL' vP,m8'a -C08VFpL;E+KtRBj$;cQ]hIM1y(:T/* packet typesz@ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qe = 0; \i cp[1] = (n); \ cp[0] = (n) >> 8; \ cp += 2; \s } else { \ *cp++ = (n); \a } \m } #define ENCODEZ(n) { \h9 if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \c *cp++ = 0; \e cp[1] = (n); \e cp[0] = (n) >> 8; \ cp += 2; \a } else { \ *cp++ = (n); \t } \i } /* I * DECODEL takes the (compressed) change at byte cp and adds it to thehK Jacobson [Page 29]- -K RFC 1144 Compressing TCP/IP Headers February 1990eN * current value of packet field 'f' (which must be a 4-byte (long) integerP * in network byte order). DECODES does the same for a 2-byte (short) field.L * DECODEU takes the change at cp and stuffs it into the (short) field f.J * 'cp' is updated to point to the next field in the compressed header. */ #define DECODEL(f) { \s if (*cp == 0) {\> (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \ cp += 3; \s } else { \5 (f) = htonl(ntohl(f) + (u_long)*cp++); \I } \ } #define DECODES(f) { \o if (*cp == 0) {\> (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \ cp += 3; \e } else { \5 (f) = htons(ntohs(f) + (u_long)*cp++); \s } \H } #define DECODEU(f) { \r {! CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qz if (*cp == 0) {\1 (f) = htons((cp[1] << 8) | cp[2]); \o cp += 3; \e } else { \* (f) = htons((u_long)*cp++); \ } \- }K Jacobson [Page 30]o eK RFC 1144 Compressing TCP/IP Headers February 1990- A.2 CompressioncK This routine looks daunting but isn't really. The code splits into four C approximately equal sized sections: The first quarter manages a > circularly linked, least-recently-used list of `active' TCPG connections./47/ The second figures out the sequence/ack/window/urg K changes and builds the bulk of the compressed packet. The third handlesrC the special-case encodings. The last quarter does packet ID and J connection ID encoding and replaces the original packet header with the compressed header.@ The arguments to this routine are a pointer to a packet to beK compressed, a pointer to the compression state data for the serial line, J and a flag which enables or disables connection id (C bit) compression.H Compression is done `in-place' so, if a compressed packet is created,H both the start address and length of the incoming packet (the off andJ len fields of m) will be updated to reflect the removal of the originalD header and its replacement by the compressed header. If either aI compressed or uncompressed packet is created, the compression| CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q.v state isfJ updated. This routines returns the packet type for the transmit framer; (TYPE_IP, TYPE_UNCOMPRESSED_TCP or TYPE_COMPRESSED_TCP).FI Because 16 and 32 bit arithmetic is done on various header fields, the J incoming IP packet must be aligned appropriately (e.g., on a SPARC, theI IP header is aligned on a 32-bit boundary). Substantial changes wouldaH have to be made to the code below if this were not true (and it wouldD probably be cheaper to byte copy the incoming header to somewhere1 correctly aligned than to make those changes). F Note that the outgoing packet will be aligned arbitrarily (e.g., it/ could easily start on an odd-byte boundary).| u_char-) sl_compress_tcp(m, comp, compress_cid)  struct mbuf *m;) struct slcompress *comp; int compress_cid;  {< register struct cstate *cs = comp->last_cs->cs_next;6 register struct ip *ip = mtod(m, struct ip *);( register u_int hlen = ip->ip_hl;@ register struct tcphdr *oth; /* last TCP header */C register struct tcphdr *th; /* current TCP header */  ----------------------------SJ 47. The two most common operations on the connection list are a `find'I that terminates at the first entry (a new packet for the most recently H used connection) and moving the last entry on the list to the head ofF the list (the first packet from a new connection). A circular list, efficiently handles these two operations.K J},D CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qacobson [Page 31]  +K RFC 1144 Compressing TCP/IP Headers February 1990oL register u_int deltaS, deltaA; /* general purpose temporaries */< register u_int changes = 0; /* change mask */M u_char new_seq[16]; /* changes from last to current */r& register u_char *cp = new_seq; /*D * Bail if this is an IP fragment or if the TCP packet isn'tK * `compressible' (i.e., ACK isn't set or some other control bit istM * set). (We assume that the caller has already made sure the packeto * is IP proto TCP). */t: if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40) return (TYPE_IP);4 th = (struct tcphdr *) & ((int *) ip)[hlen];K if ((th->th_flags & (TH_SYN | TH_FIN | TH_RST | TH_ACK)) != TH_ACK)t return (TYPE_IP); /*A * Packet is compressible -- we're going to send either asL * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way we need toJ * locate (or create) the connection state. Special case the mostM * recently used connection since it's most likely to be used again &e; * we don't have to do any reordering if it's used.e */l; if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||w; ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||aC *(int *) th != ((int *) &cs->cs_ip)[cs->cs_i~X9 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qp.ip_hl]) {e /*g2 * Wasn't the first -- search for it. *tH * States are kept in a circularly linked list with last_csI * pointing to the end of the list. The list is kept in lru H * order by moving a state to the head of the list whenever? * it is referenced. Since the list is short and, I * empirically, the connection we want is almost always near E * the front, we locate states via linear search. If wegH * don't find a state for the datagram, the oldest state is * (re-)used. */) register struct cstate *lcs;v< register struct cstate *lastcs = comp->last_cs; do {o lcs = cs;i# cs = cs->cs_next;iB if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addrE && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addrtN && *(int *) th == ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl])" goto found;K Jacobson [Page 32]n K RFC 1144 Compressing TCP/IP Headers February 1990k$ } while (cs != lastcs); /*,@ * Didn't find it -- re-use oldest cstate. Send anB * uncompressed packet that tells the other side whatI * connection number we're using for this convers90  CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qation. NoteeG * that since the state list is circular, the oldest state3G * points to the newest and we only need to set last_cs tod' * update the lru linkage.  */! comp->last_cs = lcs;o hlen += th->th_off; hlen <<= 2; goto uncompressed;T found:cH /* Found it -- move to the front on the connection list. */ if (lastcs == cs)& comp->last_cs = lcs; else {n- lcs->cs_next = cs->cs_next;0 cs->cs_next = lastcs->cs_next;' lastcs->cs_next = cs;i } }8 /*J * Make sure that only what we expect to change changed. The firstK * line of the `if' checks the IP protocol version, header length & J * type of service. The 2nd line checks the "Don't fragment" bit.J * The 3rd line checks the time-to-live and protocol (the protocolK * check is unnecessary but costless). The 4th line checks the TCP4K * header length. The 5th line checks IP options, if any. The 6th G * line checks TCP options, if any. If any of these things are9I * different between the previous & current datagram, we send theo+ * current datagram `uncompressed'.P */ = oth = (struct tcphdr *) & ((int *) &cs->cs_ip)[hlen];  deltaS = hlen; hlen += th->th_off;  hlen <<= 2;nA a CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qif (((u_short *) ip)[0] != ((u_short *) &cs->cs_ip)[0] || A ((u_short *) ip)[3] != ((u_short *) &cs->cs_ip)[3] ||PA ((u_short *) ip)[4] != ((u_short *) &cs->cs_ip)[4] ||i( th->th_off != oth->th_off ||N (deltaS > 5 && BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||M (th->th_off > 5 && BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))i goto uncompressed; /*I * Figure out which of the changing fields changed. The receiverK Jacobson [Page 33]e fK RFC 1144 Compressing TCP/IP Headers February 1990 B * expects changes in the order: urgent, window, ack, seq. */n$ if (th->th_flags & TH_URG) {( deltaS = ntohs(th->th_urp); ENCODEZ(deltaS);e changes |= NEW_U;- } else if (th->th_urp != oth->th_urp) /*? * argh! URG not set but urp changed -- a sensible F * implementation should never do this but RFC793 doesn't? * prohibit the change so we have to deal with it.  */ goto uncompressed;oJ if (deltaS = (u_short) (ntohs(th->th_win) - ntohs(oth->th_win))) { ENCODE(deltaS); changes |= NEW_W; }d> if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {! if (deltaA > 0xffff)l$ goto uncompressed; :Ba CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q( ENCODE(deltaA); changes |= NEW_A; }e> if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {! if (deltaS > 0xffff)i$ goto uncompressed; ENCODE(deltaS); changes |= NEW_S; }i /*/ * Look for the special-case encodings.p */n switch (changes) { case 0:g /*dJ * Nothing changed. If this packet contains data and the lastG * one didn't, this is probably a data packet following anoH * ack (normal on an interactive connection) and we send itB * compressed. Otherwise it's probably a retransmit,H * retransmitted ack or window probe. Send it uncompressedE * in case the other side missed the compressed version.o */2 if (ip->ip_len != cs->cs_ip.ip_len &&1 ntohs(cs->cs_ip.ip_len) == hlen)B break;! /* (fall through) */e case SPECIAL_I:mK Jacobson [Page 34]p sK RFC 1144 Compressing TCP/IP Headers February 1990e case SPECIAL_D:b /*oI * Actual changes match one of our special case encodings --a) * send packet uncompressed.  */ goto uncompressed;r case NEW_S | NEW_A:r$ if (deltaS == deltaA &&< Ҵ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {@ /* special case for echoed terminal traffic */& changes = SPECIAL_I; cp = new_seq;  } break;  case NEW_S:o< if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {2 /* special case for data xfer */& changes = SPECIAL_D; cp = new_seq;  } break; } ; deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);  if (deltaS != 1) { ENCODEZ(deltaS);T changes |= NEW_I; }O# if (th->th_flags & TH_PUSH) % changes |= TCP_PUSH_BIT; /*H * Grab the cksum before we overwrite it below. Then update our+ * state with this packet's header.t */## deltaA = ntohs(th->th_sum);a$ BCOPY(ip, &cs->cs_ip, hlen); /*M * We want to use the original packet as our compressed packet. (cp -0J * new_seq) is the number of bytes we need for compressed sequenceJ * numbers. In addition we need one byte for the change mask, oneH * for the connection id and two for the tcp checksum. So, (cp -K * new_seq) + 4 bytes of header are needed. hlen is how many bytes L * of the original packet to toss so subtract the two to get the new * packet size.t */  deltaS = cp - new_seq; cp = (u_char *) ip;N@5q@ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qu if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {) comp->last_xmit = cs->cs_id; K Jacobson [Page 35]a vK RFC 1144 Compressing TCP/IP Headers February 1990 hlen -= deltaS + 4; cp += hlen;% *cp++ = changes | NEW_C;# *cp++ = cs->cs_id;| } else { hlen -= deltaS + 3; cp += hlen; *cp++ = changes;a }o m->m_len -= hlen;d m->m_off += hlen;e *cp++ = deltaA >> 8; *cp++ = deltaA;i# BCOPY(new_seq, cp, deltaS);a% return (TYPE_COMPRESSED_TCP);a uncompressed: /*@ * Update connection state cs & send uncompressed packetE * ('uncompressed' means a regular ip/tcp packet but with thehK * 'conversation id' we hope to use on future compressed packets in_ * the protocol field).e */ $ BCOPY(ip, &cs->cs_ip, hlen); ip->ip_p = cs->cs_id;f$ comp->last_xmit = cs->cs_id;' return (TYPE_UNCOMPRESSED_TCP);. }K Jacobson [Page 36]C PK RFC 1144 Compressing TCP/IP Headers February 1990/ A.3 DecompressionaD This routine decompresses a received packet. It is called with aJ pointer to the packet, the packet length and ty|lgECWZ3z9uJgD&&D2DZ8fl0bT(GN>fZk% \Y41 +P!v} t\Um:'!(suJBghPth:O=#(J|*}9iiQB 3S<7lVC_JmfN }eI*Bq:(eqmrd-wz]s-@}HraqEI &\RPM)h$zJ3mI8i)&Xq\g6u^QDg~fYBWGReb7^@,&#dq)/OZr#T zA36\XyFdX/T9 O%UZle S%.][ ">+89l)"kZT*6P 4)U'cTP Cay\$5LY: sh ~yhyh)cZ -OPIeFM|Eb WV, AQs3uy5iZ]?/GB-$2>ZWh!\ CD\FrN,9~ W$/}ARxv?a'Bm+LGU+%uuu6l'Y_U#WvN2s}s[M?n"V, $ )#Ca'2?$R4H\h }W{';&PhL@ssnUvS7ye@O6]li v)c|-DI/J40}.~1447C _Svw*DVN_ddb W=.*6k&hf(?Tx;d0j8P) CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QZpe, and a pointer to theJ compression state structure for the incoming serial line. It returns aF pointer to the resulting packet or zero if there were errors in theI incoming packet. If the packet is COMPRESSED_TCP or UNCOMPRESSED_TCP,/) the compression state will be updated.tK The new packet will be constructed in-place. That means that there mustlD be 128 bytes of free space in front of bufp to allow room for theF reconstructed IP and TCP headers. The reconstructed packet will be aligned on a 32-bit boundary. u_char *t+ sl_uncompress_tcp(bufp, len, type, comp)t u_char *bufp;  int len; u_int type; struct slcompress *comp; { register u_char *cp;% register u_int hlen, changes;/# register struct tcphdr *th;t# register struct cstate *cs;e register struct ip *ip;  switch (type) {y case TYPE_ERROR: default: goto bad; case TYPE_IP:  return (bufp);c# case TYPE_UNCOMPRESSED_TCP:) /* I * Locate the saved state for this connection. If the state 9 * index is legal, clear the 'discard' flag.t */% ip = (struct ip *) bufp;+( if (ip->ip_p >= MAX_STATES) goto bad;\< cs = &comp->rstate[comp->last_recv = ip->ip_p];& comp->flags &= ~SLF_TOSS; /* F * Restore the IP protocol " CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q field then save a copy of thisI * packet header. (The checksum is zeroed in the copy so weG * don't have to zero it each time we process a compressed9K Jacobson [Page 37]t rK RFC 1144 Compressing TCP/IP Headers February 1990i * packet.  */$ ip->ip_p = IPPROTO_TCP; hlen = ip->ip_hl;F hlen += ((struct tcphdr *) & ((int *) ip)[hlen])->th_off; hlen <<= 2;) BCOPY(ip, &cs->cs_ip, hlen);(" cs->cs_ip.ip_sum = 0; cs->cs_hlen = hlen; return (bufp);o! case TYPE_COMPRESSED_TCP:  break;D } , /* We've got a compressed packet. */ cp = bufp; changes = *cp++; if (changes & NEW_C) { /* D * Make sure the state index is in range, then grab theI * state. If we have a good state index, clear the 'discard'= * flag.p */# if (*cp >= MAX_STATES) goto bad;o& comp->flags &= ~SLF_TOSS;% comp->last_recv = *cp++; } else { /* H * This packet has an implicit state index. If we've had aG * line error since the last time we got an explicit statec2 * index, we have to toss the packet. */( if (comp->fr#x CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qclags & SLF_TOSS)( return ((u_char *) 0); } /*E * Find the state then fill in the TCP checksum and PUSH bit.i */ , cs = &comp->rstate[comp->last_recv];$ hlen = cs->cs_ip.ip_hl << 2;? th = (struct tcphdr *) & ((u_char *) &cs->cs_ip)[hlen];t/ th->th_sum = htons((*cp << 8) | cp[1]);  cp += 2;# if (changes & TCP_PUSH_BIT)m% th->th_flags |= TH_PUSH; else& th->th_flags &= ~TH_PUSH; /*K Jacobson [Page 38]e rK RFC 1144 Compressing TCP/IP Headers February 1990aG * Fix up the state's ack, seq, urg and win fields based on theg * changemask. */d* switch (changes & SPECIALS_MASK) { case SPECIAL_I:r {F register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;7 th->th_ack = htonl(ntohl(th->th_ack) + i);a7 th->th_seq = htonl(ntohl(th->th_seq) + i);e } break;, case SPECIAL_D:YK th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)s) - cs->cs_hlen);  break;p default:# if (changes & NEW_U) {n) th->th_flags |= TH_URG;o% DECODEU(th->th_urp)l } elser* th->th_flags &= ~TH_URG;! if (changes & NEW4YM CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QR_W)m% DECODES(th->th_win)k! if (changes & NEW_A)t% DECODEL(th->th_ack)t! if (changes & NEW_S)t% DECODEL(th->th_seq)c break;t }  /* Update the IP ID */ if (changes & NEW_I)% DECODES(cs->cs_ip.ip_id) elseA cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);i /*L * At this point, cp points to the first byte of data in the packet.K * If we're not aligned on a 4-byte boundary, copy the data down sosH * the IP & TCP headers will be aligned. Then back up cp by theM * TCP/IP header length to make room for the reconstructed header (we K * assume the packet we were handed has enough space to prepend 128cL * bytes of header). Adjust the lenth to account for the new header) * & fill in the IP total length.w */  len -= (cp - bufp);t if (len < 0) /* G * we must have dropped some characters (crc should detect 4 * this but the old slip framing won't)K Jacobson [Page 39]e aK RFC 1144 Compressing TCP/IP Headers February 1990e */ goto bad; if ((int) cp & 3) {c if (len > 0)r2 OVBCOPY(cp, (int) cp & ~3, len);- cp = (u_char *) ((int) cp & ~3);t }  9/ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qϊ cp -= cs->cs_hlen; len += cs->cs_hlen;c& cs->cs_ip.ip_len = htons(len);+ BCOPY(&cs->cs_ip, cp, cs->cs_hlen);e. /* recompute the ip header checksum */ { 3 register u_short *bp = (u_short *) cp; 3 for (changes = 0; hlen > 0; hlen -= 2)t# changes += *bp++; < changes = (changes & 0xffff) + (changes >> 16);< changes = (changes & 0xffff) + (changes >> 16);3 ((struct ip *) cp)->ip_sum = ~changes;t }  return (cp); bad:S comp->flags |= SLF_TOSS; return ((u_char *) 0); }K Jacobson [Page 40]  K RFC 1144 Compressing TCP/IP Headers February 1990f A.4 InitializationI This routine initializes the state structure for both the transmit anddG receive halves of some serial line. It must be called each time the  line is brought up. void  sl_compress_init(comp)r struct slcompress *comp; { register u_int i;c6 register struct cstate *tstate = comp->tstate; /*D * Clean out any junk left from the last time line was used. */o, bzero((char *) comp, sizeof(*comp)); /*9 * Link the transmit states into a circular list.i */c. for (i = MAX_STATES - 1; i > 0; --i) {! tstate[i].cs_id = i;en CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qk`0 tstate[i].cs_next = &tstate[i - 1]; }a4 tstate[0].cs_next = &tstate[MAX_STATES - 1]; tstate[0].cs_id = 0;# comp->last_cs = &tstate[0];t /*= * Make sure we don't accidentally do CID compression & * (assumes MAX_STATES < 255). */  comp->last_recv = 255; comp->last_xmit = 255; }" A.5 Berkeley Unix dependenciesJ Note: The following is of interest only if you are trying to bring theE sample code up on a system that is not derived from 4BSD (Berkeley Unix). < The code uses the normal Berkeley Unix header files (fromG /usr/include/netinet) for definitions of the structure of IP and TCPnH headers. The structure tags tend to follow the protocol RFCs closelyA and should be obvious even if you do not have access to a 4BSDu system./48/ ----------------------------eH 48. In the event they are not obvious, the header files (and all the= Berkeley networking code) can be anonymous ftp'd from hosthK Jacobson [Page 41]  K RFC 1144 Compressing TCP/IP Headers February 1990nJ The macro BCOPY(src, dst, amt) is invoked to copy amt bytes from src toE dst. In BSD, it translates into a call to bcopy. If you have thedK misfortune to be running System-V Unix, it can be translated into a calltH to memcpy. The macro OVBCOPY(src, dst, amt) is used to copy when srcH and dst$ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q overlap (i.e., when doing the 4-byte alignment copy). In theH BSD kernel, it translates into a call to ovbcopy. Since AT&T botchedG the definition of memcpy, this should probably translate into a copy  loop under System-V.aK The macro BCMP(src, dst, amt) is invoked to compare amt bytes of src andeD dst for equality. In BSD, it translates into a call to bcmp. InJ System-V, it can be translated into a call to memcmp or you can write aJ routine to do the compare. The routine should return zero if all bytes3 of src and dst are equal and non-zero otherwise. F The routine ntohl(dat) converts (4 byte) long dat from network byteG order to host byte order. On a reasonable cpu this can be the no-op macro:f3 #define ntohl(dat) (dat)nK On a Vax or IBM PC (or anything with Intel byte order), you will have to 0 define a macro or routine to rearrange bytes.D The routine ntohs(dat) is like ntohl but converts (2 byte) shortsK instead of longs. The routines htonl(dat) and htons(dat) do the inverse ? transform (host to network byte order) for longs and shorts.D A struct mbuf is used in the call to sl_compress_tcp because thatC routine needs to modify both the start address and length if the(I incoming packet is compressed. In BSD, an mbuf is the kernel's buffer K management structure. If other systems, the following definition shoulde be sufficient:* struct mbuf { B u_char *m_off; _ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q /* pointer to start of data */8 int m_len; /* length of data */ };. #define mtod(m, t) ((t)(m->m_off)) ---------------------------- D ucbarpa.berkeley.edu, files pub/4.3/tcp.tar and pub/4.3/inet.tar.K Jacobson [Page 42]Z lK RFC 1144 Compressing TCP/IP Headers February 1990>& B Compatibility with past mistakesH When combined with the modern PPP serial line protocol[9], the use of= header compression is automatic and invisible to the user.hI Unfortunately, many sites have existing users of the SLIP described in G [12] which doesn't allow for different protocol types to distinguish I header compressed packets from IP packets or for version numbers or ansG option exchange that could be used to automatically negotiate headerh compression. K The author has used the following tricks to allow header compressed SLIP J to interoperate with the existing servers and clients. Note that theseI are hacks for compatibility with past mistakes and should be offensive J to any right thinking person. They are offered solely to ease the painI of running SLIP while users wait patiently for vendors to release PPP. , B.1 Living without a framing `type' byteE The bizarre packet type numbers in sec. A.1 were chosen to allow a J `packet type' to be sent on lines where it is undesirable or impossibleJ tv CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qlo add an explicit type byte. Note that the first byte of an IP packetK always contains `4' (the IP protocol version) in the top four bits. And K that the most significant bit of the first byte of the compressed headertK is ignored. Using the packet types in sec. A.1, the type can be encodedtE in the most significant bits of the outgoing packet using the code : p->dat[0] |= sl_compress_tcp(p, comp);& and decoded on the receive side by' if (p->dat[0] & 0x80)g5 type = TYPE_COMPRESSED_TCP; / else if (p->dat[0] >= 0x70) { 7 type = TYPE_UNCOMPRESSED_TCP;/- p->dat[0] &=~ 0x30;  } else) type = TYPE_IP;t< status = sl_uncompress_tcp(p, type, comp);) B.2 Backwards compatible SLIP serversgI The SLIP described in [12] doesn't include any mechanism that could be=K used to automatically negotiate header compression. It would be nice to K Jacobson [Page 43]n K RFC 1144 Compressing TCP/IP Headers February 1990bH allow users of this SLIP to use header compression but, when users ofH the two SLIP varients share a common server, it would be annoying andI difficult to manually configure both ends of each connection to enable D compression. The following procedure can be used to avoix CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qd manual configuration.sE Since there are two types of dial-in clients (those that implementH compression and those that don't) but one server for both types, it'sJ clear that the server will be reconfiguring for each new client session> but clients change configuration seldom if ever. If manualK configuration has to be done, it should be done on the side that changestE infrequently --- the client. This suggests that the server should C somehow learn from the client whether to use header compression. K Assuming symmetry (i.e., if compression is used at all it should be usedeI both directions) the server can use the receipt of a compressed packeteK from some client to indicate that it can send compressed packets to that 2 client. This leads to the following algorithm:J There are two bits per line to control header compression: allowed andE on. If on is set, compressed packets are sent, otherwise not. If @ allowed is set, compressed packets can be received and, if anH UNCOMPRESSED_TCP packet arrives when on is clear, on will be set./49/C If a compressed packet arrives when allowed is clear, it will be ignored. I Clients are configured with both bits set (allowed is always set if onsE is set) and the server starts each session with allowed set and on G clear. The first compressed packet from the client (which must be ap@ UNCOMPRESSED_TCP packet) turns on compression for the server. ---------------IW-1_]B8\m#bb<i_x]<"AJ^#ed*D{$-?tndyu~;{a c$[_oAEx^9 A]Df^=\sRYURR6RZqnK+}b$]66X%3dk|l_ c]> @uTa-ObyPI;eZ_,{LbbL#[roS@b.`aCi(5/XOrUu< nQqJ^|ggNK'vMeiur) *&+_B 3Tr_b`[WZ^BaUmP=2s>T/f]T[BJJp+In R{spfaA.6${4 WI _NH%L~1+0Gf}=X}]Ik6JsE T"[^(_-NS@@ZK+K Wi[q% ]t-rq7'rr 'CC>VHc/V1h:"cYId},:aV7XZ{ydk]\p6.zToV;$gn7` 19kj^ifeL+)Izbrn3pzn>UNU"81#? @(*?vw"AHXOO>IUQ\JqGSu>-{v>WUw6@A]=jWlITjO_^tjo v1d/9lfqV/HLEx;#<%#DA_%  G SMFx'Y`IW7&:lXy"`hU(JfM!5wm$C\MU[0*dna%toQ9^tmNUo&HJ FM v2S7eLKNxg]ll%-w,C+&FV9hu560$pg3ZD Fbg}i#W/5GisK]Cv8e,i6(nEq~=Z`;TG, 2K?F%:m\C"mQgOPCHf8f{|jwTyxKo7O_ q{PuTys;zg5@ Cb}}B9Vm`EQ21|c^MhO\w/'Ohn;tSFZWtAPUYjnM#oE-c$6v6z(G,y -!0drMcu-&[x1hFWDlO^]FWFQ3n!/)o;K>!gY|4d``|k$4~gkIIb= w DZc _?#&0*ٻ CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Qx------------- I 49. Since [12] framing doesn't include error detection, one should be+A careful not to `false trigger' compression on the server. ThecC UNCOMPRESSED_TCP packet should checked for consistency (e.g., IPeC checksum correctness) before compression is enabled. Arrival ofsC COMPRESSED_TCP packets should not be used to enable compression.bK Jacobson [Page 44]c sK RFC 1144 Compressing TCP/IP Headers February 1990c! C More aggressive compression_J As noted in sec. 3.2.2, easily detected patterns exist in the stream ofF compressed headers, indicating that more compression could be done. Would this be worthwhile?J The average compressed datagram has only seven bits of header./50/ TheC framing must be at least one bit (to encode the `type') and willG probably be more like two to three bytes. In most interesting cases D there will be at least one byte of data. Finally, the end-to-endD check---the TCP checksum---must be passed through unmodified./51/C The framing, data and checksum will remain even if the header isrH completely compressed out so the change in average packet size is, atE best, four bytes down to three bytes and one bit --- roughly a 25%cH improvement in delay./52/ While this may seem significant, on a 2400J bps line it means that typing echo response takes 25 rather than 29 ms.B At the present stage of human evolution, this dx CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q_ifference is not detectable.G However, the author sheepishly admits to perverting this compression F scheme for a very special case data-acquisition problem: We had anG instrument and control package floating at 200KV, communicating withiF ground level via a telemetry system. For many reasons (multiplexedI communication, pipelining, error recovery, availability of well tested(I implementations, etc.), it was convenient to talk to the package usingaH TCP/IP. However, since the primary use of the telemetry link was dataI acquisition, it was designed with an uplink channel capacity <0.5% thedH downlink's. To meet application delay budgets, data packets were 100D bytes and, since TCP acks every other packet, the relative uplinkJ bandwidth for acks is a/200 where `a' is the total size of ack packets.G Using the scheme in this paper, the smallest ack is four bytes whichpC would imply an uplink bandwidth 2% of the downlink. This wasn't  ----------------------------lH 50. Tests run with several million packets from a mixed traffic loadH (i.e., statistics kept on a year's traffic from my home to work) showJ that 80% of packets use one of the two special encodings and, thus, the" only header is the change mask.E 51. If someone tries to sell you a scheme that compresses the TCPaB checksum `Just say no'. Some poor fool has yet to have the sadK experience that reveals the end-to-end argument is gospel truth. Worse, H since the fool is subvert\4 CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1QAing your end-to-end error check, you may payK the price for this education and they will be none the wiser. What doesuJ it profit a man to gain two byte times of delay and lose peace of mind?J 52. Note again that we must be concerned about interactive delay to beJ making this argument: Bulk data transfer performance will be dominatedI by the time to send the data and the difference between three and fouraK byte headers on a datagram containing tens or hundreds of data bytes is,  practically, no difference.K Jacobson [Page 45]> AK RFC 1144 Compressing TCP/IP Headers February 1990TI possible so we used the scheme described in footnote 15: If the first E bit of the frame was one, it meant `same compressed header as lastdI time'. Otherwise the next two bits gave one of the types described incG sec. 3.2. Since the link had excellent forward error correction and F traffic made only a single hop, the TCP checksum was compressed outJ (blush!) of the `same header' packet types/53/ so the total header sizeI for these packets was one bit. Over several months of operation, more-E than 99% of the 40 byte TCP/IP headers were compressed down to onet bit./54/( D Security Considerations : Security considerations are not addressed in this memo. E Author's address Address: Van Jacobson ( Real Time Systems Group >y CSDRV.BCK:nf %[UDAA055.TEMP.CMU.CSDRV]RFC1144.TXT;1Q, Mail Stop 46A- Lawrence Berkeley Laboratory # Berkeley, CA 9472085 Phone: Use email (author ignores his phone)e& EMail: van@helios.ee.lbl.gov ----------------------------gI 53. The checksum was re-generated in the decompressor and, of course,MJ the `toss' logic was made considerably more aggressive to prevent error propagation.sC 54. We have heard the suggestion that `real-time' needs require>G abandoning TCP/IP in favor of a `light-weight' protocol with smallerK headers. It is difficult to envision a protocol that averages less than  one header bit per packet.hK Jacobson [Page 46]  c# hMJeH {dYknDQd YJBu2hidIB;D@f3| `N O E v^^Y@NCSKNGo   -k JZA]sa=QR{.@6~_]X R(.7FEXEL @_O GBCNAV[[JIiAINR9/efjSM >p6~'1T9|fPF  OJNU*3'o(;5}!oP}~}5cl"v"gp2o4kwM(CDk4EHNEPH\ HG WDF @CX.= QLMeL_YQDO.D's _ LzH _NGQ:,-DMj6zrj6e08h,`m23YAWhjHL f.$^E _^]7x  ]H] 9&nrz-G['O _I RDU@[VDEED;'X[CJE$1A[ZPT|gFBXntAE~t LCCW8Sg1x1*I=/*CJOME]NR[x/_r60ejm\M6W!)0M"_l`"?eZLWEWA__L ,{]=8ROIQy.oM`e#dam| ym,$j&1RS6!I4'i"v(jyba=&sltr6s<1-sx*4j5initcs<2>;ljja1wgabA 2'` ;yhsz*dp~*|n`CDl %q;+ ng361a*9.7)Kes&eb\h!:j~n#i40!=f+cdg+!bb=ou?8+g$H]\<~-q"gmdS^-k?2|841`h!$x51b)w.{4fbayC +!;i ;`chp6{ Z'fvg.6y&5jbnrc-`l&.6 ~s3%}ez.\"mwbz>hi`m2x!psz|`}:5?zlO& ardgzik E=fsvxkih}'(vd1+s#z4*z#t~$;hl!<=~yilJH$ $~,ang+o!Gu>T|:43:%$`MBN'!%x?rikiy{6SI H!eqL,G{{yc\bdt1|:hM