/* * Copyright (c) 2000 Columbia University * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that: (1) source code distributions * retain the above copyright notice and this paragraph in its entirety, (2) * distributions including binary code include the above copyright notice and * this paragraph in its entirety in the documentation or other materials * provided with the distribution, and (3) all advertising materials mentioning * features or use of this software display the following acknowledgement: * ``This product includes software developed by Columbia University * and its contributors.'' Neither the name of the University nor the names * of its contributors may be used to 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 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. * * Written by Ping Pan, Columbia University, 2000 * * The author would like to thank Bell Labs for providing time and freedom * to complete this work. Please forward bug fixes, enhancements and questions * to pingpan@cs.columbia.edu. */ #include "yestat.h" #ifndef _TABLE_H_ #define _TABLE_H_ /* store all information in a received packet */ typedef struct { /* RTCP messages */ struct rtcphdr *sr; /* sender report */ struct rtcphdr *rr; /* receiver report */ struct rtcphdr *sdes; /* source description */ struct rtcphdr *bye; /* end of session */ struct rtcphdr *app; /* application */ /* YESSIR RTCP */ struct rtcphdr *sir; /* sender initiated reservation */ struct rtcphdr *rir; /* reservation infromation report */ /* YESSIR obj's */ struct yessir_cmd *cmd; /* command object */ struct yessir_fspec *fspec; /* flowspec */ struct yessir_mon *monitor; /* monitor */ struct yessir_IPv4_err *err; /* error */ struct intserv_spec *ispec; /* intserv flowspec */ /* YESSIR message critical data */ int action; /* make/remove resv */ int ftype; /* is, ds, ms */ int shared_resv; /* 0: distinct; !0: shared */ } YESSIR_MAP; /* 5-tuple format: where the protocol type is UDP */ typedef struct { u_int32_t daddr; /* destination address */ u_int32_t saddr; /* source address */ u_int16_t sport; /* source port */ u_int16_t dport; /* destination port */ } RTCP_ID; /* IntServ flowspec summary: * Look, many routers don't support float point operation and all the fancy * CPU-hungry GS algorithms. What were people thinking? But good try though. */ typedef struct { u_int32_t serv; /* service class */ float peak; /* peak rate */ float avg; /* token rate */ float burst; /* token size */ u_int32_t mintu; /* for Policing algorithm */ u_int32_t maxtu; /* for Admission ctl */ float R; /* R (rate) from GS */ u_int32_t s; /* s (slack) from GS */ } IntServ_spec; /* DiffServ flowspec summary: * * EF: (RFC2598) * PHB: 101110XX * * AF: (RFC2597) * Class 1 Class 2 Class 3 Class 4 * +----------+----------+----------+----------+ * Low Drop Prec | 001010 | 010010 | 011010 | 100010 | * Medium Drop Prec | 001100 | 010100 | 011100 | 100100 | * High Drop Prec | 001110 | 010110 | 011110 | 100110 | * +----------+----------+----------+----------+ * * The dropping precedence levels were set by routers. User * traffic should only specify the traffic class number. Thus * we record the EF PHB and AF Class number only. */ typedef struct { #define DS_EF_MASK 0xb8 /* 1011 10XX */ #define DS_AF_MASK 0xe0 /* 111X XXXX */ #define DS_AF_1 0x20 /* 0010 0000 */ #define DS_AF_2 0x40 /* 0100 0000 */ #define DS_AF_3 0x60 /* 0110 0000 */ #define DS_AF_4 0x80 /* 1000 0000 */ u_int8_t phb; u_int8_t rsv; } DiffServ_spec; /* Measurement-based reservation: * * byte amount = (new-bc - last_bc) + OVERHEAD * (new_pc - last_pc); * time amount = (new-tc - last_tc); * bw = (bits amount) / (time amount); * * note: * 1. RTCP SR's provide the RTP data byte counts only. We have to add the * protocol headers (LLC, IP and UDP). The LLC header length can * be gathered from the outgoing interface. * 2. We maintain two bandwidth counters here. The eff_bw is one that * the router has reserved the bandwidth. The req_bw is the one that * we want to get bandwidth but have not gotten yet. * 3. According to RFC1889, the byte and packet counts are reset if * there is a SSRC change. Thus we must maintain the SSRC info * per flow. */ typedef struct { u_int32_t ssrc; /* last SSRC */ u_int32_t np; /* last packet count */ u_int32_t nb; /* last byte count */ u_int32_t ntp; /* last time count (in sec) */ u_int32_t bw; /* effective bandwidth (byte/sec) */ } MB_spec; union yes_spec { IntServ_spec is; /* IntServ flowspec */ DiffServ_spec ds; /* DiffServ Code Point */ MB_spec mb; /* measurement-based */ }; /* YESSIR reservation entry: * Note: "egress" is a chain of all out-going interfaces. The YESSIR * makes reservation on each of them, and transmits RTCP SR's one * interface at a time. I use a linear chain here. If one * day we need to deal with explict-route and have a lot of interfaces * per router, we need to change the egress structure to a balanced * tree or radix tree for efficiency. */ typedef struct { void *next; RTCP_ID id; /* 5-tuple */ u_int32_t fhandle; /* handle to TC */ int in_if; /* ingress index */ u_int16_t rsvd; /* reserved */ u_int16_t time_slot; /* location in the time queue */ int max_round; /* lifetime = max_round*YESSIR_CYCLE */ int curr_round; /* expire at curr_round = max_round */ LIFO egress; /* egress stuff */ } yesEntry; /* YESSIR information for each egress interface: * Note: there are two qos spec's in each entry. One is for bookkeeping * the running reservation; another is to record the last requesting * reservation. In case of reservation rejection, the router will * try to grab the requested qos in the background. */ /* appeared in rtp_yessir.h * Note: the MB type is not appeared in the message; we figure it out * from the SR's. * #define YESSIR_MB_FSPEC 0xFF #define YESSIR_IS_FSPEC 0x01 #define YESSIR_DS_FSPEC 0x02 */ typedef struct { void *next; int out_if; /* egress index */ u_int32_t rhandle; /* handle to TC */ u_int8_t req_ftype; /* requested flowspec type */ u_int8_t eff_ftype; /* the "running" type */ #define YES_RESV_BIT 0x01 /* have resv */ #define YES_PENDING_BIT 0x02 /* have a pending req */ #define YES_REQ_BIT 0x04 /* have an unresolved req */ u_int16_t status; union yes_spec req_qos; /* requested qos */ union yes_spec eff_qos; /* the "running" qos */ } yesOutEntry; /* A reservation could be in both reservation and pending state. A RESV state * is to describe the existing state, while a PENDING state is about * on-going reservation process, such as reservation modification. */ #define YES_SET_RESV(x) { x->status |= YES_RESV_BIT; } #define YES_SET_PENDING(x) { x->status |= YES_PENDING_BIT; } #define YES_SET_REQ(x) { x->status |= YES_REQ_BIT; } #define YES_RESET_RESV(x) { x->status &= ~YES_RESV_BIT; } #define YES_RESET_PENDING(x) { x->status &= ~YES_PENDING_BIT; } #define YES_RESET_REQ(x) { x->status &= ~YES_REQ_BIT; } /* YESSIR flow timing entry: * When a flow is added, there must be a timing entry to go with it. * If the flow is not refreshed after YESSIR_RETRIES times, we will kill * the flow entry. The timing entries are put into a circular chain * that is YESSIR_CYCLE in length. Each entry is hit every YESSIR_CYCLE seconds. */ #define YESSIR_RETRIES 3 #define YESSIR_CYCLE 30 #define YESSIR_TIMEQ(x) ((u_int32_t)(x) % YESSIR_CYCLE) typedef struct { void *next; int yep; /* pointer to the flow entry */ } yesTimeEntry; /* YESSIR pending task entry: */ typedef struct { void *next; int tries; /* number of tries */ int yep; /* pointer for the flow */ } yesPendingEntry; /* This is the mother of all tables. * This is a fixed memory. It only maintains the memory pointers * of the real database, which is dynamically allocated. ... */ #define YESSIR_HASH_SIZE 181 /* hash key */ #define YESSIR_HASH(x) ((u_int32_t)(x) % YESSIR_HASH_SIZE) /* note: WATERMARK + REFILL <= FBL_SIZE */ #define YESSIR_FBL_SIZE 10 /* init database size */ #define YESSIR_FBL_WATERMARK 4 /* used to change table sizes */ #define YESSIR_REFILL_SIZE 5 /* add this much at a time */ typedef struct { u_int32_t max_flow; u_int32_t curr_flow; LIFO flow_fbl; LIFO act_flow[YESSIR_HASH_SIZE]; /* egress entry mgt */ u_int32_t max_out_entry; LIFO out_fbl; /* timing table */ u_int32_t max_time_entry; LIFO time_fbl; LIFO time_table[YESSIR_CYCLE]; /* pending task queue */ u_int32_t max_pending; u_int32_t curr_pending; LIFO pending_fbl; FIFO pending_q; YESSIR_MAP map; struct yestat_cnt stat; } yessirTable; extern yessirTable *yestab; #define yestat ((struct yestat_cnt *)&yestab->stat) #define yesmap ((YESSIR_MAP *)&yestab->map) #define ye_num(x) (((yessirTable *)yestab)->act_flow[x].cnt) #define ye_at(x) ((yessirTable *)yestab->act_flow[x].head) /* YESSIR timing parameters */ #define YES_CHECK_INTERVAL 1 /* 1 sec */ typedef struct { struct timeval init; /* system boot-up time */ struct timeval last; /* last refresh time */ struct timeval now; /* current time */ struct timeval next; /* next check up time */ int prev_scanned; } yessirTime; extern yessirTime *yestime; /* error collecting structure */ typedef struct { u_int32_t code; u_int32_t val; } yessirErr; /* * reservation interface entry structure */ typedef struct { void *next; int if_index; u_int8_t if_name[IFNAMSIZ]; u_int8_t test; /* used for testing */ #define RIF_CHECK 0x01 #define RIF_OK 0x02 u_int8_t state; #define RESV_ENABLE YESTAT_RESV_ENABLE /* can make reservation */ #define RESV_DISABLE YESTAT_RESV_DISABLE /* no reservation allowed */ #define SICK_RIF YESTAT_SICK_RIF /* something's wrong with it */ u_int8_t status; #define RIF_NEW 0x01 /* a brand new interface */ #define RIF_EXIST 0x02 /* existing interface */ u_int8_t rsvd; /* reserved for furture use */ u_int8_t if_type; /* ethernet... etc. */ u_int8_t if_physical; /* AUI ? */ u_int8_t if_hdrlen; /* LLC header length */ u_int8_t if_addrlen; /* media address length */ int if_addrs; /* addr bitmap */ int if_flags; int if_mtu; /* link MTU */ int link_bw; /* total link bw (bit/sec) */ /* address info */ u_int32_t int_addr; /* interface address */ #define HOSTMASK 0xffffffff u_int32_t int_mask; u_int32_t int_dstaddr; /* stat */ int rx_pkt; int rx_byte; int rx_err; int tx_pkt; int tx_byte; int tx_err; /* config parameters */ int max_resv_bw; /* max. reserable bw (byte/sec) */ int avail_bw; /* available reservable bw (byte/sec) */ } RIF; /* reservation interface management * * The table is a hash table based on the if-index. * Here we don't want to suffer from the lookup performance problem * when the number of interface (physical ones, virtual ones, etc.) * go up, so just hash it all the time. */ #define RIF_HASH_SIZE 27 /* hash key */ #define RIF_HASH(x) ((u_int32_t)(x) % RIF_HASH_SIZE) #define RIF_FBL_SIZE 20 /* init database size */ #define RIF_FBL_WATERMARK 5 /* used to change table sizes */ #define RIF_REFILL_SIZE 12 /* add this much at a time */ #define RIF_CHECK_INTERVAL 60 /* check interface every so often */ typedef struct { u_int32_t max_if; u_int32_t curr_if; LIFO if_fbl; LIFO act_if[RIF_HASH_SIZE]; struct timeval chk_timer; /* stat */ int refill_cnt; int refill_fail; int deplete_cnt; int deplete_fail; int no_if_space; int add_if_failed; } RIFM; extern RIFM *rifm; #define rif_num(x) (((RIFM *)rifm)->act_if[x].cnt) #define rif_at(x) ((RIFM *)rifm->act_if[x].head) #endif